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

送货路线设计问题1、问题重述

现今社会⽹络越来越普及,⽹购已成为⼀种常见的消费⽅式,随之物流⾏业也渐渐兴盛,每个送货员需要以最快的速度及时将货物送达,⽽且她们往往⼀⼈送多个地⽅,请设计⽅案使其耗时最少。

现有⼀快递公司,库房在图1中的O点,⼀送货员需将货物送⾄城市内多处,请设计送货⽅案,使所⽤时间最少。该地形图的⽰意图见图1,各点连通信息见表3,假定送货员只能沿这些连通线路⾏⾛,⽽不能⾛其它任何路线。各件货物的相关信息见表1,50个位置点的坐标见表2。

假定送货员最⼤载重50公⽄,所带货物最⼤体积1⽴⽅⽶。送货员的平均速度为24公⾥/⼩时。假定每件货物交接花费3分钟,为简化起见,同⼀地点有多件货物也简单按照每件3分钟交接计算。现在送货员要将100件货物送到50个地点。请完成以下问题。

1、若将1~30号货物送到指定地点并返回。设计最快完成路线与⽅式。给出结果。要求标出送货线路。

2、假定该送货员从早上8点上班开始送货,要将1~30号货物的送达时间不能超过指定时间,请设计最快完成路线与⽅式。要求标出送货线路。

3、若不需要考虑所有货物送达时间限制(包括前30件货物),现在要将100件货物全部送到指定地点并返回。设计最快完成路线与⽅式。要求标出送货线路,给出送完所有快件的时间。由于受重量与体积限制,送货员可中途返回取货。可不考虑中午休息时间。2、问题分析

送货路线问题可以理解为:已知起点与终点的图的遍历问题的合理优化的路线设计。

图的遍历问题的指标:路程与到达的时间,货物的质量与体积,以及最⼤可以负载的质量与体积。在路线的安排问题中,考虑所⾛的路程的最短即为最合理的优化指标。

对于问题⼆要考虑到所到的点的时间的要求就是否满⾜题意即采⽤多次分区域的假设模型从⽽找出最优的解

对于问题三则要考虑到体积与质量的双重影响,每次到达后找到达到最⼤的体积与质量的点然后返回,再依次分析各个步骤中可能存在的不合理因素达到模型的进⼀步合理优化得到最合理的解。3、模型假设与符号说明3、1、模型的假设

(1)、到同⼀地点的货物要⼀次拿上,即不考虑再以后⼜经过时再带些货物(2)、要求达到不超过的时间不包括此次在该点交易的时间。(3)、所⽤的距离数据都精确到⽶⽽时间则精确到0、0001h(4)、同⼀地点有多件货物也简单按照每件3分钟交接计算。3、2、符号说明

其中i,j=1、2、3 (50)并且M=50kgV=1

4、 模型的建⽴及求解模型⼀

1、1模型的建⽴

我们为了求出各个点的之间的最短的路径,使⽤Dijstra 算法求解。Dijkstra 算法就是图论中⾮常有名的⼀个算法。

图采⽤邻接矩阵的形式描述,w(i,j)表⽰结点i 到结点j 间的最短距离,如果没有直接连通,则为⽆穷⼤,计算机中可以⽤⼀个很⼤的数据代替(如matlab 中的inf)。

但dijkstra 算法只能求出从结点i 到其它各结点的最短路径。算法引⼊这样两个集合s 与t,s 就是那些已经确定了到i 结点的最短路径的结点,t 为全集u 与s 的差集,即那些还未确定最短路径的结点。⽽且s 的初值就是{i},t 的初值就是u-{i}。另外再引⼊⼀个标记数组d[n],其中在某⼀步d[k]表⽰当前从i 到k 的较短路径,d[k]的初值为w(i,k)。 整个算法过程如下:１、 在t 中选择⼀个d[k]最⼩的结点k,将k 并⼊s,并从t 中去掉,如果t 为｛｝则转到３;模型⼀ 模型⼆ 模型三 模型四最短路

径模型 任意两点之间的最短路距离 图的遍历模型

由起始点遍历路径回到原点

多区域最短路 多区域⽆返回起点的最短路多阶段最短路

多阶段有返回起点的最短路

２、⽤k结点与t中其余结点进⾏⼀遍⽐较,如果d[i]>d[k]+m[k][i],则⽤d[k]+m[k][i]取代原来的d[i],重复１;３、算法结束,此时d[k]中保存的就就是从i到k结点的最短路径。

