Flows over time in time-varying networks: Optimality conditions and strong duality

•Studying a general class of network flows over time in a continuous-time model.•Developing the key concepts and techniques that are the cornerstones of static network flows.•Establishing reduced cost and negative cycle optimality conditions.•Deriving a strong duality result from these optimality conditions.

There has been much research on network flows over time due to their important role in real world applications. This has led to many results, but the more challenging continuous time model still lacks some of the key concepts and techniques that are the cornerstones of static network flows. The aim of this paper is to advance the state of the art for dynamic network flows by developing the continuous time analogues of the theory for static network flows. Specifically, we make use of ideas from the static case to establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of network flows over time.