Flows over Time with Load-Dependent Transit Times

More than forty years ago, Ford and Fulkerson studied maximum s-t-flows over time (also called "dynamic" flows) in networks with fixed transit times on the arcs and a fixed time horizon. Here, flow on arcs may change over time and transit times specify the amount of time it takes for flow to travel through a particular arc. Ford and Fulkerson proved that there always exists an optimal solution which sends flow on certain s-t-paths at a constant rate as long as there is enough time left for the flow along a path to arrive at the sink; a flow over time featuring this simple structure is called "temporally repeated." Although this result does not hold for the more general and also more realistic setting where transit times depend on the current flow situation, we show that there always exists a provably good temporally repeated solution. Moreover, such a solution can be determined very efficiently by only one minimum convex cost flow computation. Our results rest upon a new model of flow-dependent transit times. It is based on two assumption on the pace of flow on a particular arc. First, the pace of flow on an arc is assumed to be uniform for all flow units on an arc for each point in time. Second, this uniform pace is for each moment determined by the actual amount of flow on this arc. Finally, we show that the resulting flow-over-time problem is strongly NP-hard and cannot be approximated with arbitrary precision in polynomial time, unless P=NP.