Time-varying universal maximum flow problems

We consider a time-varying network without parallel arcs and loops, where a flow must take a certain time to traverse an are. The transit time on an a re and the capacity of an are are all time-varying parameters, which depend on the departure time to traverse the are. To depart at the best time, a f low can wait at the beginning vertex of an are, which is however limited by a time-varying vertex capacity. All those parameters, namely, the transit time, the are capacity, and the vertex capacity, are discrete functions of time t. The problem is to find an optimal solution to send the maximum flow from the source vertex to the sink vertex, within a given time T. Moreover , we address the so-called universal maximum flow problem, which is to find a solution that remains optimal when the time limit T is truncated to any t less than or equal to T. We consider three variants of the problem, with waiting at a vertex being arbitrarily allowed, strictly prohibited, and bou nded, respectively. Relevant algorithms are proposed, which can find optima l solutions in pseudopolynomial time. (C) 2001 Elsevier Science Ltd. All ri ghts reserved.