Vehicle Routing Problem with Time Windows Based on Spatiotemporal Distance

Vehicle Routing Problem with Time Windows (VRPTW) is a well known NP-hard problem. A typical way to solve this problem is to partition the customers into groups first and then construct optimal routes for each group or groups. Conventionally, customers are partitioned according to the spatial distance only, while ignoring their time window requirements. In this paper, we consider jointly spatial and temporal characteristics of customers and propose a spatiotemporal distance based criteria for customers partitioning. To improve the initial solution, a tabu search algorithm is developed. To improve the convergence efficiency, this algorithm limits the objective value ranges that around the recently visited solutions, Instead of limiting recently visited solutions, the performance of the proposed algorithm is examined with 56 Solomon benchmark problems. The results indicate that spatiotemporal distance is more effective than spatial distance when solving vehicle routing problems with narrow time windows. Some results are even comparable to the best results obtained so far.

摘要带时间窗的车辆路径问题是典型的NP难题，一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法. 传统算法在顾客分组时主要考虑顾客的空间位置关系，但是忽略了顾客对服务时间窗口的要求. 本文同时考虑顾客的时间和空间特性，提出了一种基于时空度量的顾客分组方法. 在路径优化阶段，本文提出了一种禁忌搜索算法来进行求解，该算法中禁忌的对象不是解，而是这些解的目标函数值的区间，以便于提高收敛效率. 作为验证，本文以Solomon标杆问题集为算例进行演算，结果表明，在窄时间窗约束下，基于时空距离的两阶段启发式算法明显优于基于空间距离的算法，且部分算例的解达到了国内外已发表的最好解.