數(shù)學(xué)建模送貨路線設(shè)計(jì)問題

1、.送貨路線設(shè)計(jì)問題摘要：本文主要討論的是送貨路線的設(shè)計(jì)問題。總體的解題思路是將問題中的地點(diǎn)、路線分別抽象成數(shù)學(xué)中的點(diǎn)、線，然后利用圖論的相關(guān)知識(shí)理論來考慮這些問題。最后，設(shè)計(jì)方法程序，并利用Matlab 運(yùn)行，解決問題。問題一要求根據(jù) 1-30號(hào)貨物設(shè)計(jì)一條最快的送貨路線，由于貨物的總質(zhì)量mzong和總體積 vzong （ mzong =48.5000;vzong =0.8800 ）均未超出最大限度50 和1，所以，該問題可轉(zhuǎn)化成求最短路問題。解決方法：首先，寫出每個(gè)點(diǎn)的帶權(quán)鄰接矩陣；然后，運(yùn)用Floyd 求任意兩點(diǎn)間的最短距離；最后，用H 圈構(gòu)造運(yùn)算法,并通過矩陣翻轉(zhuǎn)的二邊逐次修正法，得到最

2、短距離和最快完成路線圖，如下:o 18132431273934 4045 4942 433638322316 14172126olucheng =5.4707e+004 米 t= lucheng/1000*v+t*21/60=3.3295 小時(shí)問題二設(shè)計(jì)一條路線， 要求在時(shí)間允許的條件下， 使總路程最小。 解決思路是利用問題一中的方法，結(jié)合每個(gè)貨物的時(shí)間限制，最終得到路線圖，如下：o 18 13 24 31 27 39 34 40 45 49 42 43 38 36 32 2316 14172126olucheng2= 5.4707e+004t2=lucheng2/1000*v+t*21/60

3、= 3.3295 小時(shí)問題三將 1-100 號(hào)貨物全部送到指定地點(diǎn)， mzong=148，vzong=2.8 ，顯然不能一次性送到。解題思想是根據(jù)倉庫到各個(gè)點(diǎn)的最小距離將地點(diǎn)分為三部分，分別派送。分完組后在利用第一問的思想給予優(yōu)化求出最佳的H圈 .得到的送貨路線分別為 :第一組路線：o 26 31 27 39 27 36 4540 4740 5049 42 43 38 35 3223 17 21 o；第二組路線：o 26 31 34 40 37 41 4448 4633 2830 22 20 22 29 25 19 24 31 26 o；第三組路線：o 21 17 23 16 14 9 107

4、 1 61 8 3 4 2 515 1211 13 1811 o。送貨時(shí)間為 :t3=lucheng/1000*v+t*100/60=10.563小時(shí)關(guān)鍵詞：圖論帶權(quán)鄰接矩陣Floyd 算法最優(yōu) Hamilton圈二邊逐次修正一、問題重述現(xiàn)今社會(huì)網(wǎng)絡(luò)越來越普及，網(wǎng)購已成為一種常見的消費(fèi)方式，隨之物流行業(yè)也漸漸興盛， 每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)， 而且他們往往一人送多個(gè)地方，請(qǐng)?jiān)O(shè)計(jì)方案使其耗時(shí)最少。;.現(xiàn)有一快遞公司，庫房在圖1 中的 O點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請(qǐng)?jiān)O(shè)計(jì)送貨方案， 使所用時(shí)間最少。 該地形圖的示意圖見圖 1，各點(diǎn)連通信息見表 3，假定送貨員只能沿這些連通線

