Planning a journey through english cities – application of Travelling Salesman Problem
| Thesis title: | Plánování cesty po anglických městech – aplikace úlohy obchodního cestujícího |
|---|---|
| Author: | Matura, Ondřej |
| Thesis type: | Bakalářská práce |
| Supervisor: | Skočdopolová, Veronika |
| Opponents: | Borovička, Adam |
| Thesis language: | Česky |
| Abstract: | Tato bakalářská práce se zabývá úlohou obchodního cestujícího, také známou jako okružní dopravní problém, která se dá formulovat jako úloha celočíselného lineárního programování, a která má v praxi široké využití (např. plánování optimální trasy výletu, apod.). Cílem této práce je použít model úlohy obchodního cestujícího k nalezení nejvýhodnějšího okruhu po 16 vybraných anglických městech s možnostmi přepravy autobusovou nebo železniční dopravu, s přihlédnutím na finanční a časová kritéria. Hledání takovýchto cest má využití zejména v oblasti cestovního ruchu. Při řešení úlohy obchodního cestujícího byla použita heuristická metoda nejbližšího souseda a metoda výhodnostních čísel (Clark, Wright). Provedenými experimenty jsem došel k předpokládaným výsledkům a to sice, že železniční doprava je přibližně dvakrát finančně nákladnější, ale o polovinu méně časově náročnější než autobusová doprava mezi vybranými městy v Anglii. Výsledky této práce umožňují provést cestu po anglických městech za použití různých kombinací obou zmíněných způsobů dopravy. |
| Keywords: | autobusová doprava; celočíselné lineární programování; úloha obchodního cestujícího; železniční doprava |
| Thesis title: | Planning a journey through english cities – application of Travelling Salesman Problem |
|---|---|
| Author: | Matura, Ondřej |
| Thesis type: | Bachelor thesis |
| Supervisor: | Skočdopolová, Veronika |
| Opponents: | Borovička, Adam |
| Thesis language: | Česky |
| Abstract: | This bachelor thesis uses the travelling salesman problem, also known as circular traffic problem that can be formulated as an integer linear programming, and which in practice has widespread use (eg. optimum route planning trip, alike.). The aim of this work is to apply the model of the travelling salesman problem to find the most suitable circuit after 16 selected English towns with transportation by bus or by rail, taking into account financial and time criteria. Finding these paths has particular application in the field of tourism. To solve the travelling salesman problem heuristic of nearest neighbour and Clark-Wright method were used. After experiments were performed, I came to anticipated results and that is that rail transport is approximately twice more expensive, but half the time consuming than bus service between selected cities in England. The results of this study make it possible to carry out a journey through English towns using various combinations of both these modes of transport. |
| Keywords: | rail transport; bus service; integer linear programming; Travelling Salesman Problem |
Information about study
| Study programme: | Kvantitativní metody v ekonomice/Matematické metody v ekonomii |
|---|---|
| Type of study programme: | Bakalářský studijní program |
| Assigned degree: | Bc. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Econometrics |
Information on submission and defense
| Date of assignment: | 11. 3. 2014 |
|---|---|
| Date of submission: | 1. 6. 2015 |
| Date of defense: | 24. 6. 2015 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/46927/podrobnosti |