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

1、送货路线设计问题1、 问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少。现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少。该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物的相关信息见表1，50个位置点的坐标见表2。 假定送货员最大载重50公斤，所带货物最大体积1立方米。送货员的平均速度为24公里/小时。假定每件货物交接花费3分钟，为简化起见，同一地点有多件货

2、物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。1. 若将130号货物送到指定地点并返回。设计最快完成路线与方式。给出结果。要求标出送货线路。2. 假定该送货员从早上8点上班开始送货，要将130号货物的送达时间不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。3. 若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返回取货。可不考虑中午休息时间。2、 问题分析送货路线问题可以理解为：已知起点和终

3、点的图的遍历问题的合理优化的路线设计。图的遍历问题的指标：路程和到达的时间，货物的质量和体积，以及最大可以负载的质量和体积。在路线的安排问题中，考虑所走的路程的最短即为最合理的优化指标。对于问题二要考虑到所到的点的时间的要求是否满足题意即采用多次分区域的假设模型从而找出最优的解对于问题三则要考虑到体积和质量的双重影响，每次到达后找到达到最大的体积和质量的点然后返回，再依次分析各个步骤中可能存在的不合理因素达到模型的进一步合理优化得到最合理的解。3、 模型假设与符号说明3.1、模型的假设（1）、到同一地点的货物要一次拿上，即不考虑再以后又经过时再带些货物（2）、要求达到不超过的时间不包括此次在该

4、点交易的时间。（3）、所用的距离数据都精确到米而时间则精确到0.0001h（4）、同一地点有多件货物也简单按照每件3分钟交接计算。3.2、符号说明其中i，j=1、2、350并且M=50kg V=1m34、 模型的建立及求解模型四模型三模型二模型一最短路径模型图的遍历模型多区域最短路多阶段最短路任意两点之间的最短路距离由起始点遍历路径回到原点多区域无返回起点的最短路多阶段有返回起点的最短路模型一1.1模型的建立我们为了求出各个点的之间的最短的路径，使用Dijstra算法求解。 Dijkstra算法是图论中非常有名的一个算法。图采用邻接矩阵的形式描述，w（i,j）表示结点i到结点j间的最短距离，如

5、果没有直接连通，则为无穷大，计算机中可以用一个很大的数据代替（如matlab中的inf）。但dijkstra算法只能求出从结点i到其它各结点的最短路径。算法引入这样两个集合s和t，s是那些已经确定了到i结点的最短路径的结点，t为全集u和s的差集，即那些还未确定最短路径的结点。而且s的初值是i，t的初值是u-i。另外再引入一个标记数组dn，其中在某一步dk表示当前从i到k的较短路径，dk的初值为w（i，k）。整个算法过程如下：、 在t中选择一个dk最小的结点k，将k并入s，并从t中去掉，如果t为则转到；、 用k结点和t中其余结点进行一遍比较，如果di>dk+mki，则用dk+mki取代原来

6、的di，重复；、 算法结束，此时dk中保存的就是从i到k结点的最短路径。算法就以这样非常简单的形式完成了求解，时间复杂度是O(n2)，确定了从i到其余各结点的最短路径。1.2模型的求解根据算法和相邻的点的距离可以用dijkstra求出任意两点的最短路径。图1相邻的点的距离使用循环的结构求出1-50各个点之间的最短距离。程序1见附录2.1可以求出w和aa为最短路径是的所过的的地点如从O开始到其余50个点的a(0)= 0 7 4 8 3 15 1 18 12 14 18 13 13 18 21 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 2

7、8 31 38 21 40 36 27 34 37 43 38 41 36 41 40 46 42 40要从O点到16点则要先到23即0-23-16要从O点到23点则要先到17即0-17-23-16要从o点到17点则要先到21即0-21-17-23-16而O可以直接到21所以从0到16的最优路径是0-21-17-23-16最短的距离是w（0,16）=7493m模型二 对于问题一的求解2.1模型的建立由前30件货物可以到达的地点可以知道i，j= 13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。图2需要达到的点（红点标注

8、的）其中共经过21个点，运送30件货物该30件货物m=47.3kg<50kg v=0.8371m3,所以可以一次把货物携带进行运送。由T与W关系可知要使所用的时间最小即所走的距离最短。即目标函数是：T=W÷V+t0×30 约束条件是：必须全部遍历回到0点即求出从O出发遍历这图的21个点的并回到o的最短的距离要距离最短则每一步也要最短，即从O开始找最短的点到达后继续找未遍历的最短的点则可求出最短的距离。本题要求出回到O点则可以看到两个开始最短遍历的点在某点重合即可完成最短的遍历。2.2模型的求解由图可以明显得出距离O最近的点是21点和26点。由于32点到38点的距离小于

9、32点到16点的距离为使从21点出来的线遍历右下的点完后再和26点出来的汇合则安排32点到35点断开。有程序2（附录2.2）可得：013112132321314334141643615175381618639172174018238421924943202610452127114922遍历节点路线是：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

10、-31-26-0总路程是：W=53787m 最优时间是：T=3.7411h模型三 对于问题二的求解3.1模型的建立 由第一个模型建立的可以求出到达24时所用的时间是:可知到24点的时间是：t(24)=2.0880由表2.1可知必须在9点之前把货物送到24点即t(24)<1故模型一不适用于问题二的求解.由下图3可知：图3.考虑时间的点的位置由于右边的点的地点需要的时间要比左边的早，所以先分两个阶段，即先走左边后走右边即先走圈内的元素由程序3（附录2.3）可得：从O出发经过13、18、24、26、27、31、34、39、40到达455260.10807310.22206270.3165929

11、0.44074240.68353280.89542131.07518311.439310401.557311451.7413而到13点时必须在9点之前到达但1.0751>1，到45点时必须在9点半之前到达而1.7412>1.5故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最短距离和到达时的时间即可。目标函数：ti=Wi÷v+t0约束条件是：T到个点的时间最大值3.2模型的求解图4.4个阶段的圈图对四个阶段分别求出到达的时间，由程序4（附录2.4）可知l 分4个阶段3180.09092130.27064240.55871. 从0出发经过13、18到24。满足t<

12、1的条件故路线为：0-18-13-242310.73293340.92974401.04775451.23172. 从24出发经过31、34、40到45。 满足t<1.5故路线为：24-31-34-40-453421.42975491.56184431.73222381.89133. 从45出发经过38、42、43到49。满足t<2.25所以路线为：45-42-49-43-384. 从38出发经过14、16、17、21、23、26、27、32、36、39回到O。10362.00548272.147211392.32147262.55405212.74544172.87146232.

13、99539323.15003163.44202143.6007满足t<4故路线为：38-36-27-39-27-31-26-21-17-23-32-16-14-21-0所以总的遍历点顺序是：0-18-13-24-31-34-40-45-42-49-43-38-36-27-39-26-21-17-23-32-16-14-0总时间是T=3.9130h总距离是W=57912m最优路线是：0-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-21-17-23-32-23-16-14-21-0到每个点的时间见附录1.4模型四 对于问题

14、三的求解4.1模型的建立本题中要遍历所有的50个点但由于M总=147kg，v 总 =2.8m3而M<50kg,V<1m3故应该以M<50kg和V<1m3判断的标准到达的最远的点后返回。目标函数：W=150w(i,j)约束条件：M<50kg,V<1m34.2模型的求解由O开始逐渐依次找出最近的点后再找出离该点最近的点直到不满足约束条件。见程序5（附录2.5）图5.改进后的遍历图1第一阶段2. 第二阶段3. 第三阶段 4.第四阶段4.3模型的优化由于总的m=148kg v=2.8m3 所以最少要分四个阶段，但由于每次不可能刚好带满50kg而如果只要3次则最多只能

15、带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次。故只需要把上述的模型进行数据处理就好了。过程如下： 1.由于到21点时M=49 V=0.8757若走过14则M大于了50故直接从21点返回。最优路线为： 0-26-31-27-39-27-36-38-35-32-23-17-21-0走的距离W=27122m，花费的时间T=1.73012.若按程序给出的从13到8的路线是13-12-11-12-8而当为13-11-12-8时更短故修改之；同时到达40后如果选择34则45的周围全被遍历过。到45后M=46.83,V=1.0247不满足要求，故从40到34后沿21-26返回。最优

16、路线为:0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0走得距离是：W=83220，所用的时间是T=4.46753. 当到达45点时若要去20点放货物的话则需要遍历许多已经遍历过的地点，故从45点沿36-21-0返回最优路线为： 0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0所走的距离为：W=128970m，所用的时间是：T=6.12384.只余下了5个点,所以由图可知路线为： 0-26-31-24-19-25

17、-15-22-20-2-5-2-4-3-8-12-13-18-o总路程是：W= 171510m所用的时间是T=7.3964由上面的四个阶段可以知道该问的最优路线是：0-26-31-27-39-27-36-38-35-32-23-17-21-0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0-26-31-24-19-25-15-22-20-2-5-2-4-3-8-12-1

