Модели и методы группировки объектов для геолого-экономического районирования тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Пономарев, Андрей Васильевич

• Пономарев, Андрей Васильевич
• кандидат технических наук
• 2012

Оглавление диссертации кандидат технических наук Пономарев, Андрей Васильевич

Содержание

Введение

Глава 1. Геолого-экономическое районирование и группировка объектов

1.1. Геолого-экономическое районирование

1.1.1. О задаче геолого-экономического районирования

1.1.2. Элементы экономической оценки минерально-сырьевой базы

1.1.3. Задача формирования промышленно-сырьевых узлов

1.1.4. Модели формирования промышленно-сырьевых узлов

1.2. Задача группировки объектов

1.2.1. О группировке объектов

1.2.2. Кластерный анализ

1.2.3. Группировка в дискретной оптимизации

1.2.4. Известные обобщения задачи группировки

Выводы

Глава 2. Модели централизованной группировки

2.1. Формальная модель задачи группировки

2.1.1. Терминология задачи группировки

2.1.2. Типология задач группировки

2.2. Простейшая задача централизованной группировки

2.2.1. Описание задачи

2.2.2. Постановка задачи математического программирования

2.2.3. Постановка задачи в терминах теории графов

2.2.4. Задача формирования ПСУ как простейшая централизованная группировка

2.3. Задача централизованной группировки со стоимостью активации

2.3.1. Описание задачи

2.3.2. Постановка задачи математического программирования

2.3.3. Задача формирования ПСУ как централизованная группировка со стоимостью активации

2.4. Модификации

2.4.1. Группировка с ресурсными ограничениями

2.4.2. Запреты на одновременное вхождение

2.4.3. Количественные ограничения

2.5. Группировка векторных объектов

Выводы

Глава 3. Методы и алгоритмы решения задачи группировки

3.1. Простейшая задача централизованной группировки

3.1.1. Полная группировка

3.1.2. Полная по С

3.1.3. Полная по S

3.1.4. Неполная

3.2. Задача централизованной группировки со стоимостью активации

3.2.1. Простейшая задача размещения

3.2.2. Анализ задачи

•3.2.3. Подготовка исходных данных для эксперимента

3.2.4. Генетические алгоритмы

3.2.5. Метод локального поиска

3.3. Группировка с линейной стоимостью и бесплатным порогом

3.3.1. Наборы данных для экспериментального исследования методов решения

■3.3.2. Решение с применением CPLEX

3.3.3. Локальный поиск

3.3.4. Метод «Лидер группы»

3.3.5. Вероятностные жадные алгоритмы поиска (GRASP)

Выводы

Глава 4. Практическое решение задачи геолого-экономического районирования

4.1. Библиотека модулей группировки

4.1.1. Модули для решения простейшей задачи группировки

4.1.2. Модули для решения задачи группировки со стоимостью активации

4.2. Решение задачи геолого-экономического районирования для федерального округа

4.2.1. Исходные данные

4.2.2. Результаты

Выводы

Заключение

Литература

Введение диссертации (часть автореферата) на тему «Модели и методы группировки объектов для геолого-экономического районирования»

Введение

Актуальность темы диссертации.

Задача геолого-экономического районирования приобрела актуальность в связи с рассмотрением на государственном уровне перспектив развития политики в области недропользования, суть которых заключается в переходе от лицензирования отдельных объектов недропользования на лицензирование промышленно-сырьевых узлов и геолого-экономических районов, включающих месторождения разных полезных ископаемых. Целью этого перехода является повышение рентабельности освоения минерально-сырьевых ресурсов и полноты их вовлечения в хозяйственный оборот.

В общем случае, задача геолого-экономического районирования является комплексной системной задачей, решаемой экспертами в области экономики недропользования с учетом знаний о разведанных запасах минерально-сырьевых ресурсов, истории и перспективах развития минерально-сырьевого комплекса, данных об инфраструктуре и трудовых ресурсах исследуемого региона. Однако при решении этой задачи эксперту приходится обрабатывать значительные объемы фактической информации, что делает актуальной задачу компьютерной поддержки этого процёсса. Создание программных инструментов важно еще и потому, что способно повысить качество принимаемых экспертом решений, например, за счет обеспечения возможности быстрого анализа альтернативных вариантов районирования.

В то же время, значительное количество задач, возникающих в научной и практической деятельности человека, включая задачи геолого-экономического районирования, имеют в своей основе общую идею: образование групп из заданных объектов при определенных условиях. Многие из этих задач успешно решаются с применением различных методов и моделей теории графов, кластерного анализа, математического программирования. Вместе с тем, почти нет работ, в которых бы предпринимались попытки осознать и описать внутреннее родство таких задач, выделить общие идеи, подходы и методы, которые можно было бы применять последовательно, при решении различных задач группировки объектов.

Цель диссертационной работы и задачи исследования. Цель диссертационной работы состоит в разработке моделей и методов группировки объектов для повышения качества геолого-экономического районирования и снижения затрат на его проведение.

Для достижения поставленных целей были решены следующие задачи:

1) проведен обзор классических оптимизационных задач, связанных с группировкой объектов;

2) исследованы существующие подходы к формированию промышленно-сырьевых узлов, предложена базовая модель формирования промышленно-сырьевых узлов, основанная на принципе максимизации интегрального дохода, и набор ее конкретизации для различных условий применения;

3) проведена классификация видов задачи группировки и для распространенных подклассов задачи группировки сформулированы эквивалентные задачи математического программирования;

4) для ряда разновидностей задачи группировки объектов разработаны новые или адаптированы существующие алгоритмы решения и произведена' оценка эффективности разработанных алгоритмов на синтетических наборах данных;

5) показана связь некоторых видов абстрактных задач группировки с предложенными моделями формирования промышленно-сырьевых узлов;

6) разработанные методы и алгоритмы группировки применены к практической задаче геолого-экономического районирования.

Основные положения, выносимые на защиту:

1. Совокупность математических моделей для решения задачи формирования промышленно-сырьевых узлов, основанных на принципе оптимизации интегрального дохода, получаемого в процессе освоения недр.

2. Методы решения вариантов задачи группировки объектов, возникающих при использовании предлагаемых моделей формирования промышленно-сырьевых узлов.

3. Приближенные алгоритмы решения задачи формирования промышленно-сырьевых узлов.

Научная новизна работы состоит в следующем:

1. Разработан набор оригинальных математических моделей для решения задачи формирования промышленно-сырьевых узлов на основе принципа оптимизации интегрального дохода, учитывающий различные варианты освоенности исследуемой территории и перечня доступных данных, а также позволяющий свести задачу формирования промышленно-сырьевых узлов к задаче целочисленного линейного программирования.

2. Предложена модель абстрактной задачи централизованной группировки, обобщающая задачу формирования промышленно-сырьевых узлов и позволяющая исполь-

зовать разработанные методы и алгоритмы при решении задач централизованной

группировки объектов.

3. Разработан набор приближенных алгоритмов, основанных на применении схемы локального поиска, для решения задачи формирования промышленно-сырьевых узлов с учетом мощности действующих горно-обогатительных предприятий. Применение разработанных алгоритмов позволяет существенно ускорить решение задачи формирования промышленно-сырьевых узлов по сравнению с классическими точными методами решения задач целочисленного программирования.

4. Предложен метод решения задачи формирования промышленно-сырьевых узлов, основанный на сведении данной задачи к задаче поиска базы матроида максимального веса, позволяющий эффективно решать задачу формирования промыптленно-сырье-вых узлов и дающий лицу, принимающему решения, возможность интерактивного анализа чувствительности.

5. Предложен метод учета в задаче формирования промышленно-сырьевых узлов ограничения на разброс значений скалярной характеристики объектов одной группы в виде логических функций, позволяющий сохранить структуру задачи как задачи целочисленного линейного программирования.

Практическая значимость данной диссертационной работы состоит в повышении качества решения задачи геолого-экономического районирования за счет предоставления лицу, принимающему решения, возможности оперативно оценивать варианты районирования, отличающиеся различными модельными допущениями и доступными исходными данными.

Модели и алгоритмы, изложенные в диссертации, могут быть использованы для решения широкого круга задач централизованной группировки объектов произвольной природы.

Реализация результатов работы. Исследования, отраженные в диссертации, поддержаны грантом РФФИ №09-07-00436-а «Онтолого-ориентированное управление гибкими сетевыми организациями» и проектом Президиума РАН №2.13 «Разработка теоретических основ и интеллектуальных моделей для поддержки принятия решений при управлении гибкими сетевыми организациями», 2009-2011.

Апробация полученных в диссертации результатов подтверждена актами об использовании результатов диссертационной работы в процессе обучения студентов в Санкт-Петербургском государственном электротехническом университете «ЛЭТИ» и в научно-

