Bimodal Cooperative Matching Algorithm for the Dynamic Ride-Sharing Problem

Ride-sharing can effectively improve the utilization of transportation resources, decrease travel costs, alleviate traffic congestion, and reduce environmental pollution. Aiming at the dynamic ride-sharing problem, an integer linear programming model is constructed, and a bimodal cooperative matching algorithm based on offline and online matching is proposed. In the offline stage, the sharing route percentage and the detour length are adopted to evaluate the matching value, and a general sharing route percentage algorithm based on the weighted path search tree is designed to perform accurate pre-matching of the participants. In the online stage, a real-time order insertion algorithm based on the complex location to destination is proposed, and the routes obtained in the offline matching stage are further improved. Through the bimodal cooperation, the real-time performance and solution quality of the proposed algorithm can be significantly augmented. Finally, a large number of experiments based on real-world data are performed. The results show that the overall sharing value and efficiency of the proposed algorithm surpass those of the comparative algorithm. The average offline matching rate and the average bimodal cooperative matching rate reach 93.71% and 85.53%, respectively, while the transportation efficiency is improved by 82.86% and the vehicle concurrency is reduced by 84.86%.