Minimum Flows in Parametric Dynamic Networks. The Static Approach

Abstract

The problems of flows in parametric networks extend the classical problems of optimal flow to some special kind of networks where capacities of certain arcs are not constants but depending on several parameters. Consequently, these problems consist of solving a range of ordinary (nonparametric) optimal flow problems for all the parameter values within certain sub-intervals of the parameter values. Although classical network flow models have been widely used as valuable tools for many applications [1], they fail to capture the essential property of the dynamic aspect of many real-life problems, such as traffic planning, production and distribution systems, communication systems, evacuation planning, etc. In all these cases, time is an essential component, either because the flows take time to pass from one location to another, or because the structure of the network changes over time. Accordingly, the dynamic flow models seem suited to catch and describe different real-life dynamic problems such as network-structure changing over time or timely decision-making, but, because of their complexity, these models have not been as thoroughly investigated as those of classical flows.

This article presents and solves the problem of the minimum flows in a parametric dynamic network. The proposed approach consists in applying a parametric flow algorithm in the reduced expended network which is obtained by expanding the original dynamic network. A numerical example is also presented for a better understanding of the used approach.