On the Orienteering Arc Routing Problem

Autores UPV
CONGRESO On the Orienteering Arc Routing Problem


In the Orienteering Arc Routing Problem (OARP), in addition to a possible set of regular customers that have to be serviced, another set of potential customers is available. Each customer is associated with an arc of a directed graph. Each potential customer has a profit that is collected when it is serviced, that is, when the associated arc is traversed. The objective is to identify the customers which maximize the total profit collected. In this paper we propose a formulation for this problem and study a relaxation of its associated polyhedron. We present some families of valid and facet-inducing inequalities that we use in the implementation of a branchand- cut algorithm for the resolution of the problem. Computational experiments are run on a large set of benchmark instances.