[4F1-OS-11c] [Organized Session] OS-11

[4F1-OS-11c-02] Performance Evaluation of Path Finding Algorithm for Ride-sharing Service

〇Yuki Yoshizuka¹, Hideaki Uchida¹, Hideki Fujii¹, Shinobu Yoshimura¹ (1. School of Engineering, The University of Tokyo)

Keywords:ride-sharing, path finding, SAV

Ride-sharing service is inexpensive urban mobility which is convenient for the user and can be used in real time. Since this service needs to dispatch the car immediately after reservation by the customer, real-time property is regarded as important. Therefore, we implement this service in the traffic simulator and evaluate the performance of the exhaustive search algorithm and the sequential insertion method for the path finding algorithm for ride-sharing. In the experiment, multiple demand are generated one after another at random positions, and the sum of calculation time and the detour cost required until the cost calculation of all vehicles is completed are measured. Experiments of multiple cases show that the sequential insertion method for computation time can be computed at high speed tolerable to the user and that the accuracy of the solution is not so inferior from the optimal solution.