Optimization of wine delivery by means of the traveling salesman problem

Bakalářská práce se zabývá analýzou dvou okružních tras určených na rozvoz vína vyrobeného společností Vinařské závody Topoľčianky, s.r.o. s cílem minimalizovat počet ujetých kilometrů na daných trasách, což povede ke snížení přepravních nákladů společnosti. Uvedený problém je řešen prostřednictvím modelovacího softwaru MPL for Windows, ve kterém je aplikován model úlohy obchodního cestujícího. Velmi podrobně jsou popsány nalezené optimální trasy, které jsou následně i porovnány s aktuálně využívanými trasami. Vyvozuje se, že nalezené optimální řešení skutečně zaručí menší, resp. minimální počet ujetých kilometrů na obou uvažovaných trasách. Práce se zabývá úlohou obchodního cestujícího také z teoretického aspektu, jakým je například historický vývoj úlohy, formulace matematického modelu či výpočetní složitost. Obsahuje také krátký přehled modifikací úlohy a vybraných metod řešení včetně heuristik. Právě aplikací teoretických poznatků o úloze obchodního cestujícího se podařilo získat optimální řešení analyzovaného praktického problému, které je výhodnější než řešení aktuální.

The bachelor's thesis deals with the analysis of two circular routes intended for the distribution of wine produced by the company Vinárske závody Topoľčianky, s.r.o. in order to minimize the number of kilometers traveled on the routes, which will lead to a reduction in the company's transport costs. This problem is solved by means of modeling software MPL for Windows, in which a model of the traveling salesman problem is applied. The found optimal routes are described in a very detailed way and are consequently compared with the currently used routes. It is concluded that the optimal solution found will admittedly guarantee a smaller, or more precisely the minimal number of kilometers traveled on both routes considered. The work also deals with the traveling salesman problem from a theoretical aspect, such as the historical development of the problem, the formulation of a mathematical model or computational complexity. It also contains a brief overview of problem modifications and selected solution methods, including heuristics. It was the application of theoretical knowledge about the traveling salesman problem that managed to obtain an optimal solution to the analyzed practical problem, which is more advantageous than the current solution.