Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Preference aggregation in the ridesharing domain

Asproudi Antigoni

Full record


URI: http://purl.tuc.gr/dl/dias/26D63856-6B98-4F93-940B-05DA4AF68AE1
Year 2023
Type of Item Diploma Work
License
Details
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

Summary

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.

Available Files

Services

Statistics