算法就以这样⾮常简单的形式完成了求解,时间复杂度就是O(n^2),确定了从

i到其余各结点的最短路径。1、2模型的求解

根据算法与相邻的点的距离可以⽤dijkstra求出任意两点的最短路径。图1相邻的点的距离

使⽤循环的结构求出1-50各个点之间的最短距离。程序1见附录2、1可以求出w与a

a为最短路径就是的所过的的地点

如从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 2328 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需要达到的点(红点标注的)其中共经过21个点,运送30件货物

该30件货物=47、3kg<50kg =0、8371,所以可以⼀次把货物携带进⾏运送。由T与W关系可知要使所⽤的时间最⼩即所⾛的距离最短。即⽬标函数就是:T=W÷V+×30

约束条件就是:必须全部遍历回到0点

即求出从O出发遍历这图的21个点的并回到o的最短的距离

要距离最短则每⼀步也要最短,即从O开始找最短的点到达后继续找未遍历的最短的点则可求出最短的距离。本题要求出回到O点则可以瞧到两个开始最短遍历的点在某点重合即可完成最短的遍历。2、2模型的求解

由图可以明显得出距离O最近的点就是21点与26点。由于32点到38点的

距离⼩于32点到16点的距离为使从21点出来的线遍历右下的点完后再与26点出来的汇合则安排32点到35点断开。0 1 31 1213 2 32 1314 3 34 1416 4 36 1517 5 38 1618 6 39 1721 7 40 1823 8 42 1924 9 43 2026 10 45 2127 11 49 22

遍历节点路线就是:

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-2 7-39-27-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)可得:

、34、39、40到达455 26 0、10807 31 0、22206 27 0、31659 29 0、44074 24 0、68353 28 0、89542 13 1、07518 31 1、439310 40 1、557311 45 1、7413

⽽到13点时必须在9点之前到达但1、0751>1,到45点时必须在9点半之前到达⽽1、7412>1、5故分成两个阶段不成功,所以分四个阶段,求出各个阶段的最短距离与到达时的时间即可。⽬标函数:=÷v+

约束条件就是:T到个点的时间最⼤值3、2模型的求解图4、4个阶段的圈图

对四个阶段分别求出到达的时间,由程序4(附录2、4)可知分4个阶段

1.从0出发经过13、18到24。满⾜t<1的条件故路线为:0-18-13-24

2.从24出发经过31、34、40到45。满⾜t<1、5

故路线为:24-31-34-40-45

3.从45出发经过38、42、43到49。满⾜t<2、253 18 0、09092 13 0、27064 24 0、55872 31 0、73293 34 0、92974 40 1、04775 45 1、23173 42 1、42975 49 1、56184 43 1、73222 38 1、8913 ①②③④

所以路线为:45-42-49-43-38

4.21、23、26、27、32、36、39回到O。10 36 2、00548 27 2、147211 39 2、32147 26 2、55405 21 2、74544 17 2、87146 23 2、99539 32 3、1500

3 16 3、44202 14 3、6007

故路线为: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模型四

—对于问题三的求解4、1.模型的建⽴

本题中要遍历所有的50个点但由于=147kg, =2、8⽽

M<50kg,V<1故应该以M<50kg与V<1判断的标准到达的最远的点后返回。⽬标函数:W=

约束条件:M<50kg,V<14、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-36-38-35-32-23-17-21-0⾛的距离W=27122m,花费的时间T=1、7301

2、若按程序给出的从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、4675

3、当到达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、1238

4、只余下了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-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-2 8-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、模型的分析①误差分析:

对于模型⼀就是使⽤了精确地Dijkstra算法,故误差可以忽略不计

对于模型⼆假定了32到38点的断开存在⼀定的误差,但相对于断开其余的⼏点得到的数值要⼩,故该模型可以使⽤。

对于模型三,由于分区域的⽅法有很多,故不可避免的存在些许误差,但由于区域越多,路程越多,故选择分成4个区域最合适;分成的四个不同的时间的到达区域⽐较紧密故按照时间的不同划分了四个区域,从⽽⼤⼤的消除了误差,此模型可以使⽤。

对于模型四的误差⽐较⼤,由于未考虑货物的拆分可能会有⼀定的影响同时由于4个阶段的划分也就是有⼀定的不确定性故误差存在。对于该模型简化了考虑的条件,仅以M与V为判断标准,虽对准确性存在挑战,但该模型相对与其她的分类有明显的优越性。故该模型适⽤于该问的求解。