数学建模 送货线路设计问题 标准答案 答案仅供参考.docx

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

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

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

4、物（2）、要求达到不超过的时间不包括此次在该点交易的时间。（3）、所用的距离数据都精确到米而时间则精确到0.0001h（4）、同一地点有多件货物也简单按照每件3分钟交接计算。3.2、符号说明其中i，j=1、2、350 并且 M=50kg V=14、模型的建立及求解模型一1.1模型的建立我们为了求出各个点的之间的最短的路径，使用Dijstra算法求解。 Dijkstra算法是图论中非常有名的一个算法。图采用邻接矩阵的形式描述，w（i,j）表示结点i到结点j间的最短距离，如果没有直接连通，则为无穷大，计算机中可以用一个很大的数据代替（如matlab中的inf）。但dijkstra算法只能求出从结点

5、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中其余结点进行一遍比较，如果didk+mki，则用dk+mki取代原来的di，重复；、 算法结束，此时dk中保存的就是从i到k结点的最短路径。算法就以这样非常简单的形式完成了求解，时间复杂度是O(n2)，

6、确定了从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 28 31 38 21 40 36 27 34 37 43 38 41 36 41 40 46 42 40要从O点到16点则要先到23即

7、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需要达到的点（红点标注的）其中共经过21个点，运送30件货物该30件货物=47.3kg50kg =0.8371,所以可以一次把货物携带进行运送。由T与W关

8、系可知要使所用的时间最小即所走的距离最短。即目标函数是：T=WV+30 约束条件是：必须全部遍历回到0点即求出从O出发遍历这图的21个点的并回到o的最短的距离要距离最短则每一步也要最短，即从O开始找最短的点到达后继续找未遍历的最短的点则可求出最短的距离。本题要求出回到O点则可以看到两个开始最短遍历的点在某点重合即可完成最短的遍历。2.2模型的求解 由图可以明显得出距离O最近的点是21点和26点。由于32点到38点的距离小于32点到16点的距离为使从21点出来的线遍历右下的点完后再和26点出来的汇合则安排32点到35点断开。有程序2（附录2.2）可得：0131121323213143341416

9、43615175381618639172174018238421924943202610452127114922遍历节点路线是：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=53787m 最优时间是：T=3.7411h模型三 对于问题二的求解3.1模型的建立 由第一个模型建立的可以求出到达24时所用的时间是:可知到2

10、4点的时间是：t(24)=2.0880由表2.1可知必须在9点之前把货物送到24点即t(24)1，到45点时必须在9点半之前到达而1.74121.5故分成两个阶段不成功，所以分四个阶段，求出各个阶段的最短距离和到达时的时间即可。目标函数：=v+约束条件是：T到个点的时间最大值3.2模型的求解图4.4个阶段的圈图对四个阶段分别求出到达的时间，由程序4（附录2.4）可知分4个阶段3180.09092130.27064240.55871.从0出发经过13、18到24。满足t1的条件故路线为：0-18-13-242310.73293340.92974401.04775451.23172.从24出发经过

11、31、34、40到45。 满足t1.5故路线为：24-31-34-40-453421.42975491.56184431.73222381.89133.从45出发经过38、42、43到49。满足t2.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.99539323.15003163.44202143.6007满足t4故路线为：38-36-27-39-27-31-26-21-17-23-32-16

12、-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模型四 对于问题三的求解4.1模型的建立本题中要遍历所有的50个点但由于=147kg， =2.8而M50kg,V1故应该以M50kg和V1判断的标准到达的最远的点后返回。目标

13、函数：W=约束条件：M50kg,V14.2模型的求解由O开始逐渐依次找出最近的点后再找出离该点最近的点直到不满足约束条件。见程序5（附录2.5）图5.改进后的遍历图1第一阶段2. 第二阶段3. 第三阶段 4.第四阶段4.3模型的优化由于总的=148kg =2.8 所以最少要分四个阶段，但由于每次不可能刚好带满50kg而如果只要3次则最多只能带150kg只比原货物多2kg所以不可能是三次就把货物带完，最少要四次。故只需要把上述的模型进行数据处理就好了。过程如下： 1.由于到21点时M=49 V=0.8757若走过14则M大于了50故直接从21点返回。最优路线为： 0-26-31-27-39-27

14、-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返回。最优路线为: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点放货物的话则需

15、要遍历许多已经遍历过的地点，故从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-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-1

16、1-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-13-18-o总路程是：W= 171510m所用的时间是T=7.39645、模型的分析1误差分析：对于模型一是使用了精确地Dijkstra算法，故误差可以忽略不计对于模型二假定了32到38点的断开存在一定的误差，但相对于断开其余的几点得到的数值要小，故该模型可

17、以使用。 对于模型三，由于分区域的方法有很多，故不可避免的存在些许误差，但由于区域越多，路程越多，故选择分成4个区域最合适；分成的四个不同的时间的到达区域比较紧密故按照时间的不同划分了四个区域，从而大大的消除了误差，此模型可以使用。对于模型四的误差比较大，由于未考虑货物的拆分可能会有一定的影响同时由于4个阶段的划分也是有一定的不确定性故误差存在。对于该模型简化了考虑的条件，仅以M和V为判断标准，虽对准确性存在挑战，但该模型相对与其他的分类有明显的优越性。故该模型适用于该问的求解。2灵敏度分析 对于模型一、二、三，灵敏度很好，模型的准确性很高。 对于模型四由于质量和体积的制约，使其灵敏度不会很好

18、，但准确性较高，因此模型可以使用。6、模型评价、改进和推广6.1模型的评价优点：充分利用了已知数据建立模型，使其具有很高的准确性和可行性使用了准确的算法和适当的假设，使模型的准确性和实用性到达统一运用功能强大的Matlab工具使数据处理误差达到最小缺点由于数据较多，没法使用工具进行模型的验证，只能一步一步的精化模型6.2模型的改进对于模型一和三主要是进行验证。 对于模型二断开的那个点可以去取别的点进行。主要是模型四的改进，可以考虑到不同的地点送的货物进行拆分，从而渠道最优的解6.3模型的推广 可充分使用到图的遍历和最短路的一系列问题的求解中。 7、参考文献1.A First Course in

19、 Mathenmatical Moderling (Third Edition) Frank R.Giordiano Maurice D.weir William P.Fox2.图论 任韩。3.数学建模案例选集 姜启源 谢金星4.图论 第3版 德 迪斯特尔著5.大学生数学建模竞赛辅导教材 叶其效6.基于matlab 动态规划中最短路线的实现程序 J电脑学习 施益昌 郑贤斌 李自立7.物流配送问题的混沌优化算法研究 中央民族大学学报(自然科学版) 2009年11月第18卷第4期8. Dijkstra 算法在企业物流运输网络中的应用 湖南农业大学学报(自然科学版) 2005年8月第29卷4期附录附

20、录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.8

21、50.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

22、.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

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

24、5450.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.3

25、00.017297154.430.053698120.240.005699101.380.017510071.980.04931.2 50个位置点的坐标位置点X坐标(米)Y坐标(米)191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376305200141340553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010900347280