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

Veaceslav Ghilas; Emrah Demir; Tom Van Woensel

doi:10.1016/j.cor.2016.01.018

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

Veaceslav Ghilas
, Emrah Demir
, Tom Van Woensel

Management Science & Engineering

Eindhoven University of Technology

Research output: Contribution to journal › Article › peer-review

217 Scopus citations

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 language	British English
Pages (from-to)	12-30
Number of pages	19
Journal	Computers and Operations Research
Volume	72
DOIs	https://doi.org/10.1016/j.cor.2016.01.018
State	Published - 1 Aug 2016

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 11 Sustainable Cities and Communities

Keywords

Freight transportation
Heuristic algorithm
Pickup and delivery problem
Scheduled lines

Access to Document

10.1016/j.cor.2016.01.018

OpenUrl availability

Full text

Cite this

@article{9ad02dd6d5374cb3a149f986ba0c2ea7,

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.",

keywords = "Freight transportation, Heuristic algorithm, Pickup and delivery problem, Scheduled lines",

author = "Veaceslav Ghilas and Emrah Demir and \{Van Woensel\}, Tom",

note = "Funding Information: The authors gratefully acknowledge funds provided by Dinalog, the Dutch Institute for Advanced Logistics , under the Grant titled “Cargo Hitching”, \# 2011 4 086R . Thanks are due to the Editor and two anonymous reviewers for their useful comments and for raising interesting points for discussion. Publisher Copyright: {\textcopyright} 2016 Elsevier Ltd. All rights reserved.",

year = "2016",

month = aug,

day = "1",

doi = "10.1016/j.cor.2016.01.018",

language = "British English",

volume = "72",

pages = "12--30",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

}

TY - JOUR

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

AU - Ghilas, Veaceslav

AU - Demir, Emrah

AU - Van Woensel, Tom

N1 - Funding Information: The authors gratefully acknowledge funds provided by Dinalog, the Dutch Institute for Advanced Logistics , under the Grant titled “Cargo Hitching”, # 2011 4 086R . Thanks are due to the Editor and two anonymous reviewers for their useful comments and for raising interesting points for discussion. Publisher Copyright: © 2016 Elsevier Ltd. All rights reserved.

PY - 2016/8/1

Y1 - 2016/8/1

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.

KW - Freight transportation

KW - Heuristic algorithm

KW - Pickup and delivery problem

KW - Scheduled lines

UR - https://www.scopus.com/pages/publications/84959422616

U2 - 10.1016/j.cor.2016.01.018

DO - 10.1016/j.cor.2016.01.018

M3 - Article

AN - SCOPUS:84959422616

SN - 0305-0548

VL - 72

SP - 12

EP - 30

JO - Computers and Operations Research

JF - Computers and Operations Research

ER -

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

Abstract

UN SDGs

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this