SYSTEM AND METHOD FOR EFFICIENT ROUTING ON A NETWORK IN THE PRESENCE OF MULTIPLE-EDGE RESTRICTIONS AND OTHER CONSTRAINTS

• US 20120158299A1
• Filed: 06/17/2011
• Published: 06/21/2012
• Est. Priority Date: 12/11/2008
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Telogis Incorporated (Verizon Communications Inc.)
• Inventors: Mason, Ralph James, Koch, Jason, Jelinek, Howard, Cerecke, Carl David James, Mitchell, David John
• Granted Patent: US 8,886,453 B2
• Time in Patent Office: Days
• US Class Current: 701/533
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3484 Personalized, e.g. from learned user behaviour or user-defined profiles
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G08G 1/20 Monitoring the location of vehicles belonging to a group, e.g. fleet of vehicles, countable or determined number of vehicles

Abstract

Embodiments provide systems and methods that find the quickest route between two locations on a graph with multi-edge constraints in a time and space efficient manner. In some embodiments, Dijkstra'"'"'s algorithm is split into separate universes when a) a multiple-edge constraint is reached, and b) along each edge of a multi-edge constraint. In some embodiments, the split is performed for the purpose of finding the quickest (i.e. lowest weighted) route to the intersect ion(s) at the end of the constraints. These universes, in some embodiments, are merged or discarded when the intersection at the end of the constraint is found. Using these systems and methods, in some embodiments, the shortest path between two locations of a multi-edge constrained road network can be efficiently determined.

Claims

1. A computer-implemented method of vehicle routing optimization by using a multivariate function for calculating a route value, the vehicle routing optimization configured to determine an optimal driving route for a driver of a vehicle traveling between a starting geographical location and a destination geographical location, the computer-implemented method comprising:

accessing the starting geographical location of the vehicle;

accessing the destination geographical location of the vehicle;

accessing a model from an electronic storage, the model representing a road network comprising the starting geographical location and the destination geographical location, the model comprising a plurality of nodes representing intersections of the road network and a plurality of edges representing roadways of the road network, wherein each edge connects at least two nodes in the model and has a cost value for the vehicle to travel along the roadway represented by the edge;

determining at least one driving route for the vehicle traveling between the starting geographical location of the vehicle and the destination geographical location of the vehicle, each driving route comprising an ordered set of edges, wherein each edge comprises a multivariate cost function for determining the cost value for the vehicle to travel along the roadway represented by the edge;

determining the route value for each of the at least one driving routes based on the cost values for each edge in the at least one driving routes; and

selecting the driving route from the at least one driving routes with the lowest route value;

wherein the computer-implemented method is performed by a computer system that comprises one or more computing devices;

wherein each multivariate cost functions comprises variables, the variables comprising at least a mapping data variable and at least one of the following variables;

vehicle characteristic data variable, environmental data variable, driver data variable, and post intersection variable data.

2. The computer-implemented method of vehicle routing optimization of claim 1, wherein the model comprises multi-edge constraints.

3. The computer-implemented method of vehicle routing optimization of claim 1, wherein determining the route value for each of the at least one driving routes is based on a summation of the cost values for each edge in the at least one driving routes.

4. The computer-implemented method of vehicle routing optimization of claim 1, wherein determining the route value for each of the at least one driving routes is based on a product of the cost values for each edge in the at least one driving routes.

5. The computer-implemented method of vehicle routing optimization of claim 1, wherein determining the route value for each of the at least one driving routes is based on a combination of a summation and a product of the cost values for each edge in the at least one driving routes.

6. The computer-implemented method of vehicle routing optimization of claim 1, wherein each multivariate cost functions comprises weighting factors applied to the variables.

7. The computer-implemented method of vehicle routing optimization of claim 1, wherein the mapping data variable comprises one or more factors:

geographical coordinates, route distance, speed limit for a roadway, route travel time, elevation data, bridge data, and incline data.

8. The computer-implemented method of vehicle routing optimization of claim 1, wherein the vehicle characteristic variable comprises one or more factors:

vehicle type, vehicle size, vehicle load, and driver technical requirements.

9. The computer-implemented method of vehicle routing optimization of claim 8, wherein the vehicle type at least includes a diesel vehicle and a hybrid vehicle.

10. The computer-implemented method of vehicle routing optimization of claim 8, wherein the vehicle type at least includes a diesel vehicle, a gasoline vehicle, an electric vehicle, and a hybrid vehicle.

