送貨路線設計問題摘要：本文主要討論的是送貨路線的設計問題?？傮w的解題思路是將問題中的地點、路線分別抽象成數學中的點、線，然后利用圖論的相關知識理論來考慮這些問題。最后，設計方法程序，并利用Matlab運行，解決問題。問題一要求根據1-30號貨物設計一條最快的送貨路線，由于貨物的總質量mzong和總體積vzong（mzong=48.5000;vzong=0.8800）均未超出最大限度50和1，所以，該問題可轉化成求最短路問題。解決方法：首先，寫出每個點的帶權鄰接矩陣；然后，運用Floyd求任意兩點間的最短距離；最后，用H圈構造運算法,并通過矩陣翻轉的二邊逐次修正法，得到最短距離和最快完成路線圖，如下:o→18→13→24→31→27→39→34→40→45→49→42→43→36→38→32→23→16→14→17→21→26→olucheng=5.4707e+004米t=lucheng/1000*v+t*21/60=3.3295小時問題二設計一條路線，要求在時間允許的條件下，使總路程最小。解決思路是利用問題一中的方法，結合每個貨物的時間限制，最終得到路線圖，如下：o→18→13→24→31→27→39→34→40→45→49→42→43→38→36→32→23→16→14→17→21→26→olucheng2=5.4707e+004t2=lucheng2/1000*v+t*21/60=3.3295小時問題三將1-100號貨物全部送到指定地點，mzong=148，vzong=2.8，顯然不能一次性送到。解題思想是根據倉庫到各個點的最小距離將地點分為三部分，分別派送。分完組后在利用第一問的思想給予優(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=10.563小時關鍵詞：圖論帶權鄰接矩陣Floyd算法最優(yōu)Hamilton圈二邊逐次修正一、問題重述現今社會網絡越來越普及，網購已成為一種常見的消費方式，隨之物流行業(yè)也漸漸興盛，每個送貨員需要以最快的速度及時將貨物送達，而且他們往往一人送多個地方，請設計方案使其耗時最少?，F有一快遞公司，庫房在圖1中的O點，一送貨員需將貨物送至城市內多處，請設計送貨方案，使所用時間最少。該地形圖的示意圖見圖1，各點連通信息見表3，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關信息見表1，50個位置點的坐標見表2。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時。假定每件貨物交接花費3分鐘，為簡化起見，同一地點有多件貨物也簡單按照每件3分鐘交接計算?，F在送貨員要將100件貨物送到50個地點。請完成以下問題。1.若將1~30號貨物送到指定地點并返回。設計最快完成路線與方式。給出結果。要求標出送貨線路。2.假定該送貨員從早上8點上班開始送貨，要將1~30號貨物的送達時間不能超過指定時間，請設計最快完成路線與方式。要求標出送貨線路。3.若不需要考慮所有貨物送達時間限制(包括前30件貨物)，現在要將100件貨物全部送到指定地點并返回。設計最快完成路線與方式。要求標出送貨線路，給出送完所有快件的時間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時間。以上各問盡可能給出模型與算法。圖1快遞公司送貨地點示意圖O點為快遞公司地點，O點坐標(11000,8250),單位：米二、模型假設1.將倉庫視為第51個點，參與計算。2.送貨員在路上無特殊情況，不會因拋錨等現象而耽誤時間；3.同一地點要送多件貨物，那么這些物品在同一次中運送；4.要求到達的時間不包括此次在該點交接的時間；5.送貨員只沿著已知的路線行走；6.道路是雙向的，無單向路線；7.送貨員取貨的時間不計。三、符號說明1問中涉及到的符號a各貨物號信息（貨物號、運送地點、重量、體積和最晚時間）矩陣b50個位置點的坐標矩陣1.5.3現根據距離分組，在調整，然后求解。51號到各個地點的最小距離如下：1234567891010068162961046714004165631136281008509777580921112131415161718192069656752529550941155874933621218269681341721222324252627282930179711918539547098934139239971422310820132053132333435363738394029296707155495254762446778975621457776885414243444546474849501157797518833139437860143129216158061172299280→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。計算三個區(qū)域各自送貨員走的總路程:142173.27m239894.58m351440.73m計算時間:(51440.73+39905.76+42173.27)/24000+3/60*100=10.563小時六、模型的不足及改進的方向不足：由于數據量大，且最佳H圈與原始圈的選取有關，只能去近似最佳圈，因此對于第二問隨機性很強，只能多設置一下循環(huán)次數，以求精確。第三問的手動畫圖、分組比較麻煩，要嘗試多次才能找出符合要求的點。參考文獻【1】趙靜、但琦，數學建模與數學實驗（第3版）高等教育出版社【2】姜啟源、謝金星、葉俊，數學模型，北京：高等教育出版社，2003相關程序數據圖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：0019272.450.044512：0020242.930.04209：0021310.800.01089：3022272.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.012441111.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.005957270.420.022458281.720.058059291.340.037260300.060.040261310.600.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坐標(米)1918550021445560372705704373567052620995610080143571002522808716025259138452680101193530501178503545126585418513763052001413405532515212559751615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表3相互到達信息序號位置點1位置點21132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213638211739223040231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26程序問題一的程序1.%作圖，標號，標距離clc;a=[%貨物信息數據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.0000932.00000.70000.048112.00001038.00001.33000.021910.15001145.00001.10000.02879.30001243.00000.95000.022810.15001339.00002.56000.059512.00001445.00002.28000.03019.30001542.00002.85000.019010.15001643.00001.70000.078210.15001732.00000.25000.041212.00001836.00001.79000.018412.00001927.00002.45000.044512.00002024.00002.93000.04209.00002131.00000.80000.01089.30002227.00002.25000.001812.00002326.00001.57000.021012.00002434.00002.80000.01039.30002540.00001.14000.01559.30002645.00000.68000.03829.30002749.00001.35000.014410.15002832.00000.52000.002012.00002923.00002.91000.048712.00003016.00001.20000.042912.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.00002.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.000105323.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.050306333.00001.89000.049406434.00001.81000.032506535.00001.00000.005506636.00001.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.056608050.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.002009438.00001.82000.030809517.00000.33000.034509611.00000.30000.017209715.00004.43000.053609812.00000.24000.005609910.00001.38000.017501007.00001.98000.04930];b=[%貨物坐標數據191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376305200141340553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010900347280110653515305113753612390114153764101151038139151161039951012050408345123004149301365042132651414543141801421544303015060451091514235462330145004777351455048885148804911575151605080101532551110008250];c=[%連通數據11321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417281421291522301525311623321723331831341924352022362126372136382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740613836623927634034644045654144664137674146684243694249704338714448724450734550744542754648764740774844784950794942805040815118825121835126];fori=1:83%求相連通的點之間的距離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'];%對應點之間的距離矩陣plot(b(a(:,2),2),b(a(:,2),3),'ro')text(11000,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圈函數function[a,b,s,s1]=h(e)%e為按照初始H圈點的順序組成的含點序邊框的距離矩陣n=size(e);%求出距離矩陣的維數.a=ones(25,25);b=ones(25,25);fori=2:n-2;%有一個順序的外框,所以循環(huán)從2開始到n-2.forj=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));%翻轉e中的第i+1至j列.b=vertcat(a(1:i,:),a(j:-1:i+1,:),a(j+1:n,:));%翻轉a中的第i+1至j行.e=b;%把翻轉后的矩陣定義成新的距離矩陣,再次進入循環(huán).endendends=0;s1=zeros(1,22);fori=2:n-2;s=s+e(i,i+1);%求優(yōu)化后H圈的總權.s1(i-1)=e(i,i+1);ende;a;b;s;s1%結果可能是近似最優(yōu)解,多代幾個初始H圈.比較各自的近似最優(yōu)解,可得到最佳H圈.3.%floyd函數function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendRfork=1:nfori=1:nforj=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);endendendkDRend4.%求第一問最佳H圈、最短路、最小時間。clear,clca=[%貨物信息數據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.0000932.00000.70000.048112.00001038.00001.33000.021910.15001145.00001.10000.02879.30001243.00000.95000.022810.15001339.00002.56000.059512.00001445.00002.28000.03019.30001542.00002.85000.019010.15001643.00001.70000.078210.15001732.00000.25000.041212.00001836.00001.79000.018412.00001927.00002.45000.044512.00002024.00002.93000.04209.00002131.00000.80000.01089.30002227.00002.25000.001812.00002326.00001.57000.021012.00002434.00002.80000.01039.30002540.00001.14000.01559.30002645.00000.68000.03829.30002749.00001.35000.014410.15002832.00000.52000.002012.00002923.00002.91000.048712.00003016.00001.20000.042912.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.00002.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.000105323.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.050306333.00001.89000.049406434.00001.81000.032506535.00001.00000.005506636.00001.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.056608050.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.002009438.00001.82000.030809517.00000.33000.034509611.00000.30000.017209715.00004.43000.053609812.00000.24000.005609910.00001.38000.017501007.00001.98000.04930];b=[%坐標數據191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376305200141340553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010900347280110653515305113753612390114153764101151038139151161039951012050408345123004149301365042132651414543141801421544303015060451091514235462330145004777351455048885148804911575151605080101532551110008250];c=[%連通數據11321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417281421291522301525311623321723331831341924352022362126372136382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740613836623927634034644045654144664137674146684243694249704338714448724450734550744542754648764740774844784950794942805040815118825121835126];fori=1:83%求相連通的點之間的距離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'];%對應點之間的距離矩陣mzong=sum(a(1:30,3));vzong=sum(a(1:30,4));e1=1.0e3*[0.00100.00100.00301.91630.00200.00100.00802.86380.00300.00200.02007.82330.00400.00200.00402.29260.00500.00300.00801.95810.00600.00300.00403.53640.00700.00400.002000.00800.00500.01505.00450.00900.00500.00201.25290.01000.00600.00101.29430.01100.00700.01805.91790.01200.00700.00101.96820.01300.00800.01201.75680.01400.00900.01402.68130.01500.00900.01001.94550.01600.01000.01805.90950.01700.01000.00702.05940.01800.01100.01201.41770.01900.01200.01301.45680.02000.01200.02505.75660.02100.01200.01504.80580.02200.01300.01803.11350.02300.01300.01903.45570.02400.01300.01101.66960.02500.01400.01805.34220.02600.01400.01602.60770.02700.01400.01702.19570.02800.01400.02103.29670.02900.01500.02202.86100.03000.01500.02504.23540.03100.01600.02302.09760.03200.01700.02301.77450.03300.01800.03102.10370.03400.01900.02402.25860.03500.02000.02201.49890.03600.02100.02602.19170.03700.02100.03602.88020.03800.02100.01701.82390.03900.02200.03001.28750.04000.02300.017000.04100.02400.03101.78010.04200.02500.04104.15460.04300.02500.01901.9662