Online Coordinated Carpooling Routing Mechanism Built Upon Cost-Sharing Game and Coalition Formation

Carpooling service, as a sustainable transportation mode, has gained great interest in both industry and academic fields. However, existing TNC carpooling services provide prescriptive solutions without coordinating riders’ route choices, while each rider’s route choices will affect other riders’ travel fares under a carpooling service. The corresponding cost-sharing and route choice interaction among riders have not been carefully studied or incorporated into carpooling services. As a result, these prescriptive approaches limit the benefit of carpooling services, and the carpooling services are still under a relatively low usage rate. This study aims to develop an online coordinated carpooling route choice mechanism (CCRM) to fill this research gap. Specifically, we model this CCRM as a pure-strategy atomic cost-sharing game based on the assumption that every rider is selfish and tries to choose the best route to minimize his/her travel fare among multiple feasible candidate routes. We prove the existence of a Nash Equilibrium of this game by constructing a potential function and proving this game is a potential game. An existing carpooling tree generation algorithm generates the candidate routes of each rider. We further develop a sequential updated distributed algorithm to explore an equilibrium solution of the CCRM. To address the scalability issue, we create a coalition formation approach to separate riders into carpooling coalitions and then implement the CCRM for each carpooling coalition independently. Our experiments illustrate that the coalition approach scales down the problem size of each CCRM and dramatically improves the computation efficiency while maintaining the same level of system performance. More importantly, the CCRM can significantly promote riders’ usage of the carpooling service by greatly saving their travel fares while satisfying their trip requirements