The paper presents a dynamic solution method for the parametric minimum flow in time-dependent, dynamic network. This approach solves the problem for a special parametric dynamic network with linear lower bound functions of a single parameter. Instead of directly working in the original network, the method implements a labelling algorithm which works in the parametric dynamic residual network where repeatedly decreases the flow along quickest dynamic source-sink paths for different subintervals of parameter values, in their increasing order. In each iteration, the algorithm computes both the parametric minimum flow within a certain subinterval, and the new subinterval for which the flow needs to be computed.
Accepté le :
DOI : 10.1051/ita/2018002
Keywords: Dynamic network, parametric flow, shortest paths
Parpalea, Mircea 1 ; Avesalon, Nicoleta 1 ; Ciurea, Eleonor 1
@article{ITA_2018__52_1_43_0,
author = {Parpalea, Mircea and Avesalon, Nicoleta and Ciurea, Eleonor},
title = {Minimum parametric flow in time-dependent dynamic networks},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {43--53},
year = {2018},
publisher = {EDP Sciences},
volume = {52},
number = {1},
doi = {10.1051/ita/2018002},
mrnumber = {3843154},
zbl = {1400.90067},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ita/2018002/}
}
TY - JOUR AU - Parpalea, Mircea AU - Avesalon, Nicoleta AU - Ciurea, Eleonor TI - Minimum parametric flow in time-dependent dynamic networks JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2018 SP - 43 EP - 53 VL - 52 IS - 1 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ita/2018002/ DO - 10.1051/ita/2018002 LA - en ID - ITA_2018__52_1_43_0 ER -
%0 Journal Article %A Parpalea, Mircea %A Avesalon, Nicoleta %A Ciurea, Eleonor %T Minimum parametric flow in time-dependent dynamic networks %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2018 %P 43-53 %V 52 %N 1 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ita/2018002/ %R 10.1051/ita/2018002 %G en %F ITA_2018__52_1_43_0
Parpalea, Mircea; Avesalon, Nicoleta; Ciurea, Eleonor. Minimum parametric flow in time-dependent dynamic networks. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 52 (2018) no. 1, pp. 43-53. doi: 10.1051/ita/2018002
[1] , and , Network Flows: Theory, Algorithms and Applications. Prentice Hall Inc., Englewood Cliffs, NJ (1993). | MR | Zbl
[2] , A survey of dynamic network flows. Ann. Oper. Res. 20 (1989) 1–66. | MR | Zbl | DOI
[3] , Maximum flows in parametric dynamic networks with lower bounds. Ann. Univ. Craiova – Math. Comput. Sci. Ser. 43 (2016) 188–199. | MR | Zbl
[4] , and , The maximum parametric flow in discrete-time dynamic networks. Fundam. Inform. 156 (2017) 125–139. | MR | Zbl | DOI
[5] and , An overview on vehicle scheduling models. Public Transp. 1 (2009) 299–317. | DOI
[6] , and , Time-Varying Network Optimization. Springer (2007). | MR | Zbl
[7] , and , A simple algorithm for reliability evaluation in dynamic networks with stochastic transit time. J. Ind. Prod. Eng. 32 (2015) 115–120.
[8] and , Algorithms for flows with parametric capacities. ZOR-Methods Model. Oper. Res. 33 (1989) 21–37. | MR | Zbl | DOI
[9] , and , Model and a solution algorithm for the dynamic resource allocation problem for large-scale transportation network evacuation. Transp. Res. Part C: Emerg. Technol. 59 (2015) 233–247. | DOI
[10] and , On solving quickest time problems in time-dependent, dynamic network. J. Math. Model. Algorithms 3 (2004) 39–71. | MR | Zbl | DOI
[11] and , Minimum cost time-varying network flow problems. Optim. Methods Softw. 25 (2010) 429–447. | MR | Zbl | DOI
[12] , and , Efficient negative cycle-canceling algorithm for finding the optimal traffic routing for network evacuation with nonuniform threats. Transp. Res. Rec.: J. Transp. Res. Board 2459 (2014) 81–90. | DOI
[13] , Max flows in O(nm) time, or better, in Proc. of the Forty-Fifth Annual ACM Symposium on Theory of Computing, Palo Alto, California. ACM Press, New York (2013) 765–774. | Zbl | DOI
[14] , Min-Max Algorithm for the Parametric Flow Problem. Bull. Transilv. Univ. of Braşov. Ser. III: Math. Inf. Phys. 3 (2010) 191–198. | MR
[15] and , The quickest maximum dynamic flow of minimum cost. Int. J. Appl. Math. Inform. 3 (2011) 266–274.
[16] and , Partitioning algorithm for the parametric maximum flow. Appl. Math. 4 (2013) 3–10. | DOI
[17] and , Minimum parametric flow – a partitioning approach. Br. J. Appl. Sci. Technol. 13 (2016) 1–8. | DOI
[18] and , Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, 2nd edn. CRC Press (2015) 85–104. | DOI
[19] , Algorithmic Aspects of Flows in Networks, edited by . Vol. 69 of Mathematics and its Applications. Kluwer Academic Publishers, Springer-Verlag, Dordrecht (1991). | MR | Zbl
[20] , An introduction to network flows over time, in Research Trends in Combinatorial Optimization, edited by , and . Springer-Verlag, Berlin, Heidelberg (2009) 451–482. | MR | DOI
[21] , and , On the system optimum dynamic traffic assignment and earliest arrival flow problems. Transp. Sci. 49 (2015) 13–27. | DOI
Cité par Sources :
