Dynamic Ride-Sharing In Big Cities

The number of private cars is growing rapidly in recent years as a result of eco-nomic growth. However, traffic congestion and environmental concerns require people to use personal automobiles wisely. On the other hand, private car occupancy rates (the number of travelers per vehicle trip) are relatively low; average car occupancies in Europe range from 1.8 for leisure trips to 1.1 for commuters. As a result, the demand for ride-sharing services, which aim to bring together travelers with similar itineraries and time schedules, has increased sharply.By ride-sharing, people can save their travel cost, as well as reduce the exhaust emissions.Traditional ride-sharing systems formally or informally link riders and drivers who travel between the same places at the same time. Dynamic ride-sharing differs from traditional ones in that ride-sharing is arranged on a per trip basis rather than for trips made on a regular basis. Dynamic ride-sharing is a form of ride-sharing that is used for single, one way trips rather than for trips made on a regular basis at the same time.The development of algorithms for optimally matching drivers and riders in real-time may only play a small role in the ultimate success of ride-sharing, but it is central to the concept. Ride-sharing is still in its infancy and an opportunity exists to influence its success. By introducing and formally defining dynamic ride-sharing problems and its objectives, we introduced several methods to solve this question.The contribution of this paper lies in four aspects:1. We proposed an improved method to slove the dynamic ride-sharing problem based on clustering. By taking into account the running vechicles, this method will have a better performance than the old one.2. To slove the response delay problem in the previous methods, we introduced a new algorithm based on position approximating. We divide the area in to grids, and keep a cache for every grid. As a result, we can find the appropriate vehicles in a short time.3. We found out that, in the current taxi systems, the demand and the supply is in severe confliction. So we designed a realtime ride-sharing system for taxis. Then we evaluated this system with real world datasets. The evaluation shows that, our improved methods can help people get a higher satisfaction rate, save more money, while wait for a shorter time.