The Vehicle Routing Problem with Release and Due Dates

Benjamine Shelbourne, Maria Battarra, Chris N. Potts

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

A novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm.
LanguageEnglish
Pages705 - 723
JournalINFORMS Journal on Computing
Volume29
Issue number4
DOIs
StatusPublished - 30 Aug 2017

Fingerprint

Vehicle routing
Scheduling
Vehicle routing problem
Release dates
Due dates
Path relinking

Cite this

The Vehicle Routing Problem with Release and Due Dates. / Shelbourne, Benjamine; Battarra, Maria; Potts, Chris N.

In: INFORMS Journal on Computing, Vol. 29, No. 4, 30.08.2017, p. 705 - 723.

Research output: Contribution to journalArticle

Shelbourne, Benjamine ; Battarra, Maria ; Potts, Chris N. / The Vehicle Routing Problem with Release and Due Dates. In: INFORMS Journal on Computing. 2017 ; Vol. 29, No. 4. pp. 705 - 723.
@article{985ebc6af3bb4e1886d65d931de362d2,
title = "The Vehicle Routing Problem with Release and Due Dates",
abstract = "A novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm.",
author = "Benjamine Shelbourne and Maria Battarra and Potts, {Chris N.}",
year = "2017",
month = "8",
day = "30",
doi = "10.1287/ijoc.2017.0756",
language = "English",
volume = "29",
pages = "705 -- 723",
journal = "INFORMS Journal on Computing",
issn = "1091-9856",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "4",

}

TY - JOUR

T1 - The Vehicle Routing Problem with Release and Due Dates

AU - Shelbourne, Benjamine

AU - Battarra, Maria

AU - Potts, Chris N.

PY - 2017/8/30

Y1 - 2017/8/30

N2 - A novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm.

AB - A novel extension of the classical vehicle routing and scheduling problems is introduced that integrates aspects of machine scheduling into vehicle routing. Associated with each customer order is a release date that defines the earliest time that the order is available to leave the depot for delivery and a due date that indicates the time by which the order should ideally be delivered to the customer. The objective is to minimize a convex combination of the operational costs and customer service level, represented by the total distance traveled and the total weighted tardiness of delivery, respectively. A path-relinking algorithm (PRA) is proposed to address the problem, and a variety of benchmark instances are generated to evaluate its performance. The PRA exploits the efficiency and aggressive improvement of neighborhood search but relies on a new path-relinking procedure and advanced population management strategies to navigate the search space effectively. To provide a comparator algorithm to the PRA, we embed the neighborhood search into a standard iterated local search algorithm (ILS). Extensive computational experiments on the benchmark instances show that the newly defined features have a significant and varied impact on the problem, and the performance of the PRA dominates that of the ILS algorithm.

UR - https://doi.org/10.1287/ijoc.2017.0756

U2 - 10.1287/ijoc.2017.0756

DO - 10.1287/ijoc.2017.0756

M3 - Article

VL - 29

SP - 705

EP - 723

JO - INFORMS Journal on Computing

T2 - INFORMS Journal on Computing

JF - INFORMS Journal on Computing

SN - 1091-9856

IS - 4

ER -