Fast upper and lower bounds for a large‐scale real‐world arc routing problem

Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs wit...

Full description

Saved in:
Bibliographic Details
Published in:Networks 2023-01, Vol.81 (1), p.107-124
Main Authors: Boyacı, Burak, Dang, Thu Huong, Letchford, Adam N.
Format: Article
Language:English
Subjects:
Algorithms
arc routing
combinatorial optimization
Heuristic methods
integer programming
Lower bounds
Route planning
Vehicle routing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Arc routing problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, however, we encountered some real‐life ARPs with over 10 000 roads, which is much larger than those usually considered in the literature. For these problems, we develop fast upper‐ and lower‐bounding procedures. We also present extensive computational results.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.22120