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

ВВЕДЕНИЕ

1. ГЕОИНФОРМАЦИОННЫЕ СИСТЕМЫ И

МНОГОКРИТЕРИАЛЬНОЕ ПРИНЯТИЕ РЕШЕНИЙ

1.1. Понятие геоинформационной системы

1.2. Функции ГИС

1.2.1. Ввод и вывод данных

1.2.2. Хранение и управление данными

1.2.2.1. Геоинформационная база данных (ГБД)

1.2.2.2. Основные компоненты ГБД

1.2.2.3. ГИС-объекты

1.2.2.4. Типы атрибутивных данных

1.2.2.5. Слои данных

1.2.3. Обработка и анализ данных

1.2.3.1. Основные функции

1.2.3.2. Расширенные функции

1.3. Многокритериальная пространственная оптимизация

1.3.1. Классификация задач многокритериальной пространственной оптимизации

1.3.2. Основные понятия многокритериальной пространственной оптимизации

1.4. Операции над нечеткими данными

1.4.1. Операции над интервалами

1.4.2. Операции над нечеткими числами, описываемыми функциями

1.4.3. Операции над нечеткими треугольными числами

1.4.4. Операции над нечеткими трапециевидными числами

1.4.5. Операции над лингвистическими переменными

1.5. Выводы

2. НЕЧЕТКАЯ МИНИСУММНАЯ ЗАДАЧА РАЗМЕЩЕНИЯ

ЦЕНТРОВ ОБСЛУЖИВАНИЯ

2.1. Нечеткая однокритериальная задача размещения центров обслуживания

2.1.1. Понятие медианы нечеткого графа

2.1.1.1. Нечеткие критерии, относящиеся к сетям дорог

2.1.1.2. Нечеткие критерии, относящиеся к полигонам

2.1.1.3. Нечеткие критерии, относящиеся к сетям дорог и полигонам 53 2.1.2. Кратные медианы нечеткого графа

2.1.2.1. Понятие кратной медианы

2.1.2.2. Поиск р-медианы нечеткого графа

2.1.2.3. Алгоритм нахождения кратной медианы нечеткого графа, основанный на дереве поиска

2.2. Нечеткая многокритериальная задача размещения центров обслуживания

2.2.1. Постановка нечеткой многокритериальной задачи о р-медиане

2.2.2. Нормирование значений критериев

2.2.3. Критерии равной важности 76 2.2.3.1. Свертка критериев

2.2.4. Критерии различной важности

2.2.4.1. Определение весов критериев

2.2.4.2. Свертка критериев различной важности

2.2.5. Нахождение медиан

2.3. Выводы

3. НЕЧЕТКАЯ МИНИМАКСНАЯ ЗАДАЧА РАЗМЕЩЕНИЯ ЦЕНТРОВ

СКОРОЙ ПОМОЩИ

3.1. Нечеткая одиокритериальная задача размещения центров скорой помощи

3.1.1. Понятие нечеткого центра и нечеткого радиуса графа

3.1.2. Выбор места размещения одного центра скорой помощи в нечетком графе

3.1.3. Выбор места размещения одного центра скорой помощи при лингвистическом представлении расстояний на ребрах графа

3.2. Абсолютный центр и радиус нечеткого графа

3.2.1. Понятие нечеткого абсолютного центра и радиуса графа

3.2.2. Алгоритм определения нечеткого абсолютного центра графа

3.2.3. Модифицированный метод нахождения нечеткого абсолютного центра графа

3.3. Нечеткие р-центры и р-радиусы графа

3.3.1. Понятие нечеткого кратного центра (р-центра)

3.3.2. Понятие нечеткого абсолютного р-центра

3.3.3. Определение нечетких абсолютных р-центров

3.3.3.1. Алгоритм определения абсолютного р-центра нечеткого графа с заданной константой проникновения

3.3.3.2. Алгоритм определения абсолютного р-центра нечеткого графа с произвольной константой проникновения и с заданным числом р

3.3.4. Определение нечетких р-центров, расположенных в вершинах графа

3.4. Нечеткая многокритериальная задача размещения центров скорой помощи

3.5. Выводы

4. ПРИМЕР ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ МИНИСУММНЫХ И

МИНИМАКСНЫХ ЗАДАЧ РАЗМЕЩЕНИЯ С УЧЕТОМ НЕЧЕТКИХ

ИСХОДНЫХ ДАННЫХ

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

4.2. Модуль работы с ГИС ObjectLand. Извлечение информации из пространственной базы данных

4.2.1. Выбор тем. Работа с ГБД

4.2.2. Определение обслуживаемых объектов и сети дорог на карте

