Original title: Úloha obchodního cestujícího - doručování poštovních zásilek
Translated title: Travelling salesman problem – delivery of postal items
Authors: Říha, Vojtěch ; Borovička, Adam (advisor) ; Fábry, Jan (referee)
Document type: Bachelor's theses
Year: 2014
Language: cze
Publisher: Vysoká škola ekonomická v Praze
Abstract: [cze] [eng]
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. 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: delivery of postal items; modified nearest neighbour heuristic algorithm; multiple travelling salesman problem; doručování poštovních zásilek; modifikovaná heuristika nejbližšího souseda; okružní úloha s více obchodními cestujícími

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/47635

Permalink: http://www.nusl.cz/ntk/nusl-196657


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Bachelor's theses