Premium
Solving the close‐enough arc routing problem
Author(s) -
Hà Minh Hoàng,
Bostel Nathalie,
Langevin André,
Rousseau LouisMartin
Publication year - 2014
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.21525
Subject(s) - arc routing , computer science , routing (electronic design automation) , arc (geometry) , mathematical optimization , mathematics , computer network , geometry
The close‐enough arc routing problem has an interesting real‐life application to routing for meter reading. In this article, we propose a new mathematical formulation for this problem. We analyze our formulation and compare it with two formulations in the literature. We also develop branch‐and‐cut algorithms to solve the problem to optimality. We present computational results for instances based on three types of graphs: directed, undirected, and mixed. Copyright © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(1),107–118 2014