《快递员配送路线优化模型》由会员分享，可在线阅读，更多相关《快递员配送路线优化模型（10页珍藏版）》请在金锄头文库上搜索。
1、快递员配送路线优化模型摘要如今,随着网上购物的流行，快递物流行业在面临机遇的同步也需要不断迎接新的挑战。如何可以提高物流公司的配送效率并减少配送过程中的成本，已成为急需我们解决的一种问题。下面，本文将针对某公司的一名配送员在配送货品过程中遇到的三个问题进行讨论及解答。对于问题一，由于快递员的平均速度及在各配送点停留的时间已知，故可将最短时间转换为最短路程。在此一方面通过Floy求最短路的算法，运用Matb程序将仓库点和所有配送点间两两的最短距离求解出来，将出发点与配送点结合起来构造完备加权图，由完备加权图拟定初始H圈，列出该初始H圈加点序的距离矩阵,然后使用二边逐次修正法对矩阵进行翻转,可以求
2、得近似最优解的距离矩阵,从而拟定近似的最佳哈密尔顿圈,即最佳配送方案。对于问题二,仍旧可以将时间问题转化为距离问题。运用问题一中所建立的模型，加入一种新的时间限制条件,即可求解出满足条件的最佳路线。对于问题三，送货员由于快件载重和体积的限制,至少需要三次才干将快件送达。因此需要对100件快件分区,即将50个配送点提成三组。运用距离矩阵寻找两两之间的最短距离是50个配送点中最大的三组最短距离的三个点，以此三点为基点按照准则划分派送点。核心字：loyd算法 距离矩阵 哈密尔顿圈 二边逐次修正法矩阵翻转问题重述某公司既有一配送员,，从配送仓库出发，要将10件快件送到其负责的50个配送点。目前各配送点
3、及仓库坐标已知,货品信息、配送员所承载重物的最大体积和重量、配送员行驶的平均速度已知。问题一：配送员将前3号快件送到并返回，设计最佳的配送方案,使得路程最短。问题二：该派送员从上午8：0开始配送，规定前30号快件在指定期间前送到,设计最佳的配送方案。问题三:不考虑所有快件送达的时间限制,现将1件快件所有送到并返回。设计最佳的配送方案。配送员受快件重量和体积的限制，需半途返回取快件，不考虑休息时间。符号阐明：个矩阵：各个顶点的集合:各边的集合：每一条边:边的权:加权无向图：定点 :哈密尔顿圈：最佳哈密尔顿圈模型的建立一、基本假设1、 假设送货员的始终以4千米/小时的速度送货，半途没故意外状况；2
4、、 假设送货员按照途径示意图行走;3、 假设仓库点为第51点;4、 假设送货员回到仓库点再次取货时间不计。二、 模型建立与求解问题一:1、 数据解决使用数据解决软件，解决附表求出给定配送点之间的互相距离。最后使用矩阵对解决数据进行数据记录整顿。矩阵前两列表达互相连接的配送点,第三列表达相邻两配送点之间边的距离。使用上述数据矩阵可以构造路线示意图的带权邻接矩阵,再用Floyd算法求出各配送点之间的距离。2、 Fod算法基本思想 直接在示意图的带权邻接矩阵中,通过插入定点的措施构造出n个矩阵,最后得到的矩阵为距离矩阵，同步求出插入点矩阵以便得到两点之间的最短路程。令为一种加权无向图，其中表达各个顶
5、点的集合，;其中表达各边的集合,而。图中每一条边都相应一种实数，则称为边的权。如果任意两边相连,则为完备图。设是连通无向图,通过的每个定点正好形成一种圈,则称为哈密尔顿圈,简称H圈。最佳哈密尔顿圈是在加权图中,权最小的哈密尔顿圈。鉴定一种加权图与否存在哈密尔顿圈是一种NP问题,而它的完备加权图(中每条边的权等于之间的最短途径的权）中一定存在哈密尔顿圈。因此需要在完备加权图中谋求最佳哈密尔顿圈。该过程需要采用二边逐次修正法并且运用矩阵翻转实现。、二边逐次修正法的选法过程(）、任取初始圈：（2)、对所有的,若,则在中删去边和而加入边和，形成新的圈,即（3)、对C反复环节(2)，直到条件不满足为止，
6、最后得到的即为所求。4、 矩阵翻转在一种矩阵中,对她的第行（列)到第j行(列)翻转是以行(列）和j行（列)的中心位置为转轴、旋转1度，这样:第行(列)和第j行（列)位置互换,第+1行(列）和第-1行（列)位置互换。图一由附录给定的快件信息可知,10号快件总重量为4.g、体积为0.88m，显然送货员可以一次性携带所有货品达到配送点，经记录配送点共有21个,即1、14、16、17、18、21、4、26、27、31、32、34、36、3、4、2、4、4、4一方面在程序里设立限制:将出发点5点与2个送货点结合起来构造完备加权图,由完备加权图拟定初始H圈,列出该初始H圈加点序的距离矩阵，然后使用二边逐次
7、修正法对矩阵进行翻转，可以求得近似最优解的距离矩阵,从而拟定近似的最佳哈密尔顿圈。由于使用矩阵翻转措施来实现二边逐次修正法的成果与初始圈有关，为得到更优解,在使用软件编程时,随机搜索出若干个初始H圈,例如。在所有的H圈中筛选权值最小的一种，即就是最佳H圈。最佳H圈的近似解为：在中删去边和而加入边和，形成新的H圈。最后由编程得到近似最佳配送路线以及总长度。图二最佳配送路线：84349151解得路线总长为709m，耗时2267mi。问题二：因货品可在一次性配送，故可以不用考虑送货员的最大载重与体积问题。但是较于问题一在选择路线上，需要考虑送货时间问题,不得超过指定期间。因此在问题一的程序中需要再增
8、长时间限制。结合问题一，使用相似措施求解最佳圈。图三最佳配送路线：24383651解得路线总长为546，耗时2.50问题三:由附录给定的快件信息知,100号快件总重量为18kg、体积为.8m3。由于考虑送货员的最大载重与体积，送货员必须分多次配送快件。送货员显然至少需要持续三次配送，才干完毕配送任务。因此问题三存在配送点分组、以及每组求最佳配送方案这两个问题。一方面需要制定一种比较合理的划分准则,使三组总长加起来最短。需要选择三个点作为每一组的基点,规定这三个点两两之间的最短距离是50个配送点中最大的三组最短距离。运用距离矩阵查找其她任意点与三个基点之间的距离，距离哪一种基点近，就被划分在哪一
9、组。 通过计算三个基点为：9号、号、3号配送点。通过距离矩阵将100件快件的配送点分组如下:表一使用问题一与问题二中相似的措施:一方面将出发点与其她组内点结合起来构造完备加权图，由完备加权图拟定初始H圈，列出该初始H圈加点序的距离矩阵，然后使用二边逐次修正法对矩阵进行翻转,可以求得近似最优解的距离矩阵，从而拟定近似的最佳哈密尔顿圈。图四最后由程序解得三组最佳配送路线为：第一组: 17151解得路线总长3m，耗时2274in第二组:2解得路线总长7736m，耗时2.4in。第三组:341251解得路线总长4242m，耗时2082min模型的优缺陷点评对于问题一所建立的模型,通过Fo算法和二边逐次修正法找到最优哈密尔顿圈,可以得到精确的最优路线,在不考虑时间及负重限制的状况下,该模型可以精确地计算出唯一的最优路线。而对于问题二与问题三，其最优路线的求解均是建立在近似最优哈密尔顿圈的基本之上的。由于无法得到精确的最优哈密尔顿圈，故模型得到的最优路线与真实的最优路线还存在着一定的差距,只能通过增长计算次数不断地逼近真实最优路线。但在容许的误差范畴内，模型已经可以较好地模拟出最优的配送路线了。
