Premium
New lower bounds for the Capacitated Arc Routing Problem
Author(s) -
Pearn Wen Lea
Publication year - 1988
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.3230180305
Subject(s) - arc routing , bounding overwatch , upper and lower bounds , routing (electronic design automation) , computer science , generalization , mathematical optimization , arc (geometry) , matching (statistics) , vehicle routing problem , mathematics , computer network , artificial intelligence , mathematical analysis , statistics , geometry
The Capacitated Arc Routing Problem (CARP), a generalization of the arc routing problems such as the Chinese Postman Problem (CPP), is a very practical distribution management problem which has many real‐world applications. This paper briefly reviews two existing lower bounding procedures—the Matching Lower Bound and the Node Scanning Lower Bound, then introduces a new bounding technique to provide tighter lower bounds on the problem solutions.