[数学]送货路线设计方案论文.doc

送货路线设计方案 摘 要本文是关于快递公司送货策略的优化设计问题，即在给定送货地点和给定设计规范的条件下，确定业务员的运行线路，总的运行路程数，以及时间最省的策略。根据设计要求，制定了从静态规划到动态规划的解题思路；建立了以送货时间最省、所走路程最短等为目的的优化模型，给出的不同优化目标和约束下的优化送货策略，即送货路径。本文主要完成的工作有： 根据所给的数据，使用Dijstra算法，循环n（n为总的点个数）次。求出各点之间的最短路程，并存入二维数组distij中。 对问题一，在送货员遵循送货路线的要求前提下，以所用的时间最短为目标函数，遍历全部的21个点并回到0点，在此条件下，利用动态规划得到了一条最短路径的优化设计。 对问题二，为考虑送货时间限制，需采用多次分区域的优先时间模型，而每个区域的路径优化设计可利用问题一的模型，同时遍历完一区域后，利用其最后一点找到与它距离最短的下一区域的点，若无连通的，则找次短的。这样重复下去，直到所有的区域都遍历完。最后，从最后一点返回起始点0。如此得到的路径即为我们所需的优先时间的优化设计路径。 对问题三，其约束条件是送货员所能承受的货物的重量和体积的限制，在此前提下，则可利用多阶段送货模型，进行路线得优化设计。并且，如何实现分阶段需要进行客观实际的分析，在把握使误差最小和灵敏度最高的情况下来进行分阶段，各阶段的最优路径设计与问题二中个区域的路径设计是大同小异的，故如何分阶段，分几个阶段对解决问题三的极其重要的，也是关键的一步。关键字：路径规划，最优化，图模型，多目标动态规划，送货员送货，分区域，分阶段 一、 问题重述与分析1.1问题重述 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。图1 快递公司送货地点示意图O点为快递公司地点，O点坐标(11000,8250),单位：米注：表1“各货物号信息表”、 表2“50个位置点的坐标”、 表3“相互到达信息”见附录11.2问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的重量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题二要考虑到所到的点的时间要求是否满足题意即采用多次分区域的假设模型，从而找出最优的解。对于问题三则要考虑到体积和重量的双重影响，每次到达后找到最大的体积和重量的点然后返回，再依次分析各个步骤中可能存在的不合理因素，达到模型的进一步合理优化，得到最合理的解。二、 模型假设根据题意，可以进行如下假设：1、同一地点有多件货物也简单按照每件货物3分钟交接时间计算2、所用的距离数据都精确到米，而时间则精确到0.0001h3、要求达到不超过的时间不包括此次在该店交易的时间4、到同一地点的货物要依次拿上，即不考虑在以后经过时再带一些货物5、无塞车现象，即业务员送快递途中不受任何外界因素影响6、货物可进行任意拆分三、符号说明 符号 符号说明 i,j 货物点的标号 A 51个点的坐标矩阵 a 各点的连通关系矩阵 w 点的权值（距离）矩阵 v 送货员的平均速度 从o点到i区域所用的最短时间 到达i区域可以带的最多的货物的质量 到达i区域可以带的最多的货物的体积 M 一次可以携带的最多的货物的总质量 V 一次可以携带的最多的货物的总体积其中i、j=1、2、3.51, 且M=50kg，V=1三、 模型的建立与求解本文模型的整体框架如下：模型一模型四模型三模型二模型一多阶段最短路径模型最短路径模型图的遍历模型多区域最短路径模型由起始点通过多阶段遍历返回由起始点经多区域遍历返回由起始点遍历回到原点任意两点最短距离模型一1.1 模型的建立我们为了求出各点之间的最短路程，使用Floyd算法，即在Dijstra算法上循环n（n为总的点个数）次。1.2 模型的求解根据算法和相邻点的距离可以用Dijstra算法求出任意两点的最短距离。图采用权值矩阵的形式描述，w(i,j)表示i点到j点的距离。如果没有直接连通，则为无穷大，即用Matlab中的inf表示。Dijstra算法只能求出结点i到其余各点的距离。算法引入这样的两个集合s和t，s是确定了的到结点i最短距离的点，t为全集u和s的差集即那些还未确定最短路径的结点。而且s的初值是i,t的初值是u-i。另外在引入一个标记数组distn，其中在某一步中distk表示当前i到k的最短距离，distk的初值是w(i,k)。整个算法过程如下：1、 在t中悬着一个dk最小的节点k，将k并入s,并从t中去掉，若果t为，则转到3；2、 用k结点和t中其余的结点进行一遍比较，如果distidistk+wki，则用disti= dist k+wki 取代原来的di，重复1；3、 算法结束，此时distk中保存的就是从i到k结点的最短路径。 算法就是以这样非常简单的形式完成了求解，时间复杂度是o(n2)确定了从i点到其余各结点的最短路径。图1 相邻点的距离使用循环的结构求出151各个点之间的最短距离。程序1见附录2.1。可求出最短距离的权值矩阵di。模型二 对问题一得求解2.1 模型的建立 由前三十件货物可以到达的地点可以知道，i,j=13 18 31 26 21 14 17 23 32 38 45 43 39 42 36 27 24 34 40 49 16。图2 需要到达的点（用红色表示）其中共经过21个点，送运30件货物因该30件货物=47.3kg50kg，=0.83711，故可以一次把货物携带进运送。由t与l的关系可知，要使所用的时间最小即所走的路程最小。即目标函数是： 约束条件是：必须全部遍历并回到0点即从0点出发全部遍历这图的21个点并回到0点的最短距离。要距离最短则每一步都要最短，即从0点开始找最短的点到达后，继续找未遍历的最短的点，则可求出最短的距离。本题要求回到0点，则是两个开始最短遍历的点在某点重合。2.2 模型的求解 其求解的程序代码见附录2.2其结果如下：顺序为： Columns 1 through 18 1 19 19 27 27 22 22 22 18 24 37 37 39 28 44 22 32 32 Columns 19 through 22 32 35 43 24遍历路程为： 4.1605e+004返回路程为： 3.9968e+003总的路程为： 4.5602e+004总的时间为： 3.4001 (h)模型三 对问题二的求解3.1 模型的建立 为满足时间的约束条件，先把时间分成三个阶段，其30个目的点分布如下（用红色标注）：图3 考虑时间点的位置 注：红色表示第一个时间段8:009:30的点 黑色表示第二个时间段9:3010:15的点 蓝色表示第三个时间段1013512:00的点3.2 模型的求解 其求解的程序代码见附录2.3 其结果如下： 1、第一个时间段顺序为： 1 14 19 25 32 46 35 41 第一个时间段路程为：5.2172e+003 2、第二个时间段顺序为： 41 46 38 42 39 44 43 50 第二个时间段路程为：1.0461e+004 3、第三个时间段顺序及路程为： 50 43 44 39 36 27 22 15 18 24 33 40 37 28 17第三个时间段路程为：2.5134e+004返回路程为： 7.4930e+003总的路程为： 7.2458e+003总的时间为： 3.5127 (h)模型四 对问题三的求解4.1 模型的建立本题中要遍历50个点，但由于M总=147kg，V总=2.8，而m50kg，v1，故因应该以m50kg，v1的标准到达最远点后返回。目标函数：约束条件：m50kg,v14.2 模型的求解 由原点0点开始逐渐依次找出最近的点后，再找出离该点最近的点，直到不满足约束条件。程序见附录2.4图4 分4阶段遍历点的位置 注：第一阶段用红色标注 第二阶段用黑色标注 第三阶段用蓝色标注 第四阶段用紫红色标注 其结果如下： 1、第一阶段 顺序为： 1 27 32 28 40 37 39 36 33 24 18 22 路程为： 3.3340e+003 2、第一阶段 顺序为： Columns 1 through 18 1 19 14 13 12 9 4 2 7 8 11 10 15 17 44 43 50 51 Columns 19 through 21 41 35 35 路程为： 4.2875e+004 3、第一阶段 顺序为： Columns 1 through 18 1 27 32 25 20 26 30 23 31 29 34 47 49 45 42 38 41 48Column 1946 路程为： 4.5159e+004 4、第一阶段 顺序为： 21 16 5 3 6 路程为： 3.8530e+004 总的路程为： 1.9485e+004 总的时间为： 6.9124 (h)五、模型的分析误差分析 对于模型一是使用了精确的Floyd算法，即Dijstra算法故误差可以忽略不计。 对于模型二，虽存在断开的点会出现一定的误差，但对断开的点进行的优化处理，故该模型可以用。 对于模型三，因分区域的方法存在很多，故不可避免的会产生一些误差。有由于分的区域越多，走的路程也就越多，这样可以大大地消除一些误差，故此模型可以用。 对于模型四，该模型有较大的误差，因未考虑货物的拆分对现实会有一定的影响，同时阶段的不同划分也是会存在一些不确定的误差。虽然准确性由一定的挑战性，但相对于其他的划分又有一定的优越性，故该模型适合此问题的求解。灵敏度分析 对于模型一、二、三，灵敏度很好，模型的准确性很高。 对于模型四，由于质量和体积的限制，其灵敏度不是很好，但准确性还是很高，因此模型可以使用。六、模型的评价、改进和推广6.1 模型的评价 优点： 充分的利用了已知数据来建立模型，使其具有很高的准确性和可行性 使用的准确的算法和适当的假设，使模型的准确性和实用性达到统一 运用了功能强大的Matlab工具使数据处理误差达到最小 缺点： 由于数据太多，没法使用工具进行模型的检验，只能一步一步地精化模型6.2 模型的改进 对于模型一和模型三主要进行模型的验证 对于模型二断开的点可以取别的点进行 主要是对模型四的改进，可以考虑到不同的地点送的货物进行拆分，从而可以找到最优的解6.3 模型的推广 可充分使用到图的遍历和最短路径的一系列问题的求解中七、参考文献1：姜启源、谢金星、叶俊编，数学模型-3版，北京，高等教育出版社，2003.8 2：吴建国、汪名杰、李虎军、刘仁云编，数学建模案例精编-1版，北京，中国水利水电出版社，2005.53：唐焕文、贺明峰编，数学模型引论-3版，北京，高等教育出版社，2005.34：图论 任韩5：图论 第三版 德 迪斯特尔 著附录附录1：表格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：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.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.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.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.04931.2 50个位置点的坐标 位置点X坐标(米)Y坐标(米)19185500214455603727057043735670526209956100801435710025228087160252591384526801011935305011785035451265854185137630520014134055325152125597516153657045171416573851888258075195855816520780835521127708560222200883523147659055247790933025443595252610860963527103851050028565976529258098653015659955319395101003214835103653312501090034728011065351530511375361239011415376410115103813915116103995101205040834512300414930136504213265141454314180142154430301506045109151423546233014500477735145504888514880491157515160508010153251.3 互相到达信息 序号位置点1位置点21132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213638211739223040231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26附录2：Matlab程序代码2.1 Djistra(Floyd)算法求解 %Djistra算法 l=0;for i=1:22 dist(i)=ww(1,i); parent(i)=location(i); f(i)=0;endf(1)=1;for i=1:22 cost=inf; k=1; for j=2:22 if dist(j)1 f(k)=1; for t=2:22 if f(t)=0 if dist(t)dist(k)+ww(k,t) dist(t)=dist(k)+ww(k,t); parent(t)=location(k); l=l+dist(t)-dist(k); end end end endend%Floyd算法for i=1:22 for j=1:22 di(i,j)=ww(i,j); dian(i,j)=i; endendfor k=1:22 for i=1:22 for j=1:22 if k=i&k=j&i=j if di(i,j)di(i,k)+di(k,j) di(i,j)=di(i,k)+di(k,j); dian(i,j)=location(k); end end end endend2.2 问题一的求解 clcclear allA=xlsread(weizhi.xls); for i=1:51 for j=1:51 t=A(i,:)-A(j,:); c(i,j)=sqrt(t(1)2+t(2)2);%两点之间的距离 endenda=1 3;1 8;2 20;2 4;3 8;3 4;4 2;5 15;5 2;6 1;7 18;7 1;8 12;9 14;9 10;10 18;10 7;11 12;12 13;12 25;12 15;13 18;13 19;13 11;14 18;14 16;14 17;14 21;15 22;15 25;16 23;17 23;18 31;19 24;20 22;21 26; 21 36;21 17;22 30;23 17;24 31;25 41;25 19;25 29;27 31;28 33;29 22;30 28;30 41;31 26;31 34;32 35;32 23;33 46;33 28;34 40;35 38;36 45;36 27;37 40;38 36;39 27;40 34;40 45;41 44;41 37;41 46; 42 43;42 49;43 38;44 48;44 50;45 50;45 42;46 48;47 40;48 44;49 50;49 42;50 40;0 18;0 21;0 26; %通路表b=zeros(51);for i=1:83 b(a(i,1)+1,a(i,2)+1)=1; b(a(i,2)+1,a(i,1)+1)=1;enda=b.*c;for i=1:51 for j=1:51 if a(i,j)=0 a(i,j)=inf; end; if i=j a(i,j)=0; end endendw=a; location=0 13 18 31 26 21 14 17 23 32 38 45 43 39 42 36 27 24 34 40 49 16;for i=1:22 location(i)=location(i)+1;endfor i=1:22 aa(i,1)=A(location(i),1); aa(i,2)=A(location(i),2);endplot(A(:,1),A(:,2),g*,aa(:,1),aa(:,2),r*)title(51个点在图中的分布22个点用红色表示)xlabel(横坐标)ylabel(纵坐标)hold onfor i=1:51 for j=1:51 if a(i,j)=0&a(i,j)=inf x=A(i,1):1:A(j,1); y=(x-A(i,1)*(A(j,2)-A(i,2)/(A(j,1)-A(i,1)+A(i,2); plot(x,y,b) end endendhold on for i=1:22 for j=1:22 ww(i,j)=w(location(i),location(j); ww(j,i)=ww(i,j); endend%求送货路线l=0;for i=1:22 dist(i)=ww(1,i); parent(i)=location(i); f(i)=0;endf(1)=1;for i=1:22 cost=inf; k=1; for j=2:22 if dist(j)1 f(k)=1; for t=2:22 if f(t)=0 if dist(t)dist(k)+ww(k,t) dist(t)=dist(k)+ww(k,t); parent(t)=location(k); l=l+dist(t)-dist(k); end end end endend%用Floyd求返回路线for i=1:22 for j=1:22 di(i,j)=ww(i,j); dian(i,j)=i; endendfor k=1:22 for i=1:22 for j=1:22 if k=i&k=j&i=j if di(i,j)di(i,k)+di(k,j) di(i,j)=di(i,k)+di(k,j); dian(i,j)=location(k); end end end endenddi(17,1)di(17,1)l=l+di(17,1) parentlll=l*3.6/24ll2=ll/3600+1.52.3 问题二的求解 location1=0 13 18 24 31 45 34 40 ;for i=1:8 location1(i)=location1(i)+1;endfor i=1:8 aa1(i,1)=A(location1(i),1); aa1(i,2)=A(location1(i),2);end plot(A(:,1),A(:,2),g*,aa1(:,1),aa1(:,2),r*)text(A(:,1)+.03,A(:,2),num2cell(1:51);title(51个点在图中的分布22个点用红色表示)xlabel(横坐标)ylabel(纵坐标)hold onfor i=1:51 for j=1:51 if a(i,j)=0&a(i,j)=inf x=A(i,1):0.5:A(j,1); y=(x-A(i,1)*(A(j,2)-A(i,2)/(A(j,1)-A(i,1)+A(i,2); plot(x,y,K) end endendhold on location22=38 43 42 49 ;for i=1:4 location22(i)=location22(i)+1;endfor i=1:4 aa22(i,1)=A(location22(i),1); aa22(i,2)=A(location22(i),2);endplot(aa22(:,1),aa22(:,2),Ko) location33=26 21 14 17 23 32 39 36 27 16;for i=1:10 location33(i)=location33(i)+1;endfor i=1:10 aa33(i,1)=A(location33(i),1); aa33(i,2)=A(location33(i),2);end plot(aa33(:,1),aa33(:,2),C+) %第一层，共7个位置for i=1:8 for j=1:8 ww1(i,j)=w(location1(i),location1(j); endend l=0;for i=1:8 dist1(i)=ww1(1,i); parent1(i)=location1(i); f1(i)=0;endf1(1)=1;for i=1:8 cost=inf; k=-1; for j=2:8 if dist1(j)1 f(k)=1; for t=2:8 if f1(t)=0 if dist1(t)dist1(k)+ww1(k,t) dist1(t)=dist1(k)+ww1(k,t); parent1(t)=location1(t); l=l+dist1(t)-dist1(k); end end end endend parent1l1=l %第二层，共4个位置location2=parent1(8)-1 45 37 41 38 43 42 49 ;for i=1:8 location2(i)=location2(i)+1;endfor i=1:8 aa2(i,1)=A(location2(i),1); aa2(i,2)=A(location2(i),2);endfor i=1:8 for j=1:8 ww2(i,j)=w(location2(i),location2(j); ww2(j,i)=ww2(i,j); endend l=0;for i=1:8 dist2(i)=ww2(1,i); parent2(i)=location2(i); f2(i)=0;endf2(1)=1;for i=1:8 cost=inf; k=-1; for j=2:8 if dist2(j)1 f2(k)=1; for t=2:8 if f2(t)=0 if dist2(t)dist2(k)+ww2(k,t) dist2(t)=dist2(k)+ww2(k,t); parent2(t)=location2(t); l=l+dist2(t)-dist2(k); end end end endend parent2l2=l %第三层location3=parent2(8)-1 42 43 38 35 26 21 14 17 23 32 39 36 27 16;for i=1:15 location3(i)=location3(i)+1;endfor i=