快递员配送路线优化模型(完整资料).doc0001

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

2、矩阵，然后使用二边逐次修正法对矩阵进行翻转，可以求得近 似最优解的距离矩阵，从而确定近似的最佳哈密尔顿圈，即最佳 配送方案。对于问题二，依旧可以将时间问题转化为距离问题。利用问 题一中所建立的模型，加入一个新的时间限制条件，即可求解出 满足条件的最佳路线。对于问题三，送货员因为快件载重和体积的限制，至少需要 三次才能将快件送达。所以需要对1()()件快件分区，即将5()个 配送点分成三组。利用距离矩阵寻找两两之间的最短距离是5() 个配送点中最大的三组最短距离的三个点，以此三点为基点按照 准则划分配送点。关键宇：Floyd算法 距离矩阵 哈密尔顿圈二边逐次修正法 矩 阵翻转问题重述某公司现有一

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

4、G：加权无向图 岭巴:定点c :哈密尔顿圈/(V):最佳哈密尔顿圈模型的建立一、基本假设1、假设送货员的始终以24千米/小时的速度送货，中途没有意 外情况；2、假设送货员按照路径示意图行走；3、假设仓库点为第51点；4、假设送货员回到仓库点再次取货时间不计。二、模型建立与求解 问题一：1、数据处理使用数据处理软件，处理附表2求出给定配送点之间的相互 距离。最终使用矩阵对处理数据进行数据统计整理。_ 131916_1 828642 207823511821825121179751261392矩阵前两列表示相互连接的配送点，第三列表示相邻两配送 点之间边的距离。使用上述数据矩阵可以构造路线示意图的

5、带权邻接矩阵，再 用Floyd算法求出各配送点之间的距离。2、Floyd算法基本思想直接在示意图的带权邻接矩阵中，通过插入定点的方法构 造出n个矩阵久必几最后得到的矩阵Q为距离矩阵,同时求 出插入点矩阵以便得到两点之间的最短路程。123495051107745191620306169891006827745058292557022001169263191658290 207051738810467049203062557020705 035691172150169892200117388 35690992851100681692610467 1172199280令G = （V,E）为一个加权无

6、向图，其中V表示各个顶点的集合, 卩=也'气，"2'；其中E表示各边的集合，E = eij，而勺=（片巴）。 图G中每一条边切都对应一个实数）,则称）为边的权。如果 任意两边相连，则G为完备图。设G = （V,E）是连通无向图，经过G的每个定点正好形成一个 圈，则称G为哈密尔顿圈，简称H圈。最佳哈密尔顿圈是在加权 图G = （V,E）中，权最小的哈密尔顿圈。判定一个加权图G = （V,E）是否存在哈密尔顿圈是一个NP问 题，而它的完备加权图G =（V,£）（E中每条边的权等于片y之间的 最短路径的权）中一定存在哈密尔顿圈。所以需要在完备加权图 G =（V,E

7、）中寻求最佳哈密尔顿圈。该过程需要采用二边逐次修正 法并且利用矩阵翻转实现。3、二边逐次修正法的选法过程、任取初始H圈：Co=“2,，岭.，片，"”，人（2）、对所有的 +若闪（片旳）+ 1卩（畑,耳+1）V w（y“+i） + w（弓旳+）,则在Co中删去边vv（v,.,v；）和 叽,畑）而加入边也,vI+1）和，畑）,形成新的H圈C ,即C = V *2,岭.川厂，匕，片（3）、对C重复步骤，直到条件不满足为止，最终得到的c即为 所求。4、矩阵翻转在一个矩阵中，对他的第i行（列）到第j行（列）翻转是 以i行（列）和j行（列）的中心位置为转轴、旋转1&）度，这 样：第i行（

