Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/26D63856-6B98-4F93-940B-05DA4AF68AE1 | ||
| Year | 2023 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Antigoni Asproudi, "Preference aggregation in the ridesharing domain", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2023 https://doi.org/10.26233/heallink.tuc.98346 | ||
| Appears in Collections |
Traditional ridesharing approaches involve the matching of drivers and passengers based on their itineraries and schedules. The objective is to share the trip cost while also minimizing time delays and the extra distance covered by the driver when accommodating the passengers. It serves as a flexible and economical alternative to traditional means of transportation, offering environmental and congestion-friendly benefits, as with more individuals sharing rides, the number of vehicles on the streets is reduced. In this thesis, we approach the ridesharing problem considering spatial criteria while also incorporating agents' preferences regarding the characteristics of their co-riders. This includes matching between passengers through preference aggregation in order to determine which ones should share each vehicle. Preference satisfaction is essential in our work, enhancing the overall ride experience and contributing to riders' sense of safety by taking into account their preferences regarding potential co-riders. Rooted in game-theoretic concepts, our approach produces core-stable matches and kernel-stable payment allocations of the trip cost. Hypergraphs are employed to identify passengers located in the same area as the driver. Through experiments involving variations in the shape of the area from which the driver can accommodate passengers, we assess its impact on the extra distance covered. Employing the Gale-Shapley algorithm, we match drivers with passengers, ensuring outcomes are in the core. To plan the coalition's route, we apply a Branch and Bounce algorithm to find the optimal sequence of stops the driver has to make to minimize the cost of the trip. Dijkstra's algorithm connects these stops to form the final path. Subsequently, the trip cost is divided fairly among commuters in each vehicle using the ``kernel" cooperative game-theoretic solution concept. The performance of our work is tested in simulations run in the city of Chania, for a range of 800 to 2500 agents. The results indicate that our implementation outperforms previous work in terms of preference satisfaction. Moreover, it efficiently matches agents, with an average of around three passengers per vehicle, contributing to the minimization of the volume of vehicles in the streets. Ultimately, the rise in the extra distance covered by the driver is maintained at an acceptable level and the driver's cost for the trip is effectively reduced.
Copyright © DIAS 2013
