Metaheuristic optimalization for routing problems
| Thesis title: | Použití metaheuristik pro řešení okružních dopravních úloh |
|---|---|
| Author: | Novák, Vít |
| Thesis type: | Diplomová práce |
| Supervisor: | Fábry, Jan |
| Opponents: | Melechovský, Jan |
| Thesis language: | Česky |
| Abstract: | Okružní dopravní problémy jsou jedny z nejvýznamnějších představitelů skupiny klasických optimalizačních kombinatorických problémů. Úloha obchodního cestujícího a úlohy z ní odvozené zajímají matematiky a analytiky od doby, kdy byly prvně formulovány, a urychlují vývoj nových metod a přístupů, které později nacházejí uplatnění v celé řadě dalších reálných problémů. Tato práce si klade za cíl demonstrovat užitečnost a flexibilitu ukázaných metaheuristických metod. Výstupy jsou v případě, že je to možné, porovnávány s výstupy alternativních algoritmů nebo známými optimálními řešeními. K dosažení tohoto cíle byla vytvořena VBA aplikace. Výsledky experimentů a fungování aplikace je popsáno v druhé polovině této práce. Čtenáři by tak měl být poskytnut dostatečný návod, jakou cestu se při řešeních podobných úloh lze vydat. |
| Keywords: | úloha kurýrní služby; problém obchodního cestujícího; metoda simulovaného žíhání; metaheuristky |
| Thesis title: | Metaheuristic optimalization for routing problems |
|---|---|
| Author: | Novák, Vít |
| Thesis type: | Diploma thesis |
| Supervisor: | Fábry, Jan |
| Opponents: | Melechovský, Jan |
| Thesis language: | Česky |
| Abstract: | Routing problems are ones of the most famous members of the group of the classical optimalization combinatorial problems. Travelling salesman problem and problems derived from it have been attracting mathematics and analysts, since they were firstly formulated, and accelerating a development of new methods and approaches that can be used for a wide range of another real-life problems. This thesis aims to demonstrate an usefulness and a flexibility of shown metaheristic methods. Results are compared with outputs of alternative algorithms or known optimal solutions where it is possible. To fulfill this goal the VBA application has been developed. The results of experiments are presented and the application is decribed in a second part of this thesis. A reader should be sufficiently instructed which way he could choose to solve similar types of problems |
| Keywords: | traveling salesman problem; metaheuristics; simulated annealing; messenger problem |
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: | 31. 5. 2013 |
|---|---|
| Date of submission: | 10. 12. 2013 |
| Date of defense: | 4. 6. 2014 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/43223/podrobnosti |