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

1、装订线第九届西安电子科技学数学建模竞赛暨全国大学生数学建模赛选拔赛题目A 年 5 4 日 年 5 4 日 学院员 员 3送货路线设计问题1、 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛个送货员需要以最快的速度及时将货物送达且他们往往一人 送多个地方，请设计方案使其耗时最少。现有一快递公司图 1 中的 O 点员需将货物送至城市内多处， 请设计送货方案，使所用时间最少。该地形图的示意图见 1，各点连通信息见 表 3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线。各件货物 的相关信息见表 1，50 个位置点的坐标见表 。假定送货员最大载重 斤，所带货物最

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

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

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

5、点 到其它各结点的最短路径入这样 两个集合 s 和 t，s 是那些已经确定了到 i 结点的最短路径的结点，t 为全集 u 和 s 的差集，即那些还未确定最短路径的结点。而且 的初值是i 的初值 是 u-i外再引入一个标记数组 dn中在某一步 dk表示当前从 到 k 的较短路径，dk的初值为 w（i，k整个算法过程如下：在 t 中选择一个 最小的结点 k， k 并入 s，并 t 中去掉，如果 t 为则转到；用 k 结点和 t 中其余结点进行一遍比较，如 didk+mki，则 用 dk+mki取代原来的 di，重复；算法结束，此时 中保存的就是从 i 到 k 结点的最短路径。算法就以这样非常简单的

6、形式完成了求解，时间复杂度 O(n2)确定了从 i 到其余各结点的最短路径。模型的解根据算法和相邻的点的距离可以用 求出任意两点的最短路径。 使用循环的结构求出 各个点之间的最短距离。程序 1 见附录可以求出 w 和 aa 为最短路径是的所过的的地点如从 O 开始到其余 个点的 a(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 点则

7、要先到 23 即 0-23-16 要从 O 点到 23 点则要先到 17 即 0-17-23-16 要从 o 点到 17 点则要先到 21 即 O 可以直接到 21 所以从 0 到 16 的最优路径是 0-21-17-23-16 短的距离是 w（0,16）=7493m模型二模型的立由前 30 件货物可以到达的地点可以知道 i，j= 、14、16、17、21、 23、24、26、27、31、32、34、36、38、39、42、43、45、49。 到点其中共经过 21 个点，运送 30 件货物该 30 件货物 =50kg = ,所以可以一次把货物携带进行运送。由 T 与 W 关系可知要使所用的时间

8、最小即所走的距离最短。即：T=WV+必须部遍历回到 点即求出从 O 出发遍历这图的 个点的并回到 o 的最短的距离要距离最短则每一步也要最短 开始找最短的点到达后继续找未遍历的最 短的点则可求出最短的距离。本题要求出回 O 则可以看到两个开始最短遍历的点在某点重合即可完成 最短的遍历。模型的解由图可以明显得出距离 O 最近的点是 21 点和 26 点于 32 点到 点的距 离小 点 点的距离为使 点出来的线遍历右下的点完后再 点出 来的汇合则安排 32 点到 35 点断开。有程序 2（附录）可得：0 1 31 1213 2 32 1314 3 34 1416 4 36 1517 5 38 16

9、18 6 39 1721 7 40 1823 8 42 1924 9 43 2026 10 45 2127 11 49 22遍历节点路线是：0-2-4-40-45-49-42-43-38-36-39-27-31-26-0最优的路线是： 0-2-3-0-45-42-49-42-43-38-36-27-39-27-31-26-0 总路程是：W=53787m 最优时间是：T=模型的立由第一个模型建立的可以求出到 24 时所用的时间是:可知到 24 点的时间是：t(24)=由表可知必须在 之前把货物送到 24 即 模型一不适用于问题二 的求解.由下图 3 可知： 点由于右边的点的地点需要的时间要比左边

10、的早以先分两个阶段先走左边 后走右边即先走圈内的元素由程序 3（附录）可得： 45 点 9 = T 到个点的间最大 模型的求解段对四个阶段分别求出到达的时间，由程序 4附录）可知 分 4 个阶段1. 从 0 出发经过 、18 到 24。 满足 t1 的条件故路线为：3241813242. 从 24 出发经过 、34、40 到 45。 满足 t故路线为：24-31-34-40-453. 从 45 出发经过 、42、43 到 49。 满足 t所以路线为：45-42-49-43-382 313 344 405 454. 从 38 出发经过 、16、17、21、23、26、27、32、36、39 到

11、O。 10 368 2711 397 265 214 176 239 32 3 423 16 5 492 14 4 43满足 t4 2 38故路线为：38-36-27-39-27-3-32-16-14-21-0所以总的遍历点顺序是：0-4-40-45-42-49-43-38-36-27-39-26-2-14-0总时间是 T=总距离是 W=57912m最优路线是：0-49-42-43-38-36-27-39-27-3-32-23-16-14-21-0到每个点的时间见附录模型建立本题中要遍历所有的 个点但由于=147kg 而M50kg,V1 M50kg 和 V50)|(V1);% 顺 ) 总 ) 所： ) 第 ) (M50)|(V1);% 顺 ) 总 ) 所： ) 第 ) (M50)|(V1)