A MultiStart-VNS Algorithm for the Profitable Close-Enough Arc Routing Problem

M. Reula Martín, R. Marti

In this work we solve a practical variant of an arc routing problem. We target the close enough model in which clients can be served from relatively close arcs. This variant, known as the profitable close-enough arc routing problem, models real situations, such as inventory management or automated meter reading. We propose a heuristic based on the variable neighborhood search methodology to maximize the sum of profits of the clients served (penalized with the distance traveled). We present extensive experimentation over a benchmark of previously reported instances. Specifically, we first set the key search parameters of our method, and then compare it with the state-of-the-art heuristics for this problem. Our heuristic outperforms the previous algorithms published for this problem, as confirmed by the statistical analysis, which permits to draw significant conclusions.

Keywords: Arc routing Close-enough Profits Metaheuristic Logistics

I. Lozano Osorio, A. Oliva García, J. Sánchez-Oro Calvo

R. Martín Santamaría, T. Stuetzle, M. López Ibañez, J. M. Colmenar Verdugo

S. Salazar Cárdenas, J. M. Colmenar Verdugo, A. Abraham Duarte Muñoz

S. Gil Borrás, E. G. Pardo