Математические модели и численные методы решения задач многократного покрытия тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Карпова, Марина Александровна

• Карпова, Марина Александровна
• кандидат физико-математических наук
• 2011

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

ВВЕДЕНИЕ.

Глава 1. ЗАДАЧА ПОКРЫТИЯ.

1.1. Постановка задач покрытия.

1.2. Области Вороного.

1.3. Свойства математической модели непрерывной задачи покрытия.

1.4. Свойства математической модели дискретной задачи покрытия.

1.5. Алгоритмы решения дискретной задачи.

1.6. Решение непрерывной задачи покрытия.

1.7. Некоторые экстремальные и предполагаемые двукратные покрытия квадрата.

Глава 2. ЗАДАЧИ ПОКРЫТИЯ С ДОПОЛНИТЕЛЬНЫМИ УСЛОВИЯМИ НА ПОЛОЖЕНИЯ ЦЕНТРОВ И НА ПОКРЫВАЕМЫЕ МНОЖЕСТВА.

2.1. Оптимизация покрытия конечного множества при расположении центров в произвольных точках заданной области.

2.2. Оптимизация покрытия заданной области, когда центры кругов расположены в некоторых точках из заданных.

2.3. Оптимизация покрытия конечного множества точек, когда центры располагаются в некоторых точках заданного конечного множества.

Глава 3. ОПТИМИЗАЦИЯ РАСПОЛОЖЕНИЙ.

СТАНЦИЙ ОБСЛУЖИВАНИЯ.

3.1. Постановка задачи и математические модели. Используемые метрики.

3.2. Бисекторы и многократные области Вороного для 1Крв-метрики.

3.3. Подбор параметров 1Крв -метрики.

3.4. Вычисление параметров метрики для регионов Татарстана.

3.5. Построение доверительных интервалов.

3.6. Оптимизация расположения станций обслуживания на территории Татарстана.

3.7. Определение числа и расположения видеокамер противопожарной системы наблюдения части территории Татарстана.

3.8. Определение числа пунктов хранения химических реагентов для обслуживания нефтепромыслов.

4.1. Назначение и структура программного комплекса.

4.2. Работа с библиотекой ILOG CPLEX 11.2.

4.3. Интерфейс программного комплекса и методика использования.

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

Актуальность темы. Работа посвящена решению некоторых задач многократных (в том числе и однократных) покрытий ограниченных множеств конгруэнтными кругами. Многие технические и экономические задачи сводятся к задаче покрытия заданной области зонами обслуживания. Так, например, задачи расположения различных станций технического обслуживания, станций сотовой связи, беспроводного Интернета являются задачами покрытия кругами ограниченной области. Многократные покрытия не менее интересны и важны, чем однократные, в частности, навигационные системы GPS, Глонасс и разрабатываемая европейская система Галилео используют многократное покрытие обслуживаемых областей.

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

При размещении логистических, а также распределительных центров зоной обслуживания будет «круг», в котором расстояние от центра до потребителя измеряется по существующим дорогам. При этом расстояния можно оценивать, используя некоторую метрику на заданной области. К классу указанных задач можно отнести задачу расположения центров служб чрезвычайных событий, использующих существующие дороги. Также таковой является, например, задача определения местоположения пунктов хранения химических реагентов для нефтепромыслов. Важно расположить эти пункты таким образом, чтобы быстрее доставлять реагенты в нужную точку. При этом, если в ближайшем пункте требуемого реагента не окажется, то желательно, чтобы второй пункт оказался не очень далеко. В результате получим задачу двукратного покрытия заданной области зонами обслуживания отдельных центров хранения реагентов (станций обслуживания).

При определении расстояний можно использовать готовые матрицы расстояний или геоинформационные системы типа Агс!п&, Мар1пй), Панорама, Агс018 или функции оценки расстояний. Матрицы расстояний и геоинформационные системы сложно использовать для качественного анализа областей обслуживания отдельных станций — областей Вороного. Поэтому во многих работах используются функции для оценки расстояний, которые порождают некоторую метрику- на рассматриваемой области. В литературе используются различные метрики: евклидова, / -метрика, взвешенная /^-метрика [120-122], взвешенная 1р-метрика с возможным поворотом осей координат [121], -метрика [94, 146], манхэттенская [109], московская [107], блок-метрики [149-150] и ряд других метрик. Выбор метрики зависит от свойств рассматриваемой области и существующих связей центра с клиентами. В диссертации выбрана 1Крд -метрика, как наиболее подходящая для регионов Татарстана.

