On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation

DOI10.1287/OPRE.51.2.281.12790zbMATH Open1163.90709OpenAlexW2148447953MaRDI QIDQ3635191FDOQ3635191

Authors: Elena Fernández, Oscar Meza, Robert Garfinkel, Maruja Ortega 

Publication date: 5 July 2009

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/288d6f93a552a90996f9d16cd35f40aeb3fd10cf

Recommendations

• On crossings, the crossing postman problem, and the rural postman problem
• A branch-and-cut algorithm for the undirected rural postman problem
• A polyhedral approach to the rural postman problem
• Algorithms for the rural postman problem
• An algorithm for the Rural Postman problem on a directed graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Traffic problems in operations research (90B20)

Cited In (20)

• A constructive heuristic for the undirected rural postman problem
• Multi-depot rural postman problems
• The hierarchical mixed rural postman problem: polyhedral analysis and a branch-and-cut algorithm
• New results for the directed profitable rural postman problem
• A new view on rural postman based on Eulerian extension and matching
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• Solving the prize-collecting rural postman problem
• Reoptimizing the rural postman problem
• Recent results on arc routing problems: an annotated bibliography
• A polyhedral approach to the rural postman problem
• A partitioning column approach for solving LED sorter manipulator path planning problems
• On \((1+\varepsilon)\)-approximate data reduction for the Rural Postman problem
• Improving a constructive heuristic for the general routing problem
• Undirected postman problems with zigzagging option: a cutting-plane approach
• A heuristic for the periodic rural postman problem
• Privatized rural postman problems
• On crossings, the crossing postman problem, and the rural postman problem
• A Generalized Traveling Salesman Problem Approach to the Directed Clustered Rural Postman Problem
• A note on the undirected rural postman problem polytope
• Theoretical and computational analysis of a new formulation for the rural postman problem and the general routing problem

This page was built for publication: On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation

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