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

Stefan Røpke, David Pisinger

Research output: Contribution to journalJournal articleResearchpeer-review

4001 Downloads (Pure)

Abstract

The pickup and delivery problem with time windows is the problem of serving a number of transportation requests using a limited amount of vehicles. Each request involves moving a number of goods from a pickup location to a delivery location. Our task is to construct routes that visit all locations such that corresponding pickups and deliveries are placed on the same route, and such that a pickup is performed before the corresponding delivery. The routes must also satisfy time window and capacity constraints. This paper presents a heuristic for the problem based on an extension of the large neighborhood search heuristic previously suggested for solving the vehicle routing problem with time windows. The proposed heuristic is composed of a number of competing subheuristics that are used with a frequency corresponding to their historic performance. This general framework is denoted adaptive large neighborhood search. The heuristic is tested on more than 350 benchmark instances with up to 500 requests. It is able to improve the best known solutions from the literature for more than 50% of the problems. The computational experiments indicate that it is advantageous to use several competing subheuristics instead of just one. We believe that the proposed heuristic is very robust and is able to adapt to various instance characteristics.
Keyword: pickup and delivery problems with time windows,metaheuristics,large neighborhood search
Original languageEnglish
JournalTransportation Science
Volume40
Pages (from-to)455-472
DOIs
Publication statusPublished - 2006
Externally publishedYes

Fingerprint

Dive into the research topics of 'An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows'. Together they form a unique fingerprint.

Cite this