摘要：带集货和配送的多站点车辆路线问题（MDVRPPD）是经典VRP的扩展，是多个站点和若干客户既有需求又有供给的VRP问题。本文研究了该问题的模型并提出了求解该问题的多阶段启发式算法，即先用临界客户的思想把多站点转换为单一站点问题，再使用基于SFC的分组方法来构造初始解，并使用3－opt算法优化回路，之后使用插入算法改善解的可行性，从而得到最终优化解。最后通过实例计算证明了该方法解决MDVRPPD问题的实用可行性和科学有效性。
关键词：物流VRP SFC 优化
Research on Optimal Algorithm for Multi-Depot VehicleRouting Problem with Pickups and Deliveries
Hu Da-wei*, Chen cheng, Guo xiao-fen
（Collegeof automobile, chang’an university , xi’an, 710064, China）
Abstract:Multi-Depot Vehicle Routing Problem with Pickups and Deliveries isan extension to the classic VRP, which has several depots and customers withpickups and deliveries simultaneously. This paper makes research on its modeland further more, presents the multi-stages heuristic algorithm to solve thisproblem. Firstly, use the idea of borderline customers to change MDVRPPD toSDVRPPD. Secondly, constructs the initial solution by using cluster methodbased on SFC and optimizing the tours by using 3-opt algorithm. Thirdly,improves the infeasibilities by insertion algorithm and then obtains the finaloptimal solution. Finally, the algorithm proved to be feasible, practical,scientific and effective.
Keyword：Logistics, VRP, SFC, Optimal
1引言
车辆路线问题（Vehicle Routing Problem，简称VRP）是由Dantzing和Ramser在1959年首次提出的。VRP定义是考虑从一个或多个站点出发，车辆把货物运送到空间任意分布的一系列客户点，有序的通过它们，满足客户的需求且每个顾客只能被服务一次，组成适当的行车路线，在车辆容量等约束条件下使总行驶费用最小（行驶费用可以用路程、时间等表示）。
根据约束条件的不同VRP可扩展出不同的具体问题，常见的主要有以下几类：
（1）车辆容量：若无车辆容量约束则为经典TSP问题；
（2）时间窗：包括软时间窗和硬时间窗约束；
（3）车辆服务限制：限制每辆车所能服务的最多客户数或是所能行驶的最大距离、运行最长时间等；
（4）优先约束：限制在访问客户j之前一定要先访问客户i；
（5）相容性约束：如某些货物不能同时装在同一辆车上；
（6）车型约束：对每种车型的数量进行限制；
（7）路线中客户的性质：如集货客户和配送客户等。
带集货和配送的多站点车辆路线问题（Multi-Depot VehicleRouting Problem with Pickups and Deliveries,简称MDVRPPD）是经典VRP的扩展，是指在多个站点的情况下，客户既有需求（配送）又有供应（集货）的VRP问题，MDVRPPD的一个重要特点是可以利用回程车辆的空闲容量（即提高车辆总体装载率）来减少配送费用，实际表明这能在很大程度上节约配送费用。但其求解更加困难，因为可能导致较低的车辆容量利用率、增加行驶里程或需要增派更多的车辆。通常对这类问题做更严格的假设：所有的配送都从站点开始，所有的集货都需要送回站点，也就是说客户之间没有货物的交换。问题的目标是在已知配送和集货数量的前提下，找到一系列路线满足每个客户的需求，并且每个客户只由一辆车服务且只能访问一次，每条路线都由站点开始且最后回到站点，使总行驶距离最短。