In this article, we deal with the Profitable Close-Enough Arc Routing Problem (PCEARP), which is an extension of the Close-Enough ARP (CEARP). The CEARP models the situation in which customers are not necessarily nodes of a network and the associated serviced can be performed from any traversed edge that is close enough to the customer. It consists of finding a minimum cost tour that services all the customers. In the PCEARP, a profit is associated with each customer and it is collected (only once) when the customer is serviced. The goal is to find a tour maximizing the difference between the total profit collected and the travel distance. A formulation for this new problem and some valid inequalities are presented, and a polyhedral study of its feasible solutions is conducted. We propose a heuristic and a branch-and-cut procedure for solving the PCEARP, and their performance has been tested on several sets of instances with different characteristics.

The Profitable Close Enough Arc Routing Problem / N. Bianchessi, Á. Corberán, I. Plana, M. Reula, J.M. Sanchis. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 140:(2022), pp. 105653.1-105653.14. [10.1016/j.cor.2021.105653]

The Profitable Close Enough Arc Routing Problem

N. Bianchessi
Primo
;
2022

Abstract

In this article, we deal with the Profitable Close-Enough Arc Routing Problem (PCEARP), which is an extension of the Close-Enough ARP (CEARP). The CEARP models the situation in which customers are not necessarily nodes of a network and the associated serviced can be performed from any traversed edge that is close enough to the customer. It consists of finding a minimum cost tour that services all the customers. In the PCEARP, a profit is associated with each customer and it is collected (only once) when the customer is serviced. The goal is to find a tour maximizing the difference between the total profit collected and the travel distance. A formulation for this new problem and some valid inequalities are presented, and a polyhedral study of its feasible solutions is conducted. We propose a heuristic and a branch-and-cut procedure for solving the PCEARP, and their performance has been tested on several sets of instances with different characteristics.
Arc Routing; Close-Enough; profits; branch and cut; polyhedra
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
PCEARP_Revised-POSTPRINT.pdf

embargo fino al 04/12/2024

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 433.41 kB
Formato Adobe PDF
433.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
1-s2.0-S0305054821003567-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 931.13 kB
Formato Adobe PDF
931.13 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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: https://hdl.handle.net/2434/887462
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact