Search Results

Documents authored by Harks, Tobias

Document
DOI: 10.4230/OASIcs.ATMOS.2024.17
Computing User Equilibria for Schedule-Based Transit Networks with Hard Vehicle Capacities

Authors: Tobias Harks, Sven Jäger, Michael Markl, and Philine Schiewe

Published in: OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)

Abstract
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.
Cite as

Tobias Harks, Sven Jäger, Michael Markl, and Philine Schiewe. Computing User Equilibria for Schedule-Based Transit Networks with Hard Vehicle Capacities. In 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024). Open Access Series in Informatics (OASIcs), Volume 123, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harks_et_al:OASIcs.ATMOS.2024.17,
  author =	{Harks, Tobias and J\"{a}ger, Sven and Markl, Michael and Schiewe, Philine},
  title =	{{Computing User Equilibria for Schedule-Based Transit Networks with Hard Vehicle Capacities}},
  booktitle =	{24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)},
  pages =	{17:1--17:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-350-8},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{123},
  editor =	{Bouman, Paul C. and Kontogiannis, Spyros C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.17},
  URN =		{urn:nbn:de:0030-drops-212054},
  doi =		{10.4230/OASIcs.ATMOS.2024.17},
  annote =	{Keywords: traffic assignment, side-constrained equilibrium, public transportation}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2022.6
Dynamic Traffic Assignment for Electric Vehicles

Authors: Lukas Graf, Tobias Harks, and Prashant Palkar

Published in: OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

Abstract
We initiate the study of dynamic traffic assignment for electrical vehicles addressing the specific challenges such as range limitations and the possibility of battery recharge at predefined charging locations. We pose the dynamic equilibrium problem within the deterministic queueing model of Vickrey and as our main result, we establish the existence of an energy-feasible dynamic equilibrium. There are three key modeling-ingredients for obtaining this existence result: 1) We introduce a walk-based definition of dynamic traffic flows which allows for cyclic routing behavior as a result of recharging events en route. 2) We use abstract convex feasibility sets in an appropriate function space to model the energy-feasibility of used walks. 3) We introduce the concept of capacitated dynamic equilibrium walk-flows which generalize the former unrestricted dynamic equilibrium path-flows. Viewed in this framework, we show the existence of an energy-feasible dynamic equilibrium by applying an infinite dimensional variational inequality, which in turn requires a careful analysis of continuity properties of the network loading as a result of injecting flow into walks. We complement our theoretical results by a computational study in which we design a fixed-point algorithm computing energy-feasible dynamic equilibria. We apply the algorithm to standard real-world instances from the traffic assignment community illustrating the complex interplay of resulting travel times, energy consumption and prices paid at equilibrium.
Cite as

Lukas Graf, Tobias Harks, and Prashant Palkar. Dynamic Traffic Assignment for Electric Vehicles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{graf_et_al:OASIcs.ATMOS.2022.6,
  author =	{Graf, Lukas and Harks, Tobias and Palkar, Prashant},
  title =	{{Dynamic Traffic Assignment for Electric Vehicles}},
  booktitle =	{22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)},
  pages =	{6:1--6:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-259-4},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{106},
  editor =	{D'Emidio, Mattia and Lindner, Niels},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.6},
  URN =		{urn:nbn:de:0030-drops-171104},
  doi =		{10.4230/OASIcs.ATMOS.2022.6},
  annote =	{Keywords: Electromobility, Dynamic Traffic Assignment, Dynamic Flows, Fixed Point Algorithm}
}
Document
DOI: 10.4230/DagRep.8.3.21
Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 18102)

Authors: Roberto Cominetti, Tobias Harks, Carolina Osorio, and Britta Peis

Published in: Dagstuhl Reports, Volume 8, Issue 3 (2018)

Abstract
Traffic assignment models are crucial for traffic planners to be able to predict traffic distributions, especially, in light of possible changes of the infrastructure, e.g., road constructions, traffic light controls, etc. The starting point of the seminar was the observation that there is a trend in the transportation community (science as well as industry) to base such predictions on complex computer-based simulations that are capable of resolving many elements of a real transportation system. On the other hand, within the past few years, the theory of dynamic traffic assignments in terms of equilibrium existence and equilibrium computation has not matured to the point matching the model complexity inherent in simulations. In view of the above, this interdisciplinary seminar brought together leading scientists in the areas traffic simulations, algorithmic game theory and dynamic traffic assignment as well as people from industry with strong scientific background who identified possible ways to bridge the described gap.
Cite as

Roberto Cominetti, Tobias Harks, Carolina Osorio, and Britta Peis. Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 18102). In Dagstuhl Reports, Volume 8, Issue 3, pp. 21-38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Article{cominetti_et_al:DagRep.8.3.21,
  author =	{Cominetti, Roberto and Harks, Tobias and Osorio, Carolina and Peis, Britta},
  title =	{{Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 18102)}},
  pages =	{21--38},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2018},
  volume =	{8},
  number =	{3},
  editor =	{Cominetti, Roberto and Harks, Tobias and Osorio, Carolina and Peis, Britta},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.3.21},
  URN =		{urn:nbn:de:0030-drops-92954},
  doi =		{10.4230/DagRep.8.3.21},
  annote =	{Keywords: Algorithm and complexity of traffic equilibrium computation, dynamic traffic assignment models, Simulation and network optimization}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.154
Efficient Black-Box Reductions for Separable Cost Sharing

Authors: Tobias Harks, Martin Hoefer, Anja Huber, and Manuel Surek

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In cost sharing games with delays, a set of agents jointly uses a finite subset of resources. Each resource has a fixed cost that has to be shared by the players, and each agent has a non-shareable player-specific delay for each resource. A prominent example is uncapacitated facility location (UFL), where facilities need to be opened (at a shareable cost) and clients want to connect to opened facilities. Each client pays a cost share and his non-shareable physical connection cost. Given any profile of subsets used by the agents, a separable cost sharing protocol determines cost shares that satisfy budget balance on every resource and separability over the resources. Moreover, a separable protocol guarantees existence of pure Nash equilibria in the induced strategic game for the agents. In this paper, we study separable cost sharing protocols in several general combinatorial domains. We provide black-box reductions to reduce the design of a separable cost sharing protocol to the design of an approximation algorithm for the underlying cost minimization problem. In this way, we obtain new separable cost sharing protocols in games based on arbitrary player-specific matroids, single-source connection games without delays, and connection games on n-series-parallel graphs with delays. All these reductions are efficiently computable - given an initial allocation profile, we obtain a profile of no larger cost and separable cost shares turning the profile into a pure Nash equilibrium. Hence, in these domains any approximation algorithm can be used to obtain a separable cost sharing protocol with a price of stability bounded by the approximation factor.
Cite as

