Том 28, номер 4, 2021 г., Стр. 70-89
УДК 519.658
Забудский Г. Г., Веремчук Н. С.
Оптимизация размещения взаимосвязанных объектов на параллельных линиях с запрещенными зонами
Аннотация:
Приводится обзор постановок, моделей и методов решения задачи размещения взаимосвязанных прямоугольных объектов на параллельных линиях с запрещёнными зонами. Центры объектов связаны коммуникациями между собой и с зонами. Необходимо разместить объекты вне зон таким образом, чтобы суммарная стоимость связей объектов между собой и с зонами была минимальной. Основное внимание уделяется задаче на линии. Для нескольких линий связи прокладываются через виадук. Построены модели в теоретико-графовой формулировке и формулировке частично-целочисленного программирования с булевыми переменными. Найдены свойства, позволяющие рассматривать задачу как дискретную и декомпозировать её на ряд задач меньшей размерности. Разработаны алгоритмы поиска точного и приближённого решений, выделены полиномиально разрешимые случаи. Приведены результаты численных экспериментов.
Библиогр. 32.
Ключевые слова: дискретная оптимизация, задача размещения, запрещённые зоны.
DOI: 10.33048/daio.2021.28.717
Забудский Геннадий Григорьевич 1
Веремчук Наталья Сергеевна 2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Сибирский государственный автомобильно-дорожный университет,
пр. Мира, 5, 644080 Омск, Россия
е-mail: zabudsky@ofim.oscsbras.ru, n-veremchuk@rambler.ru
Статья поступила 3 июня 2021 г.
После доработки — 2 июля 2021 г.
Принята к публикации 5 июля 2021 г.
Литература
[1] Bischoff M., Klamroth K. An efficient solution method for Weber problems with barriers based on genetic algorithms // Eur. J. Oper. Res. 2007. Vol. 177. P. 22–41.
[2] Cabot A. V., Francis R. L., Stary M. A. A network flow solution to a rectilinear distance facility location problem // AIIE Trans. 1970. Vol. 2, No. 2. P. 132–141.
[3] Kuhn H. W. A note on Fermat’s problem // Math. Program. 1973. Vol. 4. P. 98–107.
[4] McGarvey R. G., Cavalier T. M. Constrained location of competitive facilities in the plane // Comput. Oper. Res. 2005. Vol. 32. P. 539–578.
[5] Picard J. C., Ratliff D. H. A cut approach to the rectilinear distance facility location problem // Oper. Res. 1978. Vol. 26, No. 3. P. 422–433.
[6] Мухачёва Э. А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Мат. междунар. конф. «Дискретный анализ и исследование операций». Новосибирск: Изд-во Ин-та математики, 2002. С. 80–87.
[7] Панюков А. В. Задача размещения прямоугольных объектов с минимальной стоимостью связывающей сети // Дискрет. анализ и исслед. операций. Сер. 2. 2001. Т. 8, № 1. С. 70–87.
[8] Ерзин А. И., Чо Д. Д. Задача одновременного размещения и маршрутизации при проектировании интегральных схем // Автоматика и телемеханика. 2003. № 12. С. 177–190.
[9] Забудский Г. Г., Амзин И. В. Алгоритмы компактного размещения технологического оборудования на параллельных линиях // Сиб. журн. индустр. математики. 2013. Т. 16, № 3. С. 86–94.
[10] Picard J. C., Queyranne M. On the one-dimensional space allocation problem // Oper. Res. 1981. Vol. 29, No. 2. P. 371–391.
[11] Adolphson D., Hu T. C. Optimal linear ordering // SIAM J. Appl. Math. 1973. Vol. 25, No. 3. P. 403–423.
[12] Chan A. W., Francis R. L. Some layout problems on the line with interdistance constraints costs // Oper. Res. 1979. Vol. 27, No. 5. P. 952–971.
[13] Love R. F., Wong J. Y. On solving a one-dimensional space allocation problem with integer programming // INFOR. 1976. Vol. 14, No. 2. P. 139–143.
[14] Simmons D. M. One-dimensional space allocation: an ordering algorithm // Oper. Res. 1969. Vol. 17, No. 5. P. 812–826.
[15] Ouyang R., Beacher M. R., Ma D., Noor-E-Alam Md. Navigating concave regions in continuous facility location problems // Comput. Ind. Eng. 2020. Vol. 143. 106385.
[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. 1981. Vol. 6, No. 2. P. 166–173.
[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. 2018. Vol. 5, No. 2. P. 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. 2018. Vol. 13, No. 1. P. 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. 2003. Vol. 45, No. 1. P. 1–15.
[20] Maier A., Hamacher H. W. Complexity results on planar multifacility location problems with forbidden regions // Math. Methods Oper. Res. 2019. Vol. 89. P. 433–484.
[21] Nickel S., Puerto J. Location theory. A unified approach. Springer, 2009.
[22] Руднев А. С. Алгоритм имитации отжига для решения задач двумерной упаковки в контейнеры с запрещёнными областями // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 4. С. 43–66.
[23] Забудский Г. Г., Веремчук Н. С. Алгоритм приближённого решения задачи Вебера на линии с запрещёнными зонами // Дискрет. анализ и исслед. операций. 2016. Т. 23, № 1. С. 82–96.
[24] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
[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). Cham: Springer, 2018. P. 29–41. (Commun. Comput. Inf. Sci.; Vol. 871).
[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). Aachen: RWTH Aachen Univ., 2017. P. 115–124. (CEUR Workshop Proc.;
Vol. 1623). Available at http://ceur-ws.org/Vol-1623 (accessed Aug. 2, 2021).
[27] Забудский Г. Г. О задаче линейного упорядочения вершин параллельно-последовательных графов // Дискрет. анализ и исслед. операций. 2000. Т. 7, № 1. С. 61–64.
[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). Cham: Springer, 2019. Vol. 1090. P. 131–143. (Commun. Comput. Inf. Sci.; Vol. 1090).
[29] Zabudsky G. G., Veremchuk N. S. About one-dimensional space allocation problem with forbidden zones // J. Phys. Conf. Ser. 2019. Vol. 1260, No. 8. P. 082006:1–082006:8.
[30] Забудский Г. Г. О сложности задачи размещения на линии с ограничениями на минимальные расстояния // Изв. вузов. Математика. 2005. Т. 12. С. 11–14.
[31] Zabudsky G. G., Veremchuk N. S. Multi-facility placement on lines with forbidden zones and routing of communications // J. Phys. Conf. Ser. 2020. Vol. 1546. P. 012106:1–012106:9.
[32] Zabudsky G. G., Veremchuk N. S. Numerical research of placement problem on lines with forbidden zones and routing communications // J. Phys. Conf. Ser. 2021. Vol. 1791. P. 012089:1–012089:7.
