Geodesic
Optimization of location of interconnected facilities on parallel lines with forbidden zones
Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 4, pp. 70-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2021_28_4_a2,
     author = {G. G. Zabudsky and N. S. Veremchuk},
     title = {Optimization of location of interconnected facilities on parallel lines with forbidden zones},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {70--89},
     publisher = {mathdoc},
     volume = {28},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2021_28_4_a2/}
}
TY  - JOUR
AU  - G. G. Zabudsky
AU  - N. S. Veremchuk
TI  - Optimization of location of interconnected facilities on parallel lines with forbidden zones
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2021
SP  - 70
EP  - 89
VL  - 28
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2021_28_4_a2/
LA  - ru
ID  - DA_2021_28_4_a2
ER  - 
%0 Journal Article
%A G. G. Zabudsky
%A N. S. Veremchuk
%T Optimization of location of interconnected facilities on parallel lines with forbidden zones
%J Diskretnyj analiz i issledovanie operacij
%D 2021
%P 70-89
%V 28
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2021_28_4_a2/
%G ru
%F DA_2021_28_4_a2
G. G. Zabudsky; N. S. Veremchuk. Optimization of location of interconnected facilities on parallel lines with forbidden zones. Diskretnyj analiz i issledovanie operacij, Tome 28 (2021) no. 4, pp. 70-89. http://geodesic.mathdoc.fr/item/DA_2021_28_4_a2/

[1] Bischoff M., Klamroth K., “An efficient solution method for Weber problems with barriers based on genetic algorithms”, Eur. J. Oper. Res., 177 (2007), 22–41 | DOI | Zbl

[2] Cabot A. V., Francis R. L., Stary M. A., “A network flow solution to a rectilinear distance facility location problem”, AIIE Trans., 2:2 (1970), 132–141 | DOI

[3] Kuhn H. W., “A note on Fermat's problem”, Math. Program., 4 (1973), 98–107 | DOI | Zbl

[4] McGarvey R. G., Cavalier T. M., “Constrained location of competitive facilities in the plane”, Comput. Oper. Res., 32 (2005), 539–578 | DOI

[5] Picard J. C., Ratliff D. H., “A cut approach to the rectilinear distance facility location problem”, Oper. Res., 26:3 (1978), 422–433 | DOI | Zbl

[6] E. A. Mukhacheva, “A review and prospects of development of combinatorial methods for solution of cutting and packing problems”, Proc. All-Russian Conf. “Discrete Optimization and Operation Research” (Novosibirsk, Russia, June 24–28, 2002), Inst. Mat., Novosibirsk, 2002, 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 (2001), 70–87 (Russian) | Zbl

[8] A. I. Erzin, D. D. Cho, “Concurrent placement and routing in the design of integrated circuits”, Autom. Remote Control, 64:12 (2003), 1988–1999 | DOI | Zbl

[9] G. G. Zabudsky, I. V. Amzin, “Algorithms of compact location for technological equipment on parallel lines”, Sib. Zh. Ind. Mat., 16:3 (2013), 86–94 (Russian) | Zbl

[10] Picard J. C., Queyranne M., “On the one-dimensional space allocation problem”, Oper. Res., 29:2 (1981), 371–391 | DOI | Zbl

[11] Adolphson D., Hu T. C., “Optimal linear ordering”, SIAM J. Appl. Math., 25:3 (1973), 403–423 | DOI | Zbl

[12] Chan A. W., Francis R. L., “Some layout problems on the line with interdistance constraints costs”, Oper. Res., 27:5 (1979), 952–971 | DOI | Zbl

[13] Love R. F., Wong J. Y., “On solving a one-dimensional space allocation problem with integer programming”, INFOR, 14:2 (1976), 139–143 | Zbl

[14] Simmons D. M., “One-dimensional space allocation: an ordering algorithm”, Oper. Res., 17:5 (1969), 812–826 | DOI | Zbl

[15] Ouyang R., Beacher M. R., Ma D., Noor-E-Alam Md., “Navigating concave regions in continuous facility location problems”, Comput. Ind. Eng., 143 (2020), 106385 | DOI

[16] Katz N., Cooper L., “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 (1981), 166–173 | DOI | Zbl

[17] Prakash M. A., Raju K., Raju V. R., “Facility location problems in the presence of two elliptical forbidden regions”, Int. Conf. Mater. Process. Charact., 5:2 (2018), 4000–4007

[18] Prakash M. A., Raju K., Raju V. R., “Facility location in the presence of mixed forbidden regions”, Int. J. Appl. Eng. Res., 13:1 (2018), 91–97

[19] McGarvey R. G., Cavalier T. M., “A global optimal approach to facility location in the presence of forbidden regions”, Comput. Ind. Eng., 45:1 (2003), 1–15 | DOI

[20] Maier A., Hamacher H. W., “Complexity results on planar multifacility location problems with forbidden regions”, Math. Methods Oper. Res., 89 (2019), 433–484 | DOI | Zbl

[21] Nickel S., Puerto J., 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 (2010), 43–66 (Russian) | Zbl

[23] G. G. Zabudsky, N. S. Veremchuk, “An algorithm for approximate solution to the Weber problem on a line with forbidden gaps”, J. Appl. Ind. Math., 10:1 (2016), 136–144 | Zbl

[24] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979 | Zbl

[25] Zabudsky G. G., Veremchuk N. S., “Branch and bound method for the Weber problem with rectangular facilities on lines in the presence of forbidden gaps”, Optimization Problems and Their Applications, Rev. Sel. Pap. 7th Int. Conf. (Omsk, Russia, July 8–14, 2018), Commun. Comput. Inf. Sci., 871, Springer, Cham, 2018, 29–41

[26] Zabudsky G. G., Veremchuk N. S., “About local optimum of the Weber problem on line with forbidden gaps”, Discrete Optimization and Operations Research, Suppl. Proc. 9th Int. Conf. DOOR (Vladivostok, Russia, Sept. 19–23, 2016), CEUR Workshop Proc., 1623, RWTH Aachen Univ., Aachen, 2017, 115–124 (accessed Aug. 2, 2021) http://ceur-ws.org/Vol-1623

[27] G. G. Zabudsky, “On the problem of the linear ordering of vertices of parallel-sequential graphs”, Diskretn. Anal. Issled. Oper., 7:4 (2000), 61–64 (Russian)

[28] Zabudsky G. G., Veremchuk N. S., “On the one-dimensional space allocation problem with partial order and forbidden zones”, Mathematical Optimization Theory and Operations Research, Rev. Sel. Pap. 18th Int. Conf. (Yekaterinburg, Russia, July 8–12, 2019), Commun. Comput. Inf. Sci., 1090, Springer, Cham, 2019, 131–143

[29] Zabudsky G. G., Veremchuk N. S., “About one-dimensional space allocation problem with forbidden zones”, J. Phys. Conf. Ser., 1260:8 (2019), 082006, 8 pp. | DOI

[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., 2005, no. 12, 11–14 (Russian) | Zbl

[31] Zabudsky G. G., Veremchuk N. S., “Multi-facility placement on lines with forbidden zones and routing of communications”, J. Phys. Conf. Ser., 1546 (2020), 012106, 9 pp. | DOI

[32] Zabudsky G. G., Veremchuk N. S., “Numerical research of placement problem on lines with forbidden zones and routing communications”, J. Phys. Conf. Ser., 1791 (2021), 012089, 7 pp. | DOI