Traveling across European metropolises: The traveling salesman problem

Tato bakalářská práce se zaměřuje na uplatnění role obchodního cestujícího při plánování cest v evropských metropolích. Cílem bylo najít optimální trasu, která by byla vyhovující z hlediska délky cesty a souvisejících nákladů. V práci byly použity různé modely, které se lišily podle typu minimalizace a druhu použité dopravy, a to buď s využitím autobusové dopravy, automobilové dopravy nebo kombinace autobusové a letecké dopravy. K řešení byla použita modifikace problému obchodního cestujícího, jehož úkolem bylo najít optimální trasu mezi 20 evropskými městy z celkového počtu 30. Modely byly řešeny pomocí optimalizačního systému LINGO v jeho rozšířené verzi a programu MS Excel. Na základě výsledků byly vybrány tři nejvhodnější trasy. Jednalo se o trasu minimalizující čas s využitím autobusové dopravy s náklady 248,55 € a časem 64,35 hodin, trasu minimalizující náklady s využitím automobilové dopravy s náklady 114,58 € a časem 54,67 hodin a trasu minimalizující kombinovanou dopravu s omezením nákladů s náklady 299,72 € a časem 40,18 hodin. Nakonec byla jako konečná trasa vybrána trasa minimalizující čas s omezením nákladů s využitím kombinace autobusové a letecké dopravy.

This Bachelor thesis focuses on the application of the traveling salesman problem to planning a journey across European metropolises. The goal was to find an optimal route that was satisfactory in terms of the duration of travel and associated costs. The work utilized various models that differed according to the type of minimization and the mode of transportation used, employing either bus travel, car travel, or a combination of bus and air travel. To solve the problem, a modification of the traveling salesman problem was used, aimed at finding the optimal route among 20 European cities out of a total of 30. The models were solved using the LINGO optimization system in its extended version and with the help of MS Excel application. Based on the results, three most suitable routes were selected. These included a route minimizing travel time using bus transportation with costs of €248.55 and a duration of 64.35 hours, a route minimizing costs using car travel with costs of €114.58 and a duration of 54.67 hours, and a combined route minimizing time with cost constraints costing €299.72 and lasting 40.18 hours. The final route chosen was time-minimizing route with cost constraints using a combination of bus and air travel.