Minimum parametric flow in time-dependent dynamic networks. (English) Zbl 1400.90067
Summary: 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.
MSC:
| 90B10 | Deterministic network models in operations research |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C38 | Paths and cycles |
| 05C12 | Distance in graphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90C47 | Minimax problems in mathematical programming |
References:
| [1] | R. Ahuja, T. Magnanti and J. Orlin, Network Flows: Theory, Algorithms and Applications. Prentice Hall Inc., Englewood Cliffs, NJ (1993). · Zbl 1201.90001 |
| [2] | J.E. Aronson, A survey of dynamic network flows. Ann. Oper. Res.20 (1989) 1-66. · Zbl 0704.90028 · doi:10.1007/BF02216922 |
| [3] | N. Avesalon (Grigoraş), Maximum flows in parametric dynamic networks with lower bounds. Ann. Univ. Craiova - Math. Comput. Sci. Ser.43 (2016) 188-199. · Zbl 1413.90047 |
| [4] | N. Avesalon (Grigoraş), E. Ciurea and M. Parpalea, The maximum parametric flow in discrete-time dynamic networks. Fundam. Inform.156 (2017) 125-139. · Zbl 1381.90089 · doi:10.3233/FI-2017-1600 |
| [5] | S. Bunte and N. Kliewer, An overview on vehicle scheduling models. Public Transp.1 (2009) 299-317. · doi:10.1007/s12469-010-0018-5 |
| [6] | X. Cai, D. Sha and C.K. Wong, Time-Varying Network Optimization. Springer (2007). · Zbl 1159.90005 |
| [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. · Zbl 0669.90042 · doi:10.1007/BF01415514 |
| [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.1016/j.trc.2015.05.005 |
| [10] | E. Miller-Hooks and S. Stock Patterson, On solving quickest time problems in time-dependent, dynamic network. J. Math. Model. Algorithms3 (2004) 39-71. · Zbl 1048.90048 · doi:10.1023/B:JMMA.0000026708.57419.6d |
| [11] | E. Nasrabadi and S.M. Hashemi, Minimum cost time-varying network flow problems. Optim. Methods Softw. 25 (2010) 429-447. · Zbl 1189.90018 · doi:10.1080/10556780903239121 |
| [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. Board2459 (2014) 81-90. · doi:10.3141/2459-10 |
| [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. · Zbl 1293.05151 |
| [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. |
| [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. · Zbl 1299.90066 · doi:10.4236/am.2013.410A1002 |
| [17] | M. Parpalea and E. Ciurea, Minimum parametric flow - a partitioning approach. Br. J. Appl. Sci. Technol.13 (2016) 1-8. · doi:10.9734/BJAST/2016/22636 |
| [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:10.1201/b18984-5 |
| [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). · Zbl 0746.90021 |
| [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. · Zbl 1359.90020 · doi:10.1007/978-3-540-76796-1_21 |
| [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:10.1287/trsc.2013.0485 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
