A polyhedral approach to the rural postman problem

DOI10.1016/0377-2217(94)90398-0zbMath0819.90119MaRDI QIDQ1342042

Angel Corberán, José María Sanchis

Publication date: 11 January 1995

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

Full work available at URL: https://doi.org/10.1016/0377-2217(94)90398-0

zbMATH Keywords

NP-hard; valid inequalities; facial structure; cutting-plane algorithm; rural postman; unbounded full-dimensional polyhedron

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90C10: Integer programming

90B06: Transportation, logistics and supply chain management

Related Items

Heuristics for single-pass welding task sequencing, Unnamed Item, A branch-and-price algorithm for the windy rural postman problem, A branch-and-cut algorithm for the profitable windy rural postman problem, A branch-and-cut algorithm for the orienteering arc routing problem, On the collaboration uncapacitated arc routing problem, A branch-and-cut algorithm for the maximum benefit Chinese postman problem, Lower bounds and heuristics for the windy rural postman problem, Undirected postman problems with zigzagging option: a cutting-plane approach, Solving the prize-collecting rural postman problem, New inequalities for the general routing problem, The rural postman problem with deadline classes, The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra, A heuristic algorithm based on Monte Carlo methods for the rural postman problem., Solving the hierarchical Chinese postman problem as a rural postman problem., The generalized arc routing problem, The periodic rural postman problem with irregular services on mixed graphs, The general routing polyhedron: A unifying framework, A heuristic for the periodic rural postman problem, Routing problems: A bibliography, On the distance-constrained close enough arc routing problem, Multi-depot rural postman problems, On the general routing polytope, Computing finest mincut partitions of a graph and application to routing problems, A tabu search algorithm for the Min-Max \(k\)-Chinese postman problem, A constructive heuristic for the undirected rural postman problem, The directed profitable location rural postman problem, The capacitated arc routing problem with intermediate facilities

Uses Software

• LINDO

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• A new class of cutting planes for the symmetric travelling salesman problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• The capacitated arc routing problem: Valid inequalities and facets
• The traveling salesman problem on a graph and some related integer polyhedra
• An algorithm for the Rural Postman problem on a directed graph
• On the symmetric travelling salesman problem: Solution of a 120-city problem
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• On general routing problems
• A fundamental problem in vehicle routing
• Approximation Algorithms for Some Postman Problems
• Matching, Euler tours and the Chinese postman