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

DOI10.1007/s10107-011-0507-6zbMath1295.90108MaRDI 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 problem; branch-and-cut; facets; Chinese postman problem; maximum benefit Chinese postman problem

Mathematics Subject Classification ID

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

90C27: Combinatorial optimization

Related Items

Hierarchical Chinese postman problem with fuzzy travel times, Upgrading edges in the graphical TSP, A branch-and-cut algorithm for the profitable windy rural postman problem, City streets parking enforcement inspection decisions: the Chinese postman's perspective, The generalized arc routing problem, The periodic rural postman problem with irregular services on mixed graphs, The directed profitable rural postman problem with incompatibility constraints, 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

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