EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2236. The Covering Arc Routing Problem
Invited abstract in session TB-64: Arc Routing, stream VeRoLog - Vehicle Routing and Logistics.
Tuesday, 10:30-12:00Room: S16 (building: 101)
Authors (first author is the speaker)
| 1. | Isaac Plana
|
| Matemáticas para la Economía y la Empresa, University of Valencia | |
| 2. | Mercedes Landete
|
| Departamento de Estadística y Matemática Aplicada, University Miguel Hernández of Elche | |
| 3. | Juanjo Peiró
|
| Estadística i Investigació Operativa, Universitat de València | |
| 4. | Jose Maria Sanchis
|
| Departamento de Matematica Aplicada, Universidad Politecnica de Valencia |
Abstract
Transporting valuable or dangerous goods may require constant surveillance to prevent potential thefts or incidents. Such supervision can be carried out by installing cameras or hiring security guards, which entails a monetary investment. In this work, we introduce the Covering Arc Routing Problem (CovARP), that combines arc routing and location problems. Let us consider an undirected graph with a cost associated with the traversal of each edge and a subset of edges (required edges) that must be traversed to perform some kind of service. Additionally, there is a set of potential monitors that can be activated or not. Each monitor has an activation cost and covers a certain set of edges if it is activated. The CovARP consists of both finding a closed path (tour) that traverses all the required edges at least once and determining a set of monitors that should be activated, so that all the edges traversed by the tour are covered by at least one active monitor, while minimizing the sum of the tour cost and the activation cost of the monitors. We present an integer linear formulation for this problem and a branch-and-cut algorithm. This algorithm has been tested on a randomly generated set of instances. We have analyzed three different situations: when the activation cost of the monitors is clearly higher than that of the tour, when the cost of the tour outweighs the activation cost of the monitors, and the balanced case in which both costs are comparable.
Keywords
- Vehicle Routing
- Location
- Branch and Cut
Status: accepted
Back to the list of papers