Sharing Rides with Friends: A Coalition Formation Algorithm for Ridesharing

We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, arrange one-time rides at short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system modelling such problem as a graph constrained coalition formation (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i. e. , the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i. e. , the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (Geo- Life) and social data (Twitter), to validate the applicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36. 22%). Moreover, we can provide approximate solutions for very large systems (i. e. , up to 2000 agents) and good quality guarantees (i. e. , with an approximation ratio of 1. 41 in the worst case) within minutes (i. e. , 100 seconds).

Authors

• Filippo Bistaffa Artificial Intelligence Research Institute (IIIA), CSIC
• Alessandro Farinelli University of Verona
• Sarvapali Ramchurn

Keywords

No keywords are indexed for this paper.