Publikace detail

Comparison of metaheuristic methods by solving travelling salesman problem

Autoři: Míča Ondřej

Rok: 2015

Druh publikace: článek ve sborníku

Název zdroje: Proceedings of the 9th International Scientific Conference INPROFORUM: Common challenges - Different solutions - Mutual dialogue

Název nakladatele: Jihočeská univerzita v Českých Budějovicích

Místo vydání: České Budějovice

Strana od-do: 116-120

Tituly:

Jazyk	Název	Abstrakt	Klíčová slova
cze	Porovnání metaheuristických metod prostřednictvím řešení úlohy obchodního cestujícího	Úloha obchodního cestujícího je základní úlohou operačního výzkumu. Jedná se o NP-těžkou úlohu. Počet přípustných řešení úlohy je velmi vysoký - roste s faktoriálem počtu uzlů v dopravní síti. Proto ani se současnou výpočetní technikou nelze řešit úlohu obchodního cestujícího pomocí exaktního řešení v rozumném čase. Proto se k řešení používají metaheuristické metody, které jsou schopné poskytnout dostatečně kvalitní řešení v reálném čase. Tento příspěvek se zaměřuje na čtyři základní metaheuristické metody: tabu search, simulované žíhání, genetický algoritmus a metodu mravenčí kolonie. Ke srovnání efektivnosti zkoumaných algoritmů je použita odchylka mezi nejlepším získaným a optimálním řešením.	Úloha obchodního cestujícího; Metaheuristické metody; Tabu search; Simulované žíhání; Genetický algoritmus; Metoda mravenčí kolonie
eng	Comparison of metaheuristic methods by solving travelling salesman problem	Travelling salesman problem (TSP) belongs in basic problems of operations research. It is a NP-hard problem. The number of possible solutions of this problem is very high – it increases with the factorial of the number of the nodes at the graph. So even with nowadays computers it takes very large amount of time to solve TSP with exact methods. Therefore TSP is now usually solved with a heuristic (or metaheuristic) techniques, which provides a satisfactory solution in real-time. This paper focuses on four classical metaheuristic methods: tabu search, simulated annealing, genetic algorithm and ant colony optimization algorithm, and compares all algorithms using difference between best given solution and optimal solution as evaluation criterion. Computational results on several standard instances of TSP show efficiency of all scrutinized methods.	Travelling salesman problem; Metaheuristic optimization; Tabu search; Simulated annealing; Genetic algorithm; Ant colony optimization algorithm

Vyhledávání

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Katedry

Pracoviště

Jak nás najdete?

Služby

Často hledáte