2011高教社杯全國大學生數(shù)學建模競賽承諾書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：D我們的參賽報名號為（如果賽區(qū)設置報名號的話）：J3502所屬學校（請?zhí)顚懲暾娜何靼矚W亞學院參賽隊員（打印并簽名）：1.胡勇馬璐指導教師或指導教師組負責人（打印并簽名）：教練組日期：2011年9月2日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：2011高教社杯全國大學生數(shù)學建模競賽編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號快遞公司員工送貨路線優(yōu)化摘要本文是對送貨情況求最優(yōu)路徑問題，題中給出送貨員的最大載重量和最大載貨體積的限制，在有時間和無時間的限制下，送貨員要以耗時最少，所走路程最短將貨物送達目的地，我們先依據(jù)位置點的X坐標和Y坐標找出各個位置點，再根據(jù)相互連通的信息，利用matlab數(shù)學軟件畫圖連接可以連通的位置點，建立合理優(yōu)化的路線。問題一，根據(jù)題中所給數(shù)據(jù)可求出30件貨物重量為48.5<50公斤、體積為0.88<1立方米，故在問題一的模型建立中我們不用考慮質量、體積的約束。只需要考慮路線的問題.利用Floyd算法求出所有點從一個點出發(fā)再回到這個點的最短路徑，并且路徑不重復，最后總體量化處理去除重復的點和重復的路徑，找出最短的路徑，再利用某一段路徑逐一替換其中的某段路徑，使得路徑最短為止。結果如下：最優(yōu)路徑為：oT26T21r17T14r16T23T32T35T38T36T38T43T42r49r42r45r40r34r31r27r39r27r31r24r19r13r18ro最短送貨路徑的總長為：54985米，總時間（包括交貨時間）為：226.8分。問題二，送貨員從早上8點上班開始送貨，要將1-30號貨物送達指定地點，并且時間不能超過指定的時間，這樣就增加了時間上的約束，但沒有要求送完貨返回到出發(fā)點。所以我們必須在滿足各點的時間要求前提下，尋找一條最優(yōu)的路徑。我們根據(jù)時間優(yōu)先的原則將時間劃分為四個階段，分別為：8:00-9:00、9:00-9:30、9:30-10:15、10:15-12:00，然后朝時間最早的地點方向出發(fā)，并且一個時間段最后的地點要與下個時間段第一個地點接近，這樣從一個時間段的地點到另一個時間段的地點不會浪費太長時間，由于時間的劃分，將送貨地點也劃分成了多塊，這樣可以采用窮舉法比較出其中耗時最短的路徑，前三段時間送貨員都在指定時間內完成了內務，但是走完第四時間段地點后此時的時間為12:30，已超出送貨所要求的時間。所以即使按最佳路徑走也無法按要求完成，但為了滿足時間優(yōu)先原則，使貨物盡早到達相應地點結果如下：最優(yōu)路徑為：or18r13r19r24r31r34r40r45r42r49r42r43r38r36r27r39r27r31r26r21r17r14r16r23r32總路程為：51928米；總時間（包括交貨時間）為：216分。問題三，送貨員要將100件貨物以最快完成路線送到指定地點，雖然沒有時間的限制，但是要考慮貨物的總重量和總體積，根據(jù)貨物信息可以得出100件貨總質量為148公斤，總體積為2.8立方米，送貨員最大載重50公斤，所帶貨物最大體積1立方米，所以送貨員最少分三次送貨，半途要返回o取貨，可以根據(jù)圖的遍歷和最小生成樹把整個圖分成多個路徑最小的區(qū)域，根據(jù)重合的地點和鄰近的路徑在滿足重量和體積的情況下合并，為了方便和省時，最后將多條路徑合并成三條。號線路徑的最短回路為：or26r31r27r36r45r40r47r40r50r49r42r43r38r35r32r23r17r21ro號線路徑的最短回路為：or26r31r27r39r27r31r24r19r25r29r22r20r22r30r28r33r46r48r44r41r37r40r34r31r26ro號線路徑的最短回路為：or18r13r11r12r15r5r2r4r3r8r1r6r1r7r10r9r14r16r23r17r21ro送貨員將100件貨物送完的總路程和總時間為：總路程為：142463米；總時間為：656.16分。關鍵詞：Floyd算法窮舉法最小生成樹圖的遍歷一、問題重述在物流行業(yè)中，送貨員需要以最快的速度及時將貨物送達，而且他們往往一人送多個地方?，F(xiàn)有一快遞公司，一送貨員要按圖1中的路徑需將貨物送至城市內多處，要求設計送貨方案，使所用時間最少。并且送貨員只能沿圖中那些連通線路行走，而不能走其它任何路線。各件貨物的相關信息見表1，50個位置點的坐標見表2。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時。每件貨物交接花費3分鐘，同一地點有多件貨物按照每件3分鐘交接計算?，F(xiàn)在送貨員要將100件貨物送到50個地點。請完成以下問題。若將1?30號貨物送到指定地點并返回。設計最快完成路線與方式。給出結果。要求標出送貨線路。假定該送貨員從早上8點上班開始送貨，要將1~30號貨物的送達時間不能超過指定時間，請設計最快完成路線與方式。要求標出送貨線路。若不需要考慮所有貨物送達時間限制（包括前30件貨物），現(xiàn)在要將100件貨物全部送到指定地點并返回。設計最快完成路線與方式。要求標出送貨線路，給出送完所有快件的時間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時間。二、問題分析2.1問題一分析要將1-30號貨物以最快完成路線送往指定的地點并返回。首先要考慮的是貨物的重量和體積，如果貨物超出題中要求的標準M=1Lm/50kg，就要考慮分到幾次送貨，i=1每次送往哪幾個地點，并且中途返回原點取貨等因素制定最短路線；反之，沒有超出標準M=Zmt<50kg，故在此模型建立中我們不用考慮質量、體積的約束，只需要考慮i=1路線的問題。我們先依據(jù)位置點的X坐標和Y坐標找出各個位置點，再根據(jù)相互連通的信息，連接可以連通的位置點，根據(jù)matlab計算出各連通點間的距離，利用Floyd算法求出任意兩點間最短路徑，找出所有從某點出發(fā)到某點的最短路徑，最后總體量化處理去除重復的點和重復的路徑，找出最短的路徑，再利用某一段路徑逐一替換其中的某段路徑，使得路徑最短為止。2.2問題二分析送貨員從早上8點上班開始送貨，要將1-30號貨物送達指定地點，并且時間不能超過指定的時間，首先我們將送往貨物的地點按時間限制劃分為四個階段：8:00-9:00、9:00-9:30、9:30-10:15、10:15-12:00四個階段。然后朝時間最早的地點方向出發(fā)，并且一個時間段最后的地點要與下個時間段第一個地點接近，這樣從一個時間段的地點到另一個時間段的地點不會浪費太長時間，然后選擇一條最短的路徑在指定的時間內完成任務，并計算出路程和時間。2.3問題三分析送貨員要將100件貨物以最快完成路線送到指定地點，雖然沒有時間的限制，但是要考慮貨物的總重量和總體積，根據(jù)貨物信息可以得出100件貨總質量為148公斤，總體積為2.88立方米，送貨員最大載重50公斤，所帶貨物最大體積1立方米，所以送貨員最少分三次送貨，半途要返回o取貨，那么在分區(qū)送貨時不但要考慮貨物的重量和體積，還要考慮最后送貨的地點要與o最近，這樣才能以最快的路線完成送貨。我們首先根據(jù)圖的遍歷和最小生成樹把整個圖分成多個路徑最小的區(qū)域，根據(jù)重合地點和鄰近路徑在滿足重量和體積的情況下合并，為了方便和省時，最后將多條路徑合并成三條。三、模型假設1、假設送貨員只能沿如圖路線圖行駛，不能走其他的任何路線2、假設同一地點有多件貨物按照每件3分鐘交接計算3、假設送貨員在送貨時無路障、無意外，平均速度總為24公里/小時4、假設所有的距離都精確到米，所有的時間都精確到秒四、符號說明mti號貨物質量M總質量總體積匕i號貨物的體積斗j條路線的總長度r每件貨物交接時間T總時間速度n貨物數(shù)量五、模型的建立與求解5.1問題一模型建立與求解5.1.1模型準備（Floyd算法）設A=（a）n“為賦權圖G=（V,E,F）的權矩陣，電表示從Vj到匕?點的距離”〃表示從V,到％.點的最短路中一個點的編號。賦初值.對所有i,j,d=a.,勺=j,k=1.轉向②。更新d,r.對所有i,j若d+dVd,則令di=d+d,r=k,轉向③。ij,j./7//‘,V,ikkjij，/、jikkj，ij,終止判斷.若k=n終止；否則令k=k+1,轉向②。最短路線可由r?得到。5.1.2模型的建立與求解(一)我們首先對題中所給的數(shù)據(jù)進行匯總分析，判斷貨物是否超出標準，經過計算得出30件貨物總重量和總體積分別為M二四mt=48.5(kg)，V二四匕=0.88(m3)，所i=1i=1以均未超出送貨員的載重，送貨員可以一次性將貨物送完。依據(jù)位置點的X坐標和Y坐標找出各個位置點，再根據(jù)相互連通的信息，連接可連通的位置點，利用matlab編程計算出各連通點間的距離，如表1：路徑距離路徑距離S0。261392S42j452352S26^212192S45j403271S21^171824S40j341631S17j142196S34j312325S14。162608S31j271068S16。232098S27j391780S23。321312S31j245039S32。351114S31j182104S35r381410S18j133113S38j361537S18jO2182S38j432618S24j192259S43j42918S19j133456S42j491971\\表1(二).利用Floyd算法求出所有從一個點出發(fā)再回到這點的最短路徑，并且路徑不重復，如下：o-?26-?21—?o21T17T14T2114r16T23T17T1423r32r35r38r36r21r17r2338r43r42r45r36r3845r40r34r31r27r36r4531r18ror26r31總體量化處理去除重復的點和重復的路徑得到從o點出發(fā)回到o點得總路徑為：or26r21r17r14r16r23r32r35r38r36r38r43r42r49r42r45r40r34r31r27r39r27r31r24r31r18r13r18ro計算總路徑的距離為：S29=殍s.=56240(m)j由題中圖1和表3可知上條路徑從31ro還有一條為：31r24r19r13r18ro，兩條路徑進行比較，取最短的一條路徑。計算兩條路線的總長：<1>.31r24r31r18r13r18ro的路線距離：

