6533b7dafe1ef96bd126f646

RESEARCH PRODUCT

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

Isaac PlanaJosé M. SanchisClaudia ArchettiM. Grazia SperanzaÁNgel Corberán

subject

Mathematical optimization021103 operations researchGeneral Computer Science0211 other engineering and technologiesOrienteering02 engineering and technologyManagement Science and Operations ResearchTime limitRouting problems with profitsPolyhedronExact algorithmOrienteering Arc Routing ProblemBranch-and-cutModeling and Simulation0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingDestination-Sequenced Distance Vector routingMATEMATICA APLICADAInteger programmingArc routingAlgorithmBranch and cutMathematics

description

[EN] 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.

yearjournalcountryeditionlanguage
2016-02-01Computers & Operations Research
https://doi.org/10.1016/j.cor.2015.08.003