The Profitable Close-Enough Arc Routing Problem. (April 2022)

• Record Type: Journal Article
• Authors: Bianchessi, Nicola; Corberán, Ángel; Plana, Isaac; Reula, Miguel; Sanchis, José M.
• Is Part Of: Computers & operations research. Volume 140(2022)
• Publication Date: 2022-04
• Subjects: Arc routing -- Close-enough -- Profits -- Branch and cut -- Polyhedra; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105653
• Languages: English
• ISSNs: 0305-0548

Abstract

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.