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

DOI10.1007/S10107-011-0507-6MaRDI QIDQ378087zbMATH OpenOpenAlexFDO

Authors Isaac Plana, Antonio M. Rodríguez-Chía, Ángel Corberán, José M. Sanchis

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

Chinese postman problembranch-and-cutfacetsrural postman problemmaximum benefit Chinese postman problem

Mathematics Subject Classification ID

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

Recommendations

• An improved heuristic algorithm for the maximum benefit Chinese postman problem
• The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem
• Approximate solutions for the maximum benefit chinese postman problem
• A branch-and-cut algorithm for the undirected rural postman problem
• An optimal algorithm for the mixed Chinese postman problem

Cites work

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

Cited in

(18)

• The periodic rural postman problem with irregular services on mixed graphs
• Polyhedral analysis and a new algorithm for the length constrained \(K\)-drones rural postman problem
• The generalized arc routing problem
• Theoretical and computational analysis of a new formulation for the rural postman problem and the general routing problem
• Upgrading edges in the graphical TSP
• The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem
• The multi‐purpose K‐drones general routing problem
• The profitable close-enough arc routing problem
• Hierarchical Chinese postman problem with fuzzy travel times
• Multi-depot rural postman problems
• An updated annotated bibliography on arc routing problems
• Approximate solutions for the maximum benefit chinese postman problem
• City streets parking enforcement inspection decisions: the Chinese postman's perspective
• A branch-and-cut algorithm for the profitable windy rural postman problem
• Arc routing problems: A review of the past, present, and future
• The directed profitable rural postman problem with incompatibility constraints
• An improved heuristic algorithm for the maximum benefit Chinese postman problem
• Undirected postman problems with zigzagging option: a cutting-plane approach

Describes a project that uses

Uses Software

• CPLEX

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

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