IP Library Granted Patent US 11,079,244
Granted Patent B2
US 11,079,244 · App. 16/713,049 · Granted Aug 3, 2021

Methods and systems for estimating time of arrival

Inventors: Shujuan Sun (Beijing, CN); Xinqi Bao (Beijing, CN); Zheng Wang (Beijing, CN)
Assignee: BEIJING DIDI INFINITY TECHNOLOGY AND DEVELOPMENT CO., LTD.
G01C21/343G01C21/3484G01C21/3492G01C21/3691G06N3/0454G06N3/08G06Q10/047
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,079,244
App. No.
16/713,049
Granted
Aug 3, 2021
Kind
B2
Abstract

A method for determining an ETA relating to a target route is provided. The method includes obtaining, a target route associated with a user; determining characteristic data relating to the target route, the characteristic data including first feature data corresponding to at least a portion of the target route; obtaining an estimation model, the estimation model including a first sub-model and a second sub-model; determining first cell state data and first hidden state data based on the first feature data and the first sub-model; determining a first vector based on the first cell state data and the first hidden state data; determining second cell state data and second hidden state data based on the first vector and the second sub-model; and determining an ETA relating to the target route based on the second cell state data and the second hidden state data.

Claims (82)

1. A system, comprising:

at least one computer-readable storage medium including a set of instructions; and

at least one processor in communication with the at least one computer-readable storage medium, wherein when executing the set of instructions, the at least one processor is caused to:

obtain a target route associated with a user, the target route including multiple links, each link of the target route being a portion of the target route;

determine characteristic data relating to the target route, wherein the characteristic data includes first feature data including a time sequence composed by feature data corresponding to each link of the multiple links arranged in a time order and second feature data corresponding to a whole of the target route;

obtain an estimation model, wherein the estimation model includes a first sub-model and a second sub-model each of which includes a trained neural network model;

determine first cell state data and a first output of the first sub-model corresponding to each link of the target route based on the first feature data and the first sub-model, wherein

the first sub-model is configured to determine at least one of the first cell state data or the first output corresponding to a link in the time order based on at least one of the first output or the first cell state data corresponding to a previous link in the time order;

determine a first vector based on the first cell state data and the first output of the first sub-model, the first vector including a combination of the first cell state data and the first output corresponding to the multiple links, and the second feature data;

determine second cell state data and a second output of the second sub-model corresponding to the whole of the target route based on the second feature data, the first vector, and the second sub-model; and

determine an estimated time of arrival (ETA) of the user arriving at a destination when the user travels along the target route based on the second cell state data and the second output of the second sub-model.

2. The system of claim 1 , wherein the estimation model further includes a third sub-model, determining the ETA of the user arriving at a destination when the user travels along the target route, wherein the at least one processor is further caused to:

determine a second vector based on the second cell state data and the second output; and

determine the ETA based on the second vector and the third sub-model.

3. The system of claim 2 , wherein the third sub-model comprises a multi-layer perceptron (MLP) neural network model.

4. The system of claim 1 , wherein when obtaining the estimation model, the at least one processor is further caused to:

obtain the estimation model from a storage device, wherein the estimation model stored in the storage device is generated by operations including:

obtain a plurality of historical routes and historical times of arrival of particular users arrived at destinations when the particular users traveled along the plurality of historical routes;

determine historical characteristic data of each of the plurality of historical routes, wherein the historical characteristic data includes first training feature data corresponding to at least a portion of each of the plurality of historical routes; and

generate the estimation model based on the first training feature data and the historical times of arrival of users arrived at the destinations when the users traveled along the plurality of historical routes.

5. The system of claim 4 , wherein the historical characteristic data further includes second training feature data corresponding to each of the plurality of historical routes, and the generating the estimation model based on the first training feature data and the historical times of arrival of users arrived at destinations when the users traveled along the plurality of historical routes includes:

generating the estimation model based, at least in part, on the second training feature data.

6. The system of claim 4 , wherein the generating the estimation model based on the first training feature data and the historical times of arrival of users arrived at destinations when the users traveled along the plurality of historical routes includes:

obtaining an ending time of each of the plurality of historical routes;

sorting the plurality of historical routes according to a chronological order of the ending times of the plurality of historical routes; and

generating the estimation model based on the sorted plurality of historical routes.

7. The system of claim 1 , wherein when obtaining the estimation model, the at least one processor is further caused to:

obtain the estimation model from a storage device, wherein the estimation model stored in the storage device is generated by operations including:

obtaining, from a plurality of historical routes, one or more first training routes and one or more second training routes;

extracting first historical characteristic data and first historical times of arrival of users arrived at destinations when the users traveled along the one or more first training routes;

determining a first ETA determination model based on the first historical characteristic data and the first historical times of arrival;

extracting second historical characteristic data and second historical time of arrival of users arrived at destinations when the users traveled along the one or more second training routes;

determining a second ETA determination model by modifying the first ETA determination model based on the second historical characteristic data and the second historical time of arrival; and

generating the estimation model based on the first ETA determination model and the second ETA determination model.

8. The system of claim 7 , wherein the generating the estimation model based on the first ETA determination model and the second ETA determination model includes:

determining whether an error is less than a value, the error being determined based on one or more third historical routes and the second ETA determination model; and

in response to a determination that the error is less than the value, determining the second ETA determination model as the estimation model.

9. The system of claim 8 , wherein the generating the estimation model based on the first ETA determination model and the second ETA determination model includes:

determining a loss function based on at least one of the first ETA determination model or the second ETA determination model;

determining whether the loss function converges to a first value; and

in response to a determination that the loss function converges to the first value, determining that the error is less than the value.

