An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines. (August 2016)

• Record Type: Journal Article
• Authors: Ghilas, Veaceslav; Demir, Emrah; Van Woensel, Tom
• Is Part Of: Computers & operations research. Volume 72(2016)
• Page Start: 12
• Page End: 30
• Publication Date: 2016-08
• Subjects: Freight transportation -- Pickup and delivery problem -- Heuristic algorithm -- Scheduled lines; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.01.018
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The Pickup and Delivery Problem with Time Windows and Scheduled Lines (PDPTW-SL) concerns scheduling a set of vehicles to serve freight requests such that a part of the journey can be carried out on a scheduled public transportation line. Due to the complexity of the problem, which is NP-hard, we propose an Adaptive Large Neighborhood Search (ALNS) heuristic algorithm to solve the PDPTW-SL. Complex aspects such as fixed lines׳ schedules, synchronization and time-windows constraints are efficiently considered in the proposed algorithm. Results of extensive computational experiments show that the ALNS is highly effective in finding good-quality solutions on the generated PDPTW-SL instances with up to 100 freight requests that reasonably represent real life situations. Abstract : Highlights: Integration of pickup and delivery problem with public transportation is analyzed. Public transportation is used as a part of the small-size freight's journey. An adaptive large neighborhood search heuristic is proposed to solve the problem. Considerable cost savings can be achieved from the integrated transport networks.