D-SPAC: Double-Sided Preference-Aware Carpooling of Private Cars for Maximizing Passenger Utility

Private car-based carpooling (PCC) has become an important transportation mode in our daily life. Unlike ride-hailing or taxi-based carpooling, PCC has two unique features that have yet to be fully explored: (i) A private-car driver has more bargaining space than a non-private car driver; (ii) There exists unfriendly congestion in private car-based carpooling if not handled well. Existing carpooling schemes are not tailored for PCC services with an oversimplified assumption that passengers pay detour fees and there is no guarantee on the passenger's travel time. Consequently, such limitations not only harm the passenger's carpooling incentive but also hurt the passenger's quality of experience as well as the driver's utility. We propose a novel framework for the double-sided preference-aware carpooling (D-SPAC) problem, after comprehensively addressing the above two unique features. We formulate the D-SPAC problem as a mixed-integer non-linear programming problem, which is proved to be NP-hard, to maximize the total utility of passengers while meeting the driver's buyout asking price, traversal radius, passenger's waiting time, budget and both sides' detour length constraints. We design a coalitional double auction-based scheme that can better motivate both sides with guaranteed economic properties. We further design a deep reinforcement learning algorithm to cope with the position dynamics and the changing user requests. Extensive experimental results based on real-world data sets demonstrate the effectiveness of proposed algorithms over three benchmark algorithms.