# US 11,079,244 B2 · Methods and systems for estimating time of arrival > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,079,244 B2 - Document ID: US11079244B2 - Status: Granted - Kind: B2 - Application number: 16/713,049 - Filed: 2019-12-13 - Published: 2020-04-16 - Granted: 2021-08-03 - Earliest claimed: 2017-06-22 - Assignees: Beijing Didi Infinity Technology and Development Co., Ltd. - Applicants: Beijing Didi Infinity Technology and Development Co., Ltd. - Inventors: Shujuan Sun; Xinqi Bao; Zheng Wang - Web page: https://patentgrep.com/patent/US11079244B2 ## CPC - G01C 21/343: {Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047)} - G08G 1/0129: {for creating historical data or processing based on historical data} - G01C 21/3407: {specially adapted for specific applications} - G01C 21/3484: {Personalized, e.g. from learned user behaviour or user-defined profiles} - 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/3691: {Retrieval, searching and output of information related to real-time traffic, weather, or environmental conditions (arrangements for giving variable traffic instructions G08G1/09)} - G06N 3/0442: characterised by memory or gating, e.g. long short-term memory [LSTM] or gated recurrent units [GRU] - G06N 3/045: Combinations of networks - G06N 3/0499: Feedforward networks - G06N 3/08: Learning methods - G06N 3/09: Supervised learning - G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem - G08G 1/0112: {from the vehicle, e.g. floating car data [FCD]} - G08G 1/0133: {for classifying traffic situation} - G08G 1/0141: {for traffic information dissemination} - G08G 1/096827: {where the route is computed onboard} - G08G 1/09685: {where the complete route is computed only once and not updated} - G08G 1/127: to a central station {; Indicators in a central station} - G08G 1/205: {Indicating the location of the monitored vehicles as destination, e.g. accidents, stolen, rental} - 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) - G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93}) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - 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 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) The system of claim 2, wherein the third sub-model comprises a multi-layer perceptron (MLP) neural network model. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 4) 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. ### Claim 7 (depends on 1) 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. ### Claim 8 (depends on 7) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 1) 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. ### Claim 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 12) The method of claim 12, wherein the third sub-model comprises a multi-layer perceptron (MLP) neural network model. ### Claim 14 (depends on 11) 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. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 14) 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. ### Claim 17 (depends on 11) 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. ### Claim 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.