Zastosowanie problemu komiwojażera z profitami i oknami czasowymi do wyznaczania tras atrakcyjnych turystycznie okolic Białegostoku

• Autorzy: Karbowska-Chilińska J. , Zabielski P.

Warianty tytułu

EN

An application of the Orienteering Problem with Time Windows for tour planning problem in Bialystok region

• Języki publikacji: PL

Abstrakty

PL

Problem komiwojażera z profitami i oknami czasowymi jest dogodnym modelem dla problemu optymalnego planowania tras atrakcyjnych turystycznie. W pracy przedstawiono rozwiązanie tej odmiany problemu komiwojażera za pomocą algorytmu genetycznego GAPR. W miejsce krzyżowania zaproponowano wymianę obiektów między losowo wybranymi trasami. Rozwiązanie przetestowano na rzeczywistej sieci obiektów turystycznych okolicy Białegostoku. W wyniku testów otrzymano trasy o porównywalnej atrakcyjności jak w algorytmie genetycznym GA z krzyżowaniem (różnica jest na korzyść GAPR około 0.5%) i czasem generowania trasy nie przekraczającym 1.5 sekundy. Algorytm może być zastosowany w planerach tras turystycznych.

EN

Orienteering problem with time windows (OPTW) is a good model for the tour planning problem. In this article a genetic algorithm with path relinking (GAPR) is used for solving OPTW. The path relinking (PR) process is applied instead of a crossover. The solution has been tested on a real network of tourist points of interests in Bialystok region. Routes which are the test results are comparable with the routes generated by the previous GA with crossover (the GAPR exceeds profit result about 0.5% relative to GA, the execution time of GAPR does not exceed 1.5 s). The algorithm can be used in trip planners.

Słowa kluczowe

PL

problem komiwojażera; algorytm genetyczny; generowanie tras atrakcyjnych turystycznie

EN

orienteering problem; genetic algorithm; tour planning problem

• Wydawca: Polskie Towarzystwo Symulacji Komputerowej
• Czasopismo: Symulacja w Badaniach i Rozwoju
• Rocznik: 2013
• Tom: Vol. 4, nr 2
• Strony: 81--89
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Karbowska-Chilińska J.

• Politechnika Białostocka, ul. Wiejska 45A 15-351 Białystok

autor

Zabielski P.

• Politechnika Białostocka, ul. Wiejska 45A 15-351 Białystok

Bibliografia

• 1. Campos, V., Marti R., Sanchez-Oro J., Duarte A.: Grasp with Path Relinking for the Orienteering Problem, Journal of the Operational Research Society, pp. 1-14, 2013.
• 2. 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), 15-27, 2012.
• 3. 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, pp. 609-619, 2014.
• 4. Karbowska-Chilinska J., Koszelew J., Ostrowski K., Zabielski P.: Genetic algorithm solving orienteering problem in large networks, Frontiers in Artificial Intelligence and Applications, 243, pp. 28-38, 2012.
• 5. Karbowska-Chilinska J., Zabielski P.: Genetic Algorithm with Path Relinking for the Orienteerig Problem with Time Widows, Proceedings of the 22nd International Workshop on Concurrency, Specification and Programming, pp. 245-258, 2013.
• 6. Montemanni R., Weyland D., Gambardella L. M.: An Enhanced Ant Colony System for the Team Orienteering Problem with Time Windows, Proceedings of IEEE ISCCS, 381-384, 2011.
• 7. Souffriau W., Vansteenwegen P., Vanden Berghe G., Van Oudheusden D.: A path relinking approach for the team orienteering problem. Computers & operations research, 37 (11), 1853-1859, 2010.
• 8. Vansteenwegen P., Souffriau W., Van Oudheusden D.: The Orienteering Problem: A survey, European Journal of Operational Research, 209 (1), pp. 1-10, 2011.

Uwagi

PL

Artykuł został sfinansowany z prac badawczych S/WI/1/2014 oraz W/WI/2/2013 realizowanych na Wydziale Informatyki Politechniki Białostockiej.