Real time vehicle guidance and forecasting system under traffic jam conditions

• US 6,480,783 B1
• Filed: 03/17/2000
• Issued: 11/12/2002
• Est. Priority Date: 03/17/2000
• Status: Expired due to Term

• Current Assignee: Makor Issues & Rights Ltd.
• Original Assignee: Makor Issues & Rights Ltd.
• Inventors: Myr, David
• Primary Examiner(s): Nguyen, Tan
• Assistant Examiner(s): Tran, Dalena
• Application Number:
  US09/528,134
• Time in Patent Office: 970 Days
• Field of Search: 701/117, 701/118, 701/119, 701/213, 701/200, 701/201, 701/210, 701/211, 701/209, 701/207, 701/208, 340/995, 340/905, 340/989, 340/990, 340/991, 340/993, 340/994, 455/507, 455/509, 455/457
• US Class Current: 701/117
• CPC Class Codes: 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
• CPC Class Codes: G08G 1/096811 where the route is computed offboard
• CPC Class Codes: G08G 1/096816 where the complete route is transmitted to the vehicle at once
• CPC Class Codes: G08G 1/096838 where the user preferences are taken into account or the user selects one route out of a plurality
• CPC Class Codes: G08G 1/096844 where the complete route is dynamically recomputed based on new data
• CPC Class Codes: G08G 1/096872 where instructions are given per voice
• CPC Class Codes: G08G 1/096883 where input information is obtained using a mobile device, e.g. a mobile phone, a PDA

Abstract

A system and method for real time vehicle guidance by Central Traffic Unit are presented. The proposed vehicle Guidance System includes a plurality of vehicles equipped with Individual Mobile Units including GPS units (position determining systems adapted to determine their present position) and communicatively linked to the Central Traffic Unit computer server. The Central Traffic Unit broadcasts the updated traffic patterns in real time thereby enabling the Individual Mobile Units to dynamically calculate the desired optimal travel paths. In response to a request from a driver for a route update from his present position to a desired destination, the Individual Mobile Unit searches for an optimal (usually fastest) route and shows it to the driver. In route searching by the minimal time criterion, the Individual Mobile Unit relies on estimated travel times stored in its database, and may also use current real time information on bottleneck situations received from Central Traffic Unit. The forecasting system allows the driver to enter alternative time schedules for the same destination and receive alternative travel time estimates for the same destination depending on the estimated traffic volumes on the roads at that particular time. The backbone of the system is a group of Sample Mobile Units equipped with RF transmitters that communicate their present position to the Central Traffic Unit at predetermined time intervals. The Central Traffic Unit uses those sample vehicles as antennas by tracking their positions for creating and maintaining a network of real time traffic load disposition in various geographical areas. To be able to detect a bottleneck situation when it arises and to estimate a current travel time for a corresponding section of road, the Central Traffic Unit maintains a list of sample vehicles that recently exited that section. If the times those vehicles have spent on the section differ considerably from a regular time stored in the database, Central Traffic Unit uses statistical tools for forecasting the future travel time along this section. Simultaneously, the Central Traffic Unit broadcasts updated travel times and any new information on current traffic jams and slow-down bottleneck situations in a given geographical location.

Claims

1. Multi-layer vehicular navigation system, where preferred starting point and destination point of the navigation route are significantly geographically different from each other, the system comprising:

a wireless communications system for communicating with client vehicles, and a computer system operatively connected to the communications system, the computer system performing a hierarchically computed route search based on current and statistical section data by choosing roads with fastest classifications first, the computer system further combining data from intermediate layers subsequently and slowest rated roads last and then applying predicted road section coefficients corresponding to each route section;

receiving device for collecting GPS data at predetermined time intervals from sample vehicles moving within a predefined geographical region;

map database containing digital road maps of a predefined geographical region together with predetermined relevant data on road factors;

said computer system operatively connected to the communications system capable of processing in real time said GPS data and transforming them into appropriately structured data suitable for being stored on the computer;

a database suitable for storing and updating statistical data on traffic loads on individual roads;

statistical application for collecting structured GPS data, computing individual statistical travel time estimates (regular times) for predetermined roads, and storing the results;

statistical means application for periodical updating of the said statistical data using statistical criteria for determining volumes of data necessary for obtaining valid and reliable estimates; and

computational tools for automatic identification of real time traffic jam conditions at various locations of the individual roads by utilizing the sample vehicles for measuring time delays.

2. The multi-layer vehicular navigation system of claim 1, comprising:

receiving device for collecting GPS data at predetermined time intervals from a limited number of sample mobile units moving within a predefined geographical region;

map database containing digital road maps of the entire predefined geographical region (country, state, etc.) together with predetermined relevant data on speed limits, road capacity, road category, one-way or two-way designations, entry and exit ramps, left and right turns, and other road factors;

