送货员最短路径模型优化

《送货员最短路径模型优化》由会员分享，可在线阅读，更多相关《送货员最短路径模型优化（19页珍藏版）》请在金锄头文库上搜索。

1、西安西安邮电邮电学院第五届学院第五届大学生数学建模大学生数学建模竞赛竞赛参参赛赛作作品品 参参赛赛队队编编号号 ： 5252 赛题类型代码：赛题类型代码： B B 1送货路线设计模型送货路线设计模型摘要摘要：为了解决最佳送货路线一系列问题，本文建立了求最短 Hamilton 圈问题。 利用 Floyd 算法【2】求出顶点间最短路，构造连接各顶点的一个无向赋权完备图 （矩阵） 。使用启发式算法（Heuristic Algorithm）【2】寻找该完备图最短的Hamilton 圈。 借助 Matlab 等数学工具，使用模拟退火算法（SA）求出最优解（问题一） 。 问题二中加入了时间限制，我们根据需

2、求到达时间的不同，对整个路线图进行 了片区的划分，然后对于不同的片区便转化为一个新的求最短 Hamilton 圈问题。 问题三没有时间限制，但是基于重量和体积的要求，我们比照第二问中所用方 法对总路线按照体积与重量的限制进行了划分片区，仍然按照最短 Hamilton 圈 问题进行求解。得到了令人较为满意的近似解。 由于我们考虑到各分段距离最短并不代表总和最短，所以我们对最短 Hamilton 圈问题进行了优化，最终整理为本文中的辅助途中的最短 Hamilton 圈 问题。利用辅助途中的最短 Hamilton 圈问题的求解方法，我们得到了最佳解。 总的来说，本模型不仅成功的解决了本次建模的最佳送

3、货路线模型问题， 而且可以成为类似于本最佳送货路线问题类似问题的一个有效而且具有较强实 用性的方法。关键字：关键字：Hamilton 圈 Floyd 算法 启发式算法（Heuristic Algorithm） 模拟退火算法（SA） 划分片区 2送货路线设计模型送货路线设计模型 一、一、 问题重述问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业 也渐渐兴盛，每个送货员往往一人送多个地方，他们怎么样才能以最快的速度 及时将货物送达是个十分重要的问题，本文将就送货路线设计问题展开分析和 讨论。 现有一快递公司，库房在图 1（图略）中的 O 点，一送货员需将货物送至城 市内多

4、处，需要设计适当的送货方案，使所用时间最少。该地形图的示意图见 图 1（图略） ，各点连通信息见表 3（表略） ，送货员只能沿这些连通线路行走， 而不能走其它任何路线。各件货物的相关信息见表 1（表略） ，50 个位置点的坐 标见表 2（表略） 。假定送货员最大载重 50 公斤，所带货物最大体积 1 立方米。送货员的平均 速度为 24 公里/小时。假定每件货物交接花费 3 分钟，为简化起见，同一地点 有多件货物也简单按照每件 3 分钟交接计算。 现在送货员要将 100 件货物送到 50 个地点。 问题问题 1：若将 130 号货物送到指定地点并返回。设计最快完成路线与方式。给 出结果。要求标出

5、送货线路。 问题问题 2：假定该送货员从早上 8 点上班开始送货，要将 130 号货物的送达时间 不能超过指定时间，请设计最快完成路线与方式。要求标出送货线路。 问题问题 3： 若不需要考虑所有货物送达时间限制(包括前 30 件货物)，现在要将 100 件货物全部送到指定地点并返回。设计最快完成路线与方式。要求标出送 货线路，给出送完所有快件的时间。由于受重量和体积限制，送货员可中途返 回取货。可不考虑中午休息时间。二、二、 模型假设和符号说明模型假设和符号说明2.1 模型假设模型假设1.假设送货员的行进速度与所送货物的重量无关，速度均为 24 公里/小时。2.送货员送货中途不休息，午休时间也

