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.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2018002
Classification : 05C85, 68R10, 90C47
Mots-clés : Dynamic network, parametric flow, shortest paths
Parpalea, Mircea 1 ; Avesalon, Nicoleta 1 ; Ciurea, Eleonor 1

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},
     publisher = {EDP-Sciences},
     volume = {52},
     number = {1},
     year = {2018},
     doi = {10.1051/ita/2018002},
     mrnumber = {3843154},
     zbl = {1400.90067},
     language = {en},
     url = {http://archive.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  - http://archive.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 http://archive.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. http://archive.numdam.org/articles/10.1051/ita/2018002/

[1] R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice Hall Inc., Englewood Cliffs, NJ (1993). | MR | Zbl

[2] J.E. Aronson, A survey of dynamic network flows. Ann. Oper. Res. 20 (1989) 1–66. | DOI | MR | Zbl

[3] N. Avesalon (Grigoraş), Maximum flows in parametric dynamic networks with lower bounds. Ann. Univ. Craiova – Math. Comput. Sci. Ser. 43 (2016) 188–199. | MR | Zbl

[4] N. Avesalon (Grigoraş), E. Ciurea and M. Parpalea, The maximum parametric flow in discrete-time dynamic networks. Fundam. Inform. 156 (2017) 125–139. | DOI | MR | Zbl

[5] S. Bunte and N. Kliewer, An overview on vehicle scheduling models. Public Transp. 1 (2009) 299–317. | DOI

[6] X. Cai, D. Sha and C.K. Wong, Time-Varying Network Optimization. Springer (2007). | MR | Zbl

[7] H.S. Fathabadi, S. Khezri and S. Khodayifar, A simple algorithm for reliability evaluation in dynamic networks with stochastic transit time. J. Ind. Prod. Eng. 32 (2015) 115–120.

[8] H.W. Hamacher and L.R. Foulds, Algorithms for flows with parametric capacities. ZOR-Methods Model. Oper. Res. 33 (1989) 21–37. | DOI | MR | Zbl

[9] X. He, H. Zheng and S. Peeta, 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] E. Miller-Hooks and S. Stock Patterson, On solving quickest time problems in time-dependent, dynamic network. J. Math. Model. Algorithms 3 (2004) 39–71. | DOI | MR | Zbl

[11] E. Nasrabadi and S.M. Hashemi, Minimum cost time-varying network flow problems. Optim. Methods Softw. 25 (2010) 429–447. | DOI | MR | Zbl

[12] N. Nassir, H. Zheng and M. Hickman, 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] J.B. Orlin, 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. | DOI | Zbl

[14] M. Parpalea, 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] M. Parpalea and E. Ciurea, The quickest maximum dynamic flow of minimum cost. Int. J. Appl. Math. Inform. 3 (2011) 266–274.

[16] M. Parpalea and E. Ciurea, Partitioning algorithm for the parametric maximum flow. Appl. Math. 4 (2013) 3–10. | DOI

[17] M. Parpalea and E. Ciurea, Minimum parametric flow – a partitioning approach. Br. J. Appl. Sci. Technol. 13 (2016) 1–8. | DOI

[18] H. Rashidi and E. Tsang, Vehicle Scheduling in Port Automation: Advanced Algorithms for Minimum Cost Flow Problems, 2nd edn. CRC Press (2015) 85–104. | DOI

[19] G. Ruhe, Algorithmic Aspects of Flows in Networks, edited by M. Hazewinkel. Vol. 69 of Mathematics and its Applications. Kluwer Academic Publishers, Springer-Verlag, Dordrecht (1991). | MR | Zbl

[20] M. Skutella, An introduction to network flows over time, in Research Trends in Combinatorial Optimization, edited by W. Cook, L. Lovàsz and J. Vygen. Springer-Verlag, Berlin, Heidelberg (2009) 451–482. | DOI | MR

[21] H. Zheng, Y-C. Chiu and P.B. Mirchandani, On the system optimum dynamic traffic assignment and earliest arrival flow problems. Transp. Sci. 49 (2015) 13–27. | DOI

Cité par Sources :