# US 2020/0393262 A1 · Travel time determining method and apparatus, computer device, and storage medium

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

- Number: US 2020/0393262 A1
- Document ID: US20200393262A1
- Status: Published application
- Kind: A1
- Application number: 17/004,442
- Filed: 2020-08-27
- Published: 2020-12-17
- Earliest claimed: 2018-07-23
- Assignees: Tencent Technology (Shenzhen) Company Limited
- Applicants: Tencent Technology (Shenzhen) Company Limited
- Inventors: Yuting LIU
- Web page: https://patentgrep.com/patent/US20200393262A1

## CPC

- G01C 21/3492: {employing speed data or traffic data, e.g. real-time or historical (traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968)}
- G01C 21/3415: {Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents}
- G06F 18/214: Generating training patterns; Bootstrap methods, e.g. bagging or boosting
- G06V 10/764: using classification, e.g. of video objects
- G06V 10/82: using neural networks
- G06V 20/54: of traffic, e.g. cars on the road, trains or boats
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

Aspects of the disclosure provide a method that can include obtaining a to-be-traveled target route, and determining for a first road section and a second road section adjacent to each other in any two positions starting from the first one of the plurality of road sections, a travel time of the first road section according to first state data of the first road section based on a travel time selection model and a state data prediction model, and determining second state data of the second road section after the first road section is traveled through according to the travel time under the first state data. The method can further include continuing to determine a travel time of the second road section according to the second state data based on the travel time selection model and the state data prediction model, until a travel time of each road section is determined.

## Claims

### Claim 1

A travel time determining method, the method comprising:
obtaining, by processing circuitry, a to-be-traveled target route that includes a plurality of road sections that are arranged sequentially;
determining, by the processing circuitry, a travel time of a first road section according to first state data of the first road section based on a travel time selection model and a state data prediction model, and second state data of a second road section after the first road section is traveled through according to the travel time under the first state data, the second road section being adjacent the first road section; and
continuing, by the processing circuitry, to determine a travel time of the second road section according to the second state data based on the travel time selection model and the state data prediction model, until a travel time of each road section in the plurality of road sections is determined,
wherein the travel time selection model is used to determine travel time of any road section according to state data of the any road section, and the state data prediction model is used to determine state data of a next road section of the any road section according to the state data and the travel time of the any road section.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
inputting, by the processing circuitry, the first state data to the travel time selection model and determining the travel time of the first road section based on the travel time selection model; and
inputting, by the processing circuitry, the first state data and the travel time to the state data prediction model and determining the second state data based on the state data prediction model.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
inputting the first state data to the travel time selection model, determining probabilities of a plurality of travel times based on the travel time selection model, and selecting a plurality of alternative travel times of the first road section from the plurality of travel times according to the probabilities of the plurality of travel times;
inputting, for each alternative travel time, the first state data and the alternative travel time to the state data prediction model, and determining, based on the state data prediction model, alternative state data of the second road section after the first road section is traveled through according to the alternative travel time under the first state data; and
determining, according to alternative state data corresponding to the plurality of alternative travel times, the travel time of the first road section and the second state data corresponding to the travel time.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the determining, according to alternative state data corresponding to the plurality of alternative travel times, the travel time of the first road section and the second state data corresponding to the travel time further comprises:
inputting the alternative state data corresponding to each alternative travel time to a payoff value prediction model, obtaining a payoff value of each alternative state data based on the payoff value prediction model, the payoff value being used for measuring prediction accuracy of the corresponding state data;
selecting, from the alternative state data corresponding to the plurality of alternative travel times, alternative state data having a maximum payoff value and determining the selected alternative state data as the second state data; and
determining, the alternative travel time corresponding to the second state data as the travel time of the first road section.

### Claim 5 (depends on 1)

The method according to claim 1, wherein:
the state data of any road section includes a real-time travel speed of the any road section,
the state data prediction model includes a first speed prediction model, and
the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
determining the travel time of the first road section according to the first state data based on the travel time selection model and the state data prediction model;
determining, according to a current time point and the travel time of each road section before the first road section, a first time point of reaching a start point of the first road section, and obtaining a real-time travel speed of the first road section at the first time point; and
inputting the real-time travel speed of the first road section at the first time point and the travel time of the first road section to the first speed prediction model, and determining a real-time travel speed of the second road section at a second time point based on the first speed prediction model, the second time point being determined according to the first time point and the travel time.

### Claim 6 (depends on 1)

The method according to claim 1, wherein:
the state data of any road section includes a real-time travel speed of each road section after the any road section,
the state data prediction model includes a second speed prediction model, and
the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
determining the travel time of the first road section according to the first state data based on the travel time selection model and the state data prediction model;
determining, according to a current time point and the travel time of each road section before the first road section, a first time point of reaching a start point of the first road section, and obtaining a real-time travel speed of each road section after the first road section at the first time point; and
inputting the real-time travel speed of each road section after the first road section at the first time point and the travel time of the first road section to the second speed prediction model, and determining a real-time travel speed of each road section after the second section at a second time point based on the second speed prediction model, the second time point being determined according to the first time point and the travel time.