исследовательской работе по государственному контракту №АЛ-04-06/9 «Разработка программно-технологического комплекса, обеспечивающего построение, мониторинг и функционирование ГИС-ориентированной системы для составления геолого-экономических карт федеральных округов России» совместно с Всероссийским научно-исследовательским геологическим институтом (ВСЕГЕИ) им. А.П. Карпинского.

Апробация результатов работы. Основные положения и результаты диссертации представлялись на следующих конференциях: «Информационные технологии в экономике, образовании и бизнесе» (Саратов, 2011), «Наука и техника XXI века» (Новосибирск, 2011), «Наука и современность — 2011» (Новосибирск, 2011), «Проблемы подготовки кадров в сфере инфокоммуникационных технологий» (Санкт-Петербург, 2011), а также на городском семинаре «Информатика и компьютерные технологии» (СПИИРАН, Санкт-Петербург, 2012).

Публикации. Материалы диссертации опубликованы в 8 печатных работах, в том числе в 3 рецензируемых изданиях из списка ВАК.

Структура и объем работы. Диссертация объемом 123 страницы содержит введение, четыре главы, заключение, список литературы (81 наименование), 22 рисунка, 10 таблиц.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Пономарев, Андрей Васильевич

Выводы

В этой главе описан набор программных модулей, предназначенных для решения различных видов задачи группировки. Все модули обладают единым представлением входных и выходных данных и различаются в методах, применяемых для решения задачи. По отношению к применяемым методам, разработанные модули можно разбить на три группы:

Легенда мсо I Центры грут' < Сотелш nt.i : Г в я .41 в группах

ED

Узлы и

О 40 80 120 км

Рис. 4.2. Моносырьевые группы ГПТ «Оловянные» на фрагменте карты. ДВФО

• модули, использующие популярный решатель SCIP (или IBM ILOG CPLEX);

• модули, реализующие специальные алгоритмы (жадный алгоритм, вариант поиска потока максимальной стоимости, метод спуска и т.д.);

• модули, реализующие генетический алгоритм решения (на основе библиотеки GAlib). Созданные модули были использованы для решения задачи геолого-экономического районирования территории Дальневосточного федерального округа. В качестве примера приведены результаты выделения промышленно-сырьевых узлов для двух геолого-промышленных типов месторождений: «Медные» и «Оловянные».

На опробованных наборах данных по ДВФО решение было найдено быстро (в пределах одной секунды для каждого геолого-промышленного типа), а результат на 95%-98% совпал с результатом, полученным независимой группой экспертов в области экономики недропользования.

Заключение

На основе анализа экономических показателей, связанных с формированием: про-мышленно-сырьевых узлов (ПСУ), предложено семейство моделей для решения этой задачи, различающихся способами учета существующей инфраструктуры.

Произведена попытка обобщения задачи формирования ПСУ до абстрактной задачи группировки. По замыслу автора, абстрактная идея группировки должна стать, в первую очередь, методическим базисом, с использованием которого можно было бы классифицировать схожие задачи и выбирать наиболее подходящие методы решения.

В рамках диссертации исследован определенный подкласс задач группировки, а именно, централизованная группировка с различными системами показателей. Показана связь этих задач с известными задачами дискретной оптимизации — нахождением потока минимальной стоимости и простейшей задачей размещения. Для последней предложены и оценены варианты генетических алгоритмов. Для задачи централизованной группировки с линейной стоимостью и бесплатным порогом предложено и экспериментально исследовано несколько приближенных алгоритмов, основанных на методе локального поиска. Средняя погрешность, оцененная в ходе экспериментального исследования, оказалась невысокой (в рамках 5%), что делает целесообразным применение предложенных алгоритмов для приближенного решения данной разновидности задачи группировки.

Разработаны программные модули для решения различных вариантов задачи группировки. Некоторые модули реализуют специальные алгоритмы, другие являются обертками к пакетам решения задач целочисленного и смешанного программирования. В частности, используются универсальные решатели SCIP и CPLEX.

Задача формирования ПСУ представлена в виде задачи группировки и решена, с применением разработанных модулей, на примере данных о месторождениях Дальневосточного федерального округа. Результаты показали высокую степень совпадения с результатами работы независимой группы специалистов в области экономики недропользования.

Список литературы диссертационного исследования кандидат технических наук Пономарев, Андрей Васильевич, 2012 год

Литература

1. Михайлов С. Б. Развитие механизмов регулирования пользования недрами (На примере месторождений Магаданской области): Кандидатская диссертация. 2006.

