3D travelling salesman problem - heuristics and metaheuristics
| Thesis title: | 3D problém obchodního cestujícího - heuristiky a metaheuristiky |
|---|---|
| Author: | Vávra, Vojtěch |
| Thesis type: | Diplomová práce |
| Supervisor: | Jablonský, Josef |
| Opponents: | Pelikán, Jan |
| Thesis language: | Česky |
| Abstract: | Tato práce se zabývá především problémem obchodního cestujícího ve 3D prostoru. V úvodní části je uvedeno definování problému a rešerše literatury. V teoretické části jsou definovány metody a algoritmy, kterými lze řešit formulovaný problém. Při řešení problému jsou uvedeny metody exaktní, heuristické a metaheuristické. V experimentální části byly implementovány vybrané heuristické a metaheuristické metody v prostředí jazyka R i s několika doplňky, jako je například vizualizace řešení. V rámci vyhodnocení jsou metody porovnávány mezi sebou a nejlepší doporučeny podle výpočetního času i hodnoty účelové funkce k řešení uvedeného problému. |
| Keywords: | metaheuristiky; heuristiky; TSP; problém obchodního cestujícího; jazyk R; mezihvězdné cestování |
| Thesis title: | 3D travelling salesman problem - heuristics and metaheuristics |
|---|---|
| Author: | Vávra, Vojtěch |
| Thesis type: | Diploma thesis |
| Supervisor: | Jablonský, Josef |
| Opponents: | Pelikán, Jan |
| Thesis language: | Česky |
| Abstract: | This thesis deals primarily with travelling salesmen problem in 3D. In introductory part we deliver formulation of the proposed problem and literature review. In the theoretical part we define exact, heuristic and metaheuristic methods for solving the proposed problem. In the experimental part were implemented selected heuristic and metaheuristic methods in the environment of language R with several addition for example visualization of the solution. In conclusion of the thesis all used models are compared and best recommended according to computational time and value of the objective function for solving mentioned problem. |
| Keywords: | TSP; heuristics; metaheuristics; language R; star tour; travelling salesman problem |
Information about study
| Study programme: | 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: | 20. 10. 2021 |
|---|---|
| Date of submission: | 1. 5. 2022 |
| Date of defense: | 7. 6. 2022 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/78460/podrobnosti |