Premium
Exact methods based on node‐routing formulations for undirected arc‐routing problems
Author(s) -
Baldacci R.,
Maniezzo V.
Publication year - 2006
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.20091
Subject(s) - arc routing , routing (electronic design automation) , arc (geometry) , node (physics) , transformation (genetics) , enhanced data rates for gsm evolution , vehicle routing problem , computer science , mathematics , mathematical optimization , combinatorics , algorithm , computer network , artificial intelligence , geometry , chemistry , physics , biochemistry , quantum mechanics , gene
This article proposes a new transformation of undirected arc‐routing problems into equivalent node‐routing problems, with emphasis on the transformation of Capacitated Arc Routing Problems (CARP) into Capacitated Vehicle Routing Problems (CVRP). For this last case, an analogue transformation has already been proposed in Pearn et al., where each required CARP edge is mapped onto a triplet of CVRP nodes. In our case, only two CVRP nodes are needed for every CARP required edge. The transformed instances have a structure and a dimension that make most CARP benchmarks solvable by state of the art CVRP techniques. We thus propose a general purpose transformation of arc into node‐routing problems and new results on lower bounds and exact methods for CARP instances. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 47(1), 52–60 2006