Home > Research > Publications & Outputs > Pricing routines for vehicle routing with time ...

Research

Associated organisational units

Electronic data

  • pricing-time-windows

    Rights statement: The final, definitive version of this article has been published in the Journal, Computers & Operations Research 51, 2014, © ELSEVIER.

    Accepted author manuscript, 360 KB, PDF document

Links

Text available via DOI:

Keywords

View graph of relations

Pricing routines for vehicle routing with time windows on road networks

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Pricing routines for vehicle routing with time windows on road networks. / Letchford, Adam; Nasiri, Saeideh D.; Oukil, Amar.
In: Computers and Operations Research, Vol. 51, 11.2014, p. 331-337.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, A, Nasiri, SD & Oukil, A 2014, 'Pricing routines for vehicle routing with time windows on road networks', Computers and Operations Research, vol. 51, pp. 331-337. https://doi.org/10.1016/j.cor.2014.06.022

APA

Letchford, A., Nasiri, S. D., & Oukil, A. (2014). Pricing routines for vehicle routing with time windows on road networks. Computers and Operations Research, 51, 331-337. https://doi.org/10.1016/j.cor.2014.06.022

Vancouver

Letchford A, Nasiri SD, Oukil A. Pricing routines for vehicle routing with time windows on road networks. Computers and Operations Research. 2014 Nov;51:331-337. doi: 10.1016/j.cor.2014.06.022

Author

Letchford, Adam ; Nasiri, Saeideh D. ; Oukil, Amar. / Pricing routines for vehicle routing with time windows on road networks. In: Computers and Operations Research. 2014 ; Vol. 51. pp. 331-337.

Bibtex

@article{1e4ba341293d40fd9cd4e4006c4035df,
title = "Pricing routines for vehicle routing with time windows on road networks",
abstract = "Several very effective exact algorithms have been developed for vehicle routing problems with time windows. Unfortunately, most of these algorithms cannot be applied to instances that are defined on road networks, because they implicitly assume that the cheapest path between two customers is equal to the quickest path. Garaix and coauthors proposed to tackle this issue by first storing alternative paths in an auxiliary multi-graph, and then using that multi-graph within a branch-and-price algorithm. We show that, if one works with the original road network rather than the multi-graph, then one can solve the pricing subproblem more quickly, in both theory and practice.",
keywords = "vehicle routing, Combinatorial optimisation, Bi-criteria shortest paths",
author = "Adam Letchford and Nasiri, {Saeideh D.} and Amar Oukil",
note = "The final, definitive version of this article has been published in the Journal, Computers & Operations Research 51, 2014, {\textcopyright} ELSEVIER.",
year = "2014",
month = nov,
doi = "10.1016/j.cor.2014.06.022",
language = "English",
volume = "51",
pages = "331--337",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",

}

RIS

TY - JOUR

T1 - Pricing routines for vehicle routing with time windows on road networks

AU - Letchford, Adam

AU - Nasiri, Saeideh D.

AU - Oukil, Amar

N1 - The final, definitive version of this article has been published in the Journal, Computers & Operations Research 51, 2014, © ELSEVIER.

PY - 2014/11

Y1 - 2014/11

N2 - Several very effective exact algorithms have been developed for vehicle routing problems with time windows. Unfortunately, most of these algorithms cannot be applied to instances that are defined on road networks, because they implicitly assume that the cheapest path between two customers is equal to the quickest path. Garaix and coauthors proposed to tackle this issue by first storing alternative paths in an auxiliary multi-graph, and then using that multi-graph within a branch-and-price algorithm. We show that, if one works with the original road network rather than the multi-graph, then one can solve the pricing subproblem more quickly, in both theory and practice.

AB - Several very effective exact algorithms have been developed for vehicle routing problems with time windows. Unfortunately, most of these algorithms cannot be applied to instances that are defined on road networks, because they implicitly assume that the cheapest path between two customers is equal to the quickest path. Garaix and coauthors proposed to tackle this issue by first storing alternative paths in an auxiliary multi-graph, and then using that multi-graph within a branch-and-price algorithm. We show that, if one works with the original road network rather than the multi-graph, then one can solve the pricing subproblem more quickly, in both theory and practice.

KW - vehicle routing

KW - Combinatorial optimisation

KW - Bi-criteria shortest paths

U2 - 10.1016/j.cor.2014.06.022

DO - 10.1016/j.cor.2014.06.022

M3 - Journal article

VL - 51

SP - 331

EP - 337

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

ER -