An Adaptive Large Neighbourhood Search for the Pickup and Delivery Problem with Time Windows

In this research the Adaptive Large Neighbourhood Search (ALNS) of Røpke & Pisinger (2006a) is used to solve the Pickup and Delivery Problem with Time Windows (PDPTW), replicating the research of Røpke and Pisinger. ALNS uses a set of removal and insertion procedures to iteratively construct new solutions by deleting part of a high-quality old solution and rebuilding it. It is examined whether the ALNS implementation of this research can obtain similar results for problem instances of the pickup and delivery problem with time-windows constructed by Li & Lim (2003) and Røpke & Pisinger (2006a) and how the method might be improved. It was found that although the algorithm seemed to perform somewhat poorer than in the research of Røpke and Pisinger. A variant of the problem with timedependent travel times is introduced, to examine whether this problem can also be solved efficiently by ALNS. Our finding is that time-dependent pickup and delivery problems with time windows can be solved successfully by ALNS, although the running times might increase substantially if the travel time distribution is complicated. Moreover, it was found that increases in the number of iterations might substantially increase the quality of the solutions found. A potential way to increase the performance of ALNS further, is using more sophisticated insertion procedures.