Improving the Initialization and Repair Heuristics to Effectively Solve the Pickup and Delivery Problems with Time Windows

Abstract

Pickup and delivery problems with time windows (PDP-TW) are challenging yet realistic scheduling problems in which each delivery vehicle is assigned to handle different pairs of pickup-and-delivery requests. Our previous work successfully adapted the push forward insertion heuristic (PFIH) for initialization, and proposed a new swap operator to effectively solve PDP-TWs. In this paper, we improved our adapted PFIH to efficiently obtain a better initial solution. Moreover, we proposed an adaptive swap (AD-Swap) operator that can flexibly revise its neighborhood size for iterative improvements. Our improved search prototype achieved remarkable results against those of a tabu-embedded metaheuristic search or our previous work on a set of modified Solomon's test cases. More importantly, our improved heuristics can easily be integrated into many search schemes to solve other scheduling problems.