Том 22, номер 3, 2015 г., Стр. 36–54
УДК 519.87+519.854
Кочетов Ю. А., Панин А. А., Плясунов А. В.
Сравнение метаэвристик для решения двухуровневой задачи размещения предприятий и фабричного ценообразования
Аннотация:
Показано, что исследуемая задача принадлежит классу Poly-APX. Для её решения разработаны приближённые алгоритмы, использующие генетический локальный поиск и VND-метаэвристику. Приводятся результаты вычислительных экспериментов на исходных данных из библиотеки тестовых задач «Дискретные задачи размещения». Предлагаемые алгоритмы сравниваются с ранее известными приближёнными алгоритмами и точным методом из библиотеки CPLEX. Результаты экспериментов свидетельствуют о высокой эффективности разработанных методов и возможности решать задачи большой размерности.
Табл. 2, библиогр. 30.
Ключевые слова: двухуровневая задача, размещение, ценообразование, локальное улучшение с чередующимися окрестностями, генетический локальный поиск, двухуровневая метаэвристика.
DOI: 10.17377/daio.2015.22.480
Кочетов Юрий Андреевич 1,2
Панин Артем Александрович 1
Плясунов Александр Владимирович 1,2
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: jkochet@math.nsc.ru, arteam1897@gmail.com, apljas@math.nsc.ru
Статья поступила 14 марта 2015 г.
Исправленный вариант — 6 апреля 2015 г.
Литература
[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
[2] Давыдов И. А., Кочетов Ю. А., Младенович Н., Уросевич Д. Быстрые метаэвристики для дискретной задачи о (r|p)-центроиде // Автоматика и телемеханика. 2014. Вып. 4. С. 677–687.
[3] Дементьев В. Т., Шамардин Ю. В. Задача о выборе цен на продукцию при условии обязательного удовлетворения спроса // Дискрет. анализ и исслед. операций. Сер. 2. 2002. Т. 9, № 2. С. 31–40.
[4] Кочетов Ю. А., Плясунов А. В. Полиномиально разрешимый класс задач двухуровневого линейного программирования // Дискрет. анализ и исслед. операций. Cер. 2. 1997. T. 1, № 2. С. 23–33.
[5] Кочетов Ю. А., Плясунов A. В. Генетический локальный поиск для задачи о размещении графа на доли ограниченной мощности // Журн. вычисл. математики и мат. физики. 2012. Т. 52, №1. С. 157–167.
[6] Панин А. А., Плясунов А. В. О сложности двухуровневых задач размещения и ценообразования // Дискрет. анализ и исслед. операций. 2014. T. 21, № 5. С. 54–66.
[7] Плясунов А. В., Панин А. А. Задача ценообразования. Ч. 1: Точные и приближённые алгоритмы решения // Дискрет. анализ и исслед. операций. 2012. Т. 9, № 2. С. 31–40.
[8] Aboolian R., Berman O., Krass D. Competitive facility location model with concave demand // Eur. J. Oper. Res. 2007. Vol. 181. P. 598–619.
[9] Aboolian R., Berman O., Krass D. Optimizing pricing and location decisions for competitive service facilities charging uniform price // J. Oper. Res. Soc. 2008. Vol. 59. P. 1506–1519.
[10] Adler N., Smilowitz K. Hub-and-spoke network alliances and mergers: price-location competition in the airline industry // Transp. Res. Part B. 2007. Vol. 41. P. 394–409.
[11] Attallah M. Algorithms and theory of computation handbook. Boca Raton: CRC Press LLC, 1998. 1312 p.
[12] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M. Complexity and approximation: combinatorial optimization problems and their aproximability properties. Berlin: Springer-Verl., 1999. 524 p.
[13] Bouhtou M., Grigoriev A., Van Der Kraaij A. F., Van Hoesel S., Spieksma F., Uetz M. Pricing bridges to cross a river // Nav. Res. Logist. 2007. Vol. 54, No. 4. P. 411–420.
[14] Dasci A., Laporte G. Location and pricing decisions of a multistore monopoly in a spatial market // J. Region Sci. 2004. Vol. 44. P. 489–515.
[15] Dempe S. Foundations of bilevel programming. Dordrecht: Kluwer Acad. Publ., 2002. 320 p.
[16] Diakova Z., Kochetov Yu. A double VNS heuristic for the facility location and pricing problem // Electron. Notes Discrete Math. 2012. Vol. 39. P. 29–34.
[17] Drezner Z. Facility location: A survey of applications and methods. New York: Springer-Verl., 1995. 572 p.
[18] Drezner T., Eiselt H. A. Consumers in competitive location models // Facility location: Applications and theory. Berlin: Springer-Verl., 2004. P. 151–178.
[19] Eiselt H. A., Laporte G., Thisse J.-F. Competitive location models: A framework and bibliography // Transp. Sci. 1993. Vol. 27, No. 1. P. 44–54.
[20] Eiselt H. A., Marianov V. Foundations of location analysis. New York: Springer-Verl., 2011. 510 p. (Int. Ser. Oper. Res. Manag. Sci.; Vol. 155).
[21] Grigoriev A., van Loon J., Sviridenko M., Uetz M., Vredeveld T. Optimal bundle pricing with monotonicity constraint // Oper. Res. Lett. 2008. Vol. 36, No. 5. P. 609–614.
[22] Hanjoul P., Hansen P., Peeters D., Thisse J.-F. Uncapacitated plant location under alternative spatial price policies // Manage Sci. 1990. Vol. 36, No. 1. P. 41–57.
[23] Hansen P., Mladenovic N. Variable neighborhood search // Eur. J. Oper. Res. 2001. Vol. 130, No. 3. P. 449–467.
[24] Hotelling H. Stability in competition // Econom. J. 1929. Vol. 39, No. 153. P. 41–57.
[25] Kochetov Yu., Alekseeva E., Levanova T., Loresh M. Large neighborhood local search for the p-median problem // Yugosl. J. Oper. Res. 2005. Vol. 15, No. 1. P. 53–63.
[26] Lederes Ph. J., Thisse J.-F. Competitive location on network under delivered pricing // Oper. Res. Lett. 1990. Vol. 9, No. 3. P. 147–154.
[27] Leggett E. W., Moore D. J. Optimization problems and the polynomial hierarchy // Theor. Comput. Sci. 1981. Vol. 15, No. 3. P. 279–289.
[28] Marianov V., Lüer-Villagra A. A competitive hub location and pricing problem // Eur. J. Oper. Res. 2013. Vol. 231, No. 3. P. 734–744.
[29] Serra D., ReVelle Ch. Competitive location and pricing on networks // Geograph. Anal. 1999. Vol. 31, No. 2. P. 109–129.
[30] Vives X. Oligopoly pricing: old ideas and new tools. Cambridge, MA: MIT Press, 2001. 441 p.
