The RADIUS models were originated by John Shaw, once of WisDOT and now working for the TOPS Lab at the University of Wisconsin—Madison. He envisioned using QRS II as a dynamic traffic assignment engine for a group of models for analyzing work zone traffic diversions. Part of the concept was synthetic OD table estimation from ground counts, since work zone analysis is short-term by nature, and tightly fitting existing traffic is mandatory. WisDOT gave the University of Wisconsin—Milwaukee a contract to build those models.
Each RADIUS 94 model was huge, following I-94 from Northern IL to well past Madison WI, with a branch along I-43 extending north of the Milwaukee urban area. The image below is contained within a square that is approximately 100 miles on a side.
Each RADIUS 94 models has roughly 22,000 links, 2300 TAZs and 6 time intervals. Each time interval is one-hour in duration.
The largest OD table estimation I had tried previously was for a 1000 TAZ static model, and it took a lot of computer time.
Fitting 2276 zones and 6 time intervals to data from 6600 count stations was certainly a challenge. I wanted to use the least squares (LS) whole table method, but version 8 of QRS II would have required a couple years of calculation to rigorously estimate the 31 million cells in the OD table, even with parallel processing. I needed 4 of these tables, and I am pretty sure that WisDOT did not want to wait 8 years for their models.
I needed to make three rather important changes to QRS II in order to accomplish this AND I needed to combine multiple estimation techniques. These changes will be reflected in version 9. At the end of the day I was able to fit traffic counts at those 6600 stations to within 12% RMSE, which is close enough given the quality of the traffic counts. The last and biggest estimation for each model took 2-3 weeks on my 6-core/12-thread computer. Not quick, but certainly practical.
The first change to QRS II involved how the Paij array was stored in memory. Without going into a lot of theory, this array essentially stores a separate OD table for each count station. While QRS II is running, this array is highly compressed and was originally “hashed” into smallish packets that could be referenced easily. However, each time QRS II needed to look up a value, QRS II needed to search the required packet for the particular Paij value. I changed this memory arrangement to sort the Paij table by i*N+j, which means that QRS II could find the next needed array value very quickly as it moves from OD cell to OD cell. This one change sped up the whole table method by maybe a factor of 5. However, it only sped up the Fratar biproportional method slightly.
The second change related to the realization that there are a huge number of Paij values that are trivially small and are not really affecting the estimation. So I added a filter that can be user-adjusted to eliminate these very small values. For RADIUS, I set the filter to retain 75% of all the traffic in the Paij array, which reduced the Paij array size dramatically. QRS II rescales the remaining unfiltered Paij values to make sure we are matching the original OD trip totals.
The third change was a subsequent realization that there are certain OD pairs that play almost no role in the estimation and are pretty much defaulting to the seed table, anyway. So QRS II identifies these OD pairs and ignores them during the estimation.
Altogether these changes sped of the RADIUS estimations by maybe a factor of 100.
However, I determined through smaller trial estimations that filtering the Paij table below 90% of all traffic causes noticeable changes to the OD table. So for RADIUS (at 75%) I needed to be very careful about the seed OD table, since many of the OD flows will be defaulting to the seed. So I started with a gravity OD table as a seed matrix for a LS whole table static OD table estimation while combining the 4 hours of interest. Then I did a dynamic LS single factor estimation to make the static OD table dynamic. Finally, I ran the LS whole table dynamic method using the single-factored OD table as a seed.
I wanted to use the Fratar biproportional method instead of the single factor method to get the final seed OD table, but the execution times were much too long.
The very last dynamic OD table estimations only had about 2 million OD pairs affected (out of a possible 5 million in any given interval) and the Paij table was a tiny fraction of the size it would have been without filtering.
One additional thing I did for RADIUS was to weight freeway mainline ATR counts at 50 times the weight for coverage counts in order to make sure that the OD table nailed these locations as precisely as possible. For a freeway work zone model, we could not afford to have any appreciable error on the freeway mainlines.
Alan Horowitz, March 7, 2015