Grid-based arrival time prediction

• US 9,671,232 B2
• Filed: 05/13/2014
• Issued: 06/06/2017
• Est. Priority Date: 05/13/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Nandan, Naveen
• Primary Examiner(s): Nguyen, Nga X
• Application Number:
  US14/277,015
• Publication Number:
  US 20150330798A1
• Time in Patent Office: 1,120 Days
• Field of Search: 701409, 701400
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G01C 21/3881 Tile-based structures

Abstract

Described herein is a framework for predicting arrival time of moving objects based on grid modeling of location data. In accordance with one aspect of the framework, location data of a moving object is received and positions of the moving object may be identified based on a grid model by mapping the location data to the grid model. The grid model may be segmented into cells where a cell transition time of the moving object from a current cell to another cell may be determined. The arrival time of the moving object may then be predicted based on the cell transition time of the moving object. The arrival time of the moving object may further be presented to one or more user devices.

Claims

1. A computer-implemented method of predicting arrival time, comprising:

providing, by a processor, a grid model comprising a grid of a geographical region, wherein a boundary of the grid is defined using latitude and longitude coordinate points, the grid is segmented into cells based on a set of rows and columns;

receiving, from a signal collection system, location data of a moving object;

identifying, by the processor and based on the grid model, positions of the moving object on the grid by mapping the location data to the cells of the grid, wherein identifying the positions of the moving object comprises calculating the position of the moving object on the grid using a floor function which is a mathematical function which utilizes the coordinate points of the boundaries defined for the grid model, the set of rows and columns used in the segmentation and the location data of the moving object;

determining, by the processor, a cell transition time of the moving object from a current cell to another cell of the grid;

predicting, by the processor, an arrival time of the moving object based on the cell transition time of the moving object; and

presenting the arrival time of the moving object to one or more user devices.

2. The method of claim 1 wherein determining the cell transition time of the moving object comprises determining the transition time within a time window.

3. The method of claim 2 further comprising determining an average cell transition time of all moving objects from the current cell to the other cell within the time window.

4. The method of claim 3 wherein predicting the arrival time of the moving object further comprises calculating the arrival time based on the average cell transition time of all moving objects from the current cell to the other cell.

5. The method of claim 4 wherein the cells are numbered sequentially and further comprising calculating the arrival time of the moving object based on the following algorithm:

C<sub>m→

n</sub>;

T_est←

T_est+(T<sub>m→

n</sub>−

t<sub>m→

n</sub>)

wherein

C<sub>m→

n</sub> is the transition of the moving object from the current cell denoted as m, to the other cell denoted as n;

T_est is the estimated arrival time of the moving object;

t<sub>m→

n</sub> is the cell transition time of the moving object from the current cell m to the other cell n; and

T<sub>m→

n</sub> is the average cell transition time of all moving objects from the current cell m to the other cell n.

6. The method of claim 5 wherein an initial value of T_est may be retrieved from a scheduled arrival time of the moving object.

7. The method of claim 1 wherein the signal collection system is a global positioning system.

8. The method of claim 7 wherein the location data comprises latitude-longitude coordinates points.

9. The method of claim 1 wherein receiving the location data comprises receiving location data stream of the moving object.

10. The method of claim 1 further comprising receiving location data of a plurality of moving objects, the location data comprises object identifier, location information and time stamp information.

11. The method of claim 1 wherein identifying positions of the moving object comprises calculating the position of the moving object on the grid using gridX=floor[{(lat−

lat1)*rows}/(lat2−

lat1)] and gridY=floor[{(lon−

lon1)*columns}/(lon2−

lon1)], wherein floor is the mathematical function, gridX and gridY denote the position of the moving object in the grid model, lat and lon are coordinate points in the received location data of the moving object, lat1, lat2, lon1 and lon2 are boundaries defined for the grid model, rows and columns denote number of rows and columns.

12. The method of claim 11 wherein the set of rows and columns are user defined.

13. The method of claim 11 wherein identifying a position of the moving object based on the grid model comprises determining a cell at which the moving object is located, wherein determining the cell comprises calculating a sequenced number which is assigned to the cell, the calculation is performed using cell_number=((columns*(gridX−

1))+gridY).

14. The method of claim 13 wherein the segmented cells are numbered in sequence.

15. The method of claim 14 further comprising determining a series of cell transitions of the moving object.

16. The method of claim 15 further comprising continuously calculating the arrival time of the vehicle as it transitions between cells.

17. A system comprising:

a non-transitory memory device for storing computer-readable program code; and

a processor in communication with the memory device, the processor being operative with the computer-readable program code to

provide a grid model comprising a grid of a geographical region, the grid is segmented into cells based on a set of rows and columns;

receive location data of a moving object;

identify, based on the grid model, positions of the moving object on the grid by mapping the location data to the cells of the grid, wherein identifying positions of the moving object comprises calculating the position of the moving object on the grid using gridX=floor[{(lat−

lat1)*rows}/(lat2−

lat1)] and gridY=floor[{*(lon−

lon1)*columns}/(lon2−

lon1)], wherein floor is a mathematical function, gridX and gridY denotes the position of the moving object in the grid model, lat and lon are coordinate points in the received location data of the moving object, lat1, lat2, lon1 and lon2 are boundaries defined for the grid model, rows and columns denote number of rows and columns;

determine a cell transition time of the moving object from a current cell to another cell of the grid;

predict an estimated arrival time of the moving object based on the cell transition time of the moving object; and

present the estimated arrival time of the moving object to one or more user devices.

18. The system of claim 17 further comprising determining an average cell transition time of all moving objects from the current cell to the other cell within a time window and predicting the estimated arrival time of the moving object based on the average cell transition time of all moving objects.

19. The system of claim 18 wherein the location data comprises latitude-longitude coordinates points received in real time from a global positioning system.

20. A non-transitory computer-readable medium having stored thereon program code, the program code executable by a computer to perform steps comprising:

providing, by a processor, a grid model comprising a grid of a geographical region, the grid is segmented into cells based on a set of rows and columns;

receiving, from a positioning device, location data of a moving object;

identifying, by the processor and based on the grid model, positions of the moving object on the grid by mapping the location data to the cells of the grid, wherein identifying positions of the moving object comprises calculating the position of the moving object on the grid using gridX=floor[{(lat−

lat1)*rows}/(lat2−

lat1)] and gridY=floor[{(lon−

lon1)*columns}/(lon2−

lon1)], wherein floor is a mathematical function, gridX and gridY denotes the position of the moving object in the grid model, lat and lon are coordinate points in the received location data of the moving object, lat1, lat2, lon1 and lon2 are boundaries defined for the grid model, rows and columns denote number of rows and columns;

determining, by the processor, a cell transition time of the moving object from a current cell to another cell of the grid;

estimating, by the processor, an arrival time of the moving object based on the cell transition time of the moving object; and

presenting the estimated arrival time of the moving object to one or more user devices.