Том 27, номер 4, 2020 г., Стр. 80-103

УДК 519.8
Леванова Т. В., Гнусарев А. Ю.
Алгоритмы с чередующимися окрестностями для конкурентной задачи размещения предприятий с гибким спросом

Аннотация:
Рассматривается ситуация на конкурентном рынке, когда новая Компания планирует получить прибыль от открытия своих предприятий, предлагающих товары или услуги. При этом ей необходимо учитывать, что имеется несколько проектов открытия для каждого предприятия, а на рынке уже размещены аналогичные предприятия Конкурента. Кроме того, клиенты сами выбирают места удовлетворения спроса в зависимости от того, где и какие предприятия размещены. Цель Компании — определить места и проекты открытия новых предприятий, чтобы привлечь наибольшую долю всего спроса клиентов. Особый характер спроса приводит к нелинейности целевой функции и дополнительным трудностям отыскания оптимального решения. В работе построены варианты алгоритмов поиска с чередующимися окрестностями, выполнен их экспериментальный анализ с использованием верхних оценок, получены апостериорные оценки точности и проведено обсуждение полученных результатов.
Табл. 4, ил. 2, библиогр. 44.

Ключевые слова: задача размещения предприятий, конкуренция, гибкий спрос, эвристика, поиск с чередующимися окрестностями.

DOI: 10.33048/daio.2020.27.575

Татьяна Валентиновна Леванова ^1,2
Александр Юрьевич Гнусарев ¹
1. Омский филиал Института математики им. С. Л. Соболева,
ул. Певцова, 13, 644099 Омск, Россия
2. Омский гос. университет,
пр. Мира, 55а, 644077 Омск, Россия
е-mail: levanova@ofim.oscsbras.ru, alexander.gnussarev@gmail.com

Статья поступила 17 апреля 2017 г.
После доработки — 7 июня 2020 г.
Принята к публикации 19 июня 2020 г.

Литература

[1] Леванова Т. В., Федоренко А. С. Локальный поиск с чередующимися окрестностями для двустадийной задачи размещения // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 3. С. 43–57.

[2] Discrete location theory. New York: Wiley, 1990. 555 p.

[3] Kochetov Yu. A., Alekseeva E. V., Levanova T. V., Loresh M. A. Large neighborhood local search for the $p$-median problem // Yugoslav J. Oper. Res. 2005. Vol. 15, No. 1. P. 53–63.

[4] Sridharan R. The capacitated plant location problem // Eur. J. Oper. Res. 1995. Vol. 87, No. 1. P. 203–213.

[5] Hotelling H. Stability in competition // Econ. J. 1929. Vol. 39. P. 41–57.

[6] Reilly W. J. The law of retail gravitation. New York: Knickerbocker Press, 1931. 75 p.

[7] Huff D. L. Defining and estimating a trade area // J. Mark. 1964. Vol. 28. P. 34–38.

[8] Huff D. L. A programmed solution for approximating an optimum retail location // Land Econ. 1966. Vol. 42. P. 293–303.

[9] Wilson A. G. Retailers’ profits and consumers’ welfare in a spatial interaction shopping mode // Theory and practice in regional science. London: Pion, 1976. P. 42–59.

[10] Berman O., Krass D. Locating multiple competitive facilities: Spatial interaction models with variable expenditures // Ann. Oper. Res. 2002. Vol. 111. P. 197–225.

[11] Aboolian R., Berman O., Krass D. Competitive facility location model with concave demand // Eur. J. Oper. Res. 2007. Vol. 181, No. 2. P. 598–619.

[12] Aboolian R., Berman O., Krass D. Competitive facility location and design problem // Eur. J. Oper. Res. 2007. Vol. 182, No. 1. P. 40–62.

[13] Drezner T., Drezner Z. Lost demand in a competitive environment // J. Oper. Res. Soc. 2008. Vol. 59. P. 362–371.

[14] Drezner Z., Scott C. H. Optimizing the location of a production firm // Netw. Spat. Econ. 2010. Vol. 10. P. 411–425.

[15] Drezner T., Drezner Z., Zerom D. Competitive facility location with random attractiveness // Oper. Res. Lett. 2018. Vol. 46. P. 312–317.

[16] Küçükaydin H., Necati Aras N., Altinel I. K. A leader–follower game in competitive facility location // Comput. Oper. Res. 2012. Vol. 39, No. 2. P. 437–448.

[17] Levanova T. V., Gnusarev A. Yu. Variable neighborhood search approach for the location and design problem // Discrete Optimization and Operations Research. Proc. 9th Int. Conf. DOOR 2016 (Vladivostok, Russia, Sep. 19–23, 2016). Heidelberg: Springer, 2016. P. 159–170. (Lect. Notes Comput. Sci.; Vol. 9869).

[18] Levanova T. V., Gnusarev A. Yu. Ant colony optimization for competitive facility location problem with elastic demand // Optimization Problems and Their Applications. Proc. School-Seminar OPTA-SCL 2018 (Omsk, Russia, July 8–14, 2018). Aachen: RWTH Aachen Univ., 2018. P. 239–248. (CEUR
Workshop Proc.; Vol. 2098). Available at http://ceur-ws.org/Vol-2098 (accessed July 2, 2020).

