Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 28, No 4, 2021, P. 70-89
UDC 519.658
G. G. Zabudsky and N. S. Veremchuk
Optimization of location of interconnected facilities on parallel lines with forbidden zones
Abstract:
An overview of statements, models and methods for solving location problem of interconnected rectangular facilities on parallel lines with forbidden zones is given. The centers of the facilities are connected by communications with each other and with forbidden zones. It is necessary to place facilities outside the zones in such a way that the total cost of communications facilities to each other and to the zones was minimal. The main focus is on the problem on the line. For several lines communication are through a viaduct. Models of graph–theoretic formulation and partially integer programming with Boolean variables are constructed. Properties are found that allow us to consider the problem as discrete and decompose it into a number of problems of smaller dimension. Algorithms for finding exact and approximate solutions are developed, and polynomial solvable cases are identified. The results of numerical experiments are presented.
Bibliogr. 32.
Keywords: discrete optimization, location problem, forbidden zones.
DOI: 10.33048/daio.2021.28.717
Gennady G. Zabudsky 1
Natalia S. Veremchuk 2
1. Sobolev Institute of Mathematics,
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Siberian State Automobile and Highway University,
5 Mira Avenue, 644080 Omsk, Russia
e-mail: : zabudsky@ofim.oscsbras.ru, n-veremchuk@rambler.ru
Received June 3, 2021
Revised July 2, 2021
Accepted July 5, 2021
References
[1] M. Bischoff, K. Klamroth, An efficient solution method for Weber problems with barriers based on genetic algorithms, Eur. J. Oper. Res. 177, 22–41 (2007).[2] A. V. Cabot, R. L. Francis, and M. A. Stary, A network flow solution to a rectilinear distance facility location problem, AIIE Trans. 2, 132–141 (1970).
[3] H. W. Kuhn, A note on Fermat’s problem, Math. Program. 4, 98–107 (1973).
[4] R. G. McGarvey and T. M. Cavalier, Constrained location of competitive facilities in the plane, Comput. Oper. Res. 32, 539–578 (2005).
[5] J. C. Picard and D. H. Ratliff, A cut approach to the rectilinear distance facility location problem, Oper. Res. 26 (4), 422–433 (1978).
[6] E. A. Mukhacheva, A review and prospects of development of combinatorial methods for solution of cutting and packing problems, in Proc. All-Russian Conf. “Discrete Optimization and Operation Research” Novosibirsk, Russia, June 24—28, 2002 (Inst. Mat., Novosibirsk, 2002), pp. 80–87 [Russian].
[7] A. V. Panyukov, The problem of locating rectangular plants with minimal cost for the connecting network, Diskretn. Anal. Issled. Oper., Ser. 2, 8 (1), 70–87 (2001) [Russian].
[8] A. I. Erzin and D. D. Cho, Concurrent placement and routing in the design of integrated circuits, Avtom. Telemekh., No. 12, 177–190 (2003) [Russian] [Autom. Remote Control, 64 (12), 1988–1999 (2003)].
[9] G. G. Zabudsky and I. V. Amzin, Algorithms of compact location for technological equipment on parallel lines, Sib. Zh. Ind. Mat. 16 (3), 86–94 (2013) [Russian].
[10] J. C. Picard and M. Queyranne, On the one-dimensional space allocation problem, Oper. Res. 29 (2), 371–391 (1981).
[11] D. Adolphson and T. C. Hu, Optimal linear ordering, SIAM J. Appl. Math. 25 (3), 403–423 (1973).
[12] A. W. Chan and R. L. Francis, Some layout problems on the line with interdistance constraints costs, Oper. Res. 27 (5), 952–971 (1979).
[13] R. F. Love and J. Y. Wong, On solving a one-dimentional space allocation problem with integer programming, INFORR 14 (2), 139–143 (1976).
[14] D. M. Simmons, One-dimensional space allocation: An ordering algorithm, Oper. Res. 17 (5), 812–826 (1969).
[15] R. Ouyang, M. R. Beacher, D. Ma, and Md. Noor-E-Alam, Navigating concave regions in continuous facility location problems, Comp. Ind. Eng. 143 106385 (2020).
[16] N. Katz and L. Cooper, Facility location in the presence of forbidden regions, I: Formulation and the case of Euclidean distance with one forbidden circle, Eur. J. Oper. Res. 6 (2), 166–173 (1981).
[17] M. A. Prakash, K. Raju, and V. R. Raju, Facility location problems in the presence of two elliptical forbidden regions, Int. Conf. Mater. Process. Charact. 5 (2), 4000–4007 (2018).
[18] M. A. Prakash, K. Raju, and V. R. Raju, Facility location in the presence of mixed forbidden regions, Int. J. Appl. Eng. Res. 13 (1), 91–97 (2018).
[19] R. G. McGarvey and T. M. Cavalier, A global optimal approach to facility location in the presence of forbidden regions, Comput. Ind. Eng. 45 (1), 1–15 (2003).
[20] A. Maier and Hamacher H. W., Complexity results on planar multifacility location problems with forbidden regions, Math. Methods Oper. Res. 89, 433–484 (2019).
[21] S. Nickel and J. Puerto, Location Theory. A Unified Approach (Springer, Heidelberg, 2009).
[22] A. S. Rudnev, Simulated annealing based algorithm for the rectangular bin packing problem with impurities, Diskretn. Anal. Issled. Oper. 17 (4), 43–66 (2010) [Russian].
[23] G. G. Zabudsky and N. S. Veremchuk, An algorithm for approximate solution to the Weber problem on a line with forbidden gaps, Diskretn. Anal. Issled. Oper. 23 (1), 82–96 (2016) [Russian] [J. Appl. Ind. Math. 10 (1), 136–144 (2016)].
[24] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982 [Russian]).
[25] G. G. Zabudsky and N. S. Veremchuk, Branch and bound method for the Weber problem with rectangular facilities on lines in the presence of forbidden gaps, in Optimization Problems and Their Applications (Rev. Sel. Pap. 7th Int. Conf., Omsk, Russia, July 8–14, 2018) (Springer, Cham, 2018), pp. 29–41 (Commun. Comput. Inf. Sci., Vol. 871).
[26] G. G. Zabudsky and N. S. Veremchuk, About local optimum of the Weber problem on line with forbidden gaps, in Discrete Optimization and Operations Research (Suppl. Proc. 9th Int. Conf. DOOR, Vladivostok, Russia, Sept. 19–23, 2016) (RWTH Aachen Univ., Aachen, 2017), pp. 115–124 (CEUR Workshop Proc., Vol. 1623). Available at http://ceur-ws.org/Vol-1623 (accessed Aug. 2, 2021).
[27] G. G. Zabudsky, On the problem of the linear ordering of vertices of parallel-sequential graphs, Diskretn. Anal. Issled. Oper. 7 (4), 61–64 (2000) [Russian].
[28] G. G. Zabudsky and N. S. Veremchuk, On the one-dimensional space allocation problem with partial order and forbidden zones, in Mathematical Optimization Theory and Operations Research (Rev. Sel. Pap. 18th Int. Conf., Yekaterinburg, Russia, July 8–12, 2019) (Springer, Cham, 2019), pp. 131–143 (Commun. Comput. Inf. Sci., Vol. 1090).
[29] G. G. Zabudsky and N. S. Veremchuk, About one-dimensional space allocation problem with forbidden zones, J. Phys., Conf. Ser. 1260 (8), 082006:1– 082006:8 (2019).
[30] G. G. Zabudsky, On the complexity of the problem of arrangement on a line with constraints on minimum distances, Izv. Vyssh. Uchebn. Zaved. Mat., No. 12, 11–14 (2005) [Russian].
[31] G. G. Zabudsky and N. S. Veremchuk, Multi-facility placement on lines with forbidden zones and routing of communications, J. Phys., Conf. Ser. 1546, 012106:1–012106:9 (2020).
[32] G. G. Zabudsky and N. S. Veremchuk, Numerical research of placement problem on lines with forbidden zones and routing communications, J. Phys., Conf. Ser. 1791, 012089:1–012089:7 (2021).
