最优路线设计

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、送货员只沿示意图连线路径行走；5、

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

4、求最佳哈密尔顿圈（h圈），也即是np-完备问题。用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（h圈）。 五、模型的建立与求解准备工作：用matlab编程先求出附表给定的相互之间可直接到达地点之间的距离：序号位置点1位置点2距离（米）113191621828643220782342422935381958634353675155005852125396112941071859181171451012812175713914268114910194681o/5118218282o/5121179783o/51261392用上表各地点的距离可构造示意图的带权邻接矩阵，再用floyd算法求

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

6、419582070517388104674545222933536035466746742054942424120924140035899812537082354601029210966904024317207481656361294903932106746102920326241582160018283113627196897133884742010966326204832183381502181008286477871958549490404158483201874715430850949203062557020705242412431721600183381874703569117215

7、01698922001173882092420748182831502115430356909928o/51100681629610467140031656311362810085091172199280基本概念令g=(v,e)为一个加权无向图，其中v=v1,v2,，vn为顶点集合，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圈: （2）对所有的，若,则在c0中删去边和而加入边和，形成新的h圈c，即 （3）对c重复步骤（），直到条件不满足为止，最终得到的c即为所求矩阵翻转 在一个矩阵中，对它的第i行（列）到第j行（列）翻转是以第i行（列）和j行（列

9、的）中心位置为转轴，旋转180度，这样：第i行（列）和第j行（列）的位置互换，第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）本模型运用图论中最佳推销员路径问题与最佳圈中的相关结论，建立了关于该类问题的优化模型，将出发点o/51和21个送货点结合起来构造完备加权图。不考虑送货员最大载重和体积，用矩阵翻转

10、方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（h圈）。由完备加权图,确定初始h圈,列出该初始h圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳h圈。由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的到得到较优的计算结果，我们用matlab编程时，随机搜索出若干个初始h圈，例如1000个。在所有h圈中，找出权最小的一个，此即要找的最佳h圈的近似解。最佳h圈的近似解 min11000 送货时间 t=24+0.05*h 图二下面仅列出几条用matlab编程得到的近似最佳送货路线及总路线长度：编号总路线长度（米）送货路线i

11、54709o/51262117141623323836434249454034392731241318o/51ii54996o/51181324313440454249433832231614172136392726o/51iii55773o/51211714162332363843424945403431392718132426o/51iv57914o/51181324313440454942433836273926141623321721o/51结果：选择总路线长度最短的送货路线，即第i条送货路线（图二）o/51262117141623323836434249454034392731241

12、318o/51送货员走的总长度为min11000 =54.709公里。送货总时间t=3.78小时 问题二：送130号货物仍可一次性送完，不用考虑送货员最大载重和体积。但选择路线必须得是货物的送到时间不超过指定时间。用matlab编程，在问题一程序里加入时间限制，得到结果：送货路线（图三）（o/51181324313440454249433832231614172136392726o/51）送货员走的总长度为min11000=54.996公里。t=3.79小时 图三问题三：由附录给定的各货物号信息表，1100号货物总重量148公斤、总体积2.8立方米。考虑到送货员最大载重和体积，送货员可分三次送

13、完所有货物。此问题包含两个方面：第一、对送货地点的分组；第二、在每组中求最佳送货路线。我们只能去寻求一种较合理的划分准则使得各组总路线长度加起来比较理想。选出三个点，使这三个点中两两之间的最短路长度是50个送货点所有的三点组中最大的，这三个点是各组的基点。通俗地说，就是找到图中“分的最开”的三个点作为基点。对于其他任意点，依次算出它与三个基点的最短路长度，离哪个基点近，它就被分到哪一组。 根据以上算法，用matlab编程我们得到了一个初始分组并算得它的货物重量总和、货物体积总和编号包含的送货点货物重量总和(公斤)货物体积总和（立方米）第一组2,5,11,12,13,15,19,20,22,24

14、,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立方米。调整后每组送货点，货物重量总和、货物体积总和如下表：编号包含的送货点货物重量总和(公斤)货物体积总和（立方米）第一组11,12,13,15,19,20,22,24,25,26,28,29,30,33,4

15、1,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.6947736o/51262419254144484633283029202215121113o/51（图四）第二组3.7952743o/51188254316710914163235231721o/51（图五）第三组3.4

16、742421o/512739363843424950454037473431o/51（图六） 图四 图五 图六 结果：最终三组的路线长度分别为：47.736公里，52.743公里,42.421公里均匀性很好，总路线长度为142.9公里。送完所有快件的时间为：t总=t1+t2+t3=10.95小时为了检验该结果，我们还计算了把50个送货点只分一组，在不考虑送货员最大载重和体积的情况下，送货员的最短路线长度为：119.762公里。但分组变多时，由于路线的重复，总路线会增加，本结果增加了23公里，这是可以容忍的。六、 模型的评价与改进：给定一个完备加权图,确定初始h圈,列出该初始h圈加点序边框的距离