6、略去。3.送货员送货中途无任何意外发生中断送货。4.送货的每一条路、每个地点可以重复进过。5.假定每件货物交接花费 3 分钟，同一地点有多件货物也简单按照每件 3 分 钟交接计算。32.2 符号系统符号系统N(V,E,W),WtN(V,E,W),WtN(V,E,W)表示无向图 V 是节点集合,E 为边的集合,Wt 为边上的权.d(d(, ,) )ivjv相邻顶点,之间的距离ivjvM3030 个包裹的总重量M100100 个包裹的总重量V3030 个包裹的总体积V100100 个包裹的总体积第 i 个包裹的重量第 i 个包裹的体积vi0每个阶段的起点 i=1,2,3,4viz每个阶段的终点 i

7、=1,2,3,4t送包裹到指定地点所用时间t100送完 100 件货物所用时间T到达指定地点并交接包裹后的时刻MA VAA 区包裹的总质量、总体积MB VBB 区包裹的总质量、总体积MC VCC 区包裹的总质量、总体积dAA 区送货路线总长dBB 区送货路线总长dCC 区送货路线总长4三、问题分析三、问题分析3.1 问题问题 1 的分析：的分析：注意到 30 个包裹的总重量(M30=)不超过 50kg，且总体积(V30=)301i im301i iv不超过 1 ，则送货员可一次携带 30 个包裹送货到指定地点并返回。由假设3m送货员行进速度恒定，从而最佳运送方案等价于找出一个遍历所有目的顶点并

8、返回出发点的最短路线。从而可以将该问题转化为 TSP（旅行商）问题【1】iv（本题可以重复经过某顶点） ，即寻找一个最短的 Hamilton 圈【2】。 利用 Matlab 软件编程，先计算出相邻顶点（vi，vj）之间的 Euclid 距离()并赋为边的权值，利用 Floyd 算法【2】求出顶点间最短路22dabijedgeijwt径。构造连接各顶点的一个无向赋权完备图（矩阵） 。使用启发式算法 （Heuristic Algorithm）【2】寻找该完备图最短的 Hamilton 圈。3.2 问题问题 2 的分析的分析3.2.1 建模流程建模流程问题转化示意图问题转化示意图送货路线问题送货路线

9、问题 用最短的路径在规 定时间内送到指定 地点。3.2.2 问题分析问题分析 同问题 1 送货员可一次携带 30 个包裹送货到指定地点，但是不需要返回 出发点。又由于在时间上有了限制，等价于两个限制因素，用最短的路径在规 定时间内送到指定地点。 根据指定时间的先后，分四个阶段去送货（划分见附录 2） 。从而最佳运送 方案是找出每个区域的起点 vi0到终点 viz（距离下一个区域最近的点）的最短根据规定时间先后划 分线路为四个阶段 每个阶段可以看成一 个寻找一个最短的 Hamilton 链使用穷举法及递推 算法解决5路径，即在每个区域寻找一个最短的 Hamilton 链。 结合问题 1 的结果，

10、区域 1 和区域 2 的最短路径可以经过简单计算得出， 区域 3 可以利用 Matlab 软件编程，构造连接各顶点的一个无向赋权完备图（矩 阵） 。使用枚举法寻找每个区域完备图的最短的 Hamilton 链。3.3 问题问题 3 的分析的分析3.3.1 建模流程建模流程问题转化示意图问题转化示意图3.3.2 问题分析问题分析送货员将 100 个包裹最快送到 50 个指定地点，经过计算 100 个包裹的总质量；总体积，送货员每次携带货物质100100 1148ii iMmkg100 3 100 12.8ii iVvm量不能超过 50kg，体积不能超过 1m3，可将路线划分为 n（n=3,且 n