said computer system operatively connected to the communications system capable of processing in real time said GPS data and transforming them into appropriately structured data suitable for being stored on the computer hard disk and being retrieved for future use;

a database suitable for storing and updating statistical data on traffic loads on a limited number of individual roads (defined as roads of category A), and also on all other roads (defined as roads of category B) which are classified according to the standard road classifications;

table of administrator, said statistical data further subdivided into finer categories according to day of the week, hour of the day, etc., and stored accordingly;

statistical application for collecting structured GPS data, computing individual statistical time travel estimates (regular times) for category A roads, and storing the results in the table of administrator according to said fine subdivisions;

statistical application for collecting said structured GPS data, computing common statistical time travel estimates for category B roads (regular times), and storing the results in table of administrator according to said fine subdivisions;

statistical means application for periodical updating of the said statistical data using statistical criteria for determining volumes of data necessary for obtaining valid and reliable estimates;

computational tools for real time traffic jam identification at various locations of category A roads by utilizing the limited number of said sample vehicles that are used as “

antennas”

for measuring time delays due to road congestion;

computational tools for dividing said geographical region into appropriate number of smaller geographical zones for the dual purpose of reducing volumes of traffic load data that will be broadcasted at predetermined time intervals to client vehicles, and for reducing the complexity of computations being made by on-vehicle computers;

transmitting device for one-to-many IP multicasting of real time traffic load data updates to all registered clients;

wherein multicasting of data is done on regional geographical basis according to said smaller geographical zones and is disseminated to end-users traveling within given geographical regions based on their GPS vehicle positions.

3. The multi-layer vehicular navigation system of claim 1, comprising limited but significant number of sample mobile units carrying GPS location units and RF transmitters for transmitting at predetermined time intervals their GPS data to CTU for further processing.

4. Client mobile unit guidance system for motor vehicles, the system comprising computing units capable of updating current travel times tables, predicted or estimated travel times tables and statistical travel times data tables continuously or according to predetermined time intervals from a central traffic unit, wherein the systems further includes:

receiving device for allowing collection of GPS data at predetermined time intervals from sample vehicles moving within a predefined geographical region;

map database containing digital road maps of a predefined geographical region together with predetermined relevant data on road factors;

said computer system operatively connected to the communications system capable of processing in real time said GPS data and transforming them into appropriately structured data suitable for being stored on the computer;

a database suitable for storing and updating statistical data on traffic loads on individual roads;

statistical application for collecting structured GPS data, computing individual statistical travel time estimates (regular times) for predetermined roads, and storing the results;

statistical means application for periodical updating of the said statistical data using statistical criteria for determining volumes of data necessary for obtaining valid and reliable estimates; and

computational tools for real time traffic jam identification at various locations of the individual roads by utilizing the sample vehicles for measuring time delays,

wherein the received data are used for estimating statistical models of traffic situations, and the client mobile units are provided with optimal travel routes based on those statistical models.

5. The client mobile unit guidance system of claim 4 wherein:

each of said client mobile units carries GPS location units, IP multicast receivers, on-vehicle computers, map databases, guidance software, and display units;

said IP multicast receivers are used for periodically receiving travel time traffic updates from CTU;

said guidance software is based on mathematical and Artificial Intelligence algorithms together with map databases for calculating fastest available travel routes from the present vehicle position to the desired destination while taking into account both statistical travel times and current travel times;

said travel time traffic updates from CTU are automatically entered in the database and the alternate travel route is proposed for the desired destination;

said statistical travel times are transferred from CTU to on-vehicle databases via multicasting, and said current travel times are calculated by on-vehicle computers using said guidance software;

calculation of said current travel times in traffic congestion is made directly by a special algorithm based only on said travel time traffic updates rather than using any vehicle speed estimates in traffic jams (as many if not all speed measurements may return zero values, thereby making the resulting estimates highly unstable and unreliable);

estimation of said current travel times for class A roads is based on regression prediction methods thereby enabling to detect increasing time delays when road congestion is growing, or alternatively, to detect decreasing time delays when road congestion is decreasing;

said fastest travel routes are calculated using said current travel times in the zones contiguous to the vehicle while using statistical travel times in the zones situated further from the vehicle because traffic jams far away from the present location of the vehicle may not be relevant for route planning at the given moment.

6. The system in claim 4 further comprising computing units capable of calculating an optimal fastest short and long range composite travel route for a predetermined extended time period corresponding to client'"'"'s position or requested starting and destination points by calculating an optimal fastest short and long range composite travel route for a predetermined extended time period corresponding to client'"'"'s position or requested starting and destination points.