2. Куклина Е. А. Методологический подход к локализации промышленно-сырьевых узлов как центров формирования горнопромышленных комплексов // Современные проблемы экономики и организации промышленных предприятий / Под ред. Г.А.Краюхин. СПб.: СПГИЭУ, 2007. .V- 4. С. 112-119.

3. Хаустов И., Кимельман С., Беспалов Е., Мочалов П. Геолого-экономические карты Федеральных округов, Субъектов Федерации России и объектов геолого-экономического районирования // ArcReview. 2008. № 4. С. 4-5.

4. Доклад заместителя руководителя Роснедра В. Н. Бавлова «Геолого-экономические

предпосылки развития минерально-сырьевого комплекса России». 15.06.2006. URL: http://www.rosnedra.com/article/601.html.

5. Геологи могут сделать Россию не сырьевым придатком, но сырьевой державой //

Невское время. 21 июня 2006.

6. Куклина Е. А. Природно-промьпнленные комплексы как основа устойчивого развития природно-ресурсных регионов России // Образование, Экономика, Общество. 2007. Т. 4. С. 44-51.

7. Холина В. Н. Основы экономики природопользования: учебник для вузов. СПб.: Питер, 2006.

8. Галицкий В. И., Велесеевич В. И. Менджмент горного производства. Учебное пособие. М.: Изд-во Московского государственного горного университета, 2007.

9. Сергеев И. В. Экономика организации (предприятия). М.: Изд-во «Финансы и статистика», 2006.

10. Лобанов Н. Я. Экономика природопользования при разведке, добыче и обогащении полезных ископаемых. Экономическая оценка минеральных ресурсов: Учебное пособие. СПб.: Санкт-Петербургский государственный горный институт (технический университет), 2009.

11. Бебрис Р. Методологические и методические основы геолого-экономического

районирования ресурсов и потребления минеральных материалов. М.: ВИЭМС, 1973.

12. Душин А. В. Экономическая оценка минеральных ресурсов северного региона: Кандидатская диссертация / Екатеринбург. 2003.

13. Загоруйко Н. Г. Прикладные методы анализа данных и знаний. Новосибирск: Изд-во Ин-та математики, 1999.

14. Александров В. В., Горский Н. Д. Алгоритмы и программы структурного метода обработки данных. Л.: «Наука», 1983.

15. Jain А. К., Murty М. N., Flynn P. J. Data clustering: a review // ACM Computing Surveys. 1999.-September. Vol. 31. Pp. 264-323.

16. Baeza-Yates R. A. Introduction to data structures and algorithms related to information retrieval // Information retrieval. Upper Saddle River, N«J, USA: Prentice-Hall, Inc., 1992. Pp. 13-27.

17. Zhang K. Algorithms for the constrained editing distance between ordered labeled trees and related problems //' Pattern Recognition. 1995. Vol. 28, no. 3. Pp. 463 474.

18. Мандель И. Д. Кластерный анализ. М.: Финансы и статистика, 1988.

19. Журавлев Ю. И., Рязанов В. В., Сенько О. В. «Распознавание»: Математические

методы. Программная система. Практические применения. М.: ФАЗИС, 2006.

20. Рязанов В. В. Комитетный синтез алгоритмов распознавания и классификации /7 Журнал вычислительной математики и математической физики. 1981. Т. 21(6). С. 1533 1543.

21. Рязанов В. В. О синтезе классифицирующих алгоритмов на конечных множествах алгоритмов классификации (таксономии) // Журнал вычислительной математики и

математической физики. 1981. Т. 22(2). С. 429-440.

22. Balas Е., Padberg М. Set partitioning - a survey // SIAM Review. 1976. Vol. 18, no. 4. Pp. 710-760.

23. Garey M. R., Johnson D. S. Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman к Co., 1990.

24. Byun C.-Y. Lower Bounds for Large-Scale Set Partitioning Problems: Tech. Rep. 01-06. Takustr.7, 14195 Berlin: ZIB, 2001.

25. Krarup J., Pruzan P. M. The simple plant location problem: survey and synthesis // European J. Oper. Res. 1983. Vol. 12, no. 1. Pp. 36-81.

26. Еремеев А. В., Заозерская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискретный анализ и исследование операций. Серия 2. 2000. Т. 7, S" 2. С. 22-46.

27. Morales D. R., Romejin Н. Е. The Generalized Assignment Problem and Extensions // Handbook of Combinatorial Optimization. Supplement Volume В / Ed. by D.-Z. Du, P. M. Pardalos. Springer, 2005. Vol. 5. Pp. 259-311.