8、列）和第j行（列）位置互换，第计1行（列）和 第口行（列）位置互换。图一由附录给定的快件信息可知，13（）号快件总重量为48,5kg. 体积为显然送货员可以一次性携带所有货物到达配送点, 经统计配送点共有21个,即卩（13、14、16、17、18、21、23、24、 26、27、31、32、34、36、38、4（）、42、43、45、49）首先在程序里设置限制：'34）E 叫-50/-0<30.f-o将出发点51点与21个送货点结合起来构造完备加权图，由 完备加权图确定初始H圈，列出该初始H圈加点序的距离矩阵, 然后使用二边逐次修正法对矩阵进行翻转，可以求得近似最优解 的距离矩阵

9、，从而确定近似的最佳哈密尔顿圈。由于使用矩阵翻转方法来实现二边逐次修正法的结果与初 始圈有关，为得到更优解，在使用软件编程时，随机搜索出若干 个初始H圈，例如2000o在所有的H圈中筛选权值最小的一个, 即就是最佳H圈。最佳H圈的近似解为：2(X)0工/化)r-1min/(V)在c°中删去边vv(v.,V;)和vv(vr+1，罕J而加入边w,艰)和叽乌,专+1),形 成新的H圈C。最终由编程得到近似最佳配送路线以及总长度。最佳配送路线：51t26t21t17t14t16t23t32t35t38t36t38t43t42t4 9t42t45t4()t34t31t27t39t27t31t2

10、4t19t13t18t51解得路线总长为54709m,耗时226.77mino问题二：因货物可在一次性配送，故可以不用考虑送货员的最大载重 与体积问题。但是较于问题一在选择路线上，需要考虑送货时间 问题，不得超过指定时间。所以在问题一的程序中需要再增加时 间限制。30S 叫-50<3()7； #(2 0,1,2,30)51->18t13t19t24t31t34t4()t45t42t49t42t43t38t35t 32t23t16t14t17t21t36t27t39t27t31t26t51解得路线总长为54996m,耗时227.50min问题三：由附录给定的快件信息知，11()()号

11、快件总重量为148kg、 体积为2.8m由于考虑送货员的最大载重与体积，送货员必须 分多次配送快件。送货员显然至少需要连续三次配送，才能完成 配送任务。因此问题三存在配送点分组、以及每组求最佳配送方案这两 个问题。首先需要制定一种比较合理的划分准则，使三组总长加 起来最短。需要选择三个点作为毎一组的基点，要求这三个点两 两之间的最短距离是5()个配送点中最大的三组最短距离。利用 距离矩阵查找其他任意点与三个基点之间的距离，距离哪一个基 点近，就被划分在哪一组。通过计算三个基点为：9号、28号、43号配送点。通过距离 矩阵将1()()件快件的配送点分组如下：配送方案重呈(kg)体积(m3 )一1

12、2345678910141617182123323519. 90.9112-111213151920222526282930334144464848. 380. 985三242731313637383940434547495019. 720. 9038求和1482.8表一使用问题一与问题二中相同的方法：首先将出发点与其他组 内点结合起来构造完备加权图，由完备加权图确定初始H圈， 列出该初始H圈加点序的距离矩阵，然后使用二边逐次修正法 对矩阵进行翻转，可以求得近似最优解的距离矩阵，从而确定近 似的最佳哈密尔顿圈。图四最终由程序解得三组最佳配送路线为： 第一组：51t18t7t1t8t3t4t2t

13、5t4t3t1t6t1t7t1()t9t14t16t23t32t35t32t23t17t21t51解得路线总长52743m,耗时227.4min 第二组：51t26t31t24t19t25t41t44t48t46t33t28t3()t22t2 9t22t2()t22t15t12t11t13t18t51解得路线总长47736m,耗时221.4mino第三组：51t26t31t27t39t27t36t38t43t42t49t5()t45t4()t47t4()t37t4()t34t31t26t51解得路线总长42421m,耗时208.2min模型的优缺点点评对于问题一所建立的模型，通过Floyd算法和二边逐次修正