The capacitated chinese postman problem: Lower bounds and solvable Cases

Arjang A. Assad, W.l. Pearn, Bruce L. Golden

Research output: Contribution to journalArticlepeer-review

34 Scopus citations

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.

Original languageEnglish
Pages (from-to)63-88
Number of pages26
JournalAmerican Journal of Mathematical and Management Sciences
Volume7
Issue number1-2
DOIs
StatePublished - 1 Jan 1987

Keywords

  • Network Optimization
  • Vehicle Routing

Fingerprint Dive into the research topics of 'The capacitated chinese postman problem: Lower bounds and solvable Cases'. Together they form a unique fingerprint.

Cite this