Method for regional system wide optimal signal timing for traffic control based on wireless phone networks

[0002] This invention relates generally to traffic control systems. More specifically, the present invention relates to a traffic control system that optimizes traffic flow based on information obtained via a wireless telephone network.

[0003] Problems in traffic control have been studied extensively over the last few decades. Conventional traffic control systems comprise three major components: hardware infrastructure, information gathering systems, and traffic control software including mathematical models and algorithms. At present we are primarily interested in software models and algorithms, and in information gathering systems.

[0004] Due to ever increasing traffic volume, traffic control and information acquisition have become an important part of the overall traffic management strategy.

[0005] Generally, dynamic traffic data are gathered by three methods:

[0006] 1. Road sensor devices such as induction loops, traffic detectors, and TV cameras mounted on poles;

[0007] 2. Mobile traffic units such as police, road service, helicopters, weather reporting devices, etc.

[0008] 3. Mobile positioning and communication systems using GPS devices or similar vehicle-tracking equipment.

[0009] The disadvantages of these data collection methods are summarized as follows:

[0010] 1. Relatively high cost of required capital investment into road devices especially when carried out within existing road infrastructures;

[0011] 2. Relatively limited number of organizations such as trucking, delivery and other service companies utilizing reporting vehicles equipped with GPS devices;

[0012] 3. In general only small geographical areas are effectively covered due to specific nature of service tasks, apart from the relatively small number of cars equipped with required GPS devices necessary for precise position determination.

[0013] In a recent development, GPS reporting devices have been mounted on individual cars to provide positioning information of vehicles via wireless mobile communication systems. The additional expenditures required by these mobile systems are much lower than by the traditional methods using fixed road metering. One disadvantage of these systems is in the relatively limited number of cars equipped with required GPS devices necessary for precise position determination, and therefore relatively small geographical areas that can be effectively covered.

[0014] As originally coined, the term “traffic control” implied a human operator, i.e. a policeman, or a specially trained dispatcher who directed traffic flows across road intersections. This “controller” used his experience and intuition to evaluate traffic loads and waiting times in various directions and lanes, and for changing phase timing accordingly.

[0015] Following the introduction of electric traffic signals at the beginning of the twentieth century, progress in the methods of traffic control closely followed that of the control technology, and subsequently the progress of computer science.

[0016] Initially, simple electric clocks allocated a specific amount of time to each phase in a specific pattern to controlled traffic signals. These early clock systems were preset and provided no adjustment for peak traffic periods, or for unusual conditions.

[0017] The next step was to create a clock that operated differently at different times of the day, and used several different control patterns for different times of day. Those patterns were determined from historical data.

[0018] Starting in the mid-1960's, computers were increasingly utilized in traffic control. These computers made it possible to create actuated controllers that had the ability to adjust the signal phase lengths in response to traffic flow in real time. If no vehicles were detected on an approach to an intersection, the controller could skip that phase or reduce the phase to a fixed minimum time. Thus, the green time for each approach was a function of the traffic flow, and could be varied between minimum and maximum lengths depending on traffic flows.

[0019] Modes of operation of modern traffic control systems can be divided into three primary categories: 1) pre-timed; 2) actuated (including both semi-actuated and fully actuated); and 3) traffic responsive. Under pre-timed operation, the master controller sets signal phases and cycle lengths on predetermined rates based on historical data.

[0020] An actuated controller operates based on traffic demands as registered by the actuation of vehicle and/or pedestrian detectors. There are several types of actuated controllers, but their main feature is the ability to adjust the phases in response to traffic flow.

[0021] A semi actuated controller maintains green on the major street except when vehicles are registered on minor streets, and then always return the right of way to the major street.

[0022] A fully actuated controller measures traffic flow on all approaches and makes assignments of the right of way in accordance with traffic demands. As such, a fully actuated controller requires placement of detectors on all approaches to the intersection. Thereby increasing installation and maintenance costs considerably.

[0023] In the traffic responsive mode, the system responds to inputs from traffic detectors and may react in one of the following ways:

