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

• US 20150285651A1
• Filed: 11/06/2014
• Published: 10/08/2015
• Est. Priority Date: 12/11/2008
• Status: Abandoned Application

• 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
• Application Number:
  US14/535,104
• Publication Number:
  US 20150285651A1
• Time in Patent Office: Days
• US Class Current: 1/1
• 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. (canceled)

2. A computer-implemented method comprising:

as implemented by one or more computing devices configured with specific computer-executable instructions,

accessing a plurality of destination data elements identifying a plurality of physical destinations;

accessing a plurality of driver data elements identifying a plurality of drivers available to drive a vehicle of a vehicle fleet;

determining energy-use characteristics associated with each driver from the plurality of drivers;

determining a plurality of routes within a road network, each of the plurality of routes including the plurality of physical locations;

determining a monetary cost for each route from the plurality of routes, wherein the monetary cost is determined using a multivariate cost function;

selecting a combination of a route from the plurality of routes and a driver from the plurality of drivers based at least in part on a combination of the monetary cost for each route from the plurality of routes and the energy-use characteristics associated with each driver from the plurality of drivers; and

transmitting the selected combination of the route from the plurality of routes and the driver from the plurality of drivers to a management device for presentation to a user.

3. The computer-implemented method of claim 2, wherein the multivariate cost function is calculated based at least in part on vehicle characteristic data for each vehicle included as part of the vehicle fleet.

4. The computer-implemented method of claim 3, wherein the vehicle characteristic data comprises one or more factors including:

vehicle type, vehicle size, vehicle load, or driver technical requirements, and wherein the vehicle type comprises at least one of a diesel vehicle, a gasoline vehicle, an electric vehicle, or a hybrid vehicle.

5. The computer-implemented method of claim 2, wherein the multivariate cost function is calculated based at least in part on an environmental variable.

6. The computer-implemented method of claim 5, wherein the environmental variable comprises one or more factors including:

weather conditions, roadway construction conditions, or traffic conditions.

7. The computer-implemented method of claim 2, wherein the multivariate cost function is calculated for each edge within a model of the road network comprising edges and nodes, wherein the edges are associated with streets and the nodes are associated with intersections.

8. The computer-implemented method of claim 2, wherein the multivariate cost function is calculated based at least in part on a mapping variable.

9. The computer-implemented method of claim 8, wherein the mapping variable comprises one or more factors including:

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

10. The computer-implemented method of claim 2, wherein at least some of the variables of the multivariate cost function are weighted.

11. The computer-implemented method of claim 2, wherein at least some of the variables of the multivariate cost function are normalized on a time basis or a distance basis.

12. The computer-implemented method of claim 2, wherein the multivariate cost function is calculated based at least in part on 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, or height limit restriction.

13. A system comprising:

an electronic data store configured to at least store specific computer-executable instructions; and

an interactive computing system comprising computer hardware in communication with the electronic data store, the interactive computing system configured to execute the specific compute-executable instructions to at least;

accessing a plurality of destination data elements identifying a plurality of physical destinations;

determine a plurality of routes within a transportation network each of the plurality of routes including the plurality of physical locations;

determine a monetary cost for each route from the plurality of routes, wherein the monetary cost is determined using a multivariate cost function;

accessing a plurality of driver data elements identifying a plurality of drivers available to drive a vehicle included as part of a vehicle fleet along the plurality of routes;

determine energy-use characteristics associated with each driver from the plurality of drivers;

select a route from the plurality of routes based at least in part on the monetary cost for each route from the plurality of routes and a driver from the plurality of drivers based at least in part on the energy-use characteristics associated with each driver from the plurality of drivers; and

transmit the selected combination of the route from the plurality of routes and the driver from the plurality of drivers to a management device for presentation to a user.

14. The system of claim 13, wherein the multivariate cost function is calculated based at least in part on vehicle characteristic data for each vehicle included as part of the vehicle fleet, wherein the vehicle characteristic data comprises one or more factors including:

vehicle type, vehicle size, vehicle load, or driver technical requirements, and wherein the vehicle type comprises at least one of a diesel vehicle, a gasoline vehicle, an electric vehicle, or a hybrid vehicle.

15. The system of claim 13, wherein the multivariate cost function is calculated based at least in part on an environmental variable, and wherein the environmental variable comprises one or more factors including:

weather conditions, roadway construction conditions, or traffic conditions.

16. The system of claim 13, wherein the multivariate cost function is calculated for each edge within a model of the transportation network comprising edges and nodes, wherein the edges are associated with paths within the transportation network and the nodes are associated with intersections between at least two paths within the transportation network.

17. The system of claim 13, wherein the multivariate cost function is calculated based at least in part on a mapping variable, and wherein the mapping variable comprises one or more factors including:

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

18. The system of claim 13, wherein at least some of the variables of the multivariate cost function are weighted.

19. The system of claim 13, wherein at least some of the variables of the multivariate cost function are normalized on a time basis or a distance basis.

20. The system of claim 13, wherein the multivariate cost function is calculated based at least in part on 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, or height limit restriction.

21. A computer-readable, non-transitory storage medium storing computer executable instructions that, when executed by one or more computing devices, configure the one or more computing devices to perform operations comprising:

accessing a plurality of destination data elements identifying a plurality of physical destinations;

determining a plurality of routes within a network based, each of the plurality of routes including the plurality of physical locations;

determining a monetary cost for each route from the plurality of routes, wherein the monetary cost is determined using a multivariate cost function;

accessing a plurality of driver data elements identifying a plurality of drivers available to drive a vehicle included as part of a vehicle fleet along the plurality of routes;

determining energy-use characteristics associated with each driver from the plurality of drivers;

selecting a route from the plurality of routes based at least in part on the monetary cost for each route from the plurality of routes and a driver from the plurality of drivers based at least in part on the energy-use characteristics associated with each driver from the plurality of drivers; and

transmitting the selected combination of the route from the plurality of routes and the driver from the plurality of drivers to a management device for presentation to a user.