多中心车辆路径问题的解决思路

《多中心车辆路径问题的解决思路》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、本人联系方式姓名：李桂平地址：福州市福州大学（老校区）科学楼13层e-mail：lgp0006@yahoo.com.cn联系电话：1385019924012多中心车辆路径问题的解决思路李桂平陈楠（福州大学福建省空间信息工程研究中心350002）摘要：物流配送问题通常被抽象为经典的车辆路径问题（VRP）。本文研究了多中心车辆路径问题（MDVRP）的解决思路，提出了采用混合遗传算法。初始染色体的生成和优化都采用启发式方法，随后使用经典的遗传算法方法处理染色体。相对于经典的遗传算法，使用启发式算法生成和优化的初始解更接近于最优解，最终的解也更好。关键词：物流配送，车辆

2、路径问题，多中心,混合遗传算法1引言车辆路径问题（VehicleRoutingProblem）的英文简写是VRP。车辆路径问题是很复杂的现实问题，当前，对车辆路径问题的研究有很多，因为其在包括物流配送等领域有广泛应用。假设某个物流公司有一个配送中心，配送中心的地理位置是已知的，配送中心有一个运输车队，车队的每辆车的运输能力也是确定的。现在要为一群客户配送货物，客户的需求量和地理位置已知。通常情况下，配送中心要配送的货物数量很大，其要服务的客户数量也很大，要动用不止一辆的汽车才能把货物配送到其客户手里。在车辆路径问题(VRP)里，一辆汽车等同于一个路径，任何一个客

3、户只能被一辆配送车或者路径服务。任何一辆配送车都从配送中心出发，最后又得返回配送中心。物流配送公司的决策者们要确定某个客户由那辆配送车服务，或者说要确定某辆车要为那些客户服务，这就是路径问题。紧接着，决策者们还得确定某个路径里头的客户被服务先后秩序，这是服务秩序计划问题。毫无疑问，更好的路径规划，可以在相同时间内服务更多的客户，让客户更满意。车辆路径问题（VRP）在物流配送了领域有重大的应用价值，又是复杂的问题，近年来物流业迅速成为重要的经济产业，众多学者对车辆路径问题（VRP）做了很多研究工作。在[1]这里只列举了其中一部分。1959年Dantzig和Rams

4、e提出了车辆路径问题（VRP）。1962[2][3]年，Balinski等人提出了VRP的集分割。1964年Clarke和Wright提出了节省矩阵法，在MDVRPSTW中用于确定某个车辆路径要访问那些客户。1971年，Eilon等人提出动态规划[4]法用于固定车辆数的VRP的解决。1981年，Christofides等人提出了K度中心树和相关[5]算法，用于解决固定车辆数的VRP。1995年，Sumichrast和Markham研究了多中心车辆路[6]径问题（MDVRP），用于解决从多个原料点向多个工厂配送原料的问题。1996年，Renaud[7]等人应用启发

5、式方法解决多中心车辆路径问题（MDVRP）。1999年，Su提出了用动态车辆[8]控制和规划系统来解决多中心车辆路径问题（MDVRP）。2002年，Giosa等人对多中心车项目来源：国家973前期专项“基于混合遗传算法和LBS的动态VRP研究”(编号：2007CB316507)、国家科技支撑计划课题（2007BAH16B03）、福建省科技重大专项专题（2006HZ0001-1）作者简介：李桂平（1982-），福建龙岩人，硕士研究生，研究方向为地理信息系统辆路径问题进行扩展，研究了多中心带时间窗车辆路径问题（MDVRPTW），在对客户分组时，[9]Giosa等人设

6、计并比较了六种方法。2多中心车辆路径问题的描述经典的车辆路径问题（VRP）只考虑了少量的约束条件，与现实问题比起来，还过于简单，还不能很好地模拟实际情况。为了更贴近实际情况，需要对车辆路径问题（VRP）进行扩展。车辆路径问题（VRP）可以扩展成多中心车辆路径问题（MDVRP）。本文考虑物流配送公司拥有多个配送中心的车辆路径问题（MDVRP）。多中心车辆路径问题更复杂，决策者还得确定某个客户由那个配送中心供货，这就是说多了个对客户进行分组的问题。某个物流配送公司有多个配送中心，配送中心的个数和地理位置已知，每个配送中心都足够大，能放得下客户（零售商）定的商品。每个

7、配送中心都有一个运输车队，车队的每辆车的承载能力已知，运输车把商品从配送中心运送到客户那里，每辆车必须从配送中心出发，然后返回同个配送中心。每个客户（零售商）的地理位置和所定的货物量也是已知的。每个客户只被一辆配送车访问一次。这个实际的配送问题可以称为多中心车辆路径问题（MDVRP），决策者要做三方面的决定：首先，决策者要把客户分类，每个客户类对应一个配送中心；其次，对于各个客户类，决策者要确定每个客户由那辆车服务，即是某辆车要为那些客户服务，且运送货物总量不会超过其承载能力；最后对于每辆车，决策者需确定访问客户的先后顺序。总的来说，多中心车辆路径问题（MDVR

8、P）的目标是让总的运送距