18、3-18-o总路程是：W= 171510m所用的时间是T=7.39645、 模型的分析 误差分析：对于模型一是使用了精确地Dijkstra算法，故误差可以忽略不计对于模型二假定了32到38点的断开存在一定的误差，但相对于断开其余的几点得到的数值要小，故该模型可以使用。 对于模型三，由于分区域的方法有很多，故不可避免的存在些许误差，但由于区域越多，路程越多，故选择分成4个区域最合适；分成的四个不同的时间的到达区域比较紧密故按照时间的不同划分了四个区域，从而大大的消除了误差，此模型可以使用。对于模型四的误差比较大，由于未考虑货物的拆分可能会有一定的影响同时由于4个阶段的划分也是有一定的不确定性故误

19、差存在。对于该模型简化了考虑的条件，仅以M和V为判断标准，虽对准确性存在挑战，但该模型相对与其他的分类有明显的优越性。故该模型适用于该问的求解。 灵敏度分析 对于模型一、二、三，灵敏度很好，模型的准确性很高。 对于模型四由于质量和体积的制约，使其灵敏度不会很好，但准确性较高，因此模型可以使用。6、 模型评价、改进和推广6.1模型的评价优点：l 充分利用了已知数据建立模型，使其具有很高的准确性和可行性l 使用了准确的算法和适当的假设，使模型的准确性和实用性到达统一l 运用功能强大的Matlab工具使数据处理误差达到最小缺点l 由于数据较多，没法使用工具进行模型的验证，只能一步一步的精化模型6.2

20、模型的改进对于模型一和三主要是进行验证。 对于模型二断开的那个点可以去取别的点进行。主要是模型四的改进，可以考虑到不同的地点送的货物进行拆分，从而渠道最优的解6.3模型的推广 可充分使用到图的遍历和最短路的一系列问题的求解中。7、 参考文献1.A First Course in Mathenmatical Moderling (Third Edition) Frank R.Giordiano Maurice D.weir William P.Fox2.图论 任韩。3.数学建模案例选集 姜启源 谢金星4.图论 第3版 德 迪斯特尔著5.大学生数学建模竞赛辅导教材 叶其效6.基于matlab 动态

21、规划中最短路线的实现程序 J电脑学习 施益昌 郑贤斌 李自立7.物流配送问题的混沌优化算法研究 中央民族大学学报(自然科学版) 2009年11月第18卷第4期8. Dijkstra 算法在企业物流运输网络中的应用 湖南农业大学学报(自然科学版) 2005年8月第29卷4期附录附录1.、表格1.1各货物号信息表货物号送达地点重量(公斤)体积(立方米)不超过时间1132.500.03169：002180.500.03549：003311.180.02409：304261.560.035012：005212.150.030512：006141.720.010012：007171.380.010912

22、：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：0

23、024342.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.

24、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.032565

25、351.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.29

26、0.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坐标(米)1918550021445560372705704373567052620995610080143571002522808716025259

27、138452680101193530501178503545126585418513763052001413405532515212559751615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641

28、0115103813915116103995101205040834512300414930136504213265141454314180142154430301506045109151423546233014500477735145504888514880491157515160508010153251.3相互到达信息序号位置点1位置点211321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417

29、281421291522301525311623321723331831341924352022362126372136382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740613836623927634034644045654144664137674146684243694249704338714448724450734550744542754648764740774844

30、78495079494280504081O1882O2183O261.4 模型二中到达时的时间点到的时间最大允许的时间000180.09091130.27061240.55871310.73291.5340.92971.5401.04771.5451.23171.5421.42972.25491.56182.25431.73222.25381.89132.25362.00544272.14724392.32144262.5544212.74544172.87144232.99534323.154163.4424143.6007403.9031附录2 、MATLAB程序代码2.1、Dijstra

31、 求解clcclear 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 10

32、500;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,:)-

33、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

34、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

35、=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 endend w=a;for p=1:51 n=size(w,1); w1=w(p,:); for i=1:n l(i)=w1(i); z(i)=1; end s=; s(1)=1; u=s(1); k=1; while k<n for i=1:n for j=1:k if i=s(j) if l(i)>l(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u; end end end end ll=l; for

36、i=1:n for j=1:k if i=s(j) ll(i)=ll(i); else ll(i)=inf; end end end lv=inf; for i=1:n if ll(i)<lv lv=ll(i); v=i; end end s(k+1)=v; k=k+1; u=s(k); endif p=1 a=l; t=z;else a=a;l; t=t;z;endendfor i=1:51 a(i,i)=inf;%把相同的点赋值为无穷大endsave w.txt a -ascii; %保存最小距离save t.txt t -ascii; %保存最小路径经过的点2.2、问题一得求解cl

37、ear 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;

38、 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)2.3、问题二的2阶段求解clear allclcformat shortw=数据太多省略;p=1;x=1;sum=0;v=w;w(:,p)=inf;for i=1:

