Algorithm for Equilibrium Transit Assignment Problem

Abstract

Transit assignment is an important problem in the literature of transportation. Almost all competitive algorithms in this area are strategy based. For uncongested transit networks, the problem may be formulated into an optimization problem for which good solution algorithms exist. A variational inequality formulation of the problem with several solution methods is also presented in the literature for congested networks. This paper is devoted to solving a transit assignment problem based on complementarity formulation using path flows. The solution algorithm exploits the three concepts of decomposition, path generation, and linearization. The procedure has been applied on a large-scale real-case transit network under fixed travel times as well as flow-dependent dwell times. Computational experiments show rapid convergence of the algorithm. Moreover, for the limited experiments performed, the computational time for the flow-dependent problem is only about twice that of the case for the fixed travel times, without an appreciable excess memory requirement.

Get full access to this article

View all access options for this article.

References

Spiess

On Optimal Route Choice Strategies in Transit Networks. Publication 286. Centre de Recherche sur Transports, University of Montreal, Quebec, Canada, 1983.

Spiess

and Florian

Optimal Strategies: A New Assignment Model for Transit Networks. Transportation Research Part B, Vol. 23, 1989, pp. 83–102.

Nguyen

and Pallottino

Equilibrium Traffic Assignment for Large Scale Transit Networks. European Journal of Operational Research, Vol. 37, No. 2 1988, pp. 176–186.

J. H.

Florian

and Marcotte

Transit Equilibrium Assignment: A Model and Solution Algorithms. Transportation Science, Vol. 28, No. 3 1994, pp. 193–203.

Bouzaïene-Ayari

Gendreau

and Nguyen

An Equilibrium Fixed-Point Model for Passenger Assignment in Congested Transit Networks. Publication CRT-95-57. Centre de Recherche sur Transports, University of Montreal, Quebec, Canada, 1995.

Cominetti

and Correa

Common-Line and Passenger Assignment in Congested Transit Networks. Transportation Science, Vol. 35, No. 3 2001, pp. 250–267.

Babazadeh

Equilibrium Transit Assignment Problem in Congested Networks: Formulation and Solution Algorithm. Ph.D. dissertation. Sharif University of Technology, Tehran, Iran, 2005.

Wardrop

J. G.

Some Theoretical Aspects of Road Traffic Research. Proceedings of the Institute of Civil Engineers, Vol. 1, No. 2 1952, pp. 325–378.

EMME/2 User's Manual. Software Release 9. INRO, Montreal, Quebec, Canada, 1999.

10.

Kojima

Computational Methods for the Nonlinear Complementarity Problem. Department of Administration Engineering and Management Science, Keia University, Yokohama, Japan, 1973.

11.

Lüti

H. J.

A Simplicial Approximation of a Solution for the Nonlinear Complementarity Problem. Mathematical Programming, Vol. 9, 1975, pp. 278–293.

12.

Aashtiani

H. Z.

and Magnanti

T. L.

A Linearization and Decomposition Algorithm for Computing Urban Traffic Equilibria. Proceedings of IEEE Large Scale System Symposium, 1982, pp. 8–18.

13.

Cottle

R. W.

and Dantzig

G. B.

Complementarity Pivot Theory of Mathematical Programming. Linear Algebra and Its Applications, Vol. 1, 1968, pp. 103–125.

14.

Eaves

B. C.

The Linear Complementarity Problem. Management Science, Vol. 17, 1971, pp. 612–634.

15.

Lemke

C. E.

Bimatrix Equilibrium Points and Mathematical Programming. Management Science, Vol. 11, 1965, pp. 681–689.

16.

Golden

Shortest-Path Algorithms: A Comparison. Operations Research, Vol. 24, 1976, pp. 1164–1168.

17.

Aashtiani

H. Z.

and Iravani

Application of Dwell Time Functions in Transit Assignment Model. In Transportation Research Record: Journal of the Transportation Research Board, No. 1817, Transportation Research Board of the National Academies, Washington, D.C., 2002, pp. 88–92.