28. Martello S., Toth P. An algorithm for the generalized assignment problem // Proceedings of the Ninth IFORS Conference. Hamburg, Germany: 1981.

29. Свириденко M. И. Алгоритмы с оценками для дискретных задач размещения: Кандидатская диссертация / Новосибирск. 1998.

30. Korte В., Vygen J. Combinatorial Optimization. Theory and Algorithms / Third Edition. Springer, 2005.

31. Кочетов К). А. Методы локального поиска для дискретных задач размещения: Докторская диссертация / Новосибирск. 2009.

32. Береснев В. Л., Гимади Э. X., Дементьев В. Т. Экстремальные задачи стандартизации. Наука, 1978.

33. Береснев В. Л. Алгоритмы минимизации полиномов от булевых переменных // Проблемы кибернетики. 1979. .V" 36. С. 225-246.

34. Erlenkotter D. A dual-based procedure for imcapacitated facility location // Oper. Res. 1978. Vol. 26. Pp. 992-1009.

35. Beasley J. Lagrangean heuristics for location problems /7 European Journal of Operational Research. 1993. Vol. 65. Pp. 383-399.

36. Hertz A., Taillard E., de Werra D. Tabu search // Local search in combinatorial optimization. Chichester: John Wiley & Sons, 1997. Pp. 121-136.

37. Kochetov Y., Ivanenko D. Computationally difficult instances for the ^incapacitated facility location problem // Metaheuristics: progress as real solvers. Springer, 2005. Pp. 351-367.

38. -Jain K., Mahdian M., Saberi A. A new greedy approach for facility location problems // Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. STOC '02. 2002. Pp. 731-740.

39. Mahdian M., Ye Y., Zhang J. Improved Approximation Algorithms for Metric Facility Location Problems / ,/ In Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization. 2002. Pp. 229-242.

40. Kratica J., Filipovic V., Tosic D. Solving The Uncapacitated Warehouse Location Problem By SGA With Add-Heuristic // In XV ECPD International Conference on Material Handling and Warehousing. 1996. Pp. 3 33.

41. Bhadurv J., Jaramillo J., Bait a R. On the Use of Genetic Algorithms for Location problems // Computers and Operations Research. 2002. Vol. 29. Pp. 761-779.

42. Guner A. R., Sevkli M. A Discrete Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem // Journal of Artificial Evolution and Applications Volume 2008, Article ID 861512, 9 pages. 2008. Vol. 2008. Pp. 10:1-10:9.

43. Amir A., Lindenbaum M. A Generic Grouping Algorithm and its Quantitative Analysis /,/ IEEE Transactions on Pattern Analysis and Machine Intelligence. 1998. Vol. 20. Pp. 168 185.

44. Falkenauer E. A New Representation and Operators for Genetic Algorithms Applied to Grouping Problems // Evolutionary Computation. 1994. Vol. 2(2). Pp. 123-144.

45. Falkenauer E. Genetic Algorithms and Grouping Problems. Wiley, 1998.

46. Falkenauer E. Solving Equal Piles with the Grouping Genetic Algorithm // Proceedings of the 6th International Conference on Genetic Algorithms. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1995. Pp. 492-497.

47. Greene W. A. Genetic algorithms for partitioning sets /7 International Journal on Artificial Intelligence Tools. 2001. Vol. 10. Pp. 225-241.

48. Eiben A., van der Hauw -J., van Hemert J. Graph Coloring with Adaptive Evolutionary Algorithms // Journal of Heuristics. 1998. Vol. 4, no. 1. Pp. 25-46.

49. Erben W. A Grouping Genetic Algorithm for Graph Colouring and Exam Timetabling /7 Proceedings of Practice and Theory of Automated Timetabling PATAT2001. 2001. Pp. 132 156.

50. Баргесян А. А., Куприянов M., Степаненко В. В., Холод И. И. Методы и модели анализа данных: OLAP и Data Mining. БХВ-Петербург, 2004.

51. Аеанов М. О. Дискретная оптимизация: учебное пособие. Екатеринбург: УралНАУКА, 1998.

52. Bertsekas D. Linear Network Optimization: Algorithms and Codes. The MIT Press, 1991.

53. Новиков Ф. А. Дискретная математика для программистов. СПб.: Питер, 2000.

54. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. М: Физматлит, 2003.

