A Dynamic Grid-Based Algorithm for Taxi Ridesharing in Multiple Road Condition

As the way of easing urban traffic congestion, taxi ridesharing can effectively protect the environment and solve the difficulty of passengers taking taxis when taxi demand is high. In this paper, we formally define the dynamic ride-sharing problem and propose a taxi candidates-reduction ride-sharing scheduling algorithm based on dynamic grid. Regarding the congestion situation of the multiple road condition, the concept of speed decay zone was purposed to simulate this area. To solve the problem of low satisfaction in the congested situation, we devise a dynamic grid division strategy that reduces the grid size of the hotspot area to satisfy the specific needs of passengers in rush hour, and efficiently screen candidate taxis by dynamic grid index. We perform the experiments using the request dataset generated by the taxi request simulator of Beijing Chaoyang district. The performance shows that our approach reduce 35.5% computation without losing average satisfaction compared with existing ridesharing algorithm.