Institutional Repository of Vilnius University
Algoritmai realaus laiko bendrakeleivio paieškos sistemoms /
Abstract
dc:descriptionAs urban traffic infrastructure demands continue to grow, real-time ride-sharing systems can become a major turning point for sustainable, and economical urban mobility. This thesis analyses and proposes algorithms for the development of such systems, focusing on exact shortest-path search with precedence constraints and dynamic driver-rider matching under dynamically changing environment conditions. For route planning, an adapted Held-Karp dynamic programming algorithm, tailored to precedence constraints, was proposed, achieving over 100 times greater efficiency compared to the alternative studied algorithms. Among the analysed dynamic matching solutions, the proposed Particle Swarm Optimization (PSO) model, initialised with 40 particles and parameterised with Time-Varying Acceleration Coefficients (TVAC), showcased over 50 times faster computation and double the cost savings compared to the static matching baseline. Experiments, conducted in real-world simulated urban layouts, modelled using “OpenStreetMap” data, revealed that an active system participant on average saved more than 30% in travel costs, with matches found for over 50% of all riders who submitted ride requests. These results confirm the proposed algorithms to be applicable for the development of efficient real-time ride-sharing systems and highlight their potential to assist in addressing urban mobility challenges.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Griškus, Šarūnas,
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:ELABAETD239030357&prefLang=en_US