An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled Lines

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 pr...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2016-08, Vol.72, p.12-30
Main Authors: Ghilas, Veaceslav, Demir, Emrah, Van Woensel, Tom
Format: Article
Language:English
Subjects:
Algorithms
Complexity theory
Delivery scheduling
Freight forwarding
Freight transportation
Heuristic
Heuristic algorithm
Operations research
Pickup and delivery problem
Public transportation
Scheduled lines
Schedules
Scheduling algorithms
Searching
Studies
Synchronism
Windows (intervals)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. •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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2016.01.018