Travelling salesman problem – delivery of postal items
| Thesis title: | Úloha obchodního cestujícího - doručování poštovních zásilek |
|---|---|
| Author: | Říha, Vojtěch |
| Thesis type: | Bakalářská práce |
| Supervisor: | Borovička, Adam |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | Cílem práce je navrhnout postup doručování poštovních zásilek pomocí poznatků z úlohy obchodního cestujícího. V první části je stručně charakterizován historický vývoj se zaměřením na řešení reálných úloh v čase. Druhá část popisuje problematiku úlohy obchodního cestujícího s jedním obchodním cestujícím a s více obchodními cestujícími. Důraz je kladen na heuristické algoritmy, především na heuristiku nejbližšího souseda. Zmíněny jsou také různé modifikace úloh obchodního cestujícího. V aplikované části je zpracována reálná úloha doručování poštovních zásilek v rámci dané oblasti s cílem minimalizace celkového času. Pro tento specifický typ úlohy je navržen matematický model a jeho případná obměna pro minimalizaci nejdříve možného času příjezdu vozidla do obce. Ke zpracování optimalizace jsou využity výpočetní softwary MPL a Lingo. Průběžné výsledky těchto programů jsou detailně rozebrány. Vzhledem ke složitosti výpočtu je navržena modifikovaná heuristika nejbližšího souseda, jejíž zpracování je naprogramováno v softwaru MATLAB. Tento postup je podrobně popsán. Je představen záměr snížení koeficientu výše limitu v programu MATLAB a následně jsou tyto výsledky aplikovány. V závěru práce jsou pečlivě analyzovány a porovnány výsledky heuristiky s průběžnými hodnotami MPL. |
| Keywords: | modifikovaná heuristika nejbližšího souseda; doručování poštovních zásilek; okružní úloha s více obchodními cestujícími |
| Thesis title: | Travelling salesman problem – delivery of postal items |
|---|---|
| Author: | Říha, Vojtěch |
| Thesis type: | Bachelor thesis |
| Supervisor: | Borovička, Adam |
| Opponents: | Fábry, Jan |
| Thesis language: | Česky |
| Abstract: | The aim of this thesis is to propose the process of delivering postal items by using general knowledge of the travelling salesman problem. The first part briefly describes the historical evolution concentrating on solving real problems. The second part describes the travelling salesman problem and the multiple travelling salesman problem. Emphasis is placed on heuristic algorithms, primarily on the nearest neighbour algorithm. Various modifications of the travelling salesman problems are also mentioned. In the part of the application a real problem of delivering postal items in a given area is handled in order to minimize the total time spend on delivery. For this specific type of problem a mathematical model is design as well as its possible modification for minimizing the earliest possible time of vehicle's arrival to the village. For the optimization, computer software MPL and Lingo are used. Interim results of these calculations are described in detail. Due to the complexity of the calculation the modified nearest neighbour algorithm is suggested. Its process is programmed in MATLAB software and is described in detail. In this thesis the intention of reducing the coefficient of the limit in MATLAB is also presented and then these results are applied. In the conclusion the results of heuristic algorithms are carefully analysed and compared with interim results of MPL. |
| Keywords: | multiple travelling salesman problem; modified nearest neighbour heuristic algorithm; delivery of postal items |
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: | 26. 6. 2014 |
|---|---|
| Date of submission: | 1. 5. 2015 |
| Date of defense: | 24. 6. 2015 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/48481/podrobnosti |