Genetic algorithm finds routes in travelling salesman problem with profits

• Autorzy: Piwońska A.

Warianty tytułu

PL

Algorytm genetyczny odnajduje trasy w problemie komiwojażera z zyskami

• Języki publikacji: EN

Abstrakty

EN

Travelling salesman problem with profits is a version of a classic travelling salesman problem where it is not necessary to visit all vertices. Instead of it, with each vertex a number meaning a profit is associated. The problem is to find a cycle in a graph which maximizes collected profit but does not exceed a given cost constraint. This problem is NP-hard. Additional assumptions to this problem were proposed in the paper.We assumed that a graph may not be a complete graph. Moreover, repeated visiting of a given vertex is allowed, however with an assumption that a profit is realized only during first visiting. With these additional assumptions, the problem is more real-life and could have applications in logistics and shipping. To solve the problem, a genetic algorithm with special operators was proposed. The algorithm was tested on networks of cities in some voivodeships of Poland, obtaining very good results.

PL

Problem komiwojażera z zyskami (ang. TSP with profits) jest pewną wersją klasycznego problemu komiwojażera, w której nie jest konieczne odwiedzenie wszystkich wierzchołków grafu. Zamiast tego, z każdym wierzchołkiem związana jest pewna liczba oznaczająca zysk. Problem polega na znalezieniu cyklu w grafie, który maksymalizuje zysk, ale którego koszt nie przekracza zadanego ograniczenia. Problem ten jest problemem NPtrudnym. Do tak postawionego problemu, w pracy zaproponowano dodatkowe założenia. Przyjęto mianowicie, że graf nie musi być pełny. Ponadto dopuszczona jest możliwość powrotów, czyli ponownego odwiedzenia danego wierzchołka, przy założeniu jednak, iż zysk realizowany jest tylko podczas pierwszego odwiedzenia. Przy tych dodatkowych założeniach problem jest bardziej realny i może mieć konkretne zastosowania w logistyce i spedycji. Do rozwiązania problemu zaproponowano algorytm genetyczny, uzyskując bardzo dobre wyniki.

Słowa kluczowe

EN

genetic algorithm; traveling salesman problem

PL

algorytm genetyczny; zysk; komiwojażer

• Wydawca: Oficyna Wydawnicza Politechniki Białostockiej
• Czasopismo: Zeszyty Naukowe Politechniki Białostockiej. Informatyka
• Rocznik: 2010
• Tom: Z. 5
• Strony: 51--65
• Opis fizyczny: Bibliogr. 17 poz., rys., tab., wykr.

Twórcy

autor

Piwońska A.

• Politechnika Białostocka. Wydział Informatyki, Białystok

Bibliografia

• [1] Fatih Tasgetiren, M.: A Genetic Algorithm with an Adaptive Penalty Function for the Orienteering Problem. Journal of Economic and Social Research, vol. 4 (2), pp. 1-26, 2002.
• [2] Feillet, D., Dejax, P., Gendreau, M.: Traveling Salesman Problems with Profits, Transportation Science, vol. 39 (2), pp. 188-205, 2005.
• [3] Fischetti, M., Salazar González, J. J., Toth, P.: Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, vol. 10 (2), pp. 133- 148, 1998.
• [4] Geem, Z. W., Tseng, Ch.-L., Park, Y.: Harmony Search for Generalized Orienteering Problem: Best Touring in China. LNCS, vol. 3612, Springer, pp. 741-750, 2005.
• [5] Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, vol. 106 (2-3), Elsevier, pp. 539-545, 1998.
• [6] Goldberg, D. E.: Genetic algorithms and their applications. WNT, Warsaw, 1995.
• [7] Jozefowiez, N., Glover F., Laguna, M.: Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits. Journal of Mathematical Modelling and Algorithms, vol. 7 (2), pp. 177-195, 2008.
• [8] Koszelew, J., Piwonska, A.: Tunning Parameters of Evolutionary Algorithm in Travelling Salesman Problem with Profits and Returns. Archives of Transport System Telematics, to appear (2010).
• [9] Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., Shmoys, D. B.: The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. John Wiley & Sons, 1985.
• [10] Liang, Y.-C., Smith, A. E.: An ant colony approach to the orienteering problem. Technical report. Department of Industrial and Systems Engineering, Auburn University, Auburn, USA, 2001.
• [11] Michalewicz, Z.: Genetic Algorithms+Data Structures=Evolution Programs. WNT, Warsaw, 1996.
• [12] Mitchell, M.: An Introduction to Genetic Algorithms. MIT Press, 1998.
• [13] Ramesh, R., Brown, K. M.: An efficient four-phase heuristic for the generalized orienteering problem. Computers & Operations Research, vol. 18 (2), Elsevier,pp. 151-165, 1991.
• [14] Qin, H., Lim, A., Xu, D.: The Selective Traveling Salesman Problem withRegular Working Time Windows. Studies in Computational Intelligence, vol. 214, pp. 291-296, 2009.
• [15] Sevkli, Z., Sevilgen, F. E.: Variable Neighborhood Search for the Orienteering Problem. LNCS, vol. 4263, Springer, pp. 134-143, 2006.
• [16] Souffriau, W., Vansteenwegen, P., Berghe, G. V., Oudheusden, D. V.: A Greedy Randomised Adaptive Search Procedure for the Team Orienteering Problem. In Proceedings of EU/MEeting 2008 - Troyes, France, 2008.
• [17] Wang, Q., Sun, X., Golden, B. L., Jia, J.: Using artificial neural networks to solve the orienteering problem. Annals of Operations Research, vol. 61, Springer, pp. 111-120, 1995.