Multi-objective optimization for real time traffic light control and navigation systems for urban saturated networks

• US 20080094250A1
• Filed: 10/19/2006
• Published: 04/24/2008
• Est. Priority Date: 10/19/2006
• Status: Active Grant

• Current Assignee: Makor Issues & Rights Ltd.
• Original Assignee: Makor Issues & Rights Ltd.
• Inventors: Myr, David
• Granted Patent: US 9,076,332 B2
• Time in Patent Office: Days
• US Class Current: 340/909
• CPC Class Codes: G08G 1/04 using optical or ultrasonic detectors
• CPC Class Codes: G08G 1/081 Plural intersections under common control
• CPC Class Codes: G08G 1/096811 where the route is computed offboard

Abstract

A multiobjective management system for saturated traffic road networks comprising: green wave coordination of locally adaptive traffic control units, traffic movement optimization and live traffic route guidance. Current traffic congestion measurements on intersections are generated from local traffic cameras and remote air-borne conventional cameras and thermal sensing imaging cameras or satellite radar such as SAR/ISAR using optical image brightness analysis. At the first stage of traffic optimization, individual local intersection green times are computed based on current traffic congestion level. At the second stage optimization, the central traffic server uses a multiobjective approach to coordinate the current locally-optimized green times of the first stage and create input constraints for green-way coordination of plurality of traffic lights. The server updates dynamically current cycle start and green times on all network-connected traffic light controllers and also broadcasts recommended travel times, green times and green waves to all on-line client vehicle navigation units. Traffic server and individual client guidance units utilize novel time-dependent modifications of an A*-type algorithm to update current travel and recommended travel times and to execute fastest route searches.

Claims

1. A method for real time adaptive traffic light control of a plurality of intersections, the method comprising the steps of:

a) evaluating traffic flow through the plurality of intersections based on

     1) where and how many vehicles enter each respective intersection and

     2) where and how many vehicles are blocking or causing blockage of exits of each respective intersection; and

b) determining a timing of green lights for said intersections based on step a), based on the number of vehicles that need to exit the intersection so that it is not blocked and based on an ability of said vehicles to utilize said green light.

2. A method for real time adaptive traffic light control of a plurality of intersections according to claim 1, wherein steps a) and b) include the steps of:

a) generating an estimated vehicle loading for each of the plurality of intersections, the vehicle loading including an approach vehicle loading in approaching lane regions of a respective intersection, and an exit vehicle loading in exiting lane regions of the respective intersection;

b) processing the estimated vehicle loading for each of the plurality of intersections to separately optimize traffic light timing parameters corresponding to each of the plurality of intersections, the optimization maximizing a queue clearance through the respective intersection and reducing the vehicle loading for the respective intersection;

c) processing the traffic light timing parameters corresponding to a number of intersections within the plurality of intersections to determine a timing of green lights for the number of intersections; and

d) adjusting the traffic light timing parameters corresponding to the number of intersections based on the determined timing of the green lights.

3. The method according to claim 2, the method further including the steps of:

e) generating recommended travel speeds for road links in order to reach a green light at a next intersection from a current intersection and current travel speeds on the said road links within the plurality of intersections; and

f) generating a fastest route path guidance to client vehicle units and on-line roadside electronic displays based on the recommended travel speeds.

4. The method according to claim 2, step (a) including the step of estimating numbers of vehicles on the approaching lane regions and the exiting lane regions, respectively, of each of the plurality of intersections as a function of an approach or an exit lane length, an average car safe-following distance, an average car length and a current travel speed.

5. The method according to claim 2, step (b) including the step of, for each of the plurality of intersections, computing minimum and maximum cycle lengths for a traffic light of the respective intersection by combining a maximum of all minimal pedestrian crossing times and a minimum of maximal vehicle waiting times on all directions of the respective traffic light.

6. The method according to claim 2, step (b) including the step of using an objective function such that a number of vehicles will clear a traffic light during a whole cycle, the objective function having the constraints of:

a) all green times being between a preset minimal value and a preset maximal value, b) all green times of a same group are equal and c) a sum of all green times of all groups provide together a current adaptive cycle length.

7. The method according to claim 2, wherein step (c) includes using a multiobjective optimization method for adapting the traffic light timing parameters from the number of intersections to produce a green wave coordination of traffic lights corresponding to the number of intersections.

