Institutional Repository of Vilnius University
Optimalių maršrutų radimas ir pavaizdavimas taikant algoritmus grafuose /
Abstract
dc:descriptionSolving Optimal Routing Problem by Algorithms in Graphs and Visualizing Results. In my final Bachelors thesis I am looking into on how to help out couriers with their shipments by examining the recorded route data. The theory of graphs was used to get the results and one of the main problems was the task of the Traveling salesman problem solving. In this thesis, the concept of optimal route was defined, where starting the journey from one of the vertice, then visiting all of the remaining ones and finishing the route in the first vertice. The chosen route is the one that has the lowest margin of edges. One of the ways to get the best results was to study examples of similar systems, analyse their advantages and disadvantages. Algorithms capable of finding the Hamiltonian cycle with full search and sorting out, modification of the closest neighbour, partial search of depth and four steps search of depth were created and closely examined. Comprehensive algorithm testing was performed for both randomly generated graphs and for real life examples. The results of the testing showed that the system is capable of correctly generating the route and has a real utilisation in everyday life. The best working heuristic algorithm was chosen (according to the length of the route and the shortest operating time) and the final tool for the website was created using Python, Javascript, HTML and CSS programming language.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2018
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Pupelytė, Rūta Melanija,
- Contributors dc:contributor
-
- Meškauskas, Tadas
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD35374535&prefLang=en_US