Mechanism design for first-mile ridesharing based on personalized requirements part II: Solution algorithm for large-scale problems

Ridesharing provides travelers with a low-cost and convenient first-mile mobility service. Our Part I paper designed a mechanism to incentivize more travelers to participate in the first-mile ridesharing service accounting for passengers’ personalized requirements on inconvenience attributes of ridesharing. In order to address the computational challenge of obtaining the mechanism for large-scale transportation networks, this paper develops a novel heuristic algorithm, called the Solution Pooling Approach (SPA) for efficiently solving large-scale mechanism design problems in the first-mile ridesharing context. This paper also extends the SPA to solve generalized mechanism design problems, analyzes specific circumstances under which the SPA can sustain the game-theoretic properties, including “individual rationality” and “incentive compatibility” and identifies its limitations. For the particular application in first-mile ridesharing, the SPA maintains the properties of “individual rationality” and “incentive compatibility”. Numerical experimental results show that the SPA can address the complex first-mile ridesharing service mechanism design problem in a computationally viable and efficient manner.