The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm

DOI10.1016/J.EJOR.2016.07.026MaRDI QIDQ1752763zbMATH OpenOpenAlexFDO

Authors Marco Colombi, Renata Mansini, Isaac Plana, Ángel Corberán, José M. Sanchis

Publication date 24 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2016.07.026

zbMATH Keywords

branch-and-cuthierarchical routing problemsmixed rural postman problempolyhedral analysis

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A polyhedral approach to the rural postman problem
• A branch-and-cut algorithm for the undirected rural postman problem
• Heuristics for the mixed rural postman problem
• The time-dependent rural postman problem: polyhedral results
• A branch-and-bound algorithm for the time-dependent rural postman problem
• A note on the undirected rural postman problem polytope
• The Rural Postman Problem on mixed graphs with turn penalties
• Approximation algorithms for the min-max mixed rural postmen cover problem and its variants
• A branch-and-cut algorithm for the profitable windy rural postman problem
• On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation

Cites work

• A branch & cut algorithm for the windy general routing problem and special cases
• A branch-and-cut algorithm for the undirected rural postman problem
• An algorithm for the hierarchical Chinese postman problem
• Arc Routing
• scientific article; zbMATH DE number 1568941 (Why is no real title available?)
• scientific article; zbMATH DE number 6741960 (Why is no real title available?)
• Integer Programming and Combinatorial Optimization
• New Results on the Mixed General Routing Problem
• Odd Minimum Cut-Sets and b-Matchings
• On the hierarchical Chinese postman problem with linear ordered classes
• Postman tour on a graph with precedence relation on arcs
• Solving matching problems with linear programming
• Solving the hierarchical Chinese postman problem as a rural postman problem.
• The mixed general routing polyhedron
• The rural postman problem with deadline classes
• The stacker crane problem and the directed general routing problem
• The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra

Cited in

(16)

• A polyhedral approach to the rural postman problem
• Solving the hierarchical Chinese postman problem as a rural postman problem.
• The periodic rural postman problem with irregular services on mixed graphs
• The directed profitable rural postman problem with incompatibility constraints
• The target visitation arc routing problem
• The hierarchical Chinese postman problem: the slightest disorder makes it hard, yet disconnectedness is manageable
• A branch-price-and-cut algorithm for the min-max k-vehicle windy rural postman problem
• New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem
• Hierarchical Chinese postman problem with fuzzy travel times
• Variants of the mixed postman problem solvable using linear programming
• The Rural Postman Problem on mixed graphs with turn penalties
• A two-phase hybrid algorithm for the periodic rural postman problem with irregular services on mixed graphs
• An updated annotated bibliography on arc routing problems
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem
• Approximation algorithms for two clustered arc routing problems
• On the hierarchical directed capacitated arc routing problem

This page was built for publication: The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm

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