Solving pickup and delivery problems with refined construction and repair heuristics

Abstract

Pickup and delivery problems with time windows (PDP-TW) involve assigning all paired pickup-and-delivery requests to various vehicles to satisfy relevant time-window requirements while minimizing certain objective measures including the total number of vehicles used. In some previous work, the conventional push forward insertion heuristic (PFIH) was successfully adapted to work with a new swap operator for repairs so as to effectively solve PDP-TWs. Here, we firstly adapted the PFIH to efficiently construct a better initial solution which will then be iteratively improved by another refined swapping scheme which systematically revises its neighborhood size for opportunistic improvements. The prototype using our refined heuristics gained impressive results against those of a tabu-embedded metaheuristic search on a set of modified Solomon's test cases. More importantly, the refined heuristics prompts for future investigation and improvement to effectively solve related scheduling problems. © Springer-Verlag Berlin Heidelberg 2004.