Vehicle Routing Problem with Private and Common Carriers
Thesis title: | Rozvozní problém s interním a externím dopravcem |
---|---|
Author: | Zikmund, Adam |
Thesis type: | Diplomová práce |
Supervisor: | Pelikán, Jan |
Opponents: | Fábry, Jan |
Thesis language: | Česky |
Abstract: | Tato diplomová práce se zabývá úlohou z oboru kombinatorické optimalizace s názvem rozvozní problém s interním a externím dopravcem. V této úloze dán úplný neorientovaný symetrický graf a úkolem je uspokojit poptávku ve všech uzlech s minimálními náklady. Doprava může být realizována buďto pomocí interních vozidel, nebo s využitím externího dopravce. Náklady interní dopravy závisí na zdolané vzdálenosti, zatímco externí náklady se odvíjí pouze od hmotnosti požadavků. K řešení úlohy je navrženo několik heuristických metod, které jsou později testovány na třech experimentálních instancích o různých velikostech (ve smyslu počtu zadaných uzlů). Důraz je kladen především na srovnání výsledků uvedených heuristických metod a výsledků dosažených pomocí klasického optimalizačního přístupu, který může vést k horším řešením (v případě rozsáhlejších instancí) z důvodu výpočetní složitosti dané úlohy. |
Keywords: | kombinatorická optimalizace; rozvozní problém; heuristické metody |
Thesis title: | Vehicle Routing Problem with Private and Common Carriers |
---|---|
Author: | Zikmund, Adam |
Thesis type: | Diploma thesis |
Supervisor: | Pelikán, Jan |
Opponents: | Fábry, Jan |
Thesis language: | Česky |
Abstract: | This diploma thesis deals with a problem from the field of combinatorial optimization called Vehicle Routing Problem with Private and Common Carriers (VRPPC). A complete undirected symmetric graph is given. The task is to satisfy demands in all nodes with minimal total costs. There are two possibilities of doing so. Either private fleet or common carrier can be used for the transport of the demanded goods. The private costs depend on the covered distance whereas the common costs are conditional only on the weight of demand. Several heuristic methods for solving this problem are proposed and tested on three experimental instances of different sizes (in terms of number of nodes). Emphasis is primarily put on comparison between the presented heuristic and the classical optimization approach, which can often lead to inferior results (especially in case of larger instances) because of the computational complexity of the given problem. |
Keywords: | heuristic method; Vehicle Routing Problem; combinatorial optimization |
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: | 28. 2. 2017 |
---|---|
Date of submission: | 23. 5. 2017 |
Date of defense: | 12. 9. 2017 |
Identifier in the InSIS system: | https://insis.vse.cz/zp/61072/podrobnosti |