An ant colony system for team orienteering problems with time windows

• Autorzy: Montemanni R. , Gambardella L.M.
• Języki publikacji: EN

Abstrakty

EN

This paper discusses a heuristic approach for Team Orienteering Problems with Time Windows. The method we propose takes advantage of a solution model based on a hierarchic generalization of the original problem, which is combined with an Ant Colony System algorithm. Computational results on benchmark instances previously adopted in the literature suggest that the algorithm we propose is effective in practice.

Słowa kluczowe

EN

team orienteering; time windows; metaheuristics; ant colony optimization

PL

zespół orientacyjny; okna czasowe; metaheurystyka; optymalizacja kolonii mrówek

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2009
• Tom: Vol. 34, No. 4
• Strony: 287--306
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Montemanni R.

autor

Gambardella L.M.

• Istituto Dalle Molle di Studi sull'Intelligenza Artificiale, Manno, Switzerland

Bibliografia

• [1] C. Archetti, A. Hertz, and M.G. Speranza. Metaheuristics for the team orienteering problem. Journal of Heuristics, 13:49-76, 2007.
• [2] S. Boussier, D. Feillet, and M. Gendreau. An exact algorithm for team orienteering problems. 4 OR, 5(3):211-230, 2007.
• [3] S. Butt and D. Ryan. A heuristic for the multiple path maximum collection problem. Computers and Operations Research, 26:427-441, 1999.
• [4] S.E. Butt and T.M. Cavalier. A heuristic for the multiple path maximum collection problem. Computers and Operations Research, 21:101-111, 1994.
• [5] I-M. Chao, B.L. Golden, and E.A. Wasil. A fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88:475-489, 1996.
• [6] I-M. Chao, B.L. Golden, and E.A. Wasil. The team orienteering problem. European Journal of Operational Research, 88:464-474, 1996.
• [7] J.-F. Cordeau, M. Gendreau, and G. Laporte. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30:105-119, 1997.
• [8] J. J. Dongarra. Performance of various computers using standard linear algebra software in a fortran environment. Technical Report CS-89-85, University of Tennessee, July 2009.
• [9] M. Dorigo, G. Di Caro, and L.M. Gambardella. Ant algorithms for discrete optimization. Artificial Life, 5:137-172, 1999.
• [10] M. Dorigo and L.M. Gambardella. Ant Colony System: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1:53-66, 1997.
• [11] D. Feillet, P. Dejax, and M. Gendreau. Traveling salesman problems with profits. Transportation Science, 39(2):188-205, 2005.
• [12] M. Fischetti, J.J. Salazar-González, and P. Toth. Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, 20:133-148, 1998.
• [13] L.M. Gambardella, É. Taillard, and G. Agazzi. MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, in New ideas in optimization, D. Corne et al. eds., McGraw-Hill, London, U.K., pages 63-76, 1999.
• [14] M. Gendreau, G. Laporte, and F. Semet. The selective traveling salesman problem. Networks, 32:263-273, 1998.
• [15] B.L. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics, 34:263-273, 1987.
• [16] B.L. Golden, Q. Wang, and L. Liu. A multifaceted heuristic for the orienteering problem. Naval Research Logistics, 35:359-366,1987.
• [17] C. Gueguen. Méthodes de résolution exacte pour les problèmes de tournées de véhicules. PhD thesis, École Centrale Paris, 1999.
• [18] R. Hall and M. Racer. Transportation with common carrier and private fleet: System assignment and shipment frequency optimization. HE Transactions, 21:217-225,1995.
• [19] S. Irnich. A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. INFORMS Journal on Computing, to appear.
• [20] M. Kantor and M. Rosenwein. The orienteering problem with time windows. Journal of the Operational Research Society, 43(6):629-635, 1992.
• [21] S. Kataoka, T. Yamada, and S. Morito. Minimum directed 1-subtree relaxation for score orienteering problem. European Journal of Operational Research, 104:139-153, 1998.
• [22] L. Ke, C. Archetti, and Z. Feng. Ants can solve the team orienteering problem. Computers and Industrial Engineering, 54:49-76, 2008.
• [23] G. Laporte and S. Martello. The selective traveling salesman problem. Discrete Applied Mathematics, 26:193-207, 1990.
• [24] A.C. Leifer and M.B. Rosenwein. Strong linear programming relaxations for the orienteering problem. European Journal of Operational Research, 73:517-523, 1989.
• [25] L. Lopez, M.W. Carter, and M. Gendreau. The hot strip mill production scheduling problem: A tabu search approach. European Journal of Operational Research, 106:317-335, 1998.
• [26] R. Mansini, M. Pelizzari, and R. Wolfler Calvo. A granular variable neighborhood search heuristics for the tour orienteering problem with time windows. Technical Report 2008-02-52, Dipartimento di Elettronica per l'Automazione, Universita di Brescia, 2008.
• [27] G. Righini and M. Salani. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers and Operations Research, 36(4):1191-1203, 2009.
• [28] M. Salani. Private communication. 2008.
• [29] M. Solomon. Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research, 35:254-265, 1987.
• [30] É. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin. A tabu search heuristic for the vehicle routing problem with soft time windows. Transportation Science, 31:170-186, 1997.
• [31] H. Tang and E. Miller-Hooks. A tabu search heuristic for the team orienteering problem. Computers and Operations Research, 32:1379-1407, 2005.
• [32] F. Tricoire, M. Romauch, K.F. Doerner, and R.F. Hartl. Heuristics for the multi-period orienteering problem with multiple time windows. Computers and Operations Research, to appear.
• [33] T. Tsiligrides. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35:797-809, 1984.
• [34] P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, and D. Van Oudheusden. Iterated local search for the team orienteering problem with time windows. Computers and Operations Research, 36(12):3281-3290, 2009.