【正文】 送貨路線設(shè)計(jì)問題摘要：本文主要討論的是送貨路線的設(shè)計(jì)問題。總體的解題思路是將問題中的地點(diǎn)、路線分別抽象成數(shù)學(xué)中的點(diǎn)、線，然后利用圖論的相關(guān)知識理論來考慮這些問題。最后，設(shè)計(jì)方法程序，并利用Matlab運(yùn)行，解決問題。問題一要求根據(jù)130號貨物設(shè)計(jì)一條最快的送貨路線，由于貨物的總質(zhì)量mzong和總體積vzong（mzong =。vzong =）均未超出最大限度50和1，所以，該問題可轉(zhuǎn)化成求最短路問題。解決方法：首先，寫出每個點(diǎn)的帶權(quán)鄰接矩陣；然后，運(yùn)用Floyd求任意兩點(diǎn)間的最短距離；最后，用H圈構(gòu)造運(yùn)算法,并通過矩陣翻轉(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=問題二設(shè)計(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/1000*v+t*21/60= 問題三將1100號貨物全部送到指定地點(diǎn)，mzong=148，vzong=，顯然不能一次性送到。解題思想是根據(jù)倉庫到各個點(diǎn)的最小距離將地點(diǎ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。送貨時間為:t3=lucheng/1000*v+t*100/60=關(guān)鍵詞：圖論 帶權(quán)鄰接矩陣 Floyd算法 最優(yōu)Hamilton圈 二邊逐次修正一、問題重述現(xiàn)今社會網(wǎng)絡(luò)越來越普及，網(wǎng)購已成為一種常見的消費(fèi)方式，隨之物流行業(yè)也漸漸興盛，每個送貨員需要以最快的速度及時將貨物送達(dá)，而且他們往往一人送多個地方，請?jiān)O(shè)計(jì)方案使其耗時最少?，F(xiàn)有一快遞公司，庫房在圖1中的O點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請?jiān)O(shè)計(jì)送貨方案，使所用時間最少。該地形圖的示意圖見圖1，各點(diǎn)連通信息見表3，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關(guān)信息 見表1，50個位置點(diǎn)的坐標(biāo)見表2。 假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時。假定每件貨物交接花費(fèi)3分鐘，為簡化起見，同一地點(diǎn)有多件貨物也簡單按照每件3分鐘交接計(jì)算?，F(xiàn)在送貨員要將100件貨物送到50個地點(diǎn)。請完成以下問題。1. 若將1~30號貨物送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。給出結(jié)果。要求標(biāo)出送貨線路。2. 假定該送貨員從早上8點(diǎn)上班開始送貨，要將1~30號貨物的送達(dá)時間不能超過指定時間，請?jiān)O(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路。3. 若不需要考慮所有貨物送達(dá)時間限制(包括前30件貨物)，現(xiàn)在要將100件貨物全部送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快件的時間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時間。以上各問盡可能給出模型與算法。 圖1 快遞公司送貨地點(diǎn)示意圖O點(diǎn)為快遞公司地點(diǎn)，O點(diǎn)坐標(biāo)(11000,8250),單位：米二、模型假設(shè)，參與計(jì)算。，不會因拋錨等現(xiàn)象而耽誤時間；，那么這些物品在同一次中運(yùn)送；；；，無單向路線；。三、符號說明1問中涉及到的符號a各貨物號信息（貨物號、運(yùn)送地點(diǎn)、重量、體積和最晚時間）矩陣b 50個位置點(diǎn)的坐標(biāo)矩陣c互通點(diǎn)信息矩陣d任意兩相通兩點(diǎn)間距離e對應(yīng)兩相通兩點(diǎn)間距離e1對e進(jìn)行去重后得到的矩陣f帶權(quán)鄰接矩陣D任意兩點(diǎn)間最小距離矩陣u初始H圈mzong貨物的總質(zhì)量vzong貨物的總體積luxian最短路線lucheng最小路程t1最短時間t貨物交接時所需時間（3分鐘）v送貨員的行駛速度(24千米每小時)2問中涉及到的符號luxian2最短路線lucheng2最小路程t2最短時間3問中涉及到的符號luxian3最短路線lucheng3最小路程t3最短時間D3分組矩陣 四、問題的分析與模型的建立將快遞網(wǎng)圖中，每個投遞點(diǎn)看作圖中的一個節(jié)點(diǎn)，各投點(diǎn)之間的公路看作圖中對應(yīng)節(jié)點(diǎn)間的邊，各條路的長度（或行駛時間）看作對應(yīng)邊上的權(quán)，所給快遞網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)0出發(fā)，行遍所有頂點(diǎn)至少一次再回到O點(diǎn)，使得總權(quán)（路程或時間）最小，此即最佳推銷員回路問題。1)問題一是需將30個貨物送達(dá)21個固定點(diǎn)并返回，O點(diǎn)和另外21個點(diǎn)構(gòu)成了一個典型的最短路問題。即先利用Floyd計(jì)算兩點(diǎn)間的最短距離，再隨機(jī)構(gòu)造哈密頓圈，利用優(yōu)化算法對此H圈優(yōu)化，使H圈的權(quán)最小。2)問題二本小問是在一問的基礎(chǔ)上加入時間的限制，解題思想是以第一問的過程為基礎(chǔ)，從隨機(jī)產(chǎn)生的H圈中選出符合時間要求的多條路線，再從中學(xué)出事的路程權(quán)重最小的路線。并檢驗(yàn)其是否符合時間的要求。3)問題三主要是對路線的分組,分組后檢驗(yàn)，調(diào)整使得每組貨物質(zhì)量小于50kg，體積小于1m3，然后利用問題一，解出每組的最佳H圈。五、模型的分析與求解 由附錄1給定的數(shù)據(jù)知，前30號貨物由于貨物的總質(zhì)量mzong和總體積vzong ，顯然送貨員能夠一次帶上所有貨物到達(dá)各送貨點(diǎn)，且貨物要送達(dá)總共為21個，如下：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)于該類問題的優(yōu)化模型，將出發(fā)點(diǎn)O和21個送貨點(diǎn)結(jié)合起來構(gòu)造完備加權(quán)圖。用矩陣翻轉(zhuǎn)來實(shí)現(xiàn)二邊逐次修正，求最佳哈密爾頓圈（H圈）。由完備加權(quán)圖,確定初始H圈,列出該初始H圈加點(diǎn)序邊框的距離矩陣,然后用二邊逐次修正法對矩陣進(jìn)行“翻轉(zhuǎn)”,就可得到近似最優(yōu)解的距離矩陣,從而確定近似最佳H圈。由于用矩陣翻轉(zhuǎn)方法來實(shí)現(xiàn)二邊逐次修正法的結(jié)果與初始圈有關(guān)，故為了的到得到較優(yōu)的計(jì)算結(jié)果，在用MATLAB編程時，隨機(jī)搜索出200個初始H圈。在所有H圈中，找出權(quán)最小的一個，即要找的最佳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送貨時間： lucheng =+004米 t=lucheng/24000+3*21/60=本小問是在一問的基礎(chǔ)上加入時間的限制，解題思想是以第一問的過程為基礎(chǔ)，從隨機(jī)產(chǎn)生的H圈中選出符合時間要求的多條路線，即選擇符合每個點(diǎn)時間要求的最佳H圈。為了更有針對性，可將一問的最佳路線作為初始的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號到各個地點(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ì)算三個區(qū)域各自送貨員走的總路程:1 2 3 計(jì)算時間:(++)/24000+3/60*100=六、模型的不足及改進(jìn)的方向不足： 由于數(shù)據(jù)量大，且最佳H圈與原始圈的選取有關(guān)，只能去近似最佳圈，因此對于第二問隨機(jī)性很強(qiáng)，只能多設(shè)置一下循環(huán)次數(shù)，以求精確。第三問的手動畫圖、分組比較麻煩，要嘗試多次才能找出符合要求的點(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 各貨物號信息表貨物號送達(dá)地點(diǎn)重量(公斤)體積(立方米)不超過時間1139：002189：003319：30426