On the Distance-Constrained Close Enough Arc Routing Problem
Mostra el registre complet de l'element
Visualització
(1.544Mb)
|
|
|
|
|
|
Corberán Salvador, Ángel; Plana Andani, Isaac; Reula Martín, Miguel; Sanchis Llopis, José María
|
|
Aquest document és un/a article, creat/da en: 2021
|
|
|
|
Arc routing problems consist basically of finding one or several routes traversing a given set of arcs and/or edges that must be serviced. The Close-Enough Arc Routing Problem, or Generalized Directed Rural Postman Problem, does not assume that customers are located at specific arcs, but can be serviced by traversing any arc of a given subset. Real-life applications include routing for meter reading, in which a vehicle equipped with a receiver travels a street network. If the vehicle gets within a certain distance of a meter, the receiver collects its data. Therefore, only a few streets which are close enough to the meters need to be traversed. In this paper we study the generalization of this problem to the case in which a fleet of vehicles is available. This problem, the Distance-Constrained Close Enough Arc Routing Problem, consists of finding a set of routes with minimum total cost such that their length does not exceed a maximum distance.
In this article, we propose a new formulation for the Distance-Constrained Close Enough Arc Routing Problem and present some families of valid inequalities that we use in a branch-and-cut algorithm for its solution. Extensive computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with other heuristic and exact methods.
|
|
Veure al catàleg Trobes
|
|
|
Aquest element apareix en la col·lecció o col·leccions següent(s)
Mostra el registre complet de l'element