Time-varying universal maximum flow problems (Q5936757)

The authors are deeling with maximum flow problems in time-varying networks, where the transit time and the capacity of an arc are time-dependent parameters as well as the waiting-time in vertices, too. The focus is on solutions, which remain optimal, when the time-horizon \(T\) is truncated to any \(t\leq T\). For this reason the authors adapt the classical concepts of flow-augmenting path and residual network to dynamic f-augmenting path and dynamic residual network. Three special seenarios are analysed in detail:NEWLINENEWLINENEWLINE1. if no waiting is allowed at vertices, a labeling algorithm is proposed, which solves the problem in \(O(U nm T^2)\) time, where \(U\) denotes the maximum capacity of arcs over time-horizon \(T,n\) is the number of vertices and \(m\) the number of arcs in the network.NEWLINENEWLINENEWLINE2. if arbitrary waiting times at vertices are allowed, but no restriction on the capacity of vertices is given, a simple modification of the labeling operation yields similar results.NEWLINENEWLINENEWLINEIf additionally time-dependent capacities at vertices are to be included, a more detailed labeling process is proposed.NEWLINENEWLINENEWLINE3. in case of bounded waiting times at vertices, but no vertex capacity limits, the authors provide a complicated labeling procedure and show -- by a detailed case analysis -- optimality within \(O(UnT^2 (m+n\log T))\) time.NEWLINENEWLINENEWLINEThe paper does not refer to any of the interesting results obtained in the last ten years, e.g. in dynamic traffic assignment or evacuation problems.