8. The method according to claim 2, wherein step (a) includes generating an estimated vehicle congestion for each of the plurality of intersections and step (b) includes processing the estimated vehicle congestion for each of the plurality of intersections.

9. The method of claim 8, wherein a current vehicle loading and the vehicle congestion on the plurality of intersections is generated from one or more of a space borne high resolution camera, a thermal imaging camera or air satellite surveillance radar including synthetic aperture radar (SAR) or inverse synthetic aperture radar (ISAR) with high spatial resolution.

10. The method according to claim 2, step (a) including the step of estimating the vehicle loading by measuring an image brightness of a captured image for each of the plurality of intersections.

11. The method according to claim 10, wherein, for each of the plurality of intersections, the captured image includes bitmap images collected over a short calibration period and the estimated vehicle loading is generated using a pixel brightness value on specified traffic lane-regions corresponding to the approaching lane regions and the exiting lane regions in the collected bitmap images.

12. The method according to claim 10, wherein the estimated vehicle loading is computed according to a quantity of pixel strings from the captured image in horizontal and vertical directions of a region where a difference of an initial and an ending pixel brightness exceeds a pre-set tolerance brightness value.

13. The method according to claim 2, further including the step of broadcasting current, recommended and predicted travel times on all links from a traffic guidance center to all on-line connected client vehicle databases for on-vehicle fastest route guidance using the traffic light timing parameters of the plurality of intersections.

14. The method according to claim 13, wherein optimal fastest routes to on-line driver units are broadcast from the traffic guidance center according to individual start and destination requests.

15. A method of claim 13, wherein current and recommended travel times updates, and green time durations are broadcast to roadside monitor displays according to corresponding GPS coordinates.

16. The method according to claim 2, wherein step (a) includes correlating intersection video camera views with the respective approaching lane regions and the respective exiting lane regions on a GIS graphic information map and a database system.

17. The method according to claim 16, wherein the method includes constructing and maintaining a central traffic guidance database for storing and updating data on current travel times on all road links in at least one geographical region where each road link contains a directed road segment and a turn-off or a go-through segment, the method including the steps of:

a) constructing and maintaining database tables for storing and updating statistical data on said travel times;

b) subdividing said statistical data into finer categories according to one or more of a day of the week, a type of the day, an hour of the day, fractions of the hour of the day, or weather conditions, and storing the subdivided statistical data;

c) computing real time estimates of travel times along the road links in a vicinity of at least one vehicle that has requested travel guidance;

d) constructing partitioned graphs of road networks for at least one geographical region and pre-computing distances associated with the partitioned graphs; and

e) combining said statistical data and said real time estimates of the travel times along the road links into a temporary combined table for use in route guidance applications.

18. The method according to claim 17, wherein time-dependent modifications of an A*-type algorithm are used in conjunction with the combined temporary table for finding an optimal route for the at least one vehicle that has requested the travel guidance from its present position to a desired destination.

19. The method according to claim 18, wherein the time-dependent A*-type algorithm uses time-dependent estimates for travel times of already covered road links and time-dependent estimation functions for the remaining travel time for destination.

20. The method according to claim 19, wherein the time-dependent A*-type algorithm uses the time-dependent estimation functions for the remaining travel time based on lower bound estimates of the remaining travel route length and on upper bound estimates of feasible travel speeds, including the steps of:

a) constructing the lower bound estimates of the remaining travel route length based on the partitioned graphs of the at least one geographical region and on the pre-computed distances associated with the partitioned graphs; and

b) constructing the upper bound estimates of the feasible travel speeds based on available estimates of travel times and on feasible time windows required for completing the desired route.

21. The method according to claim 2, the method including the step of, for each of the plurality of intersections, generating current travel times and speeds on the respective approach lane regions and the respective exiting lane regions as an inverse ratio of an allowable speed on the corresponding region and a respective currently measured intersection vehicle loading.

22. The method according to claim 21, including the step of predicting short-time travel times for shortest route guidance for user-specified route destinations based on the current travel times and a predicted congestion delay index on each link within a user'"'"'s current geographical position.

23. The method according to claim 22, wherein short-distance travel times are computed based on the generated current travel times that are within less than a 10 minute travel-time radius of a location of the user that has requested travel guidance.

24. A method of claim 22, wherein estimated travel times are generated for at least one location of the user that has requested travel guidance for distances greater than 10 minutes of travel-time using the generated current travel times and recent historical traffic data.