An algorithm for the Rural Postman problem on a directed graph

DOI10.1007/BFB0121091MaRDI QIDQ3730368zbMATH OpenOpenAlexFDO

Authors Vicente Campos, Ángel Corberán, Enrique Mota, 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

arc routingasymmetric travelling salesmanbranch and boundComputational resultsdirected graphDirected Rural Postman ProblemLagrangian relaxationminimum cost flowNP-completenessshortest arborescencetree searchtwo stage heuristic

Mathematics Subject Classification ID

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

Recommendations

• A computational study of several heuristics for the DRPP
• Algorithms for the rural postman problem
• The rural postman problem on directed, mixed, and windy graphs
• The Directed Rural Postman Problem with Turn Penalties
• Rural postman parameterized by the number of components of required edges

Cited in

(47)

• The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra
• A polyhedral approach to the rural postman problem
• Modeling and solving several classes of arc routing problems as traveling salesman problems
• A heuristic algorithm based on Monte Carlo methods for the rural postman problem.
• The generalized arc routing problem
• The windy rural postman problem with a time-dependent zigzag option
• Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity
• A computational study of several heuristics for the DRPP
• Transforming arc routing into node routing problems
• A heuristic for the periodic rural postman problem
• Algorithms for the rural postman problem
• Routing problems: A bibliography
• A new view on rural postman based on Eulerian extension and matching
• A two-stage solution approach for the directed rural postman problem with turn penalties
• The target visitation arc routing problem
• Integer programming formulation and polyhedral results for windy collaborative arc routing problem
• New heuristic algorithms for the windy rural postman problem
• Multi-depot rural postman problems
• Solving SCS for bounded length strings in fewer than \(2^n\) steps
• A note on the undirected rural postman problem polytope
• Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems
• The directed profitable location rural postman problem
• A partitioning column approach for solving LED sorter manipulator path planning problems
• Solving the close-enough arc routing problem
• New results for the directed profitable rural postman problem
• Min-Max K-vehicles windy rural postman problem
• Rural postman parameterized by the number of components of required edges
• A branch-and-cut algorithm for the profitable windy rural postman problem
• On the collaboration uncapacitated arc routing problem
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation
• An ILP-refined tabu search for the directed profitable rural postman problem
• A Generalized Traveling Salesman Problem Approach to the Directed Clustered Rural Postman Problem
• scientific article; zbMATH DE number 861418 (Why is no real title available?)
• Approximating shortest superstring problem using de Bruijn graphs
• The Directed Rural Postman Problem with Turn Penalties
• On path-bridge inequalities for the orienteering arc routing problems
• The rural postman problem on directed, mixed, and windy graphs
• A branch & cut algorithm for the windy general routing problem and special cases
• A branch-and-price algorithm for the windy rural postman problem
• The Rural Postman Problem on mixed graphs with turn penalties
• A heuristic algorithm for the drone rural postman problem
• A branch-and-cut algorithm for the windy profitable location rural postman problem
• Uncertain multi-objective Chinese postman problem
• The arc partitioning problem
• Lower bounds and heuristics for the windy rural postman problem
• A metaheuristic for the min-max windy rural postman problem with K vehicles

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

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