Retour aux résultats
Articles (2016), Computers & Operations Research, 66, pp. 95-104

A branch-and-cut algorithm for the Orienteering Arc Routing Problem

ARCHETTI Claudia , Corberán Ángel, Plana Isaac, Sanchis José M., Speranza M. Grazia

In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP), in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route. In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds a heuristic solution to the OARP on the basis of the information provided by the solution of the linear relaxation. Extensive computational experiments over different sets of OARP instances show that the exact algorithm is capable of solving to optimality large instances, with up to 2000 vertices and 14,000 arcs, within 1 h and often within a few minutes. Lien vers l'article

ARCHETTI, C., CORBERÁN, , PLANA, I., SANCHIS, J.M. and SPERANZA, M.G. (2016). A branch-and-cut algorithm for the Orienteering Arc Routing Problem. Computers & Operations Research, 66, pp. 95-104.

Mots clés : #Orienteering-Arc-Routing-Problem, #Routing-problems-with-profits, #Branch, #and, #cut