Lukas Graf

Publications

Side-Constrained Dynamic Traffic Equilibria (published)
joint work with Tobias Harks

We study dynamic traffic assignment with side-constraints. We first give a counter-example to a key result from the literature regarding the existence of dynamic equilibria for volume-constrained traffic models in the classical edge-delay model. We then propose a new framework for side-constrained dynamic equilibria based on the concept of feasible ε-deviations of flow particles in space and time. Under natural assumptions, we characterize the resulting equilibria by means of quasi-variational and variational inequalities, respectively. Finally, we establish first existence results for side-constrained dynamic equilibria for the non-convex setting of volume-constraints.
- One-page abstract at Twenty-Fourth ACM Conference on Economics and Computation (EC'23): https://doi.org/10.1145/3580507.3597801
- Preprint on arXiv: https://arxiv.org/abs/2211.03194
Dynamic Traffic Assignment for Electric Vehicles (published)
joint work with Tobias Harks and Prashant Palkar

We study 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. We complement our theoretical results by a computational study in which we design a fixed-point algorithm computing energy-feasible dynamic equilibria.
- Extended abstract at 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and System (ATMOS 2022): https://doi.org/10.4230/OASIcs.ATMOS.2022.6
- Preprint on arXiv: https://arxiv.org/abs/2207.04454
Machine-Learned Prediction Equilibrium for Dynamic Traffic Assignment (published)
joint work with Tobias Harks, Kostas Kollias and Michael Markl

We study a dynamic traffic assignment model, where agents base their instantaneous routing decisions on real-time delay predictions. We describe a general mathematical model which, in particular, includes the settings leading to IDE und DE. On the theoretical side we show existence of equilibrium solutions under some additional assumptions while on the practical side we implement a machine-learned predictor and compare it to other static predictors.
- Extended abstract at 36th AAAI Conference on Artificial Intelligence. AAAI-22: https://doi.org/10.1609/aaai.v36i5.20438
- Full version in Journal of Machine Learning Research (2023): https://jmlr.org/papers/v24/22-1446.html
- Preprint on arXiv: https://arxiv.org/abs/2109.06713
A Finite Time Combinatorial Algorithm for Instantaneous Dynamic Equilibrium Flows (published)
joint work with Tobias Harks

We study the computational complexity of Instantaneous Dynamic Equilibria (IDE) and show that a natural extension algorithm needs only finitely many phases to converge leading to the first finite time combinatorial algorithm computing an IDE. We complement this result by several hardness results showing that computing IDE with natural properties is NP-hard.
- Extended abstract in International Conference on Integer Programming and Combinatorial Optimization. IPCO 2021: https://doi.org/10.1007/978-3-030-73879-2_8
- Full version in Mathematical Programming (2022): https://doi.org/10.1007/s10107-022-01772-0
- Full version on arXiv: https://arxiv.org/abs/2007.07808
The Price of Anarchy for Instantaneous Dynamic Equilibria (published)
joint work with Tobias Harks

We study the price of anarchy (PoA) for Instantaneous Dynamic Equilibria (IDE) and show an upper bound of order O(U⋅τ) for single-sink instances, where U denotes the total inflow volume and τ the sum of edge travel times. We complement this upper bound with a family of instances proving a lower bound of order Ω(U⋅logτ).
- Extended abstract in International Conference on Web and Internet Economics. WINE 2020: https://doi.org/10.1007/978-3-030-64946-3_17
- Full version in Mathematics of Operations Research: https://doi.org/10.1287/moor.2022.1336
- Full version on arXiv: https://arxiv.org/abs/2007.07794
Dynamic Flows with Adaptive Route Choice (published)
joint work with Tobias Harks and Leon Sering

We study dynamic network flows and introduce a notion of instantaneous dynamic equilibrium (IDE) requiring that for any positive inflow into an edge, this edge must lie on a currently shortest path towards the respective sink. We measure current shortest path length by current waiting times in queues plus physical travel times. For single-sink networks we show existence and termination of IDE flows. For multi-sink networks we show existence and give an example for an instance where IDE flows never terminate.
- Extended abstract in Integer Programming and Combinatorial Optimization. IPCO 2019: https://doi.org/10.1007/978-3-030-17953-3_17
- Full version in Mathematical Programming (2020): https://doi.org/10.1007/s10107-020-01504-2
- Full version on arXiv: https://arxiv.org/abs/1811.07381

There is also a list of errata for these papers.

Talks

2023:

Thesis Defense (Augsburg), September „Dynamic Network Flows with Adaptive Route Choice based on Current Information“ (Slides | Thesis)
EC 2023 (London), July „Side-Constrained Dynamic Traffic Equilibria“ (Slides)
Group workshop (Passau), June „Dynamic Network Flows with Adaptive Route Choice“ (Slides)
13th DCGT (Amsterdam), June „Side-Constrained Dynamic Traffic Equilibria“ (Slides)

2022:

ATMOS 2022 (Potsdam), September „Dynamic Traffic Assignment for Electric Vehicles“ (Slides)
Graduate Get Together (Augsburg), June „Dynamic Flows with Adaptive Route Choice“ (Slides)
Dagstuhl-Seminar (Schloss Dagstuhl), May „Dynamic Traffic Assignment for Electric Vehicles“ (Slides)

2021:

IPCO 2021 (Atlanta), May „A Finite Time Combinatorial Algorithm for Instantaneous Dynamic Equilibrium Flows“ (Slides | Video | extended Video)

2020:

WINE 2020 (Beijing), December „The Price of Anarchy for Instantaneous Dynamic Equilibria“ (Slides | Video)
OMS-Seminar (Aachen), October „Instantaneous Dynamic Equilibrium Flows“ (Slides)
Dagstuhl-Seminar (Schloss Dagstuhl), September „Computational Complexity of Instantaneous Dynamic Equilibrium Flows“ (Slides)
Arbeitsseminar (Augsburg), June „Dynamic Flows with Adaptive Route Choice“ (Slides)

2019:

OR 2019 (Dresden), September: „Termination Time of IDE Flows in Single Sink Networks“ (Slides)
IPCO 2019 (Ann Arbor), May: „Dynamic Flows with Adaptive Route Choice“ (Slides)
DCGT 2019 (Potsdam), February: „Dynamic Flows with Adaptive Route Choice“ (Slides)

Other Activities

I have been a guest on the podcast Algo2Go, where I talked with the hosts Laura Vargas Koch and Niklas Rieken about IDE flows (in German):

Episode 17 - IDEs in dynamischen Flüssen

I am part of the „Mathezirkel-Team“ at Augsburg University - a group of students organizing various activities for pupils interested in mathematics. Some of my lecture notes for such activities can be found here (in German).

Curriculum Vitea

2023 - present: PostDoc

Since 2023 I am a PostDoc in the group of Tobias Harks at the University of Passau.

Teachings: I am currently teaching a course on Dynamic Network Flows (lecture notes)

2017 - 2023: PhD Student

From 2017 to 2023 I was a PhD student of Tobias Harks at the University of Augsburg.

2014 - 2017: Mathematics M.Sc.

Master's Thesis: „Zusammenhänge von Auslastungs- und Potentialspielen“ (Connections between Congestion and Potential Games), supervisor: Tobias Harks (pdf | LaTeX-Files | Slides)
My personal notes for some of the lectures I attended during the course of my studies can be found here.
Teachings: Exercise classes to the lectures „Lineare Algebra I/II“, „Analysis I/II“, Informatik III (Computer Science III), „Kombinatorische Optimierung“ (Combinatorial Optimiziation), a lecture on differentiation and integration in a repetition course for Analysis I (Slides) and tutor at „Offener Matheraum“

2014: Internship at Munich Re

2011 - 2014: Mathematics B.Sc.

Bachelor's Thesis: „Der Satz von Gelfand-Neumark und eine Erweiterung für topologische Mannigfaltigkeiten“ (The Theorem of Gelfand-Neumark and an Extension for Topological Manifolds), supervisor: Kai Cieliebak (pdf | LaTeX-Files)
My personal lecture notes for some of the lectures I attended during the course of my studies can be found here.
Teachings: Exercise classes to the lectures „Logik für Informatiker“ (Logic for Computer Scientists) and „Einführung in die theoretische Informatik“ (Introduction to Theoretical Computer Sciences)

Contact/Social Media