Problem komiwojażera – studium przypadku

• Autorzy: Ziółkowski Jarosław , Miziołek Angelika , Ćwik Dariusz

Identyfikatory

DOI

10.5604/01.3001.0012.7149

Warianty tytułu

EN

Travelling Salesman Problem – Case Study

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono problem komiwojażera na przykładzie liczbowym. Celem jest znalezienie trasy łączącej wszystkie miasta, która całościowo jest najkrótsza, najszybsza lub najtańsza i ponadto zaczyna się i kończy się w określonym punkcie. Jest to typowe zagadnienie optymalizacyjne, w którym zadane jest n miast, które komiwojażer musi odwiedzić. Jego rozwiązanie polega na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.

EN

The paper presents the travelling salesman problem (TSP) on a numerical example. The aim of the paper is to find the shortest, the fastest and the cheapest route, which links all the cities and additionally starts and ends at a particular point. This is the typical optimization problem with n number of cities that the travelling salesman has to visit. The solution of the problem is to find the minimum Hamiltonian cycle in a complete weighted graph.

Słowa kluczowe

PL

problem komiwojażera; studium przypadku; optymalizacja

EN

travelling salesman problem; case study; optimization

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Systemy Logistyczne Wojsk
• Rocznik: 2018
• Tom: Vol. 49, no. 2
• Strony: 236--245
• Opis fizyczny: Bibliogr. 14 poz., rys..

Twórcy

autor

Ziółkowski Jarosław

• Wojskowa Akademia Techniczna, Wydział Mechaniczny

autor

Miziołek Angelika

• Wojskowa Akademia Techniczna, Wydział Mechaniczny

autor

Ćwik Dariusz

• Wojskowa Akademia Techniczna, Wydział Logistyki

Bibliografia

• 1. Michalewicz Z., Algorytmy genetyczne+ struktury danych= programy ewolucyjne, Wydawnictwo Naukowo-Techniczne, Warszawa 2003.
• 2. Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, Massachusetts Institute of Technology, London 2009.
• 3. Ignasiak E. (red.)., Badania operacyjne, PWE, Warszawa 2001.
• 4. Dziamski O., Współczesne metody automatycznego planowania dystrybucji towarów, Logistyka nr 6/2004, ILiM, Poznań 2004.
• 5. Johnson D. S., McGeoch L. A., The Traveling Salesman Problem: A Case Study in Local Optimization, John Wiley and Sons, London 1997.
• 6. Kernighan B.W., Lin S., An efficient heuristic procedure for partitioning graphs, Bell Systems Technical Journal no 49.
• 7. Lin S., Computer solutions of the traveling salesman problem, Bell Systems Technical Journal no 44.
• 8. Ochelska – Mierzejewska J., Rozwiązanie problemu komiwojażera przy użyciu algorytmu genetycznego, Logistyka nr 1/2016, ILiM, Poznań 2016.
• 9. Rutczyńska-Wdowiak K., Jabłoński N., Algorytm mrówkowy w problemie komiwojażera, Autobusy nr 6/2016.
• 10. Witkowski K., Tanona K., Analiza kosztów transportu drogowego, Logistyka nr 5/2013, ILiM, Poznań 2013.
• 11. http://algorytmy.ency.pl (08.05.2018).
• 12. http://www.mini.pw.edu.pl (03.05.2018).
• 13. http://www.staff.amu.edu.pl (03.05.2018).
• 14. https://xlinux.nist.gov/dads/HTML/christofides.html (09.05.2018).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).