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.
|Number of pages||26|
|Journal||American Journal of Mathematical and Management Sciences|
|State||Published - 1 Jan 1987|
- Network Optimization
- Vehicle Routing