Heuristic for optimization of vehicle routes

Thesis title: Heuristika pro optimalizaci tras od dodavatelů
Author: Daniel, Marek
Thesis type: Diplomová práce
Supervisor: Pelikán, Jan
Opponents: Fábry, Jan
Thesis language: Česky
Abstract:
Cílem diplomové práce je nalézt a porovnat možnosti řešení rozsáhlého svozního problému s více druhy zboží a heterogenním vozovým parkem. Nejdříve jsou prozkoumány již známé modifikace úlohy obchodního cestujícího a rozvozní úlohy, poté jsou popsány metody, kterými je možné tyto problémy řešit. To jsou především exaktní optimalizační metody, heuristiky a metaheuristiky.V hlavní části práce je zapsán matematický model řešené úlohy a vytvořena heuristika v jazyce VBA. Po podrobném popisu heuristiky je provedeno srovnání výsledků získaných z MPL a z heuristiky. U úloh menších rozměrů je řešení z heuristiky průměrně horší o 9 % než optimální řešení nalezené v MPL. U větších úloh, kde MPL do 30 minut optimum nenajde, je porovnání provedeno s nejlepším dosud nalezeným řešením. V takovém případě nachází heuristika průměrně o 4,8 % horší řešení, ale ve významně kratším čase.
Keywords: heuristika; MPL; optimalizace tras vozidel; svozní problém; VBA
Thesis title: Heuristic for optimization of vehicle routes
Author: Daniel, Marek
Thesis type: Diploma thesis
Supervisor: Pelikán, Jan
Opponents: Fábry, Jan
Thesis language: Česky
Abstract:
The goal of the master’s thesis is to find and compare the possible solutions of a large Vehicle Routing Problem with multiple types of product and heterogenous fleet. Firstly, the already known modifications of the Traveling Salesmen Problem and the Vehicle Routing Problem are explored. Next, the methods to solve such problems are introduced – the optimization exact methods, heuristics and metaheuristics.In the main chapter of the thesis, the mathematical model of the problem at hand is formulated and a new heuristic to solve the problem is implemented in VBA. A detailed description of the heuristic is provided and a comparison of the results obtained from MPL and the heuristic is made. For small sample problems, the heuristic finds a solution which is on average 9 % worse than the optimal solution found by MPL. For large problems, MPL cannot find the optimal solution within 30 minutes, therefore the comparison is made to the best solution MPL found within the given time. In such cases, the solution from the heuristic is on average worse by 4.9 % but can be found within several seconds.
Keywords: heuristic; MPL; VBA; vehicle routing 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: 24. 9. 2019
Date of submission: 24. 6. 2020
Date of defense: 27. 8. 2020
Identifier in the InSIS system: https://insis.vse.cz/zp/70714/podrobnosti

Files for download

    Last update: