Heuristic methods for solving travelling salesman problem with time windows
| Thesis title: | Heuristické metody pro řešení úlohy obchodního cestujícího s časovými okny |
|---|---|
| Author: | Bartoň, Jan |
| Thesis type: | Diplomová práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Borovička, Adam |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | diskrétní modely; heuristiky; úloha obchodního cestujícího s časovými okny; optimalizace; okružní úlohy |
| Thesis title: | Heuristic methods for solving travelling salesman problem with time windows |
|---|---|
| Author: | Bartoň, Jan |
| Thesis type: | Diploma thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Borovička, Adam |
| Thesis language: | Česky |
| Abstract: | 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. |
| Keywords: | discrete models; heuristics; travelling salesman problem with time windows; optimization; route problems |
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: | 9. 11. 2020 |
|---|---|
| Date of submission: | 1. 5. 2022 |
| Date of defense: | 7. 6. 2022 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/75049/podrobnosti |