The Team Orienteering Arc Routing Problem

• Published in: Transportation science 2014-08, Vol.48 (3), p.442-457
• Main Authors: Archetti, Claudia, Speranza, M. Grazia, Corberán, Ángel, Sanchis, José M., Plana, Isaac
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; Benchmarking; Branch & bound algorithms; branch and cut; Computational methods; Customers; facets; Heuristics; Inequality constraints; Integers; Motor vehicle fleets; multivehicle; Orienteering; Polyhedrons; Profit; profits; Public transportation; Routing; Studies; Tall tales; team orienteering arc routing problem; Travel; Variable coefficients; Vehicles; Vertices
• ISSN: 0041-1655; 1526-5447
• DOI: 10.1287/trsc.2013.0484

The team orienteering arc routing problem (TOARP) is the extension to the arc routing setting of the team orienteering problem. In the TOARP, 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. A fleet of vehicles with a given maximum traveling time is available. The profit from a customer can be collected by one vehicle at most. The objective is to identify the customers that maximize the total profit collected while satisfying the given time limit for each vehicle. 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 branch-and-cut algorithm for the resolution of the problem. Computational experiments are run on a large set of benchmark instances.