Earliest Arrival Flows with Flow-Dependent Transit Times

with capacities $u_a$ and transit times $\tau_a$ on its arcs $a \in
A$, together with a source vertex $s \in V$ and a sink vertex $t \in
V$. The objective is to send flow from $s$ to $t$, that moves through
the network over time, such that for each point in time $\theta \in
[0,T)$ the maximal amount of flow reaches $t$. In practical
applications, a higher congestion on an arc of a network often implies
a considerable increase in transit time. Therefore, in this talk we
study the earliest-arrival problem for the case, that the transit
times of each arc in the network at each time $\theta$ depends on the
flow on this particular arc at that time $\theta$.

For constant transit times it has been shown by Gale in 1957 that
earliest-arrival flows exist for any network. We give examples,
showing that this is no longer true for flow-dependent transit times.
For that reason we define an optimization version of this problem
where one looks for flows that are almost earliest-arrival flows. In
particular, we look for flows that for each $\theta \in [0,T)$ need
only $\alpha$-times longer to send the maximal flow to the sink. We give
both constant lower and upper bounds on $\alpha$. Furthermore, we present
a constant factor approximation algorithm for this problem. Finally,
we present some computational results to show the practicability of
the designed approximation algorithm.