Travelling salesman problem – delivery of postal items

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