Dynamic ride matching system

• US 8,140,256 B1
• Filed: 08/16/2007
• Issued: 03/20/2012
• Est. Priority Date: 08/16/2006
• Status: Expired due to Fees

• Current Assignee: University of South Florida (State University System of Florida)
• Original Assignee: University of South Florida (State University System of Florida)
• Inventors: Barbeau, Sean J., Winters, Philip L., Perez, Rafael, Labrador, Miguel, dos-Santos, Sasha
• Primary Examiner(s): NGUYEN, TAN QUANG
• Application Number:
  US11/839,942
• Time in Patent Office: 1,678 Days
• Field of Search: 701/202, 701/209, 701/117, 701/80, 701/319, 705/6, 705/7, 705/5, 705/1, 707/102, 455/414.1, 342/357.09
• US Class Current: 701/202
• CPC Class Codes: G01C 21/3438 Rendez-vous, i.e. searching a destination where several users can meet, and the routes to this destination for these users; Ride sharing, i.e. searching a route such that at least two users can share a vehicle for at least part of the route
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 50/188 Electronic negotiation

Abstract

A ride matching method is disclosed herein. The ride matching method addresses many of the limitations associated with traditional dynamic ride matching applications. The method is unique in its ability to accept trips with schedules that cannot be expressed in terms of a simple recurrence pattern (e.g. Monday thru Friday work schedule). It can handle one-time and occasional trips. It is also distinct in its use of spatial analysis techniques to locate matches. Specifically, the use of a shortest path solver enables the ride matching method to perform a search along the path of a user'"'"'s trip, in addition to the customary radial search around the endpoints. The shortest path solver is also used to calculate the driving distance between the user and a match. This provides a more accurate measurement than the straight-line distance used by other methods, especially in the presence of barriers.

Claims

1. A dynamic ride matching method comprising

storing a plurality of trips in a trip module, wherein each trip further comprises a plurality of attributes including a source location, a destination location and a shortest path between the source location and the destination location;

segmenting the shortest path between the source location and the destination location into a plurality of path segments;

defining a plurality of radial buffers, each of the plurality of radial buffers defined around one of each of the plurality of path segments and each of the plurality of radial buffers having a radius equal to a predetermined percentage of a length of the shortest path between the source location and the destination location;

associating each of the plurality of radial buffers with at least one attribute of the plurality of attributes for each trip in the trip module;

storing at least one scheduling parameter associated with each of the plurality of trips in a scheduling module; and

matching trips in the trip module having correlating trip attributes in at least one of the plurality of radial buffers and correlating scheduling parameters in the scheduling module.

2. The method of claim 1 wherein the trip module comprises at least one attribute selected from the group consisting of a trip ID, a user ID, carpool type, trip type, recurrence, earliest departure time, latest departure time, earliest arrival time, latest arrival time, start date, end date, driving time and driving distance.

3. The method of claim 1 wherein the trip is segmented into a first leg and a second leg.

4. The method of claim 3 wherein the first leg is the segment of the trip from the source location to the destination location and the second leg is the segment from the destination location to the source location.

5. The method of claim 1 wherein the scheduling parameter is selected from the group consisting of earliest departure date, earliest departure time, latest departure date, latest departure time, earliest arrival date, earliest arrival time, latest arrival date and latest arrival time.

6. The method of claim 1, further comprising identifying trips having a trip attribute within the same radial buffer, wherein the trip attribute is selected from the group consisting of the source location, the destination location and the shortest path between the source location and the destination location.

7. The method of claim 1, further comprising associating at least one trip instance with each trip.

8. The method of claim 7, further comprising identifying trips with overlapping trip instances.

9. The method of claim 1, further comprising associating at least one trip type with each trip.

10. The method of claim 9 wherein the trip type is selected from the group consisting of one-way trip and round-trip.

11. The method of claim 9, further comprising identifying trips with matching trip types.

12. The method of claim 1, further comprising associating a user type with each trip.

13. The method of claim 12 wherein the user type is selected from the group consisting of driver, passenger and no preference.

14. The method of claim 13, further comprising identifying trips with matching user types.

15. The method of claim 14, wherein:

trips with driver user types do not match to other trips with driver user types;

trips with passenger user types match with at least one trip with a driver user type.

16. The method of claim 1, further comprising calculating the shortest path from the source location to the destination location.

17. The method of claim 16, wherein the shortest path from the source location to the destination location is calculated using Dijkstra'"'"'s algorithm.

18. The method of claim 1, further comprising calculating the shortest travel time between the source location and the destination location.

19. The method of claim 1 wherein the plurality of path segments include a source path segment, a mid-path segment and a destination path segment and the plurality of radial buffers include a source buffer, a mid-path buffer, and a destination buffer for each trip in the trip module.