Implementace heuristik pro rozvozní problém s časovými okny
| Název práce: | Implementace heuristik pro rozvozní problém s časovými okny |
|---|---|
| Autor(ka) práce: | Trunda, Otakar |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Holý, Vladimír |
| Jazyk práce: | Česky |
| Abstrakt: | Rozvozní problém s časovými okny patří mezi těžké optimalizační problémy. Přestože má tento typ problémů mnoho praktických aplikací, otázka jeho efektivního řešení stále není uspokojivě objasněná. Tato práce se zabývá studiem Rozvozních problémů s časovými okny a návrhem nových algoritmů pro jejich řešení. Jsou zde představené dvě heuristiky a několik navazujících algoritmů, které tyto heuristiky dále rozšiřují. Efektivita navržených postupů je experimentálně ověřena na sadě testovacích dat.Součástí práce je také vytvoření desktopové aplikace, která implementuje navržené algoritmy a poskytuje další funkcionalitu pro usnadnění řešení rozvozních problémů v praxi. Patří mezi ně například generátor pseudo-náhodných zadání problému, vizualizace řešení a podobně. |
| Klíčová slova: | Rozvozní problém s časovými okny; Heuristiky; Dopravní problémy; Kombinatorická optimalizace |
| Název práce: | Implementation of Heuristics for Vehicle Routing Problem with Time Windows |
|---|---|
| Autor(ka) práce: | Trunda, Otakar |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Pelikán, Jan |
| Oponenti práce: | Holý, Vladimír |
| Jazyk práce: | Česky |
| Abstrakt: | Vehicle Routing Problem with Time Windows is a hard optimization problem. Even though it has numerous practical applications, the question of solving it efficiently has not been satisfyingly solved yet. This thesis studies the Vehicle Routing Problem with Time Windows and presents several new algorithms for solving it.There are two heuristics presented here, as well as several more complex algorithms which use those heuristics as their components. The efficiency of presented techniques is evaluated experimentally using a set of test samples.As a part of this thesis, I have also developed a desktop application which implements presented algorithms and provides a few additional features useful for solving routing prob-lems in practice. Among others, there is a generator of pseudo-random problem instances and several visualization methods. |
| Klíčová slova: | Vehicle Routing Problem with Time Windows; Heuristics; Transportation Problems; Combinatorial Optimization |
Informace o studiu
| Studijní program / obor: | Aplikovaná informatika/Kognitivní informatika |
|---|---|
| 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 informačních technologií |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 28. 2. 2017 |
|---|---|
| Datum podání práce: | 24. 4. 2017 |
| Datum obhajoby: | 31. 5. 2018 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/61075/podrobnosti |