Premium
Capacitated arc routing problems
Author(s) -
Golden Bruce L.,
Wong Richard T.
Publication year - 1981
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.3230110308
Subject(s) - arc routing , computer science , mathematical optimization , routing (electronic design automation) , vehicle routing problem , arc (geometry) , focus (optics) , class (philosophy) , destination sequenced distance vector routing , static routing , node (physics) , link state routing protocol , mathematics , routing protocol , computer network , artificial intelligence , engineering , optics , physics , geometry , structural engineering
A capacitated node routing problem, known as the vehicle routing or dispatch problem, has been the focus of much research attention. On the other hand, capacitated arc routing problems have been comparatively neglected. Both classes of problems are extremely rich in theory and applications. Our intent in this paper is to define a capacitated arc routing problem, to provide mathematical programming formulations, to perform a computational complexity analysis, and to present an approximate solution strategy for this class of problems. In addition, we identify several related routing problems and develop tight lower bounds on the optimal solution.