S6=1Ls.=1780+1780+2104+3113+3113+2182=14072(m)j=1＜2＞.31—24—19—13—18—o的路線距離：S5=￡s.=1780+2259+3456+3113+2182=1282(m)j=1根據(jù)計算結果明顯可看出＜2＞的路線距離小于＜1＞的路線距離，所以用＜2＞路線替換＜1＞的路線。最短路線如下：oT26T21r17T14r16T23T32T35T38T36T38T43T42T49T42r45r40r34r31r27r39r27r31r24r19r13r18ro最短路線的總長度為：S28=蕓s.=54958(m)j總時間(包括交貨時間)為：T=_2^+1x30=54920.7+3x30=226.8(min)v+6024000+60總線路如圖(1)：160001400012000100008000600040002000020004000600080001600014000120001000080006000400020000200040006000800010000120001400016000圖（1）0本題利用分塊思想，首先找出8:00-9:00、9:00-9:30、9:30-10:15、10:15-12:00四個時間段的位置點，然后應用局部窮舉法求解每一塊的最佳路徑，并且要考慮一個時間段最后的地點要與下個時間段第一個地點接近，這樣可以節(jié)省從一個時間段的地點到另一個時間段的地點所用的時間。其基本步驟為：所給的時間段分塊所得結果如表2所示:時間段地點貨號131

