A Spatio-temporal Distance Based Two-Phase Heuristic Algorithms for Vehicle Routing Problem

Vehicle Routing Problem with Time Windows (VRPTW) is a well-known NP-hard problem. An effective method to solve this problem is to partition the customers first and then create and improve the routes. Conventionally, customers are partitioned by spatial distance only. In this paper, we propose to use a spatiotemporal distance to group customers. A new tabu search algorithm with a self-adaptive objective function is employed to improve the route. With 56 Solomon benchmark problems, different strategies have been tested and compared. Computational results show that proposed spatiotemporal distance is more efficient than spatial distance when solving narrow time window VRPTW problems, which can provide many known best solutions.