11. The computer-implemented method of vehicle routing optimization of claim 1, wherein the environmental data variable comprises one or more factors:

weather conditions, roadway construction conditions, and traffic conditions.

12. The computer-implemented method of vehicle routing optimization of claim 1, wherein the driver data variable comprises one or more factors:

driver education qualifications, hours driven by driver, and driver experience.

13. The computer-implemented method of vehicle routing optimization of claim 1, wherein the post intersection variable data comprises one or more factors:

no left turn restriction, no right turn restriction, long light, one-way street, roadway class, roadway weigh restriction, narrow bridge or roadway condition, and height limit restriction.

14. The computer-implemented method of vehicle routing optimization of claim 1, wherein the variables inputted into the multivariate cost functions are normalized on a time basis or a distance basis.

15. The computer-implemented method of vehicle routing optimization of claim 1, wherein the computer-implemented method is performed on a periodic basis by inputting updated variables into the multivariate cost functions of the edges.

16. The computer-implemented method of vehicle routing optimization of claim 1, wherein the computer-implemented method is performed for a plurality of drivers and a plurality of vehicles and plurality of destination geographical locations to determine the combinations of drivers-vehicles-destinations that produce the lowest cost values.

17. A non-transitory storage medium having a computer program stored thereon for causing a suitably programmed system to process computer-program code by performing a method of vehicle routing optimization by using a multivariate function for calculating a route value, the vehicle routing optimization configured to determine an optimal driving route for a driver of a vehicle traveling between a starting geographical location and a destination geographical location, the method comprising:

accessing the starting geographical location of the vehicle;

accessing the destination geographical location of the vehicle;

accessing a model from an electronic storage, the model representing a road network comprising the starting geographical location and the destination geographical location, the model comprising a plurality of nodes representing intersections of the road network and a plurality of edges representing roadways of the road network, wherein each edge connects at least two nodes in the model and has a cost value for the vehicle to travel along the roadway represented by the edge;

determining at least one driving route for the vehicle traveling between the starting geographical location of the vehicle and the destination geographical location of the vehicle, each driving route comprising an ordered set of edges, wherein each edge comprises a multivariate cost function for determining the cost value for the vehicle to travel along the roadway represented by the edge;

determining the route value for each of the at least one driving routes based on the cost values for each edge in the at least one driving routes; and

selecting the driving route from the at least one driving routes with the lowest route value;

wherein the method is performed by a computer system that comprises one or more computing devices;

wherein each multivariate cost functions comprises variables, the variables comprising at least a mapping data variable and at least one of the following variables;

vehicle characteristic data variable, environmental data variable, driver data variable, and post intersection variable data.

18. The non-transitory storage medium of claim 17, wherein the model comprises multi-edge constraints.

19. The non-transitory storage medium of claim 17, wherein determining the route value for each of the at least one driving routes is based on a summation of the cost values for each edge in the at least one driving routes.

20. The non-transitory storage medium of claim 17, wherein determining the route value for each of the at least one driving routes is based on a product of the cost values for each edge in the at least one driving routes.

21. The non-transitory storage medium of claim 17, wherein determining the route value for each of the at least one driving routes is based on a combination of a summation and a product of the cost values for each edge in the at least one driving routes.

22. The non-transitory storage medium of claim 17, wherein each multivariate cost functions comprises weighting factors applied to the variables.

23. The non-transitory storage medium of claim 17, wherein the mapping data variable comprises one or more factors:

geographical coordinates, route distance, speed limit for a roadway, route travel time, elevation data, bridge data, and incline data.

24. The non-transitory storage medium of claim 17, wherein the vehicle characteristic variable comprises one or more factors:

vehicle type, vehicle size, vehicle load, and driver technical requirements.

25. The non-transitory storage medium of claim 24, wherein the vehicle type at least includes a diesel vehicle and a hybrid vehicle.

26. The non-transitory storage medium of claim 24, wherein the vehicle type at least includes a diesel vehicle, a gasoline vehicle, an electric vehicle, and a hybrid vehicle.

27. The non-transitory storage medium of claim 17, wherein the environmental data variable comprises one or more factors:

weather conditions, roadway construction conditions, and traffic conditions.

28. The non-transitory storage medium of claim 17, wherein the driver data variable comprises one or more factors:

driver education qualifications, hours driven by driver, and driver experience.

