Two-Echelon Vehicle Routing Problem with Time Windows and Simultaneous Pickup and Delivery

Abstract In this paper, we propose a tabu search algorithm for the two-echelon vehicle routing problem with time windows and simultaneous pickup and delivery (2E-VRPTWSPD), which is a new variant of the two-echelon vehicle routing problem (2E-VRP) by considering the time windows constraints and simultaneous pickup and delivery. In 2EVRPTWSPD, the pickup and delivery activities are performed simultaneously by the same vehicles through the depot to satellites in the first echelon and satellites to customers in the second echelon, where each customer has a specified time window. To solve this problem, firstly, we formulate the problem with a mathematical model. Then, we implement a variable neighborhood tabu search algorithm with the proposed solution representation of dummy satellites to solve large-scale instances. Dummy satellites time windows are used in our algorithm to speed up the algorithm. Finally, we generate two instance sets based on the existing 2E-VRP and 2E-VRPTW benchmark sets and conduct additional experiments to analyze the performance of our algorithm.