Theoretical Paper
Journal of the Operational Research Society (2009) 60, 831–842; doi:10.1057/palgrave.jors.2602603; published online 28 May 2008
The capacitated team orienteering and profitable tour problems
C Archetti1, D Feillet2, A Hertz3 and M G Speranza1
- 1University of Brescia, Brescia, Italy
- 2Université d'Avignon et des Pays de Vaucluse, Avignon, France
- 3École Polytechnique and GERAD, Montréal, Canada
Correspondence: C Archetti, Department of Quantitative Methods, University of Brescia, C. da S. Chiara 50, Brescia 25122, Italy. E-mail: archetti@eco.unibs.it
Received April 2007; Accepted February 2008; Published online 28 May 2008.
Abstract
In this paper, we study the capacitated team orienteering and profitable tour problems (CTOP and CPTP). The interest in these problems comes from recent developments in the use of the Internet for a better matching of demand and offer of transportation services. We propose exact and heuristic procedures for the CTOP and the CPTP. The computational results show that the heuristic procedures often find the optimal solution and in general cause very limited errors.
Keywords:
team orienteering problem, profitable tour problem, column generation, branch and price, tabu search, variable neighbourhood search
