ALGORITHMS OF TERRITORIAL SEGMENTATION FOR FACILITY NETWORK WITH OVERLAPPING SERVICE ZONES
DOI:
https://doi.org/10.32782/IT/2023-2-2Keywords:
territorial zoning, optimal multiplex partitioning of sets, continuous model, facility location, redistributing, non-differentiable optimization.Abstract
We consider the problems of territorial segmentation of a given region into service areas for facilities. The optimization criterion is the distance to the k closest centers. When modelling, we consider the following: the centers themselves can be functioning or newly created and located in the most favorable places; they can have limited options. The paper presents a statement and a numerical algorithm for solving a continuous linear problem of optimal multiplex partitioning of bounded sets under constraints. It is a mathematical model of the optimal location of service centers with simultaneous territorial segmentation into their service areas. We demonstrate the work of this algorithm and its cases: for a fixed set of centers, with finding their optimal location on a given set, with the placement of several additional centers and redistribution of service spheres for an updated service network.
References
Коряшкіна Л.С. Розширення одного класу нескінченновимірних оптимізаційних задач. Вісн. Черкаського ун-ту. Сер. Прикл. матем. Інф. 2015. № 18(351). С. 28–36.
Kiseleva E., Koriashkina L. Theory of Continuous Optimal Set Partitioning Problems as a Universal Mathematical Formalism for Constructing Voronoi Diagrams and Their Generalizations. I. Theoretical Foundations. Cybernetics and Systems Analysis. 2015. Vol. 51. Issue 3. Р. 325–335. 3. Boots B., South R. Modeling retail trade areas usinghigher-order, multiplicatively weighted Voronoi diagrams. Journal of Retailing 73. 1997. P. 519–536.
Koriashkina L.S., Cherevatenko А.Р. Continuous problems of optimal multiplex-partitioning of sets without constraints and solving methods. Journal of Computational & Applied Mathematics. 2015. № 2 (119). P. 15–32
Sahin G., Sural H. A review of hierarchical facility location models. Comput. Oper. Res. 2007. Vol. 34. P. 2310–2331.
Mallozzi L., Puerto J., Rodríguez-Madrena M. On Location-Allocation Problems for Dimensional Facilities. Journal of Optimization Theory and Applications. 2018. P. 1–38.
Torkestani S.S., Seyedhosseini S.M., Makui A. Hierarchical Facility Location and Hub Network Problems: A literature review. J. Ind. Syst. Eng. 2016. Vol. 9. P. 1–22.
Lin Y., Jia H., Yang Y., Tian G., Tao F., Ling L. An improved artificial bee colony for facility location allocation problem of end-of-life vehicles recovery network. J. Clean. Prod. 2018. Vol. 205. P. 134–144.
Chen L., Zhang W., Ma J., Wang L. Newly-added Station Location-allocation in One-way Station-based Carsharing Systems. In Proceedings of the 2019 Chinese Control Conference (CCC), Guangzhou, China, 27–30 July 2019. Vol. 2019.
Wang X, Lim M, Ouyang Y. A Continuum Approximation Approach to the Dynamic Facility Location Problem in a Growing Market. Transportation Science. 2018. 51:1. P. 343–357.
Lage M.d.O., Machado C.A.S., Monteiro C.M., Davis C.A. Jr., Yamamura C.L.K., Berssaneti F.T., Quintanilha J.A. Using Hierarchical Facility Location, Single Facility Approach, and GIS in Carsharing Services. Sustainability. 2021. 13, 12704. https://doi.org/10.3390/su132212704
Murray A.T., Church R.L., Feng X. Single facility siting involving allocation decisions. Eur. J. Oper. Res. 2020. Vol. 284. P. 834–846.
Monteiro C.M., Machado C.A.S., Lage M.O., Berssaneti F.T., Davis C.A., Quintanilha J.A. Optimization of carsharing fleet size to maximize the number of clients served. Comput. Environ. Urban Syst. 2021. Vol. 87. 101623.
Murray A.T., Xu J., Wang Z., Church R.L. Commercial GIS location analytics: Capabilities and performance. Int. J. Geogr. Inf. Sci. 2019. Vol. 33. P. 1106–1130.
Itai Feigenbaum, Jay Sethuraman, Chun Ye. Approximately optimal mechanisms for strategyproof facility location: Minimizing Lp norm of costs. Mathematics of Operations Research. 2017. Vol. 42 (2). P. 434–447,
Karatas M. A multi-objective facility location problem in the presence of variable gradual coverage performance and cooperative cover. Eur. J. Oper. Res. 2017. V. 262. P. 1040–1051.
Karatas M., Dasci A. A two-level facility location and sizing problem for maximal coverage. Comput. Ind. Eng. 2020. Vol. 139. 106204.
Rodriguez S.A., De la Fuente R.A., Aguayo M.M. A facility location and equipment emplacement technique model with expected coverage for the location of fire stations in the Concepción province, Chile. Comput. Ind. Eng. 2020. Vol. 147, 106522.
Zheng C., Zhao X., Shen J. Research on Location Optimization of Metro-Based Underground Logistics System with Voronoi diagram. IEEE Access 2020. Vol. 8. P. 34407–34417.
Kiseleva E., Koriashkina L. The Theory of Continuous Optimal Set Partitioning Problems as a Universal Mathematical Formalism for Constructing the Voronoi Diagram and its Generalizations. ІI. Algorithms for constructing Voronoi Diagrams based on the theory of optimal partitioning of sets. Cybernetics and Systems Analysis. 2015. Vol. 51, Issue 4. Р. 3–12.
Gemsa A., Lee D., Liu C.H., Wagner D. Higher Order City Voronoi Diagrams. Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’12). Helsinki, 2012. (Lecture Notes in Computer Science; Vol. 7357). P. 59–70.
Коряшкина Л.С., Череватенко А.П. Оптимальные диаграммы Вороного высших порядков ограниченных множеств и алгоритмы их построения. Вісник Черкаського університету. Серія Прикладна математика. Інформатика. 2016. №. 1-2. С. 59–76.
Mallozzi L., Justo P. The geometry of optimal partitions in location problems. Optimization Letters 12. 2018. P. 203-220.
Lynskey J., Thar K., Oo T.Z., Hong C.S. Facility Location Problem Approach for Distributed Drones. Symmetry. 2019. 11. 118. https://doi.org/10.3390/sym11010118
Wolf Gert W. Solving location-allocation problems with professional optimization software. Transactions in GIS 26. 2022. P. 2741–2775.
Alghanmi Nusaybah, Alotaibi Reem, Alshammari Sultanah, Alhothali Areej, Bamasag Omaimah, Faisal Kamil. A Survey of Location-Allocation of Points of Dispensing During Public Health Emergencies Front. Public Health, 10 March 2022 Sec. Disaster and Emergency Medicine. 2022. Vol. 10. https://doi.org/10.3389/fpubh.2022.811858
Lebedeva O., Kripak M., Gozbenko V. Increasing effectiveness of the transportation network by using the automation of a Voronoi diagram. Transp. Res. Procedia. 2018. Vol. 36. P. 427–433.
Коряшкіна Л.С., Череватенко А.П., Коряшкіна Е.О. Інтеграція ГІС-технологій і методів розв’язання неперервних задач оптимального мультиплексного розбиття множин. Системні дослідження та інформаційні технології. 2017. № 4. С. 97–108.
Koriashkina L., Cherevatenko A., Mykhalova O. The continuous problems of the optimal multiplex partitioning an application of sets. Power Engineering and Information Technologies in Technical Objects Control. Annual Proceedings. 2016. P. 233–240.
Шор Н. З., Бардадым Т. А., Журбенко Н. Г., Лиховид А. П., Стецюк П. И. Использование методов негладкой оптимизации в задачах стохастического программирования. Кибернетика и системный анализ. 1999. № 5. С. 33−47.
