Optimization of a a route for collecting waste with Traveling Salesman Problem
| Thesis title: | Optimalizace trasy svozu odpadu pomocí úlohy obchodního cestujícího |
|---|---|
| Author: | Trnka, Zdeněk |
| Thesis type: | Bakalářská práce |
| Supervisor: | Borovička, Adam |
| Opponents: | Pelikán, Jan |
| Thesis language: | Česky |
| Abstract: | Tato bakalářská práce se zabývá optimalizací délky trasy určené pro svoz komunálního odpadu společnosti FCC Česká republika, s.r.o. Pro vyřešení uvedeného reálného případu hledá práce nejvhodnější metodu. Takto formulovaný ekonomický model lze řešit pomocí úlohy obchodního cestujícího, jejíž matematický model, modifikace a možnosti řešení jsou podrobně popsány. K vyřešení úlohy obchodního cestujícího je možné použít exaktní metody, které jsou vhodné pro méně rozsáhlé příklady, nebo heuristické metody, které však nemusejí poskytnout optimální řešení. Úloha obchodního cestujícího zde bude řešena pomocí modelovacího softwaru MPL for Windows. Dále budou použity dvě heuristické metody - metoda nejbližšího souseda a metoda výhodnostních čísel. Kvůli zvýšení efektivity byla zvolena i modifikace úlohy obchodního cestujícího s časovými okny, která bude taktéž řešena v MPL for Windows. V závěru práce budou výsledky shrnuty a porovnány jak mezi sebou tak se stávající firemní trasou. |
| Keywords: | Heuristické metody; Úloha obchodního cestujícího; MPL for Windows |
| Thesis title: | Optimization of a a route for collecting waste with Traveling Salesman Problem |
|---|---|
| Author: | Trnka, Zdeněk |
| Thesis type: | Bachelor thesis |
| Supervisor: | Borovička, Adam |
| Opponents: | Pelikán, Jan |
| Thesis language: | Česky |
| Abstract: | The Bachelor's dissertation deals with optimization of route designed for collecting communal waste of a company FCC Czech Republic, Ltd. Dissertation search for the most suitable method to solve the real-life example. So formed economic model is to be solved via Traveling Salesman Problem method, whose mathematical model, modifications and solutions options are described in detail in theoretical sections of the dissertation. Exact methods, which are suitable for smaller problem, and heuristic methods, which did not have to give optimal solution, can be used for solving the Traveling Salesman Problem. The Traveling Salesman Problem will be solved here with help of modeling software MPL for Windows. There will be also used two heuristic approaches - Nearest Neighbor algorithm and Savings method. Due to increasing efficiency, a modified Traveling Salesman Problem with Time Windows will be used and solved also through MPL for Windows. To close the dissertation, the result will be summarized and compare firstly among each other and secondly against current company route. |
| Keywords: | Traveling Salesman Problem; MPL for Windows; Heuristic methods |
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: | 22. 8. 2016 |
|---|---|
| Date of submission: | 31. 5. 2017 |
| Date of defense: | 22. 6. 2017 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/58249/podrobnosti |