An Online Ride-Sharing Path-Planning Strategy for Public Vehicle Systems

As efficient traffic-management platforms, public vehicle (PV) systems are envisioned to be a promising approach to solving traffic congestion and pollution for future smart cities. PV systems provide online/dynamic peer-to-peer ride-sharing services with the goal of serving a sufficient number of customers with a minimum number of vehicles and the lowest possible cost. A key component of the PV system is the online ride-sharing scheduling strategy. In this paper, an efficient path-planning strategy based on a greedy algorithm is proposed, which focuses on a limited potential search area for each vehicle by filtering out the requests that violate the passenger service quality level, so that the global search is reduced to a local search. Moreover, the proposed heuristic can be easily used in the future globally optimal algorithm (if it will exist) to speed the computation time. The performance of the proposed solution, such as reduction ratio of computational complexity, is analyzed. Simulations based on the Manhattan taxi data set show that the computing time is reduced by 22% compared with the exhaustive search method under the same service quality performance.