Estimating travel times through transportation structures using location traces

Patent metadata

Field	Value
Publication number	US-9691276-B2
Application number	US-201615146163-A
Country	US
Kind code	B2
Filing date	May 4, 2016
Priority date	Jun 10, 2014
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

A method, apparatus, computer program product, and device with various means are disclosed for determining the time it takes to a traverse a transportation structure by enclosing a representation of a transportation structure with a bounding polygon, specifying a plurality of gates which represent legitimate entry or exit points of the transportation structure as one or more edges of the bounding polygon, and computing the travel time for a probe traveling through the bounding polygon via the gates. Computing the probe's travel time comprises generating a location trace of movement of the probe, determining an entry and exit time, and calculating the difference between the exit time and the entry time. Determining the entry and exist time can be done by interpolation. An average of a set of computations can be used to get an average of the time it takes traverse the transportation structure.

First claim

That which is claimed:

1. An apparatus comprising at least one processor and at least one memory including computer program code, wherein the at least one memory and the computer code are configured, with the at least one processor, to cause the apparatus to perform the following:
enclose a representation of a transportation structure with a bounding polygon;
specify a plurality of gates, wherein a gate comprises one or more edges of the bounding polygon that represent a legitimate entry point or exit point of the transportation structure;
generate a location trace of movement of a probe through the bounding polygon;
interpolate at least one of the entry point or the exit point in response to a data point not being available in the generated trace of movement proximate the respective one of the entry point or the exit point; and
compute a travel time for the probe traveling through the bounding polygon via the gates, wherein computing the travel time for the probe comprises causing the apparatus to:
determine an entry time of when the probe passes an entry point;
determine an exit time of when the probe passes an exit point; and
determine the travel time as a difference between the entry time and the exit time.

2. The apparatus of claim 1 , wherein causing the apparatus to enclose the representation of the transportation structure with a bounding polygon comprises causing the apparatus to:
identify a node representing a center of the transportation structure, wherein the transportation structure is an intersection of at least two roadways;
for each of the at least two roadways, determine a delay zone extending a distance from the node of the intersection along a respective one of the at least two roadways;
determine a width for each delay zone, and
generate a bounding polygon comprising the delay zones of each of the at least two roadways.

3. The apparatus of claim 2 , wherein causing the apparatus to determine a width for each delay zone comprises, for each of the at least two roadways, causing the apparatus to determine a width based on a number of lanes of the respective roadway, a width of each lane, and a standard deviation of positioning errors of a determined location of the respective roadway.

4. The apparatus of claim 2 , wherein causing the apparatus to determine a delay zone extending a distance from the node of the intersection along a respective one of the at least two roadways comprises causing the apparatus to determine a distance at which vehicles approaching the intersection begin to decelerate in anticipation of a stop at the intersection.

5. The apparatus of claim 4 , wherein the distance the delay zone extends along a respective one of the at least two roadways is established as the distance at which vehicles approaching the intersection begin to decelerate.

6. A computer program product embodied on a non-transitory computer-readable medium in which a computer program is stored that, when executed by a computer, is configured to provide instructions to control or carry out:
enclosing a representation of a transportation structure with a bounding polygon;
specifying a plurality of gates, wherein a gate comprises one or more edges of the bounding polygon that represent a legitimate entry point or exit point of the transportation structure;
generating a location trace of movement of a probe through the bounding polygon;
interpolate at least one of the entry point or the exit point in response to a data point not being available in the generated trace of movement proximate the respective one of the entry point or the exit point; and
computing a travel time for the probe traveling through the bounding polygon via the gates, wherein computing the travel time for the probe comprises:
determining an entry time of when the probe passes an entry point;
determining an exit time of when the probe passes an exit point; and
determining the travel time as a difference between the entry time and the exit time.

7. The computer program product of claim 6 , further configured to provide instructions to control or carry out:
identifying a node representing a center of the transportation structure, wherein the transportation structure is an intersection of at least two roadways;
for each of the at least two roadways, determining a delay zone extending a distance from the node of the intersection along a respective one of the at least two roadways;
determining a width for each delay zone, and
generating a bounding polygon comprising the delay zones of each of the at least two roadways.

8. The computer program product of claim 7 , wherein the instructions for determining a width for each delay zone comprises, for each of the at least two roadways, instructions for determining a width based on a number of lanes of the respective roadway, a width of each lane, and a standard deviation of positioning errors of a determined location of the respective roadway.

9. The computer program product of claim 7 , wherein the instructions for determining a delay zone extending a distance from the node of the intersection along a respective one of the at least two roadways comprises instructions for determining a distance at which vehicles approaching the intersection begin to decelerate in anticipation of a stop at the intersection.

10. The computer program product of claim 9 , wherein the distance the delay zone extends along a respective one of the at least two roadways is established as the distance at which vehicles approaching the intersection begin to decelerate.

11. A method comprising:
enclosing, by a processor, a representation of a transportation structure with a bounding polygon;
specifying a plurality of gates, wherein a gate comprises one or more edges of the bounding polygon that represent a legitimate entry point or exit point of the transportation structure;
generating, by the processor, a location trace of movement of a probe through the bounding polygon;
interpolating at least one of the entry point or the exit point in response to a data point not being available in the generated trace of movement proximate the respective one of the entry point or the exit point; and
computing a travel time for the probe traveling through the bounding polygon via the gates, wherein computing the travel time for the probe comprises:
determining an entry time of when the probe passes an entry point;
determining an exit time of when the probe passes an exit point; and

determining the travel time as a difference between the entry time and the exit time.

12. The method of claim 11 , further comprising:
identifying a node representing a center of the transportation structure, wherein the transportation structure is an intersection of at least two roadways;
for each of the at least two roadways, determining a delay zone extending a distance from the node of the intersection along a respective one of the at least two roadways;
determining a width for each delay zone, and
generating a bounding polygon comprising the delay zones of each of the at least two roadways.

13. The method of claim 12 , wherein determining a width for each delay zone comprises, for each of the at least two roadways, determining a width based on a number of lanes of the respective roadway, a width of each lane, and a standard deviation of positioning errors of a determined location of the respective roadway.

14. The method of claim 12 , wherein determining a delay zone extending a distance from the node of the intersection along a respective one of the at least two roadways comprises determining a distance at which vehicles approaching the i

Assignees

• Here Global Bv

Inventors

• Xu Bo
• Stroila Matei Nicolae
• Macfarlane Jane

Classifications

• G06T11/23

  using straight lines or curves · CPC title

• G08G1/0104 Primary

  Measuring and analyzing of parameters relative to traffic conditions · CPC title

• G06T2210/12

  Bounding box · CPC title

• G06T15/405

  using Z-buffer · CPC title

• G06T2210/32

  Image data format · CPC title