Оптимизации расположения различных станций обслуживания посвящены специальные монографии и большое число статей, исследующих как общие вопросы, так и решение задач для выбранных областей. Например, в ряде работ рассматривается оптимизация расположений станций для отдельных стран (США, Германия, Индия) [58, 62, 81, 82, 88, 120, 144], отдельных регионов или городов и даже для отдельных частей населенных пунктов [69].

Актуальность тематики определяется не только важными разнообразными приложениями задач покрытий, но имеет также самостоятельный математический аспект, ибо к таким задачам (моделям) сводится исследование многих комбинаторных и других задач, см., например, работы [18, 37, 46, 48, 49].

Цель работы

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

• повышение эффективности алгоритмов решения непрерывных и дискретных задач многократного покрытия ограниченных множеств.

Задачи исследования

• выявить свойства математических моделей дискретных и непрерывных задач покрытия, условия существования решений;

• разработать численные алгоритмы оптимизации числа кругов или (и) их расположения для ^-кратного (к > 1) покрытия заданных областей или заданного конечного множества точек;

• получить оценки насколько далеки результаты решений от глобальных экстремумов;

• подобрать метрики и их параметры для выбранных районов Татарстана;

• оптимизировать числа и расположения некоторых станций обслуживания на всей или части территории Татарстана.

Апробация работы и публикации. Основные результаты исследований опублйкованы в трех статьях [10, 22, 23] в журналах из списка, рекомендованного ВАК РФ. Результаты исследований докладывались и обсуждались на различных конференциях [8, 9, 24—29].

Структура и объем диссертации

Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложения. Общий объем диссертации составляет 140 страниц

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Карпова, Марина Александровна

ЗАКЛЮЧЕНИЕ (ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ)

1. Выявлены свойства математических моделей задач покрытия:

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

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

2. Разработаны численные алгоритмы решения дискретной задачи многократного покрытия и алгоритмы решения непрерывной задачи многократного покрытия. Решение осуществляется комбинированным использованием математических* моделей непрерывных и дискретных задач покрытия.

3. Получены оценки, минимальных радиусов покрывающих кругов.

4. Получены экстремальные и предполагаемые значения радиусов п кругов для двукратного покрытия единичного квадрата при п < 9 и п = 11,13,15,17,19,21.

5. Исследованы различные варианты задач покрытия при ограничениях на положения центров кругов и покрываемые множества. Для каждого варианта разработаны численные алгоритмы для решения этих задач. Для некоторых из них получены оценки решений.

6. Выбрана метрика для части регионов территории Татарстана, подобраны параметры этой метрики. Исследованы свойства бисекторов и областей Вороного при выбранной метрике.

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

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

9. В работе сформулированы и доказаны 5 теорем, 6 лемм и 2 следствия. Имеется справка об использовании результатов работы из Минлесхоза Татарстана и акт внедрения в учебный процесс Казанского национального исследовательского технического университета им. А.Н. Туполева-КАИ.

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

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

1. Брусов B.C., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журнал вычисл. матем. и матем. физ. -Москва, 1971 (11). -№2. -С. 304-312.

2. Бухараев Р.Г., Захаров В.М. и др. Программная система для анализа методов стохастической геометрии в распознавании образов // Распознавание образов и изображений: Тезисы доклада межд. конф. -Ульяновск: Изд-во УГТУ, 1995. С. 39-41.

3. Галиев Ш.И. Максимин задачи покрытий и упаковок. Казань: Изд-во Казан, гос. техн. ун-та, 1997. - 260 с.

4. Галиев Ш.И. Многократные упаковки и покрытия сферы // Дискретная математика. 1996. - Т. 8. № 3. - С. 148-160.

5. Галиев Ш. И. Направления убывания для минимаксиминных задач // Журнал вычисл. матем. и матем. физ. 1994. - Т. 34. № 3. - С. 323343.

6. Галиев Ш.И., Заботин В.И. О непрерывном обзоре поверхности Земли // Исследование Земли из космоса. 1983. - №1. - С. 117-120.

7. Галиев Ш.И., Карпова М.А. Многократное покрытие ограниченного множества кругами // Наука в вузах: математика, физика, информатика: Тезисы доклада Международной научно-образовательной конференции 23 27 марта 2009 г. - г.Москва, 2009. -С. 338-340.

8. Галиев Ш.И., Карпова М.А. Оптимизация многократного покрытия ограниченного множества кругами // Журнал вычисл. матем. и матем. физ. 2010. - Т. 50. №7. - С. 757-769.

9. Демьянов В.Ф., Васильев JI.B. Недифференцируемая оптимизация. -М.: Наука, Главная редакция физико-математической литературы, 1981.-384 с.

10. Демьянов В.Ф. Минимакс: дифференцируемость по направлениям. -Л., Изд-во Ленингр. ун-та, 1974. 112 с.

11. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972.-368 с.

12. Емалетдинова Л.Ю., Галиев Ш.И., М.А.Разина. Нахождение глобального экстремума и субоптимальных решений для задач размещения станций скорой помощи // Вестник КГТУ им. А.Н.Туполева. 2004. - №3. - С. 40^5.

13. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. М.: Наука, Главная редакция физико-математической литературы, 1981. 344 с.

14. Еремеев A.B. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. 2000. - Сер. 2. Т. 7. №1. - С. 47-60.

15. Еремеев A.B., Заозерская Л.А., Колоколов A.A. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования//

16. Дискретный анализ и исследование операций. -2000. Серия 2. Т. 7. № 2. - С. 22^6.

17. Журавлев Ю. И. Избранные труды. М.: Магистр, 1998. 420 с.

18. Заозерская JI.A., Китриноу Е., Колоколов A.A. Задача оптимального размещения центров телекоммуникаций в регионе // Тр. 13 Байкал, междунар. шк.-семинара "Методы оптимизации и их приложения". -Иркутск, 2005. Т. 1. - С. 469-475.

19. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: Учеб. пособие. — М.: Физматлит, 2005. — 304 с.

20. Кабатянский Г.А., Левенштейн В.И. О границах для упаковки на сфере и в пространстве // Проблемы передачи информации. 1978. -Т. 14. №1.-С. 3-25.

21. Карпова М.А., Галиев Ш.И. Оптимизация расположения станций обслуживания. Часть 1 // Вестник КГТУ им. А.Н. Туполева. 2011. -№ 1. - С. 104-109.

22. Карпова М.А., Галиев Ш.И. Оптимизация расположения станций обслуживания. Часть 2 // Вестник КГТУ им. А.Н. Туполева. 2011. -№2.-С. 67-71.

23. Карпова М.А. Оптимизация расположения станций обслуживания заданной области // Туполевские чтения: Материалы 16-й Междунар. молод, научн. конф. Казань: КГТУ, 2008. - Т.4. - С. 18-20.

24. Карпова М.А. Многократное покрытие заданной области зонами обслуживания // Математические методы и информационные технологии в экономике, социологии и образовании: Тезисы доклада XXI Международной научно-техн. конф. г. Пенза, 2008. - С. 26-28.

25. Карпова М.А. Оптимизация расположения станций обслуживания заданной области с учетом подбора метрики // Туполевские чтения:

26. Материалы 17-й Междунар. молод, научн. конф. Казань, 2009. — С. 14-16.

27. Карпова М.А. Программное обеспечение решения задач многократного покрытия ограниченного множества кругами // Туполевские чтения: Материалы 18-й Междунар. молод, научн. конф.-Казань, 2010.-С. 140-142.

28. Кларк Ф. Оптимизация и негладкий анализ: Пер. с англ. М.: Наука, 1988.-280 с.

29. Ковалев М.М., Пирьянович В.А. Случайный поиск локально-оптимальных планов задач дискретной оптимизации // Вопр. совершенствования планирования и управления народным хозяйством. Минск: НИИЭМП, 1975. С. 215-223.

