Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

A cooperative game-theoretic approach to the social ridesharing problem

Bistaffa Filippo, Farinelli Alessandro, Chalkiadakis Georgios, Ramchurn, Sarvapali D

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/8C12E752-9FED-4E69-86D0-57BCE03FEB96-
Αναγνωριστικόhttps://www.sciencedirect.com/science/article/pii/S0004370217300243?via%3Dihub-
Αναγνωριστικόhttps://doi.org/10.1016/j.artint.2017.02.004-
Γλώσσαen-
Μέγεθος32 pagesen
ΤίτλοςA cooperative game-theoretic approach to the social ridesharing problemen
ΔημιουργόςBistaffa Filippoen
ΔημιουργόςFarinelli Alessandroen
ΔημιουργόςChalkiadakis Georgiosen
ΔημιουργόςΧαλκιαδακης Γεωργιοςel
ΔημιουργόςRamchurn, Sarvapali Den
ΕκδότηςElsevieren
ΠερίληψηIn this work, we adopt a cooperative game theoretic approach in order to tackle the social ridesharing (SR) problem, where a set of commuters, connected through a social network, form coalitions and arrange one-time rides at short notice. In particular, we address two fundamental aspects of this problem. First, we focus on the optimisation problem of forming the travellers' coalitions that minimise the travel cost of the overall system. To this end, we model the formation problem as a Graph-Constrained Coalition Formation (GCCF) one, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Our approach allows users to specify both spatial and temporal preferences for the trips. Second, we tackle the payment allocation aspect of SR, by proposing the first approach that computes kernel-stable payments for systems with thousands of agents. We conduct a systematic empirical evaluation that uses real-world datasets (i.e., GeoLife and Twitter). We are able to compute optimal solutions for medium-sized systems (i.e., with 100 agents), and high quality solutions for very large systems (i.e., up to 2000 agents). Our results show that our approach improves the social welfare (i.e., reduces travel costs) by up to 36.22% with respect to the scenario with no ridesharing. Finally, our payment allocation method computes kernel-stable payments for 2000 agents in less than an hour—while the state of the art is able to compute payments only for up to 100 agents, and does so 84 times slower than our approach. en
ΤύποςPeer-Reviewed Journal Publicationen
ΤύποςΔημοσίευση σε Περιοδικό με Κριτέςel
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2018-05-14-
Ημερομηνία Δημοσίευσης2017-
Θεματική ΚατηγορίαCoalition formationen
Θεματική ΚατηγορίαGraphsen
Θεματική ΚατηγορίαRidesharingen
Θεματική ΚατηγορίαSocial networksen
Βιβλιογραφική ΑναφοράF. Bistaffa, A. Farinelli, G. Chalkiadakis and S. D. Ramchurn, "A cooperative game-theoretic approach to the social ridesharing problem," Artif. Intell., vol. 246, pp. 86-117, May 2017. doi: 10.1016/j.artint.2017.02.004en

Υπηρεσίες

Στατιστικά