# US 12,601,603 B2 · Carbon footprint optimized timely E-truck transportation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,601,603 B2
- Document ID: US12601603B2
- Status: Granted
- Kind: B2
- Application number: 18/436,350
- Filed: 2024-02-08
- Published: 2025-08-14
- Granted: 2026-04-14
- Earliest claimed: 2024-02-08
- Assignees: City University of Hong Kong
- Applicants: City University of Hong Kong
- Inventors: Minghua Chen; Junyan Su; Qiulin Lin
- Web page: https://patentgrep.com/patent/US12601603B2

## CPC

- G01C 21/3469: {Fuel consumption; Energy use; Emission aspects}
- G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)}
- 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)

## Abstract

Carbon footprint optimization of an electric vehicle, such as a heavy-duty e-truck, traveling in a trip across a highway network subject to a hard deadline constraint and one or more battery state-of-charge (SoC) constraints is carried out by co-determining a route plan, a speed plan and an intermediary charging plan for the electric vehicle with an objective of minimizing a carbon footprint incurred in the trip. In co-determining the three plans, a stage-expanded graph for modeling possible routing decisions of routing the trip in the highway network and possible charging decisions of charging the electric vehicle during the trip is constructed. The stage-expanded graph embeds information of arrival time and arrival SoC to facilitate modeling the charging decisions. The three plans are optimized by a dual subgradient method according to the stage-expanded graph under the objective of minimizing the carbon footprint while satisfying the constraints.

## Claims

### Claim 1

A computer-implemented method for co-determining a route plan, a speed plan and an intermediary charging plan for an electric vehicle to travel in a trip from an origin to a destination across a highway network under a hard deadline constraint and one or more state-of-charge (SoC) constraints, the method comprising:
constructing a stage-expanded graph to model possible routing decisions of routing the trip in the highway network and possible charging decisions of charging the electric vehicle during the trip, wherein the stage-expanded graph embeds information of arrival time and arrival SoC to thereby facilitate modeling the charging decisions; and
optimizing the route plan, speed plan and intermediary charging plan according to the stage-expanded graph under an objective of minimizing a carbon footprint incurred in the trip while satisfying the hard deadline constraint and the one or more SoC constraints;
wherein the constructing of the stage-expanded graph comprises:
preparing a transportation graph for modeling the possible routing decisions, wherein the transportation graph includes a plurality of nodes, an individual node being associated with an arriving event of arriving at a corresponding road segment or corresponding charging station in the highway network;
creating a first number of copies of the plurality of nodes for the stage-expanded graph, wherein an individual copy of the plurality of nodes is associated with a second number and represents a plurality of respective arriving events occurred at a charging stage that the electric vehicle has been charged for the second number of times during the trip; and
forming the stage-expanded graph with the created first number of copies of the plurality of nodes,
wherein the first number is given by Y+1 and the second number is selected from 0 to Y, where Y is a maximum allowable number of times of charging the electric vehicle during the trip.

### Claim 2 (depends on 1)

The method of claim 1, wherein the one or more SoC constraints consist of Y SoC constraints, wherein an i-th SoC constraint, i between 1 and Y, is that the electric vehicle does not run out of battery when the electric vehicle arrives at a charging station to be used for charging the electric vehicle for the i-th time.

### Claim 3 (depends on 1)

The method of claim 1, wherein the route plan, speed plan and intermediary charging plan as optimized are determined by a dual subgradient method.

### Claim 4 (depends on 1)

The method of claim 1, wherein the electric vehicle is an e-truck.

### Claim 5 (depends on 1)

A method for navigating an electric vehicle during a trip from an origin to a destination across a highway network and advising battery charging during the trip under a hard deadline constraint and one or more state-of-charge (SoC) constraints, the method comprising:
co-determining a route plan, a speed plan and an intermediary charging plan for the electric vehicle to travel in a trip from the origin to the destination across the highway network under the hard deadline constraint and the one or more SoC constraints according to the method of claim 1; and
providing navigation instructions and charging advices to the electric vehicle during the trip according to the route plan, speed plan and intermediary charging plan.