TY - UNPB

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

AU - Letchford, Adam

AU - Nasiri, Saeideh D.

N1 - It was published in "Computers & Operations Research" in August 2014.

PY - 2014

Y1 - 2014

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

M3 - Working paper

T3 - Lancaster University Management School Working Paper Series

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

PB - The Department of Management Science

CY - Lancaster University

ER -