### Claim 7 (depends on 1)

The method according to claim 1, the method further comprising:
obtaining, by processing circuitry, historical travel data of each road section in at least one sample route, the historical travel data of the road section including the travel time of the road section and state data of the road section;
constructing, by the processing circuitry, a plurality of first sample data groups according to the obtained historical travel data, each first sample data group including a state data group and the travel time of the road section corresponding to the state data group;
performing, by the processing circuitry, training according to the plurality of first sample data groups in order to obtain the travel time selection model; and
constructing, by the processing circuitry, a plurality of second sample data groups according to the obtained historical travel data, each second sample data group including a state data group, the travel time of the road section corresponding to the state data group, and a next state data group of the state data group, and performing training according to the plurality of second sample data groups in order to obtain the state data prediction model.

### Claim 8 (depends on 7)

The method according to claim 7, the method further comprising:
obtaining, by the processing circuitry, for each sample route, a global reward value of the sample route and a local reward value of each road section in the sample route, the global reward value being used for measuring accuracy of a travel time of the sample route, and the local reward value being used for measuring accuracy of the travel time of a corresponding road section;
obtaining, by the processing circuitry, for first sample state data of any road section in the at least one sample route, a payoff value of the first sample state data according to a payoff value of next sample state data of the first sample state data in each sample route, a probability of transition from the first sample state data to the next sample state data, and a payoff value of the next sample state data when transitioning from the first sample state data to the next sample state data, until the payoff value of each state data in the at least one sample route is obtained,
wherein payoff value of final state data in any sample route is equal to a sum of the global reward value of the sample route and the local reward value of each road section in the sample route; and
performing, by the processing circuitry, training according to each state data and the payoff value of each state data, in order to obtain a payoff value prediction model that is used for obtaining a payoff value of any state data according to the any state data.

### Claim 9 (depends on 8)

The method according to claim 8, wherein the obtaining the global reward value of the sample route and the local reward value of each road section in the sample route further comprises:
determining a predicted travel time of each road section in the sample route based on the currently trained travel time selection model and state data prediction model;
obtaining a predicted total travel time of the sample route according to the predicted travel time of each road section, and determining the global reward value of the sample route according to a first error between the predicted total travel time of the sample route and an actual total travel time of the sample route, the global reward value being inversely proportional to the first error; and
determining the local reward value of each road section according to a second error between the predicted travel time of each road section and an actual travel time of each road section, the local reward value being inversely proportional to the second error.

### Claim 10 (depends on 8)

The method according to claim 8, wherein the obtaining the payoff value of the first sample state data according to the payoff value of next sample state data of the first sample state data in each sample route, the probability of transition from the first sample state data to the next sample state data, and the payoff value of the next sample state data when transitioning from the first sample state data to the next sample state data comprises:
obtaining the payoff value of the first sample state data by using the following formula:
V
π

(
s
i
)
=
∑
s
i
+
1
∈
s

P

(
s
i
+
1
|
s
i
,
a
i
)

[
R

(
s
i
+
1
|
s
i
,
a
i
)
+
γ

V
π

(
s
i
+
1
)
]
,
where si representing the first sample state data, Vπ(si) representing the payoff value of the first sample state data, si+1 representing the next sample state data, Vπ(si+i) representing the payoff value of the next sample state data, S representing a set including all next sample state data of the first sample state data in the at least one sample route, and π representing a travel policy comprising travel times of a plurality of road sections; and
P(si+1|si,ai) representing the probability of transition from the first sample state data to the next sample state data, and being equal to a probability of a travel time used during transition from the first sample state data to the next sample state data, R(si+1|si,ai) representing the payoff value of the next sample state data under the condition of transition from the first sample state data to the next sample state data, and being equal to a local reward value of a road section that is traveled through during transition from the first sample state data to the next sample state data, and γ representing a discount factor.

### Claim 11

A travel time determining apparatus, the apparatus comprising:
processing circuitry that is configured to perform operations comprising:
obtaining a to-be-traveled target route including a plurality of road sections arranged sequentially;
determining a travel time of a first road section according to first state data of the first road section based on a travel time selection model and a state data prediction model, and second state data of a second road section after the first road section is traveled through according to the travel time under the first state data, the second road section being adjacent the first road section;
determining a travel time of the second road section according to the second state data based on the travel time selection model and the state data prediction model, until a travel time of each road section in the plurality of road sections is determined; and
determining a travel time of any road section according to state data of the any road section, and the state data prediction model being used for determining state data of a next road section of the any road section according to the state data and the travel time of the any road section.

### Claim 12 (depends on 1)

A computer device comprising processing circuitry configured to cause the computer device to implement operations comprising the travel time determining method according to claim 1.

