The culture of sharing instead of ownership is sharply increasing in individuals behaviors. Particularly in transportation, concepts of sharing a ride in either carpooling or ridesharing have been recently adopted. An efficient optimization approach to match passengers in real-time is the core of any ridesharing system. In this paper, we model ridesharing as an online matching problem on general graphs such that passengers do not drive private cars and use shared taxis. We propose an optimization algorithm to solve it. The outlined algorithm calculates the optimal waiting time when a passenger arrives. This leads to a matching with minimal overall overheads while maximizing the number of partnerships. To evaluate the behavior of our algorithm, we used NYC taxi real-life data set. Results represent a substantial reduction in overall overheads.
Todays ride sharing services still mimic a better billboard. They list the offers and allow to search for the source and target city, sometimes enriched with radial search. So finding a connection between big cities is quite easy. These places are on a list of designated origin and distination points. But when you want to go from a small town to another small town, even when they are next to a freeway, you run into problems. You can't find offers that would or could pass by the town easily with little or no detour. We solve this interesting problem by presenting a fast algorithm that computes the offers with the smallest detours w.r.t. a request. Our experiments show that the problem is efficiently solvable in times suitable for a web service implementation. For realistic database size we achieve lookup times of about 5ms and a matching rate of 90 instead of just 70 for the simple matching algorithms used today.