4.2.3. Переход от карты к нечеткому графу

4.3. Описание модуля реализации алгоритмов размещения

4.3.1. Определение кратчайших путей между станциями

4.3.2. Определение наилучшего места размещения одного центра обслуживания

4.3.3. Определение оптимальных мест размещения нескольких центров обслуживания

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

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

4.3.6. Определение оптимальных мест размещения нескольких центров скорой помощи

4.4. Выводы 143 ЗАКЛЮЧЕНИЕ 144 СПИСОК ЛИТЕРАТУРЫ

Актуальность работы

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

ГИС могут использоваться в различных областях деятельности, например, для ведения автоматизированных земельных кадастров в различных городах, для получения информации об экологической обстановке регионов, для ведения кадастра автомобильных и железных дорог.

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

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

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

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

Объект исследования.

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

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

Диссертационные исследования в практическом приложении направлены на создание прикладного программного продукта, поддерживающего связь с ГИС, для его применения на объектах железных дорог с целью оптимизации размещения обслуживающих пунктов.

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

Цель работы.

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

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

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

2). Осуществить анализ задач размещения обслуживающих пунктов в ГИС и построить модели решаемых задач. Данные модели будут основаны на нечетких графах.

3). Разработать алгоритмы решения задач размещения центров обслуживания с учетом нечетких данных, относящихся к точечным (площадным) объектам, а также к линейным объектам, описывающим участки сети дорог. В частности: а) определить место размещения одного центра обслуживания с учетом нечетких данных; б) разработать алгоритм для определения оптимальных мест размещения заданного числа центров обслуживания с нечеткими исходными данными, относящимися к сети дорог; в) разработать и проанализировать методы решения многокритериальных минисуммных задач размещения с однородными и разнородными нечеткими данными.

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

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

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

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

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

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

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

4. Алгоритмы определения оптимального места размещения одного центра скорой помощи, расположенного в пределах точечного, площадного, а также линейного объектов, с исходными данными, представленными в виде интервалов и лингвистических переменных.

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

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

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

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

Реализация результатов работы.

Результаты диссертации внедрены на Московской и Северо-Кавказской железных дорогах, в Федеральном кадастровом центре "Земля" (г. Москва), что подтверждается соответствующими актами.

Апробация работы.

Основные результаты диссертации представлены на Международной конференции по мягким вычислениям и измерениям SCM'2001 (г. Санкт-Петербург, 2001 г.), на Третьей всероссийской научной конференции молодых ученых и аспирантов "Новые информационные технологии. Разработка и аспекты применения" (Таганрог, 2000 г.).

Публикации.

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

Структура и объем диссертационной работы.

Диссертация состоит из введения и четырех глав, заключения, списка литературы из 40 наименований и приложений. Текст диссертации изложен на 190 страницах, включая 51 рисунок, 23 таблицы и 43 страницы приложений.

4.4. ВЫВОДЫ

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

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

3). Разработанная программа применяется для решения задач наилучшего размещения центров обслуживания и центров скорой помощи с учетом исходных нечетких данных для объектов железных дорог.

ЗАКЛЮЧЕНИЕ

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

В ходе выполнения работы получены следующие научные и практические результаты.

1). Рассмотрена ГИС ObjectLand и определены способы извлечения из нее необходимой информации об объектах, чьи характеристики подлежат оптимизации.

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

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

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

5). Разработана программа, реализующая алгоритмы решения однокритериальных задач размещения центров обслуживания и центров скорой помощи с учетом интервальных данных, относящихся к участкам дорог. Она позволяет работать с геоинформационной системой ObjectLand и осуществить доступ к геоинформационной базе данных ГИС, а также получить необходимые для оптимизации данные из ГБД.

Программная реализация была внедрена на объектах железных дорог.

1. Баранов Ю.Б., Берлянт A.M., Кошкарев А.В., Серапинас Б.Б., Филиппов Ю.А. Толковый словарь по геоинформатике / Под редакцией А.М.Берлянта и А.В.Кошкарева. Издание на CD-ROM. ГИС-обозрение, 1998.

2. Malczewski J. GIS and Multicriteria Decision Analysis. New York: John Wiley&Sons Inc., 1999.

3. Bernhardsen T. Geographic Information Systems. VIAK IT, 1992. - 318 p.

4. Розенберг И.Н., Гитис C.A., Святов Д.С. Геоинформационная система ObjectLand. // Сборник трудов ИПИ РАН «Системы и средства информатики». Вып. 10. Москва: Наука, 2000 г.

5. Геоинформационная система ObjectLand. Руководство пользователя.

6. DeMers M.N. Fundamentals of geographic information systems. New York: Wiley, 1997.

