The Pickup and Delivery Problem with Time Windows: an Adaptive Large Neighborhood Search heuristic

The Pickup and Delivery Problem with Time Windows, concerns the transportation of goods between paired pickup and delivery locations. In this problem, which is a generalization of the classical Vehicle Routing Problem, pickup locations must be visited before the corresponding delivery locations by the same vehicle. In this thesis we implement the adaptive large neighborhood search heuristic, as proposed by Ropke and Pisinger (2006). This heuristic is an extension of the large neighborhood search heuristic, in which the removal heuristics and insertion heuristics are picked at random with adaptive selection probabilities. These probabilities change during the search, based on previous performance. We reproduce the results of Ropke and Pisinger (2006). In addition, we propose a new time related removal heuristic for the adaptive large neighborhood search heuristic and investigate an extension of the problem which includes a transfer point. At this transfer point the goods from the pickup location can be stored temporarily, after which a different vehicle can deliver these goods to its corresponding delivery location. We found that the inclusion of the time related removal heuristic results in better solutions for part of the test instances. Moreover, the adaptive large neighborhood search heuristic for the extended problem with transfer point also gives better solutions for many of the test instances.