[0024] Use vehicle volume data as measured by traffic detectors;

[0025] Perform pattern matching—the volume and occupancy data from system detectors are compared with profiles in memory, and the most closely matching profile is used for decision making;

[0026] Perform future traffic prediction—projections of future conditions are computed based on data from traffic detectors.

[0027] A number of algorithms exist that purport to optimize performance of traffic responsive controllers that make use of various techniques such as linear programming, dynamic programming, fuzzy logic, regression analysis, and optimization and prediction procedures. The objective function that is usually set up to be optimized is some measure of overall traffic delay at an intersection or at a number of intersections, while the major control parameter for achieving this is the distribution of green and red light timings among different phases.

[0028] The usual framework for those algorithms is as follows. Signal timings should reflect the number of vehicles present on each approach to an intersection and the pattern of arrivals in the near future. The current queue lengths on each approach are identified by locating slow-moving and stationary traffic close to the stop-line. Algorithms minimize the total delay subject to certain constraints. Such constraints are:

[0029] 1. Adequate capacity for all allowed traffic movements; and

[0030] 2. Safety constraints (minimum number of seconds for green and inter-green times).

[0031] Minimization is performed over the pre-selected planning time horizon, which limits the forward time interval for which computations are made. As optimization is performed continuously, we have a rolling horizon framework.

[0032] The rate of delay on an approach is estimated as proportional to the number of vehicles in the queue. Accordingly, the total rate of delay at the intersection is the sum over all streams of these rates of delay. The objective function for optimization is the sum of those total rates of delay over the planning time period, which represents the total delay incurred. A slightly different formulation of the objective of optimization is minimization of the weighted sum of the estimated rate of delay and the number of stops per unit time for all traffic streams. In such a formulation the problem is amenable to treatment by mathematical optimization methods. In particular, by dynamic programming and linear programming techniques.

[0033] Most conventional attempts for real time responsive control are either optimized on a per intersection basis or make highly restrictive simplifying assumptions in treating multiple intersection problems. Still, there are a few works treating area-wide traffic control optimization problems. For example, U.S. Pat. No. 5,668,717 issued to James C. Spall proposed the use of neural networks that are able to learn patterns of traffic situations, store them for future use and modify them when the traffic situation changes.

[0034] It appears, though, that at the present time no widely accepted and approved method exists for optimizing traffic control signals on an area wide scale.

[0035] In view of the shortcomings of the prior art, it is an object of the present invention to provide a system and method for optimizing traffic flow based on information received from wireless telephone systems.

[0036] The above-identified disadvantages of the prior art systems may be overcome by using wireless networks as the sole means to provide location information. Technologically, this may be achieved by measuring the distances the signals traveling between a moving wireless (cellular) phone and a fixed set of base stations, and the times these signals take to travel. This information may then be applied to mathematical and statistical methods to solve the resulting equations.

[0037] This exemplary approach takes advantage of improved accuracy of measurement methods and of the large pool of wireless handsets that exist. For example, in the United States alone there are presently about 50 million such handsets. Furthermore, any necessary modifications, such as specialized location equipment, can be made on the network rather than on the handsets.

[0038] The present invention utilizes a cell phone network in which the data from moving vehicles are collected continuously and input into the system. The exemplary system filters and cleans the data by applying intelligent heuristic algorithms and produces accurate real time information on traffic situations that, in turn, can be supplied to automated traffic controllers. This eliminates the need for developing a dedicated mobile wireless information gathering fleet and other high cost devices requiring large capital investments and considerable work force.

[0039] Network system wide control is the means for real time adjustment of the timings of all signals in a traffic network to achieve a reduction in overall congestion consistent with the chosen system wide measure of effectiveness. This real time control is preferably responsive to instantaneous changes in traffic conditions including changes due to various traffic incidents. Also, the system is preferably adaptive in order to reflect daily and hourly non-recurring events, such as unexpected traffic pattern changes, temporary lane closures, etc., as well as long-term evolution in transportation systems like seasonal effects, permanent road changes, infrastructure development, etc. To achieve system wide optimization, the timings at different signalized intersections will not, in general, have predetermined relationships to one another except possibly for those signals along transportation arteries, where it will be preferable to synchronize the intersections.

