×

An exact algorithm for team orienteering problems. (English) Zbl 1211.90029

Summary: Optimising routing of vehicles constitutes a major logistic stake in many industrial contexts. We are interested here in the optimal resolution of special cases of vehicle routing problems, known as team orienteering problems. In these problems, vehicles are guided by a reward that can be collected from customers, while the length of routes is limited. The main difference with classical vehicle routing problems is that not all customers have to be visited. The solution method we propose here is based on a Branch & Price algorithm. It is, as far as we know, the first exact method proposed for such problems, except for a preliminary work from C. Gueguen [Methodes de résolution exacte pour problémes de tournées de véhicules, Thése de doctorat, école Centrale Paris (1999)] and a work from S. E. Butt and D. M. Ryan [Comput. Oper. Res. 26, No. 4, 427–441 (1999; Zbl 0951.90007)]. It permits to solve instances with up to 100 customers.

MSC:

90B06 Transportation, logistics and supply chain management

Citations:

Zbl 0951.90007
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Archetti C, Hertz A, Speranza MG (2005) Metaheuristics for the team orienteering problem. Technical Report GERAD-2005-47, Groupes d’Etudes et de Recherche en Analyse des Dcisions
[2] Butt SE, Ryan DM (1999) An optimal solution procedure for the multiple tour maximum collection problem using column generation. Comput Oper Res 26(4): 427–441 · Zbl 0951.90007 · doi:10.1016/S0305-0548(98)00071-9
[3] Chao I-M, Golden BL, Wasil EA (1996) The team orienteering problem. Eur J Oper Res 88(3): 464–474 · Zbl 0911.90145 · doi:10.1016/0377-2217(94)00289-4
[4] Desaulniers G, Desrosiers J, Solomon MM (eds) (2005) Column generation. GERAD 25th Anniversary Series. Springer, Berlin Heidelberg New York
[5] Desrochers M, Desrosiers J, Solomon MM (1992) A new optimization algorithm for the vehicle routing problem with time windows. Oper Res 40(2): 342–354 · Zbl 0749.90025 · doi:10.1287/opre.40.2.342
[6] Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44 (3): 216–229 · Zbl 1056.90014 · doi:10.1002/net.20033
[7] Feillet D, Dejax P, Gendreau M (2005a). Traveling salesman problems with profits. Transp Sci 39(2): 188–205 · doi:10.1287/trsc.1030.0079
[8] Feillet D, Gendreau M, Rousseau LM (2005b) New refinements for the solution of vehicle routing problems with branch and price. Technical Report CRT-2005-08, Centre de Recherche sur les Transports
[9] Gueguen C (1999) Méthodes de résolution exacte pour les problèmes de tournées de véhicules. Thése de doctorat, école Centrale Paris
[10] Gueguen C (2006) Private communication
[11] Harvey W, Ginsberg M (1995) Limited discrepancy search. In: Proceedings of the 14th international joint conference on artificial intelligence (IJCAI-95), Morgan Kaufmann, Montréal, pp. 607–615
[12] Hayari N, Manier M-A, Bloch C, El Moudni A (2003) Un algorithme évolutionniste pour le problème de tournées sélectives avec contraintes de fenêtre de temps. In 4ème Conférence Francophone de MOdélisation et SIMulation MOSIM’03, Toulouse
[13] Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers G, Desrosiers J, Solomon MM, (eds) Column generation, GERAD 25th Anniversary Series, chap 2, pp. 33–65, Springer, Berlin Heidelberg New York · Zbl 1130.90315
[14] Laporte G, Martello S (1990) The selective traveling salesman problem. Discrete Appl Math 26:193–207 · Zbl 0695.90098 · doi:10.1016/0166-218X(90)90100-Q
[15] Tang H, Miller-Hooks E (2005) A tabu search heuristic for the team orienteering problem. Comput Oper Res 32(6): 1379–1407 · Zbl 1122.90434 · doi:10.1016/j.cor.2003.11.008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.