# US 10,502,578 B2 · Methods and systems for efficient and timely transportation of heavy-duty trucks > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,502,578 B2 - Document ID: US10502578B2 - Status: Granted - Kind: B2 - Application number: 15/622,743 - Filed: 2017-06-14 - Published: 2018-12-20 - Granted: 2019-12-10 - Earliest claimed: 2017-06-14 - Assignees: The Chinese University of Hong Kong - Applicants: The Chinese University of Hong Kong - Inventors: Minghua Chen; Lei Deng; Mohammad Hassan Hajiesmail - Web page: https://patentgrep.com/patent/US10502578B2 ## CPC - G01C 21/3469: {Fuel consumption; Energy use; Emission aspects} - G01C 21/3453: {Special cost functions, i.e. other than distance or default speed limit of road segments} - G01C 21/3605: {Destination input or retrieval} - G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR ## Abstract Optimal routes and speeds for a heavy-duty truck traversing a network of roads can be automatically determined so as to minimize fuel costs (and optionally other operating costs) while still making on-time delivery of freight to a destination. Route and speed optimization can be based on a network model in which edges correspond to road segments and each edge has an associated cost function that reflects fuel consumption for a truck traversing the corresponding road segment. Given a starting location, destination location, delivery deadline, and truck information, an efficient search algorithm can be executed by a computer to determine an optimal path and speed through the network model, subject to the constraint of arriving at the destination by the delivery deadline. A truck operator can follow the route to the destination, driving at the optimal speed. ## Claims ### Claim 1 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, wherein the generalized cost function for each edge is determined based at least in part on a fuel-rate-speed function derived from a characteristic of the corresponding road and the speed-dependent fuel consumption model associated with the truck information; 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 path and speed has a lowest cost subject to a constraint based on arriving at the destination node by the deadline; 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. ### Claim 2 (depends on 1) The method of claim 1 wherein the input information is received from an in-vehicle computing device communicatively coupled to the computer system by a wide-area network. ### Claim 3 (depends on 2) The method of claim 2 wherein providing the optimal route and speed to the user includes transmitting a report specifying the optimal route and speed to the in-vehicle computing device. ### Claim 4 (depends on 1) The method of claim 1 wherein the user drives the truck in accordance with the optimal route and speed from the starting location to the destination location. ### Claim 5 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. ### Claim 6 (depends on 5) The method of claim 5 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 λ. ### Claim 7 (depends on 6) The method of claim 6 wherein performing the binary search in the dual problem space further includes, 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. ### Claim 8 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. ### Claim 9 (depends on 8) The system of claim 8 wherein an operator of the truck follows the optimal route and speed to the destination location. ### Claim 10 (depends on 8) The system of claim 8 wherein the processing subsystem is further configured such that the generalized cost function for each edge is determined based at least in part on a fuel-rate-speed function derived from a characteristic of the corresponding road and the speed-dependent fuel consumption model associated with the truck information. ### Claim 11 (depends on 10) The system of claim 10 wherein the processing subsystem is further configured such that the generalized cost function for each edge also includes a term reflecting a user fee for driving the truck on the corresponding road. ### Claim 12 (depends on 8) The system of claim 8 wherein the processing subsystem is further configured such that the current value λ0 is selected by computing an average of an upper bound λU and a lower bound λL on the dual variable λ. ### Claim 13 (depends on 12) The system of claim 12 wherein the processing subsystem is further configured such that performing the binary search in the dual problem space further includes, 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. ### Claim 14 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. ### Claim 15 (depends on 14) The non-transitory computer-readable storage medium of claim 14 wherein the input information is received from an in-vehicle computing device communicatively coupled to the computer system by a wide-area network and wherein providing the optimal route and speed to the user includes transmitting a report specifying the optimal route and speed to the in-vehicle computing device. ### Claim 16 (depends on 14) The non-transitory computer-readable storage medium of claim 14 wherein the user drives the truck in accordance with the optimal route and speed from the starting location to the destination location. ### Claim 17 (depends on 14) The non-transitory computer-readable storage medium of claim 14 wherein the generalized cost function for each edge is determined based at least in part on a fuel-rate-speed function derived from a characteristic of the corresponding road and the speed-dependent fuel consumption model associated with the truck information.