Application of Heuristics on Vehicle Routing Problem

Thesis title: Aplikace heuristik při řešení rozvozní úlohy
Author: Gerlich, Michal
Thesis type: Diplomová práce
Supervisor: Fábry, Jan
Opponents: Pelikán, Jan
Thesis language: Česky
Abstract:
S úlohami operačního výzkumu se člověk v praktickém světě potkává velice často. Tato práce se zabývá řešením jedné ze specifických částí operačního výzkumu - diskrétních úloh. Nejznámějším druhem této skupiny problémů jsou okružní úlohy. Tato práce konkrétně řeší rozvozní problém, který hledá optimální rozmístění odběratelů do okruhů, ve kterých hraje roli kapacita používaného vozidla a velikosti požadavků zákazníků. Cílem je rozmístění odběratelů do okruhů, jejichž celková vzdálenost je minimální. Data, potřebná pro řešení tohoto problému, vycházejí z reálné situace Pivovaru Svijany a.s. Svou povahou se jedná o rozvozní problém s více vozidly různých kapacit a odběrateli s dělenou poptávkou. Vzhledem k rozsahu úlohy není možné pro řešení problému využít matematický model úlohy, ale je jej potřeba vyřešit pomocí některé ze známých heuristik. Úloha je řešena upravenou metodou výhodnostních čísel. Tato heuristika je naprogramována prostřednictvím jazyka Visual Basic for Applications nad MS Excel. Práce mimo jiné analyzuje citlivost výstupů na zadaných hodnotách některých parametrů, které předem nejsou pevně stanoveny a jejichž konkrétní nastavení záleží na uživateli. Na konci práce je popsán nejlepší nalezený výsledek a porovnán s výchozím řešením Pivovaru Svijany.
Keywords: rozvozní úlohy; diskrétní modely; metoda výhodnostních čísel; heuristiky
Thesis title: Application of Heuristics on Vehicle Routing Problem
Author: Gerlich, Michal
Thesis type: Diploma thesis
Supervisor: Fábry, Jan
Opponents: Pelikán, Jan
Thesis language: Česky
Abstract:
This thesis deals with solving a real case from one specific part of Operations Research -- Discrete Models. The case can be classified as Vehicle Routing Problem (VRP) which is a subset of classical Travelling Salesman Problem (TSP). The VRP is modified TSP when requirements of customers and capacities of trucks play role. The data needed for calculations were taken from the real situation of Pivovar Svijany a.s. The problem can be defined as VRP with cars with different capacities and split delivery. Even though the mathematic model of the problem is known and described in the thesis, the size of the problem is too big to be optimized. Therefore heuristic was used to solve it. Because of the good computational results in the past the savings algorithm was chosen. Its model was set using Visual Basic for Applications (VBA). The thesis (among others) analyses the sensitivity of the output on the values of the factors that can be chosen by the analyst. At the end of the thesis the best found solution is presented and the initial and the new scheme of the circles are compared.
Keywords: Discrete Models; Vehicle Routing Problem; Heuristics; Savings Algorithm

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: 4. 1. 2011
Date of submission: 10. 5. 2011
Date of defense: 1. 6. 2011
Identifier in the InSIS system: https://insis.vse.cz/zp/29705/podrobnosti

Files for download

    Last update: