Heuristické metody pro řešení úlohy obchodního cestujícího s časovými okny
| Název práce: | Heuristické metody pro řešení úlohy obchodního cestujícího s časovými okny |
|---|---|
| Autor(ka) práce: | Bartoň, Jan |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Borovička, Adam |
| Jazyk práce: | Česky |
| Abstrakt: | Tato práce se zabývá heuristickými metodami v úlohách obchodního cestujícího s časovými okny. Představeno je pět heuristik založených na různých přístupech a principech k řešení okružních úloh. Jsou jimi metoda nejbližšího souseda, modifikovaný přiřazovací problém, vkládací heuristika, algoritmus mravenčí kolonie a variabilní lokální prohledávání. Představen byl i exaktní algoritmus vystavěný na principu větvení a mezí. Všechny heuristiky vychází z přední odborné literatury, je zde však navrženo několik úprav a zjednodušení. Každá z heuristik je v práci detailně popsána a demonstrována na ilustračním příkladu. Dále jsou pak všechny heuristiky implementovány v rámci statistického softwaru R a testovány na vzorových úlohách. Nejlepších výsledků dosahují algoritmus mravenčí kolonie a variabilní lokální prohledávání, které se tak jeví k řešení těchto úloh nejvhodnější. Práce rovněž dokazuje výhodnost použití heuristických metod namísto exaktního algoritmu, který se ukázal jako neefektivní, jelikož nedokázal vzorové úlohy řešit v akceptovatelném čase. |
| Klíčová slova: | diskrétní modely; heuristiky; úloha obchodního cestujícího s časovými okny; optimalizace; okružní úlohy |
| Název práce: | Heuristic methods for solving travelling salesman problem with time windows |
|---|---|
| Autor(ka) práce: | Bartoň, Jan |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Fábry, Jan |
| Oponenti práce: | Borovička, Adam |
| Jazyk práce: | Česky |
| Abstrakt: | This thesis covers the topic of heuristic approaches in the travelling salesman problem with time windows. Five heuristics are introduced, each of them represents different approach and principles for solving route problems. These are nearest neighbour algorithm, modified assignment problem, inserting heuristic, ant-colony algorithm and variable neighbourhood search. An exact algorithm based on branch and bound algorithm is introduced as well. Heuristics are derived from algorithms presented in the leading scientific literature. However, several adjustments and simplifications are suggested. Each heuristic is described in detail, as well as demonstrated in example. Also, all heuristics are implemented within the statistical software R and tested via benchmark instances. Ant-colony algorithm and variable neighbourhood search show the best results, which indicates they are the most adequate methods for solving such problems. The thesis also proves the advantage of usage of heuristic approaches instead of the exact algorithm, as the exact algorithm was unable to solve benchmark instances within the acceptable time limit. |
| Klíčová slova: | discrete models; heuristics; travelling salesman problem with time windows; optimization; route problems |
Informace o studiu
| Studijní program / obor: | Kvantitativní metody v ekonomice/Ekonometrie a operační výzkum |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| 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. 11. 2020 |
|---|---|
| Datum podání práce: | 1. 5. 2022 |
| Datum obhajoby: | 7. 6. 2022 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/75049/podrobnosti |