8:00-9:00時間段1822420313、219:00-9:30時間段342440254511、14、2638109:30-10:15時間段42154312、164927146163017721510:15-12:00時間段238、29264、232719、22329、17、2836183913表2根據(jù)上表可知每個時間段要送貨物的地點和貨物的數(shù)量，采用局部窮舉法求最短路徑，并判斷其總的送貨時間是否滿足指定的時間。其基本步驟為：（1）、第一時間段8:00——9:00之間送到的站點為：13、18、24,送的貨物數(shù)量為3件，因為下個時間段第一個地點是31，所以這個時間段的出發(fā)點是o點，終點應該是24點，根據(jù)第一問可知有兩種行程路線，分別為oT18T13T18r31r24路徑和\or18r13r19r24路徑。由時間公式：T=——+1xn可知，每件貨物交接花費t=3v+60分鐘一定，數(shù)量n一定，送貨員的平均速度為V=24米/時一定，則要求時間最短，也就是行程的路徑最短。由問題一的結果知or18r13r19r24的路徑最短，所用的總時間（包括交貨時間）為：1101024000+60+3x3r37(min)所以送貨員走完第一時間段地點后此時的時間為8:37，在指定時間范圍之內。所以最佳路線為：or1101024000+60+3x3r37(min)（2）、第二時間段9:00-9:30之間送到的地點為：31、34、40、45，送的貨物數(shù)量為7件，因為下個時間段第一個地點是42,所以這個時間段的終點應該是45點，在送第一時間段地點時用了37分鐘，此時時間為8:37，那么從上個時間段到這個時間段也需要..、....一一..、..S.時間，從點24到這個時間段點31的路程為1780米，根據(jù)時間公式T=S可計算出這段路v用時為5分鐘，所以在8:42就到達了這個時間段31點。根據(jù)Floyd算法和窮舉法得到最佳路線：31r34r40r45，所用的總時間（包括交貨時間）為：T=-^+1xn=—71^3—+3x7r39（min）v+6024000+60

所以送貨員走完第二時間段地點后此時的時間為9:21，剛好在指定時間范圍之內。所以最佳路線為：31—34—40—45。、第三時間段9:30-10:15之間送到的地點為：38、42、43、49,送的貨物數(shù)量為5件，因為下個時間段第一個地點是36或32,所以這個時間段的終點應該是38點，在送第二時間段地點時用了39分鐘，此時時間為9:21，那么從上個時間段到這個時間段也S需要時間，從點45到點42的路程為2352米，根據(jù)時間公式T=S可計算出這段路用時為v6分鐘，所以在9:27就到達了這個時間段42點。根據(jù)Floyd算法和窮舉法得到最佳路線：42r49T42r43T38，所用的總時間(包括交貨時間)為：T=—禹—+1xn=——7*9——+3x5^34(min)v+6024000+60所以送貨員走完第三時間段地點后此時的時間為9:55，在指定時間范圍之內。所以最佳路線為：42r49r42r43r38。、第四時間段10:15-12:00之間送到的地點為:14、16、17、21、23、26、27、32、36、39,送的貨物數(shù)量為13件，根據(jù)Floyd算法和窮舉法可得到兩條路徑，分別為：36r27r39r27r31r26r21r17r14r16r23r32或35r32r23r16r14r17r21r26r31r27r39r27r36。對兩條線路優(yōu)化處理：＜1＞、36r27r39r27r31r26r21r17r14r16r23r32路徑的總長度和時間為：S11=丈七=2204+1780+1780+1068+1537+2192+1824+2196+2608+2098+1312j=20597(m)2059724000+60+3x13r91(min)2059724000+60+3x13r91(min)<2>、35r32r23r16r14r17r21r26r31r27r39r27r36路徑的總長和時間為：S12=產s=1410+1114+1312+2098+2608+2196+1824+2192+1537+1068+1780j+1780+2204=23121(m)T=^!^+1xn=23121+3x13r97(min)v+6024000+60根據(jù)分析結果我們選＜1＞的路線送貨。在送第三時間段地點時用了39分鐘，此時時間為9:55,那么從上個時間段到這個時間段也需要時間，從點38到點36的路程為1537米，根據(jù)時間公式T=S可計算出這段路用時為4分鐘，所以在9:59就到達了36點。v再根據(jù)以上算出36r27r39r27r31r26r21r17r14r16r23r32路徑的時間為91分鐘，所以送貨員走完第四時間段地點后此時的時間為12:30，已超出送貨所要求的時間。所以即使按最佳路徑走也無法按要求完成，但為了滿足時間優(yōu)先原則，使貨物盡早到達相應地點，最佳路線為：36r27r39r27r31r26r21r17r14r16r23r32。因此，根據(jù)以上所給的時間段所得結果可知最佳總路線為：?！?8—13—19—24—31—34—40—45—42—49—42—43—38—36—27—39T27T31T26T21T17T14T16T23T32總路程為：：S25=51928（m）；總時間（包括交貨時間）為：T=216（min）。送貨員行走路徑如圖（2）：1600014000120001000080006Q00400020000020001600014000120001000080006Q004000200000200040006000圖（2）10000120001400016000Kruskal算法是每次選擇n-1條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會產生環(huán)路的具有最小耗費的邊加入己選擇的邊的集合中。注意到所選取的邊若產生環(huán)路則不可能形成一棵生成樹。Kruska1算法分e步，其中e是網絡中邊的數(shù)目。按耗費遞增的順序來考慮這e條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。圖的廣度優(yōu)先遍歷（BFS）：廣度優(yōu)先搜索算法（又稱為寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，具有“先進先出”的特點；具體過程為：首先訪問圖中指定的起始點并將其標記為已訪問，然后由該點出發(fā)訪問與它相鄰的所有頂點，并均標記為以訪問，然后在按照上述的方法，訪問沒一個頂點的所有未被訪問過得鄰接頂點，并標記為已訪問過；下一步再從這些頂點出發(fā)訪問與它們相鄰接的尚未被訪問的頂點，如此循環(huán)，直到所有的頂點均被訪問過為止。若G是連通圖，則遍歷完成；否則，在該圖中另選一個尚未訪問的頂點作為新源點繼續(xù)上述的搜索過程，直至圖中所有頂點均已被訪問為止。5.3.2模型的建立與求解根據(jù)貨物信息可以得出100件貨總質量為148公斤，總體積為2.8立方米，送貨員最大載重50公斤，所帶貨物最大體積1立方米，從方便和節(jié)省時間來分析送貨的趟數(shù)越少越好，所以送貨員分三次送貨，根據(jù)圖的遍歷和最小生成樹把整個圖分成多個路徑最小的區(qū)域，根據(jù)重合地點和鄰近路線在滿足重量和體積的情況下合并，并且貨量也不

能過少，每個區(qū)域的貨物總重量不能小于48公斤，體積不能小于0.8立方米，這樣才能完成任務。具體分四步完成。第一步將整個路徑分成多個最小的路徑；第二步計算每條路徑的總重量和總體積；第三步將重合地點和鄰近路徑進行合并，計算合并后的貨物總重量和總體積，判斷總重量是否在48-50公斤區(qū)間，體積是否在0.8-1立方米之間，如果不滿足進行改進路徑；第四步計算改進后的貨物總重量、總體積和總時間，畫出路線。（1）、根據(jù)圖的遍歷和最小生成樹把整個路徑分成多個最小的路徑，如圖（3）：1600014000120001000080006000400020000。200040006000圖（3）10000120001400016000根據(jù)圖（3）寫出A、B、C、D、E、F六條路徑所經過的地點：A路徑所經過的地點：oT26T31T27T39B路徑所經過的地點：27—36—38—35—32—23—16—14—17—21C路徑所經過的地點：36—45—40—47—40—50—49—42—43—38D路徑所經過的地點：o—18—13—11—12—8—3—1—6—1—7—10—9—14E路徑所經過的地點：3—4—2—5—15—12F路徑所經過的地點：31—24—19—25—29—22—20—22—30—28—33—46—48—44—41—37—34（2）、根據(jù)附錄表1計算A、B、C、D、E、F六條路徑每條路徑貨物的總重量和總體積，如表3：路徑重量體積A14.440.2844B39.90.6912C24.460.4867D21.870.4592E7.520.1138F41.380.7027（3）、根據(jù)重合地點和鄰近路徑進行合并，將B、C兩條路徑合并一條為1號線路徑，A、F兩條路徑合并一條為2號線路徑，D、E兩條路徑合并一條為3號線路徑。計算1線、2線、3線路徑的總重量和總體積，如下：1號線路徑貨物的總重量為：60.36公斤，總體積為：1.1179立方米

