Genetic Algorithm with Path Relinking for the Orienteering Problem with Time Windows

• Autorzy: Karbowska-Chilinska J. , Zabielski P.

Identyfikatory

DOI

10.3233/FI-2014-1132

• Języki publikacji: EN

Abstrakty

EN

The Orienteering Problem with Time Windows (OPTW) is an optimisation NP-hard problem. This paper proposes a hybrid genetic algorithm (GAPR) for approximating a solution to the OPTW. Instead of a crossover we use a path relinking (PR) strategy as a form of intensification solution. PR generates a new solution by exploring trajectories between two random solutions: genes not present in one solution are included in the other one. Experiments performed on popular benchmark instances show that the proposed GAPR gives good quality solutions using short computing times. Moreover, GAPR gives new best solutions for some test instances.

Słowa kluczowe

EN

orienteering problem with time windows; genetic algorithm; path relinking

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 4
• Strony: 419--431
• Opis fizyczny: Bibliogr. 31 poz., rys., tab., wykr.

Twórcy

autor

Karbowska-Chilinska J.

• Faculty of Computer Science, Bialystok University of Technology, Poland

autor

Zabielski P.

• Faculty of Computer Science, Bialystok University of Technology, Poland

Bibliografia

• [1] Archetti, C., Hertz, A., Speranza, M. G.: Metaheuristics for the team orienteering problem, Journal of Heuristics, 13, 2007, 49–76.
• [2] Campos, V., Marti, R., Sanchez-Oro, J., Duarte, A.: Grasp with Path Relinking for the Orienteering Problem, Journal of the Operational Research Society, 2013, 1–14.
• [3] http://www.citytripplanner.com/en/home, Last access: April 27, 2014.
• [4] Cordeau, J. F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2), 1997, 105-119.
• [5] Garcia, A., Vansteenwegen, P., Arbelaitz, O., Souffriau, W., Linaz, M.: Integrating Public Transportation in Personalised Electronic Tourist Guides. Computers & Operations Research, 40, 2013, 758–774.
• [6] Glover, F.: A Template For Scatter Search And Path Relinking, Lecture Notes in Computer Science, 1363, 1997, 13-54.
• [7] Glover, F., Laguna, M.: Tabu Search, Kluwer Academic Publishers, Boston, 1997.
• [8] Huang, Y. H., Ting, C. K.: Genetic algorithm with Path Relinking for the Multi-Vehicle Selective Pickup and Delivery problem, Evolutionary Computation (CEC), Proceedings of the IEEE Congress, 2011, 1818–1825.
• [9] Kantor, M., Rosenwein, M.: The Orienteering Problem with Time Windows, Journal of the Operational Research Society, 43, 1992, 629–635.
• [10] Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K., Zabielski, P.: Genetic algorithm solving orienteering problem in large networks, Frontiers in Artificial Intelligence and Applications. 243, 2012, 28–38.
• [11] Karbowska-Chilinska, J., Zabielski, P.: A Genetic Algorithm Solving Orienteering Problem with Time Windows, Advances in Systems Science, Advances in Intelligent Systems and Computing, Springer, 240, 2014, 609-619.
• [12] Karbowska-Chilinska, J., Zabielski, P.: Addendum to the paper A Genetic Algorithm Solving Orienteering Problem with Time Windows, 2014. http://asia.chilan.com/artykuly/addendum.pdf
• [13] Labadie, N., Mansini, R., Melechovsky, J., Wolfler Calvo, R.: The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search, European Journal of Operational Research, 220(1), 2012, 15-27.
• [14] Labadie, N., Melechovsky, J., Wolfler Calvo, R.: Hybridized evolutionary local search algorithm for the team orienteering problem with time windows, Journal of Heuristics, 17(6), 2011, 729-753.
• [15] Mansini, R., Pelizzari, M., Wolfler, R.: A Granular Variable Neighborhood Search for the Tour Orienteering Problem with Time Windows, Technical Report of the Department of Electronics for Automation, University of Brescia, 2006.
• [16] Montemanni, R., Gambardella, L. M.: Ant colony system for team orienteering problems with time windows, Foundations of Computing and Decision Sciences, 34(4), 2009, 287-306.
• [17] Montemanni, R., Weyland, D., Gambardella L. M.: An Enhanced Ant Colony System for the Team Orienteering Problem with Time Windows, Proceedings of IEEE ISCCS, 2011, 381-384.
• [18] Mota, G., Abreu, M., Quintas, A., Ferreira, J., Dias, L. S., Pereira, G. A., Oliveira, J. A.: A genetic algorithm for the TOPdTW at operating rooms, In Computational Science and Its Applications ICCSA 2013, Springer, 2013, 304–317.
• [19] Oliveira, P. L, Arroyo, J. E. C, Santos, A. G., Goncalves, L. B. , Oliveira, A. P.: An evolutionary algorithm with path-relinking for the parallel machine with job splitting, Systems, Man, and Cybernetics (SMC), IEEE International Conference, 2012, 3153–3158.
• [20] http://openmp.org/wp/, Last access: April 27, 2014.
• [21] Righini, G., Salani, M.: New dynamic programming algorithms for the resource constrained elementary shortest path, Networks, 51(3), 2008, 155 –170.
• [22] Righini, G., Salani, M.: Decremental state space relaxation strategies and initialization heuristics for solving the Orienteering Problem with Time Windows with dynamic programming, Computers & Operations Research, 36, 2009, 1191 – 1203.
• [23] Solomon, M.: Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints, Operations Research, 35(2), 1987, 254 –265.
• [24] Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., Van Oudheusden, D.: A Path Relinking approach for the Team Orienteering Problem, Computers & Operations Research, 37(11), 2010, 1853-1859.
• [25] Tasgetiren, M. F., Smith, A. E.: A genetic algorithm for the orienteering problem, Proceedings of the 2000 Congress on Evolutionary Computation San Diego, 2, 2000, 1190–1195.
• [26] Tricoire, F., Romauch, M., Doerner, K. F., Hartl, R. F.: Heuristics for the multi-period orienteering problem with multiple time windows, Comput. Oper. Res., 34(2), 2010, 351–367.
• [27] Tricoire, F., Romauch, M., Doerner, K. F., Hartl, R. F. : Addendum to the paper Heuristics for the multiperiod orienteering problem with multiple time windows. http://prolog.univie.ac.at/research/publications/downloads/Tri 2010 567.pdf.
• [28] Tsiligirides, T.: Heuristic Methods Applied to Orienteering, Journal of the Operational Research Society, 35(9), 1984, 797–809.
• [29] Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: The City Trip Planner: An expert system for tourists, Expert Systems with Applications, 38(6), 2011, 6540–6546.
• [30] Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: Iterated local search for the team orienteering problem with time windows. Computers O.R., 36, 2009, 3281–3290.
• [31] Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The Orienteering Problem: A survey, European Journal of Operational Research, 209(1), 2011, 1–10.