5、路行走， 而不能走其它任何路線。 各件貨物的相關(guān)信息見表 1， 50 個(gè)位置點(diǎn)的坐標(biāo)見表 2。假定送貨員最大載重50 公斤，所帶貨物最大體積1 立方米。 送貨員的平均速度為 24 公里 / 小時(shí)。假定每件貨物交接花費(fèi)3 分鐘，為簡化起見，同一地點(diǎn)有多件貨物也簡單按照每件3 分鐘交接計(jì)算?，F(xiàn)在送貨員要將100 件貨物送到50 個(gè)地點(diǎn)。請(qǐng)完成以下問題。1. 若將 130 號(hào)貨物送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。給出結(jié)果。要求標(biāo)出送貨線路。2. 假定該送貨員從早上 8 點(diǎn)上班開始送貨， 要將 130 號(hào)貨物的送達(dá)時(shí)間不能超過指定時(shí)間，請(qǐng)?jiān)O(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路。3. 若不需

6、要考慮所有貨物送達(dá)時(shí)間限制( 包括前 30 件貨物 ) ，現(xiàn)在要將 100 件貨物全部送到指定地點(diǎn)并返回。 設(shè)計(jì)最快完成路線與方式。 要求標(biāo)出送貨線路， 給出送完所有快件的時(shí)間。 由于受重量和體積限制， 送貨員可中途返回取貨。 可不考慮中午休息時(shí)間。以上各問盡可能給出模型與算法。圖 1快遞公司送貨地點(diǎn)示意圖O 點(diǎn)為快遞公司地點(diǎn)，O 點(diǎn)坐標(biāo) (11000,8250), 單位：米二、模型假設(shè)1. 將倉庫視為第 51 個(gè)點(diǎn)，參與計(jì)算。2. 送貨員在路上無特殊情況，不會(huì)因拋錨等現(xiàn)象而耽誤時(shí)間；3. 同一地點(diǎn)要送多件貨物，那么這些物品在同一次中運(yùn)送；4. 要求到達(dá)的時(shí)間不包括此次在該點(diǎn)交接的時(shí)間；5.

7、送貨員只沿著已知的路線行走；6. 道路是雙向的，無單向路線；7. 送貨員取貨的時(shí)間不計(jì)。三、符號(hào)說明1 問中涉及到的符號(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 問中涉及到的符號(hào)luxian2最短路線luch

8、eng2 最小路程t2 最短時(shí)間3 問中涉及到的符號(hào)luxian3最短路線lucheng3 最小路程t3 最短時(shí)間D3 分組矩陣四、問題的分析與模型的建立將快遞網(wǎng)圖中， 每個(gè)投遞點(diǎn)看作圖中的一個(gè)節(jié)點(diǎn)， 各投點(diǎn)之間的公路看作圖中對(duì)應(yīng)節(jié)點(diǎn)間的邊，各條路的長度 （或行駛時(shí)間）看作對(duì)應(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)（路程或時(shí)間）最小， 此即最佳推銷員回路問題。1) 問題一是需將30 個(gè)貨物送達(dá)21 個(gè)固定點(diǎn)并返回，O 點(diǎn)和另外21 個(gè)點(diǎn)構(gòu)成了一個(gè)典型的最短路問題。即先利用Floyd 計(jì)算兩點(diǎn)間的最

9、短距離，再隨機(jī)構(gòu)造哈密頓圈，利用優(yōu)化算法對(duì)此H 圈優(yōu)化，使H 圈的權(quán)最小。2) 問題二本小問是在一問的基礎(chǔ)上加入時(shí)間的限制，解題思想是以第一問的過程為基礎(chǔ)， 從隨機(jī)產(chǎn)生的 H 圈中選出符合時(shí)間要求的多條路線， 再從中學(xué)出事的路程權(quán)重最小的路線。并檢驗(yàn)其是否符合時(shí)間的要求。3) 問題三主要是對(duì)路線的分組, 分組后檢驗(yàn)，調(diào)整使得每組貨物質(zhì)量小于50kg，體積小于1m3，然后利用問題一，解出每組的最佳H圈。五、模型的分析與求解由附錄 1 給定的數(shù)據(jù)知， 前 30 號(hào)貨物由于貨物的總質(zhì)量 mzong 和總體積 vzong 分別為 48.5 和 0.88 均未超出最大限度 50 和 1，顯然送貨員能夠一

