Maximum Flow Location (FlowLoc) Modeling without Size Restrictions on Facilities
DOI:
https://doi.org/10.3126/jist.v30i1.74913Keywords:
Dynamic FlowLoc, Heuristics, Network flow, Static FlowLocAbstract
There are situations when traffic flow is obstructed because of facility placement in the road segments. FlowLoc models deal with such a situation in which a set of facilities with given sizes (capacities) has to be allocated with a given set of arcs of a directed network. The existing models assume that the size of each facility does not exceed the capacity of each of the arc in the given set of arcs and that the number of given facilities does not exceed the total number of available locations on arcs. In this work, we extend the FlowLoc modeling in which facilities can have arbitrary sizes and can have arbitrary numbers. We construct mixed-integer programming models based on static and dynamic network flow modeling. Realizing NP-hardness of problems, we design polynomial time heuristic algorithms to solve the constructed models. The performance of the algorithms is tested in a road network of Bhaktapur city Nepal.
Downloads
References
Ahuja, R.K., Magnanti, T.L., & Orlin, J.B. (1993). Network flows: theory, algorithms, and applications. Prentice hall.
Akter, S., & Wamba, S.F. (2019). Big data and disaster management: a systematic review and agenda for future research. Annals of Operations Research, 283(1-2), 939–959.
Balakrishnan, A., Ward, J.E., & Wong, R.T. (1987). Integrated facility location and vehicle routing models: Recent work and future prospects. American Journal of Mathematical and Management Sciences, 7(1-2), 35–61.
Berge, C. (1957). Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 43(9), 842.
Bhandari, P.P., Khadka, S.R., Ruzika, S., & Schäfer, L.E. (2020). Lexicographically maximum dynamic flow with vertex capacities. Journal of Mathematics and Statistics, 16(1), 142–147.
Boeing, G. (2024). Modeling and analyzing urban networks and amenities with osmnx [Working paper]. Retrieved January 14, 2025 from https:// geoffboeing.com/publications/ osmnx-paper/
Cova, T.J., & Johnson, J.P. (2003). A network flow model for lane-based evacuation routing. Transportation Research Part A: Policy and Practice, 37(7), 579–604.
Dhamala, T.N., Adhikari, M.C., Khanal, D.P., & Pyakurel, U. (2024). Generalized maximum flow over time with intermediate storage. Annals of Operations Research, 335(1), 111–134.
Dhamala, T.N., Pyakurel, U., & Dempe, S. (2018). A critical survey on the net work optimization algorithms for evacuation planning problems. International Journal of Operations Research, 15(3), 101–133.
Dhamala, T.N., Wagle, S., & Pyakurel, U. (2023). Flowloc problems with maximum excess flow. Journal of Industrial and Management Optimization, 19(12), 8851–8870.
Ford, L.R., & Fulkerson, D.R. (1962). Flows in networks. New Jersey: Princeton University Press.
Goldberg, A.V., & Tarjan, R.E. (1989). Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM (JACM), 36(4), 873–886.
Hakimi, S.L. (1965). Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations Research, 13(3), 462–475.
Hamacher, H.W., Heller, S., & Rupp, B. (2013). Flow location (FlowLoc) problems: dynamic network flow and location models for evacuation planning. Annals of Operations Research, 207(1), 161–180.
Hamacher, H.W., & Tjandra, S.A. (2001). Mathematical modelling of evacuation problems: A state of art. Fraunhofer-Institut für Techno-und Wirtschaftsmathematik, Fraunhofer (ITWM).
Heßler, P., & Hamacher, H.W. (2016). Sink location to find optimal shelters in evacuation planning. EURO Journal on Computational Optimization, 4(3-4), 325–347.
Huangfu, Q., & Hall, J.J. (2018). Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1), 119–142.
Kim, S., Shekhar, S., & Min, M. (2008). Contraflow transportation network reconfiguration for evacuation route planning. IEEE Transactions on Knowledge and Data Engineering, 20(8), 1115–1129.
Köhler, E., Langkau, K., & Skutella, M. (2002). Time-expanded graphs for flow dependent transit times. In European symposium on algorithms (pp. 599–611).
Kotsireas, I.S., Nagurney, A., & Pardalos, P.M. (2015). Dynamics of disasters-key concepts, models, algorithms, and insights. Springer Proceedings in Mathematics and Statistics.
Kuby, M.J. (1987). Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems. Geographical Analysis, 19(4), 315–329.
Laporte, G., Nickel, S., & Saldanha-da-Gama, F. (Eds.). (2019). Location science. Switzerland: Springer.
Nath, H.N., Dempe, S., & Dhamala, T.N. (2021). A bicriteria approach for saving a path maximizing dynamic contraflow. Asia-Pacific Journal of Operational Research, 39(3), 2150027.
Nath, H.N., & Dhamala, T.N. (2018). Network flow approach for locating optimal sink in evacuation planning. International Journal of Operations Research, 15(4), 175–185.
Nath, H.N., Dhamala, T.N., & Dempe, S. (2024). Saving a path minimizing egress time of a dynamic contraflow: a bi-objective programming approach. OPSEARCH, 61(1), 98–120.
Nath, H.N., Pyakurel, U., Dhamala, T.N., & Dempe, S. (2021). Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 17(5), 2925–2941.
Orlin, J.B. (2013). Max flows in O(nm) time, or better. In Proceedings of the forty-fifth annual acm symposium on theory of computing (pp. 765–774).
Pyakurel, U., & Dempe, S. (2019). Network flow with intermediate storage: Models and algorithms. Preprint, TU Bergakademie, Freiberg.
Pyakurel, U., & Dempe, S. (2020). Network flow with intermediate storage: models and algorithms. SN Operations Research Forum, 1, 37.
Pyakurel, U., & Dhamala, T.N. (2017). Continuous dynamic contraflow approach for evacuation planning. Annals of Operations Research, 253(1), 573–598.
Pyakurel, U., Nath, H.N., & Dhamala, T.N. (2018). Efficient contraflow algorithms for quickest evacuation planning. Science China Mathematics, 61(11), 2079–2100.
Rebennack, S., Arulselvan, A., Elefteriadou, L., & Pardalos, P.M. (2010). Complexity analysis for maximum flow problems with arc reversals. Journal of Combinatorial Optimization, 19(2), 200–216.
Skutella, M. (2009). An introduction to network flows over time. In Cook, W., Lovász, L., & Vygen, J. (Eds.), Research trends in combinatorial optimization (pp. 451-482). Springer.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Institute of Science and Technology, T.U.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The views and interpretations in this journal are those of the author(s). They are not attributable to the Institute of Science and Technology, T.U. and do not imply the expression of any opinion concerning the legal status of any country, territory, city, area of its authorities, or concerning the delimitation of its frontiers of boundaries.
The copyright of the articles is held by the Institute of Science and Technology, T.U.
