An Equilibrium Model for Schedule-Based Transit Networks with Hard Vehicle Capacities
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912619111120896 |
|---|---|
| author | Harks, Tobias Jäger, Sven Markl, Michael Schiewe, Philine |
| author_facet | Harks, Tobias Jäger, Sven Markl, Michael Schiewe, Philine |
| contents | 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 is to integrate passengers' selfish routing behaviour under limited vehicle capacities. We formulate a side-constrained user equilibrium model in a schedule-based transit network, where passengers are modelled via a continuum of non-atomic agents that travel from their origin to their 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 for fixed departure times by generalizing a well-known result of Bernstein and Smith (Transp. Sci., 1994). We further derive a polynomial time algorithm for single-commodity instances with fixed departure times. For the multi-commodity case with departure time choice, we show that deciding whether an equilibrium exists is NP-hard, and we devise an exponential-time algorithm that computes an equilibrium if it exists, and signals non-existence otherwise. Using our quasi-variational characterization, we formulate a heuristic for computing multi-commodity user equilibria in practice, which is tested on multiple real-world instances. In terms of social cost, the computed user-equilibria are quite efficient compared to a system optimum. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_17153 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Equilibrium Model for Schedule-Based Transit Networks with Hard Vehicle Capacities Harks, Tobias Jäger, Sven Markl, Michael Schiewe, Philine Computer Science and Game Theory Optimization and Control 91A07 (Primary) 91A68, 90B06 (Secondary) 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 is to integrate passengers' selfish routing behaviour under limited vehicle capacities. We formulate a side-constrained user equilibrium model in a schedule-based transit network, where passengers are modelled via a continuum of non-atomic agents that travel from their origin to their 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 for fixed departure times by generalizing a well-known result of Bernstein and Smith (Transp. Sci., 1994). We further derive a polynomial time algorithm for single-commodity instances with fixed departure times. For the multi-commodity case with departure time choice, we show that deciding whether an equilibrium exists is NP-hard, and we devise an exponential-time algorithm that computes an equilibrium if it exists, and signals non-existence otherwise. Using our quasi-variational characterization, we formulate a heuristic for computing multi-commodity user equilibria in practice, which is tested on multiple real-world instances. In terms of social cost, the computed user-equilibria are quite efficient compared to a system optimum. |
| title | An Equilibrium Model for Schedule-Based Transit Networks with Hard Vehicle Capacities |
| topic | Computer Science and Game Theory Optimization and Control 91A07 (Primary) 91A68, 90B06 (Secondary) |
| url | https://arxiv.org/abs/2406.17153 |