快递员配送线路优化模型

快递员配送线路优化模型摘要现在，随着网上购物的流行，快递物流行业在面临机缘的同时也需要不断迎接新的挑战。如何能够提高物流公司的配送效率并降低配送进程中的本钱，已成为急需咱们解决的一个问题。下面，本文将针对某公司的一名配送员在配送货物进程中碰到的三个问题进行讨论及解答。关于问题一，由于快递员的平均速度及在各配送点停留的时刻已知，故可将最短时刻转换为最短路程。在此第一通过Floyd求最短路的算法，利用Matlab程序将仓库点和所有配送点间两两的最短距离求解出来，将起点与配送点结合起来构造完备加权图，由完备加权图确信初始H圈，列出该初始H圈加点序的距离矩阵，然后利用二边逐次修正法对矩阵进行翻转，能够求得近似最优解的距离矩阵，从而确信近似的最正确哈密尔顿圈，即最正确配送方案。关于问题二，依旧能够将时刻问题转化为距离问题。利用问题一中所成立的模型，加入一个新的时刻限制条件，即可求解出知足条件的最正确线路。关于问题三，送货员因为快件载重和体积的限制，至少需要三次才能将快件送达。因此需要对100件快件分区，即将50个配送点分成三组。利用距离矩阵寻觅两两之间的最短距离是50个配送点中最大的三组最短距离的三个点，以此三点为基点依照准那么划分派送点。关键字：Floyd算法距离矩阵哈密尔顿圈二边逐次修正法矩阵翻转问题重述某公司现有一配送员，，从配送仓库动身，要将100件快件送到其负责的50个配送点。此刻各配送点及仓库坐标已知，货物信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。问题一：配送员将前30号快件送到并返回，设计最正确的配送方案，使得路程最短。问题二：该派送员从上午8：00开始配送，要求前30号快件在指按时刻前送到，设计最正确的配问题三：不考虑所有快件送达的时刻限制，现将100件快件全数送到并返回。设计最正确的配送方案。配送员受快件重量和体积的限制，需半途返回取快件，不考虑休息时刻。符号说明D：n个矩阵nV：各个极点的集合E：各边的集合e：每一条边ijw:边的权(e)G：加权无向图v,v：定点ijC：哈密尔顿圈f(V)：最正确哈密尔顿圈i模型的成立一、大体假设1、假设送货员的始终以24千米/小时的速度送货，半途没成心外情形2、假设送货员依照途径示用意行走；3、假设仓库点为第51点；4、假设送货员回到仓库点再次取货时刻不计二、模型成立与求解问题一：1、数据处置利用数据处置软件，处置附表2求出给定配送点之间的彼此距离。最终利用矩阵对处置数据进行数据统计整理。TOC\o"1-5"\h\z'131916_828642078235118218251211797_51261392_矩阵前两列表示彼此连接的配送点，第三列表示相邻两配送点之间边的距离。利用上述数据矩阵能够构造线路示用意的带权邻接矩阵，再用Floyd算法求出各配送点之间的距离。2、Floyd算法大体思想直接在示用意的带权邻接矩阵中，通过插入定点的方式构造出n个矩阵D,D，…,D,最后取TOC\o"1-5"\h\z12n得的矩阵D为距离矩阵，同时求出插入点矩阵以便取得两点之间的最短路程。n123…，…4950511077451916…'…2030616989100682774505829…，…2557022001169263191658290…，…20705173881046749203062557020705……035691172150169892200117388……35690992851100681692610467……1172199280TOC\o"1-5"\h\z令G二(V,E)为一个加权无向图，其中V表示各个极点的集合，V={v,v,v，…,v}；其中E表012n示各边的集合，E={e，而e=(v,v)。图G中每一条边e都对应一个实数w，那么称w为边JJIJJ(e)(e)的权。若是任意两边相连，那么G为完备图。设G=(V,E)是连通无向图，通过G的每一个定点正好形成一个圈，那么称G为哈密尔顿圈,简称H圈。最正确哈密尔顿圈是在加权图G=(V,E)中，权最小的哈密尔顿圈。判定一个加权图G=(V,E)是不是存在哈密尔顿圈是一个NP问题，而它的完备加权图G'=(V,E')(E'中每条边的权等于v,v之间的最短途径的权)中必然存在哈密尔顿圈。因此需要在ij完备加权图G'=(V,E')中寻求最正确哈密尔顿圈。该进程需要采纳二边逐次修正法而且利用矩阵翻转实现。3、二边逐次修正法的选法进程⑴、任取初始H圈：C=v,v，…,v,v，…,v,vTOC\o"1-5"\h\z012i,jn1⑵、对所有的i,j,1<i+1<j<n，假设w(v,v)+w(v,v)<w(v,v)+w(v,v)，那么在C中删iji+1j+1ii+1jj+10去边w(v,v)和w(v,v)而加入边w(v,v)和w(v,v)，形成新的H圈C，即iji+1j+1ii+1jj+1C=v,v，…，v…，v，…，v,v12i,jn1(3)、对C重复步骤(2),直到条件不知足为止，最终取得的C即为所求。4、矩阵翻转在一个矩阵中，对他的第i行(列)到第j行(列)翻转是以i行(列)和j行(列)的中心位置为转轴、旋转180度，如此：第i行(列)和第j行(列)位置互换，第i+1行(列)和第j-1行(列)位置互换。图一由附录给定的快件信息可知，1…30号快件总重量为48.5kg、体积为0・88m3,显然送货员能够一次性携带所有货物抵达配送点，经统计配送点共有21个，即V(

13、14、1六、17、1八、2—、23、24、2六、27、3—、3二、34、3六、3八、40、4二、43、4五、49)第一在程序里设置限制：艺w<50ivi=0艺v<1i1i=0将起点51点与21个送货点结合起来构造完备加权图，由完备加权图确信初始H圈，列出该初始H圈加点序的距离矩阵，然后利用二边逐次修正法对矩阵进行翻转，能够求得近似最优解的距离矩阵，从而确信近似的最正确哈密尔顿圈。由于利用矩阵翻转方式来实现二边逐次修正法的结果与初始圈有关，为取得更优解，在利用软件编程时，随机搜索出假设干个初始H圈，例如2000。在所有的H圈中挑选权值最小的一个，即确实是最正确H圈。最正确H圈的近似解为：200f(V)ii=1minf(V)i在C中删去边w(v,v)和w(v,v)而加入边w(v,v)和w(v,v)，形成新的H圈C。0iji+1j+1ii+1jj+1最终由编程取得近似最正确配送线路和总长度。ViVi图二最正确配送线路：51t26t21t17t14t16t23t32t35t38t36t38t43t42t49t42t45t40t34t31t27t39t27t31t24t19t13t18t51解得线路总长为54709m，耗时226.77min。问题二:因货物可在一次性配送，故能够不用考虑送货员的最大载重与体积问题。可是较于问题一在选择线路上，需要考虑送货时刻问题，不得超过指按时刻。因此在问题一的程序中需要再增加时刻限制。艺w<50ii=0<艺v<1ii=0T<t(i=0,1,2,…加ii结合问题一，利用相同方式求解最正确H圈。图三最正确配送线路：51t18t13t19t24T31t34t40t45t42t49t42t43t38t35t32t23t16t14t17t21t36t27t39t27t31t26t51解得线路总长为54996m，耗时227.50min问题三：由附录给定的快件信息知，1~100号快件总重量为148kg、体积为2.8m3。由于考虑送货员的最大载重与体积，送货员必需分多次配送快件。送货员显然至少需要持续三次配送，才能完成配送任务。因此问题三存在配送点分组、和每组求最正确配送方案这两个问题。第一需要制定一种比较合理的划分准那么，使三组总长加起来最短。需要选择三个点作为每一组的基点，要求这三个点两两之间的最短距离是50个配送点中最大的三组最短距离。利用距离矩阵查找其他任意点与三个基点之间的距离，距离哪个基点近，就被划分在哪一组。通过计算三个基点为：9号、28号、43号配送点。通过距离矩阵将100件快件的配送点分组如下：配送方案重量(kg)体积(m3)12345678910141617182123323549.90.9112一111213151920222526282930334144464848.380.985三242731343637383940434547495049.720.9038求和1482.8表利用问题一与问题二中相同的方式：第一将起点与其他组内点结合起来构造完备加权图，由完备加权图确信初始H圈，列出该初始H圈加点序的距离矩阵，然后利用二边逐次修正法对矩阵进行翻转，能够求得近似最优解的距离矩阵，从而确信近似的最正确哈密尔顿圈。图四最终由程序解得三组最正确配送线路为：第一组：51T18T7T1T8T3T4T2T5T4T3T1T6T1T7T10T9T14T16T23T32T35T32t23t17t21t51解得线路总长52743m，耗时227.4min第二组：51t26t31t24t19t25t41t44t48t46t33t28t30t22t29t22t20t22t15t12t11t13t18t51解得线路总长47736m，耗时221.4min。第三组：51t26t31t27t39t27t36t38t43t42t49t50t45t40t47t40t37t40t34t31t26t51解得线路总长42421m，耗时208.2min模型的优缺点点评关于问题一所成立的模型，通过Floy