【正文】 送貨路線設(shè)計(jì)問(wèn)題摘要：本文主要討論的是送貨路線的設(shè)計(jì)問(wèn)題。總體的解題思路是將問(wèn)題中的地點(diǎn)、路線分別抽象成數(shù)學(xué)中的點(diǎn)、線，然后利用圖論的相關(guān)知識(shí)理論來(lái)考慮這些問(wèn)題。最后，設(shè)計(jì)方法程序，并利用Matlab運(yùn)行，解決問(wèn)題。問(wèn)題一要求根據(jù)130號(hào)貨物設(shè)計(jì)一條最快的送貨路線，由于貨物的總質(zhì)量mzong和總體積vzong（mzong =。vzong =）均未超出最大限度50和1，所以，該問(wèn)題可轉(zhuǎn)化成求最短路問(wèn)題。解決方法：首先，寫(xiě)出每個(gè)點(diǎn)的帶權(quán)鄰接矩陣；然后，運(yùn)用Floyd求任意兩點(diǎn)間的最短距離；最后，用H圈構(gòu)造運(yùn)算法,并通過(guò)矩陣翻轉(zhuǎn)的二邊逐次修正法，得到最短距離和最快完成路線圖，如下:o→18→13→24→31→27→39→34→40→45→49→42→43→36→38→32→ 23→16→14→17→21→26→olucheng =+004米 t=lucheng/1000*v+t*21/60=問(wèn)題二設(shè)計(jì)一條路線，要求在時(shí)間允許的條件下，使總路程最小。解決思路是利用問(wèn)題一中的方法，結(jié)合每個(gè)貨物的時(shí)間限制，最終得到路線圖，如下：o→18→13→24→31→27→39→34→40→45→49→42→43→38→36→32→ 23→16→14→17→21→26→olucheng2= +004 t2=lucheng2/1000*v+t*21/60= 問(wèn)題三將1100號(hào)貨物全部送到指定地點(diǎn)，mzong=148，vzong=，顯然不能一次性送到。解題思想是根據(jù)倉(cāng)庫(kù)到各個(gè)點(diǎn)的最小距離將地點(diǎn)分為三部分，分別派送。分完組后在利用第一問(wèn)的思想給予優(yōu)化求出最佳的H圈. 得到的送貨路線分別為: 第一組路線：o→26→31→27→39→27→36→45→40→47→40→50→49→42→43→38→35→32→23→17→21→o；第二組路線：o→26→31→34→40→37→41→44→48→46→33→28→30→22→20→22→29→25→19→24→31→26→o；第三組路線：o→21→17→23→16→14→9→10→7→1→6→1→8→3→4→2→5→15→12→11→13→1811→o。送貨時(shí)間為:t3=lucheng/1000*v+t*100/60=關(guān)鍵詞：圖論 帶權(quán)鄰接矩陣 Floyd算法 最優(yōu)Hamilton圈 二邊逐次修正一、問(wèn)題重述現(xiàn)今社會(huì)網(wǎng)絡(luò)越來(lái)越普及，網(wǎng)購(gòu)已成為一種常見(jiàn)的消費(fèi)方式，隨之物流行業(yè)也漸漸興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人送多個(gè)地方，請(qǐng)?jiān)O(shè)計(jì)方案使其耗時(shí)最少?，F(xiàn)有一快遞公司，庫(kù)房在圖1中的O點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請(qǐng)?jiān)O(shè)計(jì)送貨方案，使所用時(shí)間最少。該地形圖的示意圖見(jiàn)圖1，各點(diǎn)連通信息見(jiàn)表3，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關(guān)信息 見(jiàn)表1，50個(gè)位置點(diǎn)的坐標(biāo)見(jiàn)表2。 假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時(shí)。假定每件貨物交接花費(fèi)3分鐘，為簡(jiǎn)化起見(jiàn)，同一地點(diǎn)有多件貨物也簡(jiǎn)單按照每件3分鐘交接計(jì)算?，F(xiàn)在送貨員要將100件貨物送到50個(gè)地點(diǎn)。請(qǐng)完成以下問(wèn)題。1. 若將1~30號(hào)貨物送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。給出結(jié)果。要求標(biāo)出送貨線路。2. 假定該送貨員從早上8點(diǎn)上班開(kāi)始送貨，要將1~30號(hào)貨物的送達(dá)時(shí)間不能超過(guò)指定時(shí)間，請(qǐng)?jiān)O(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路。3. 若不需要考慮所有貨物送達(dá)時(shí)間限制(包括前30件貨物)，現(xiàn)在要將100件貨物全部送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快件的時(shí)間。由于受重量和體積限制，送貨員可中途返回取貨。可不考慮中午休息時(shí)間。以上各問(wèn)盡可能給出模型與算法。 圖1 快遞公司送貨地點(diǎn)示意圖O點(diǎn)為快遞公司地點(diǎn)，O點(diǎn)坐標(biāo)(11000,8250),單位：米二、模型假設(shè)，參與計(jì)算。，不會(huì)因拋錨等現(xiàn)象而耽誤時(shí)間；，那么這些物品在同一次中運(yùn)送；；；，無(wú)單向路線；。三、符號(hào)說(shuō)明1問(wèn)中涉及到的符號(hào)a各貨物號(hào)信息（貨物號(hào)、運(yùn)送地點(diǎn)、重量、體積和最晚時(shí)間）矩陣b 50個(gè)位置點(diǎn)的坐標(biāo)矩陣c互通點(diǎn)信息矩陣d任意兩相通兩點(diǎn)間距離e對(duì)應(yīng)兩相通兩點(diǎn)間距離e1對(duì)e進(jìn)行去重后得到的矩陣f帶權(quán)鄰接矩陣D任意兩點(diǎn)間最小距離矩陣u初始H圈mzong貨物的總質(zhì)量vzong貨物的總體積luxian最短路線lucheng最小路程t1最短時(shí)間t貨物交接時(shí)所需時(shí)間（3分鐘）v送貨員的行駛速度(24千米每小時(shí))2問(wèn)中涉及到的符號(hào)luxian2最短路線lucheng2最小路程t2最短時(shí)間3問(wèn)中涉及到的符號(hào)luxian3最短路線lucheng3最小路程t3最短時(shí)間D3分組矩陣 四、問(wèn)題的分析與模型的建立將快遞網(wǎng)圖中，每個(gè)投遞點(diǎn)看作圖中的一個(gè)節(jié)點(diǎn)，各投點(diǎn)之間的公路看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，各條路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給快遞網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問(wèn)題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)0出發(fā)，行遍所有頂點(diǎn)至少一次再回到O點(diǎn)，使得總權(quán)（路程或時(shí)間）最小，此即最佳推銷員回路問(wèn)題。1)問(wèn)題一是需將30個(gè)貨物送達(dá)21個(gè)固定點(diǎn)并返回，O點(diǎn)和另外21個(gè)點(diǎn)構(gòu)成了一個(gè)典型的最短路問(wèn)題。即先利用Floyd計(jì)算兩點(diǎn)間的最短距離，再隨機(jī)構(gòu)造哈密頓圈，利用優(yōu)化算法對(duì)此H圈優(yōu)化，使H圈的權(quán)最小。2)問(wèn)題二本小問(wèn)是在一問(wèn)的基礎(chǔ)上加入時(shí)間的限制，解題思想是以第一問(wèn)的過(guò)程為基礎(chǔ)，從隨機(jī)產(chǎn)生的H圈中選出符合時(shí)間要求的多條路線，再?gòu)闹袑W(xué)出事的路程權(quán)重最小的路線。并檢驗(yàn)其是否符合時(shí)間的要求。3)問(wèn)題三主要是對(duì)路線的分組,分組后檢驗(yàn)，調(diào)整使得每組貨物質(zhì)量小于50kg，體積小于1m3，然后利用問(wèn)題一，解出每組的最佳H圈。五、模型的分析與求解 由附錄1給定的數(shù)據(jù)知，前30號(hào)貨物由于貨物的總質(zhì)量mzong和總體積vzong ，顯然送貨員能夠一次帶上所有貨物到達(dá)各送貨點(diǎn)，且貨物要送達(dá)總共為21個(gè)，如下：13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49本模型運(yùn)用圖論中Floyd算法與最佳Ｈ圈中的相關(guān)結(jié)論，建立了關(guān)于該類問(wèn)題的優(yōu)化模型，將出發(fā)點(diǎn)O和21個(gè)送貨點(diǎn)結(jié)合起來(lái)構(gòu)造完備加權(quán)圖。用矩陣翻轉(zhuǎn)來(lái)實(shí)現(xiàn)二邊逐次修正，求最佳哈密爾頓圈（H圈）。由完備加權(quán)圖,確定初始H圈,列出該初始H圈加點(diǎn)序邊框的距離矩陣,然后用二邊逐次修正法對(duì)矩陣進(jìn)行“翻轉(zhuǎn)”,就可得到近似最優(yōu)解的距離矩陣,從而確定近似最佳H圈。由于用矩陣翻轉(zhuǎn)方法來(lái)實(shí)現(xiàn)二邊逐次修正法的結(jié)果與初始圈有關(guān)，故為了的到得到較優(yōu)的計(jì)算結(jié)果，在用MATLAB編程時(shí)，隨機(jī)搜索出200個(gè)初始H圈。在所有H圈中，找出權(quán)最小的一個(gè)，即要找的最佳H圈的近似解。最佳H圈的近似解 min｛H0，H1，H2,…H99｝ 送貨路線：o→18→13→24→31→27→39→34→40→45→49→42→43→36→38→32→ 23→16→14→17→21→26→o送貨時(shí)間： lucheng =+004米 t=lucheng/24000+3*21/60=本小問(wèn)是在一問(wèn)的基礎(chǔ)上加入時(shí)間的限制，解題思想是以第一問(wèn)的過(guò)程為基礎(chǔ)，從隨機(jī)產(chǎn)生的H圈中選出符合時(shí)間要求的多條路線，即選擇符合每個(gè)點(diǎn)時(shí)間要求的最佳H圈。為了更有針對(duì)性，可將一問(wèn)的最佳路線作為初始的H圈進(jìn)行計(jì)算。得到結(jié)果，如下：o→18→13→24→31→27→39→34→40→45→49→42→43→38→36→32→ 23→16→14→17→21→26→olucheng2= +004 t2=lucheng2/24000+3*21/60= 現(xiàn)根據(jù)距離分組，在調(diào)整，然后求解。51號(hào)到各個(gè)地點(diǎn)的最小距離如下： 1 2 3 4 5 6 7 8 9 10 10068 16296 10467 14004 16563 11362 8100 8509 7775 8092 11 12 13 14 15 16 17 18 19 20 6965 6752 5295 5094 11558 7493 3621 2182 6968 13417 21 22 23 24 25 26 27 28 29 30 1797 11918 5395 4709 8934 1392 3997 14223 10820 13205 31 32 33 34 35 36 37 38 39 40 2929 6707 15549 5254 7624 4677 8975 6214 5777 6885 41 42 43 44 45 46 47 48 49 50 11577 9751 8833 13943 7860 14312 9216 15806 11722 99280→26→31→27→39→27→36→45→40→47→40→50→49→42→43→38→35→32→23→17→21→0； 0→26→31→34→40→37→41→44→48→46→33→28→30→22→20→22→29→25→19→24→31→26→0； 0→21→17→23→16→14→9→10→7→1→6→1→8→3→4→2→5→15→12→11→13→1811→0。計(jì)算三個(gè)區(qū)域各自送貨員走的總路程:1 2 3 計(jì)算時(shí)間:(++)/24000+3/60*100=六、模型的不足及改進(jìn)的方向不足： 由于數(shù)據(jù)量大，且最佳H圈與原始圈的選取有關(guān)，只能去近似最佳圈，因此對(duì)于第二問(wèn)隨機(jī)性很強(qiáng)，只能多設(shè)置一下循環(huán)次數(shù)，以求精確。第三問(wèn)的手動(dòng)畫(huà)圖、分組比較麻煩，要嘗試多次才能找出符合要求的點(diǎn)。參考文獻(xiàn)【1】趙靜、但琦，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)（第3版）高等教育出版社【2】姜啟源、謝金星、葉俊，數(shù)學(xué)模型，北京：高等教育出版社，2003相關(guān)程序數(shù)據(jù)圖1 快遞公司送貨地點(diǎn)示意圖O點(diǎn)為快遞公司地點(diǎn)，O點(diǎn)坐標(biāo)(11000,8250),單位：米表1 各貨物號(hào)信息表貨物號(hào)送達(dá)地點(diǎn)重量(公斤)體積(立方米)不超過(guò)時(shí)間1139：002189：003319：30426