W poszukiwaniu optymalnej trasy – wybrane algorytmy w zastosowaniu do problemu komiwojażera

• Autorzy: Jakubowska A. , Piechocka K.

Warianty tytułu

EN

In search of the optimal route – selected algorithms applicable to the travelling salesman problem

• Języki publikacji: PL

Abstrakty

PL

Ze względu na dążenie do ograniczenia kosztów logistycznych przedsiębiorstw coraz większego znaczenia nabiera zagadnienie optymalizacji tras. Coraz częściej wykorzystuje się w tym celu rozwiązania heurystyczne oparte na sztucznej inteligencji. Uwzględniając duży stopień trudności w tym zakresie, szczególnie istotne jest wykorzystanie wsparcia informatycznego. Niniejsza praca przedstawia problem komiwojażera oraz możliwość jego rozwiązania za pomocą algorytmów heurystycznych. Szerzej zaprezentowano algorytmy mrówkowy oraz genetyczny.

EN

Due to striving for reducing the logistic cost of enterprises, the route optimisation issue becomes more and more important. For this purpose heuristic solutions based on artificial intelligence are often used. Taking into account the high difficulty of optimization problems, it is particularly important to use IT support. This paper presents the Traveling Salesman Problem and the idea of heuristic algorithms used to solve this problem. More detailed were presented Ant Colony Optimization Algorithm and Genetic Algorithm.

Słowa kluczowe

PL

optymalizacja trasy; problem komiwojażera; heurystyka

EN

route optimization; travelling salesman problem; heuristics

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Journal of TransLogistics
• Rocznik: 2015
• Tom: Vol. 1, nr 1
• Strony: 7--24
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Jakubowska A.

• Koło Naukowe „Logistyka”, Politechnika Poznanska

autor

Piechocka K.

• Koło Naukowe „Logistyka”, Politechnika Poznanska

Bibliografia

• [1] Banks J., Handbook of simulation: Principles, Methodology, Advances, Applications, and Practise, John Wiley & Sons, Inc., Atlanta 1998, s. 2-3.
• [2] Domka P., Łokińska M., Programowanie strukturalne i obiektowe, Wydawnictwa Szkolne i Pedagogiczne Spółka Akcyjna, Warszawa 2009.
• [3] Dorigo M., Di Caro G., Gambardella L.M., Ant Algorithms for Discrete Optimization, Artificial Life, 5 (2), 1999, dostęp w Internecie (05.11.2015): http://people.idsia.ch/luca/ij23-alife99.pdf
• [4] Dorigo M., Gambardella L. M., Ant colonies for the traveling salesman problem,Technical Report TR/IRIDIA/1996-3, Universit´e Librede Bruxelles, Belgium, 1996, dostęp w Internecie (05.11.2015): http://people.idsia.ch/luca/acs-bio97.pdf
• [5] Dorigo M., Stützle T., Ant Colony Optimization, MIT Press, Cambridge, MA, USA, 2004, dostęp w Internecie (05.11.2015): http://golem.iimas.unam.mx/caleb/IA/Topic3-Optimization/literature/Ant_Colony_Optimization.pdf
• [6] Filo G., Zastosowanie algorytmów mrówkowych w rozwiązaniu problemu szeregowania zadań, Czasopismo Techniczne. Mechanika, 4-M/2011, dostęp 06.11.2015: https://suw.biblos.pk.edu.pl/resources/i4/i5/i8/i8/r4588/FiloG _ZastosowanieAlgorytmow.pdf]
• [7] http://sjp.pwn.pl, dostęp 06.11.2015
• [8] http://www.alife.pl/opt/p/aa.html, dostęp 05.11.2015
• [9] http://www.cwr.webd.pl/js/dane/praca.pdf, dostęp 05.11.2015
• [10] http://www.optifacility.com/site/pl/optymalizacja-tras, dostęp 06.11.2015
• [11] http://www.rgtechmix.pl/logistyka.html, dostęp 06.11.2015
• [12] http://zasoby1.open.agh.edu.pl/dydaktyka/informatyka/c_algorytmy_i_str_danych/index.php?go=komiwojazer, dostęp 06.11.2015
• [13] http://zsi.ii.us.edu.pl/mboryczka/IntStad/sm_inteligencja.php, dostęp 05.11.2015
• [14] https://www.ii.pwr.edu.pl/kwasnicka/tekstystudenckie/algorytmymrowkowe.pdf, dostęp 05.11.2015
• [15] https://www.ii.uni.wroc.pl/prz/2011lato/ah/opracowania/alg_mrow.opr.pdf, dostęp 05.11.2015
• [16] Jachimowski R., Ambroziak T., Klasteryzacja punktów obsługi i wyznaczanie tras pojazdów w dwuszczeblowym systemie dystrybucji, Logistyka 4/2012.
• [17] Jachimowski R., Zastosowanie algorytmów heurystycznych do rozwiązywania problemu układania tras pojazdów, Logistyka 2/2015.
• [18] Karkula M., Szymanowska A., Usprawnianie procesów transportowych z wykorzystaniem usług sieciowych na przykładzie przedsiębiorstwa komunalnego, dostęp 05.11.2015: http://www.logistyka.net.pl/bank-wiedzy/transport-i-spedycja/item/81472-usprawnianie-procesow-transportowych-z-wykorzystaniem-uslug-sieciowych-na-przykladzie-przedsiebiorstwa-komunalnego
• [19] Komosiński M., Jaszkiewicz A., Wykłady z przedmiotu „Optymalizacja”, Politechnika Poznańska, dostęp w Internecie (05.11.2015): https://www.cs.put.poznan.pl/mkomosinski/materialy/optymalizacja/Algorytmy.pdf
• [20] Kozik J., Rozprawa doktorska: Diagnostyka maszyny synchronicznej z zastosowaniem metod sztucznej inteligencji, Kraków 2011.
• [21] Krishnaiyer K., Hossein Cheraghi S., Ant Algorithms: Review and Future Applications, Proc. Industrial Engineering Research Conference, Wichita 2002.
• [22] Michalewicz Z., Algorytmy Genetyczne + struktury danych = programy ewolucyjne, Wydawnictwo Naukowo Techniczne, Warszawa 2003.
• [23] Michlowicz E., Rozwiązywanie problemów dostaw w systemach dystrybucji, Logistyka 4/2012.
• [24] Piętoń Ł., praca magisterska pt. Zastosowanie metod inteligencji obliczeniowej do rozwiązania problemu komiwojażera, Kraków 2011.
• [25] Pyza D., Wybrane aspekty racjonalizacji systemów przewozowych w łańcuchu dostaw przy ograniczonych zasobach, Logistyka 4/2012.
• [26] Różanowski K., P. Sienkiewicz (red.): Zeszyt Naukowy NR 2. WWSI, Warszawa, 2007, str. 109-135.
• [27] Rucińska D., Popyt na usługi transportowe, [w:] Rydzkowski W., Wojewódzka-Król K. [red.], Transport, Warszawa 1997.
• [28] Rutkowski L., Metody i techniki sztucznej inteligencji, Wydawnictwo Naukowe PWN, Warszawa 2009.
• [29] Tomeczko B., Problem komiwojażera – algorytmy metaheurystyczne, 2010, dostęp 06.11.2015 http://www.tomeczko.pl/pwr/index.php?option=com vfm&Itemid=37&do=download&file=PDF%7CMH.pdf
• [30] Wykłady z przedmiotu „Heurystyki i meta heurystyki”, AGH, dostęp 05.11.2015 http://www.pi.zarz.agh.edu.pl/intObl/notes/IntObl w2.pdf