System and method for efficient routing on a network in the presence of multiple-edge restrictions and other constraints

• US 8,886,453 B2
• Filed: 06/17/2011
• Issued: 11/11/2014
• 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: Cerecke, Carl David James, Mitchell, David John, Mason, Ralph James, Koch, Jason, Jelinek, Howard
• Primary Examiner(s): To, Tuan C.
• Assistant Examiner(s): Hilgendorf, Dale W
• Application Number:
  US13/163,630
• Publication Number:
  US 20120158299A1
• Time in Patent Office: 1,243 Days
• Field of Search: 701/400, 701/410, 701/411, 701/414, 701/415, 701/416, 701/418, 701/420, 701/423, 701/424, 701/425, 701/428, 701/435, 701/439, 701/467, 701/532, 701/533, 701/117, 701/422, 340/905, 340/995.19, 340/995.2, 340/995.21
• US Class Current: 701/422
• 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, the vehicle included as part of a vehicle fleet;

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;

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

selecting a driver from a number of available drivers for the driving route based at least in part on energy-use characteristics associated with the driver; and

transmitting the driving route, and a combination of an identity of the vehicle and an identity of the driver as determined by a routing module to a management device for presentation to a user,

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

wherein each multivariate cost function 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, and driver data variable,

wherein the cost value for each edge comprises a monetary cost value and each multivariate cost function further comprises a monetary cost function,

wherein the driver data variable corresponds at least in part to energy-use characteristics associated with each of the available drivers, and

wherein the combination of the identity of the vehicle and the identity of the driver is based at least in part on the energy-use characteristics and the cost values for each edge in the driving route.

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 function 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 including:

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 including:

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 including:

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 including:

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

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

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, the vehicle included as part of a vehicle fleet;

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;

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

selecting a driver from a number of available drivers for the driving route based at least in part on energy-use characteristics associated with the driver; and

transmitting the driving route, and a combination of an identity of the vehicle and an identity of the driver as determined by a routing module to a management device for presentation to a user,

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

wherein each multivariate cost function 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, and driver data variable,

wherein the cost value for each edge comprises a monetary cost value and each multivariate cost function further comprises a monetary cost function,

wherein the driver data variable corresponds at least in part to energy-use characteristics associated with each of the available drivers, and

wherein the combination of the identity of the vehicle and the identity of the driver is based at least in part on the energy-use characteristics and the cost values for each edge in the driving route.

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 function 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 including:

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 including:

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 including:

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 including:

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

29. The non-transitory storage medium of claim 17, wherein the variables further comprise post intersection variable data, the post intersection variable data comprising one or more factors including:

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 computer system comprising:

a start location module configured to access the starting geographical location of the vehicle, the vehicle included as part of a vehicle fleet;

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;

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

a driver selection module configured to select a driver from a number of available drivers for the driving route based at least in part on energy-use characteristics associated with the driver; and

a communication module configured to transmit the driving route, and a combination of an identity of the vehicle and an identity of the driver to a management device for presentation to a user,

wherein the computer system comprises one or more computing devices,

wherein each multivariate cost function 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, and driver data variable;

wherein the cost value for each edge comprises a monetary cost value and each multivariate cost function further comprises a monetary cost function,

wherein the driver data variable corresponds at least in part to energy-use characteristics associated with each of the available drivers, and

wherein the combination of the identity of the vehicle and the identity of the driver is based at least in part on the energy-use characteristics and the cost values for each edge in the driving route.

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 function comprises weighting factors applied to the variables.

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

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 including:

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 including:

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 including:

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

45. The computer system of claim 33, wherein the variables further comprise post intersection variable data, the post intersection variable data comprising one or more factors including:

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.