Premium
Fast upper and lower bounds for a large‐scale real‐world arc routing problem
Author(s) -
Boyacı Burak,
Dang Thu Huong,
Letchford Adam N.
Publication year - 2023
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.22120
Subject(s) - arc routing , bounding overwatch , arc (geometry) , routing (electronic design automation) , computer science , heuristic , variety (cybernetics) , mathematical optimization , vehicle routing problem , upper and lower bounds , scale (ratio) , mathematics , artificial intelligence , computer network , geography , mathematical analysis , geometry , cartography
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.