The Maximum Parametric Flow in Discrete-time Dynamic Networks

• Autorzy: Avesalon N. , Ciurea E. , Parpalea M.

Identyfikatory

DOI

10.3233/FI-2017-1600

• Języki publikacji: EN

Abstrakty

EN

This article states and solves the maximum parametric flow over time problem. The proposed approach consists in repeatedly finding the maximum dynamic flow in discrete dynamic networks, for a sequence of parameter values, in their increasing order. In each of its iterations, the algorithm computes both the maximum flow, by minimizing the transit time (quickest flow), and the new breakpoint for the maximum parametric dynamic flow value function. The dynamic flow is augmented along quickest paths from the source node to the sink node in the time-space network, avoiding the explicit time expansion of the network. The complexity of the algorithm is presented and also an example is given on how the algorithm works.

Słowa kluczowe

EN

dynamic networks; parametric flow; successive shortest paths

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 156, nr 2
• Strony: 125--139
• Opis fizyczny: Bibliogr. 15 poz., rys., tab., wykr.

Twórcy

autor

Avesalon N.

• Faculty of Mathematics and Computer Science, Transilvania University of Braşov, Eroilor blvd 25, 500030 Brasov, Romania

autor

Ciurea E.

• Faculty of Mathematics and Computer Science, Transilvania University of Braşov, Eroilor blvd 25, 500030 Brasov, Romania

autor

Parpalea M.

• National College Andrei Şaguna, Şaguna str. 1, 590000, Brasov, Romania

Bibliografia

• [1] Ahuja R, Magnanti T, Orlin J. Network Flows. Theory, algorithms and applications, Prentice Hall Inc., Englewood Cliffs, New Jersey, 1993. ISBN-10:013617549X, 13:978-0136175490.
• [2] Aronson JA. A survey of dynamic network flows, Annals of Operations Research, 1989;20(5)1–66. URL https://doi.org/10.1007/BF02216922.
• [3] Cai X, Sha D, Wong C. Time-varying Network Optimization, Springer, 2007. doi:10.1007/0-387-71215-1.
• [4] Fathabadi HS, Khezri S, Khodayifar S. A simple algorithm for reliability evaluation in dynamic networks with stochastic transit times, Journal of Industrial and Production Engineering 2015;32(2)115–120. URL http://dx.doi.org/10.1080/21681015.2015.1015460.
• [5] Hamacher HW, Foulds LR. Algorithms for Flows with Parametric Capacities, ZOR-Methods and Models of Operations Research, 1989;3321–37. doi:10.1007/BF01415514.
• [6] He X, Zheng H, Peeta S. Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation, Transportation Research Part C: Emerging Technologies, 2015;7441–458. URL https://doi.org/10.1016/j.trpro.2015.06.023.
• [7] Miller-Hooks E, Patterson SS. On solving quickest time problems in time-dependent, dynamic networks, Journal of Mathematical Modelling and Algorithms, 2004;3(1)39–71. URL https://doi.org/10.1023/B:JMMA.0000026708.57419.6d.
• [8] Nasrabadi E, Hashemi SM. Minimum cost time-varying network flow problems, Optimization Methods and Software, 2010;25(3)429–447. doi:10.1080/10556780903239121.
• [9] Nassir N, Zheng H, Mark M. Efficient Negative Cycle-Canceling Algorithm for Finding the Optimal Traffic Routing for Network Evacuation with Nonuniform Threats, Transportation Research Record: Journal of the Transportation Research Board, 2014;245981–90. URL https://doi.org/10.3141/2459-10.
• [10] Orlin JB. Max flows in O(nm) time, or better, Proceedings of the forty-fifth annual ACM symposium on Theory of computing, ACM Press, New York, 2013, 765–774. doi:10.1145/2488608.2488705.
• [11] Parpalea M, Ciurea E. The quickest maximum dynamic flow of minimum cost, International Journal of Applied Mathematics and Informatics, 2011;3(5)266–274.
• [12] Parpalea M, Ciurea E. Partitioning algorithm for the parametric maximum flow, Applied Mathematics, 2013;4(10A)3–10. doi:10.4236/am.2013.410A1002.
• [13] Rashidi, H., Tsang, E. Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, CRC Press, 2 edition 2015. ISBN:9781498732536 - CAT# K26250.
• [14] Ruhe G. Algorithmic Aspects of Flows in Networks, Kluwer Academic Publishers. Dordrecht (The Netherlands), 1991. doi:10.1007/978-94-011-3444-6.
• [15] Zheng H, Chiu YC, Mirchandani PB. On the System Optimum Dynamic Traffic Assignment and Earliest Arrival Flow Problems, Transportation Science, 2015;4913–27. ISSN:0041-1655.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).