A branch-and-cut algorithm for the undirected rural postman problem

DOI10.1007/s101070050007zbMath0987.90091OpenAlexW2053944393MaRDI QIDQ1575070

Gilbert Laporte, Gianpaolo Ghiani

Publication date: 14 August 2000

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

Full work available at URL: https://doi.org/10.1007/s101070050007

zbMATH Keywords

branch-and-cutfacetsarc routing problemspolyhedral analysisundirected rural postman problem

Mathematics Subject Classification ID

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

Related Items (32)

A heuristic for the periodic rural postman problem ⋮ The capacitated arc routing problem with refill points ⋮ Polyhedral analysis and a new algorithm for the length constrained \(K\)-drones rural postman problem ⋮ Modeling and Solving the Intersection Inspection Rural Postman Problem ⋮ Multi-depot rural postman problems ⋮ A branch-and-cut algorithm for the maximum benefit Chinese postman problem ⋮ A new view on rural postman based on Eulerian extension and matching ⋮ Solving the Periodic Edge Routing Problem in the Municipal Waste Collection ⋮ Upgrading edges in the graphical TSP ⋮ The generalized arc routing problem ⋮ A Branch-and-Cut method for the Capacitated Location-Routing Problem ⋮ Improving a constructive heuristic for the general routing problem ⋮ The multi‐purpose K‐drones general routing problem ⋮ Solving the hierarchical Chinese postman problem as a rural postman problem. ⋮ Undirected postman problems with zigzagging option: a cutting-plane approach ⋮ A branch-and-price algorithm for the windy rural postman problem ⋮ The capacitated arc routing problem with intermediate facilities ⋮ The periodic rural postman problem with irregular services on mixed graphs ⋮ On the general routing polytope ⋮ Computing finest mincut partitions of a graph and application to routing problems ⋮ The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm ⋮ The Steiner traveling salesman problem and its extensions ⋮ A note on the undirected rural postman problem polytope ⋮ Privatized rural postman problems ⋮ A constructive heuristic for the undirected rural postman problem ⋮ Min-Max K -vehicles windy rural postman problem ⋮ Recent results on Arc Routing Problems: An annotated bibliography ⋮ Solving the length constrained \(K\)-drones rural postman problem ⋮ Solving the close-enough arc routing problem ⋮ Solving the prize-collecting rural postman problem ⋮ An integer programming approach for the Chinese postman problem with time-dependent travel time ⋮ The time-dependent rural postman problem: polyhedral results

This page was built for publication: A branch-and-cut algorithm for the undirected rural postman problem