10. The system of claim 1 , wherein at least one of the first sub-model or the second sub-model comprises a long short term memory (LSTM) neural network model.

11. A method implemented on a computing device having a processor, a storage medium, and a communication platform connected to a network, the method comprising:

obtaining, by the processor, a target route associated with a user, the target route including multiple links, each link of the target route being a portion of the target route;

determining, by the processor, characteristic data relating to the target route, wherein the characteristic data includes first feature data including a time sequence composed by feature data corresponding to each link of the multiple links arranged in a time order and second feature data corresponding to a whole of the target route;

obtaining, by the processor, an estimation model, wherein the estimation model includes a first sub-model and a second sub-model each of which includes a trained neural network model;

determining, by the processor, first cell state data and a first output of the first sub-model corresponding to each link of the target route based on the first feature data and the first sub-model, wherein

the first sub-model is configured to determine at least one of the first cell state data or the first output corresponding to a link in the time order based on at least one of the first output or the first cell state data corresponding to a previous link in the time order;

determine a first vector based on the first cell state data and the first output of the first sub-model, the first vector including a combination of the first cell state data and the first output corresponding to the multiple links, and the second feature data;

determining, by the processor, second cell state data and a second output of the second sub-model corresponding to the whole of the tar et route based on the second feature data, the first vector, and the second sub-model; and

determining, by the processor, an estimated time of arrival (ETA) of the user arriving at a destination when the user travels along the target route based on the second cell state data and the second output of the second sub-model.

12. The method of claim 11 , wherein the estimation model further includes a third sub-model, and the determining of the ETA of the user arriving at a destination when the user travels along the target route further comprises:

determining a second vector based on the second cell state data and the second output; and

determining the ETA based on the second vector and the third sub-model.

13. The method of claim 12 , wherein the third sub-model comprises a multi-layer perceptron (MLP) neural network model.

14. The method of claim 11 , wherein the estimation model is generated by a process, the process comprising:

obtaining a plurality of historical routes and historical times of arrival of particular users arrived at destinations when the particular users traveled along the plurality of historical routes;

determining historical characteristic data of each of the plurality of historical routes, wherein the historical characteristic data includes first training feature data corresponding to at least a portion of each of the plurality of historical routes; and

generating the estimation model based on the first training feature data and the historical times of arrival of users arrived at the destinations when the users traveled along the plurality of historical routes.

15. The method of claim 14 , wherein the historical characteristic data further includes second training feature data corresponding to each of the plurality of historical routes, the generating the estimation model based on the first training feature data and the historical times of arrival of users arrived at the destinations when the users traveled along the plurality of historical routes includes:

generating the estimation model based, at least in part, on the second training feature data.

16. The method of claim 14 , wherein the generating the estimation model based on the first training feature data and the historical times of arrival of users arrived at the destinations when the users traveled along the plurality of historical routes includes:

obtaining an ending time of each of the plurality of historical routes;

sorting the plurality of historical routes according to a chronological order of the ending times of the plurality of historical routes; and

generating the estimation model based on the sorted plurality of historical routes.

17. The method of claim 11 , wherein the estimation model is generated by a process, the process further comprising:

obtaining, from a plurality of historical routes, one or more first training routes and one or more second training routes;

extracting first historical characteristic data and first historical times of arrival of particular users arrived at destinations when the users traveled along the one or more first training routes;

determining a first ETA determination model based on the first historical characteristic data and the first historical times of arrival;

extracting second historical characteristic data and second historical times of arrival of users arrived at destinations when the users traveled along the one or more second training routes;

determining a second ETA determination model by modifying the first ETA determination model based on the second historical characteristic data and the second historical times of arrival data;

determining whether an error is less than a value, the error being determined based on one or more third historical routes and the second ETA determination model; and

in response to a determination that the error is less than the value, determining the second ETA determination model as the estimation model.

18. A non-transitory computer readable medium, comprising at least one set of instructions, wherein when executed by at least one processor of an electronic terminal, the at least one set of instructions causes the at least one processor to perform acts of:

obtaining a target route associated with a user, the target route including multiple links, each link of the target route being a portion of the target route;

determining characteristic data relating to the target route, wherein the characteristic data includes first feature data including a time sequence composed by feature data corresponding to each link of the multiple links arranged in a time order and second feature data corresponding to a whole of the target route;

obtaining an estimation model, wherein the estimation model includes a first sub-model and a second sub-model each of which includes a trained neural network model;

determining first cell state data and a first output of the first sub-model corresponding to each link of the tar et route based on the first feature data and the first sub-model, wherein

the first sub-model is configured to determine at least one of the first cell state data or the first output corresponding to a link in the time order based on at least one of the first output or the first cell state data corresponding to a previous link in the time order;

determining a first vector based on the first cell state data and the first output of the first sub-model, the first vector including a combination of the first cell state data and the first output corresponding to each link, and the second feature data;

determining second cell state data and a second output of the second sub-model corresponding to the whole of the target route based on the second feature data, the first vector, and the second sub-model; and

determining, by the processor, an estimated time of arrival (ETA) of the user arriving at a destination when the user travels along the target route based on the second cell state data and the second output of the second sub-model.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Feb 9, 2021
From: SUN, SHUJUAN; BAO, XINQI; WANG, ZHENG
To: BEIJING DIDI INFINITY TECHNOLOGY AND DEVELOPMENT CO., LTD.
Reel/Frame 055188/0496 →
Continuity (2)
Continuation PCTCN2017089518 · Jun 22, 2017
Related Publication 20200116504A1 · Apr 16, 2020
Cited By (2)
US 12,567,325 US 12,663,122