hide
Free keywords:
-
Abstract:
For the earliest arrival flow problem one is given a network $G=(V,
A)$ with capacities $u(a)$ and transit times $\tau(a)$ on its arcs $a
\in A$, together with a source and a sink vertex $s, 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 maximum possible amount of flow reaches $t$. If, for
each $\theta \in [0,T)$ this flow is a maximum flow for time horizon
$\theta$, then it is called \emph{earliest arrival flow}. In
practical applications a higher congestion of an arc in the network
often implies a considerable increase in transit time. Therefore,
in this paper we study the earliest arrival problem for the case
that the transit time 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 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 the
objective is to find flows that are almost earliest arrival flows.
In particular, we are interested in flows that, for each $\theta \in
[0,T)$, need only $\alpha$-times longer to send the maximum 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 give some computational results to
show the practicability of the designed approximation algorithm.
