Here we introduce the Min-Max Close-Enough Arc Routing Problem, where a fleet of vehicles must serve a set of customers while trying to balance the length of the routes. The vehicles do not need to visit the customers, since they can serve them from a distance by traversing arcs that are “close enough” to the customers. We present two formulations of the problem and propose a branch-and-cut and a branch-and-price algorithm based on the respective formulations. A heuristic algorithm used to provide good upper bounds to the exact procedures is also presented. Extensive computational experiments to compare the performance of the algorithms are carried out.

The min-max close-enough arc routing problem / N. Bianchessi, A. Corberan, I. Plana, M. Reula, J.M. Sanchis. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 300:3(2022), pp. 837-851. [10.1016/j.ejor.2021.10.047]

### The min-max close-enough arc routing problem

#### Abstract

Here we introduce the Min-Max Close-Enough Arc Routing Problem, where a fleet of vehicles must serve a set of customers while trying to balance the length of the routes. The vehicles do not need to visit the customers, since they can serve them from a distance by traversing arcs that are “close enough” to the customers. We present two formulations of the problem and propose a branch-and-cut and a branch-and-price algorithm based on the respective formulations. A heuristic algorithm used to provide good upper bounds to the exact procedures is also presented. Extensive computational experiments to compare the performance of the algorithms are carried out.
##### Scheda breve Scheda completa Scheda completa (DC)
Branch-and-cut; Branch-and-price; Close-enough arc routing problem; Min-max; Routing;
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
2022
29-ott-2021
Article (author)
File in questo prodotto:
File
1-s2.0-S0377221721008961-main.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 1.14 MB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/2434/884813`