39、10 s,t=min(w(p,:); sum=sum+s; T=sum/1000/24+3*i/60; disp(t,T) w(:,t)=inf; p=t; x=x;t;enddisp('顺序为：')disp(x)disp('总的路程为：')disp(sum)T=sum/1000/24+3*30/60;disp('总的时间是：')disp(T)2.4问题二4阶段的解法clcclear allw=inf 5295.49 2182.03 4709.245295.49 inf 3113.46 5714.342182.03 3113.46 inf 388

40、3.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(:,t)=inf; p=t; x=x;t;enddisp('顺序为')disp(x')disp('×总路程是：')disp(sum)disp('总时间是)disp(T)disp('第二个区域')w=inf

41、1780.15 4104.9 5735.68 8234.281780.15 inf 2324.75 3955.53 6454.134104.9 2324.75 inf 1630.78 4847.795735.68 3955.53 1630.78 inf 3217.018234.28 6454.13 4847.79 3217.01 inf;p=1;x=1;v=w;w(:,p)=inf;T=0.6087;for i=1:4 s,t=min(w(p,:); sum=sum+s; T=T+3/60; T=s/1000/24+T; disp(t,T) if(i=1); T=T+3/60; end if(

42、i=4); T=T+3/60*2; end w(:,t)=inf; p=t; x=x;t;enddisp('顺序为')disp(x')disp('×总路程是：')disp(sum)disp('总时间是)disp(T)disp('第三个区域')w=inf 4719.88 2351.72 3269.39 4323.14719.88 inf 3536.11 2618.44 5507.492351.72 3536.11 inf 917.67 1971.383269.39 2618.44 917.67 inf 2889.05432

43、3.1 5507.49 1971.38 2889.05 inf;x=1 3 5 4 2;T=1.3317;for i=1:4 m=i; s=w(x(i),x(i+1); sum=sum+s; if(i=4) m=m+1; end T=s/1000/24+T; disp(x(i+1),T) T=T+3/60;enddisp('顺序为')disp(x')disp('×总路程是：')disp(sum)disp('总时间是)disp(T)disp('第四个区域')w=数据太多省略;p=1;x=1;v=w;w(:,p)=inf;w

44、(:,12)=inf;T=1.9413;for i=1:10 s,t=min(w(p,:); sum=sum+s; T=s/1000/24+T; disp(t,T) T=T+3/60; w(:,t)=inf; p=t; x=x;t; if i=2 T=T+3/60; end if i=4 T=T+3/60; end if i=7 T=T+3/60; end if i=8 T=T+3/60*2; end disp(p,sum)endsum=sum+v(t,12);disp('顺序是：')disp(x',1)disp('总距离是：')disp(sum)T=s

45、um/1000/24+3*30/60;disp('总时间是：')disp(T)2.5、问题3的初步设定clcclear allw=;i=1;while i<50 if (w(i,1)=w(i+1,1) w(i,2)=w(i,2)+w(i+1,2); w(i,3)=w(i,3)+w(i+1,3); w(i+1,:)=; i=i-1; end i=i+1;endsave x.txt w -ascii;clcclear allload w.txta=w;for i=1:51 a(i,i)=inf;endload x.txtw=x;p=1;x=0;M=0;V=0;sum=0;v=

46、a;a(:,p)=inf;disp('第一阶段')for i=1:50 s,t=min(a(p,:); M=M+w(t-1,2); V=V+w(t-1,3); sum=sum+s; p=t; if(M>50)|(V>1) break; end n=i; x=x;t-1; % disp(t-1,M,V) a(:,t)=inf;endsum=sum+v(p,1);disp('顺序为：')disp(x',0)disp('总路程是：')disp(sum)T=sum/1000/24+3*i/60;disp('所用时间是：')disp(T)disp('第二阶段')p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50 s,t=min(a(p,:); M=M+w(t-1,2); V=V+w(t-1,3); sum=sum+s; if(M>50)|(V>1) break; end n=n+1; p=t; x=x;t-1; % disp(t-1,M,V) a(:,t)=inf;enddisp(&