Problem komiwojażera z zyskami i oknami czasowymi dla sieci o wagach zmiennych w czasie i jego zastosowania w systemach typu e-tourism

• Autorzy: Zabielski P. , Koszelew J. , Zimnoch R.

Warianty tytułu

Time Dependent Orienteering Problem with Time Windows and its use in systems of e-tourism

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono problem komiwojażera z zyskami i oknami czasowymi dla sieci o wagach zmiennych w czasie. Jest to rozszerzenie standardowego problemu komiwojażera z zyskami. Przyczynia się to do bardziej praktycznego zastosowania go na przykład w systemach typu e-tourism. Dzięki dodatkowym ograniczeniom może stanowić prawdziwą pomoc podczas planowania ciekawych wycieczek, spełniających wszelkie preferencje użytkownika. W artykule zaproponowano algorytm wykorzystujący iteracyjne poszukiwanie lokalnych rozwiązań. Wykonano testy na realnych danych i przeanalizowano je pod względem czasu wykonywania oraz jakości otrzymanych wyników.

EN

This paper presents the Time Dependent Orienteering Problem with Time Windows. It is an extension of the standard traveling salesman problem with profits. This contributes to a more practical application of it, for example in systems of e-tourism. It can be a really helpful during planning trips and meet all your preferences and additional restrictions. The article proposes an algorithm that uses an iterative search for local solutions. This algorithm was tested on real data. After that we analyzed it in terms of execution time and quality results.

Słowa kluczowe

PL

problem komiwojażera z zyskami i oknami czasowymi; iteracyjny algorytm lokalnego wyszukiwania; planer podróży; algorytm ewolucyjny

EN

salesman problem with profits and time windows; iterated local search; planner of travel; evolutionary algorithm

• Wydawca: Polskie Towarzystwo Symulacji Komputerowej
• Czasopismo: Symulacja w Badaniach i Rozwoju
• Rocznik: 2012
• Tom: Vol. 3, nr 3
• Strony: 175--182
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Zabielski P.

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

autor

Koszelew J.

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

autor

Zimnoch R.

• Transition Technologies, ul. Lipowa 19/21, 15-424 Białystok

Bibliografia

• 1. Garcia A., O., Vansteenwegen P., Souffriau W., Linaza M.T., Hybrid Approach for the Public Transportation Time Dependent Orienteering Problem with Time Windows, 151-158.
• 2. Golden B., Levy L., Vohra R., The orienteering problem, Naval Research Logistics, vol. 34, pp. 307–18, 1987.
• 3. Karbowska-Chilińska J., Koszelew J., Ostrowski K., Zabielski P.: Genetic Algorithm Solving Orienteering Problem in Large Network, KES 2012.
• 4. Koszelew J., An Evolutionary Algorithm for The Urban Public Transportation, Springer-Verlag, Computational and Collective Intelligence – Technologies and Applications, Lecture Notes in Computer Science, vol. 6922, pp. 234-243.
• 5. Koszelew J., Logistyka na usługach obieżyświatów – innowacyjny komponent oprogramowania typu e-tourism, Logistyka, 6/2010, pp. 54-56.
• 6. Li J., Research on Team Orienteering Problem with Dynamic Travel Times, Journal of Software, vol. 7, no. 2, 2012.
• 7. www.e-biznes.pl.
• 8. Vansteenwegen P., Souffriau W., Berghe G.V., Oudheusden D.V., Iterated local search for the team orienteering problem with time windows, Gent, Leuven, 2009.
• 9. Vansteenwegen P., Souffriau W., Oudheusden D.V., The orienteering problem: A survey, Gent, Leuven, 2010.
• 10. Zimnoch R., Efektywne rozwiązania dla problemu Time Dependent Orienteering Problem with Time Windows, Białystok 2012.