A polyhedral approach to the rural postman problem
From MaRDI portal
Publication:1342042
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
NP-hard; valid inequalities; facial structure; cutting-plane algorithm; rural postman; unbounded full-dimensional polyhedron
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 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 general routing polyhedron: A unifying framework, A heuristic for the periodic rural postman problem, Routing problems: A bibliography, 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
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