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

数学建模论文送货路线设计问题xxxxxx20年7月7日21 摘要针对本题要解决的问题，由于它不是一个完全的欧拉回路，但它可以转化为在遍历所有要送达货物节点的前提下，使总路程最小。用Floyd算法迭代出任意两点最短路的距离矩阵，并将原来的图构造成完全图。问题一：将1~30号货物送到指定地点并返回，构造最优Hamilton回路，设计出最快完成路线与方式，给出结果为总路程是：W=53787.24m；最优时间是：T=3.7411h。问题二：基于问题一，在添加了时间限制的情况下，即在满足时间条件约束时求最短路径的问题，从而转化多区域最短路模型，设计最佳方案，给出结果为总路程：W=5499.64m；总时间为：T=11.7911h。问题三：由于考虑到送货员一次送货所能承载的最大重量和体积，要达到送货时间最短，从而转化为多阶段最短路模型，设计最佳方案，给出结果。关键字：Floyd算法多区域最短路多阶段最短路问题欧拉回路Hamilton回路21 一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1.若将1~30号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2.假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。二、模型假设1．假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2．假设送货员回到出发点O后取货时间不计；3．每件货物交接花费3分钟，同一地点有多件货物也简单按照没见3分钟交接计算；4．对于某些至少要经过两次以上的送货点，认为仅在第一次经过是停留，即每第一次经过时就把所有货物一次性送到；5．要求到达的时间不包括此次在该点交易的时间；6．所用的精确数据都精确到0.01m，时间精确到0.0001h；7．在满足时间限制的条件下，顾客能够更早的拿到货物，顾客的满意度越高；8．送货员在多次经过同一送货地点时，在第一次经过就交接货物效率最高。三、符号说明符号符号说明送货点的标号从O点回到O点的最短回路距离21 从O点回到O点所用的总时间从送货点到送货点的最短距离送货员的平均速度从O点到的最短时间到达可以带的最多货物质量到达可以带的最大的货物体积一次可以携带的最多货物的总质量一次可以携带的最多货物的总体积四、问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题一1~30号货物的总重量是48.5公斤，总体积是0.88立方米，均在送货员的最大承受范围，所以不用考虑送货员返回取货。由于送货地点确定，在每个送货地点交界的时间均为3分钟，因此总的交接时间确定，只需要求解最优路线问题。若不考虑送货员最大载重和体积，两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈。对于问题二则要考虑每件货物送达时间的要求，而每件货物对应相应的送货地点，从而转化为到达指定送货地点的时间限制，而时间的限制可以分为几个时间段，因此采用以时间为基础的多区域最短路的假设模型从而找出最优解。对于问题三要在体积和质量的双重限制下得到送货员最快完成送货的路线，1~100号货物的总重量是148公斤，总体积是2.8公斤，根据时间和体积的限制，送货员至少要往返三次送货，又由于每次不可能刚好带满50kg而如果只要三次则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次，所以将问题分为四个阶段进行求解。五、模型的建立与求解我们使用Flody算法求出两点间的最短路径，图采用邻接矩阵的形式描述，w(i,j)表示结点i到结点j间的最短距离，如果没有直接连通，则为无穷大，计算机中可以用一个很大的数据来代替。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归的进行n次更新，即有矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)……，最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继结点矩阵path来记录两点间的最短路径，采用得是松弛技术，对在i和j21 之间的所有其它点进行松弛。其状态转移方程如下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}其中：map[i,j]表示i到j的最短距离；k是穷举i,j的断点;map[n,n]的初值应该为0，或者按照题目意思来做。如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。算法过程如下：1.把图用用矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=的，d表示该路的长度；否则G[i,j]=空值2.定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj要经过的点，初始化为D[i,j]=j。3.把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j]),如果G[I,j]的值变小，则D[i,j]=k，在G中包含有两点之间最短道路的信息，而在D中包含了最短通路径的信息。5.1问题一5.1.1模型的建立根据所给图表可知道30件货物需要到达21个不同的地点，所以有=13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。且该30件货物的质量和和体积和分别为为：=47.4kg＜50kg=0.8371m3＜1m3所以可以一次把货物携带并进行运送。由与的关系可知要使所用的时间最少即所走的距离最短。所以目标函数为：约束条件是：必须遍历全部顶点并最终回到O点，即求出从O点出发遍历本张图的21个点的并回到O点的最短距离。为使距离最短则一个点到达另一点的距离也要最短，即从O点开始找到距离O点最短距离的点后再以这一点为起点寻找下一点，以此类推即可求出一个最优回路本题要求出回到O点则可以看到两个开始最短遍历的点在某点重合即可完成最短的遍历。5.1.2模型的求解由图可以明显得出距离O点最近的点是21点和26点。由于32点到38点的距离小于32点到16点的距离为使从21点出来的线遍历右下的点完后再和26点出来的汇合则安排32点到35点断开。遍历节点路线是：0-21-17-23-32-16-14-18-13-24-34-40-45-49-42-43-38-36-39-27-31-26-0最优的路线是：21 0-21-17-23-32-23-16-14-21-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-0总路程是：W=53787.24m最优时间是：T=3.7411h5.2问题二5.2.1模型的建立本问也是图上点的遍历性问题。但此问多出时间限制因素。首先考虑借鉴第一问的结论，是否满足时间限制。由第一问模型建立可知到达24点所走的距离为：40511m，所以可求得到达24点所用时间为：2.0880。由表1（见附录1）可知到达24点必须在九点前，即t(24)<1，所以模型一不适用于问题二求解。考虑到时间因素，可将21个点按时间先后分为四部分，将问题转化为多区域规划问题，求出各个区域的最短距离和到达时的时间即可。统计可得:不超过九点的货物组成的集合为(18,13,24);不超过九点半的货物组成的集合为(31,34,40,45);不超过十点十五的货物组成的集合为(38,42,43,49）;不超过十二点的货物组成的集合为(14,16,17,21,23,26,32,36)。目标函数：约束条件是：T到各个点的时间最大值5.2.2模型的求解分析可得：1区与2区过渡点为24；2区与3区过渡点为45；3区与4区过渡点为38。由此可将每个阶段简化为已知起点和终点的独立模型求出每一阶段的最短路径。求出最短路径为：0-18-13-19-24-31-34-40-45-42-49-42-43-38-35-32-23-16-14-17-21-36-27-39-27-31-26-0计算可得：表1到达各点实际时间顺次到点0181319243134累计距离02182.0295295.4928751.19211009.83212789.98215114.732到达时刻88.1409188.3206468.4646338.6087438.78291598.9297805续表：21 4045424942433816745.51219962.52222314.24224285.62226257.00227174.67229793.3129.04772979.33177189.47976019.61190099.69404189.83227819.991388续表：3532231614172131203.04232317.04233628.91235726.55238334.23240529.95242353.86210.05012710.24654310.40120510.53860610.6972610.83874810.964744续表：362739273126045234.04247437.96249217.8850997.852065.5553602.5854994.6411.13475211.32658211.4507511.5249111.569411.7334411.79144由上表可知，所有时间点都满足限制条件，得出结果为：总路程：W=5499.64m；总时间为：T=11.7911h5.3问题三5.3.1模型的建立本题中要遍历所有的50个点但由于=147kg，=2.8m3而<50kg,<1m3故应该以<50kg和<1m3为判断标准使到达的最远的点后返回。目标函数：约束条件：<50kg,<1m3由于总的=148kg，=2.8m3且每次不可能刚好带满50kg而如果只要3次则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次，所以分为四个阶段。由O开始逐渐依次找出最近的点后再找出离该点最近的点直到不满足约束条件。六、模型的评价6.1优点1.Floyd算法适用于APSP，是一种动态规划算法，稠密图效果最佳，边权可正可负，此算法简单有效，一由于三重循环结构紧凑，对于稠密图，效率较高。容易理解，可以算出任意节点之间的最短距离，代码编写简单。2.本模型在建模过程中，对送货员送货的过程以及交接时间做了合理的简化，建立了最短路模型，模型简单、清晰，具有一定的普遍意义。3.在具体问题中，根据限制条件合理划分区域处理，使问题得以简化，同时，在分类时提出了理论依据，不是简单的依据经验，客观性很强，具有一定的创新性和先进性。21 4.充分利用了已知数据建立模型，使其具有很高的准确性和可行性。5.使用了准确的算法和适当的假设，使模型的准确性和实用性到达统一。6.运用功能强大的Matlab工具使数据处理误差达到最小。6.2缺点1.Floyd算法时间复杂度比较高，不适合计算大量数据。2.缺乏某些专业的知识和数据，是讨论无法更加深入进行。3.由于数据较多，没法使用工具进行模型的验证，只能一步一步的精化模型。七、参考文献[1]胡运权等,运筹学基础与应用(第四版)[M],北京：高等教育出版社,2005.[2]方世昌,离散数学[M],西安：西安电子科技大学出版社,2008.[3]朱战立,数据结构[M],西安：西安交通大学出版社,2004.八、附录：附录1表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：0021 21310.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.022421 58281.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.030821 95170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.0493表250个位置点的坐标位置点X坐标(米)Y坐标(米)19185500214455603727057043735670526209956100801435710025228087160252591384526801011935305011785035451265854185137630520014134055325152125597516153657045171416573851888258075195855816520780835521127708560222200883523147659055247790933025443595252610860963527103851050028565976521 2925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表3相互到达信息序号位置点1位置点211321832204245386347428515952106111718127121 1381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213638211739223040231741243142254143251944252945273146283347292248302849304121 50312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26附录21、邻接矩阵的求解程序%求邻接矩阵a121 clcclearalla=[110008250;9185500;1445560;7270570;3735670;2620995;100801435;100252280;71602525;138452680;119353050;78503545;65854185;76305200;134055325;21255975;153657045;141657385;88258075;58558165;7808355;127708560;22008835;147659055;77909330;44359525;108609635;1038510500;5659765;25809865;15659955;939510100;1483510365;125010900;728011065;1530511375;1239011415;641011510;1391511610;951012050;834512300;493013650;1326514145;1418014215;303015060;1091514235;233014500;773514550;88514880;1157515160;801015325];%a是各个点的坐标fori=1:51forj=1:51t=a(i,:)-a(j,:);c(i,j)=sqrt(t(1)^2+t(2)^2);%两点之间的直线距离endendg=[13;18;220;24;38;34;42;515;52;61;718;71;812;914;910;1018;107;1112;1213;1225;1215;1318;1319;1311;1418;1416;1417;1421;1522;1525;1623;1723;1831;1924;2022;2126;2136;2117;2230;2317;2431;2541;2519;2529;2731;2833;2922;3028;3041;3126;3134;3235;3223;3346;3328;3440;3538;3645;3627;3740;3836;3927;4034;4045;4144;4137;4146;4243;4249;4338;4448;4450;4550;4542;4648;4740;4844;4950;4942;5040;5118;5121;5126];%通路表b=zeros(51);fori=1:83b(g(i,1),g(i,2))=1;b(g(i,2),g(i,1))=1;%b方阵为各点的联通关系，为1说明连通，为0则不连通enda1=b.*c;%a1各联通点距离fori=1:51forj=1:51ifa1(i,j)==0a1(i,j)=inf;endifi==ja1(i,j)=0;end21 endendFloyd算法函数functionFloyd(w,router_direction,MAX)%w为此图的距离矩阵%router_direction为路由类型：0为前向路由；非0为回溯路由　%MAX是数据输入时的∞的实际值len=length(w);flag=zeros(1,len);%根据路由类型初始化路由表R=zeros(len,len);fori=1:lenifrouter_direction==0%前向路由R(:,i)=ones(len,1)*i;else%回溯路由R(i,:)=ones(len,1)*i;endR(i,i)=0;enddisp("");disp("w(0)");dispit(w,0);disp("R(0)");dispit(R,1);%处理端点有权的问题fori=1:lentmp=w(i,i)/2;iftmp~=0w(i,:)=w(i,:)+tmp;w(:,i)=w(:,i)+tmp;flag(i)=1;w(i,i)=0;endend%Floyd算法具体实现过程fori=1:lenforj=1:lenifj==i||w(j,i)==MAXcontinue;end21 fork=1:lenifk==i||w(j,i)==MAXcontinue;endifw(j,i)+w(i,k)