Practical application of the Travelling Salesman Problem
| Thesis title: | Praktická aplikace okružního dopravního problému |
|---|---|
| Author: | Bushkov, Denis |
| Thesis type: | Bakalářská práce |
| Supervisor: | Kobzareva, Maria |
| Opponents: | Borovička, Adam |
| Thesis language: | Česky |
| Abstract: | Tato bakalářská práce se zabývá okružním dopravním problémem, který je též nazýván úloha obchodního cestujícího a je hodně využíván v praxi. Podstatou této úlohy je, že musíme navštívit každé požadované místo právě jednou a vrátit se zpět do výchozího bodu. Cílem úlohy je nalezení nejlepší cesty, a to nejčastěji z hlediska celkové vzdálenosti, času stráveného na cestě nebo nejnižších nákladů. První část této práce je věnovaná lineárnímu programování, distribučním úlohám a teoretickým aspektům, které budou využívány při simulaci různých dopravních problémů. Druhá část práce je zaměřená na praktickou aplikaci úlohy obchodního cestujícího, kde se snažíme najít nejlepší možnou cestu mezi 15 městy za vybraných omezujících podmínek. Cílem této části práce je ukázat, že optimalizační algoritmy mohou pomoci ušetřit čas, přispět ke snížení nákladů a usnadnit práci při plánovaní. |
| Keywords: | Distribuční úlohy; Úloha obchodního cestujícího; Lineární programování |
| Thesis title: | Practical application of the Travelling Salesman Problem |
|---|---|
| Author: | Bushkov, Denis |
| Thesis type: | Bachelor thesis |
| Supervisor: | Kobzareva, Maria |
| Opponents: | Borovička, Adam |
| Thesis language: | Česky |
| Abstract: | This bachelor's thesis deals with the Travelling Salesman Problem, which has a wide practical use. The core of the problem is, that we have to visit every required place exactly once and return back to the starting point. The objective is to find the best route, according to total distance, time spent or total expenses. The first part of the thesis is devoted to linear programming, distibution problems and theoretical aspects, that will be used in the simulation of different transportation probems. The second part is focused on practical application of the Travelling Salesman Problem in order to find the best possible route between 15 places in Europe according to restrictive conditions. The goal of this part is to show the reader that the optimization algorithms can help to save time, money and to make planning easier. |
| Keywords: | Distribution problems; Travelling Salesman Problem; Linear programming |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| 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: | 3. 3. 2015 |
|---|---|
| Date of submission: | 8. 6. 2015 |
| Date of defense: | 24. 6. 2015 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/51856/podrobnosti |