Original title:
Problém obchodního cestujícího s velkým počtem měst
Translated title:
Large-Scale Travelling Salesman Problem
Authors:
Kukula, Lukáš ; Žaloudek, Luděk (referee) ; Bartoš, Pavel (advisor) Document type: Bachelor's theses
Year:
2011
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Práce se zabývá řešením problému obchodního cestujícího s velkým počtem měst. Snahou je nalézt co nejkvalitnější řešení během krátké doby. Porovnány byly nejpoužívanější heuristiky, z nichž se nejefektivnější ukázala být Lin-Kernighan. Její spojení se stochastickým genetickým algoritmem přineslo v přijatelném čase kvalitnější výsledky než heuristika Lin-Kernighan samotná.
Thesis deals with solving large-scale traveling salesman problem. The aim is to find the best possible solution within a short time. Most widely used heuristics was compared and most efficient proved to be Lin-Kernighan. This heuristic combined with the stochastic algorithm brings even better results than the Lin-Kernighan heuristic itself.
Keywords:
ant colony optimization; hybrid genetic algorithm.; Inver-over; k-opt; Large-scale traveling salesman problem; Lin-Kernighan; simulated annealing; tabu search; hybridní genetický algoritmus.; Inver-over; k-opt; Lin-Kernighan; mravenčí kolonie; Problém obchodního cestujícího s velkým počtem měst; simulované žíhání; zakázané prohledávání
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/187423