Tobias Harks, Martin Hoefer, Anja Huber, and Manuel Surek. Efficient Black-Box Reductions for Separable Cost Sharing. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 154:1-154:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{harks_et_al:LIPIcs.ICALP.2018.154,
  author =	{Harks, Tobias and Hoefer, Martin and Huber, Anja and Surek, Manuel},
  title =	{{Efficient Black-Box Reductions for Separable Cost Sharing}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{154:1--154:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.154},
  URN =		{urn:nbn:de:0030-drops-91587},
  doi =		{10.4230/LIPIcs.ICALP.2018.154},
  annote =	{Keywords: Cost Sharing, Price of Stability, Matroids, Connection Games}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.49
Competitive Packet Routing with Priority Lists

Authors: Tobias Harks, Britta Peis, Daniel Schmand, and Laura Vargas Koch

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In competitive packet routing games, packets are routed selfishly through a network and scheduling policies at edges determine which packages are forwarded first if there is not enough capacity on an edge to forward all packages at once. We analyze the impact of priority lists on the worst-case quality of pure Nash equilibria. A priority list is an ordered list of players that may or may not depend on the edge. Whenever the number of packets entering an edge exceeds the inflow capacity, packets are processed in list order. We derive several new bounds on the price of anarchy and stability for global and local priority policies. We also consider the question of the complexity of computing an optimal priority list. It turns out that even for very restricted cases, i.e., for routing on a tree, the computation of an optimal priority list is APX-hard.
Cite as

Tobias Harks, Britta Peis, Daniel Schmand, and Laura Vargas Koch. Competitive Packet Routing with Priority Lists. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{harks_et_al:LIPIcs.MFCS.2016.49,
  author =	{Harks, Tobias and Peis, Britta and Schmand, Daniel and Vargas Koch, Laura},
  title =	{{Competitive Packet Routing with Priority Lists}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{49:1--49:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.49},
  URN =		{urn:nbn:de:0030-drops-64622},
  doi =		{10.4230/LIPIcs.MFCS.2016.49},
  annote =	{Keywords: packet routing, Nash equilibrium, price of anarchy, priority policy, complexity}
}
Document
DOI: 10.4230/DagRep.5.10.19
Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 15412)

Authors: José R. Correa, Tobias Harks, Kai Nagel, Britta Peis, and Martin Skutella

Published in: Dagstuhl Reports, Volume 5, Issue 10 (2016)

Abstract
Traffic assignment models are crucial for traffic planners to be able to predict traffic distributions, especially, in light of possible changes of the infrastructure, e.g., road constructions, traffic light controls, etc. The starting point of the seminar was the observation that there is a trend in the transportation community (science as well as industry) to base such predictions on complex computer-based simulations that are capable of resolving many elements of a real transportation system. On the other hand, within the past few years, the theory of dynamic traffic assignments in terms of equilibrium existence and equilibrium computation has not matured to the point matching the model complexity inherent in simulations. In view of the above, this interdisciplinary seminar brought together leading scientists in the areas traffic simulations, algorithmic game theory and dynamic traffic assignment as well as people from industry with strong scientific background who identified possible ways to bridge the described gap.
Cite as

José R. Correa, Tobias Harks, Kai Nagel, Britta Peis, and Martin Skutella. Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 15412). In Dagstuhl Reports, Volume 5, Issue 10, pp. 19-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{correa_et_al:DagRep.5.10.19,
  author =	{Correa, Jos\'{e} R. and Harks, Tobias and Nagel, Kai and Peis, Britta and Skutella, Martin},
  title =	{{Dynamic Traffic Models in Transportation Science (Dagstuhl Seminar 15412)}},
  pages =	{19--34},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{10},
  editor =	{Correa, Jos\'{e} R. and Harks, Tobias and Nagel, Kai and Peis, Britta and Skutella, Martin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.10.19},
  URN =		{urn:nbn:de:0030-drops-56938},
  doi =		{10.4230/DagRep.5.10.19},
  annote =	{Keywords: Dynamic traffic equilibria, Complexity of equilibrium computation, Simulation, Dynamic network flow theory, Network optimization}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.226
Complexity and Approximation of the Continuous Network Design Problem

Authors: Martin Gairing, Tobias Harks, and Max Klimm

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
We revisit a classical problem in transportation, known as the continuous (bilevel) network design problem, CNDP for short. Given a graph for which the latency of each edge depends on the ratio of the edge flow and the capacity installed, the goal is to find an optimal investment in edge capacities so as to minimize the sum of the routing cost of the induced Wardrop equilibrium and the investment cost for installing the capacity. While this problem is considered as challenging in the literature, its complexity status was still unknown. We close this gap showing that CNDP is strongly NP-complete and APX-hard, both on directed and undirected networks and even for instances with affine latencies. As for the approximation of the problem, we first provide a detailed analysis for a heuristic studied by Marcotte for the special case of monomial latency functions (Math. Program., Vol. 34, 1986). We derive a closed form expression of its approximation guarantee for arbitrary sets of latency functions. We then propose a different approximation algorithm and show that it has the same approximation guarantee. However, we show that using the better of the two approximation algorithms results in a strictly improved approximation guarantee for which we derive a closed form expression. For affine latencies, e.g., this algorithm achieves a 49/41-approximation which improves on the 5/4 that has been shown before by Marcotte. We finally discuss the case of hard budget constraints on the capacity investment.
Cite as

Martin Gairing, Tobias Harks, and Max Klimm. Complexity and Approximation of the Continuous Network Design Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 226-241, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gairing_et_al:LIPIcs.APPROX-RANDOM.2014.226,
  author =	{Gairing, Martin and Harks, Tobias and Klimm, Max},
  title =	{{Complexity and Approximation of the Continuous Network Design Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{226--241},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.226},
  URN =		{urn:nbn:de:0030-drops-46998},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.226},
  annote =	{Keywords: Bilevel optimization, Optimization under equilibrium constraints, Network design, Wardrop equilibrium, Computational complexity, Approximation algorit}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact