Czasopismo
Tytuł artykułu
Warianty tytułu
Travelling Salesman Problem - Case Study
Języki publikacji
Abstrakty
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. (abstrakt oryginalny)
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. (original abstract)
Twórcy
autor
- Wojskowa Akademia Techniczna w Warszawie
autor
- Wojskowa Akademia Techniczna w Warszawie
autor
- Wojskowa Akademia Techniczna w Warszawie
Bibliografia
- Michalewicz Z., Algorytmy genetyczne+ struktury danych= programy ewolucyjne, Wydawnictwo Naukowo-Techniczne, Warszawa 2003.
- Cormen T.H., Leiserson C.E., Rivest R.L., Stein C., Introduction to Algorithms, Massachusetts Institute of Technology, London 2009.
- Ignasiak E. (red.)., Badania operacyjne, PWE, Warszawa 2001.
- Dziamski O., Współczesne metody automatycznego planowania dystrybucji towarów, Logistyka nr 6/2004, ILiM, Poznań 2004.
- Johnson D. S., McGeoch L. A., The Traveling Salesman Problem: A Case Study in Local Optimization, John Wiley and Sons, London 1997.
- Kernighan B.W., Lin S., An efficient heuristic procedure for partitioning graphs, Bell Systems Technical Journal no 49.
- Lin S., Computer solutions of the traveling salesman problem, Bell Systems Technical Journal no 44.
- Ochelska - Mierzejewska J., Rozwiązanie problemu komiwojażera przy użyciu algorytmu genetycznego, Logistyka nr 1/2016, ILiM, Poznań 2016.
- Rutczyńska-Wdowiak K., Jabłoński N., Algorytm mrówkowy w problemie komiwojażera, Autobusy nr 6/2016.
- Witkowski K., Tanona K., Analiza kosztów transportu drogowego, Logistyka nr 5/2013, ILiM, Poznań 2013.
- http://algorytmy.ency.pl (08.05.2018).
- http://www.mini.pw.edu.pl (03.05.2018).
- http://www.staff.amu.edu.pl (03.05.2018).
- https://xlinux.nist.gov/dads/HTML/christofides.html (09.05.2018).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ekon-element-000171536931