dc.contributor.author |
Míča Ondřej
|
|
dc.date.accessioned |
2016-11-14T08:20:21Z |
|
dc.date.available |
2016-11-14T08:20:21Z |
|
dc.date.issued |
2015 |
|
dc.identifier.isbn |
978-80-7394-536-7 |
eng |
dc.identifier.issn |
2336-6788 |
|
dc.identifier.uri |
http://hdl.handle.net/10195/66616 |
|
dc.description.abstract |
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. |
eng |
dc.format |
p. 116-120 |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Jihočeská univerzita v Českých Budějovicích |
eng |
dc.relation.ispartof |
Proceedings of the 9th International Scientific Conference INPROFORUM: Common challenges - Different solutions - Mutual dialogue |
eng |
dc.rights |
Práce není přístupná |
eng |
dc.subject |
Travelling salesman problem |
eng |
dc.subject |
Metaheuristic optimization |
eng |
dc.subject |
Tabu search |
eng |
dc.subject |
Simulated annealing |
eng |
dc.subject |
Genetic algorithm |
eng |
dc.subject |
Ant colony optimization algorithm |
eng |
dc.subject |
Úloha obchodního cestujícího |
cze |
dc.subject |
Metaheuristické metody |
cze |
dc.subject |
Tabu search |
cze |
dc.subject |
Simulované žíhání |
cze |
dc.subject |
Genetický algoritmus |
cze |
dc.subject |
Metoda mravenčí kolonie |
cze |
dc.title |
Comparison of metaheuristic methods by solving travelling salesman problem |
eng |
dc.title.alternative |
Porovnání metaheuristických metod prostřednictvím řešení úlohy obchodního cestujícího |
cze |
dc.type |
ConferenceObject |
eng |
dc.description.abstract-translated |
Ú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. |
cze |
dc.event |
INPROFORUM 2015: 9th International Scientific Conference (05.11.2015 - 06.11.2015) |
eng |
dc.peerreviewed |
yes |
eng |
dc.publicationstatus |
postprint |
eng |
dc.identifier.wos |
000383863800026 |
|
dc.identifier.obd |
39875074 |
|