If you are reading this article you probably know something about equilibrium traffic assignment and how it is done in at least one travel forecasting package. Traditional methods of equilibrium traffic assignment, say Frank-Wolfe decomposition and MSA (method of successive averages) found in wide use around the world, converge to an equilibrium solution rather slowly. (Researchers have proposed much faster algorithms to solve very narrowly defined traffic assignment problems, but that is another story.) Just let it be said that many a travel modeler has spent much of his or her life waiting for forecasts to converge. Once upon a time, there were recommendations to terminate equilibrium traffic assignment after just 5 iterations. Convergence tests that I did soon after the initial development of QRS II (and verified by other researchers since) revealed that convergence rates (as measured by RMS differences between assigned volumes at any iteration and the assigned volumes at a huge number of iterations) is roughly inversely proportional to the number of iterations. For example, if you want to decrease your convergence error by 50%, then plan on doubling the number of iterations.
Critical to this discussion is the means of measuring convergence error. I have chosen, like many other researchers, to measure convergence using RMS deviations in link volumes. After all, the most salient and reliable outputs of travel models are volume estimates and, most of our validation statistics relate to link volumes. As a drawback, it not really possible to measure RMS differences on the fly. There is, of course, other ways of measuring convergence, such as “relative gap”. Relative gap uses Wardrop’s first principle directly – at equilibrium no driver can improve his or her travel time by changing paths. Operationally, this means that at equilibrium computed path travel times must be the same as shortest path travel times. And therefore, prior to equilibrium, assigned path travel times are somewhat longer than shortest path travel times. The total difference, across the whole network, expressed as a percentage, is the relative gap. (See: http://ops.fhwa.dot.gov/publications/fhwahop13015/sec2.htm for a precise definition.) Shortest path travel times change with the equilibrium iteration, but not much, so relative gap doesn’t have quite the concern of a moving target as does RMS differences.
So why have I been avoiding relative gap all these years? Well, I haven’t been totally ignoring it, since I have used it in research from time to time, but I admit that I have not implemented it within QRS II, frankly because it is deceiving. First, it is a complicated, nonintuitive concept that most modelers have not bothered to learn. Second, it is a measure of the rate of convergence of travel times (and speeds) not of volumes. Third, it totals up errors, which tends to wash out important differences. And fourth, it implies a much, much faster rate of convergence than is actually going on.
Fairly recently, I added to the History report in QRS II a new statistic – the RMS difference between successive iterations. This statistic is not a true convergence error, but my experience shows that it tracks convergence error fairly well. MSA (the only equilibrium assignment option now in QRS II) has an oscillatory characteristic. Volumes that are a little high (relative to convergence) at one iteration are often a little low at the next iteration and vice versa. So as a rough rule of thumb, you can guess the convergence error by dividing the iteration-to-iteration RMS difference by 2, once things get going.
I still like the idea of doing convergence tests, then picking a number of iterations for all subsequent runs. However, QRS II 9 contains a new option to terminate equilibrium iterations when the RMS difference between successive iterations falls below a specified number, such as 10 vph.
Alan Horowitz, January 2, 2015