Premium
Eulerian location problems
Author(s) -
Ghiani Gianpaolo,
Laporte Gilbert
Publication year - 1999
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/(sici)1097-0037(199912)34:4<291::aid-net9>3.0.co;2-4
Subject(s) - arc routing , context (archaeology) , computer science , mathematical optimization , relaxation (psychology) , set (abstract data type) , eulerian path , arc (geometry) , routing (electronic design automation) , lagrangian relaxation , mathematics , algorithm , lagrangian , geography , psychology , computer network , social psychology , geometry , archaeology , programming language
The problem of locating a set of depots in an arc routing context (with no side constraints) is addressed. In the case of one depot, it is shown that the problem can be transformed into a Rural Postman Problem (RPP). In the case of a set of depots, the problem is also reduced to an RPP if there are no bounds on the number of depots to be opened or to a RPP relaxation otherwise. The problem is then solved to optimality using a branch‐and‐cut algorithm. Extensive computational results on real‐world and on some randomly generated test networks are reported. © 1999 John Wiley & Sons, Inc. Networks 34: 291–302, 1999