A branch-and-cut algorithm for the maximum benefit Chinese postman problem

DOI10.1007/s10107-011-0507-6zbMath1295.90108OpenAlexW1997409263MaRDI QIDQ378087

Antonio M. Rodríguez-Chía, Isaac Plana, José María Sanchis, Angel Corberán

Publication date: 11 November 2013

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-011-0507-6

zbMATH Keywords

rural postman problembranch-and-cutfacetsChinese postman problemmaximum benefit Chinese postman problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (12)

A branch-and-cut algorithm for the profitable windy rural postman problem ⋮ Polyhedral analysis and a new algorithm for the length constrained \(K\)-drones rural postman problem ⋮ Multi-depot rural postman problems ⋮ The profitable close-enough arc routing problem ⋮ Upgrading edges in the graphical TSP ⋮ The generalized arc routing problem ⋮ Arc routing problems: A review of the past, present, and future ⋮ The multi‐purpose K‐drones general routing problem ⋮ The periodic rural postman problem with irregular services on mixed graphs ⋮ Hierarchical Chinese postman problem with fuzzy travel times ⋮ The directed profitable rural postman problem with incompatibility constraints ⋮ City streets parking enforcement inspection decisions: the Chinese postman's perspective

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• The undirected capacitated arc routing problem with profits
• Solving the prize-collecting rural postman problem
• On the cycle polytope of a binary matroid
• The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem
• A polyhedral approach to the rural postman problem
• A branch-and-cut algorithm for the undirected rural postman problem
• Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems
• Privatized rural postman problems
• Odd Minimum Cut Sets and b-Matchings Revisited
• On general routing problems
• A fundamental problem in vehicle routing
• A branch & cut algorithm for the windy general routing problem and special cases
• Transformation of Facets of the General Routing Problem Polytope
• Approximate solutions for the maximum benefit chinese postman problem
• A cutting plane algorithm for the general routing problem

This page was built for publication: A branch-and-cut algorithm for the maximum benefit Chinese postman problem