ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (6): 1269-1283.doi: 10.7544/issn1000-1239.2020.20190484

Previous Articles     Next Articles

Multi-Strategy Solution Space Graph Search Algorithm of Real-Time Ride-Sharing Problem

Guo Yuhan, Zhang Yu, Shen Xueli, Yu Junyu   

  1. (College of Software, Liaoning Technical University, Huludao, Liaoning 125100)
  • Online:2020-06-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61404069), the Natural Science Foundation of Liaoning Province of China (2019-ZD-0048), and the Basic Research Project of Liaoning Provincial Education Department (LJ2019JL012).

Abstract: Ride-sharing can improve transportation efficiency, alleviate traffic congestion, reduce environmental pollution and save travel costs through decreasing the vehicle vacancy rate of all participants. Firstly, in this paper, a mathematical model is constructed for the real-time ride-sharing problem, where the utilization efficiency of the driver resources in the ride-sharing is evaluated by means of the shared route percentage and the detour distance constraint. Then, a solution space graph theory of discrete permutation problem is proposed and its principle is elaborated and analyzed. Based on this theory, a multi-strategy solution space graph search algorithm is constructed. The algorithm utilizes a parallel structure to generate the value matrix of driver-rider pairs, which greatly improves the efficiency of the algorithm compared with traditional approaches. Several different search operators, designed based on the characteristics of the discrete permutation problem, are manipulated by multiple control strategies proposed in this paper, which guide the search process to move to higher value directions of the solution space graph to obtain high quality matching results efficiently. The experimental results show that the quality of the algorithm can exceed 95% of the optimal solution, and the efficiency of the algorithm is significantly superior than the other algorithms compared in the experiment.

Key words: ride-sharing, solution space graph, multi-strategy search algorithm, discrete permutation problem, combinational optimization algorithm

CLC Number: