A comparison of ant colony optimization and genetic algorithm for solving the traveling salesman problem

• Autorzy: Ochelska-Mierzejewska, J.
• Języki publikacji: EN

Abstrakty

EN

Every company in today’s world faces the constant challenge of cost reduction. For distribution and transport service providers, cost cutting appears to be the main operational goal. The successful companies seek to develop an optimal routes for their fleets to minimize the costs and guarantee a timely delivery of the goods. With a growing informatization of the industrial world, it is worth considering the use of intelligent systems as a possible way of solving various types of decision problems, which in turn can contribute to the reduction of costs incurred by a company. Such systems enable multidimensional data analysis and to provide information useful in decision making. The paper investigates the use of the genetic algorithm and the ants colony optimization algorithm as a solution to the travelling salesman problem. It has been shown that both methods provide satisfactory results in solving the problem under examination.

Słowa kluczowe

PL

problem komiwojażera; optymalizacja kolonii mrówek; algorytm genetyczny

EN

travelling salesman problem; ant colony optimization; genetic algorithm

• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2016
• Tom: Vol. 24, nr 1
• Strony: 51--66
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Ochelska-Mierzejewska, J.

• Lodz University of Technology, Institute of Information Technology, Wolczanska 215, 90-924 Lodz, Poland,

Bibliografia

• [1] Rydzkowski, W. and Wojewódzka-Król, K., Transport, PWN, 1997, in Polish.
• [2] Szczepaniak, T. E., Transport Mi˛edzynarodowy, PWE, 1998, in Polish.
• [3] Krasucki, Z. E., Transport i spedycja w handlu zagranicznym, Wyd. UG, 1997, in Polish.
• [4] Wilson, R., Wprowadzenie do teorii grafów, PWN, 1998, in Polish.
• [5] Travelling salesman problem, [Online] http://fds.oup.com/www.oup.com/pdf/oxed/D2.pdf.
• [6] Travelling salesman problem, [Online] http://www.travellingsalesmanproblem.com/.
• [7] Dorigo, M. and Stützle, T., Ant Colony Optimization, MIT Press, 2004.
• [8] Hammerl, T., Ant Colony Optimization for Tree and Hypertree Decompositions, Betreuer/in (nen): N. Musliu; Institut für Informationssysteme, Arbeitsbereich Datenbanken & Artificial Intelligence, 2009.
• [9] Grzymkowski, R., Kaczmarek, K., Kiełtyka, S., and Nowak, I., Wybrane algorytmy optymalizacji. Algorytmy genetyczne. Algorytmy mrówkowe, Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, 2008, in Polish.
• [10] Brezina, I. and Èièková, Z., Solving the Travelling Salesman Problem Using the Ant Colony Optimization, Management Information Systems, Vol. 6, No. 4, 2011.
• [11] Gwiazda, T., Algorytmy Genetyczne. Wst˛ep do teorii, PWN, 1995, in Polish.
• [12] Wierzchoń, S., Sztuczne systemy immunologiczne. Teoria i zastosowania, Akademicka Oficyna Wydawnicza EXIT, 2001, in Polish.
• [13] Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, PWN, 1999, in Polish.
• [14] Goldberg, D., Algorytmy genetyczne i ich zastosowania, WNT, 1998, in Polish.
• [15] Michalewicz, Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, 2004, in Polish.
• [16] Rutkowski, L., Metody i techniki sztucznej inteligencji, PWN, 2012, in Polish.
• [17] Ochelska-Mierzejewska, J., Rozwiązanie problemu komiwojażera przy użyciu algorytmu genetycznego, Logistyka, Vol. 1, 2016, pp. 350–356, in Polish.
• [18] Ochelska-Mierzejewska, J., Algorytm mrówkowy jako metoda rozwiązania problemu komiwojażera, TTS Technika Transportu Szynowego, Vol. 12, 2015, pp. 1140–1147, in Polish.
• [19] TSPLIB, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.