30. Ковалев М.М. Дискретная оптимизация (целочисленное программирование) Изд. 2-ое, стереотипное. М.: Едиториал УРСС, 2003.- 192 с.

31. Колмогоров А.Н., Фомин C.B. Элементы теории функций и функционального анализа. М.: Наука, 1972. 496 с.

32. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. Т. 1 и 2. М.: Мир, 1990.-415 с.

33. Кониов И.В. Адаптивный алгоритм неявного перебора в задачах дискретной оптимизации // Исслед. по прикл. матем. Казань, 1999. — Вып.21. - С. 140-154.

34. Коннов И.В. Методы недифференцируемой оптимизации. Казань: Казанск. ун-т, 1993. - 100 с.

35. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-429 с.

36. Кузюрин H.H. О сложности построения асимптотически оптимальных покрытий и упаковок // Докл. РАН. 1998. - Т. 363. №1. - С. 11-13.

37. Левенштейн В.И. Границы для упаковок метрических пространств и некоторые их приложения // Проблемы кибернетики. 1983. — Т. 40. — С. 43-110.

38. Леонтьев В.К. Дискретная оптимизация // Журнал вычисл. матем. и матем. физ. 2007. - Т. 47. № 2. - С. 338-352.

39. Михалевич B.C., Гупал A.M., Норкин В.Н. Методы невыпуклой оптимизации. М.: Наука, 1987.-280с.

40. Мухачева Э.А. Обзор и перспективы развития комбинаторных методов решения задач раскроя и упаковки // Дискретный анализ и исследование операций: Материалы конференций. Институт математики СО РАН. Новосибирск, 2002. - С. 80-70.

41. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. САПР раскроя: основные проблемы и опыт их решения // М.: Машиностроение. Вестник компьютерных и информационных технологий. 2004. — № 2. -С. 31^10.

42. Мухачева Э.А., Залгаллер В.А. Линейное программирование в задачах раскроя // Международный журнал программного обеспечения в инженерных знаниях. 1993. - Т. 3. № 4. - С. 463-476.

43. Пиявский С.А. Об оптимизации сетей // Известия АН СССР. Техническая кибернетика. 1968. — №1. — С. 68-80.

44. Роджерс К. Укладки и покрытия. М.: Мир, 1968. 134 с.

45. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Физматлит, 2007. 240 с.

46. Сидельников В.М. О плотнейшей укладке шаров на поверхности п-мерной сферы и числе векторов двоичного кода с заданным кодовым расстоянием // Докл. АН СССР. 1973. - Т. 213. - С. 1029-1032.

47. Фейеш Тот Л. Расположения на плоскости, на сфере и в пространстве. М.: Физматгиз, 1958. 364 с.

48. Финкелыптейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука, 1976. 264 с.

49. Aardal К., Nemhauser G.L., Weismantel R. Discrete optimization. North Holland, 2005. - 606 pp.

50. Al-Sultan K.S. and Al-Fawzan M.A. A tabu search approach to the uncapacitated facility location problem // Annals of Operations Research. -1999.-V. 86.-C. 91-103.

51. Alves M.L. and Almeida M.T. Simulated annealing algorithm for simple plant location problems // Rev. Invest. 1992. - № 12. - P. 167.j

52. Arya V., Garg N., Khandekar R., Meyerson A., Munagala K. and Pandit V. Local search heuristics for k-median and facility location problems // ACM Symposium on Theory of Computing. 2001. - P. 21-29.

53. Aurenhammer F. Voronoi diagram — a survey of a fundamental geometric data structure // ACM Computing Surveys. 1991. - V.33. №3. - P. 345405.

54. Balas E., Caprrera M.C. A dynamic subgradient-based branch and bound procedure for set covering // Oper. Res. 1996. - V. 44. № 6. - P. 875-890.

55. Balas E., Ho A. Set covering algorithms using cutting planes, heuristics and subgradient optimization: a computational study // Math. Prog. Study. -1980.-V. 12.-P. 37-60.

56. Banerji S.H., Fisher H.B. Hierarchical location analysis for integrated area planning in rural India // Papers of the Regional Science Association 33. -1974.-P. 177-194.

57. Barahona F. and Chudak F.A. Near-optimal solutions to large scale facility location problems // Technical Report, IBM Watson Research Center. -2000.-P. 168, 169, 172.

58. Beasley J. E., Jornston K. Enhancing an algorithm for set covering problems // Europ. J. Oper. Res. 1992. - V. 58. - P. 293-300.

59. Belacel N., Hansen P. and Mlladenovic N. Fuzzy J-means: A new heuristic for fuzzy clustering // Pattern Recognition. 2002. - V. 35. - P. 21932200.

60. Berens W., Korling E.J. Estimating road distances by mathematical functions // European Journal of Operational Research. 1985. - V. 21. - P. 54-56.

61. Bertsimas D., Vohra R. Rounding algorithms for covering problems // Mathematical Programming. 1998. - V. 80. - P. 63-89.

62. Bilde O. and Krarup J. Sharp lower bounds and efficient algorithms for the simple plant location problem // Annals of Discrete Mathematics. 1977. -V. l.-P. 79-97.

63. Brimberg J., Love R. F., Walker J. H. The effect of axis rotation on distance estimation // European Journal of Operational Research. 1995. -V. 80.-P. 357-364.

64. Buharaev R.G., Zaharov V.M., Salimov F.I., Frolov V.B. The model of specialized stohchastic network // Inter. Work shop on mathem. Method and tools in computer simul. Saint-Peter. Msa-bo C-FI rocyHHBepcuTexa, 1994. Preprint MM-94-01. C. 27-29.

65. Caprara A., Fischetti M., Toth P. Algorithms for the set covering problem // DEIS Operations Res. Group. - 1998. - Technical Rep. N OR-98-3. http://citeseer.ist.psu.edu/Caprara 98 algorithms.html

66. Caprara A., Toht P., and Fischetti M. Algorithms for the set covering problem H Annals of Operations Research. 2000. - Vol. 98. - P. 353-371.

67. Carson Y, Butta R. Location an ambulance on the Amherst campus of State University of New York at Buffalo // Interfaces. Vol. 20. - P. 43-49.

68. Ceria S., Nobili P. and Sassano A. A Lagrangian-based heuristic for large-scale set covering problems // Mathematical Programming. -1998. Vol. 81. №2.-P. 215-228.

69. Chen L., Yuan D. Solving a minimum-power covering problem with overlap constraint for cellular network design // European Journal of Operational Research. 2010. - Vol. 203. - P. 714-723.

70. Chudak F.A. Improved approximation algorithms for uncapacitated facility location // In Proceedings of the 6th IPCO Conference. 1998. - P. 180194.

71. Chvatal V. A greedy heuristic for the set covering // Mathematics of Optimization Research. 1979. - Vol. 4. - P. 233-235.

72. Cordone R., Ferrandi F., Sciuto D., Calvo R.W. An efficient heuristic approach to solve the unate covering problem // IEEE Transactions oncomputer-aided design of integrated circuits and systems. 2001. - Vol. 120. № 12.-P. 1377-1387.

73. Coudert O. On solving covering problems // In proceedings of 30th ACM/IEEE Design automation conference. 1996. - P. 197-202.

74. Daskin M.S. Network and discrete location: Models, algorithms, and applications. Wiley, New York, 1995. 520 pp.

75. Drezner Z. (editor). Facility location: A survey of applications and methods. Springer-Verlag, N.Y., 1995. 572 pp.

76. Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin, 2002. P. 233-274.

77. Drezner Z. The p-centre problem heuristic and optimal algorithms // J. OR Soc. - 1984. - Vol. 35. - P. 741-748.

78. Drezner Z. A general global optimization approach for solving location problems in the plane // J Glob. Optim. 2007. - Vol. 37. - P. 305-319.

79. Eaton D., Hector M., Sancher V., Latingua R., Morgan I. Determing ambulance deployment in Santo Doming, Dominican Respublic // Journal of the Operational Research Society. 1986. - Vol. 37. - P. 113-126.

80. Eaton D.J., Daskin M.S., Simmons D., Bulloch B. and Jansma G. Determing emergency medical deployment in Austin. Texas // Interfaces. -1985.-Vol. 15. № l.-P. 96-108.

81. Eremeev A.V., Kolokolov A. A., Zaozerskaya L. A. A hybrid algorithm for set covering // Proc. of Intern, workshop on discrete optimization methods design.-Minsk: S. n., 2000.-P. 123-129.

82. Farahani R. Z., Hekmatfar M. (eds.). Facility location. Concepts, models, algorithms and case studies. Springer-Verlag. - Berlin, Heidelberg. -2009. - 530 pp.

83. Fejes Tot G. Multiple packing and covering of the plane with circles // Acta Math. Acad. Sci. Hungar. 1976. - Vol. 27. № 1-2. - P. 135-140.

84. Fejes Tot G. Multiple packing and covering of spheres // Acta Math. Acad. Sci. Hungar. 1979. - Vol. 34. № 1-2. - P. 165-176.

85. Fisher M.L., Kedia P. Optimal solution of set covering/ partitioning problems using dual heuristics // Management Sci. — 1990. Vol. 36. — P. 674-688.

86. Fugerholt K., Lindstad H. Optimal policies for maintaining a supply service in the Norwegian Sea//0mega.-2000. Vol. 28. № 3.-P. 269 - 275.

87. Fujito T. On combinatorial approximation of covering 0-1 integer programs and partial set cover // Journal of Combinatorial Optimization. -2004. Vol. 8. - P. 439^152.

88. Galinier P. and Heztz A. Solution techniques for the large set covering problem // Discrete applied Mathematics. 2007. - Vol. 155. Issue 3.-P. 312-326.

89. Galv~ao R.D. and Raggi L.A. A method for solving to optimality uncapacitated facility location problems // Annals of Operations Research. — 1989,- Vol. 18.-P. 225-244.

90. Guha S. and Khuller S. Greedy strikes back: Improved facility location algorithms // Journal of Algorithms. -1999. Vol. 31. - P. 228-248.

91. Hall N., Hochbaum D. A fast approximation algorithm for the multicovering problem // Discrete Applied Mathematics. 1989. - Vol. 15. -P. 35-40.

92. Hardy G.H., Littlewood J.E., Polya G. Inequalties. — London: Cambridge University Press, 1934. -312 pp.

93. Hentenryck P. Van and Michel L. A simple tabu search for warehouse location // Technical Report, CS-02-05. Brown University. - 2002. - P. 167, 172.

94. Heppes A. and Melissen H. Covering a rectangle with equal circles // Period. Math. Hungar. 1997. - Vol. 34. - P. 65-81.

95. Hochbaum D. S. In approximation algorithms for NP-hard problem. -1997. D. S. Hochbaum Ed. PWS Publishing Company. - P. 46-93.

96. Hochbaum D. S. Approximation algorithms for set covering and vertex cover problems // SIAM Journal of Computing. — 1982. Vol. 11. — P. 555-556.

97. Iwamura K., Okaday N., Deguchiz Y. Recent advancements of a genetic algorithm to solve the set covering problem. — 2004. P. 392-404.

98. Jain K., Vazirani V.V. Approximation algorithms for metric facility location and A:-median problems using the primal-dual schema and langrangian relaxation // Journal of the ACM. 2001. - V. 48. № 2. - P. 274-296.

99. Jain K., Mahdian M. and Saberi A. A new greedy approach for facility location problems // In Proceedings of the 34th Symposium on Theory of Computing. 2002, forthcoming, 2002. - P. 166.

100. Jandl H., Wieder K. A continuous set covering problem as a quasidifferentiable optimization problem // Optimization. J. of Math. Progr. and Operat. Res. 1988. - V. 19. № 6. - P. 781-802.

101. Johnson D. Approximation algorithms for combinatorial problems // Journal of computer and System Science. 1974. - V. 9. - P. 256-248.

102. Kolokolov A.A., Zaozerskaya L.A. A bicriteria problem of optimal service centers location // Proc. of 12th IFAC intern, symp., St. Etienne (France), 17-19 May 2006. Elsevier, 2006. S. 1.: V. 3. - P. 429^134.

103. Konnov I.V. Equilibrium models and variational inequalities. — Elsevier B.V., Amsterdam, e.a. 2007. - 248 pp.

104. Klein R. Voronoi diagrams in the Moscow metric // Graph-Theoretic Concepts in Computer Science International Workshop WG'88. Amsterdam June 15-17, 1988. Proceedings. P. 432^141.

105. Klose A., Drexl A. Facility location models for distribution system design // European Journal of Operational Research. 2004. - V. 162. - P. 4-29.

106. Kolesar P., Walker W. and Hausner J. Determining the relation between fire engine travel times and travel distanses in New York city // Operational Research. 1975. - V. 23. - P. 614-625.

107. Korupolu M.R., C.G. Plaxton and Rajaraman R. Analysis of a local search heuristic for facility location problems // In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms. -1998. P. 1-10.

108. Kratica J., Tosic D. and Filipovic V. Solving the uncapacitated warehouse location problem by sga with add-heuristic // In XV ECPD International Conference on Material Handling and Warehousing, 1998. -P. 167.

109. Kratica J., Tosic D., Filipovic V. and Ljubic I. Solving the simple plant location problem by genetic algorithm // RAIRO Operations Research. -2001.-V. 35.-P. 127-142.

110. Kratica J., Filipovic V., Sesum V. and Tosic D. Solving the uncapacitated warehouse location problem using a simple genetic algorithm // In Proceedings of the XIV International Conference on Material Handling and Warehousing. -1996. P. 3.33-3.37.

111. Kupper A. Location-based services. Fundamentals and Operation. John Wiley & Sons, Ltd. - 2005. - 368 pp.

112. Lee D.T. and Wong C.K. Voronoi diagrams in Z, metrics with 2dimensional storage applications // SIAM J. COMPUT. -1980. V. 9. - P. 200-211.

113. Lee D.T. Two-dimensional Voronoi diagrams in the Lp -metric // JACM. 1980.-V. 27.-P. 604-618.

114. Lifschitz V., Pittel B. The worst and the most probable performance of a class of set-covering algorithms // SIAM J. Comput. 1983. - V. 12. № 2. -P. 329-346.

115. Lilliefors H.W. On the Kolmogorov-Smirnov test for normally with mean and variance unknown // American Statistical Association Journal. — 1967.-P. 399-402.

116. Love R. F., Uster H. A statistical comparasion of three goodness-of-fit criteria used in modelling distances // Journal of Applied Mathematics and Decision Sciences. -2001. -V.5 № 4. P. 235-251.

117. Love R.F., Morris J.G. Mathematical models of road travel distances // Mamagement Science. 1979. - V. 25. - P. 130-139.

118. Love R.F., Morris J.G. Modeling inter-city road distances by mathematical models // Operational Research Quarterly. —1972. — V. 23. — P. 61-71.

119. Love R.F., Morris J.G. On estimating road distances by mathematical functions // European Journal of Operational Research. 1988. - V. 36. - P. 251-253.

120. Mahdian M., Marakakis E., Sabieri A. and. Vazirani V.V. A greedy facility location algorithm analyzed using dual fitting // In Proceedings of 5th International Workshop on Randomization and Approximation

121. Techniques in Computer Science, Lecture Notes in Computer Science. v. 2129. - Springer-Verlag, 2001. - P. 127-133.

122. Mahdian M., Ye Y. and Zhang J. Improved approximation algorithms for metric facility location problems // In Proceedings of the 5th APPROX• Conference, Lecture Notes in Computer Science. — v. 2462. 2002. - P.229.242.

123. Melissen H. Loosest circle coverings of an equilateral triangle // Math. Mag. 1997. - V. 70. - P. 119-125.

124. Melissen J.B.M. and Schuur P.C. Covering a rectangle with six and seven circles // Discrete Appl. Math. 2000. - V. 99. - P. 149-156.

125. Melissen J.B.M. and Schuur P.C. Improved coverings of a square with six and eight equal circles // Electron. J. Combin. 1996. - 3. R32. - 10 pp. (electronic).

126. Mirchandani P.B., Francis R.L. (eds) Discrete location theory. Wiley, New York. - 1990. - 576 pp.

127. Molin P., Abdi H. New Tables and numerical approximation for the Kolmogorov-Smimov/Littlefors/Van Soest test of normality // Technical report, University of Bourgogne // www.utd.edu/wherve/MolinAbdil998-LittleforsTechReport.pdf

128. Murray A. T., K. Kim, J. W. Davis, R. Machiraju, R. Parent. Coverage optimization to support security monitoring // Computers, Environment and Urban Systems.-2007.-V. 31.-P. 133-147.

129. Nickel S., Justo P. Location theory: a unified approach. SpringerVerlag. - Berlin, Heidelberg. - 2005. - 434 pp.

130. Novaesa A.G.N., Souza de Cursib J.E., A.C.L. da Silvac, Souzaa J. C. Solving continuous location-districting problems with Voronoi diagrams // Computers & Operations Research. 2009. - V. 36. - P. 40-59.c

131. Nurmella K.J. Conjectually optimal covering of an equilateral triangle with up to 36 equal circles // Experiment. Math. 2000. - V. 9. № 2. - P. 241-250.

132. Oded B., Drezner Z., Krass D., Wesolowsky G.O. The variable radius covering problem // European Journal of Operational Research. 2009. — V. 196.-P. 516-525.

133. Rahoual M., Hadji R., Bachelet V. Parallel ant system for the set covering problem // Lecture notes in computer science. S. 1.: Springer, 2002.-P. 262-267.

134. Repede J.F., Bernardo J.J. Developing and validating a decision support system for location emergency medical vehicles in Louisville, Kentucky // European Journal of Operational Research. 1994. — V. 40. - P. 58-69.

135. ReVelle C.S., Eiselt H.A., Location analysis: A synthesis and survey // European Journal of Operational Research. 2005. - V. 165. - P. 1-19.

136. ReVelle C.S., Eiselt H.A., Daskin M.S., A bibliography for some fundamental problem categories in discrete location science // European Journal of Operational Research. 2008. - 184. - P. 817-848.

137. Schiller J., Voisard A. Location-based services-Elsevier, 2004. 256p.

138. Solar M. Parada V., Urrutia R. A parallel genetic algorithm to solve the set-covering problem // Computer and Operations Research. 2002. - V. 29.-P. 1221-1235.

139. Sun M. A tabu search heuristic procedure for the uncapacitated facility location problem. In C. Rego and B. Alidaee (eds.) Adaptive Memory and Evolution: Tabu Search and Scatter Search, Kluwer Academic Publishers, forthcoming. 2002. - 167 pp.

140. Sviridenko M. An improved approximation algorithm for the metric uncapacitated facility location problem // In Proceedings of the 10th IPCO Conference, Lecture Notes in Computer Science. V. 2337. - 2002. - V. 166.-P. 230-239.

141. Talmar M. Location of rescue helicopters in South Tyrol // Papers Presented at 37th Annual ORSNZ Conference. Auckland, New Zealand. -2001.-386 p.

142. Tarnai T. and Gaspar Zs. Covering a square by equal circles // Elem. Math. -1995. V. 50. - P. 167-170.

143. Uster H., Love R.F. Application of weighted sum of order p to distance estimation // HE Transactions. 2001. - V. 33. № 8. - P. 675-684.

144. Uster H., Love R.F. Formulation of confidence intervals for estimated actual distances// Eur. J. Oper. Res. 2003. - V. 151. - P. 586 - 601.

145. Uster H., Love R.F. Application of weighted sum of order p»to distance estimation // HE Transactions. 200. - V.33. № 8. - P. 675-684.

146. Ward J.E., Wendell R.E. A new norm for measuring distance which yields linear location problems // Operations Research. 1980. - Vol. 28, № 3, Part II, May-June. - P. 836-844.

147. Ward James E., Richard E. Wendell. Using block norms for location modeling // Operations Research. 1985. - V. 33. - P. 1074-1090.

148. Zahn. C. T. Black box maximization of circular coverage // J. Res. Nat. Bur. Standards Sect. B. 1962. -V. 66. - P. 181-216.152. www2stetson.edu/~efriedma/packing.html153. http:// www.fire-watch.de154. http:// www.lesdozor.ru