Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems

DOI10.1007/s10107-005-0643-yzbMath1099.90079OpenAlexW1994436719MaRDI QIDQ2494509

Isaac Plana, José María Sanchis, Angel Corberán

Publication date: 28 June 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0643-y

zbMATH Keywords

FacetsWindy Rural Postman ProblemArc RoutingMixed Rural Postman ProblemPolyhedral CombinatoricsWindy General Routing Problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (5)

A branch-and-cut algorithm for the maximum benefit Chinese postman problem ⋮ New results on the windy postman problem ⋮ Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem ⋮ Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm ⋮ Recent results on Arc Routing Problems: An annotated bibliography

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the windy postman problem
• Lower bounds and heuristics for the windy rural postman problem
• The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities
• A cutting plane algorithm for the windy postman problem
• New inequalities for the general routing problem
• On the mixed Chinese postman problem
• The mixed general routing polyhedron
• New heuristic algorithms for the windy rural postman problem
• A comparison of two different formulations for arc routing problems on mixed graphs
• The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra
• The traveling salesman problem on a graph and some related integer polyhedra
• An algorithm for the Rural Postman problem on a directed graph
• The Chinese Postman Problem for Mixed Networks
• The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities
• Arc Routing Problems, Part II: The Rural Postman Problem
• An optimal algorithm for the mixed Chinese postman problem
• New Results on the Mixed General Routing Problem

This page was built for publication: Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems