最优路线设计

1、一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人 送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处， 请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见 表3。各件货物的相关信息见表1，50个位置点的坐标见表2。现在送货员要将100件货物送到50个地点。问题如下问题一：若将130号货物送到指定地点并返回。设计最快完成路线与方式。给 出结果。要求标出送货线路。问题二：假定该送货员从早上8点上班开始送货，要将130号货物的送

2、达时间 不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。问题三：若不需要考虑所有货物送达时间限制（包括前30件货物），现在要将 100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货 线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取 货。可不考虑中午休息时间。图一二、基本假设1、假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2、假设送货员的路上平均速度为24公里/小时，不会出现意外现象；3、每件货物交接花费3分钟，同一地点有多件货物也简单按照每件3分钟 交接计算，不会出现特殊情况而延误时间；4、送货员只沿示意图连线路径行走；

3、5、假设快递公司地点O为第51个位置点；6、假设送货员回到出发点O后取货时间不计。符号定义及说明D两点最短路径距离矩阵V . (1,2，n)从1到50个位置点里n个位置点集合f (V )I从O/51点出发，经过V中所有点最后回到O/51点的最佳送货路线的权 1值（即总路程）T送货员完成一次送货的时间HV:集合所有位置点要送达的货物件数四、问题的分析快递公司的送货员需要把货物送到所有货物交接地点，最后回到出发点。问 如何安排送货路线，能最快完成任务，即总的送货行程最短。此即图论中最佳推 销员路径问题。若不考虑送货员最大载重和体积，两个位置点边上的权表示距离，于是问题 就成为在加权图中寻找一条经过

4、每个位置点至少一次的最短闭通路问题，即求最 佳哈密尔顿圈（H圈），也即是NP-完备问题。用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（H圈）。五、模型的建立与求解准备工作：用MATLAB编程先求出附表给定的相互之间可直接到达地点之间的距离:序号位置点1位置点2距离（米）113191621828643220782342422935381958634353675155005852125396112941071859181171451012812175713914268114910194681O/5118218282O/5121179783O/51261392用上表各地点的距离可构造示意

