2026-07-25T06:17:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21205 2024-10-07T04:59:11Z ddc:004 open_access

Computing User Equilibria for Schedule-Based Transit Networks with Hard Vehicle Capacities Harks, Tobias Jäger, Sven Markl, Michael Schiewe, Philine traffic assignment side-constrained equilibrium public transportation Modelling passenger assignments in public transport networks is a fundamental task for city planners, especially when deliberating network infrastructure decisions. A key aspect of a realistic model for passenger assignments is to integrate selfish routing behaviour of passengers on the one hand, and the limited vehicle capacities on the other hand. We formulate a side-constrained user equilibrium model in a schedule-based time-expanded transit network, where passengers are modelled via a continuum of non-atomic agents that want to travel with a fixed start time from a user-specific origin to a destination. An agent’s route may comprise several rides along given lines, each using vehicles with hard loading capacities. We give a characterization of (side-constrained) user equilibria via a quasi-variational inequality and prove their existence by generalizing a well-known existence result of Bernstein and Smith (Transp. Sci., 1994). We further derive a polynomial time algorithm for single-commodity instances and an exact finite time algorithm for the multi-commodity case. Based on our quasi-variational characterization, we finally devise a fast heuristic computing user equilibria, which is tested on real-world instances based on data gained from the Hamburg S-Bahn system and the Swiss long-distance train network. It turns out that w.r.t. the total travel time, the computed user-equilibria are quite efficient compared to a system optimum, which neglects equilibrium constraints and only minimizes total travel time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tobias Harks and Sven Jäger and Michael Markl and Philine Schiewe 2024 Is Part Of OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2024.17 urn:nbn:de:0030-drops-212054 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.17 eng https://creativecommons.org/licenses/by/4.0/legalcode