[0040] The present invention utilizes an intelligent data gathering and processing system based on information flow from existing cellular phone networks, and uses such obtained cell phone based position data for real time computation of adjusted phase timings at signalized intersections.

[0041] The system of the present invention is capable of constructing and maintaining lists of vehicles moving along road sections at particular periods of time. This is achieved by tracking a predetermined number of in-vehicle cell phones within a given region. The exemplary system maintains a series of such lists associated with the previous elapsed time period and calculates estimates of the numbers of vehicles traveling on each particular road section, their actual traveling times, and the turning times and go-through times for all signalized intersections. Thus, the exemplary system is able to (1) compute real time traffic loads for various roads and road sections, (2) generate detailed lists and descriptions of vehicle turning movements, (3) compute real time turning data for all relevant intersections, and (4) estimate other relevant traffic parameters. The resulting information setup (with numerous relevant parameters estimated on the basis of observations) is then transferred with minimum delay to the automated traffic control system for the purpose of adjusting phase timings at signalized intersections for the next control time period. In other words, based on the traffic flow data obtained for the previous control time period, the system attempts to adjust phase timing at signalized intersections in such a way as to provide more green time for more heavy traffic flows at the expense of less loaded roadways for the next control time period. Roughly speaking, the longer travel time has been registered at a particular turn during the previous control time period, the more green light the intersection is going to get at the next time period.

[0042] This result may be achieved by maximizing a linear function in green light timings the coefficients of which are functions of time delays affected at all road sections during the previous control time period within the given region. Optimization is achieved under certain constraints, such as minimal and maximal values of green light timings, safety constraints expressing minimum number of seconds for inter-green times at each intersection, and other relevant constraints which could be set up individually for any turn and go-through of any signalized intersection, etc. The new values of green light timings obtained from the optimization will be applied to the next control time period during which new measurements of traffic travel times and traffic flows will be made as before, and the whole process will be repeated.

[0043] The invention is best understood from the following detailed description when read in connection with the accompanying drawing. It is emphasized that, according to common practice, the various features of the drawing are not to scale. On the contrary, the dimensions of the various features are arbitrarily expanded or reduced for clarity. Included in the drawing are the following Figures:

[0044] FIG. 1 is a flowchart representation of the traffic control system for an exemplary embodiment of the present invention;

[0045] FIGS. 2A-2B are a detailed flowchart of Step 102 shown in FIG. 1;

[0046] FIG. 3 is a example of measured positions of a cell phone in a vehicle moving along a road section;

[0047] FIG. 4 is an example of outlying vehicle positions in the vicinity of an intersection.;

[0048] FIG. 5 is an exemplary intersection of two two-way roads;

[0049] FIG. 6 is a topologically equivalent detailed map of the intersection shown in FIG. 5; and

[0050] FIG. 7 is an estimation of actual travel times for various portion of the intersection shown in FIG. 6.

[0051] One purpose of the present invention is to optimize the phase timings at signalized intersections in such a way as to relieve the most jammed portions of the network at the expense of its less loaded portions. In an exemplary embodiment of the present invention, this may be achieved by collecting location data from the maximum possible number of vehicles moving in a given region, estimating of traffic loads on all road sections and turns, and then by adjusting phase timings to ease the most congested roadways.

[0052] Naturally, the extent and the precision of the overall data collected from the plurality of cell phones in the given network will largely depend on the total number of current cell phone users as well as on the technology used for measuring and recording the data. It should be noted here that for purposes of the present invention, data collection is based on any cell phone in an “on” position, and as such will be considered part of the reporting system.

[0053] The present invention does not deal with problems related to the precision of the cell phone location methods, but rather presumes existing cell phone location technologies and anticipates their progressive improvement in the future. It is also assumed that increasing competition in the cell phone market will further enhance the already large popularity of cell phone usage by the public.

