Pricing routines for vehicle routing with time windows on road networks

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

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2014-11, Vol.51, p.331-337
Main Authors: Letchford, Adam N., Nasiri, Saeideh D., Oukil, Amar
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Bi-criteria shortest paths
Combinatorial optimization
Exact sciences and technology
Flows in networks. Combinatorial problems
Graph algorithms
Ground, air and sea transportation, marine construction
Logistics
Mathematical programming
Network flow problem
Operational research and scientific management
Operational research. Management science
Road transportation and traffic
Roads & highways
Route optimization
Studies
Vehicle routing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 co-authors 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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2014.06.022