5、图的带权邻接矩阵，再用Floyd算法求每对 地点之间最短路径。1. Floyd算法的基本思想直接在示意图的带权邻接矩阵中用插入顶点的方法依次构造出n个矩阵D、D( 2)、.、D(n)，使最后得到的矩阵D(n)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径.用Matlab编程得D(51=(气)5京51，其中D(i,j)即为两点最短路径距离，123456784950O/511077451916545289981294196828642030616989100682774505829229312539039971377872557022001162963191658290353670

6、823210388419582070517388104674545222933536035466746742054942424120924140035899812537082354601029210966904024317207481656361294903932106746102920326241582160018283113627196897133884742010966326204832183381502181008286477871958549490404158483201874715430850949203062557020705242412431721600183381874703

7、56911721501698922001173882092420748182831502115430356909928O/51100681629610467140031656311362810085091172199280基本概念令G=(V,E)为一个加权无向图，其中V= I v1,v2,，vn I为顶点集合，E为边集合。图G中每一条边e都对应一个实数w（e）,则称w（e）为该边的权。若任 意两点均有边相连，则G为完备图。哈密尔顿图设G=（V,E）是连通无向图，经过G的每个顶点正好一次的圈，称为G的一条哈密尔顿圈，简称H圈；含H圈的图成为哈密尔顿图或H图。最佳H圈在加权图G=（V，E）中，权最

8、小的哈密尔顿圈称为最佳H圈；判定一个加权图G=（V，E）是否存在哈密尔顿圈是一个NP问题，而它的完备 加权图G=（V,E） （E中的每条边（x,y）的权等于顶点x与y在图G中最短路 径的权）中一定存在哈密尔顿圈，所以在完备图G=（V,E）中寻找最佳H圈。该 过程采用二边逐次修正法并利用矩阵翻转实现。二边逐次修正法的算法过程如下：（1） 任取初始 H 圈：C = v , v ,.v ,.v，盘，v012 i j n 1 TOC o 1-5 h z HYPERLINK l bookmark31 o Current Document （2） 对所有的 i, j，1 i +1 j n，若 w（v,）岫

9、 v ）wvV ）wv（v, +）:i j i j+1 1+i i 1+ j j1+则在C中删去边（v , v ）和（v , v ）而加入边（v , v ）和（v , v ），形成新的H圈C，0i i+1j j+1i ji+1 j+1艮口 C = v v ,., v , v , v ,., v , v ,., v v1, 2 i j j-1i+1 j+1n, 1（3）对C重复步骤（2），直到条件不满足为止，最终得到的C即为所求.矩阵翻转 在一个矩阵中，对它的第i行（列）到第j行（列）翻转是以第 i行（列）和j行（列的）中心位置为转轴，旋转180度，这样：第i行（列） 和第j行（列）的位置互换，

10、第i+1行（列）和第j-1行（列）位置互换，问题一:由附录给定的各货物号信息表，130号货物总重量48.5公斤、总体积0.88 立方米，显然送货员能够一次带上所有货物到达各送货点，而且货物要送达的送 货点总共为21个V （13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49）本模型运用图论中最佳推销员路径问题与最佳H圈中的相关结论，建立了关 于该类问题的优化模型，将出发点O/51和21个送货点结合起来构造完备加权图。不考虑送货员最大载重和体积，用矩阵翻转方法来实现二边逐次修正法过 程，求最佳哈密尔顿圈（H圈）。由完备加权图

11、，确定初始H圈，列出该初始H圈 加点序边框的距离矩阵，然后用二边逐次修正法对矩阵进行“翻转”，就可得到 近似最优解的距离矩阵，从而确定近似最佳H圈。由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的 到得到较优的计算结果，我们用MATLAB编程时，随机搜索出若十个初始H圈， 例如1000个。在所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似 解。最佳h圈的近似解minEz :，叫）送货时间t=M）”+0.05*H图二卜面仅列出几条用MATLAB编程得到的近似最佳送货路线及总路线长度:编号总路线长度（米）送货路线I54709O/512621 1714-16 23323836

12、-43-42 -49 45403439-27-31 -24-13-18-0/51II54996Q/51-18-13-24 -31- 34-40-45-42-49-43-38-32-23-16-14-17-21-36-39-27-26-Q/51III55773O/5121 17141623323638-43-42-49 -45-40 34313927-18-13 -24-26-0/51IV579140/51-18- 13-24-31 -34-40 45-49-42 -43-38-36 27392614162332-17-21-0/51结果：选择总路线长度最短的送货路线，即第I条送货路线（图二）Q

13、/51-26-21-17-14-16-23-32-38-36-43-42-49-45-40-34-39-27-31 -24-13-18-Q/51送货员走的总长度为mi己了叫）=54.709公里。送货总时间T=3.78小时问题二送130号货物仍可一次性送完，不用考虑送货员最大载重和体积。但选择路 线必须得是货物的送到时间不超过指定时间。用MATLAB编程，在问题一程序里 加入时间限制，得到结果：送货路线（图三）（0/51一18一13一24一31一 34一40一45一42一49一43一38一32一23一16一14一17一21一36一39一27一26一 0/51）送货员走的总长度为min二；/（*）

14、=54.996公里。T=3.79小时图三Y8J-5F4h问题三：由附录给定的各货物号信息表，1100号货物总重量148公斤、总体积2.8 立方米。考虑到送货员最大载重和体积，送货员可分三次送完所有货物。此问题包含两个方面：第一、对送货地点的分组；第二、在每组中求最佳送 货路线。我们只能去寻求一种较合理的划分准则使得各组总路线长度加起来比较理想。 选出三个点，使这三个点中两两之间的最短路长度是50个送货点所有的三点组 中最大的，这三个点是各组的基点。通俗地说，就是找到图中“分的最开”的三 个点作为基点。对于其他任意点，依次算出它与三个基点的最短路长度，离哪个 基点近，它就被分到哪一组。根据以上算

15、法，用MATLAB编程我们得到了一个初始分组并算得它的货物重量 总和、货物体积总和编号包含的送货点货物 重量 总和 （公斤）货物体积总和/、4、 A（立方米）第一组2,5,11,12,13,15,19,20,22,24,25,26,28,29,30,31,33,41,44,46,4855.041.0622第组1,3,4,6,7,8,9,10,14,16,17,18,2129.120.5688第组23,27,32,34,35,36,37,38,39,40,42,43,45,47,49,5063.841.169可以看出要对初始分组进行调整，满足每组货物重量总和50公斤、货物体积 总和1立方米。调整

16、后每组送货点，货物重量总和、货物体积总和如下表:编号包含的送货点货物重量总和（公斤）货物体 积总和 （立方米）第一 组11,12,13,15,19,20,22,24,25,26,28,29,30,33,41,44,46,4849.90.9112第二 组1,2,3,4,5,6,7,8,9,10,14,16,17,18,21,23,32,3548.380.985第三 组27,31,34,36,37,38,39,40,42,43,45,47,49,5049.720.9038由问题一算法，可得出每组送货时间，最优送货路线及总路线长度编号送货 时间 （小时）总路线长度（米）送货路线第一组3.694773

17、60/512624192541444846332830-29-20-22-15-12-11-13-O/51 （图四）第组3.7952743O/51 1882543 1671091416323523 1721O/51 （图五）第组3.47424210/512739363843424950454037 4734310/51 （图六）图四图五图六结果：最终三组的路线长度分别为：47.736公里，52.743公里,42.421公里均匀性很好，总路线长度为142.9公里。送完所有快件的时间为：T总二T1+T2+T3=10.95小时为了检验该结果，我们还计算了把50个送货点只分一组，在不考虑送货员最大 载

18、重和体积的情况下，送货员的最短路线长度为：119.762公里。但分组变多时， 由于路线的重复，总路线会增加，本结果增加了 23公里，这是可以容忍的。六、模型的评价与改进：给定一个完备加权图，确定初始H圈，列出该初始H圈加点序边框的距离矩阵, 然后用二边逐次修正法对矩阵进行“翻转”，就可得到近似最优解的距离矩阵， 从而确定近似最佳H圈。最佳哈密尔顿圈是一个NP问题。通常米用近似算法 二边逐次修正法求该问题的近似最优解。用MATLAB编写的程序实现二边逐次修 正法过程运行时间长，而且当顶点数较多时，甚至没办法求解。用矩阵翻转方法 来实现二边逐次修正法过程，在MATLAB中实现非常简单、快捷，而且适

19、合顶点数 较多情况，程序简单、计算时占用内存少，而且可以用一个M文件表示。优化时 只需调用这个文件,即可得到近似最优解，这样提高了程序的实用性。本模型运用图论中最佳推销员路径问题与最佳H圈中的相关结论，建立了关 于该类问题的严格的优化模型，但是用矩阵翻转方法来实现二边逐次修正法的结 果与初始圈有关，初始圈的选择直接决定了结果的好坏，最后得到的结果只能是 近似最优解。为了减小误差，我们调用的时候随机搜索了多个初始H圈，但是， 误差究竟是存在的。七、参考文献：【1】赵静、但琦.数学建模与数学试验，高等教育出版社,2004【2】贾秋玲、袁冬丽、栾云凤，基于matlab的系统仿真、分析及设计，西北工业

20、大学出版社.2006【3】龚劬，图论与网络最优化，重庆大学出版社，1998【4】姜启源，谢金星，叶俊，数学模型，高等教育出版社，2003【5】刘来福，数学模型与数学建模，北京师范大学出版社，1997八、附录相互之间可直接到达地点之间的距离function L=juli(u,x,y) % u,x,y 为表 2，表 3 构造数组 format short g for i=1:83m=u(1,i);n=u(2,i);p(m,n)=sqrtm(x(m)-x(n)”2+(y(m)-y(n)”2);endfor i=1:83m=u(2,i);n=u(1,i);p(m,n)=sqrtm(x(m)-x(n)”

21、2+(y(m)-y(n)”2);endL=round(p);Floyd算法求每对地点之间最短路径距离：functionD,R=floyd(a)n=size(a,1);D=afor i=1:nfor j=1:nR(i,j)=j;endendRfor k=1:nfor i=1:nfor j=1:nif D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=R(i,k);endendendkDRend求最佳H圈M文件functiona,b,s=h(e)%e为按照初始H圈点的顺序组成的含点序边框的距离矩阵 n=size(e);%求出距离矩阵的维数.for i=2

22、:n-2;%有一个顺序的外框，所以循环从2开始到n - 2.for j=i+1:n-2;if e(i,j)+e(i+1,j+1)mm=s-(p-q);z1=i;z2=j;z3=k;endendendendz1,z2,z3 %这三个点是各组的基点p=1;m=1;n=1;u=1;for i=1:50if i=51,keyboard;endif (D(i,z1)D(i,z2)&(D(i,z3)D(i,z2)Z1(p)=i;p=p+1;elseif (D(i,z2)D(i,z1)&(D(i,z3)D(i,z1)Z2(m)=i;m=m+1;elseif (D(i,z2)D(i,z3)&(D(i,z1)D

23、(i,z3) Z3(n)=i;n=n+1;endendZ1,Z2,Z3 %对送货地点的分组的初始分组表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

24、.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.01441

25、0： 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.

26、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.04

27、4070400.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坐标（米）1918550021445560372705704373567052620995610080143571002522808716025259138452