The Team Orienteering Arc Routing Problem

Claudia Archetti (), M. Grazia Speranza (), Ángel Corberán (), José M. Sanchis () and Isaac Plana ()
Additional contact information
Claudia Archetti: Dipartimento Metodi Quantitativi, Universitá di Brescia, 25122 Brescia, Province of Brescia, Italy
M. Grazia Speranza: Dipartimento Metodi Quantitativi, Universitá di Brescia, 25122 Brescia, Province of Brescia, Italy
Ángel Corberán: Departamento de Estadística e Investigación Operativa, Universidad de Valencia, 46010 Valencia, Spain
José M. Sanchis: Departamento de Matemática Aplicada, Universidad Politécnica de Valencia, 46022 Valencia, Spain
Isaac Plana: Departamento Matemáticas para la Economía y la Empresa, Universidad de Valencia, 46010 Valencia, Spain

Transportation Science, 2014, vol. 48, issue 3, 442-457

Abstract: 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.

Keywords: team orienteering arc routing problem; profits; multivehicle; facets; branch and cut (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0484 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:48:y:2014:i:3:p:442-457

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().