Minimum Flows in Parametric Dynamic Networks. The Static Approach
DOI:
https://doi.org/10.31449/inf.v44i3.1907Abstract
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.References
REFERENCES
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.
Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
