Route based equilibrium assignment in congested transit networks

Abstract

This work introduces a new route-based equilibrium assignment formulation and algorithm for congested transit networks. It is an extension of De Cea and Fernández (1993), which implements congestion effects in the boarding process and introduced the concept of effective frequencies. That seminal work provides a solution algorithm for the equilibrium problem that takes advantage of two main simplifications. First, it limits the number of route sections under consideration (i.e., it considers a reduced set of attractive services for users to choose from on each leg of their trip). Second, it assumes that the flow split between attractive services can be estimated using the nominal frequencies of the services instead of the effective ones.In this paper, we develop an equilibrium model and solution algorithm that extend the original formulation without relying on the two assumptions mentioned above, while still addressing three key challenges. First, user cost functions are asymmetric in nature, and therefore, an equivalent optimization problem cannot be formulated. Second, cost functions on this approach can only be expressed implicitly, which makes the implementation of a diagonalization algorithm a challenging problem. Lastly, dealing with the whole set of route sections implies working with all feasible sets of attractive services, which can make the underlying auxiliary network grow exponentially in size.We solve the equilibrium problem by using a diagonalization algorithm, obtaining approximate diagonalized functions by solving a fixed-point problem. Our methodology also includes an efficient algorithm to generate potential candidate sets of services in the network. We test our algorithm on three networks of increasing size, where we show that the approach effectively converges to a user equilibrium solution in a matter of seconds. We also show that the benchmark original algorithm converges to solutions that violate user equilibrium conditions, exhibiting unutilized routes with lower than equilibrium costs, confirming that our algorithm is the first one to find an exact solution to the route-based public transport user equilibrium problem.