送货线路设计问题数学建模.doc

数学建模论文送货路线设计问题xx xx xx 20 年7月7日摘要针对本题要解决的问题，由于它不是一个完全的欧拉回路，但它可以转化为在遍历所有要送达货物节点的前提下，使总路程最小。用Floyd 算法迭代出任意两点最短路的距离矩阵，并将原来的图构造成完全图。问题一：将130 号货物送到指定地点并返回，构造最优Hamilton 回路，设计出最快完成路线与方式，给出结果为总路程是：W=53787.24m；最优时间是：T=3.7411h。问题二：基于问题一，在添加了时间限制的情况下，即在满足时间条件约束时求最短路径的问题，从而转化多区域最短路模型，设计最佳方案，给出结果为总路程：W=5499.64m；总时间为：T=11.7911h。问题三：由于考虑到送货员一次送货所能承载的最大重量和体积，要达到送货时间最短， 从而转化为多阶段最短路模型，设计最佳方案，给出结果。关键字：Floyd算法 多区域最短路 多阶段最短路问题 欧拉回路 Hamilton 回路22一、问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。二、模型假设1假设送货员的最大载重是50公斤，所带货物的最大体积为1立方米；2假设送货员回到出发点O后取货时间不计；3每件货物交接花费3分钟，同一地点有多件货物也简单按照没见3分钟交接计算；4对于某些至少要经过两次以上的送货点，认为仅在第一次经过是停留，即每第一次经过时就把所有货物一次性送到；5要求到达的时间不包括此次在该点交易的时间；6所用的精确数据都精确到0.01m，时间精确到0.0001h；7在满足时间限制的条件下，顾客能够更早的拿到货物，顾客的满意度越高；8送货员在多次经过同一送货地点时，在第一次经过就交接货物效率最高。三、符号说明符号符号说明送货点的标号从O点回到O点的最短回路距离从O点回到O点所用的总时间从送货点到送货点的最短距离送货员的平均速度从O点到的最短时间到达可以带的最多货物质量到达可以带的最大的货物体积一次可以携带的最多货物的总质量一次可以携带的最多货物的总体积四、问题分析送货路线问题可以理解为：已知起点和终点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题一130号货物的总重量是48.5 公斤，总体积是0.88 立方米，均在送货员的最大承受范围，所以不用考虑送货员返回取货。由于送货地点确定，在每个送货地点交界的时间均为3 分钟，因此总的交接时间确定，只需要求解最优路线问题。若不考虑送货员最大载重和体积，两个位置点边上的权表示距离，于是问题就成为在加权图中寻找一条经过每个位置点至少一次的最短闭通路问题，即求最佳哈密尔顿圈。对于问题二则要考虑每件货物送达时间的要求，而每件货物对应相应的送货地点，从而转化为到达指定送货地点的时间限制，而时间的限制可以分为几个时间段，因此采用以时间为基础的多区域最短路的假设模型从而找出最优解。对于问题三要在体积和质量的双重限制下得到送货员最快完成送货的路线，1100号货物的总重量是148 公斤，总体积是2.8 公斤，根据时间和体积的限制，送货员至少要往返三次送货，又由于每次不可能刚好带满50kg而如果只要三次则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次，所以将问题分为四个阶段进行求解。五、模型的建立与求解我们使用Flody算法求出两点间的最短路径，图采用邻接矩阵的形式描述，w(i,j)表示结点i到结点j间的最短距离，如果没有直接连通，则为无穷大，计算机中可以用一个很大的数据来代替。从图的带权邻接矩阵A=a(i,j)nn开始，递归的进行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和j之间的所有其它点进行松弛。其状态转移方程如下：mapi,j:=minmapi,k+mapk,j,mapi,j其中：mapi,j表示i到j的最短距离；k是穷举i,j的断点;mapn,n的初值应该为0，或者按照题目意思来做。如果这条路没有通的话，还必须特殊处理，比如没有mapi,k这条路。算法过程如下：1.把图用用矩阵G表示出来，如果从Vi到Vj有路可达，则Gi,j=的，d表示该路的长度；否则Gi,j=空值2.定义一个矩阵D用来记录所插入点的信息，Di,j表示从Vi到Vj要经过的点，初始化为Di,j=j。3.把各个顶点插入图中，比较插点后的距离与原来的距离，Gi,j=min(Gi,j,Gi,k+Gk,j),如果GI,j的值变小，则Di,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.4kg50kg =0.8371m31m3所以可以一次把货物携带并进行运送。由与的关系可知要使所用的时间最少即所走的距离最短。所以目标函数为：约束条件是：必须遍历全部顶点并最终回到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最优的路线是：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续表：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.在具体问题中，根据限制条件合理划分区域处理，使问题得以简化，同时，在分类时提出了理论依据，不是简单的依据经验，客观性很强，具有一定的创新性和先进性。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：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.0493表2 50个位置点的坐标位置点X坐标(米)Y坐标(米)1918550021445560372705704373567052620995610080143571002522808716025259138452680101193530501178503545126585418513763052001413405532515212559751615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641011510381391511610399510120504083451230041493013650421326514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325表3 相互到达信息序号位置点1位置点21132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213638211739223040231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26附录21、邻接矩阵的求解程序%求邻接矩阵a1clcclear alla=11000 8250;9185 500;1445 560;7270 570;3735 670;2620 995;10080 1435;10025 2280;7160 2525;13845 2680;11935 3050;7850 3545;6585 4185;7630 5200;13405 5325;2125 5975;15365 7045;14165 7385;8825 8075;5855 8165;780 8355;12770 8560;2200 8835;14765 9055;7790 9330;4435 9525;10860 9635;10385 10500;565 9765;2580 9865;1565 9955;9395 10100;14835 10365;1250 10900;7280 11065;15305 11375;12390 11415;6410 11510;13915 11610;9510 12050;8345 12300;4930 13650;13265 14145;14180 14215;3030 15060;10915 14235;2330 14500;7735 14550;885 14880;11575 15160;8010 15325;%a是各个点的坐标for i=1:51 for j=1:51 t=a(i,:)-a(j,:); c(i,j)=sqrt(t(1)2+t(2)2);%两点之间的直线距离 endendg=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;51 18;51 21;51 26;%通路表b=zeros(51);for i=1:83 b(g(i,1),g(i,2)=1; b(g(i,2),g(i,1)=1; %b方阵为各点的联通关系，为1说明连通，为0则不连通enda1=b.*c;%a1 各联通点距离 for i=1:51 for j=1:51 if a1(i,j)=0 a1(i,j)=inf; end if i=j a1(i,j)=0; end endendFloyd算法函数function Floyd(w,router_direction,MAX)%w为此图的距离矩阵%router_direction为路由类型：0为前向路由；非0为回溯路由 %MAX是数据输入时的的实际值len=length(w);flag=zeros(1,len); %根据路由类型初始化路由表R=zeros(len,len);for i=1:lenif router_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); %处理端点有权的问题for i=1:lentmp=w(i,i)/2;if tmp=0w(i,:)=w(i,:)+tmp;w(:,i)=w(:,i)+tmp;flag(i)=1;w(i,i)=0;endend%Floyd算法具体实现过程for i=1:lenfor j=1:lenif j=i | w(j,i)=MAXcontinue;endfor k=1:lenif k=i | w(j,i)=MAXcontinue;endif w(j,i)+w(i,k)w(j,k) %Floyd算法核心代码w(j,k)=w(j,i)+w(i,k);if router_direction=0 %前向路由R(j,k)=R(j,i);else %回溯路由R(j,k)=R(i,k);endendendend%显示每次的计算结果disp(w(,num2str(i),)dispit(w,0);disp(R(,num2str(i),)dispit(R,1);end%中心和中点的确定Center,index=min(max(w);disp(中心是V,num2str(index);Middle,index=min(sum(w);disp(中点是V,num2str(index);endfunction dispit(x,flag)%x：需要显示的矩阵%flag：为0时表示显示w矩阵，非0时表示显示R矩阵len=length(x);s=;for j=1:lenif flag=0s=s sprintf(%5.2ft,x(j,:);elses=s sprintf(%dt,x(j,:);ends=s sprintf(n);enddisp(s);disp(-);end 运行Floyd(a1,1,inf) %a1为邻接矩阵2、问题一的求解程序clear allclcformat shortw=数据太多省略;p1=7;p2=10;sum=0;w(:,1)=inf;w(:,p1)=inf;w(:,p2)=inf;w(13,16)=inf;w(16,13)=inf;x1=1,p1;x2=p2,1;for i=1:15 s1,t1=min(w(p1,:); s2,t2=min(w(p2,:); sum=sum+s1+s2; w(:,t1)=inf; w(:,t2)=inf; p1=t1; p2=t2; if t1=9|t2=9 disp(到达24时所走的距离) disp(sum) T=sum/1000/24+3*i/60; disp(到24所用的时间) disp(T) end if t1=t2 x1=x1,t1; x=x1,x2; break; end x1=x1,t1; x2=t2,x2; x=x1,x2;enddisp(顺序为：)disp(x)disp(总的路程为：)disp(sum)T=sum/1000/24+3*30/60;disp(总的时间是：)disp(T)3、问题二的求解程序clcclear allw=inf 5295.49 2182.03 4709.245295.49 inf 3113.46 5714.342182.03 3113.46 inf 3883.844709.24 5714.34 3883.84 inf;disp(第一个区域)p=1;x=1;sum=0;v=w;T=0;w(:,p)=inf;for i=1:3 s,t=min(w(p,:); sum=sum+s; T=s/1000/24+T; disp(t,T) T=T+3/60; w