[0054] In the exemplary system, all relevant cell phone position data will be obtained directly from the cell phone network operator without any involvement of the individual phone user. After receiving all location data, the system proceeds to compute travel times for all road sections and turns, and optimizes the phase timings accordingly.

[0055] FIGS. 1-3 are a representation of the exemplary cell phone gathering system. The following main steps of data exchange flow are described in detail below.

[0056] 1. Overview of Control Scheme and of Computational Method

[0057] 2. Obtaining Cell Phone Records From the Network Operator

[0058] 3. Creating and Storing the Current and Previous Cell Phone Lists

[0059] 4. Creating Preliminary Cell Phone Path Profiles

[0060] 5. Cleaning the Data

[0061] 6. Discrimination Between Phones in Moving Vehicles and Other Phones

[0062] 7. Grouping Cell Phones Into Vehicular Clusters

[0063] 8. Theoretical Travel Times for Turns and Go-throughs

[0064] 9. Actual Travel Times for Road Sections, Turns and Go- throughs

[0065] 10. Maximization of Objective Function F, Computation of Resulting Phase Timings, and Applying Them for The Next Control Period

[0066] 11. Future Embodiments And Additional Applications

[0067] As indicated above, the exemplary system and method uses traffic data obtained during the previous control time period T_sfor adjusting phase timings at signalized intersections at the next control time period T_s+1in such a way as to provide more green light time for more heavy traffic flows at the expense of less loaded roadways. This is achieved by maximizing a linear function F in green light timings G_ij $F=\sum _{i,j}^{}{W}_{ij}{G}_{ij}$

[0068] where, i indexes signalized intersections within the given region, j runs over the green lights at intersection i, and coefficients W_ijmeasure time delays resulting from traffic congestions.

[0069] The new values of green light timings G_ijresulting from the optimization of F will be applied to the control period T_s+1during which new measurements of traffic delays will be made as before, and the whole process will be repeated.

[0070] To compute the values of G_ij, we will perform the maximization of F above under the system of constraints

[0071] G_ij,min≲G_ij≲G_ij,max

[0072] and $G_{i,\min }\le \sum _j{G}_{ij}\le G_{i,\max }$

[0073] where computation of weights W_ijwill be explained below, the constants G_ij,min, G_ij,max, G_i,minand G_i,maxare assumed known, and i and j are as defined above.

[0074] Apart from the listed constraints, the minimization problem may contain other relevant constraints, such as safety constraints expressing minimum number of seconds for inter-green times at each intersection. As their structure is quite similar to the listed above constraints, however, we will not try to enumerate all of them explicitly, and will presume they have been included into the system of constraints above.

[0075] Maximization of F can be performed by standard linear programming techniques.

[0076] Computation of Weights W_ij

[0077] For maximization of F we need to know the weights W_ij. These weights indicate an increase in waiting times resulting from traffic congestion at the corresponding intersections.

[0078] The weights W_ijkare computed where, k is the index number of turn at the intersection i controlled by the green light j. The weights W_ijkare computed by the formula

[0079] W_ijk=t_ijk|T_ijk

[0080] where, t_ijkis an average actual travel time for the turn k averaged over a number of vehicles that made that turn during the previous time period, and T_ijkis the theoretical (regular) travel time for that turn.

[0081] The travel times t_ijkwill be called actual travel times, and the travel times T_ijkthe theoretical travel times. Now, the weights W_ijare computed by the formula $W_{ij}=\sum _k{W}_{ijk}$

[0082] and substituting them into the function F, we can perform optimization as described above and compute the corresponding green light timings G_ij.

[0083] It is assumed that the cell phone network operator is capable of providing all the necessary information on the plurality of active cell phone units in the network. The process of collecting and transmitting cell phone position data is well known to those skilled in the art and described in the literature.

[0084] For the purposes of the present invention it is contemplated that the data are received in the form of periodic data packets in real time, such as every 1 to 3 minutes, for example. The exemplary packet file consists of a list of records, each for a single cell phone, containing the phone's unique ID number, the recorded time of signal reception t, and its location P (x, y):

[0085] record(CP)=(ID,t,x,y)

[0086] For the purposes of protecting privacy of individual cell phone users, an automatic coding system set up by the network operator will assign to each cell phone number a unique ID reference number. In the exemplary embodiment of the present invention, only the reference ID will be used to identify each cell phone record.

[0087] At each time period T_i, the Traffic Control System compiles a current phone list consisting of cell phone records (in the sense defined above) of all available active cell phones in a system database ordered by their ID reference numbers. At the next control period T_i+1, a new current phone list is compiled and recorded similarly, with the first current phone list becoming the previous phone list number 1. At the following control period, a new current phone list is compiled, the current phone list becomes the previous phone list number 1, and the previous phone list number 1 becomes the previous phone list number 2, etc. For the purposes of analysis, it may be necessary to store at any given moment a predetermined number of those lists, such as, 4 or 5 for example.

[0088] To track moving vehicles, it will be convenient to create a temporary cell phone path profile for each active cell phone in a given area and to place individual cell phone positions onto the digital map. The exemplary map database contains a list of all road sections, each with a number of fixed attributes such as road name, the names of two adjacent intersection nodes, permissible speed, number of lanes, turns to and from the nodes, sensor devices if available, automatic traffic control signals, and all other pertinent data. For each individual cell phone, we define its original path profile as a series of its database records, i.e. initial location measurements. The path profile for a cell phone can only be constructed if the re-determined number of its latest recorded positions is available.

[0089] FIG. 3 illustrates a cell phone path profile along road section 300 based on positions 302, 304, 306, 308, 310 of a cell phone (not shown). Note that due to measurement errors those recorded cell phone positions will generally not lay on the road the vehicle traveled by, but rather in the vicinity of it. To correct for this, the Positioning Algorithm disclosed in co-pending patent application no. 09/xxxxxx, filed Jul. 10, 2001 and assigned to the same assignee as the present invention, may be used for finding most likely positions of cell phones on road sections. This co-pending application is entitled “Traffic Information Gathering via Cellular Phone Networks for Intelligent Transportation Systems” and is incorporated herein by reference. In brief, the Positioning Algorithm works as follows. Given a point P′ (recorded cell phone position), the Positioning Algorithm searches for a point P nearest to point P′ located on one of the closest road sections. Such a point is deemed to be the most probable position of the cell phone.

[0090] After all recorded cell phone positions have been adjusted and associated with individual road sections, the adjusted phone list is created with all cell phones placed on road sections.

[0091] For some computations required by the traffic model, continuous paths will be used as travel routes rather than lists of cell phone positions. Construction of such continuous path profiles can be achieved by simple interpolation and extrapolation techniques, in particular by constructing linear regression curves. It is assumed that valid interpolations and extrapolations can be performed within the given road section.

[0092] Even with less than predetermined number of recorded positions, linear regression or interpolation may still be performed although precision may suffer. On the other hand, one should be warned again attempting extrapolation over section boundaries. It appears that while the assumption of validity of interpolation and extrapolation within a common road section is tenable, extrapolating across section boundaries is not recommended. This is due to abrupt changes in speed that often occur while switching between sections, long waiting times near intersections, possible congestion at section ends, sudden stops that drivers make before entering highways, various turning point delays, etc.

[0093] A continuous cell phone path profile constructed by means of the Positioning Algorithm and interpolations and extrapolations may not always be satisfactory. As a matter of fact, due to large measurement errors and the closeness of road sections to one another, especially in dense urban areas, it may occur that outliers, i. e. untenable cell phone positions, have been included into the path profile.

[0094] FIG. 4 is an example of outlying vehicle positions in the vicinity of intersection 414. In the series of vehicle positions 402, 404, 406, 408, 410 shown in FIG. 4, positions 408, 410 are outliers. Line 412 illustrates the path taken by the subject vehicle.

