QRS II had always had a form of feedback to trip distribution (more correctly to trip generation, although the trip generation step was insensitive to network travel times).
In 1988 or so when I was testing a new installation of a “modified” Evans’ algorithm I had put into QRS II, which was quite similar to Franke-Wolfe decomposition, I noticed a peculiar pattern of averaging weights. The first weight always seemed to be close to 0.5, the second weight always seemed to be close to 0.33, etc. This same pattern emerged no matter which network I tested. The modified Evans’ algorithm wanted a 1/k sequence or something not so different.
Conjecture #1. Evans’ algorithm doesn’t really need the demand term in the line-search step.
The modified Evans’ algorithm worked, sort of. (I published a short research note on it, ”Tests of an Ad Hoc Algorithm of Elastic- Demand Equilibrium Traffic Assignment”, in an attempt to get someone to tell me whether I was onto something important.) The modified Evans’ algorithm found exactly the same answer as the unmodified Evans algorithm, if it found any answer at all. However, in rare occasions it locked up and failed to give any results. There was a very nice follow-up paper by Haung and Lam proving that the algorithm was fantastic when it was working, but failed dramatically when it wasn’t working. We were close to a solution to the feedback problem, but not yet close enough.
So not so long afterward I am having a phone conversation with Roger Tobin about traffic assignment and he said “Patrice thinks that one over kay might solve the elastic demand assignment problem”. Of course, Roger was referring to Patrice Marcotte, the brilliant network theorist who had quite an influence on my thinking. OK, 1/k was being generally discussed, but were there any papers about it in the published literature? I found some mention in the literature about how 1/k assignment was similar to incremental traffic assignment, but nothing about feedback. Eventually, by flipping through old, dusty journals, I stumbled across an article by Powell and Sheffi proving that MSA (method of successive averages, a generalization of the 1/k concept) gave correct equilibrium solutions for the static, inelastic demand problem.
Powell and Sheffi’s article was minimally cited at the time, probably because of a mind-bogglingly incorrect conclusion. After a really great paper, otherwise, those guys concluded that MSA was at best a poor substitute for Frank-Wolfe decomposition, since it was always slower computationally.
The modified Evans’ algorithm was locking up because the line-search failed (rarely, but enough to be of concern). What if we eliminated the line-search altogether?
Conjecture #2. Evans’ algorithm’s line-search step can be replaced entirely by a 1/k weighting scheme.
This was going to be difficult to prove, and I am not nearly the network theorist of Tobin, Marcotte, Lam, et. al, so I decided to demonstrate the truth of the 1/k idea by much testing on toy and real-world networks. These first tests were summarized in the article “Convergence Properties of Some Iterative Traffic Assignment Algorithms”. In brief, the MSA modification of Evans’ worked perfectly.
“You might ask, “What’s the problem with Evans’ line search?” First, the demand term adds a lot of computation. Second, the line search would not be easily extensible to newer demand models that were brewing. There is yet another looming reason that I didn’t know about at the time.
Here is the whole algorithm in a nutshell.
Step 1: Compute OD table; AON assignment; compute new travel times.
Step 2. Compute OD table with new travel times; AON assignment; take average of all AON assignments; compute new travel times.
Step 3. Check for convergence; if good, stop; if not good, do Step 2 again.
As an accounting task, it is necessary to average all the OD tables, but the average table does not ever get assigned to the network. We need the average table later so it agrees with the averaged volumes, since we never run the algorithm close enough to complete convergence.
Even though MSA with feedback has been part of QRS II for more than 2 decades, there was no rush by other software vendors or MPOs to put it in their models. First, the necessity still needed to be demonstrated. And second, it was very difficult to get modular software packages to do it correctly. That is still the case. Eventually, the double-loop feedback scheme was hatched.
The double-loop feedback scheme overcomes the issue of modularity at the cost of a lot of computation. The double-loop feedback scheme is sometimes referred to as MSA, but it is not MSA. It will do the same thing for limited networks, if you are patient enough. The outer loop deals with demand and the inner loop deals with assignment. So let’s say you need 10 iterations to get demand to settle down and you need 20 iterations to get good convergence for your Frank-Wolfe decomposition. This means you will need upwards of 200 AON assignments. However, MSA solves the exact same problem in maybe 25 AON assignments, allowing 5 more iterations to account for the slowness of MSA relative to Frank-Wolfe decomposition. MSA beats the double loop by a factor of 8.
Sometime in 1990 Dane Ismart, then of FHWA, asked me to look into how the 1985 Highway Capacity Manual should affect the BPR curve. I could get the BPR curve to fit freeways and multilane arterials, but I had no success getting the BPR curve or, indeed any other VDF, to fit stop signs or signals. While working on this project I programmed into QRS II the HCM’s operational analysis procedures for signals and two-way stops. Frank-Wolfe decomposition simply would not converge with signals and stop signs. However, switching to MSA gave me convergence. Thus…
Conjecture #3. MSA solves the traffic assignment problem with signals and signs.
I knew from Marcotte, Nagurney and others that I was venturing into the realm of variational inequalities, which took us far away from familiar optimization theory, but nobody had yet taken on anything as complex as what was found in the HCM. So without much help available from theorists, I again turned to repeated testing of toy and real networks. The results of these tests were published in three papers, the first of which appeared in the Transportation Research Record as “Implementing Travel Forecasting with Traffic Operational Strategies”.
You may have noticed that many of my papers were published in the Transportation Research Record rather than in some of the more academic journals known for their network theory. I was deliberately avoiding network theorists as referees, who I felt would not be receptive to such radical concepts without a lot of math to back them up.
So MSA is a remarkably strong and resilient algorithm. It is grounded in the theory of numerical analysis rather than in the highly restrictive optimization theory of Beckmann. Where MSA has the most trouble is with the issue of multiple equilibrium solutions; however, the real world has multiple equilibrium solutions, so this is not an issue with MSA itself but an issue of the way we have collectively formulated the urban traffic assignment problem.
Subsequent years and many tests have shown that MSA can handle dynamic traffic assignments and multiclass traffic assignments … and rather surprisingly, everything all at once.
Alan Horowitz, Whitefish Bay WI, September 12, 2015
*“My Life with Marilyn” is more interesting. I recommend it.