2022年2022年快递员配送路线优化模型 .pdf

《2022年2022年快递员配送路线优化模型 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年快递员配送路线优化模型 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、快递员配送路线优化模型摘要如今，随着网上购物的流行，快递物流行业在面临机遇的同时也需要不断迎接新的挑战。如何能够提高物流公司的配送效率并降低配送过程中的成本，已成为急需我们解决的一个问题。下面，本文将针对某公司的一名配送员在配送货物过程中遇到的三个问题进行讨论及解答。对于问题一，由于快递员的平均速度及在各配送点停留的时间已知，故可将最短时间转换为最短路程。在此首先通过Floyd 求最短路的算法，利用Matlab程序将仓库点和所有配送点间两两的最短距离求解出来，将出发点与配送点结合起来构造完备加权图，由完备加权图确定初始H圈，列出该初始 H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转

2、，可以求得近似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈，即最佳配送方案。对于问题二，依旧可以将时间问题转化为距离问题。利用问题一中所建立的模型，加入一个新的时间限制条件，即可求解出满足条件的最佳路线。对于问题三，送货员因为快件载重和体积的限制，至少需要三次才能将快件送达。所以需要对100 件快件分区，即将50 个配送点分成三组。利用距离矩阵寻找两两之间的最短距离是50 个配送点中最大的三组最短距离的三个点，以此三点为基点按照准则划分配送点。关键字：Floyd 算法 距离矩阵哈密尔顿圈二边逐次修正法矩阵翻转名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -问题重述某公

3、司现有一配送员，从配送仓库出发，要将100件快件送到其负责的50个配送点。现在各配送点及仓库坐标已知，货物信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。问题一：配送员将前30 号快件送到并返回，设计最佳的配送方案，使得路程最短。问题二：该派送员从上午8：00 开始配送，要求前 30 号快件在指定时间前送到，设计最佳的配送方案。问题三：不考虑所有快件送达的时间限制，现将 100 件快件全部送到并返回。设计最佳的配送方案。配送员受快件重量和体积的限制，需中途返回取快件，不考虑休息时间。符号说明nD：n 个矩阵V：各个顶点的集合E：各边的集合ije：每一条边ew:边的权G：加权无

4、向图,ijv v：定点C：哈密尔顿圈()if V：最佳哈密尔顿圈名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -模型的建立一、基本假设1、假设送货员的始终以24 千米/小时的速度送货，中途没有意外情况；2、假设送货员按照路径示意图行走；3、假设仓库点为第51 点；4、假设送货员回到仓库点再次取货时间不计。二、模型建立与求解问题一：1、数据处理使用数据处理软件，处理附表2 求出给定配送点之间的相互距离。最终使用矩阵对处理数据进行数据统计整理。1319161828642207823511821825121179751261392矩阵前两列表示相互连接的配送点，第三列表示相邻

5、两配送点之间边的距离。使用上述数据矩阵可以构造路线示意图的带权邻接矩阵，再用 Floyd 算法求出各配送点之间的距离。2、Floyd 算法基本思想直接在示意图的带权邻接矩阵中，通过插入定点的方法构造出n 个矩阵12,nD DD,最后得到的矩阵nD 为距离矩阵，同时求出插入点矩阵以便得到两点之间的最短路程。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -123495051107745191620306169891006827745058292557022001 1692631916582902070517388 104670492030625570207050356911

6、72150169892200117388356909928511006816926104671172199280令(,)GV E为 一 个 加 权 无 向 图，其 中V表 示 各 个 顶 点 的 集 合，012,nVv v vv；其中E表示各边的集合，ijEe，而(,)ijijev v。图G中每一条边ije 都对应一个实数ew，则称ew为边的权。如果任意两边相连，则G为完备图。设(,)GV E是连通无向图，经过G的每个定点正好形成一个圈，则称G为哈密尔顿圈，简称H圈。最佳哈密尔顿圈是在加权图(,)GV E中，权最小的哈密尔顿圈。判定一个加权图(,)GV E是否存在哈密尔顿圈是一个NP问题，而它

7、的完备加权图(,)GV E(E中每条边的权等于,ijv v 之间的最短路径的权)中一定存在哈密尔顿圈。所以需要在完备加权图(,)GV E 中寻求最佳哈密尔顿圈。该过程需要采用二边逐次修正法并且利用矩阵翻转实现。3、二边逐次修正法的选法过程(1)、任取初始 H圈：012,1=,ijnCv vvvv v(2)、对所有的,11i jijn，若1111(,)(,)(,)(,)ijijiijjw v vwvvwv vwv v，则在0C 中删去边(,)ijw v v和11(,)ijw vv而加入边1(,)iiw v v和1(,)jjw v v，形成新的H圈C，即12,1,ijnCv vvvv v(3)、对

8、 C重复步骤(2)，直到条件不满足为止，最终得到的C即为所求。4、矩阵翻转在一个矩阵中，对他的第i 行（列）到第 j 行（列）翻转是以 i 行（列）和名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -j 行（列）的中心位置为转轴、旋转180 度，这样：第 i 行（列）和第 j 行（列）位置互换，第 i+1 行（列）和第 j-1 行（列）位置互换。图一由附录给定的快件信息可知，130 号快件总重量为 48.5kg、体积为 0.88m3,显然送货员可以一次性携带所有货物到达配送点，经统计配送点共有21 个，即(V13、14、16、17、18、21、23、24、26、27、31

9、、32、34、36、38、40、42、43、45、49)首先在程序里设置限制：300300501iiiiwv将出发点 51 点与 21 个送货点结合起来构造完备加权图，由完备加权图确定初始 H圈，列出该初始 H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈。由于使用矩阵翻转方法来实现二边逐次修正法的结果与初始圈有关，为得到更优解，在使用软件编程时，随机搜索出若干个初始H圈，例如 2000。在所有的 H圈中筛选权值最小的一个，即就是最佳H圈。最佳 H圈的近似解为：20001()iif Vmin()if V名师资料总结-精品资料

10、欢迎下载-名师精心整理-第 5 页，共 8 页 -在0C 中删去边(,)ijw v v和11(,)ijw vv而加入边1(,)iiw v v和1(,)jjw v v，形成新的 H圈C。最终由编程得到近似最佳配送路线以及总长度。图二最佳配送路线：5126211714162332353836384342494245403431273927312419131851 解得路线总长为 54709m，耗时 226.77min。问题二：因货物可在一次性配送，故可以不用考虑送货员的最大载重与体积问题。但是较于问题一在选择路线上，需要考虑送货时间问题，不得超过指定时间。所以在问题一的程序中需要再增加时间限制。3

11、00300501(0,1,2,30)iiiiiiwvTt i结合问题一，使用相同方法求解最佳H圈。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -图三最佳配送路线：51181319243134404542494243383532231614172136273927312651 解得路线总长为 54996m，耗时 227.50min 问题三：由附录给定的快件信息知，1100 号快件总重量为 148kg、体积为 2.8m3。由于考虑送货员的最大载重与体积，送货员必须分多次配送快件。送货员显然至少需要连续三次配送，才能完成配送任务。因此问题三存在配送点分组、以及每组求最佳配送

12、方案这两个问题。首先需要制定一种比较合理的划分准则，使三组总长加起来最短。需要选择三个点作为每一组的基点，要求这三个点两两之间的最短距离是50 个配送点中最大的三组最短距离。利用距离矩阵查找其他任意点与三个基点之间的距离，距离哪一个基点近，就被划分在哪一组。通过计算三个基点为：9 号、28 号、43 号配送点。通过距离矩阵将100件快件的配送点分组如下：表一使用问题一与问题二中相同的方法：首先将出发点与其他组内点结合起来构造完备加权图，由完备加权图确定初始H圈，列出该初始 H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵，从配送方案重量(kg)体积(m3

13、)一123456789 101416 1718 21 23323549.90.9112二11 121315 19 20 222526 282930 3341 44 464848.380.985 三 24 273134 36 37 383940 434547 495049.720.9038求和1482.8名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -而确定近似的最佳哈密尔顿圈。图四最终由程序解得三组最佳配送路线为：第一组：5118718342543161710914162332353223172151 解得路线总长 52743m，耗时 227.4min 第二组：5126

14、31241925414448463328302229222022151211131851 解得路线总长 47736m，耗时 221.4min。第三组：51263127392736384342495045404740374034312651 解得路线总长 42421m，耗时 208.2min 模型的优缺点点评对于问题一所建立的模型，通过 Floyd 算法和二边逐次修正法找到最优哈密尔顿圈，可以得到准确的最优路线，在不考虑时间及负重限制的情况下，该模型可以精确地计算出唯一的最优路线。而对于问题二与问题三，其最优路线的求解均是建立在近似最优哈密尔顿圈的基础之上的。由于无法得到准确的最优哈密尔顿圈，故模型得到的最优路线与真实的最优路线还存在着一定的差距，只能通过增加计算次数不断地逼近真实最优路线。但在允许的误差范围内，模型已经可以很好地模拟出最优的配送路线了。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -