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

• Косарев, Николай Александрович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Косарев, Николай Александрович

Введение.

1 Задачи оптимального размещения предприятий и методы их решения.

1.1 Постановки задач 1.2 Вычислительная сложность и методы решения

1.3 Схема декомпозиции Бендерса.

2 Исследование декомпозиционных алгоритмов

2.1 Декомпозиционные алгоритмы решения задачи о р-медиане.

2.2 Оценки числа итераций для алгоритмов с отсечениями Бендерса

2.3 Анализ некоторых релаксационных алгоритмов целочисленного программирования.

2.4 Вопросы устойчивости декомпозиционных алгоритмов

3 Разработка алгоритмов и их экспериментальное исследование.

3.1 Алгоритмы поиска "перспективных" производственных планов.

3.2 Оптимизация выбора значений двойственных оценок при построении отсечений Бендерса.

3.3 Гибридный алгоритм для решения задачи о р-медиане на максимум.

3.4 Результаты вычислительного эксперимента.

Введение диссертации (часть автореферата) на тему «Разработка и анализ декомпозиционных алгоритмов для задач оптимального размещения предприятий»

Задачи оптимального размещения предприятий имеют широкий круг приложений, возникающих при планировании и реконструкции производства, проектировании сетей обслуживания, в стандартизации, кластерном анализе и других областях [3,4,10,15,50,51,84]. Значительный интерес к таким задачам связан также со сложностью многих из них. Поэтому для исследования и решения рассматриваемых задач требуется применение методов системного анализа и оптимизации.

В настоящее время исследования задач размещения предприятий ведутся в следующих основных направлениях. Анализируется структура и вычислительная сложность задач, выделяются полиномиально разрешимые случаи и семейства трудных задач, разрабатываются и изучаются методы решения [16,22,26,34,91]. Интенсивно развивается область, связанная с эволюционными алгоритмами, алгоритмами муравьиной колонии и другими метаэвристиками [29,52, 62]. Большое внимание уделяется простейшей задаче размещения (ПЗР) [28,46,51,54], задаче о р-медиане [29,40,44,49,80,93], задачам с ограничениями на объемы производства [27], динамическим задачам размещения предприятий [4,37]. В работах [3,10] и других исследуются многопродуктовые и многоуровневые задачи размещения.

В общих чертах многие задачи оптимального размещения предприятий могут быть сформулированы следующим образом. Даны пункты возможного размещения предприятий и множество клиентов, которые должны быть ими обслужены. Требуется открыть предприятия в некоторых из указанных пунктов, прикрепить к ним клиентов и выполнить обслуживание таким образом, чтобы полученное решение было оптимальным в определенном смысле. Под обслуживанием может пониматься, например, транспортировка продукции от поставщиков к ее потребителям. Задачи различаются между собой имеющимися ограничениями, в частности, возможностями предприятий по обслуживанию клиентов, числом открываемых предприятий, затратами на их открытие, и т.п. Многие из рассматриваемых задач являются АГР-трудными [1,9,67].

Для исследования и решения задач оптимального размещения предприятий широко используется аппарат целочисленного линейного программирования (ЦЛП) [4,44,51,54]. Значительная часть известных точных алгоритмов решения основаны на методе ветвей и границ и различных схемах перебора допустимых решений [40,49]. Часто при этом исходная задача сводится к последовательности более простых, которые могут быть решены методами непрерывной оптимизации. Для построения оценок значений целевой функции используется решение соответствующей задачи линейного программирования (ЛП) или двойственной к ней задачи. С целыо исключения просмотренных и "неперспективных" решений применяются отсечения. В частности, достаточно эффективными оказались фасетные неравенства, порождаемые выпуклой оболочкой множества целочисленных решений [55].

Во многих задачах размещения предприятий, в том числе в задачах о р-медиане и ПЗР, переменные соответствующей модели ЦЛП естественным образом делятся на две группы: целочисленные и непрерывные. Ввиду этого для их решения применяются декомпозиционные алгоритмы с отсечениями Бендерса [3,22,51], в которых решение исходной задачи размещения сводится к анализу и решению последовательности производственных (целочисленных) и транспортных (непрерывных) подзадач.

Для построения производственных подзадач используются дополнительные неравенства (отсечения Бендерса).

Основное направление исследований метода Бендерса - разработка и экспериментальное исследование декомпозиционных алгоритмов для различных задач частично целочисленного программирования [57, 59, 90,92]. С теоретической точки зрения указанные алгоритмы исследованы недостаточно. В частности, актуальными являются вопросы получения оценок числа итераций, построения семейств "трудных" задач, устойчивости алгоритмов при малых колебаниях исходных данных.

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

В области целочисленного программирования (ЦП) получил развитие предложенный А.А.Колоколовым подход, основанный на регулярных разбиениях евклидова пространства [17,70]. Применение такого подхода позволило изучить структуру некоторых задач ЦП, ввести и исследовать новые классы отсечений, построить оценки числа итераций (отсечений) для ряда алгоритмов. Многие результаты получены на основе использования элементов ¿-разбиения, называемых ¿-классами. В работах [22,69] алгоритм перебора ¿-классов в сочетании с декомпозицией Бендерса применяется для решения задач размещения предприятий.

Важное место в дискретной оптимизации занимают вопросы устойчивости задач и алгоритмов ЦП [11,30,33,53]. На практике исходные данные задачи могут быть неточными, и даже в случае их достаточно малых колебаний оптимальное решение задачи может сильно изменяться. Задачи, решение которых при этом остается прежним, либо меняется незначительно, называются устойчивыми в том или ином смысле. Но и при сохранении оптимального решения число итераций алгоритма может существенно возрасти, и его естественно считать неустойчивым. Некоторые последние результаты по устойчивости задач и алгоритмов получены с использованием ¿-разбиения [18,53]. Представляет интерес исследование устойчивости декомпозиционных алгоритмов с отсечениями Бендерса.

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

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

Выделено семейство трудных задач для известных релаксационных алгоритмов ЦЛП: прямо-двойственного алгоритма перебора ¿-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Построены оценки числа итераций этих алгоритмов при решении задач из указанного семейства.

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

Диссертация состоит из введения, трех глав, заключения и списка литературы.

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

Основные результаты диссертации заключаются в следующем:

1. Построены семейства задач о р-медиане, на основе которых получены оценки числа итераций для декомпозиционных алгоритмов с отсечениями Бендерса, алгоритма перебора ¿-классов и алгоритма ветвей и границ (схема Лэнд и Дойг). Некоторые из этих оценок перенесены на достаточно широкий подкласс задач о р-медиане.

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

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

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

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

Заключение

В работе проведено исследование декомпозиционных алгоритмов с отсечениями Бендерса и некоторых алгоритмов целочисленного программирования при решении классических задач оптимального размещения предприятий — задачи о р-медиане (на минимум и на максимум) и простейшей задачи размещения. Разработаны новые декомпозиционные алгоритмы для решения задачи о р-медиане на максимум, проведены их экспериментальные исследования.

Список литературы диссертационного исследования кандидат физико-математических наук Косарев, Николай Александрович, 2006 год

1. Агеев A.A. О сложности задач минимизации полиномов от булевых переменных //Управляемые системы. - Новосибирск, 1983. -Вып. 23. - С. 3-19.

2. Агеев A.A. Точные и приблиэюенные алгоритмы для задач размещения: обзор последних достижений //Труды междунар. конференции. "Сибирская конференция по исследованию операций" , Новосибирск, 1998. С. 4-10.

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

4. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск, 1978. - 333 с.

5. Гимади Э.Х. Задача размещения на сети с центрально-связными областями обслуживания //Управляемые системы. 1979. -Вып. 19. - С. 3-13.

6. Гончаров E.H., Иваненко Д.А., Кочетов Ю.А., Кочетова H.A. Электронная библиотека "Дискретные задачи размещения" //Труды Байкальской междунар. конференции, Иркутск, 2001. Т. 1. -С. 132-137. http://math.nsc.ru/AP/benchmarks/

7. Гончаров E.H., Кочетов Ю.А. Вероятностный жадный алгоритм с ветвлением для многостадийной задачи размещения //Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения", Иркутск, 1998. С. 121-124.

8. Горбачевская JI.E., Кочетов Ю.А. Вероятностная эвристика для двухуровневой задачи размещения //Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения" , Иркутск, 1998. С. 249-252.

9. Гэри М., Джонсон Д. Вычислительные машины и труднорешае-мые задачи. М.: Мир, 1982. - 416 с.

10. Дементьев В.Т., Ерзин А.И., Ларин P.M., Шамардин Ю.В. Задачи оптимизации иерархических структур Новосибирск: НГУ, 1996. - 167 с.

11. И. Емеличев В. А, Кузьмин К., Леонович А., Устойчивость в векторных комбинаторных задачах оптимизации //Автоматика и телемеханика. 2004. - №2. - с. 79-92.

12. Еремин И.И., Мазуров В.Д., Астафьев H.H. Несобственные задачи линейного и выпуклого программирования М: Наука, 1983. - 336 с.

13. Заблоцкая O.A. L-разбиеиие многогранника стандартизации //Моделирование и оптимизация систем сложной структуры: Меж-вуз. сб. научн. труд., Омск: ОмГУ, 1987. С. 151-154.

14. Забудский Г.Г. Некоторые свойства многогранника о р-медиане //Вестник Омского гос. университета. 1998. - № 2. - С. 11-13.

15. Заозерская Л.А., Китриноу Е., Колоколов A.A. Задача оптимального размещения центров телекоммуникаций в регионе //Труды XIII междунар. Байкальской школы-семинара, Иркутск-Северобайкальск, 2006. Т. 1. - С. 469-474.

16. Ильев В.П. Оценка точности алгоритма жадного спуска для задачи минимизации супермодулярной функции //Дискретный анализ и исследование операций. Серия 1. 1998. - Т. 5. - № 4. - С. 45-60.

17. Колоколов A.A. Регулярные разбиения и отсечения в целочисленном программировании //Сибирский журнал исследования операций. 1994. - № 2. - С. 18-39.

18. Колоколов A.A., Девятерикова М.В. Анализ устойчивости L-разбиения мноэюеств в конечномерном пространстве //Дискретный анализ и исследование операций, 2000. Серия 2. Т. 7. - № 2. -С. 47-53.

19. Колоколов A.A., Косарев H.A. Гибридный алгоритм для решения задачи о р-медиане //Труды Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2006. -С. 101.

20. Колоколов A.A., Косарев H.A. Исследование отсечений Бендерса для задачи о р-медиане //Труды Всероссийской конференции "Проблемы оптимизации и экономические приложения", Омск, 2003. -С. 96.

21. Колоколов A.A., Косарев H.A., Рубанова H.A. Исследование отсечений Бендерса в декомпозиционных алгоритмах решения некоторых задач размещения //Омский научный вестник. 2005.2(31). С. 76-80.

22. Колоколов A.A., Леванова Т.В. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения //Вестник Омского гос. университета. 1996. - № 1. - С. 21-23.

23. Косарев H.A. Оценки числа итераций для некоторых алгоритмов решения задачи о р-медиаие //Труды 37-й Региональной молодежной конференции "Проблемы теоретической и прикладной математики" , Екатеринбург: УрО РАН, 2006. С. 386-390.

24. Косарев H.A. Разработка и экспериментальные исследования декомпозиционных алгоритмов для задачи о р-медиане. //Препринт. Омск: ОмГУ, 2006. 23 с.

25. Косарев H.A., Рубанова H.A. Об отсечениях Бендерса для некоторых задач размещения предприятий// Труды всероссийской конф. "Дискретный анализ и исследование операций". Новосибирск, 2004. С. 164.

26. Кочетов Ю.А., Пащенко М.Г., Плясунов A.B. О сложности локального поиска в задаче о р-медиане //Дискретный анализ и исследование операций. Серия 2. 2005. - Т. 12. - № 2. - С. 44-71.

27. Леванова Т.В. Некоторые алгоритмы решения задачи размещения с ограничениями на объемы производства //Труды междунар. конференции. "Сибирская конференция по исследованию операций", Новосибирск, 1998. С. 103.

28. Леванова Т.В. Разработка и анализ алгоритмов решения дискретных задач оптимального размещения //Диссертация на соискание ученой степени кандидата физ.-мат. наук. Иркутск, 2000.

29. Леванова Т.В., Лореш М.А. Алгоритмы муравьиной колонии и имитации отжига для задачи о р-медиане //Автоматика и телемеханика. 2004. - № 3. - С. 80-88.

30. Леонтьев В.К., Мамутов К.Х. Устойчивость решений в задачах линейного булева программирования //ЖВМ и МФ. 1988. -С. 21-24.

31. Пащенко M.Г. Нижние оценки для целевой функции в динамической задаче выбора оптимального состава двухуровневой системы технических средств //Дискретный анализ и исследование операций. Серия 2. 1997. - Т. 4. - № 1. - С. 40-53.

32. Попков В.К. Математические модели связности Новосибирск, 2006. - 490 с.

33. Сергиенко И.В., Козерацкая Л.Н., Лебедева Т.Т. Исследование устойчивости и параметрический анализ дискретных оптимизационных задач Киев: Наукова думка, 1995. - 170 с.

34. Стрекаловский A.C., Васильева A.M. Поиск глобального решения в задаче размещения //Труды междунар. конференции "Дискретный анализ и исследование операций", Новосибирск, 2000. С. 121.

35. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. М.: Мир, 1991. - 702 с.

36. Трубин В.А. Эффективный алгоритм размещения на сети в форме дерева //Докл. АН СССР. 1976. - Т. 231. - № 3. - С. 547-550.

37. Хачатуров В.Р. Математические методы регионального программирования М.: Наука, 1989. - 304с.

38. Ageev A.A., Sviridenko M.I. Approximation Algorithms for some Problems with cardinalyty-type contraints //Труды XI междунар. Байкальской школы-семинара "Методы оптимизации и их приложения" , Иркутск, 1998. С. 107-110.

39. Avella P., Sassano A. On the p-median polytope //Mathematical Programming. 2001. - № 89. - P. 395-411.

40. Avella P., Sassano A., VasiPev I. Computational study of large scale p-median problems //Mathematical Programming. 2006. - DOI: 10.1007/sl0107-005-0700-6.

41. Balinski M.L. Integer Programming: Methods, Using, Computation //Management Science. 1965. - № 12. - P. 253-313.

42. Barany I., Edmonds J., Wolsey L.A. Packing and Covering Trees by Subtrees //Combinatorica. 1986. - № 6. - P. 245-257.

43. Beasley J.E. A note on solving large p-median problems //European Journal of Operational Research. 1985. - № 21. - P. 270-273.

44. Beasley J.E. Lagrangean heuristic for location problems //European Journal of Operational Research. 1993. - № 65. - P. 383-399.

45. Benders J. F. Partitioning Procedures for Solving Mixed-variables Programming Problems //Numerische Mathematik 1962. - Vol. 4. -№.3.- P. 238-252.

46. Charikar M., Guha S. Improved Combinatorial Algorithms for the Facility Location and k-Median Problems //Proceedings of the 40th Annual IEEE Conference on Foundations of Computer Science, 1999. -P. 378-388.

47. Charikar M., Guha S., Tardos E., Shmoys D.B. A constant factor approximation algorithm for the k-median problem //Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999. -P. 1-10.

48. Chiyoshi F., Galvao D. A statistical analysis of simulated annealing applied to the p-median problem //Annals of Operations Research. -2000. № 96. - P. 61-74.

49. Christofides N., Beasley J.E. A tree search algorithm for the p-median problem J/European Journal of Operational Research. 1982. - № 10. -P. 196-204.

50. Cornuejols G., Fisher M.L., Nemhauser G.L. Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms //Management Science. 1977. - № 23. - P. 789-810.

51. Cornuejols G., Nemhauser G.L., Wolsey L.A. The Uncapacitated Facility Location Problem //In "Discrete Location Theory" (Ed. by Pitu B. Mirchandani and Richard L. Franscis), by John Wiley and Sons, Inc., 1990. P. 119-171.

52. Correa E.S., Steiner M.T.A., Freitas A.A., Carnieri C. A genetic algorithm for the p-median problem// Proceedings of 2001 Genetic and Evolutionary Computation Conf. (GECCO-2001), P. 1268-1275.

53. Devyaterikova M.V., Kolokolov A.A. On the stability of some integer programming algorithms //Operation Research Letters. 2006. -№34(2).-P. 149-154.

54. Galvao R. D. A dual-bounded algorithm for the p-median problem //Operation Research. 1980. - № 28. - P. 1112-1121.

55. Gascon V., Benchakroun A., Ferland J. Benders decomposition for network design problems with underlying tree structure //Investigación Operativa. 1997. - № 6. - P. 165-180.

56. Garfinkel R.S., Neebe A.W., Rao M.R. An algorithm for the M-median plant location problem //Transportation Science. 1974. - № 25. -P. 183-187.

57. Geoffrion A.M., Graves G.W. Multicomodity distribution system design by Benders decomposition //Management Science. 1974. - № 20. -P. 822-844.

58. Hakimi S.L. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph //Operation Research.- 1964. -№ 12. P. 450-459.

59. Handler G.Y., Mirchandani P.B. Location on Networks: Theory and Algorithms MIT Press, Cambridge, Massachusetts, 1979.

60. Hansen P., Mladenovic N. Variable neighbourhood search for the p-median //Location Science. 1997. - № 5. - P. 207-226.

61. Held M., Wolfe P., Crowder H. Validation of Subgradient Optimization //Mathematical Programming. 1974. - № 6. - P. 62-88.

62. Hosage C.M., Goodchild M.F. Discrete space location-allocation solutions from genetic algorithms //Annals of Operational Research. -1986. № 6. - P. 35-46.

63. Hua L.K. et al. Applications of Mathematical Methods to Wheat Harvesting. //Chinese Mathematics. 1962. - № 2. - P. 77-91.

64. Jain K., Vazirani V.V. Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation //Journal of ACM. 2001. - P. 274-296.

65. Kariv O., Hakimi S.L. An Algorithmic Approach to Network Location Problems. Part 2. The p-Median. //SIAM J. Appl. Math. 1979. -№ 37. - P. 539-560.

66. Kolen A. Solving Covering Problems and the Uncapacitated Plant Location Problem on Trees. //European Journal of Operational Research. 1983. - № 12. - P. 266-278.

67. Kolokolov A.A. Decomposition Algorithms for Solving of some Production-Transportation Problems //Triennal Symposium on Transportation Analysis II. Preprints. Vol. 1. Capri, Italy, 1994. -P. 179-183.

68. Kolokolov A.A. Regular partitions and cuts in integer programming// Discrete Analysis and Operation Research. 1996. - P. 59-79.

69. Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem //Journal of Mathematical Modelling and Algorithms. 2006. - № 5. - P. 189-199.

70. Kolokolov A.A., Kosarev N.A. Analysis of decomposition algorithms with Benders cuts for p-median problem //Proceedings of The 2nd International Workshop "Discrete Optimization Methods in Production and Logistics", Omsk-Irkutsk, Russia, 2004. P. 66-69.

71. Kolokolov A.A., Kosarev N.A. Analysis of some Benders decomposition algorithms for the p-median problem //Proceedings of XIV Meeting of EURO Working Group on Location Analysis, Corfu, Greece, 2003. -P. 36.

72. Kolokolov A.A., Kosarev N.A. Study of some decomposition algorithms for p-median problems //Proceedings of XV Meeting of EURO Working Group on Location Analysis, Saarbruecken, Germany, 2004. P. 58.

73. Kosarev N.A., Kolokolov A.A. On Stability of Some Benders Decomposition Algorithms for p-median Problem //Proceedings of European Chapter on Combinatorial Optimization XVIII, Minsk, Byelorussia, 2005. P. 26.

74. Kosarev N.A., Kolokolov A.A., Rubanova N.A. On Iterations Number of Benders Decomposition Algorithms for Some Facility Location Problems //Proceedings of European Chapter on Combinatorial Optimization XVIII, Minsk, Byelorussia, 2005. P. 27.

75. Krarup J., Pruzan P.M. The simple plant location problem: survey and synthesis. //European Journal of Operational Research. 1983. -№ 12. - P. 36-81.

76. Levy J. An Extended Theorem for Location on a Network //Operation Research Quarterly. 1967. - № 18. - P. 433-442.

77. Mirchandani P.B., Oudjit A., Wong R. Multidimensional Extensions and a Nested Dual Approach for the m-Median Problem //European Journal of Operational Research. 1985. - № 21. - P. 121-137.

78. Mirchandani P.B., Reilly J.M. Spatial Distribution Design for Fire Fighting Units //In "Spatial Analysis and Location-Allocation Models" (Ed. by A. Ghosh and G. Rushton), 1987. P. 203-222.

79. Moon D.I., Chaudhry S.S. An Analysis on Network Location Problems with Distant Constraints //Management Science. 1984. - № 30. -P. 290-307.

80. Mulvey J., Crowder H. Cluster analysis: an application of lagrangian relaxation //Management Science. 1979. - № 25. - P. 329-340.

81. Narula S.C. Hierarhical Location-Allocation Problems: A Classification Scheme //European Journal of Operational Research. 1984. - № 15. -P. 93-99.

82. Nemhauser G.L., Wolsey L.A. and Fisher M.L. An analysis of approximations for maximizing submodular set functions. I. //Mathematical Programming. 1978. - № 14. - P. 265-294.

83. Reinelt G. TSPLIB: A traveling salesman problem library //ORSA Journal on Computing. № 1991. - № 3. - P. 376-384. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/.

84. Randazzo D., Luna H. P. L., Mahey P. Benders Decomposition For Local Access Network Design With Two Technologies //Discrete Mathematics and Theoretical Computer Science. 2001. - № 4. -P. 235-246.

85. Resende M.G.C., Werneck R.F. A GRASP with path-relinking for the p-median problem //AT&T Labs Research Technical Report TD-5E53XLKA. 2002.

86. Richardson R. An optimization approach to routing aircraft //Transportation Science. 1976. - № 10. - P. 52-71.

87. Rolland E. , Schilling D. A., Current J.R. An efficient tabu search procedure for the p-median problem //European Journal of Operational Research. 1996. - № 96. - P. 329-342.

88. Teitz M.B., Bart P. Heuristic methods for estimating the generalized vertex median of a weighted graph //Operation Research. 1968. -№ 16 - P. 955-961.

89. Whitaker R.A. A fast algorithm for the greedy interchange for large-scale clustering and median location problems //INFORS. 1983. -№ 21. - P. 95-108.