System and method for determining routing information

• US 20090292463A1
• Filed: 05/21/2009
• Published: 11/26/2009
• Est. Priority Date: 05/21/2008
• Status: Abandoned Application

• Current Assignee: Xora, Inc. (Salesforce.com, Inc.)
• Original Assignee: Xora, Inc. (Salesforce.com, Inc.)
• Inventors: Chase, Robert Gregory
• Application Number:
  US12/454,720
• Publication Number:
  US 20090292463A1
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047

Abstract

A system and method for determining an optimal set of routes from an origin to one or more destinations. The system comprises a reverse geo-code database of closest intersections for one or more locations of a particular geographical region, a matrix generator, and a vehicle routing problem solver. The matrix generator creates a set of shortest routes among the possible routes between the origin location and the one or more destination locations. The shortest routes are determined by calculating a distance from a first location to a first nearest artery, a distance from a second location to a second nearest artery, and from the first nearest artery to the second nearest artery. The vehicle routing problem solver generates an optimal set of routes connecting the one or more locations by combining the one or more shortest routes.

Claims

1. A system for determining an optimal set of routes from an origin location to one or more destination locations comprising:

a reverse geo-code database of closest intersections for a set of one or more locations of a particular geographical region;

a matrix generator for creating a set of shortest paths among the possible paths between the origin location and the one or more destination locations wherein the shortest paths are determined by calculating a first shortest distance from a first location to a first nearest artery, a second shortest distance from a second location to a second nearest artery, a third shortest distance from the first nearest artery to the second nearest artery, and combining the first shortest distance, the second shortest distance, and the third shortest distance; and

a vehicle routing problem solver for generating an optimal set of routes connecting the one or more destination locations by combining the one or more shortest paths.

2. The system of claim 1, further comprising one or more client devices for receiving the optimal set of routes from the vehicle routing problem solver.

3. The system of claim 2, wherein the client devices provide a set of location information used to determine the origin location.

4. The system of claim 3, wherein the client devices compute the current location via a GNSS system.

5. The system of claim 1, wherein the reverse geo-coder database comprises at least one hash value representing the at least one street intersection.

6. The system of claim 5, wherein the hash values are determined by multiplying the latitude and longitude coordinates of the at least one street intersection.

7. A method for determining an optimal set of routes linking an origin location and one or more destination locations performed by a special-purpose computer programmed by an application software module comprising:

creating a set of shortest paths among each of the one or more possible paths between the origin location and the one or more destination locations, wherein the shortest paths are determined by calculating a first shortest distance from a first location to a first nearest artery, a second shortest distance from a second location to a second nearest artery, a third shortest distance from the first nearest artery to the second nearest artery, and combining the first shortest distance, the second shortest distance, and the third shortest distance; and

generating an optimal set of routes connecting the one or more destination locations by combining the one or more shortest paths.

8. The method of claim 7;

wherein the generating step further comprises calculating an optimal set of routes using an enhanced Standard Savings Method comprising;

calculating a time savings for each of one or more possible combinations of the routes comprising the set of shortest routes;

executing the Standard Savings Method algorithm on each of one or more shortest combinations of the one or more possible combinations; and

choosing the shortest combination which yields a least number of routes;

adding the chosen shortest combination to the set of routes; and

repeating until the set of shortest routes can no longer be combined.

9. A computer program executed on a processor to perform the method of claim 7.

10. A computer program executed on a processor to perform the method of claim 8.

11. The method of claim 7, further comprising sending the determined optimal set of routes to one or more client devices.

12. A computer program executed on a processor to perform the method of claim 11.

13. The method of claim 11, wherein the client device computes location information used to determine the origin location.

14. The method of claim 13, wherein the origin location is computed using signals from a GNSS system.

15. The method of claim 7, wherein the creating step further comprises

generating a hash value for each of the origin location and destination locations and

comparing the generated hash value with a reverse geo-code database to determine a nearest intersection.

16. The method of claim 15, wherein the reverse geo-code database comprises one or more intersection hash values for each of one or more intersections in a region.

17. The method of claim 15, wherein the hash generating step further comprises multiplying a latitude coordinate and a longitude coordinate of a target location to create the hash value.

18. The method of claim 15, wherein the geo-code database comprises one or more hash values corresponding to one or more street intersections.

19. A system for determining an optimal set of routes from an origin location to one or more destination locations comprising:

means for creating a set of shortest paths among the possible routes between the origin location and the one or more destination locations wherein the shortest paths are determined by calculating a first shortest distance from a first location to a first nearest artery, a second shortest distance from a second location to a second nearest artery, a third shortest distance from the first nearest artery to the second nearest artery, and adding the first shortest distance, the second shortest distance, and the third shortest; and

means for generating an optimal set of routes connecting the one or more locations by combining the one or more shortest paths.

20. The system of claim 19, further comprising means for sending the optimal set of routes to one or more client devices.