10、次帶上所有貨物到達(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)于該類問題的優(yōu)化模型，將出發(fā)點(diǎn)O和 21 個(gè)送貨點(diǎn)結(jié)合起來構(gòu)造完備加權(quán)圖。;.用矩陣翻轉(zhuǎn)來實(shí)現(xiàn)二邊逐次修正，求最佳哈密爾頓圈（H 圈）。由完備加權(quán)圖, 確定初始 H 圈, 列出該初始 H 圈加點(diǎn)序邊框的距離矩陣 , 然后用二邊逐次修正法對(duì)矩陣進(jìn)行“翻轉(zhuǎn)” , 就可得到近似最優(yōu)解的距離矩陣 , 從而確定近似最佳 H 圈。由于用矩陣翻轉(zhuǎn)方法來實(shí)現(xiàn)二邊逐次

11、修正法的結(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 18132431273934 4045 4942 433638322316 14172126o送貨時(shí)間：lucheng =5.4707e+004 米 t= lucheng/24000+3*21/60=小時(shí)3.3295本小問是在一問的基礎(chǔ)上加入時(shí)間的限制，解題思想是以第一問的過程為基礎(chǔ)，從隨機(jī)產(chǎn)生的H 圈中選出符合時(shí)間要求的多條路線，即選擇符合每個(gè)點(diǎn)時(shí)間

12、要求的最佳H 圈。為了更有針對(duì)性，可將一問的最佳路線作為初始的H 圈進(jìn)行計(jì)算。得到結(jié)果，如下：o 18 13 24 31 27 39 34 40 45 49 42 43 38 36 32 2316 14172126olucheng2= 5.4707e+004t2=lucheng2/24000+3*21/60= 3.3295 小時(shí);.現(xiàn)根據(jù)距離分組，在調(diào)整，然后求解。51 號(hào)到各個(gè)地點(diǎn)的最小距離如下：1234567891010068 1629610467 14004 16563 11362 81008509777580921112131415161718192069656752529550941

13、1558 7493 36212182 6968 1341721222324252627282930179711918539547098934 1392399714223 10820 1320531323334353637383940292967071554952547624 4677 89756214 5777 68854142434445464748495011577 97518833139437860 14312 9216 15806 11722 99280 26 31 27 39 27 36 45 40 47 40 50 49 42 4338 3532 2317 21 0；0 26 31

14、 34 40 37 4144 4846 33 28 30 22 20 22 29 25 1924 31 26 0；0 21 17 23 16 14 9 10 7 1 6 1 8 3 42 5 15 12 11 13 18;.11 0。計(jì)算三個(gè)區(qū)域各自送貨員走的總路程:1 42173.27m 2 39894.58m3 51440.73m計(jì)算時(shí)間 :(51440.73+39905.76+42173.27)/24000+3/60*100=10.563小時(shí)六、模型的不足及改進(jìn)的方向不足：由于數(shù)據(jù)量大， 且最佳 H圈與原始圈的選取有關(guān)， 只能去近似最佳圈， 因此對(duì)于第二問隨機(jī)性很強(qiáng)， 只能多設(shè)置一下循環(huán)

15、次數(shù)，以求精確。第三問的手動(dòng)畫圖、分組比較麻煩，要嘗試多次才能找出符合要求的點(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)重量 (公斤 )體積 (立方米 )不超過時(shí)間1132.500.03169： 002180.500.03549： 003311.180.02409： 304261.560.035012：005212.150.030512：00;.6141.

16、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：0019272.450.044512：0020242.930.04209： 0021310.800.01089： 3022272

17、.250.001812：0023261.570.021012：0024342.800.01039： 3025401.140.01559： 3026450.680.03829： 3027491.350.014410：1528320.520.002012：0029232.910.048712：0030161.200.042912：003111.260.02503221.150.05013331.630.04833441.230.00063551.410.03873660.540.00673770.700.01293880.760.03463992.140.008740101.070.0124411

18、11.370.051042122.390.042843130.990.004844141.660.049145150.450.020946162.040.009847171.950.032448182.120.055449193.870.026250202.010.032451211.380.041952220.390.000153231.660.050254241.240.053455252.410.001256261.260.0059;.57270.420.022458281.720.058059291.340.037260300.060.040261310.600.027462322.1

19、90.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.003

20、484232.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 個(gè)位置點(diǎn)的坐標(biāo)位置點(diǎn)X 坐標(biāo) (米)Y 坐標(biāo) (米)19185500214455603727057043735

21、670526209956100801435;.7100252280871602525913845268010119353050117850354512658541851376305200141340553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010

22、9003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表 3相互到達(dá)信息序號(hào)位置點(diǎn) 1位置點(diǎn) 21132183220424538634;.74285159521061117181271138121491415910161018171071811121912132

23、01225211215221318231319241311251418261416271417281421291522301525311623321723331831341924352022362126372136382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740;.61383662392763403464404565414466413767414668424369424

24、970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26程序問題一的程序%作圖，標(biāo)號(hào)，標(biāo)距離1.clc;a =%貨物信息數(shù)據(jù)113.00002.50000.03169.0000218.00000.50000.03549.0000331.00001.18000.02409.3000426.00001.56000.035012.0000521.00002.15000.030512.0000614.00001.72000.010012.0000717.00001.38000.010912.00

25、00823.00001.40000.042612.00009 32.0000 0.7000 0.0481 12.000010 38.0000 1.3300 0.0219 10.150011 45.0000 1.1000 0.0287 9.300012 43.0000 0.9500 0.0228 10.150013 39.0000 2.5600 0.0595 12.000014 45.0000 2.2800 0.0301 9.300015 42.0000 2.8500 0.0190 10.150016 43.0000 1.7000 0.0782 10.150017 32.0000 0.2500

26、0.0412 12.000018 36.0000 1.7900 0.0184 12.0000;.19 27.0000 2.4500 0.0445 12.000020 24.0000 2.9300 0.0420 9.000021 31.0000 0.8000 0.0108 9.300022 27.0000 2.2500 0.0018 12.000023 26.0000 1.5700 0.0210 12.000024 34.0000 2.8000 0.0103 9.300025 40.0000 1.1400 0.0155 9.300026 45.0000 0.6800 0.0382 9.30002

27、7 49.0000 1.3500 0.0144 10.150028 32.0000 0.5200 0.0020 12.000029 23.0000 2.9100 0.0487 12.000030 16.0000 1.2000 0.0429 12.0000311.00001.26000.02500322.00001.15000.05010333.00001.63000.04830344.00001.23000.00060355.00001.41000.03870366.00000.54000.00670377.00000.70000.01290388.00000.76000.03460399.0

28、0002.14000.008704010.00001.07000.012404111.00001.37000.051004212.00002.39000.042804313.00000.99000.004804414.00001.66000.049104515.00000.45000.020904616.00002.04000.009804717.00001.95000.032404818.00002.12000.055404919.00003.87000.026205020.00002.01000.032405121.00001.38000.041905222.00000.39000.000

29、105323.00001.66000.050205424.00001.24000.053405525.00002.41000.001205626.00001.26000.005905727.00000.42000.022405828.00001.72000.058005929.00001.34000.037206030.00000.06000.040206131.00000.60000.027406232.00002.19000.05030;.6333.00001.89000.049406434.00001.81000.032506535.00001.00000.005506636.00001

30、.24000.017706737.00002.51000.036106838.00002.04000.011006939.00001.07000.044007040.00000.49000.032907141.00000.51000.009407242.00001.38000.045507343.00001.31000.012107444.00001.26000.000507545.00000.98000.041307646.00001.35000.024107747.00002.12000.023007848.00000.54000.054207949.00001.01000.0566080

31、50.00001.12000.028408125.00000.79000.001108246.00002.12000.049208332.00002.77000.003408423.00002.29000.005408520.00000.21000.049008625.00001.29000.008808719.00001.12000.024908841.00000.90000.003808946.00002.38000.043409037.00001.42000.002009132.00001.01000.030009233.00002.51000.013309336.00001.17000

32、.002009438.00001.82000.030809517.00000.33000.034509611.00000.30000.017209715.00004.43000.053609812.00000.24000.005609910.00001.38000.017501007.00001.98000.04930;b=%貨物坐標(biāo)數(shù)據(jù)1918550021445560;.3727057043735670526209956100801435710025228087160252591384526801011935305011785035451265854185137630520014134055

33、325152125597516153657045171416573851888258075195855816520780835521127708560222200883523147659055247790933025443595252610860963527103851050028565976529258098653015659955319395101003214835103653312501090034728011065351530511375361239011415376410115103813915116103995101205040834512300414930136504213265

34、141454314180142154430301506045109151423546233014500;.4777351455048885148804911575151605080101532551110008250;c=%連通數(shù)據(jù)1132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637

35、2136;.38 21 1739 22 3040 23 1741 24 3142 25 4143 25 1944 25 2945 27 3146 28 3347 29 2248 30 2849 30 4150 31 2651 31 3452 32 3553 32 2354 33 4655 33 2856 34 4057 35 3858 36 4559 36 2760 37 4061 38 3662 39 2763 40 3464 40 4565 41 4466 41 3767 41 4668 42 4369 42 4970 43 3871 44 4872 44 5073 45 5074 45

36、4275 46 4876 47 4077 48 4478 49 5079 49 4280 50 4081 51 18;.82 51 2183 51 26;fori=1:83%求相連通的點(diǎn)之間的距離x(i) = b(c(i,2),2);x(i+1)=b(c(i,3),2);y(i) = b(c(i,2),3);y(i+1) = b(c(i,3),3);d(i) = sqrt(x(i) - x(i+1).2 + (y(i) - y(i+1).2);endd;e=c,d'%對(duì)應(yīng)點(diǎn)之間的距離矩陣plot(b(a(:,2),2),b(a(:,2),3),'ro')text(110

37、00,8250,'O庫房 ' );forj=1:81text(b(a(j,2),2),b(a(j,2),3),num2str(a(j,2);endholdonfori=1:83plot(b(c(i,2:3),2),b(c(i,2:3),3),'b' )x=b(c(i,2:3),2);x1=sum(x)/2;y=b(c(i,2:3),3);y1=sum(y)/2;text(x1,y1,num2str(e(i,4)end2. %H圈函數(shù)functiona,b,s,s1=h(e)%e為按照初始 H圈點(diǎn)的順序組成的含點(diǎn)序邊框的距離矩陣n=size(e);%求出距離矩陣的

38、維數(shù).a=ones(25,25);b=ones(25,25);fori=2:n-2;%有一個(gè)順序的外框, 所以循環(huán)從 2開始到 n - 2.for j=i+1:n-2;ife(i,j)+e(i+1,j+1)<e(i,i+1)+e(j,j+1);a=horzcat(e(:,1:i),e(:,j:-1:i+1),e(:,j+1:n);%翻轉(zhuǎn) e中的第 i + 1至 j 列 .b=vertcat(a(1:i,:),a(j:-1:i+1,:),a(j+1:n,:);%翻轉(zhuǎn) a中的第 i + 1至 j 行 .e=b;%把翻轉(zhuǎn)后的矩陣定義成新的距離矩陣, 再次進(jìn)入循環(huán).endendends=0;s1

39、=zeros(1,22);fori=2:n-2;s=s+e(i,i+1);%求優(yōu)化后 H圈的總權(quán) .;.s1(i-1)=e(i,i+1);ende;a;b;s ;s1%結(jié)果可能是近似最優(yōu)解, 多代幾個(gè)初始H圈 .比較各自的近似最優(yōu)解, 可得到最佳H圈 .3. %floyd 函數(shù)functionD,R=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nfor j=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendend

40、kDRend4. %求第一問最佳 H圈、最短路、最小時(shí)間。clear,clca =%貨物信息數(shù)據(jù)113.00002.50000.03169.0000218.00000.50000.03549.0000331.00001.18000.02409.3000426.00001.56000.035012.0000521.00002.15000.030512.0000614.00001.72000.010012.0000717.00001.38000.010912.0000823.00001.40000.042612.0000;.9 32.0000 0.7000 0.0481 12.000010 38.0000 1.3300 0.0219 10.150011 45.0000 1.1000 0.028