11、为整数） 个片区，相当于 n 个送货员同时从同一地点出发再返回出发点，考虑到送货员 需最快送货完毕，即需要最短送货路线，则每个区域的包裹质量和体积在不超 过限制时应尽可能最大，所以考虑选取 n=3。划分方案如下：（1）按照地理位置划分法将路线划分为 A、B、C 三个区域。 （2）由送货员负载包裹的重量限制和体积限制对三个区域进行优化。（3）区域的公共地点可以将一个地点的多份包裹进行两次或三次送 到，达到区域的优化。由假设送货员行进速度恒定，从而最佳运送方案等价于找出一个遍历每个区域所有目的顶点并返回出发点的最短路线。从而可以将该问题转化为iv6TSP（旅行商）问题（本题可以重复经过某顶点） ，

12、即寻找一个最短的 Hamilton 圈。四、模型建立与求解四、模型建立与求解4.1 模型准备模型准备先根据题中所给的距离表将各节点标在示意图中（附录 1）,其中节点代表 目标地点,边上的权表示路径的长度.设其为 N(V,E,W) Wt,V 是节点集合,E 为边 的集合,Wt 为边上的权. 其中边上的权 Wt 确定方法如下：计算出相邻顶点（vi，vj）之间的 Euclid 距离()，22dabijwt再将该图转化为一个无向赋权完备图（undirected weighted complete graph） 。转 换方法如下：利用 Floyd 算法求出任意两个顶点,之间的距离(最短路径长度)d(,i

13、vjviv)=得到矩阵无向赋权完备图 d=.jvijdijd（程序，结果见附录 4）4.2 问题问题 1 模型的建立与求解模型的建立与求解4.2.1 模型建立模型建立由问题 1 的分析知，本题可以转化为一个 TSP【1】（旅行商）问题（本题可 以重复经过某顶点） ，即寻找一个最短的 Hamilton 圈【2】 。 数据预处理部分已经得到了连接各顶点的一个无向赋权完备图（矩阵） 。由 于 TSP 问题是一个典型的 NP-hard 问题【1】。对于本问题的规模在有效建模时间 内利用穷举法（exhaustion method）是困难的。所以这里考虑使用模拟退火算法 （SA）【1】来寻找该完备图中的最

14、短 Hamilton 圈。4.2.2 模型求解模型求解借助数学工具 Matlab，使用模拟退火算法（SA）可以求出最优解如下： 路线：O262117141623323538363843424942454034312739273124191318O7图示：4.3 问题问题 2 模型的建立与求解模型的建立与求解4.3.1 模型的建立模型的建立由问题二的分析可知模型建立步骤如下： （1）根据时间先后划分为四个阶段（划分见附录 2） ； （2）确定每个阶段的起点和终点，显然第一阶段的起点为 O 点， 然后每一阶段的起点要求距离上一个阶段最近，终点要求距 离下一个阶段距离最近。 （3）阶段一二三结合问题

15、的结果可以分析计算出；阶段四较一二 三复杂，可借助数学工具 Matlab，使用递归法得出最优解 。（4）所用时间（t）的计算可以根据公式：所用时间=路程/速度+3货物数目（）3tdvm （5）到达时间（T）可以根据公式：到达时间=起始时间+该阶段各路段累计所用时间（）iTTt4.3.2 模型的求解模型的求解8（1）阶段一 要求 9:00 到达：共有三个指定地点：13,18,24，分析可得起点为 18，终点为 24。则可确 定路线即为 181324。此时我们只要计算出每一段的最短距离即可。根据 图示以及问题 1 所得数据，确定最优线路为 18131924。具体计算结 果如下表所示： 路线起点 O-1818-1313-24 路程（m）2182.02893113.46275704.3372 所用时间5 分 27 秒7 分 47 秒14 分 17 秒 到达时间8 点 5 分 27 秒8 点 16 分 14 秒8 点 36 分 31 秒 交货用时3 分3 分3 分 离开时间8 点 8 分 27 秒8 点 19 分 14 秒8 点 39 分 31 秒（2）阶段二 要求 9:30 到达 共有四个指定地点：31,34,40,45。分析可得起点为 31，终点为 45。从而 可以得到两种行程路线。31344045 或 31403445。分析比 较两种路线的行程总路程如下： 路