一、问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。 现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3。各件货物的相关信息见表1，50个位置点的坐标见表2。 现在送货员要将100件货物送到50个地点。问题如下 问题一： 若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。 问题二：假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 问题三： 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。 图一 二、 基本假设 1、假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米； 2、假设送货员的路上平均速度为24公里/小时，不会出现意外现象； 3、每件货物交接花费3分钟，同一地点有多件货物也简单按照每件3分钟交接计算，不会出现特殊情况而延误时间； 4、送货员只沿示意图连线路径行走； 5、假设快递公司地点O为第51个位置点； 6、假设送货员回到出发点O后取货时间不计。 三．符号定义及说明 D 两点最短路径距离矩阵 i（1,2，…n） 从1到50个位置点里n个位置点集合 从O/51点出发，经过中所有点最后回到O/51点的最佳送货路线的权值（即总路程） 送货员完成一次送货的时间 H i集合所有位置点要送达的货物件数 四、问题的分析 快递公司的送货员需要把货物送到所有货物交接地点，最后回到出发点。问如何安排送货路线，能最快完成任务，即总的送货行程最短。此即图论中最佳推销员路径问题。 若不考虑送货员最大载重和体积，两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈（H圈），也即是NP-完备问题。 用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（H圈）。 五、模型的建立与求解 准备工作： 用MATLAB编程先求出附表给定的相互之间可直接到达地点之间的距离： 序号 位置点1 位置点2 距离（米） 1 1 3 1916 2 1 8 2864 3 2 20 7823 4 2 4 2293 5 3 8 1958 6 3 4 3536 7 5 15 5005 8 5 2 1253 9 6 1 1294 10 7 18 5918 11 7 1 4510 12 8 12 1757 13 9 14 2681 14 9 10 1946 …… …… …… …… 81 O/51 18 2182 82 O/51 21 1797 83 O/51 26 1392 用上表各地点的距离可构造示意图的带权邻接矩阵，再用Floyd算法求每对地点之间最短路径。 1. Floyd算法的基本思想 直接在示意图的带权邻接矩阵中用插入顶点的方法依次构造出n个矩阵D(1)、 D(2)、… 、D(n)，使最后得到的矩阵D(n)成为图的距离矩阵，同时也求出插入点矩阵以便得到两点间的最短路径． 用Matlab编程得D(51)=（Dij）51×51，其中D(i,j)即为两点最短路径距离， 1 2 3 4 5 6 7 8 …… 49 50 O/51 1 0 7745 1916 5452 8998 1294 1968 2864 …… 20306 16989 10068 2 7745 0 5829 2293 1253 9039 9713 7787 …… 25570 22001 16296 3 1916 5829 0 3536 7082 3210 3884 1958 …… 20705 17388 10467 4 5452 2293 3536 0 3546 6746 7420 5494 …… 24241 20924 14003 5 8998 1253 7082 3546 0 10292 10966 9040 …… 24317 20748 16563 6 1294 9039 3210 6746 10292 0 3262 4158 …… 21600 18283 11362 7 1968 9713 3884 7420 10966 3262 0 4832 …… 18338 15021 8100 8 2864 7787 1958 5494 9040 4158 4832 0 …… 18747 15430 8509 …… …… …… …… …… …… …… …… …… …… …… …… …… 49 20306 25570 20705 24241 24317 21600 18338 18747 …… 0 3569 11721 50 16989 22001 17388 20924 20748 18283 15021 15430 …… 3569 0 9928 O/51 10068 16296 10467 14003 16563 11362 8100 8509 …… 11721 9928 0 基本概念 令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)中，权最小的哈密尔顿圈称为最佳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行（列的）中心位置为转轴，旋转180度，这样：第i行（列）和第j行（列）的位置互换，第i+1行（列）和第j-1行（列）位置互换，…… 问题一 ： 由附录给定的各货物号信息表，1~30号货物总重量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个送货点结合起来构造完备加权图。 不考虑送货员最大载重和体积，用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（H圈）。由完备加权图,确定初始H圈,列出该初始H圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳H圈。 由于用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，故为了的到得到较优的计算结果，我们用MATLAB编程时，随机搜索出若干个初始H圈，例如1000个。在所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解。 最佳H圈的近似解 min 送货时间 T=+0.05*H 图二 下面仅列出几条用MATLAB编程得到的近似最佳送货路线及总路线长度： 编号 总路线 长度（米） 送货路线 I 54709 O/51→26→21→17→14→16 →23→32→38→36→43→42 →49 →45→40→34→39→27→31 →24→13→18→O/51 II 54996 O/51→18→13→24 →31→ 34→40→45→42→49→43→38→32→23 →16→14→17→21→36→39→27→26→O/51 III 55773 O/51→21→17→14→16→23→32→36→38→43→42→49 →45→40 →34→31→39→27→18→13 →24→26→O/51 IV 57914 O/51→18→ 13→24→31 →34→40→ 45→49→42 →43→38→36 →27→39→26→14→16→23→32→17→21→O/51 结果：选择总路线长度最短的送货路线，即 第I条送货路线（图二） O/51→26→21→17→14→16→23→32→38→36→43→42→49 →45→40→34→39→27→31 →24→13→18→O/51 送货员走的总长度为min =54.709公里。送货总时间T=3.78小时 问题二： 送1~30号货物仍可一次性送完，不用考虑送货员最大载重和体积。但选择路线必须得是货物的送到时间不超过指定时间。用MATLAB编程，在问题一程序里加入时间限制， 得到结果：送货路线（图三） （O/51→18→13→24→31→ 34→40→45→42→49→43→38→32→23 →16→14→17→21→36→39→27→26→O/51） 送货员走的总长度为min=54.996公里。T=3.79小时 图三 问题三： 由附录给定的各货物号信息表，1~100号货物总重量148公斤、总体积2.8立方米。考虑到送货员最大载重和体积，送货员可分三次送完所有货物。 此问题包含两个方面：第一、对送货地点的分组；第二、在每组中求最佳送货路线。 我们只能去寻求一种较合理的划分准则使得各组总路线长度加起来比较理想。 选出三个点，使这三个点中两两之间的最短路长度是50个送货点所有的三点组中最大的，这三个点是各组的基点。通俗地说，就是找到图中“分的最开”的三个点作为基点。对于其他任意点，依次算出它与三个基点的最短路长度，离哪个基点近，它就被分到哪一组。 根据以上算法，用MATLAB编程我们得到了一个初始分组并算得它的货物重量总和、货物体积总和 编号 包含的送货点 货物重量总和(公斤) 货物体积总和（立方米） 第一组 2,5,11,12,13,15,19,20,22,24,25,26,28,29,30,31,33,41,44,46,48 55.04 1.0622 第二组 1,3,4,6,7,8,9,10,14,16,17,18,21 29.12 0.5688 第三组 23,27,32,34,35,36,37,38,39,40,42,43,45,47,49,50 63.84 1.169 可以看出要对初始分组进行调整，满足每组货物重量总和<50公斤、货物体积总和<1立方米。 调整后每组送货点，货物重量总和、货物体积总和如下表： 编号 包含的送货点 货物重量总和(公斤) 货物体积总和（立方米） 第一组 11,12,13,15,19,20,22,24,25,26,28,29,30,33,41,44,46,48 49.9 0.9112 第二组 1,2,3,4,5,6,7,8,9,10,14,16,17,18,21,23,32,35 48.38 0.985 第三组 27,31,34,36,37,38,39,40,42,43,45,47,49,50 49.72 0.9038 由问题一算法，可得出每组送货时间，最优送货路线及总路线长度 编号 送货时间(小时) 总路线 长度（米） 送货路线 第一组 3.69 47736 O/51→26→24→19→25→41→44→48→46→33→28→30 →29→20→22→15→12→11→13→O/51（图四） 第二组 3.79 52743 O/51→18→8→2→5→4→3→1→6→7→10→9→14→16→ 32→35→23→17→21→O/51（图五） 第三组 3.47 42421 O/51→27→39→36→38→43→42→49→50→45→40→37→ 47→34→31→O/51（图六） 图四 图五 图六 结果：最终三组的路线长度分别为：47.736公里，52.743公里,42.421公里均匀性很好，总路线长度为142.9公里。 送完所有快件的时间为：T总=T1+T2+T3=10.95小时 为了检验该结果，我们还计算了把50个送货点只分一组，在不考虑送货员最大载重和体积的情况下，送货员的最短路线长度为：119.762公里。但分组变多时，由于路线的重复，总路线会增加，本结果增加了23公里，这是可以容忍的。 六、 模型的评价与改进： 给定一个完备加权图,确定初始H圈,列出该初始H圈加点序边框的距离矩阵,然后用二边逐次修正法对矩阵进行“翻转”,就可得到近似最优解的距离矩阵,从而确定近似最佳H圈。最佳哈密尔顿圈是一个NP问题。通常采用近似算法----二边逐次修正法求该问题的近似最优解。用MATLAB编写的程序实现二边逐次修正法过程运行时间长，而且当顶点数较多时，甚至没办法求解。用矩阵翻转方法来实现二边逐次修正法过程，在MATLAB中实现非常简单、快捷,而且适合顶点数较多情况，程序简单、计算时占用内存少,而且可以用一个M文件表示。优化时只需调用这个文件,即可得到近似最优解,这样提高了程序的实用性。 本模型运用图论中最佳推销员路径问题与最佳Ｈ圈中的相关结论，建立了关于该类问题的严格的优化模型，但是用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，初始圈的选择直接决定了结果的好坏，最后得到的结果只能是近似最优解。为了减小误差，我们调用的时候随机搜索了多个初始H圈，但是，误差究竟是存在的。 七、参考文献： 【1】赵静、但琦. 数学建模与数学试验 ，高等教育出版社,2004 【2】贾秋玲、袁冬丽、栾云凤，基于matlab的系统仿真、分析及设计，西北工业大学出版社.2006 【3】龚劬，图论与网络最优化，重庆大学出版社， 1998 【4】姜启源，谢金星，叶俊，数学模型，高等教育出版社，2003 【5】刘来福，数学模型与数学建模，北京师范大学出版社，1997 八、附录 相互之间可直接到达地点之间的距离 function [L]=juli(u,x,y) % u,x,y为表2 ，表3构造数组 format short g for 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); end for 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); end L=round(p); Floyd算法求每对地点之间最短路径距离： function[D,R]=floyd(a) n=size(a,1); D=a for i=1:n for j=1:n R(i,j)=j; end end R for k=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 R end 求最佳H圈M文件 function[a,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(:,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 end end s=0; for i=2:n-2; s=s+e(i,i+1);%求优化后H圈的总权. end e; s %结果可能是近似最优解,多代几个初始H圈. 比较各自的近似最优解,可得到最佳H圈. 用矩阵翻转方法来实现二边逐次修正法过程，求最佳哈密尔顿圈（H圈） clc clear load(＇D1.txt＇); D=D1;%floyd算法求得的每对地点之间最短路径矩阵 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)); end u2=[51];%定义点O/51为起始点 for i=1:21 u2(i+1)=u1(i); end for i=1:22 for j=1:22 e(i,j)=D(u2(i),u2(j)); end end E=zeros(25,25); %列出该初始H圈加点序边框的距离矩阵 for i=1:23; E(1,i)=i-1; E(25,i)=i-1; end E(1,24)=1;E(25,24)=1; for i=1:22 for j=1:22 E(i+1,j+1)=e(i,j); end end for i=2:23 E(24,i)=e(1,i-1); end for i=2:23 E(i,24)=e(i-1,1); end [a,b,s]=h(E);%调用求最佳H圈的h函数. [a,b,s]=h(b); %把得出的结果矩阵再次调用这个函数,即为近似最佳H圈. for i=1:23 l(i)=u2(a(1,i+1));%列出送货员送货路线 end L(q,:)=l; S(q)=s;%送货员走的总路线长度矩阵 End 对送货地点的分组 clc clear D=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 end end z1,z2,z3 %这三个点是各组的基点 p=1;m=1;n=1;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; end end Z1,Z2,Z3 %对送货地点的分组的初始分组 表1 各货物号信息表 货物号 送达地点 重量(公斤) 体积(立方米) 不超过时间 1 13 2.50 0.0316 9：00 2 18 0.50 0.0354 9：00 3 31 1.18 0.0240 9：30 4 26 1.56 0.0350 12：00 5 21 2.15 0.0305 12：00 6 14 1.72 0.0100 12：00 7 17 1.38 0.0109 12：00 8 23 1.40 0.0426 12：00 9 32 0.70 0.0481 12：00 10 38 1.33 0.0219 10：15 11 45 1.10 0.0287 9：30 12 43 0.95 0.0228 10：15 13 39 2.56 0.0595 12：00 14 45 2.28 0.0301 9：30 15 42 2.85 0.0190 10：15 16 43 1.70 0.0782 10：15 17 32 0.25 0.0412 12：00 18 36 1.79 0.0184 12：00 19 27 2.45 0.0445 12：00 20 24 2.93 0.0420 9：00 21 31 0.80 0.0108 9：30 22 27 2.25 0.0018 12：00 23 26 1.57 0.0210 12：00 24 34 2.80 0.0103 9：30 25 40 1.14 0.0155 9：30 26 45 0.68 0.0382 9：30 27 49 1.35 0.0144 10：15 28 32 0.52 0.0020 12：00 29 23 2.91 0.0487 12：00 30 16 1.20 0.0429 12：00 31 1 1.26 0.0250 32 2 1.15 0.0501 33 3 1.63 0.0483 34 4 1.23 0.0006 35 5 1.41 0.0387 36 6 0.54 0.0067 37 7 0.70 0.0129 38 8 0.76 0.0346 39 9 2.14 0.0087 40 10 1.07 0.0124 41 11 1.37 0.0510 42 12 2.39 0.0428 43 13 0.99 0.0048 44 14 1.66 0.0491 45 15 0.45 0.0209 46 16 2.04 0.0098 47 17 1.95 0.0324 48 18 2.12 0.0554 49 19 3.87 0.0262 50 20 2.01 0.0324 51 21 1.38 0.0419 52 22 0.39 0.0001 53 23 1.66 0.0502 54 24 1.24 0.0534 55 25 2.41 0.0012 56 26 1.26 0.0059 57 27 0.42 0.0224 58 28 1.72 0.0580 59 29 1.34 0.0372 60 30 0.06 0.0402 61 31 0.60 0.0274 62 32 2.19 0.0503 63 33 1.89 0.0494 64 34 1.81 0.0325 65 35 1.00 0.0055 66 36 1.24 0.0177 67 37 2.51 0.0361 68 38 2.04 0.0110 69 39 1.07 0.0440 70 40 0.49 0.0329 71 41 0.51 0.0094 72 42 1.38 0.0455 73 43 1.31 0.0121 74 44 1.26 0.0005 75 45 0.98 0.0413 76 46 1.35 0.0241 77 47 2.12 0.0230 78 48 0.54 0.0542 79 49 1.01 0.0566 80 50 1.12 0.0284 81 25 0.79 0.0011 82 46 2.12 0.0492 83 32 2.77 0.0034 84 23 2.29 0.0054 85 20 0.21 0.0490 86 25 1.29 0.0088 87 19 1.12 0.0249 88 41 0.90 0.0038 89 46 2.38 0.0434 90 37 1.42 0.0020 91 32 1.01 0.0300 92 33 2.51 0.0133 93 36 1.17 0.0020 94 38 1.82 0.0308 95 17 0.33 0.0345 96 11 0.30 0.0172 97 15 4.43 0.0536 98 12 0.24 0.0056 99 10 1.38 0.0175 100 7 1.98 0.0493 表2 50个位置点的坐标 位置点 X坐标(米) Y坐标(米) 1 9185 500 2 1445 560 3 7270 570 4 3735 670 5 2620 995 6 10080 1435 7 10025 2280 8 7160 2525 9 13845 2680 10 11935 3050 11 7850 3545 12 6585 4185 13 7630 5200 14 13405 5325 15 2125 5975 16 15365 7045 17 14165 7385 18 8825 8075 19 5855 8165 20 780 8355 21 12770 8560 22 2200 8835 23 14765 9055 24 7790 9330 25 4435 9525 26 10860 9635 27 10385 10500 28 565 9765 29 2580 9865 30 1565 9955 31 9395 10100 32 14835 10365 33 1250 10900 34 7280 11065 35 15305 11375 36 12390 11415 37 6410 11510 38 13915 11610 39 9510 12050 40 8345 12300 41 4930 13650 42 13265 14145 43 14180 14215 44 3030 15060 45 10915 14235 46 2330 14500 47 7735 14550 48 885 14880 49 11575 15160 50 8010 15325 表3 相互到达信息 序号 位置点1 位置点2 1 1 3 2 1 8 3 2 20 4 2 4 5 3 8 6 3 4 7 4 2 8 5 15 9 5 2 10 6 1 11 7 18 12 7 1 13 8 12 14 9 14 15 9 10 16 10 18 17 10 7 18 11 12 19 12 13 20 12 25 21 12 15 22 13 18 23 13 19 24 13 11 25 14 18 26 14 16 27 14 17 28 14 21 29 15 22 30 15 25 31 16 23 32 17 23 33 18 31 34 19 24 35 20 22 36 21 26 37 21 36 38 21 17 39 22 30 40 23 17 41 24 31 42 25 41 43 25 19 44 25 29 45 27 31 46 28 33 47 29 22 48 30 28 49 30 41 50 31 26 51 31 34 52 32 35 53 32 23 54 33 46 55 33 28 56 34 40 57 35 38 58 36 45 59 36 27 60 37 40 61 38 36 62 39 27 63 40 34 64 40 45 65 41 44 66 41 37 67 41 46 68 42 43 69 42 49 70 43 38 71 44 48 72 44 50 73 45 50 74 45 42 75 46 48 76 47 40 77 48 44 78 49 50 79 49 42 80 50 40 81 O 18 82 O 21 83 O 26 本文档由香当网(https://www.xiangdang.net)用户上传