[0095] For the process of construction of continuous cell phone path profiles, outlying positions (408, 410 shown in FIG. 4) are misleading records that may severely impair or invalidate the continuous cell phone path, which has been influenced by it. Therefore, it is requisite to use statistical procedures for filtering or cleaning the data prior to cell phone path construction, or after attempting path construction. In any case, before proceeding to the following computations, the observed cell phone positions should be checked for validity and consistency. Furthermore, if some observable cell phone positions are missing due to technical errors or other reasons, statistical procedures for treating missing observations should be applied. Examples of such procedures can be found in the co-pending patent application referred to above (Traffic Information Gathering via Cellular Phone Networks for Intelligent Transportation Systems).

[0096] Once the list of all cell phone profiles has been set up, it should be analyzed as to which phones are located in traveling vehicles and which are not. In fact, phones located in traveling vehicles usually possess some attributes not found with other phones. As a result, some of these attributes can be used for separating phones located in moving vehicles, on the one hand, and all other phones on the other. Among those other phones may be stationary phones, such as phones inside houses, phones left in parked cars, slowly moving phones such as phones held by pedestrians, fast moving phones located in trains, held by bicycle and motorcycle riders which may be moving in the open without regard to any roads, and probably many other cases difficult to envision and enumerate. Roughly speaking, phones moving along discernible roads with speeds that, at least part of the time, are significantly greater than speeds of pedestrians should be classified as phones in moving vehicles. A formal and detailed discriminating procedure for performing this task may be found in aforementioned co-pending patent application (Traffic Information Gathering via Cellular Phone Networks for Intelligent Transportation Systems).

[0097] After the phones travelling in moving vehicles have been identified with a minimum number of errors, it is necessary to identify and eliminate the possibility that two or more cell phones traveling in a single vehicle will mistakenly be recorded as two or more moving vehicles. If this is allowed to happen, it will lead to misrepresenting the actual number of moving vehicles or the “vehicular load” on a particular road section and to distortion of general picture representing the traffic situation at the given moment.

[0098] In our co-pending patent application (Traffic Information Gathering via Cellular Phone Networks for Intelligent Transportation Systems), procedures for 1) grouping moving phones into vehicular clusters, 2) positioning thus constructed vehicular clusters onto roads, and 3) constructing continuous path profiles for them are described. The net result is a list of vehicular clusters moving along particular roads in a given time period.

[0099] As indicated in the first section Overview of Control Scheme and of Computational Method, the weights W_ijkwere computed by the formula

[0100] W_ijk=t_ijk|T_ijk

[0101] where, t_ijkare actual travel times, and T_ijkare theoretical travel times.

[0102] Actual travel times for turns and go-throughs include waiting due to congestion conditions, while theoretical travel times do not.

[0103] First, theoretical travel times T_ijkare computed, and in the next section a method for estimating actual travel times t_ijkis described.

[0104] Let t_rdenote the time during which the red light is on, and similarly t_gthe time for a green light. Denote by E(t_wait|red) the mathematical expectation of the waiting time if the driver arrived to the intersection when the red light was on, and similarly E(t_wait|green) for green. Also denote by Pr(red) the probability that the red light is on when the driver arrives at the intersection, and similarly Pr(green) the probability of the green light. Now, the expectation of the waiting time can be computed by the total probability formula:

[0105] Et_wait=E(t_wait|red)Pr(red)+E(t_wait|green)Pr(green)

[0106] Since E(t_wait|green)=0, this simplifies to

[0107] Et_wait=E(t_wait|red)Pr(red)

[0108] It is easily seen that E(t_wait|red)=t_r/2, and Pr(red)=t_r/(t_g+t_r),

[0109] resulting in:

[0110] Et_wait=t²_r/(2(t_g+t_r))

[0111] This formula gives the mean waiting time of the driver arriving at an intersection under ideal traffic conditions with no congestion and no delays whatsoever.

[0112] In this section a method for estimating actual travel times t_ijkfor turns and go-throughs is described. First, however, some definitions are necessary.

[0113] For computing actual travel times for traveling across a road network, it is convenient to represent each two-way road section as a pair of one-way sections. Also, as each road intersection contains a number of changeovers (turns and go-throughs) from one section to another, it will be useful to represent each such changeover from an incoming section to an outgoing section by a new abstract transition segment possessing its own travel time.

[0114] FIG. 5 shows a rather simple example of an intersection of two two-sided roads. The intersection itself is marked by I_0,and the neighboring intersections are denoted I₁, I₂, I₃and I_4.

[0115] Section S₁₀goes from intersection I₁to intersection I_0,section S₀₁goes from intersection I₀to intersection I₁, section S₀₂goes from intersection I₀to intersection I₂, etc., so that we have 8 separate one-sided road sections.

[0116] All the turns and pass-throughs at I₀are permissible except for two left turns: the turn from S₁₀to S₀₂(502) and the turn from S₃₀to S₀₄(504) are not allowed.

[0117] A topologically equivalent detailed map of the intersection area in FIG. 5 is shown in FIG. 6. In FIG. 6, all two-sided sections are shown as pairs (I1, I2, I3, I4) of one-sided sections with travel directions indicated by arrows (S₀₁, S₁₀, S₀₂, S₂₀, S₀₃, S₃₀, S₀₄, S₄₀). Permissible turns (602, 604, 606, 608, 610, 612) and go-throughs (614, 616, 618, 620) are also shown by arrows so that, e.g., the incoming section S₁₀is followed by two arrows connecting it to the outgoing section S₀₄(right turn) and to the outgoing section S₀₃(go-through). Similarly, the incoming section S₄₀is followed by three arrows connecting it to the outgoing section S₀₁(left turn), to the outgoing section S₀₂(go-through) and to the outgoing section S₀₃(right turn). In total, there are 10 additional transition segments, i. e. permissible changeovers, out of 12 theoretically possible transition segments.

[0118] Geometrical sizes of the additional transition segments connecting road sections are negligible whereas times spent on them by the drivers are not.

[0119] The actual travel time associated with the transition segment connecting section S₁₀to section S_04,for example, will include the waiting time by red light, time spent in a vehicle queue, times spent on slow-downs and speeding up, actual turning time, etc. Including all those times into a new transition segment will allow to “free” travel times of road sections from “wait and turn” times and thereafter to estimate both types of travel times separately and more accurately.

[0120] A method that may be used for estimating travel times for various transition segments is now presented. Consider the right turn (608 in FIG. 6) from the incoming section S₄₀to the outgoing section S₀₃shown separately in FIG. 7 and denoted by R₄₃. Let the length of S₄₀be l₁, and the length of S₀₃be t₂. Also, let the actual travel time for S₄₀be t₁, the actual travel time for S₀₃be t₂, and the actual travel time for the turn R₄₃be t₀. The values l₁and l₂are known, whereas the times t₁, t₂and t₀are unknown and should be estimated via location signals from cell phones in traveling vehicles.

[0121] Now, assume that a traveling vehicle was observed at some point P₁on section S₄₀at time moment z₁, and next at a point P₂on section S₀₃at time moment z₂. Thereby, the coordinates of both points P₁and P₂are known.

[0122] Let the distance from P₁up to the end of section S₄₀be p₁*I₁, and the distance from the beginning of section S₀₃to the point P₂be q₁*I_{2 .}Assuming that the vehicle has spent time p₁*t₁for traveling the distance p₁*I₁on section S_40,and time q₁* t₂for traveling the distance q₁*I₂on section S_03,we can write an equation

[0123] p₁*t₁+t₀+q₁*t₂=T₁

[0124] where T₁=z₂−z₁is known.

[0125] If we observed signals from n (greater than 3) vehicles that traveled by section S_40,and then turned to the right to section S₀₃, we will be able to write n equations similar to the equation above:

[0126] p₁*t₁+t₀+q₁*t₂=T₁