2號線路徑貨物的總重量為：55.82公斤，總體積為：0.9871立方米3號線路徑貨物的總重量為：29.39公斤，總體積為：0.5730立方米根據(jù)結果可知，1號線和2號線路徑貨物的總重量都超出標準，3號線路徑貨物總重量低于標準，根據(jù)圖（3）把臨近的地點和路徑進行分讓，1號線路徑與3號線臨近，所以將1號線路徑的部分地點分讓給3號線路徑，1號線路徑的B線與3號線路徑的D線最近，可將B線經過的23、16、14、17、21地點也讓D線經過如圖（4），這樣可以把重復經過地點的貨物分成多次，就能滿足貨物總重量和總體積的標準。16000140001200010000800060004000200000200040006000800010000120001400016000圖（4）（4）、計算去除重復點后1線、2線、3線路徑的貨物總重量和總體積為:1號線路徑貨物的總重量為：36.66公斤，總體積為：0.7206立方米2號線路徑貨物的總重量為：45.01公斤，總體積為：0.8062立方米3號線路徑貨物的總重量為：36.01公斤，總體積為：0.6848立方米重復地點貨物的重量和體積如表4：路徑地點貨物重量貨物體積1號線與2號線路徑重復經過的地點264.390.0619275.120.0687312.580.0622401.630.04841號線與3號線路徑重復經過的地點173.660.0778213.530.0724238.260.1469表4根據(jù)表知，1號線路徑與2號線和3號線路徑都有重復經過的地點，根據(jù)總重量M<50公斤總體積V<1立方米的標準將重復地點的貨物盡量分給2號線和3號線路徑，所以將1號線和2號線路徑重復地點26、27的包裹分到1號線路徑送，地點31、40的包裹分到2號線路徑送；將1號線和3號線路徑重復地點21的包裹分到1號線路徑送，地點17、23的包裹分到3線路徑送。劃分好后1號線、2號線、3號線路徑貨物的總重量和總體積如下：1號線路徑貨物的總重量為：49.75公斤，總體積為：0.9536立方米

