Bachelor Thesis BCLR-2022-64

BibliographyKlimentov, Kliment: Optimized Collective Route Planning in Transport Networks.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 64 (2022).
69 pages, english.

In recent years, both the large-scale adoption of smart devices and the decrease of cellular communication costs have led to Location Based Services (LBS) gaining tremendous amounts of popularity. Said services allow many and different kinds of queries to be processed, which in turn brings benefits for all kinds of users. These queries relate to different sets of problems and as such can be categorized to different (sub-)fields of research, such as carpooling, ride-sharing, vehicle routing, collective route planning, etc. Out of all the listed fields, collective route planning has the most relevance for this bachelor thesis. It is a topic that hasn’t been researched so thoroughly in the past decades (or at least not as much as it deserves to), but it is important to do so, as it can have many positive consequences for society. Collective route planning, as it will be discussed in this work, is environmentally friendly and may potentially solve (or positively affect) problems like pollution, energy consumption and traffic congestion. This bachelor thesis will present a problem that relates to finding an optimal pick-up location and determining the shortest individual routes and shared route for a group of travellers that are aiming to reach the same destination, with one of the travellers being a driver that can pick up and carry other passengers. The goal is to minimize the time needed by the whole group to reach their respective goal (under various constraints). In turn, the focal point of the whole work is developing and presenting an algorithm that can solve this problem optimally, in a relatively small amount of time. First, a formal definition of the problem is presented. Then, both a naive Brute-Force solution and a much more advanced solution are introduced and in turn compared to each other. The latter solution is then analysed in detail. Different experiments are also mentioned and provided so that the accuracy and efficiency of the algorithm for collective route planning can be proven.

Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Algorithmic
Superviser(s)Funke, Prof. Stefan; Proissl, Claudius
Entry dateNovember 29, 2022
   Publ. Computer Science