7. Пржиялковский В. Модели, базы данных и СУБД в информационных системах. // «Биосистемы в экстремальных условиях». М.: ВЦ РАН, 1996 г. - с. 34 - 43.

8. Кофман А. Введение в теорию нечетких множеств. / Пер. с франц. В.Б. Кузьмина; Под ред. С.И. Травкина. М.: Радио и связь, 1982 г. - 432 с.

9. Заде J1. Понятие лингвистической переменной и его применение к принятию приближенных решений. М.: Мир, 1976 г. - 168 с.

10. Zimmermann H.-J. Fuzzy Set Theory and Its Applications (2nd edition). -Boston/Dordrecht/London: Kluwer Academic Publishers, 1991. 435p.

11. Калмыков C.A., Шокин Ю.И. Методы интервального анализа. Новосибирск: Наука, 1986 г.-234 с.

12. Дюбуа Д., Прад А. Теория возможностей. / Перевод с франц. М.: Радио и связь, 1990.-328 с.

13. Кофман А., Хил Алуха X. Введение теории нечетких множеств в управление предприятиями: пер. с испанского. Минск: Выш. шк., 1992 г. - 352 с.

14. Bellman R.E., Zadeh L.A. Decision-making in a fuzzy environment. // Management Science. 1970.-Vol. 17. - P. 141-164.

15. Кини Р., Райфа X. Принятие решений при многих критериях: предпочтения и замещения. М.: Радио и связь, 1981 г. - 560 с.

16. Саати Т. Принятие решений. Метод анализа иерархий. М: Радио и Связь, 1993 г.

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

18. Bhattacharya U., Rao J.R., Tiwari R.N. Bi-criteria multi facility location problem in fuzzy environment. // Fuzzy Sets and Systems N 56, 1993. p.145-153.

19. Keeney R.L. Sitting energy facilities. San Diego: CA Academic Press, 1980.

20. Линейное и нелинейное программирование. / Под ред. И.Н. Ляшенко. Киев: Вища школа, 1975 г.

21. Борисов А. Н., Крумберг О.А., Федоров И.П. Принятие решений на основе нечетких моделей. Примеры использования. Рига: Зинатне, 1990 г. - 184 с.

22. Bershtein L.S., Dziouba Т.A. Construction of a spanning subgraph with the ordered degrees in the fuzzy bipartite graph. // Proceedings of EUFIT'98, Aachen, Germany, 1998. -p. 47-51.

23. Модели принятия решений на основе лингвистической переменной. / А.Н. Борисов, А.В. Алексеев, О.А. Крумберг и др. Рига: Зинатне, 1982. - 256с.

24. Попов В.А. Аналитическое выполнение арифметических операций над нечеткими числами. // Тезисы докладов Всесоюз. науч. семинара «Модели выбора альтернатив в нечеткой среде». Рига: Риж. политехи, ин-т, 1980. - с. 14-15.

25. Wang X., Kerre Е.Е. On Robustness and Sensitivity of an Ordering Index. // Proceedings of EUFFF97, Aachen, Germany, 1997. Vol. 1. - p. 20-23.

26. Борисов A.H., Алексеев А.В. и др. Обработка нечеткой информации в системах принятия решений. М.: Радио и связь, 1989. - 304 с.

27. Кристофидес Н. Теория графов. М.: Мир, 1978. - 432 с.

28. Розенберг И.Н., Дзюба Т.А. Размещение центров обслуживания на карте местности при нечетких расстояниях. // Сборник трудов ТРТУ «Проектирование имоделирование интеллектуальных систем». Таганрог: ТРТУ, 2000 г. - с. 79-85.

29. Рейнгольд Э., Нивергельт Ю. Део Н. Комбинаторные алгоритмы. Теория и практика. Пер. с англ. М: Мир, 1980. - 476 с.

30. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. Пер. с англ. -М: Мир, 1981. -366 с.

31. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации. Киев: Наукова Думка, 1981 г.- 288 с.

32. Stillwell W.G., Seaver D.A., Edwards W. A comparison of weight approximation techniques in multiattribute utility decision making. // Organizational Behavior and Human Performance. N 28, 1981. p. 62-77.

33. Saaty T.L. The analytic hierarchy process. New York: McGraw-Hill, 1980.

34. Мелихов А.Н., Берштейн JI.C., Коровин С.Я. Ситуационные советующие системы с нечеткой логикой. М.: Наука. Гл. ред. физ.-мат. лит., 1990. - 272 с.

35. Hakimi S.L. Optimum location of switching centres and the absolute centres and medians of a graph. // Operations Research, N12, 1964. p.450.