Does LUCE outperform OBA? A Comparison Study of Two Bush-based Algorithms for the Traffic Assignment Problem

摘要

This paper compares two bush-based traffic assignment algorithms, the origin-based algorithm (OBA)and the local user cost equilibrium algorithm (LUCE). The two algorithms are closely related with one majordifference: they solve the decomposed elementary node-based subproblem using different methods. Specifically,LUCE employs a greedy algorithm that is able to solve the subproblem exactly, whereas OBA uses aone-step quasi-Newton method known as gradient projection to solve the subproblem approximately. Therefore,LUCE seems to hold promises to improve OBA because its subproblem solver is presumably faster andmore precise. We implemented these two algorithms in the same programming platform, where the codes ofthem are shared as many as possible. Numerical experiments reported in this paper, however, indicate thatLUCE not only provide no obvious computational advantages over OBA, it often fails to converge beyondcertain point. The focus of this paper is to find an answer to this counter-intuitive phenomenon. Our analysissuggests that the greedy method used by LUCE require highly accurate estimation of second-order derivatives.When second-order derivatives are subject to large errors, the greedy method can provide consistentlysub-optimal descent direction, which seems to be unable to fix.Keywords: Bush-based algorithm, traffic assignment problem, greedy method, gradient projection method,local user cost equilibrium.