The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases

SYNOPTIC ABSTRACT

The Capacitated Chinese Postman Problem (CCPP) is an important arc routing problem in which demands occurring on arcs of a network have to be serviced by vehicles of fixed capacity at minimal total cost. In this paper, we investigate the behavior of a matching-based lower bound for this problem and introduce a new bounding technique. We then turn to special classes of the CCPP that one can solve directly when suitable restrictions apply to the problem data and the network structure.

Key Words and Phrases:

• Network Optimization
• Vehicle Routing