Fast Detour Computation for Ride Sharing

Details Fast Detour Computation for Ride Sharing Fast Detour Computation for Ride Sharing

2009-07-30

arxiv.org/abs/0907.5269v1

Computer Science

Data Structures and Algorithms

5 pages, 2 figure environment, 4 includegraphics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Fast Detour Computation for Ride Sharing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Detour Computation for Ride Sharing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Detour Computation for Ride Sharing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-468734