The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases

DOI10.1080/01966324.1987.10737208zbMATH Open0623.90083OpenAlexW2021646400WikidataQ58116978 ScholiaQ58116978MaRDI QIDQ3762097FDOQ3762097

Arjang A. Assad, Bruce Golden, Wen Lea Pearn

Publication date: 1987

Published in: American Journal of Mathematical and Management Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/01966324.1987.10737208

zbMATH Keywords

NP-hardvehicle routingCapacitated Chinese Postman Problemmatching- based lower bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Cites Work

• Matching, Euler tours and the Chinese postman
• Capacitated arc routing problems
• Networks and vehicle routing for municipal waste collection
• A parallel insert method for the capacitated arc routing problem

Cited In (21)

• Augment-insert algorithms for the capacitated arc routing problem
• New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem
• The \(k\)-centrum Chinese postman delivery problem and a related cost allocation game
• New lower bound for the capacitated arc routing problem
• Min-Max K -vehicles windy rural postman problem
• A survey of models and algorithms for winter road maintenance. IV: Vehicle routing and fleet sizing for plowing and snow disposal
• Solvable cases of the \(k\)-person Chinese postman problem
• A metaheuristic for the min-max windy rural postman problem with K vehicles
• GRASP with evolutionary path-relinking for the capacitated arc routing problem
• The open capacitated arc routing problem
• Approximate solutions for the maximum benefit chinese postman problem
• Title not available (Why is that?)
• Approximate solutions for the capacitated arc routing problem
• A capacitated general routing problem on mixed networks
• Routing problems: A bibliography
• Improved lower bounds and exact algorithm for the capacitated arc routing problem
• The arc partitioning problem
• Routeing winter gritting vehicles
• A cutting plane algorithm for the capacitated arc routing problem
• Transforming arc routing into node routing problems
• Solving capacitated arc routing problems using a transformation to the CVRP

   Recommendations

• Title not available (Why is that?) 👍 👎
• Solvable cases of the \(k\)-person Chinese postman problem 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The Capacitated Canadian Postman Problem 👍 👎

This page was built for publication: The Capacitated Chinese Postman Problem: Lower Bounds and Solvable Cases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3762097)