Dualizm logistyczno-kombinatoryczny zadania komiwojażera

• Autorzy: Ficoń Krzysztof

Identyfikatory

DOI

10.5604/01.3001.0012.7153

Warianty tytułu

EN

Logistic-Combinatorial Dualism of Setting the Travelling Salesman

• Języki publikacji: PL

Abstrakty

PL

W pracy został przedstawiony dualny charakter problemu komiwojażera (TPS –Travelling Salesman Problem), który może być jednocześnie rozpatrywany jako utylitarne zadanie transportowe według kryteriów logistycznych oraz jako złożony problem kombinatoryczny optymalizacji dyskretnej. W aspekcie optymalizacyjnym zadanie TSP należy do problemów NP-zupełnych, dla których w ogólności nie istnieją efektywne metody rozwiązań. Ze względu na bardzo szeroki zakres logistycznych aplikacji zadania TSP, dokonano prezentacji najbardziej popularnych metod jego rozwiązania. Szczególną uwagę zwrócono na nowoczesne podejście oparte na metodach sztucznej inteligencji i algorytmach mrówkowych. Klasyczny problem TSP jest szczególnym przypadkiem bardzo ważnego we współczesnej logistyce wielowymiarowego problemu marszrutacji rzutującego m.in. na globalne koszty działalności transportowej i logistycznej.

EN

At the work described dual character of the vehicle routing stayed (TPS – Travelling Salesman Problem) which can simultaneously be considered as the utilitarian transport task according to logistic criteria and as a combinatorial many-sided problem of discreet optimization. In the operational research aspect the TSP task is included in problems NP-complete, which in general effective methods of solutions don’t exist for. On account of very wide range of logistic applications of the TSP task they made the pre-sentation the most of popular methods of untying him. They paid special attention to the modern attempt based on methods of the artificial intelligence and ant algorithms. The classic TSP problem is a special case very much important in the contemporary logistics of the multidimensional problem route projecting among others onto total costs of transport and logistic activity.

Słowa kluczowe

PL

algorytm; logistyka; komiwojażer; metody; optymalizacja

EN

algorithms; logistics; travelling salesman; methods; optimization

• Wydawca: Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego
• Czasopismo: Systemy Logistyczne Wojsk
• Rocznik: 2015
• Tom: Vol. 42, no. 1
• Strony: 45--64
• Opis fizyczny: Bibliogr. 35 poz., rys., tab.

Twórcy

autor

Ficoń Krzysztof

• Akademia Marynarki Wojennej, Wydział Dowodzenia i Operacji Morskich

Bibliografia

• [1] Aarts E., Lenstra J. (2003), Local search in combinatorial optimization, John Wiley & Sons.
• [2] Applegate D. L., Bixby R. E., Chvátal V., Cook W. J. (2007), The Traveling Salesman Problem: A Computational Study, Lanchester Prize, Princeton University Press.
• [3] Arabas J. (2004), Wykłady z algorytmów ewolucyjnych, WNT, Warszawa.
• [4] Bozarth C., Handfield R. B. (2007), Wprowadzenie do zarządzania operacjami i łańcuchem dostaw, Helion S.A., Gliwice.
• [5] Christopher M. (1992), Logistyka i zarządzanie łańcuchem podaży, Wyd. PSB, Kraków.
• [6] Clerc M. (2000), Discrete Particle Swarm Optimization Illustrated by the Travelling Salesman Problem.
• [7] Coffman E. C. (red.) (1980), Teoria szeregowania zadań, WN-T, Warszawa.
• [8] Cook W. J. (2012), In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton University Press.
• [9] Cormen T. H., Leiserson Ch. E., Rivest R. L., Stein C. (2007), Wprowadzenie do algorytmów, WN-T, Warszawa.
• [10] Davendra D. (2010), Traveling Salesman Problem, Theory and Applications, InTech.
• [11] Deo N. (1980), Teoria grafów i jej zastosowanie w technice i informatyce, Warszawa, PWN.
• [12] Do Tianrui R., Yong L. X. (2010), Computational Intelligence, World Scientific Publishing Company.
• [13] Dorigo M., Maniezzo V., Colorni A. (1996), The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics – Part B, 26 (1).
• [14] Dorigo M., Stützle T. (2004), Ant Colony Optimization, MIT Press.
• [15] Duch W., Mandziuk J. (2011), Challenges for Computational Intelligence, Springer.
• [16] Ficoń K. (2006), Badania operacyjne stosowane. Modele i aplikacje, BEL Studio, Warszawa.
• [17] Ficoń K. (2013), Sztuczna inteligencja. Nie tylko dla humanistów, BEL Studio, Warszawa.
• [18] Glover F. (1986), Future Paths for Integer Programming and Links to Artificial Intelligence, Computer and Operations Research, vol. 13, no. 5.
• [19] Hall S. N. (2012), A Group Theoretic Tabu Search Approach to the Traveling Salesman Problem, Biblioscholar.
• [20] Holland J. H. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press.
• [21] Kosiński R. A. (2007), Sztuczne sieci neuronowe. Dynamika nieliniowa i chaos, WNT, Warszawa.
• [22] Kozubski J. J. (2000), Wprowadzenie do badań operacyjnych, Wyd. UG, Gdańsk.
• [23] Krawczyk S. (1996), Badania operacyjne dla menedżerów, Wyd. AE, Wrocław.
• [24] Kulikowski J. J. (1986), Zarys teorii grafów. Zastosowania w technice, PWN, Warszawa.
• [25] Kwaśnicka H. (1999), Obliczenia ewolucyjne w sztucznej inteligencji, Wyd. PW, Wrocław.
• [26] Metropolis N. et al. (1953), Equation of State Calculations by Fast Computing Machines, The Journal of Chemical Physics 21 (6), 108.
• [27] Michalewicz Z. (1998), Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa.
• [28] Nilsson C. (2003), Heuristics for the traveling salesman problem, Department of Computer Science, Linkoping University.
• [29] Penc J. (1997), Leksykon biznesu, AW Placet, Warszawa.
• [30] Pszczołowski T. (1978), Mała encyklopedia prakseologii i teorii organizacji, Ossolineum, Wrocław – Warszawa – Kraków – Gdańsk.
• [31] Radzikowski W., Sarjusz-Wolski Z. (1994), Metody optymalizacji decyzji logistycznych, Wyd. UW, Toruń.
• [32] Ramani G. (2011), Travelling Salesman Problem (TSP) optimization through Genetic Algorithm: Improvised solution to VLSI Detailed Routing and National Tour Paperback – September 8.
• [33] Rutkowski L. (2006), Metody i techniki sztucznej inteligencji, WN PWN, Warszawa.
• [34] Tadeusiewicz R. (1993), Sieci neuronowe, Akademicka Oficyna Wydawnicza RM.
• [35] TSPLIB. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (15.01.2015).