Premium
A branch & cut algorithm for the windy general routing problem and special cases
Author(s) -
Corberán Angel,
Plana Isaac,
Sanchis José M.
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20176
Subject(s) - arc routing , polyhedron , routing (electronic design automation) , branch and cut , cutting plane method , mathematical optimization , plane (geometry) , vehicle routing problem , computer science , mathematics , algorithm , travelling salesman problem , integer programming , combinatorics , geometry , computer network
In this paper, we present an exact algorithm for the Windy General Routing Problem. This problem generalizes many important Arc Routing Problems and also has some interesting real‐life applications. The Branch & Cut method presented here is based on a cutting‐plane algorithm that identifies violated inequalities of several classes of facet‐inducing inequalities for the corresponding polyhedron. The whole procedure has been tested over different sets of instances and is capable of solving to optimality large‐size instances of several routing problems defined on undirected, mixed, and windy graphs. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 49(4), 245–257 2007