7. The system in claim 4 further comprising computing units capable of calculating an optimal fastest short and long range composite travel route for 2 hours or more corresponding to client'"'"'s position or requested starting and destination points by calculating an optimal fastest short and long range composite travel route for a predetermined extended time period corresponding to client'"'"'s position or requested starting and destination points.

8. The system in claim 4 further comprising computing units capable of updating current travel times data in specified area only for current real time updates from the central traffic unit.

9. The system in claim 4 further comprising computing units capable of updating statistical travel times data in specified area only for current real time updates from the Central Traffic Unit.

10. The system in claim 4 further comprising computing units capable of updating standard travel times in specified area only for current real time updates from the central traffic unit.

11. The system in claim 4 further comprising computing units with multi-layer vehicular navigation capabilities the computing units including multi-layer vehicular navigation system, in which a preferred starting point and destination point of the navigation route are significantly geographically different from each other, the navigation system performing a hierarchically computed route search based on current and statistical section data by choosing roads with fastest classifications first, combining data from intermediate layers subsequently and slowest rated roads last and then applying predicted road section coefficients corresponding to each route section, wherein the client mobile unit obtains preferred starting and destination point from client input and performs multi-layer route search.

17. The method in claim 4 comprising mathematical optimization of estimated travel times, wherein the travel times in the current area are based on current time range within 20 minutes of the current position and are computed with data from intermediate 20 to 60 minutes travel range, corresponding to an intermediate geographical area, the intermediate travel range based on statistical predictions or other traffic delay reports and forecasted estimates consisting of travel times in 1 to 2 hour or longer range based on statistical travel times collected for that given period.

12. Method of operating a central traffic guidance unit comprising method of calculating an optimal fastest short and long range composite travel route for a predetermined extended time period corresponding to client'"'"'s position or requested starting and destination points;

collecting GPS data at predetermined time intervals from sample vehicles moving within a predefined geographical region;

providing a map database containing digital road maps of a predefined geographical region together with predetermined relevant data on road factors;

processing in real time said GPS data and transforming them into appropriately structured data suitable for being stored on using a computer system operatively connected to a communications system;

storing and updating statistical data on traffic loads on individual roads;

subdividing said statistical data into subdivisions according to time factors;

collecting GPS data and computing individual statistical travel time estimates (regular times) for predetermined roads, and storing the results according to said subdivisions;

periodical updating of the said statistical data using statistical criteria for determining volumes of data necessary for obtaining valid and reliable estimates;

computing real time traffic jam identification at various locations of the individual roads by utilizing the sample vehicles for measuring time delays; and

transmitting real time traffic load data updates.

13. The method of claim 12, wherein the extended time period is at least 2 hours.

14. The method in claim 12 further comprising measurements and calculations of longer-term traffic conditions and delays which may immediately influence the optimal route selection now and may require revision of the current travelling route accordingly.

15. The method in claim 12 further comprising mathematical optimization of estimated travel times, wherein the travel times in the current area are based on current time range within a first predetermined estimated travel time from the current position and are computed with data from a predetermined intermediate time range of travel and estimates consisting of travel times within a longer predetermined time range based on statistical travel times collected for that given period.

16. The method of claim 15 comprising determining the intermediate time range statistical predictions.

18. The method in claim 12 further comprising multi-stage calculations of optimal travel route based on accumulated time criteria algorithms in which different time ranges are used for searching for optimal route solutions at each different stage.

19. The method of claim 18, comprising obtaining the different time ranges used for searching for optimal route solutions at each different stage from predicted current travel times, statistical travel times and standard travel times.

20. The method in claim 12 further comprising continuous tracking sample data lists for each corresponding road section by maintaining current status Entry List classified by current IDs and entry times of all sample vehicles, past and current duration of travel on the given section, wherein Exit times of all sample (reporting) vehicles which left that road section within a given time interval are registered in Exit Lists containing also the vehicles IDs and past travel history interval with all appropriate travel times for statistical prediction computations.

21. The method in claim 12 further comprising short time range statistical estimates of current travel times for any road section wherein up to 20 minutes advanced statistical predictions are prepared by regressing a set of registered travel times of all vehicles on the corresponding Exit List on their registered entry times and making short time range statistical predictions of travel times for the corresponding road section within a given short time horizon.

22. The method in claim 12 further comprising establishing short time range statistical estimates of current travel times for a predetermined short time range by using statistical predictions obtained by regressing a set of registered travel times of all vehicles on a corresponding exit list based on their registered entry times.

23. The method in claim 12 further comprising:

establishing short time range statistical estimates of current travel times by using statistical predictions prepared by regressing a set of registered travel times of all vehicles on a corresponding exit list based on their registered entry times; and

making short time range statistical predictions of travel times for the corresponding road section within a given short time horizon.