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

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.

---

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.