An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers

An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers

0.00 Avg rating0 Votes
Article ID: iaor20135214
Volume: 47
Issue: 3
Start Page Number: 344
End Page Number: 355
Publication Date: Aug 2013
Journal: Transportation Science
Authors: , ,
Keywords: adaptive search, neighborhood search
Abstract:

The pickup and delivery problem (PDP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the PDP where requests can change vehicle during their trip. The transfer is made at specific locations called ‘transfer points.’ The corresponding problem is called the pickup and delivery problem with transfers (PDPT). Solving the PDPT leads to new modeling and algorithmic difficulties. We propose new heuristics capable of efficiently inserting requests through transfer points. These heuristics are embedded into an adaptive large neighborhood search. We evaluate the method on generated instances and apply it to the transportation of people with disabilities. On these real‐life instances we show that the introduction of transfer points can bring significant improvements (up to 9%) to the value of the objective function.

Reviews

Required fields are marked *. Your email address will not be published.