2號線路徑送貨的總重量為：49.32公斤，總體積為：0.9368立方米3號線路徑貨物的總重量為：48.93公斤，總體積為：0.9096立方米三條路徑的最短回路分別為：號線路徑的最短回路為：o—26—31—27—36—45—40—47—40—50—49T42r43T38T35T32T23T17T21ro號線路徑的最短回路為：or26r31r27r39r27r31r24r19r25r29r22r20r22r30r28r33r46r48r44r41r37r40r34r31r26ro號線路徑的最短回路為：or18r13r11r12r15r5r2r4r3r8r1r6r1r7r10r9r14r16r23r17r21ro根據(jù)附表一計算三條路徑的總路程和總時間(不包括貨物交接時間)分別為：1號線路徑總路程為：S19=尤s.=42173(m)，總時間為：T=_^也=105.43(min)j2號線路徑總路程為：S26=藝Sj=48849(m)，總時間為：T=‘26=122.12(min)ju3號線路徑總路程為：S22=￡Sj=51441(m)，總時間為：T=‘22=128.60(min)j送貨員將100件貨物送完的總路程和總時間為：總路程：S總=S19+S26+S22=42173+48849+51441=142463(m)總時間：T=^總+1xn=142463+3x100=656.16(min)v+6024000+60總線路如圖(5)：1400012000100008000600040002000020004000600080001000012000140001200010000800060004000200002000400060008000100001200014000160000六、模型評價與推廣6.1模型評價優(yōu)點：本模型在建模過程中，對送貨員送貨的過程以及交接時間做了合理的簡化，建立了最短路模型，模型簡單、清晰，具有一定的普遍意義。本文所建模型中，提供了較多的圖形解說，使得文章直觀易懂，有較高可讀性和可行性。整個模型都是將整體劃分成個體，這樣簡化了模型建立難度，具有較強的實用性和通用性。缺點：Floyd算法時間復雜度比較高，不適合大量數(shù)據(jù)的計算。由于數(shù)據(jù)較多，難以對模型結果進行驗證，只能一步一步的對模型進行優(yōu)化。首先求局部最優(yōu)解，再逐一替換求全局最優(yōu)解，計算量大；本文忽略了送貨員送貨途中遇到紅綠燈問題，且看成一直勻速行駛，可能造成結果不精確。6.2模型的推廣本模型不僅適應于快遞公司的送貨問題，還可用于一般送貨和交通調度、出租車載客、郵遞員送信和自駕旅行等問題，既有普遍性。七、參考文獻吳躍合者:李樹全陳端兵，數(shù)據(jù)結構與算法，機械工業(yè)出版社，2010年02月范曉平;最小生成樹（MST）的“分級選樹”算法[J];西南交通大學學報；1983年01期周品，趙新芬，數(shù)學建模與仿真，國防工業(yè)出版社，2009年4月八、附錄附表

3500圖1快遞公司送貨地點示意圖O點為快遞公司地點，O點坐標（11000,8250），單位：米表1各貨物號信息表貨物號送達地點重量（公斤）體積（立方米）不超過時間1132.500.03169：002180.500.03549：003311.180.02409：304261.560.035012：005212.150.030512：006141.720.010012：007171.380.010912：008231.400.042612：009320.700.048112：0010381.330.021910：1511451.100.02879：3012430.950.022810：1513392.560.059512：0014452.280.03019：3015422.850.019010：1516431.700.078210：1517320.250.041212：0018361.790.018412：0021310.8022272.2523261.5724342.8025401.1426450.6827491.3528320.5229232.9130161.20311.26321.150.04200.01080.00180.02100.01030.01550.03820.01440.00200.04870.04290.02500.05019：009：3012：0012：009：309：309：3010：1512：0012：0012：00331.63341.23351.41360.54370.70380.76392.1440414243444546474849505152535455565758596061101112131415161718192021222324252627282930311.071.372.390.991.660.452.041.952.123.872.011.380.391.661.242.411.260.421.721.340.060.600.04830.00060.03870.00670.01290.03460.00870.01240.05100.04280.00480.04910.02090.00980.03240.05540.02620.03240.04190.00010.05020.05340.00120.00590.02240.05800.03720.04020.027462322.190.050363331.890.049464341.810.032565351.000.005566361.240.017767372.510.036168382.040.011069391.070.044070400.490.032971410.510.009472421.380.045573431.310.012174441.260.000575450.980.041376461.350.024177472.120.023078480.540.054279491.010.056680501.120.028481250.790.001182462.120.049283322.770.003484232.290.005485200.210.049086251.290.008887191.120.024988410.900.003889462.380.043490371.420.002091321.010.030092332.510.013393361.170.002094381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.0493表250個位置點的坐標位置點X坐標（米）Y坐標（米）19185500214455603727043735526206100807100258716091384510119351178501265851376301413405152125161536517141651888251958552078021127702222002314765247790570670995143522802525268030503545418552005325597570457385807581658355856088359055933025443595252610860963527103851050028565976529258098653015659955