Practical application of travelling salesman problem

Okružní dopravní problém je optimalizační úloha v dnešní době velice využívaná. Slouží k nalezení optimálního okruhu mezi danými n místy, přičemž tato trasa začíná a končí ve stejném místě. V praxi je tato úloha hojně využívána nejen distribučními firmami, ale také například při cestování. V této práci je úloha aplikována na příkladu kontroly památek UNESCO, přičemž cílem je nalézt co nejlepší možnost rozložení cesty. Jednou z variant navštívení všech památek je jeden samostatný cyklus, dále to může být více uzavřených cyklů nebo několik samostatných cest, kde není podmínkou vracet se do původního místa. Pro vyřešení těchto úloh je využit program MPL for Windows 4.2, Academic version. První část práce je věnována teorii okružního dopravního problému a jiných distribučních úloh. Ve druhé části je řešen okružní dopravní problém a jeho modifikace s různými kritérii. V závěru práce jsou jednotlivé možnosti přepravy mezi památkami vyhodnoceny.Travelling salesman problem is a very common optimization problem nowadays. It is used to find the optimal range of n points or places and also the route begins and ends in the same place. This task is widely used in practise not only by distribution companies, but also for instance when travelling. Travelling salesman problem is applied to an example of a control of the world heritage sites UNESCO in this thesis. The aim is to find the best option of the route's layout. The first option of the visiting all the places is one single range, next options are more closed cycles and more separate paths where returning to the start point is not required. The program MPL for Windows 4.2, Academic version is used to solve these problems. The first part of the thesis is dedicated to the theory of travelling salesman problem and to the other distribution problems. The solutions of travelling salesman problem and its modifications with various criteria are in the second part. All transportation options between monuments are evaluated in conclusion of the thesis