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.

Este trabajo presenta una nueva formulación y algoritmo de asignación de equilibrio basado en rutas para redes de tránsito congestionadas. Es una extensión de De Cea y Fernández (1993), que implementa efectos de congestión en el proceso de abordaje e introdujo el concepto de frecuencias efectivas. Ese trabajo fundamental proporciona un algoritmo de solución para el problema de equilibrio que aprovecha dos simplificaciones principales. Primero, limita el número de tramos de ruta bajo consideración (es decir, considera un conjunto reducido de servicios atractivos para que los usuarios elijan en cada tramo de su viaje). En segundo lugar, supone que la distribución del flujo entre servicios atractivos se puede estimar utilizando las frecuencias nominales de los servicios en lugar de las efectivas.

En este artículo, desarrollamos un modelo de equilibrio y un algoritmo de solución que amplían la formulación original sin depender de los dos supuestos mencionados anteriormente, sin dejar de abordar tres desafíos clave. Primero, las funciones de costo de usuario son de naturaleza asimétrica y, por lo tanto, no se puede formular un problema de optimización equivalente. En segundo lugar, las funciones de costo en este enfoque solo se pueden expresar implícitamente, lo que hace que la implementación de un algoritmo de diagonalización sea un problema desafiante. Por último, ocuparse de todo el conjunto de tramos de ruta implica trabajar con todos los conjuntos factibles de servicios atractivos, lo que puede hacer que la red auxiliar subyacente crezca exponencialmente en tamaño.

Resolvemos el problema de equilibrio utilizando un algoritmo de diagonalización, obteniendo funciones diagonalizadas aproximadas al resolver un problema de punto fijo. Nuestra metodología también incluye un algoritmo eficiente para generar conjuntos de servicios candidatos potenciales en la red. Probamos nuestro algoritmo en tres redes de tamaño creciente, donde mostramos que el enfoque converge efectivamente a una solución de equilibrio del usuario en cuestión de segundos. También mostramos que el algoritmo original de referencia converge a soluciones que violan las condiciones de equilibrio del usuario, mostrando rutas no utilizadas con costos inferiores al equilibrio, lo que confirma que nuestro algoritmo es el primero en encontrar una solución exacta al problema de equilibrio del usuario del transporte público basado en rutas.