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

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.

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.