摘要
具有硬时间窗口约束下同时收发的车辆路径问题(vehicle routing problem with simultaneous pick-up and delivery with hard time windows,VRPSPD with Hard TW)是将产品配送和废物回收统一进行优化的问题。本文研究了一个中心仓库,多台车辆向具有配送需求和回收需求的客户提供服务,客户存在硬时间窗口要求的车辆运输问题。该问题中,客户的配送需求和回收需求必须同时获得满足,即客户仅允许被访问一次,且需求不可分割,只能由一台车辆提供服务。且客户的硬时间窗口要求必须获得满足。首先将修正后的旅程分割方法应用于硬时间窗口约束下的VRPSPD问题初始解的获得,并利用响应性禁忌搜索算法框架,结合基于多种领域的可变式搜索方法,给出一启发式算法。计算机实验结果表明,该启发式算法在求解VRPSPD with hard TW上是有效的。
The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection. The paper analyzes the vehicle routing problem in which a single depot can offer service to many customers that may both receive and send goods by multiple vehicles, and customers strictly require that their delivery and pickup is to be served in a single visit by a vehicle simultaneously. The objective of the problem is to minimize the total distance to all customers, each with a single stop, without violating the capacity of each vehicle and the customer＇s hard time windows. Firstly, the revised tour-partitioning algorithm is used to get the initial solution to the vehicle routing problem with simultaneous pick-up and delivery and the hard time windows. In the reactive tabu search phase, variable neighborhood search modules are also proposed to improve the results. Finally, computational experiments show that the proposed hybrid heuristic can obtain optimal solutions very efficiently.