29. The non-transitory storage medium of claim 17, wherein the post intersection variable data comprises one or more factors:

no left turn restriction, no right turn restriction, long light, one-way street, roadway class, roadway weigh restriction, narrow bridge or roadway condition, and height limit restriction.

30. The non-transitory storage medium of claim 17, wherein the variables inputted into the multivariate cost functions are normalized on a time basis or a distance basis.

31. The non-transitory storage medium of claim 17, wherein the method is performed on a periodic basis by inputting updated variables into the multivariate cost functions of the edges.

32. The non-transitory storage medium of claim 17, wherein the method is performed for a plurality of drivers and a plurality of vehicles and plurality of destination geographical locations to determine the combinations of drivers-vehicles-destinations that produce the lowest cost values.

33. A computer system for vehicle routing optimization by using a multivariate function for calculating a route value, the vehicle routing optimization configured to determine an optimal driving route for a driver of a vehicle traveling between a starting geographical location and a destination geographical location, the method comprising:

a start location module configured to access the starting geographical location of the vehicle;

a destination location module configured to access the destination geographical location of the vehicle;

a data access module configured to access a model from an electronic storage, the model representing a road network comprising the starting geographical location and the destination geographical location, the model comprising a plurality of nodes representing intersections of the road network and a plurality of edges representing roadways of the road network, wherein each edge connects at least two nodes in the model and has a cost value for the vehicle to travel along the roadway represented by the edge;

a route determination module configured to determine at least one driving route for the vehicle traveling between the starting geographical location of the vehicle and the destination geographical location of the vehicle, each driving route comprising an ordered set of edges, wherein each edge comprises a multivariate cost function for determining the cost value for the vehicle to travel along the roadway represented by the edge;

a route value module configured to determine the route value for each of the at least one driving routes based on the cost values for each edge in the at least one driving routes; and

a route selection module configured to select the driving route from the at least one driving routes with the lowest route value;

wherein the computer system comprises one or more computing devices;

wherein each multivariate cost functions comprises variables, the variables comprising at least a mapping data variable and at least one of the following variables;

vehicle characteristic data variable, environmental data variable, driver data variable, and post intersection variable data.

34. The computer system of claim 33, wherein the model comprises multi-edge constraints.

35. The computer system of claim 33, wherein determining the route value for each of the at least one driving routes is based on a summation of the cost values for each edge in the at least one driving routes.

36. The computer system of claim 33, wherein determining the route value for each of the at least one driving routes is based on a product of the cost values for each edge in the at least one driving routes.

37. The computer system of claim 33, wherein determining the route value for each of the at least one driving routes is based on a combination of a summation and a product of the cost values for each edge in the at least one driving routes.

38. The computer system of claim 33, wherein each multivariate cost functions comprises weighting factors applied to the variables.

39. The computer system of claim 33, wherein the mapping data variable comprises one or more factors:

geographical coordinates, route distance, speed limit for a roadway, route travel time, elevation data, bridge data, and incline data.

40. The computer system of claim 33, wherein the vehicle characteristic variable comprises one or more factors:

vehicle type, vehicle size, vehicle load, and driver technical requirements.

41. The computer system of claim 40, wherein the vehicle type at least includes a diesel vehicle and a hybrid vehicle.

42. The computer system of claim 40, wherein the vehicle type at least includes a diesel vehicle, a gasoline vehicle, an electric vehicle, and a hybrid vehicle.

43. The computer system of claim 33, wherein the environmental data variable comprises one or more factors:

weather conditions, roadway construction conditions, and traffic conditions.

44. The computer system of claim 33, wherein the driver data variable comprises one or more factors:

driver education qualifications, hours driven by driver, and driver experience.

45. The computer system of claim 33, wherein the post intersection variable data comprises one or more factors:

no left turn restriction, no right turn restriction, long light, one-way street, roadway class, roadway weigh restriction, narrow bridge or roadway condition, and height limit restriction.

46. The computer system of claim 33, wherein the variables inputted into the multivariate cost functions are normalized on a time basis or a distance basis.

47. The computer system of claim 33, wherein the method is performed on a periodic basis by inputting updated variables into the multivariate cost functions of the edges.

48. The computer system of claim 33, wherein the method is performed for a plurality of drivers and a plurality of vehicles and plurality of destination geographical locations to determine the combinations of drivers-vehicles-destinations that produce the lowest cost values.