17、矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳h圈。最佳哈密尔顿圈是一个np问题。通常采用近似算法-二边逐次修正法求该问题的近似最优解。用matlab编写的程序实现二边逐次修正法过程运行时间长，而且当顶点数较多时，甚至没办法求解。用矩阵翻转方法来实现二边逐次修正法过程，在matlab中实现非常简单、快捷,而且适合顶点数较多情况，程序简单、计算时占用内存少,而且可以用一个m文件表示。优化时只需调用这个文件,即可得到近似最优解,这样提高了程序的实用性。 本模型运用图论中最佳推销员路径问题与最佳圈中的相关结论，建立了关于该类问题的严格的优化模型，但是用矩

18、阵翻转方法来实现二边逐次修正法的结果与初始圈有关，初始圈的选择直接决定了结果的好坏，最后得到的结果只能是近似最优解。为了减小误差，我们调用的时候随机搜索了多个初始h圈，但是，误差究竟是存在的。七、参考文献：【1】赵静、但琦. 数学建模与数学试验 ，高等教育出版社,2004【2】贾秋玲、袁冬丽、栾云凤，基于matlab的系统仿真、分析及设计，西北工业大学出版社.2006【3】龚劬，图论与网络最优化，重庆大学出版社， 1998【4】姜启源，谢金星，叶俊，数学模型，高等教育出版社，2003【5】刘来福，数学模型与数学建模，北京师范大学出版社，1997八、附录相互之间可直接到达地点之间的距离funct

19、ion l=juli(u,x,y) % u,x,y为表2 ，表3构造数组format short gfor i=1:83 m=u(1,i);n=u(2,i); p(m,n)=sqrtm(x(m)-x(n)2+(y(m)-y(n)2);endfor i=1:83 m=u(2,i);n=u(1,i); p(m,n)=sqrtm(x(m)-x(n)2+(y(m)-y(n)2);endl=round(p);floyd算法求每对地点之间最短路径距离：functiond,r=floyd(a)n=size(a,1);d=afor i=1:n for j=1:n r(i,j)=j; endendrfor k=

20、1:n for i=1:n for j=1:n if d(i,k)+d(k,j)<d(i,j) d(i,j)=d(i,k)+d(k,j); r(i,j)=r(i,k); end end end k d rend求最佳h圈m文件functiona,b,s=h(e)%e为按照初始h圈点的顺序组成的含点序边框的距离矩阵n=size(e);%求出距离矩阵的维数.for i=2:n-2;%有一个顺序的外框,所以循环从2开始到n - 2. for j=i+1:n-2; if e(i,j)+e(i+1,j+1)<e(i,i+1)+e(j,j+1); a=horzcat(e(:,1:i),e(:,

21、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; %把翻转后的矩阵定义成新的距离矩阵,再次进入循环. end endends=0;for i=2:n-2; s=s+e(i,i+1);%求优化后h圈的总权.ende;s %结果可能是近似最优解,多代几个初始h圈. 比较各自的近似最优解,可得到最佳h圈.用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（h圈）clcclearload('d1.txt');d=d1;%fl

22、oyd算法求得的每对地点之间最短路径矩阵u=13,14,16,17,18,21,23,24,26,27,31,32,34,36,38,39,40,42,43,45,49,;%21个送货点a2=size(u);for q=1:1000 %随机搜索1000个初始h圈a1=1:a2(2);b=a1(randperm(length(a1);x=b(1:a2(2); for p=1:a2(2) u1(p)=u(x(p);endu2=51;%定义点o/51为起始点for i=1:21 u2(i+1)=u1(i);endfor i=1:22 for j=1:22 e(i,j)=d(u2(i),u2(j);

23、endend e=zeros(25,25); %列出该初始h圈加点序边框的距离矩阵for i=1:23;e(1,i)=i-1;e(25,i)=i-1;ende(1,24)=1;e(25,24)=1;for i=1:22 for j=1:22e(i+1,j+1)=e(i,j); end endfor i=2:23 e(24,i)=e(1,i-1);endfor i=2:23 e(i,24)=e(i-1,1);enda,b,s=h(e);%调用求最佳h圈的h函数.a,b,s=h(b); %把得出的结果矩阵再次调用这个函数,即为近似最佳h圈.for i=1:23l(i)=u2(a(1,i+1);%列

24、出送货员送货路线endl(q,:)=l;s(q)=s;%送货员走的总路线长度矩阵end对送货地点的分组clccleard=load('d1.txt');m=0;for i=1:51 for j=1:51 for k=1:51 s=min(d(i,j),d(j,k),d(i,k); p=max(d(51,i),d(51,j),d(51,k); q=min(d(51,i),d(51,j),d(51,k); if s-(p-q)>m m=s-(p-q); z1=i;z2=j;z3=k; end end endendz1,z2,z3 %这三个点是各组的基点p=1;m=1;n=1;

25、u=1;for i=1:50 if i=51,keyboard;end if (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(i,z3) z3(n)=i;n=n+1; endendz1,z2,z3 %对送货地点的分组的初始分组表1 各货物号信息表货物号送达地点重量(公斤)体积(

26、立方米)不超过时间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：151

27、7320.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.04833

28、441.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.001

29、256261.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

30、.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表2 50个位置点的坐标位置点x坐标(米)y坐标