[19] Levanova T. V., Gnusarev A. Yu. Development of threshold algorithms for a location problem with elastic demand // Large-Scale Scientific Computing. Rev. Sel. Pap. 11th Int. Conf. LSSC 2017 (Sozopol, Bulgaria, June 5–9, 2017). Cham: Springer, 2017. P. 382–389. (Lect. Notes Comput. Sci.; Vol. 10665).

[20] Levanova T. V., Gnusarev A. Yu. Simulated annealing for competitive $p$-median facility location problem // J. Phys. Conf. Ser. 2018. Vol. 1050. P. 012044.1–5. Available at https://iopscience.iop.org/article/10.1088/1742-6596/1050/1/012044/pdf (accessed July 2, 2020).

[21] Levanova T. V., Gnusarev A. Yu. Development of ant colony optimization algorithm for competitive $p$-median facility location problem with elastic demand // Mathematical Optimization Theory and Operations Research. Rev. Sel. Pap. 18th Int. Conf. MOTOR 2019 (Ekaterinburg, Russia, July 8–12, 2019). Cham: Springer, 2019. P. 68–78. (Commun. Comput. Inf. Sci.; Vol. 1090).

[22] McGarvey R. G., Cavalier T. M. Determining the location and capacity of competitive facilities // Int. J. Math. Oper. Res. 2010. Vol. 2, No. 6. P. 694–723.

[23] Perl J., Ho P. Public facilities location under elastic demand // Transp. Sci. 1990. Vol. 24, No. 2. P. 117–136.

[24] Pahlavani A., Saidi-Mehrabad M. A competitive facility location model with elastic demand and patronising behaviour sensitive to location, price and waiting time // Int. J. Logist. Syst. Manage. 2011. Vol. 10, No. 3. P. 293–312.

[25] Wang X. Location and design decisions of facilities in a distribution system with elastic customer demand // J. Shanghai Jiaotong Univ. (Sci.). 2009. Vol. 14, No. 5. P. 606–612.

[26] Ashtiani M. G. Competitive location: A state-of-art review // Int. J. Ind. Eng. Comput. 2016. Vol. 7. P. 1–18.

[27] Berman O., Drezner T., Drezner Z., Krass D. Modeling competitive facility location problems: New approaches and results // Decision Technologies and Applications. Catonsville: Inst. Oper. Res. Manage. Sci., 2009. P. 156–181. (INFORMS Tutor. Oper. Res.).

[28] Drezner T. Gravity models in competitive facility location // Contributions to Location Analysis. Cham: Springer, 2019. P. 253–275. (Int. Ser. Oper. Res. Manage. Sci.; Vol. 281).

[29] Eiselt H. A., Marianov V., Drezner T. Competitive location models // Location Science. Cham: Springer, 2015. P. 365–398.

[30] Karakitsiou A. Modeling discrete competitive facility location. Cham: Springer, 2015. 54 p.

[31] Kress D., Pesch E. Sequential competitive location on networks // Eur. J. Oper. Res. 2012. Vol. 217, No. 3. P. 483–499.

[32] Бахтин А. Е., Колоколов А. А., Коробкова З. В. Дискретные задачи производственно-транспортного типа. Новосибирск: Наука, 1978. 160 с.

[33] Aboolian R., Berman O., Krass D. Capturing market share: Facility location and design problem // Мат. Междунар. конф. «Дискретная оптимизация и исследование операций» (Новосибирск, Россия, 24–28 июня 2013 г.). Новосибирск: Изд-во Ин-та математики, 2013. C. 7–11.

[34] Nicholson T. A. J. A sequential method for discrete optimization problems and its application to the assignment, traveling salesman and tree scheduling problems // J. Inst. Math. Appl. 1965. Vol. 13. P. 362–375.

[35] Кочетов Ю. А., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет. анализ и исслед. операций. Сер. 2. 2003. Т. 10, № 1. С. 11–43.

[36] Hansen P., Mladenovic N. Variable neighborhood search: Principles and applications // Eur. J. Oper. Res. 2001. Vol. 130, No. 3. P. 449–467.

[37] Anokic A., Stanimirovic Z., Davidovic T., Stakic Ð. Variable neighborhood search based approaches to a vehicle scheduling problem in agriculture // Int. Trans. Oper. Res. 2020. Vol. 27, No. 1. P. 26–56.

[38] Handbook of metaheuristics. New York: Springer, 2010. 648 p. (Int. Ser. Oper. Res. Manage. Sci.; Vol. 146).

[39] Кононова П. А., Кочетов Ю. А. Локальный поиск с чередующимися окрестностями для задачи Джонсона с пассивным буфером // Дискрет. анализ и исслед. операций. 2012. Т. 19, № 5. С. 63–82.

[40] Pei J., Mladenovic N., Uroševic D., Brimberg J., Liu X. Solving the traveling repairman problem with profits: A novel variable neighborhood search approach // Inf. Sci. 2020. Vol. 507. P. 108–123.

[41] Dréo J., Pétrowski A., Siarry P., Taillard E. Metaheuristics for hard optimization. Heidelberg: Springer, 2006. 369 p.

[42] Леванова Т. В., Белан С. Е. Применение верхних оценок для анализа алгоритмов приближённого решения конкурентной задачи размещения с гибким спросом // Вестн. Омск. гос. ун-та. 2017. № 4. С. 4–10.

[43] The general algebraic modeling system. Fairfax: GAMS Development, 2020. Available at http://www.gams.com (accessed July 2, 2020).

[44] LocalSolver. Paris: LocalSolver, 2020. Available at http://www.localsolver.com (accessed July 2, 2020).