Methods and systems for efficient and timely transportation of heavy-duty trucks

A method for determining a route for a truck, the method comprising:

• receiving, at a computer system, input information indicating a starting location, a destination location, a deadline, truck information, and weight;
• defining, at a computer system, a road network model, the road network model including a plurality of nodes and a plurality of edges connecting pairs of the nodes, wherein each edge corresponds to a road and has a generalized cost function associated therewith, the generalized cost function depending in part on a speed-dependent fuel consumption model associated with the truck information and in part on a speed-dependent delay time associated with the edge;
• identifying, by the computer system, a source node of the road network model that corresponds to the starting location and a destination node of the road network model that corresponds to the destination location;
• performing, by the computer system, a binary search in a dual problem space to find an optimal path and speed though the road network model from the source node to the destination node, wherein each path and speed has a cost determined from the generalized cost functions of the edges included in the path and wherein the optimal route has a lowest cost subject to a constraint based on arriving at the destination node by the deadline,
• wherein performing the binary search in the dual problem space includes:
• selecting a current value λ0 for a dual variable λ that represents a per-unit delay price over the road network model;
• computing an optimal travel time te*(λ0) for each of the plurality of edges, wherein the optimal travel time te*(λ0) represents an optimal travel time for the edge given the current value λ0;
• computing the generalized cost function we(λ0) for each of the plurality of edges, wherein the generalized cost function we(λ0) includes a fuel cost associated with the optimal travel time te*(λ0) and a delay cost associated with the optimal travel time te*(λ0);
• determining, using the generalized cost functions we(λ0) for the plurality of edges, a path p*(λ0) that has a minimum total generalized cost function;
• computing a total travel time δ(λ0) for the path p*(λ0);
• and
• determining, based on the total travel time δ(λ0), whether to accept the path p*(λ0) as an optimal path or to select a new value for the dual variable λ and continue the binary search;
• identifying, by the computer system, an optimal route and speed for the truck based on the binary search;
• and
• providing, by the computer system, the optimal route and speed to a user.

A system for determining a route for a truck, the system comprising:

• a network interface configured to communicate with an in-vehicle computing device of a truck;
• and
• a processing subsystem coupled to the network interface, the processing subsystem configured to execute program code to:
• receive, from the in-vehicle computing device, input information indicating a starting location, a destination location, a deadline, truck information, and weight;
• define a road network model, the road network model including a plurality of nodes and a plurality of edges connecting pairs of the nodes, wherein each edge corresponds to a road and has a generalized cost function associated therewith, the generalized cost function depending in part on a speed-dependent fuel consumption model associated with the truck information and in part on a speed-dependent delay time associated with the edge;
• identify a source node of the road network model that corresponds to the starting location and a destination node of the road network model that corresponds to the destination location;
• perform a binary search in a dual problem space to find an optimal path and speed though the road network model from the source node to the destination node, wherein each path and speed has a cost determined from the generalized cost functions of the edges included in the path and wherein the optimal path has a lowest cost subject to a constraint based on arriving at the destination node by the deadline, wherein performing the binary search in the dual problem space includes:
• selecting a current value λ0 for a dual variable λ that represents a per-unit delay price over the road network model;
• computing an optimal travel time te*(λ0) for each of the plurality of edges, wherein the optimal travel time te*(λ0) represents an optimal travel time for the edge given the current value λ0;
• computing the generalized cost function we(λ0) for each of the plurality of edges, wherein the generalized cost function we(λ0) includes a fuel cost associated with the optimal travel time te*(λ0) and a delay cost associated with the optimal travel time te*(λ0);
• determining, using the generalized cost functions we(λ0) for the plurality of edges, a path p*(λ0) that has a minimum total generalized cost function;
• computing a total travel time δ(λ0) for the path p*(λ0);
• and
• determining, based on the total travel time δ(λ0), whether to accept p*(λ0) as an optimal path or to select a new value for the dual variable λ and continue the binary search;
• identify an optimal route and speed for the truck based on the binary search;
• and
• provide the optimal route and speed to the in-vehicle computing device.

A non-transitory computer-readable storage medium having stored therein program code instructions that, when executed by a processing subsystem of a computer system, cause the processing subsystem to execute a method comprising:

• receiving input information indicating a starting location for a truck, a destination location for the truck, a deadline, truck information for the truck, and weight;
• defining a road network model, the road network model including a plurality of nodes and a plurality of edges connecting pairs of the nodes, wherein each edge corresponds to a road and has a generalized cost function associated therewith, the generalized cost function depending in part on a speed-dependent fuel consumption model associated with the truck information and in part on a speed-dependent delay time associated with the edge;
• identifying a source node of the road network model that corresponds to the starting location and a destination node of the road network model that corresponds to the destination location;
• performing a binary search in a dual problem space to find an optimal path and speed though the road network model from the source node to the destination node, wherein each path and speed has a cost determined from the generalized cost functions of the edges included in the path and wherein the optimal route has a lowest cost subject to a constraint based on arriving at the destination node by the deadline, wherein performing the binary search in the dual problem space includes:
• selecting a current value λ0 for a dual variable λ that represents a per-unit delay price over the road network model, wherein the current value λ0 is selected by computing an average of an upper bound λU and a lower bound λL on the dual variable λ;
• computing an optimal travel time te*(λ0) for each of the plurality of edges, wherein the optimal travel time te*(λ0) represents an optimal travel time for the edge given the current value λ0;
• computing the generalized cost function we(λ0) for each of the plurality of edges, wherein the generalized cost function we(λ0) includes a fuel cost associated with the optimal travel time te*(λ0) and a delay cost associated with the optimal travel time te*(λ0);
• determining, using the generalized cost functions we(λ0) for the plurality of edges, a path p*(λ0) that has a minimum total generalized cost function;
• computing a total travel time δ(λ0) for the path p*(λ0);
• determining, based on the total travel time δ(λ0), whether to accept p*(λ0) as an optimal path or to select a new value for the dual variable λ and continue the binary search;
• and
• in response to determining to select a new value for the dual variable λ and continue the binary search:
• setting the lower bound λL equal to the current value λ0 in the event that the total travel time δ(λ0) exceeds a hard delay constraint;
• and
• setting the upper bound λU equal to the current value λ0 in the event that the total travel time δ(λ0) is less than the hard delay constraint;
• identifying an optimal route and speed for the truck based on the binary search;
• and
• providing the optimal route and speed to a user.