Uroad：An Efficient Method for Large-Scale Many to Many Ride Sharing Matching

Due to the congested road and the increasing cost of private car, more and more people are willing to choose carpooling for travel. Although there are a lot of algorithms for ride sharing research, there is no algorithm to consider this problem from a global view. Plan all the matching routes from the global view and make all drivers’ detour distances minimize, which not only can reduce air pollution, but also can ease the traffic pressure. This paper presents an efficient large-scale matching method for many to many ride sharing algorithm, called Uroad, to make up for the shortcomings of existing algorithms. Uroad allows the rider to request a ride service which includes the periods of departure time when he gets ready to start off and the maximum cost of the ride-sharing he is willing to pay for this service. At the same time, Uroad allows the driver to set the departure time to indicate when he will set out and the arrival time that he must reach to his destination before. The same to the other Carpooling algorithms, Uroad calculates the fare based on the distance of rider’s trip and the detour caused by the rider. According to the requirements of riders and drivers, Uroad supports the global optimal matching among multiple riders and drivers, matches a driver who can meet the requirements to each rider as far as possible, and minimizes the total detour of all the drivers to reach the goal of environmental protection and reducing the traffic pressure. Uroad uses a series of time pruning techniques and Euclidean distance pruning techniques to reduce the calculation of the shortest path which can make the overall algorithm more quick and efficient. The experiments show that it is less than 2 minutes for Uroad to find the optimal combination of ride-sharing for 1 000 riders in 100 000 drivers, which is 40% shorter than the direct calculation of the shortest path. Compared with the random selection of drivers, the total detours of all drivers can be reduced by about 60% with the global optimization strategy.