A polyhedral approach to the rural postman problem

DOI10.1016/0377-2217(94)90398-0zbMath0819.90119OpenAlexW2072370153MaRDI 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-hardvalid inequalitiesfacial structurecutting-plane algorithmrural postmanunbounded full-dimensional polyhedron

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Transportation, logistics and supply chain management (90B06)

Related Items (33)

A heuristic for the periodic rural postman problem ⋮ 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 ⋮ A branch-and-cut algorithm for the orienteering arc routing problem ⋮ On the collaboration uncapacitated arc routing problem ⋮ Routing problems: A bibliography ⋮ Polyhedral analysis and a new algorithm for the length constrained \(K\)-drones rural postman problem ⋮ Eulerian location problems ⋮ Multi-depot rural postman problems ⋮ A branch-and-cut algorithm for the maximum benefit Chinese postman problem ⋮ The profitable close-enough arc routing problem ⋮ A partitioning column approach for solving LED sorter manipulator path planning problems ⋮ The generalized arc routing problem ⋮ Improving a constructive heuristic for the general routing problem ⋮ A heuristic algorithm based on Monte Carlo methods for the rural postman problem. ⋮ Solving the hierarchical Chinese postman problem as a rural postman problem. ⋮ Undirected postman problems with zigzagging option: a cutting-plane approach ⋮ A branch-and-price algorithm for the windy rural postman problem ⋮ The capacitated arc routing problem with intermediate facilities ⋮ The periodic rural postman problem with irregular services on mixed graphs ⋮ 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 ⋮ On the distance-constrained close enough arc routing problem ⋮ The directed profitable location rural postman problem ⋮ The general routing polyhedron: A unifying framework ⋮ Heuristics for single-pass welding task sequencing ⋮ New inequalities for the general routing problem ⋮ Solving the prize-collecting rural postman problem ⋮ The rural postman problem with deadline classes ⋮ The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra

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

This page was built for publication: A polyhedral approach to the rural postman problem