[0127] p₂*t₁+t₀+q₂*t₂=T₂

[0128] . . .

[0129] p_n*t₁+t₀+q_n*t₂=T_n

[0130] This system is a linear regression model whose solutions {circumflex over (t)}₁, {circumflex over (t)}₀, {circumflex over (t)}₂will give the sought for estimates for the corresponding travel times.

[0131] Similar systems associated with other turns and go-throughs related to the present intersection and also to all other intersections within a given region produce estimates for all travel times of interest.

[0132] After the actual travel times t_ijkfor all turns and go-throughs have been estimated during the time period T_s, and their theoretical counterparts T_ijkcomputed, we can compute the weights W_ijkand W_ijand then use a linear programming method for performing maximization of the objective function F under the restrictions laid out in the first section. Optimization produces the corresponding values of green light timings G_ijthat bring F to its maximum. Those values will be used as control variables during the next control period T_i+1, new data will be collected, and the whole computation cycle repeated. The process is shown schematically in FIG. 1.

[0133] FIG. 1 is a flowchart of an exemplary embodiment of the inventive traffic control system and method. At Step 100 preliminary computations are performed. At Step 102, data is collected from vehicles during control time period T_i. At Step 104, theoretical travel times for turns are computed. At Step 106, actual travel times for turns are computed. At Step 108, weights W_ijkfor all values of indexes i, j and k are updated. At Step 110, weights W_ijfor all values of indexes i and j are computed. At Step 112, maximization of objective function F and computation of all corresponding values of is performed. At Step 114, the green light timings G_ijobtained at Step 112 are applied to the next control period T_i+1and the process is reentered at Step 102.

[0134] FIGS. 2A and 2B provide a detailed flowchart of Step 102 shown in FIG. 1. At Step 1021, location data is received and collected by the cell phone operator. At Step 1022, the file containing the location data is transferred to the traffic control system. At Step 1023, a Positioning Algorithm for putting cell phones on road sections is applied to the location data. At Step 1024, the resulting data is subjected to a filtering or cleaning process. At Step 1025, cell phone lists are created. At Step 1026, a special algorithm is applied to each cell phone record to determine if a particular cell phone is in a traveling vehicle. If the cell phone is determined not to be located within a traveling vehicle at Step 1026 the record is rejected at Step 1027 and the process ends. On the other hand, if the cell phone is determined to be located within a traveling vehicle at Step 1026 the record is stored in a memory system at Step 1028. At Step 1029, the vehicular clusters representing moving vehicles are created. At Step 1030, the vehicles are put onto road sections by the Positioning Algorithm. At Step 1031, the vehicle travel paths along the road sections are constructed by interpolation methods. At Step 1032, the data relating to the vehicle positions, travel routes, etc., needed for adjusting phase timing and other traffic control computations are prepared and stored in the database.

[0135] As described above with respect to the exemplary embodiment, the present invention provides a system and method for calculating a large number of traffic characteristics and parameters not readily available under other systems. In particular, it allows computation or estimation of the following parameters and quantities: actual travel times of all road sections within a given geographical region; actual travel times of all road turns and go-throughs at all signalized intersections within a given geographical region; short-term predictions of those quantities; and current vehicle loads on all road sections within a given geographical region.

[0136] Based on the above quantities, many important statistical historical data items may be computed and stored for future use, including the use by third parties. Among such data are: vehicle loads at particular roads categorized by days, hours, etc., vehicle densities at particular roads categorized by days, hours, etc., vehicle densities in the vicinities of signalized intersections, average speeds along important arteries categorized by days, hours, etc.

[0137] Also, numerous additional types of information may be computed based on the above. These real time or historical data can be readily transmitted to other client application programs such as guided navigation systems, traffic related and congestion studies, emergency services 911, etc.

[0138] Although the invention has been described with reference to exemplary embodiments, it is not limited thereto. Rather, the appended claims should be construed to include other variants and embodiments of the invention which may be made by those skilled in the art without departing from the true spirit and scope of the present invention.