Traveling salesman problem: approach to optimality

• Authors: Radosław Jadczak
• Languages of publication: EN

Abstracts

EN

Traveling Salesman Problem (TSP) is a basic and one of the most important transportation problems in operational logistics. It is also known in the literature as a Chinese postman problem or single vehicle routing problem. TSP can be shortly described as follows. Vehicle starting from the selected city must visit a set of another cities exactly once and return to the starting city in such a way that the total distance of the route is minimized. In this paper first mathematical formulation of decision problem is presented. Then solution strategies of TSP are shown with selected algorithms as examples. In the last part of article, a computational results of selected methods are presented.

Keywords

EN

traveling salesman problem; heuristics; Lin-Kernighan algorithm

• Publisher: Sciendo
• Journal: Przedsiębiorczość i Zarządzanie
• Year: 2014
• Volume: 15
• Issue: 2
• Pages: 157-169

Dates

online

2014-08-15

Contributors

author

Radosław Jadczak

• University of Lodz

References

• Całczyński A. (1992), Metody optymalizacji w obsłudze transportowej rynku, PWE, Wa rszawa.
• Całczyński A., Kędzierska-Stróż D., Orzechowska D., Śleszyński Z. (2000), Elementy badań operacyjnych w zarządzaniu, Wydawnictwo Politechniki Radomskiej, Radom.
• Ignasiak E. (1996), Badania operacyjne, PWE, Warszawa.
• Junhert M., Reinelt G., Rinnaldi G. (1995), The travelling salesman problem in: M.O. Ball et al. (Eds), Handbook in OR&MS, Vol. 7, Elsevier.
• Krawczyk S. (2001), Metody ilościowe w logistyce (przedsiębiorstwa), Academia Oeconomica, Warszawa.
• Lin S., Kernighan B.W. (1973), An effective heuristic for the traveling salesman problem, “Operations Research”, Vol. 21, pp. 498–516.[Crossref]
• Little J.D.C., Murty K.G., Sweeney D.W., Karel C. (1963), An algorithm for the traveling salesman problem, “Operations Research”, Vol. 11.[Crossref]
• Solich R. (1974), Pewne uogólnienia zadania komiwojażera, Prace Centrum Obliczeniowego PAN, Nr 14.
• Sysło M.M. (1984), Optymalizacja kombinatoryczna [w:] T. Kasprzak (red), Optymalizacja dyskretna. Zastosowania ekonomiczne, PWE, Warszawa.
• Szymanowski W. (red.) (1977), Optymalizacja dostaw do sieci punktów sprzedaży z uwzględnieniem warunków ich działalności operatywnej, Uniwersytet Warszawski, Wydział Nauk Ekonomicznych.
• Szymanowski W. (red.) (1979), Optymalizacja dostaw do miejskiej sieci detalicznej, Praca zbiorowa, Instytut Handlu Wewnętrznego i Rynku, Warszawa.

Identifiers

DOI

10.2478/eam-2014-0024