A branch-and-cut algorithm for the maximum benefit Chinese postman problem
This article studies a variation of the undirected Chinese Postman Problem which considers several benefits associated with each edge. The objective function of the problem is to find a closed walk which maximize the total benefit. The article begins with an overview of the literature associated with this problem and the mathematical formulation of the maximum benefit Chinese postman problem which is in the form of an integer program. The authors then study the associated polyhedron defined by the inequalities and several types of valid inequalities are derived and proven. A branch-and-cut algorithm is then described and the separation algorithms for the proposed cuts are provided. The article concludes with the results of the numerical experimentation which was performed using the CPLEX optimizer on test instances generated by the authors.
- 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
- 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
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- 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
- The maximum benefit Chinese postman problem and the maximum benefit traveling salesman problem
- 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
- A branch-and-cut algorithm for the profitable windy rural postman problem
- Hierarchical Chinese postman problem with fuzzy travel times
- An improved heuristic algorithm for the maximum benefit Chinese postman problem
- Approximate solutions for the maximum benefit chinese postman problem
- Upgrading edges in the graphical TSP
- Arc routing problems: A review of the past, present, and future
- The multi‐purpose K‐drones general routing problem
- An updated annotated bibliography on arc routing problems
- Theoretical and computational analysis of a new formulation for the rural postman problem and the general routing problem
- The multidepot drone general routing problem with duration and capacity constraints
- The min max multi-trip drone location arc routing problem
- City streets parking enforcement inspection decisions: the Chinese postman's perspective
- Undirected postman problems with zigzagging option: a cutting-plane approach
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)