### Claim 13 (depends on 12)

The computer device according to claim 12, wherein the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
inputting the first state data to the travel time selection model and determining the travel time of the first road section based on the travel time selection model; and
inputting the first state data and the travel time to the state data prediction model and determining the second state data based on the state data prediction model.

### Claim 14 (depends on 12)

The computer device according to claim 12, wherein the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
inputting the first state data to the travel time selection model, determining probabilities of a plurality of travel times based on the travel time selection model, and selecting a plurality of alternative travel times of the first road section from the plurality of travel times according to the probabilities of the plurality of travel times;
inputting, for each alternative travel time, the first state data and the alternative travel time to the state data prediction model, and determining, based on the state data prediction model, alternative state data of the second road section after the first road section is traveled through according to the alternative travel time under the first state data; and
determining, according to alternative state data corresponding to the plurality of alternative travel times, the travel time of the first road section, and the second state data corresponding to the travel time.

### Claim 15 (depends on 12)

The computer device according to claim 12, wherein:
the state data of any road section includes a real-time travel speed of the any road section,
the state data prediction model includes a first speed prediction model, and
the determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
determining the travel time of the first road section according to the first state data based on the travel time selection model and the state data prediction model;
determining, according to a current time point and the travel time of each road section before the first road section, a first time point of reaching a start point of the first road section, and obtaining a real-time travel speed of the first road section at the first time point; and
inputting the real-time travel speed of the first road section at the first time point and the travel time of the first road section to the first speed prediction model, and determining a real-time travel speed of the second road section at a second time point based on the first speed prediction model, the second time point being determined according to the first time point and the travel time.

### Claim 16

A non-transitory computer-readable storage medium storing computer-readable instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:
obtaining a to-be-traveled target route that includes a plurality of road sections arranged sequentially;
determining a travel time of a first road section according to first state data of the first road section based on a travel time selection model and a state data prediction model, and second state data of a second road section after the first road section is traveled through according to the travel time under the first state data, the second road section being adjacent the first road section; and
continuing to determine a travel time of the second road section according to the second state data based on the travel time selection model and the state data prediction model, until a travel time of each road section in the plurality of road sections is determined,
wherein the travel time selection model is used to determine the travel time of any road section according to state data of the any road section, and the state data prediction model is used to determine state data of a next road section of the any road section according to the state data and the travel time of the any road section.

### Claim 17 (depends on 16)

The storage medium according to claim 16, wherein determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
inputting the first state data to the travel time selection model, and determining the travel time of the first road section based on the travel time selection model; and
inputting the first state data and the travel time to the state data prediction model, and determining the second state data based on the state data prediction model.

### Claim 18 (depends on 16)

The storage medium according to claim 16, wherein determining the travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
inputting the first state data to the travel time selection model, determining probabilities of a plurality of travel times based on the travel time selection model, and selecting a plurality of alternative travel times of the first road section from the plurality of travel times according to the probabilities of the plurality of travel times;
inputting, for each alternative travel time, the first state data and the alternative travel time to the state data prediction model, and determining, based on the state data prediction model, alternative state data of the second road section after the first road section is traveled through according to the alternative travel time under the first state data; and
determining, according to alternative state data corresponding to the plurality of alternative travel times, the travel time of the first road section, and the second state data corresponding to the travel time.

### Claim 19 (depends on 18)

The storage medium according to claim 18, wherein determining, according to alternative state data corresponding to the plurality of alternative travel times, the travel time of the first road section, and the second state data corresponding to the travel time further comprises:
inputting the alternative state data corresponding to each alternative travel time to a payoff value prediction model, obtaining a payoff value of each alternative state data based on the payoff value prediction model, the payoff value being used for measuring prediction accuracy of the corresponding state data;
selecting, from the alternative state data corresponding to the plurality of alternative travel times, alternative state data having a maximum payoff value, and determining the selected alternative state data as the second state data; and
determining the alternative travel time corresponding to the second state data as the travel time of the first road section.

### Claim 20 (depends on 16)

The storage medium according to claim 16, wherein:
the state data of any road section includes a real-time travel speed of the any road section,
the state data prediction model includes a first speed prediction model,
the determining a travel time of the first road section according to first state data of the first road section based on the travel time selection model and the state data prediction model, and second state data of the second road section after the first road section is traveled through according to the travel time under the first state data further comprises:
determining the travel time of the first road section according to the first state data based on the travel time selection model and the state data prediction model;
determining, according to a current time point and the travel time of each road section before the first road section, a first time point of reaching a start point of the first road section, and obtaining a real-time travel speed of the first road section at the first time point; and
inputting the real-time travel speed of the first road section at the first time point and the travel time of the first road section to the first speed prediction model, and determining a real-time travel speed of the second road section at a second time point based on the first speed prediction model, the second time point being determined according to the first time point and the travel time.
