Use of Software Concorde for the Travelling Salesman Problem
| Thesis title: | Využití softwaru Concorde pro řešení úlohy obchodního cestujícího |
|---|---|
| Author: | Šejhl, Jan |
| Thesis type: | Bakalářská práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Sokol, Ondřej |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | heuristiky; úloha obchodního cestujícího; Concorde |
| Thesis title: | Use of Software Concorde for the Travelling Salesman Problem |
|---|---|
| Author: | Šejhl, Jan |
| Thesis type: | Bachelor thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Sokol, Ondřej |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | heuristics; TSP; Concorde |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Statistika a ekonometrie |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 9. 12. 2015 |
|---|---|
| Date of submission: | 30. 4. 2016 |
| Date of defense: | 21. 6. 2016 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/57322/podrobnosti |