Minimum Flows in Parametric Dynamic Networks. The Static Approach

Nicoleta Grigoras


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.

Full Text:




Ahuja R., Magnanti T., Orlin J. (1993), Network Flows. Theory, algorithms and applications, Prentice Hall, Inc., Engleewood Clifss, New Jersey.

Aronson J.A. (1989),A survey of dynamic networks flows, Annals of Operations Research, 20 (5), pp. 1-66.

Avesalon N., Ciurea E., Parpalea M. (2017),Maximum parametric flow in discrete-time dynamic networks, Fundamenta informaticae, 156 (2), pp. 125-139.

Cai X., Sha D., Wong C. (2007), Time-varying Network Optimization, Springer.

Ciurea E., Ciupal_a L. (2004), Sequential and parallel algorithms for minimum flow, Journal of Applied Mathematics and Computing, 15(1-2), pp. 53-75.

Ciurea E., Second best temporally repeated flows (2002), The Korean Journal of Computational and Applied Mathematics, 9(1), pp. 77-86.

He X., Zheng H., Peeta S. (2015), Model and solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation, Transportation Research Part C.: Emerging Technologies,59, pp.233-247.

Miller-Hooks E., Patterson S.S. (2004), On solving quickest time problems in time-dependent, dynamic networks, Journal of Mathematical Modelling and Algorithms, 3,pp.39-71

Nasrabadi E., Hashemi S.M. (2010), Minimum cost time-varying network flow problems, Optimization Methods and Software, 25(3), pp. 429-447.

Orlin J. (2013), Max Flows in O(nm) time, or better, Proceeding of the forty-_fifth Annual ACM Symposium on Theory of Computing., ACM Press, New York, pp. 765-774.

Parpalea M., Ciurea E.(2016), Minimum parametric flow. A partitioning approach., British Journal of Applied Science and Technology, 13(6), pp. 1-8.

Parpalea M., Ciurea E. (2011), The quickest maximum dynamic flow of minimum cost, International Journal of Applied Mathematics and Informatics, 3(5), pp.266-274.

Parpalea M., Ciurea E.(2013), Partitioning algorithm for the parametric maximum flow, Applied Mathematics, 4(10A), pp. 3-10.

Parpalea M., Avesalon N., Ciurea E. (2018) minimum parametric flow in time dependent dynamic networks, revue d’Automatique, d’Informatique et de Recherche Operationnelle – Theoretical Informatics and Applications (RAIRO: ITA),52(1), pp. 43-53.

Rashidi H., Tsang E. (2015), Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, CRC Press, 2 edition, Boca Raton, London, New York.

Ruhe G. (1991), Algorithmic Aspects of Flows in Networks, Kluwer Academic Publisher, Dordrecht, The Netherlands.

Zheng H., Chiu Y.C., Mirchandani P.B. (2015), On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems, Transportation Science, 49, pp. 13-27.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.