Optimization of packages transport
| Thesis title: | Optimalizace balíkové přepravy |
|---|---|
| Author: | Ptáčková, Michaela |
| Thesis type: | Bakalářská práce |
| Supervisor: | Borovička, Adam |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | Tato bakalářská práce se zabývá především úlohou obchodního cestujícího, která patří mezi distribuční úlohy, a hledáním jejího nejlepšího řešení. Podstatou řešení této úlohy je nalezení nejkratšího možného okruhu, který zahrnuje všechna plánovaná místa a vrací se zpět do výchozího místa. Každé místo musí být navštíveno právě jedenkrát. Existuje řada modifikací jako například úloha obchodního cestujícího s časovými okny, úloha kurýrní služby, dynamická úloha obchodního cestujícího a mnoho dalších. Tyto úlohy můžeme řešit pomocí systémů na podporu modelování nebo pomocí heuristických či metaheuristických metod. Práce je dělena do dvou částí, část teoretickou a praktickou. V teoretické části jsou popsány distribuční úlohy, podrobněji úloha obchodního cestujícího a algoritmy vybraných heuristických metod. Praktická část je zaměřena na aplikaci těchto metod, pomocí kterých se snažíme vypočítat nejkratší možnou trasu, kterou by zaměstnanec společnosti PPL CZ s.r.o. ujel během dne při rozvážení balíků. Řešení je získáváno pomocí optimalizačního systému MPL for Windows, dále pomocí aplikace metody nejbližšího souseda, metody výhodnostních čísel a metody vkládací. V závěru práce jsou shrnuty veškeré výsledky a je provedeno vzájemné porovnání jednotlivých metod výpočtu. |
| Keywords: | distribuční úlohy; úloha obchodního cestujícího; heuristické metody |
| Thesis title: | Optimization of packages transport |
|---|---|
| Author: | Ptáčková, Michaela |
| Thesis type: | Bachelor thesis |
| Supervisor: | Borovička, Adam |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | This bachelor thesis deals mainly with traveling salesman problem which belongs to the distribution problems and looking for its the best solution. The principle of the solutions of this problem is finding the shortest possible route that includes all of the prescribed addresses and returns to the initial location. Every location must be visited exactly once. There are numbers of modifications such as traveling salesman problem with time windows, courier service problem, dynamic traveling salesman problem and many others. We can solve these problems by using the systems to support modelling or using heuristic or metaheuristic methods. The thesis is divided into two parts, theoretical and practical. In the theoretical part the distribution problems are described, the traveling salesman problem in detail and selected algorithms of heuristic methods. The practical part is focused on the application of these methods which helps us to find the shortest possible route, which the PPL's employee would be able to manage during one day when he distributes packages. The solution is obtained by using an optimization system MPL for Windows, by application the nearest neighbour algorithm, the savings algorithm and the insert algorithm. In conclusion of the thesis all results are summarized and a mutual comparison of the calculation methods is performed. |
| Keywords: | traveling salesman problem; distribution problems; heuristic methods |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| 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: | 16. 7. 2013 |
|---|---|
| Date of submission: | 1. 5. 2014 |
| Date of defense: | 24. 6. 2014 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/43630/podrobnosti |