Využití softwaru Concorde pro řešení úlohy obchodního cestujícího
| Název práce: | Využití softwaru Concorde pro řešení úlohy obchodního cestujícího |
|---|---|
| Autor(ka) práce: | Šejhl, Jan |
| Typ práce: | Bakalářská práce |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Sokol, Ondřej |
| Jazyk práce: | Česky |
| Abstrakt: | Jednou z nejznámějších úloh operačního výzkumu je úloha obchodního cestujícího. Práce je věnována softwaru Concorde a teoretickému pozadí úloh v něm řešeným. První kapitola je zaměřena na formulaci úlohy obchodního cestujícího stejně jako dalším úlohám, které je možné v Concorde řešit. Druhá kapitola je věnována heuristikám zabudovaným v softwaru Concorde. Ve třetí kapitole je popsán samotný software Concorde a jeho ovládání. Závěrečná kapitola je zaměřena na výpočetní experimenty. Na konkrétních příkladech je zde uvedeno porovnání jednotlivých heuristik dle hodnot účelové funkce, stejně tak jako srovnání softwaru Concorde s řešitelem Gurobi na základě výpočetního času. Na základě dosažených výsledků lze konstatovat, že software Concorde je schopný řešit stejnou úlohu v neporovnatelně kratším čase. |
| Klíčová slova: | heuristiky; úloha obchodního cestujícího; Concorde |
| Název práce: | Use of Software Concorde for the Travelling Salesman Problem |
|---|---|
| Autor(ka) práce: | Šejhl, Jan |
| Typ práce: | Bachelor thesis |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Sokol, Ondřej |
| Jazyk práce: | Česky |
| Abstrakt: | The Travelling Salesman Problem is one of the famous exercises of operations research. This Bachelor Thesis offers insights into the software Concorde and the theoretical background of the tasks solved by this software. The first chapter focuses on formulation of the Travelling Salesman Problem and other exercises that can be solved using Concorde. The second chapter describes heuristics integrated in the software Concorde. The third chapter describes the software Concorde and its control. The final chapter contains computational experiments. Using concrete examples, particular heuristics are compared according to values of objective function as well as the comparison of software Concorde with Gurobi optimizer. Based on the results we can conclude that software Concorde is able to solve same exercises in a significantly shorter time when compared to Gurobi optimizer. |
| Klíčová slova: | heuristics; TSP; Concorde |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Statistika a ekonometrie |
|---|---|
| Typ studijního programu: | Bakalářský studijní program |
| Přidělovaná hodnost: | Bc. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra ekonometrie |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 9. 12. 2015 |
|---|---|
| Datum podání práce: | 30. 4. 2016 |
| Datum obhajoby: | 21. 6. 2016 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/57322/podrobnosti |