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. - (2022), pp. 1-15. [Epub ahead of print] [10.1016/j.ejor.2021.10.047]

The min-max close-enough arc routing problem

N. Bianchessi
Primo
;
2022

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.
Branch-and-cut; Branch-and-price; Close-enough arc routing problem; Min-max; Routing;
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
29-ott-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0377221721008961-main.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 1.11 MB
Formato Adobe PDF
1.11 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/884813
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact