An algorithm for the Rural Postman problem on a directed graph

DOI10.1007/BFB0121091zbMath0596.90097OpenAlexW74564317MaRDI QIDQ3730368

Enrique Mota, Angel Corberán, Vicente Campos, Nicos Christofides

Publication date: 1986

Published in: Mathematical Programming Studies (Search for Journal in Brave)

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

zbMATH Keywords

Lagrangian relaxationbranch and boundNP-completenessdirected graphminimum cost flowarc routingtree searchComputational resultsasymmetric travelling salesmanDirected Rural Postman Problemshortest arborescencetwo stage heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Numerical mathematical programming methods (65K05) Deterministic network models in operations research (90B10)

Related Items (36)

The target visitation arc routing problem ⋮ New results for the directed profitable rural postman problem ⋮ A polyhedral approach to the rural postman problem ⋮ A branch & cut algorithm for the windy general routing problem and special cases ⋮ Integer programming formulation and polyhedral results for windy collaborative arc routing problem ⋮ A branch-and-cut algorithm for the profitable windy rural postman problem ⋮ Lower bounds and heuristics for the windy rural postman problem ⋮ New heuristic algorithms for the windy rural postman problem ⋮ On the collaboration uncapacitated arc routing problem ⋮ Algorithms for the rural postman problem ⋮ Routing problems: A bibliography ⋮ Modeling and solving several classes of arc routing problems as traveling salesman problems ⋮ An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem ⋮ Multi-depot rural postman problems ⋮ A partitioning column approach for solving LED sorter manipulator path planning problems ⋮ A new view on rural postman based on Eulerian extension and matching ⋮ The generalized arc routing problem ⋮ An ILP-refined tabu search for the directed profitable rural postman problem ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ A branch-and-price algorithm for the windy rural postman problem ⋮ On path-bridge inequalities for the orienteering arc routing problems ⋮ A two-stage solution approach for the directed rural postman problem with turn penalties ⋮ The windy rural postman problem with a time-dependent zigzag option ⋮ Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity ⋮ Approximating Shortest Superstring Problem Using de Bruijn Graphs ⋮ A note on the undirected rural postman problem polytope ⋮ Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems ⋮ Min-Max K -vehicles windy rural postman problem ⋮ A metaheuristic for the min-max windy rural postman problem with K vehicles ⋮ The directed profitable location rural postman problem ⋮ A computational study of several heuristics for the DRPP ⋮ Solving the close-enough arc routing problem ⋮ Transforming arc routing into node routing problems ⋮ Uncertain multi-objective Chinese postman problem ⋮ The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra ⋮ The arc partitioning problem

This page was built for publication: An algorithm for the Rural Postman problem on a directed graph