Lower bounds and heuristics for the windy rural postman problem

DOI10.1016/j.ejor.2005.09.021zbMath1103.90095OpenAlexW2060202476MaRDI QIDQ852946

Daniele Vigo, Alessandro Carrotta, Angel Corberán, Enrique Benavent, José María Sanchis

Publication date: 15 November 2006

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2005.09.021

zbMATH Keywords

heuristicscutting planesroutingWindy Rural Postman Problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (16)

New heuristic algorithms for the windy rural postman problem ⋮ A hybrid heuristic procedure for the windy rural postman problem with zigzag time windows ⋮ A scatter search algorithm for time-dependent prize-collecting arc routing problems ⋮ The generalized arc routing problem ⋮ Plowing with precedence in polynomial time ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ New results on the windy postman problem ⋮ Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem ⋮ An Open-Source Desktop Application for Generating Arc-Routing Benchmark Instances ⋮ A branch-and-price algorithm for the windy rural postman problem ⋮ Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems ⋮ Min-Max K -vehicles windy rural postman problem ⋮ Recent results on Arc Routing Problems: An annotated bibliography ⋮ A metaheuristic for the min-max windy rural postman problem with K vehicles ⋮ Solving the close-enough arc routing problem ⋮ New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem

Cites Work

• On the windy postman problem
• On the windy postman problem on Eulerian graphs
• A cutting plane algorithm for the windy postman problem
• New inequalities for the general routing problem
• The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra
• Algorithms for the windy postman problem
• A polyhedral approach to the rural postman problem
• Modeling and solving several classes of arc routing problems as traveling salesman problems
• The general routing polyhedron: A unifying framework
• An algorithm for the Rural Postman problem on a directed graph
• The Chinese Postman Problem for Mixed Networks
• Odd Minimum Cut-Sets and b-Matchings
• Arc Routing Problems, Part II: The Rural Postman Problem
• A cutting plane algorithm for the general routing problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds and heuristics for the windy rural postman problem