The determination of the route for running footraces by a modification Travelling Salesman Problem
| Thesis title: | Vymezení trasy pro běžecký závod modifikací úlohy obchodního cestujícího |
|---|---|
| Author: | Havel, Filip |
| Thesis type: | Diplomová práce |
| Supervisor: | Borovička, Adam |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | Diplomová práce se zabývá nalezením optimální trasy pro běžecký závod. V množině až 251 křižovatek hledá propojení vymezující okruh s předem daným počátečním a současně cílovým místem. Modelově čerpá ze základního tvaru úlohy obchodního cestujícího, jehož primárním úkolem je projít zadanou množinu míst po co nejkratší cestě či v co nejkratším čase a vrátit se zpět do výchozího místa, přičemž každé místo navštíví právě jednou. Trasy hledané touto prací se ovšem v několika aspektech odlišují. Předně není nutné, aby zahrnovaly všechna místa, ty lze navštívit i vícekrát. Výsledná trasa nemá být nejkratší, ale měla by mít určité délkové rozpětí a klíčovým faktorem k optimalizaci jsou získané výškové metry. Řešení exaktními metodami předvede optimalizační software LINGO, pro vyšší výpočetní náročnost však pouze na omezeném rozsahu úlohy, 21 křižovatkách v centru města. Vymezení delší trasy na větší množině křižovatek umožní až odvozené heuristiky s pracovními názvy: nejvzdálenější soused s nejmenším stoupáním a minimální profilová změna. Součástí práce je detailní popis použitého matematického modelu i obecný postup, ukázka a rozbor obou aplikovaných heuristik. |
| Keywords: | křižovatka; vzdálenost; stoupání; trasa; úloha obchodního cestujícího; heuristika |
| Thesis title: | The determination of the route for running footraces by a modification Travelling Salesman Problem |
|---|---|
| Author: | Havel, Filip |
| Thesis type: | Diploma thesis |
| Supervisor: | Borovička, Adam |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | This diploma thesis deals with finding the optimal route for running footraces. This work seeks to find a link that determines a lap with a predetermined beginning and a goal at the same time, given the possibility of 251 intersections. This model is derived from the travelling salesman problem, whose primary task is to pass the specified set of places according to the shortest route or in the shortest possible time and to return back to the starting point while visiting each place only once. Of course, the routes searched for in this work may be differentiated in several aspects. First of all, it is not necessary to include all of the places you can visit multiple times. The resulting route does not have to be the shortest, but it should have a certain span of distance, as the height metrics obtained are the key factor for optimization. A solution with the exact methods will be demonstrated by the LINGO optimization software, but only for a higher computational difficulty with a limited range of tasks, 21 junctions in the city center. Determining a longer route on a larger set of intersections will allow for derived heuristics with working names: the furthest neighbor with the smallest ascent and a minimal profile change. Part of the thesis is a detailed description of the mathematical model used, the general procedure, along with both a demonstration and an analysis of the applied heuristics. |
| Keywords: | distance; ascent; route; travelling salesman problem; heuristic; intersection |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| 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: | 13. 12. 2016 |
|---|---|
| Date of submission: | 30. 6. 2017 |
| Date of defense: | 12. 9. 2017 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/60000/podrobnosti |