Method and system for traffic prediction based on space-time relation

• US 8,606,727 B2
• Filed: 11/09/2010
• Issued: 12/10/2013
• Est. Priority Date: 12/28/2009
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Company Limited
• Inventors: Wu, Tao, Wang, Shaoya, Hu, Weisong, Liu, Xiaowei, He, Junjian, Rao, Jia
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): HANCHAK, WALTER P
• Application Number:
  US12/942,783
• Publication Number:
  US 20110161261A1
• Time in Patent Office: 1,127 Days
• Field of Search: None
• US Class Current: 706/12
• CPC Class Codes: G08G 1/0104 Measuring and analyzing of parameters relative to traffic conditions

Abstract

A system and method for traffic prediction based on space-time relation are disclosed. The system comprises a section spatial influence determining section for determining, for each of a plurality of sections to be predicted, spatial influences on the section by its neighboring sections; a traffic prediction model establishment section for establishing, for each of the plurality of sections to be predicted, a traffic prediction model by using the determined spatial influences and historical traffic data of the plurality of sections; and a traffic prediction section for predicting traffic of each of the plurality of sections to be predicted for a future time period by using real-time traffic data and the traffic prediction model. An apparatus and method for determining spatial influences among sections, as well as an apparatus and method for traffic prediction, are also disclosed. With the present invention, a spatial influence of a section can be used as a spatial operator and a time sequence model can be incorporated, such that the influences on a current section by its neighboring section for a plurality of spatial orders can be taken into account. In this way, the traffic condition in a spatial scope can be measured more practically, so as to improve accuracy of prediction.

Claims

1. A method for determining spatial influences among sections, comprising:

determining, for each of sections in a road network, a spatial scope having influence on the section, wherein the spatial scope is of a spatial order of N, which is an integer equal to or greater than 1;

extracting, from the road network, neighboring sections of the section within the determined spatial scope, as N-th order influential sections for the section;

classifying the spatial relation between each of the sections and each of its N-th order influential sections into one of predefined types of spatial relation;

performing, for the classified type of spatial relation, correlation analysis based on historical traffic data of the section and its N-th order influential sections of this type of spatial relation, to learn a correlation between the section and its N-th order influential sections for this type of spatial relation; and

step of determining spatial influences of spatial order N for the section based on the learned correlation, wherein each of the spatial influences reflects an extent to which the section is influenced by one of its N-th order influential sections.

2. The method of claim 1, wherein in the spatial scope determining operation, the spatial scope having influence on the section is determined according to the relative spatial locations of the sections in the road network.

3. The method of claim 1, wherein in the spatial scope determining operation, for each of the sections in the road network, a spatial scope that can be reached

within a preset time period by starting travel from the section is determined as the spatial scope having influence on the section.

4. The method of claim 1, wherein the predefined types of spatial relation comprise no relation, precede straight, precede merge, precede intersect,

precede diverge, succeed straight, succeed merge, succeed intersect, and succeed diverge;

or

the predefined types of spatial relation comprise straightforward, left turn and right turn.

5. The method of claim 1, wherein in the spatial influence determining operation, each of the N-th order influential sections of a section is allocated with an influential weight based on the correlation between the section and the N-th order influential section, and the spatial influence on the section by the N-th order influential section is determined using the influential weight.

6. The method of claim 1, wherein the spatial influences on a section by its N-th order influential sections are represented in a vector having a dimension equal to the number of its N-th order influential sections.

7. The method of claim 1, wherein the spatial influences among all of a plurality of sections are represented in a M×

M matrix, M being equal to the number of the plurality of sections and each row or each column of the matrix representing the spatial influences on one of the plurality of sections by its N-th order influential sections.

8. The method of claim 1, wherein, for a changed spatial order N, spatial influences for the changed spatial order N are determined for each of the sections through the spatial scope determining operation, the influential section extraction operation, the spatial relation determining operation, the correlation learning operation and the spatial influence determining operation.

9. The method of claim 1, further comprising:

storing, for each of the sections, the determined spatial influences for at least one spatial order N.

10. The method of claim 1, wherein the historical traffic data comprise, for a particular time period in a day, at least one of the following historical traffic data for each section:

a travel speed at which a vehicle travels along the section,

a travel time period required for a vehicle to travel through the section,

a section congestion indication representing a ratio between an actual travel time period required by a vehicle to actually travel through the section and

a free flow travel time period expected for a vehicle to travel through the section in a free flow condition, or representing a ratio between an actual travel speed at which a vehicle actually travels along the section and a free flow travel speed at which a vehicle travels along the section in a free flow condition.

11. The method of claim 1, wherein a section comprises one of:

a link as basic road element of a road network,

a road segment obtained by analyzing a road network and building a mapping between road segments and links; and

a road segment from one intersection to another adjacent intersection in the road network.

12. A traffic prediction method, comprising:

obtaining real-time traffic data for a plurality of sections within one or more time periods, as prediction input;

selecting a traffic prediction model for each of the sections whose traffic is to be predicted, based on a future time period for which the prediction is to be made and/or a specified time order and/or spatial order, wherein the traffic prediction model is a time sequence model considering spatial relation, and the spatial relation is represented by the spatial influences among the sections as determined by a method for determining spatial influences among sections according to claim 1; and

predicting traffic of each of the sections for a future time period after a specified time period by using the prediction input and the selected traffic prediction model.

13. The method of claim 12, wherein the traffic prediction model comprises a Space-Time Auto Regression (STAR) model or a Space-Time Auto Regression Moving Average (STARMA) model.

14. The method of claim 12, further comprising, after the prediction input obtaining operation:

analyzing the difference between the obtained real-time traffic data and the historical traffic data, adjusting the obtained real-time traffic data based on the analysis result, and using the adjusted real-time traffic data as the prediction input.

15. The method of claim 14, wherein in the data difference analysis operation, the obtained real-time traffic data is adjusted by way of statistical averaging.

22. A method for traffic prediction based on space-time relation, comprising:

determining, for each of a plurality of sections to be predicted, spatial influences on the section by its neighboring sections, by a method for determining spatial influences among sections according to claim 1;

establishing, for each of the plurality of sections to be predicted, a traffic prediction model by using the spatial influences determined at the section spatial influence determining operation and historical traffic data of the plurality of sections; and

predicting traffic of each of the plurality of sections to be predicted for a future time period by using real-time traffic data and the traffic prediction model established at the traffic prediction model establishment operation.

24. The method of claim 1, wherein the spatial relation between each of the sections and each of its N-th order influential sections are classified into different groups based on the spatial relation.

16. An apparatus for determining spatial influences among sections, comprising:

a spatial scope determining unit, implemented by a processor, configured to determine, for each of sections in a road network, a spatial scope having influence on the section, wherein the spatial scope is of a spatial order of N, which is an integer equal to or greater than 1;

an influential section extraction unit configured to extract, from the road network, neighboring sections of the section within the determined spatial scope, as N-th order influential sections for the section;

a spatial relation determining unit configured to classify the spatial relation between each of the sections and its N-th order influential sections into one of predefined types of spatial relation;

a correlation learning unit configured to perform, for the classified type of spatial relation, correlation analysis on historical traffic data of the section and its N-th order influential sections of this type of spatial relation, to learn a correlation between the section and its N-th order influential sections for this type of spatial relation; and

a spatial influence determining unit configured to determine spatial influences for the N-th order influential sections of the section based on the learned correlation, wherein each of the spatial influences reflects an extent to which the section is influenced by one of its N-th order influential sections.

17. The apparatus of claim 16, wherein the spatial scope determining unit determines the spatial scope having influence on the section according to the relative spatial locations of the sections in the road network.

18. The apparatus of claim 16, wherein the spatial scope determining unit determines, for each of the sections in the road network, a spatial scope that can be reached within a preset time period by starting travel from the section as the spatial scope having influence on the section.

19. The apparatus of claim 16, wherein the spatial influence determining unit allocates to each of the N-th order influential sections of a section with an influential weight based on the correlation between the section and the N-th order influential section, and determines the spatial influence on the section by its N-th order influential section using the influential weights.

20. A traffic prediction apparatus, comprising:

a prediction input obtaining unit configured to obtain real-time traffic data for a plurality of sections within one or more time periods, as prediction input;

a traffic prediction model selection unit configured to select a traffic prediction model for each of the sections whose traffic is to be predicted, based on a future time period for which the prediction is to be made and/or a specified time order and/or spatial order, wherein the traffic prediction model is a time sequence model considering spatial relation, and the spatial relation is represented by spatial influences among the sections as determined by an apparatus for determining spatial influences among sections according to claim 16; and

a traffic prediction unit configured to predict traffic of each of the section for a

future time period after a specified time period by using the prediction input and the selected traffic prediction model.

21. The apparatus of claim 20, further comprising:

a data difference analysis unit configured to analyze the difference between the obtained real-time traffic data and the historical traffic data, adjusting the obtained real-time traffic data based on the analysis result, and using the adjusted real-time traffic data as the prediction input.

23. A system for traffic prediction based on space-time relation, comprising:

a section spatial influence determining section, implemented by a processor, configured to determine, for each of a plurality of sections to be predicted, spatial influences on the section by its neighboring sections, by an apparatus for determining spatial influences among sections according to claim 16;

a traffic prediction model establishment section configured to establish, for each of the plurality of sections to be predicted, a traffic prediction model by using the spatial influences determined at the section spatial influence determining section and historical traffic data of the plurality of sections; and

a traffic prediction section configured to predict traffic of each of the plurality of sections to be predicted for a future time period by using real-time traffic data and the traffic prediction model established by the traffic prediction model establishment section.

25. The apparatus of claim 16, wherein the spatial relation between each of the sections and each of its N-th order influential sections are classified into different groups based on the spatial relation.