Two-stage optimization of robotaxi dispatch via recommendation of pick-up/drop-off points and boarding time

As autonomous driving technology reaches a more advanced stage, robotaxis are poised to become a highly promising option for urban mobility. When passengers opt for carpooling, their requested origins/destinations and boarding time (BT) may lead to inefficient robotaxi dispatch. This paper studies a novel robotaxi dispatch problem to recommend pick-up and drop-off (PUDO) points and BT that differ from the requested ones for passengers, considering passenger willingness, i.e., whether to accept these recommendations or not. However, one-stage optimization cannot formulate the realistic decision-making behavior of passengers. To address this issue, a two-stage method is proposed to solve the problem. In the first stage, the PUDO points and BT are optimized and recommended to passengers. In the second stage, with passenger willingness, the routes of robotaxis are planned to optimize travel efficiency. The two stages are formulated as Mixed Integer Programming (MIP) models solved by two algorithms based on Nondominated Sorting Genetic Algorithm II (NSGA-II). The first algorithm is called Nondominated Sorting Genetic Algorithm II via Mass Center (NSGA-MC). It includes a trip similarity determination strategy, a segmented encoding process, and a three-operation evolution to update each fragment of the solution, and introduces a mass center for obtaining a high-quality solution. The second is a Nondominated Sorting Genetic Algorithm II with Improved Evolution (NSGA-IE). It involves an integer encoding process, a new evolution operator for route planning, and a post-iteration selection to choose a final solution from the Pareto-optimal set. The proposed algorithms can balance the conflicting objectives of maximizing the profit per kilometer of robotaxis and minimizing the total travel expense of passengers. The validity of the proposed model is confirmed by an exhaustive search method and a commercial solver CPLEX. The experimental results demonstrate that the proposed algorithms effectively determine feasible solutions and outperform NSGA-II and Multi-objective Evolutionary Algorithm based on Decomposition (MOEA/D) across multiple performance metrics. An ablation study illustrates the benefits of the recommendation of PUDO points and BT. Furthermore, a sensitivity analysis examines the full range of passenger willingness to accept recommendations, ranging from 0 to 100%, with intervals of 25%. Consequently, the proposed method effectively reduces the travel cost for passengers and increases the revenue of robotaxi companies. This work can actively prepare and promote the adoption of robotaxis in our real life, thereby contributing to the advancement of intelligent public transportation services.