The comparison of genetic algorithms which solve orienteering problem using complete and incomplete graph

• Autorzy: Ostrowski K. , Koszelew J.

Warianty tytułu

PL

Porównanie algorytmów genetycznych rozwiązujących Orienteering Problem przy pomocy grafu pełnego i niepełnego

• Języki publikacji: EN

Abstrakty

EN

The purpose of this work was to compare two forms of genetic algorithm (complete and incomplete graph version) which solves Orienteering Problem (OP). While in most papers concerning OP graph is complete and satisfies triangle inequality, in our versions such assumptions may not be satisfied. It could be more practical as transport networks are graphs which do not have to satisfy those conditions. In such cases, graphs are usually complemented with fictional edges before they can be used by classic OP solving algorithms which operate on complete graphs. This paper answers the question: Is it better (in terms of results quality and time consumption) to transform graphs to classic OP form before running algorithm (complete graph version) or to solve OP on graphs without any assumptions and changes (incomplete graph version)? The computer experiment was conducted on the real transport network in Poland and its results suggest that it is worth checking both versions of the algorithm on concrete networks.

PL

Celem pracy było porównanie dwóch odmian algorytmu (wersja dla grafu pełnego i niepełnego) rozwiązujących Orienteering Problem (OP). W większości artykułów dotyczących OP graf jest pełny, a jego krawędzie spełniają nierówność trójkąta, natomiast w naszej wersji takie założenia mogą nie być spełnione. Może to być bardziej praktyczne ponieważ sieci transportowe są grafami, ktore nie muszą spełniać tych warunków. W takich przypadkach grafy są zazwyczaj uzupełniane fikcyjnymi krawędziami, a następnie działają na nich algorytmy rozwiązujące klasyczną wersje OP, które operują na grafie pełnym. Artykuł odpowiada na pytanie: czy pod względem jakości wyników i czasu obliczeń lepiej jest przekształcać graf do klasycznej formy OP przed uruchomieniem algorytmu w wersji dla grafu pełnego czy rozwiązywać OP na grafie niezmienionym i nie spełniającym dodatkowych założeń (wersja dla grafu niepełnego)? Eksperyment został przeprowadzony na prawdziwej sieci transportowej w Polsce, a jego wyniki sugerują, że warto sprawdzać obie wersje algorytmu na konkretnych sieciach.

Słowa kluczowe

EN

OP; GA; orienteering problem; transport network; genetic algorithm; incomplete graph; complete graph

PL

graf niepełny; graf pełny; sieć transportowa; OP; GA; algorytm genetyczny

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2011
• Tom: Z. 8
• Strony: 61--77
• Opis fizyczny: Bibliogr. 20 poz., rys., tab., wykr.

Twórcy

autor

Ostrowski K.

autor

Koszelew J.

• Bialystok University of Technology, Faculty of Computer Science, Białystok, Poland

Bibliografia

• [1] I. Chao, B. Golden, E. Wasil, Theory and methodology - the team orienteering problem, European Journal of Operational Research 88, 464-474, 1996.
• [2] A. Garcia, M.T. Linaza, O. Arbelaitz, P. Vansteenwegen, Intelligent Routing System for a Personalised Electronic Tourist Guide, Springer, 4, 185-197, 2009.
• [3] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979.
• [4] B. Golden, L. Levy, R. Vohra, The orienteering problem, Naval Research Logistics 34, 1987.
• [5] B. Golden, Q. Wang, L. Liu, A Multifaceted Heuristic for The Orienteering Problem, Naval Research Logistics, vol. 35, pp. 359-366, 1988.
• [6] M. Hayes, J. M. Norman, Dynamic Programming in Orienteering: Route Choice and the Siting of Controls, Journal of the Operational Research Society, vol. 35, no. 9, pp. 791-796, 1984.
• [7] G. Laporte, S. Martello, The Selective Traveling Salesman Problem, Discrete Applied Mathematics, vol. 26, pp. 193-207, 1990.
• [8] J. Koszelew, Logistics for globetrotters - innovative software component for e-tourism, Logistics, vol. 6, 54-56, 2010.
• [9] A. Piwonska, J. Koszelew, A Memetic Algorithm for a Tour Planning in the Selective Travelling Salesman Problem on a Road Network Springer, vol. 6804, 684-694, 2011.
• [10] R. Ramesh, K. M. Brown, An Efficient Four-Phase Heuristic for the Generalized Orienteering Problem, Computers and Operations Research, vol. 18, no. 2, pp. 151-165, 1991.
• [11] W. Souffriau, P. Vansteenwegen, J. Vertommen, G. Vanden Berghe, D. Van Oudheusden, A personalized tourist trip design algorithm for mobile tourist guides, Applied Artificial Intelligence, 22:10, 964-985, 2008.
• [12] W. Souffriau, P. Vansteenwegen, Tourist Trip Planning Functionalities: State-of-the-Art and Future, Springer, vol. 6385/2010, 474-485, 2010.
• [13] M.F. Tasgetiren, A.E. Smith, A Genetic Algorithm for the Orienteering Problem, Proceedings of the 2000 Congress on Evolutionary Computation, San Diego, CA, pp. 1190-1195, 2000.
• [14] F. Tricoire, M. Romauch, K. Doerner, R. Hartl, Heuristics for the multi-period orienteering problem with multiple time windows, Computers and Operations Research 37 (2), 351-367, 2010.
• [15] T. Tsiligirides, Heuristic Methods Applied to Orienteering, Journal of Operational Research Society, vol. 35, no. 9, pp. 797-809, 1984.
• [16] P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, D. Van Oudheusden, A guided local search metaheuristic for the team orienteering problem, European Journal of Operational Research in Press, vol. 196, 2008.
• [17] P. Vansteenwegen, W. Souffriau, D. Van Oudheusden, The orienteering problem: A survey, Elsevier, vol. 209, 2010.
• [18] P. Vansteenwegen, W. Souffriau, G. Vanden Berghe, D. Van Oudheusden, The City Trip Planner: An expert system for tourists, Elsevier, vol. 38, 2011.
• [19] Q.Wang, X. Sun, B.L. Golden, J. Jia, Using Artificial Neural Networks to Solve the Orienteering Problem, Annals of Operations Research, vol. 61, pp. 111-120, 1995.
• [20] http://piwonska.pl/research