An adaptive large neighborhood search heuristic for the pickup and delivery problem with time Windows and scheduled lines

V. Ghilas, E. Demir, T. van Woensel

Research output: Contribution to journalArticleAcademicpeer-review

36 Citations (Scopus)
5 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)12-30
JournalComputers & Operations Research
Volume72
DOIs
Publication statusPublished - 2016

Fingerprint

Pickup and Delivery
Neighborhood Search
Pickups
Time Windows
Heuristics
Line
Heuristic algorithms
Synchronization
Scheduling
Computational Experiments
Heuristic algorithm
Search Algorithm
Schedule
NP-complete problem
Pickup and delivery
Time windows
Heuristic search
Experiments
Freight

Cite this

@article{180d06f3d3a8491c86da0cc1fe6a030a,
title = "An adaptive large neighborhood search heuristic for the pickup and delivery problem with time Windows and scheduled lines",
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.",
author = "V. Ghilas and E. Demir and {van Woensel}, T.",
year = "2016",
doi = "10.1016/j.cor.2016.01.018",
language = "English",
volume = "72",
pages = "12--30",
journal = "Computers & Operations Research",
issn = "0305-0548",
publisher = "Elsevier",

}

An adaptive large neighborhood search heuristic for the pickup and delivery problem with time Windows and scheduled lines. / Ghilas, V.; Demir, E.; van Woensel, T.

In: Computers & Operations Research, Vol. 72, 2016, p. 12-30.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - An adaptive large neighborhood search heuristic for the pickup and delivery problem with time Windows and scheduled lines

AU - Ghilas, V.

AU - Demir, E.

AU - van Woensel, T.

PY - 2016

Y1 - 2016

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

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

U2 - 10.1016/j.cor.2016.01.018

DO - 10.1016/j.cor.2016.01.018

M3 - Article

VL - 72

SP - 12

EP - 30

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -