数学建模送货路线设计问题

1、.送货路线设计问题摘要：本文主要讨论的是送货路线的设计问题。总体的解题思路是将问题中的地点、路线分别抽象成数学中的点、线，然后利用图论的相关知识理论来考虑这些问题。最后，设计方法程序，并利用Matlab 运行，解决问题。问题一要求根据 1-30号货物设计一条最快的送货路线，由于货物的总质量mzong和总体积 vzong （ mzong =48.5000;vzong =0.8800 ）均未超出最大限度50 和1，所以，该问题可转化成求最短路问题。解决方法：首先，写出每个点的带权邻接矩阵；然后，运用Floyd 求任意两点间的最短距离；最后，用H 圈构造运算法,并通过矩阵翻转的二边逐次修正法，得到最

2、短距离和最快完成路线图，如下:o 18132431273934 4045 4942 433638322316 14172126olucheng =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 2316 14172126olucheng2= 5.4707e+004t2=lucheng2/1000*v+t*21/60

3、= 3.3295 小时问题三将 1-100 号货物全部送到指定地点， mzong=148，vzong=2.8 ，显然不能一次性送到。解题思想是根据仓库到各个点的最小距离将地点分为三部分，分别派送。分完组后在利用第一问的思想给予优化求出最佳的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。送货时间为 :t3=lucheng/1000*v+t*100/60=10.563小时关键词：图论带权邻接矩阵Floyd 算法最优 Hamilton圈二边逐次修正一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛， 每个送货员需要以最快的速度及时将货物送达， 而且他们往往一人送多个地方，请设计方案使其耗时最少。;.现有一快递公司，库房在图1 中的 O点，一送货员需将货物送至城市内多处，请设计送货方案， 使所用时间最少。 该地形图的示意图见图 1，各点连通信息见表 3，假定送货员只能沿这些连通线

5、路行走， 而不能走其它任何路线。 各件货物的相关信息见表 1， 50 个位置点的坐标见表 2。假定送货员最大载重50 公斤，所带货物最大体积1 立方米。 送货员的平均速度为 24 公里 / 小时。假定每件货物交接花费3 分钟，为简化起见，同一地点有多件货物也简单按照每件3 分钟交接计算。现在送货员要将100 件货物送到50 个地点。请完成以下问题。1. 若将 130 号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上 8 点上班开始送货， 要将 130 号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需

6、要考虑所有货物送达时间限制( 包括前 30 件货物 ) ，现在要将 100 件货物全部送到指定地点并返回。 设计最快完成路线与方式。 要求标出送货线路， 给出送完所有快件的时间。 由于受重量和体积限制， 送货员可中途返回取货。 可不考虑中午休息时间。以上各问尽可能给出模型与算法。图 1快递公司送货地点示意图O 点为快递公司地点，O 点坐标 (11000,8250), 单位：米二、模型假设1. 将仓库视为第 51 个点，参与计算。2. 送货员在路上无特殊情况，不会因抛锚等现象而耽误时间；3. 同一地点要送多件货物，那么这些物品在同一次中运送；4. 要求到达的时间不包括此次在该点交接的时间；5.

7、送货员只沿着已知的路线行走；6. 道路是双向的，无单向路线；7. 送货员取货的时间不计。三、符号说明1 问中涉及到的符号a 各货物号信息（货物号、运送地点、重量、体积和最晚时间）矩阵b 50 个位置点的坐标矩阵;.c 互通点信息矩阵d 任意两相通两点间距离e 对应两相通两点间距离e1 对 e 进行去重后得到的矩阵f 带权邻接矩阵D任意两点间最小距离矩阵u 初始 H 圈mzong货物的总质量vzong 货物的总体积luxian最短路线lucheng 最小路程t1 最短时间t 货物交接时所需时间（3 分钟）v 送货员的行驶速度(24 千米每小时 )2 问中涉及到的符号luxian2最短路线luch

8、eng2 最小路程t2 最短时间3 问中涉及到的符号luxian3最短路线lucheng3 最小路程t3 最短时间D3 分组矩阵四、问题的分析与模型的建立将快递网图中， 每个投递点看作图中的一个节点， 各投点之间的公路看作图中对应节点间的边，各条路的长度 （或行驶时间）看作对应边上的权，所给快递网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点0 出发，行遍所有顶点至少一次再回到 O点，使得总权（路程或时间）最小， 此即最佳推销员回路问题。1) 问题一是需将30 个货物送达21 个固定点并返回，O 点和另外21 个点构成了一个典型的最短路问题。即先利用Floyd 计算两点间的最

9、短距离，再随机构造哈密顿圈，利用优化算法对此H 圈优化，使H 圈的权最小。2) 问题二本小问是在一问的基础上加入时间的限制，解题思想是以第一问的过程为基础， 从随机产生的 H 圈中选出符合时间要求的多条路线， 再从中学出事的路程权重最小的路线。并检验其是否符合时间的要求。3) 问题三主要是对路线的分组, 分组后检验，调整使得每组货物质量小于50kg，体积小于1m3，然后利用问题一，解出每组的最佳H圈。五、模型的分析与求解由附录 1 给定的数据知， 前 30 号货物由于货物的总质量 mzong 和总体积 vzong 分别为 48.5 和 0.88 均未超出最大限度 50 和 1，显然送货员能够一

10、次带上所有货物到达各送货点，且货物要送达总共为21 个，如下：13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49本模型运用图论中Floyd 算法与最佳圈中的相关结论，建立了关于该类问题的优化模型，将出发点O和 21 个送货点结合起来构造完备加权图。;.用矩阵翻转来实现二边逐次修正，求最佳哈密尔顿圈（H 圈）。由完备加权图, 确定初始 H 圈, 列出该初始 H 圈加点序边框的距离矩阵 , 然后用二边逐次修正法对矩阵进行“翻转” , 就可得到近似最优解的距离矩阵 , 从而确定近似最佳 H 圈。由于用矩阵翻转方法来实现二边逐次

11、修正法的结果与初始圈有关，故为了的到得到较优的计算结果，在用MATLAB编程时，随机搜索出200 个初始 H 圈。在所有H 圈中，找出权最小的一个，即要找的最佳H 圈的近似解。最佳 H圈的近似解min H0， H1， H2, H99送货路线：o 18132431273934 4045 4942 433638322316 14172126o送货时间：lucheng =5.4707e+004 米 t= lucheng/24000+3*21/60=小时3.3295本小问是在一问的基础上加入时间的限制，解题思想是以第一问的过程为基础，从随机产生的H 圈中选出符合时间要求的多条路线，即选择符合每个点时间

12、要求的最佳H 圈。为了更有针对性，可将一问的最佳路线作为初始的H 圈进行计算。得到结果，如下：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 小时;.现根据距离分组，在调整，然后求解。51 号到各个地点的最小距离如下：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。计算三个区域各自送货员走的总路程:1 42173.27m 2 39894.58m3 51440.73m计算时间 :(51440.73+39905.76+42173.27)/24000+3/60*100=10.563小时六、模型的不足及改进的方向不足：由于数据量大， 且最佳 H圈与原始圈的选取有关， 只能去近似最佳圈， 因此对于第二问随机性很强， 只能多设置一下循环

15、次数，以求精确。第三问的手动画图、分组比较麻烦，要尝试多次才能找出符合要求的点。参考文献【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：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 个位置点的坐标位置点X 坐标 (米)Y 坐标 (米)19185500214455603727057043735

21、670526209956100801435;.7100252280871602525913845268010119353050117850354512658541851376305200141340553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010

22、9003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表 3相互到达信息序号位置点 1位置点 21132183220424538634;.74285159521061117181271138121491415910161018171071811121912132

23、01225211215221318231319241311251418261416271417281421291522301525311623321723331831341924352022362126372136382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740;.61383662392763403464404565414466413767414668424369424

24、970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26程序问题一的程序%作图，标号，标距离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.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=%货物坐标数据1918550021445560;.3727057043735670526209956100801435710025228087160252591384526801011935305011785035451265854185137630520014134055

33、325152125597516153657045171416573851888258075195855816520780835521127708560222200883523147659055247790933025443595252610860963527103851050028565976529258098653015659955319395101003214835103653312501090034728011065351530511375361239011415376410115103813915116103995101205040834512300414930136504213265

34、141454314180142154430301506045109151423546233014500;.4777351455048885148804911575151605080101532551110008250;c=%连通数据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%求相连通的点之间的距离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(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圈函数functiona,b,s,s1=h(e)%e为按照初始 H圈点的顺序组成的含点序边框的距离矩阵n=size(e);%求出距离矩阵的

38、维数.a=ones(25,25);b=ones(25,25);fori=2:n-2;%有一个顺序的外框, 所以循环从 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);%翻转 e中的第 i + 1至 j 列 .b=vertcat(a(1:i,:),a(j:-1:i+1,:),a(j+1:n,:);%翻转 a中的第 i + 1至 j 行 .e=b;%把翻转后的矩阵定义成新的距离矩阵, 再次进入循环.endendends=0;s1

39、=zeros(1,22);fori=2:n-2;s=s+e(i,i+1);%求优化后 H圈的总权 .;.s1(i-1)=e(i,i+1);ende;a;b;s ;s1%结果可能是近似最优解, 多代几个初始H圈 .比较各自的近似最优解, 可得到最佳H圈 .3. %floyd 函数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圈、最短路、最小时间。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.0000;.9 32.0000 0.7000 0.0481 12.000010 38.0000 1.3300 0.0219 10.150011 45.0000 1.1000 0.028