55. Панченко Т. В. Генетические алгоритмы, Под ред. Ю. Ю. Тарасевич. Издательский дом «Астраханский университет», 2007.

56. Holland ,J. Н. Adaptation irx Natural and Artificial Systems. Arm Arbor, MI, USA: University of Michigan Press, 1975.

57. Goldberg D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. 1 edition. Addison-Wesley Professional, 1989.

58. Booker L. Improving search in genetic algorithms // Genetic Algorithms and Simulated Annealing. Morgan Kaufmann Publisher, Inc., 1987. Pp. 61-73.

59. Larranaga P., Kuijpers С. M. H., Murga R. H., Yurramendi Y. Learning Bayesian Network Structures by Searching For the Best Ordering With Genetic Algorithms // IEEE Transactions on Systems, Man and Cybernetics. 1996. Vol. 26. Pp. 487-493.

60. Davis L. Applying adaptive algorithms to epistatic domains // Proceedings, International Joint Conference on Artificial Intelligence. 1985.

61. Syswerda G. Schedule optimization using genetic algorithms // A Handbook of Genetic Algorithms / Ed. by L. Davis. New York: Van Nostrand Reinhold, 1991. Pp. 332-349.

62. Goldberg D. E., Lingle R., Jr. Alleles, loci, and the traveling salesman problem // Proceedings of the First International Conference on Genetic Algorithms and Their Applications / Ed. by J. J. Grefenstette. Lawrence Erlbaum Associates, Publishers, 1985.

63. Oliver I. M., Smith D. J., Holland J. R. C. A study of permutation crossover operators

on the TSP /7 Genetic Algorithms and Their Applications: Proceedings of the Second International Conference. 1987. Pp. 224-230.

64. Larranaga P., Kuijpers С. M. H., Murga R. et al. Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators // Artificial Intelligence Review. 1999. Vol. 13. Pp. 129-170.

65. Goldberg D. E., Deb K. A comparative analysis of selection schemes used in genetic algorithms // Foundations of Genetic Algorithms. Morgan Kaufmann, 1991. Pp. 69-93.

66. Рутковская Д., Пилиньский M., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. 2-е изд. изд. М: Горячая линия-Телеком, 2008.

67. Luke S. Essentials of Metaheuristics. Lulu, 2009.

68. Driscoll J. R., Gabow H. N., Shrairman R., Taxjan R. E. Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation /,/ Commun. ACM. 1988. — November. Vol. 31. Pp. 1343-1354.

69. Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms // J. ACM. 1987. July. Vol. 34. Pp. 596 615.

70. Sleator D. D., Tarjan R. E. Self adjusting heaps // SIAM J. Comput. 1986. - February. Vol. 15. Pp. 52-69.

71. Broda! G. S. Worst-case efficient priority queues // Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms. SODA '96. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1996. Pp. 52-58.

72. Таха X. А. Введение в исследование операций. 6-е издание изд. М.: Издательский дом

«Вильяме», 2001.

73. Mittelman Н. Decision tree for optimization software: Benchmarks for optimization software. URL: http: //platо. asu. edu/bench. html.

74. Mateus G., Resende M., Silva R. GRASP with path-relinking for the generalized quadratic

assignment problem: Tech. rep.: AT&T Labs Research, Shannon Laboratory, Florham Park, 2009.

75. Resende M. G. C., Silva R. M. A. GRASP: Greedy Randomized Adaptive Search Procedures: Tech. rep.: AT&T Labs, 2009.

76. Feo T., Resende M. A probabilistic heuristic for a computationally difficult set covering problem /7 Operations Research Letters. 1989. Vol. 8. Pp. 67-71.

77. Achterberg T„ Berthold T., Koch T., Wolter K. Constraint integer programming: a new approach to integrate CP and MIP // Proceedings of the 5th international conference on Integration of AI and OR techniques in constraint programming for combinatorial optimization problems. CPAIOR'08. Berlin, Heidelberg: Springer-Verlag, 2008. Pp. 6-20.

78. Koch T. Rapid Mathematical Programmin: Ph. D. thesis / Technische Universität Berlin. 2004.

79. URL: http: //lancet. mit. edu/ga/.

80. De Jong K. A. An analysis of the behavior of a class of'genetic adaptive systems.: Ph.D. thesis. Ann Arbor, MI, USA: University of Michigan, 1975.

81. Whitley D., Kauth K. GENITOR: A different genetic algorithm // Proceedings of the 1988 Rocky Mountain Conference on Artificial Intelligence. 1988. Pp. 118-130.