System and method for efficient routing on a network in the presence of multiple-edge restrictions and other constraints
First Claim
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, andwherein 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.
8 Assignments
0 Petitions
Accused Products
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.
-
Citations
48 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
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. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32)
-
-
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. - View Dependent Claims (34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
-
Specification