Содержание к диссертации
Введение
1. Геоинформационные системы и многокритериальное принятие решений 10
1.1. Понятие геоинформационной системы 11
1.2. Функции ГИС
1.2.1. Ввод и вывод данных 12
1.2.2. Хранение и управление данными
1.2.2.1. Геоинформационная база данных (ГБД)
1.2.2.2. Основные компоненты ГБД 15
1.2.2.3. ГИС-объекты 17
1.2.2.4. Типы атрибутивных данных 25
1.2.2.5. Слои данных 31
1.2.3. Обработка и анализ данных 32
1.2.3.1. Основные функции 32
1.2.3.2. Расширенные функции 33
1.3. Многокритериальная пространственная оптимизация 37
1.3.1. Классификация задач многокритериальной пространственной оптимизации 37
1.3.2. Основные понятия многокритериальной пространственной оптимизации 39
1.4. Операции над нечеткими данными 40
1.4.1. Операции над интервалами 41
1.4.2. Операции над нечеткими числами, описываемыми функциями 42
1.4.3. Операции над нечеткими треугольными числами 44
1.4.4. Операции над нечеткими трапециевидными числами 44
1.4.5. Операции над лингвистическими переменными 45
1.5. Выводы 46
2. Нечеткая минисуммная задача размещения центров обслуживания 47
2.1. Нечеткая однокритериальная задача размещения центров обслуживания 47
2.1.1. Понятие медианы нечеткого графа 47
2.1.1.1. Нечеткие критерии, относящиеся к сетям дорог
2.1.1.2. Нечеткие критерии, относящиеся к полигонам 52
2.1.1.3. Нечеткие критерии, относящиеся к сетям дорог и полигонам 53
2.1.2. Кратные медианы нечеткого графа
2.1.2.1. Понятие кратной медианы 55
2.1.2.2. Поиск р-медианы нечеткого графа 56
2.1.2.3. Алгоритм нахождения кратной медианы нечеткого графа, основанный на дереве поиска 59
2.2. Нечеткая многокритериальная задача размещения центров обслуживания 69
2.2.1. Постановка нечеткой многокритериальной задачи о р-медиане 69
2.2.2. Нормирование значений критериев 72
2.2.3. Критерии равной важности 76
2.2.3.1. Свертка критериев 76
2.2.4. Критерии различной важности
2.2.4.1. Определение весов критериев 77
2.2.4.2. Свертка критериев различной важности 82
2.2.5. Нахождение медиан 82
2.3. Выводы 83
3. Нечеткая минимаксная задача размещения центров скорой помощи 84
3.1. Нечеткая однокритериальная задача размещения центров скорой помощи 84
3.1.1. Понятие нечеткого центра и нечеткого радиуса графа 84
3.1.2. Выбор места размещения одного центра скорой помощи в нечетком графе 85
3.1.3. Выбор места размещения одного центра скорой помощи при лингвистическом представлении расстояний на ребрах графа 88
3.2. Абсолютный центр и радиус нечеткого графа 92
3.2.1. Понятие нечеткого абсолютного центра и радиуса графа 92
3.2.2. Алгоритм определения нечеткого абсолютного центра графа 93
3.2.3. Модифицированный метод нахождения нечеткого абсолютного центра графа 101
3.3. Нечеткие р-центры и р-радиусы графа 102
3.3.1. Понятие нечеткого кратного центра (р-центра) 103
3.3.2. Понятие нечеткого абсолютного р-центра 103
3.3.3. Определение нечетких абсолютных р-центров 104
3.3.3.1. Алгоритм определения абсолютного р-центра
нечеткого графа с заданной константой проникновения 106
3.3.3.2. Алгоритм определения абсолютного р-центра нечеткого графа с произвольной константой проникновения и с заданным числом р 120
3.3.4. Определение нечетких р-центров, расположенных в вершинах графа 121
3.4. Нечеткая многокритериальная задача размещения центров скорой помощи 124
3.5. Выводы 126
4. Пример практической реализации минисуммных и минимаксных задач размещения с учетом нечетких исходных данных 127
4.1. Краткое описание программной реализации и рассматриваемых задач 127
4.2. Модуль работы с ГИС ObjectLand. Извлечение информации из пространственной базы данных 129
4.2.1. Выбор тем. Работа с ГБД 12 9
4.2.2. Определение обслуживаемых объектов и сети дорог на карте 135
4.2.3. Переход от карты к нечеткому графу 135
4.3. Описание модуля реализации алгоритмов размещения 136
4.3.1. Определение кратчайших путей между станциями 136
4.3.2. Определение наилучшего места размещения одного центра обслуживания 137
4.3.3. Определение оптимальных мест размещения нескольких центров обслуживания 137
4.3.4. Определение наилучшего места размещения одного центра скорой помощи для случая, когда он должен быть расположен на станции 139
4.3.5. Определение наилучшего места размещения одного центра скорой помощи для случая, когда он может быть размещен на участке железной дороги, соединяющем станции 139
4.3.6. Определение оптимальных мест размещения нескольких центров скорой помощи 141
4.4. Выводы 143
Заключение 144
Список литературы
- Геоинформационная база данных (ГБД)
- Нечеткие критерии, относящиеся к сетям дорог
- Понятие нечеткого центра и нечеткого радиуса графа
- Описание модуля реализации алгоритмов размещения
Геоинформационная база данных (ГБД)
Согласно приведенной классификации, первой группой ГИС функций является ввод и вывод данных.
Ввод данных ссылается на процесс идентификации и сбора данных, необходимых для конкретного применения. Этот процесс включает в себя приобретение, переформатирование, установление геоссылок, компилирование и документирование данных. Компонент ввода переводит данные из их существующих форм в одну, которая может быть использована конкретной ГИС. Данные, требуемые определенным проектом обычно доступны в различных формах, например, аналоговые карты, таблицы, символы, цифровые множества данных, карт, аэрофотоснимков, спутниковые изображения и другие источники в цифровых форматах.
Преимущество ГИС - это эффективность интеграции широкого круга данных и информационных источников в единый формат. ГИС может использоваться не только для автоматического формирования карт, но они являются уникальным средством для интеграции и пространственного анализа множеств данных различных источников, таких как данных о населении, топографии, гидрологии, климате, транспортных сетях, общей инфраструктуре и других [3].
ГИС обычно обеспечивают альтернативные методы ввода данных, включая ввод с клавиатуры непространственных атрибутов и случайно размещенных данных, устройства ручного размещения (дигитайзеры, мышь), автоматические устройства (например, сканеры) или импортацию существующих файлов данных.
Процесс оцифровки (дигитализации) представляет собой преобразование аналоговых графических и картографических документов (твердых копий карт или графиков) в форму цифровых записей.
Сканеры переводят документ из аналогового источника в цифровую растровую форму. Они используются в ГИС для ввода карт или фото информации. Качество информации обычно зависит от качества используемого сканера и от качества сканируемого изображения. Обычно такой способ ввода данных применяют для больших карт.
Удаленный сбор информации - один из главных источников данных для ГИС. Он определяется как процесс сбора данных о поверхности Земли и окружающей среды на расстоянии, обычно с космических кораблей или со спутников.
Компонент вывода данных в ГИС обеспечивает способ представления данных или информации в форме карт, таблиц, диаграмм и т.п. Подсистема вывода отображает пользователю результаты обработки и анализа ГИС данных. Результаты могут быть представлены в твердой копии, мягкой копии или в электронном формате. Карты являются наиболее распространенным форматом, но часто сопровождаются табличным отображением. Существует множество устройств вывода: мониторы, плоттеры, принтеры. Результаты, обычно в форме карт, часто модифицируются или расширяются интерактивно через функции композиции картографических карт для добавления следующих элементов: легенд, заголовков, диаграмм, модификации цветов и символов. Функции вывода определяются нуждами пользователей, поэтому важно привлекать пользователей для определения требований вывода. Можно выделить четыре основных категории типов вывода [2]: 1) вывод текста: таблицы, списки, числа или текст в соответствии с запросами; результаты могут быть представлены в виде списка или таблицы выбранных объектов и их атрибутов; запросы могут представлять собой результирующие значения (например, суммы, расстояния, области); 2) графический вывод: карты, диаграммы, графы, трехмерные участки и т.п.; устройства диалоговой графики позволяют пользователю отметить объект и идентифицировать его с точки зрения пространственного положения; 3) цифровые данные: хранящиеся на диске или переданные по сети; 4) другие: например, звук, генерируемый компьютером и видео.
Кроме того, могут быть выделены две формы вывода данных в ГИС: отображение и преобразование.
Отображение представляет информацию пользователю ГИС в какой-либо форме (карты, таблицы и т.п.). Преобразование переводит информацию в другую компьютерную систему для последующей обработки и анализа. Цифровые данные могут быть выведены (записаны) прямо на диск или переданы в сеть, а затем введены в другую компьютерную систему. Преобразование данных играет важную роль в интегрированных ГИС и используется при многокритериальном анализе. Обработанные и проанализированные выходные данные используются в качестве входных данных в процессе пространственного многокритериального принятия решений.
Вторая группа функций ГИС - хранение данных и управление. Компонент хранения данных и управления ими включает в себя функции, необходимые для хранения и извлечения данных из базы данных (БД). Методы, использующиеся для внедрения этих функций, показывают, насколько эффективно система осуществляет операции с данными. Большинство ГИС систем являются БД-ориентированными. БД может быть определена набором неизбыточных компьютерных данных, организованных таким образом, что он может быть расширен, изменен, разделен различными пользователями. Отличием БД ГИС или геоинформационной базы данных (ГБД) от обычной БД является то, что она является представлением или моделью реальной географической системы. Рассмотрим структуру ГБД на примере ГБД ГИС ObjectLand.
Геоинформационная база данных (ГБД) - это организованная совокупность пространственных и табличных данных, которые описывают некоторую территорию и расположенные на ней объекты. [4]
Содержание ГБД не ограничивается координатами объектов. Прежде всего, объекты могут быть классифицированы по типам, геометрическим характеристикам, назначению и другим признакам. Из этого следует, что ГБД должна иметь определенную структуру, отражающую эту классификацию. Кроме того, с каждым объектом может быть связана определенная атрибутивная информация. Например, для объектов-зданий может быть задан адрес, полезная площадь, число этажей, владелец, дата ремонта и другие характеристики. Эта информация также должна храниться в составе ГБД. Атрибутивная информация может использоваться для формулировки запросов (например, «найти все двухэтажные здания») и для управления отображением объектов («раскрасить здания различными цветовыми оттенками в зависимости от числа этажей»).
Нечеткие критерии, относящиеся к сетям дорог
Пусть на выделенном участке местности, описываемом географической картой требуется расположить центр обслуживания таким образом, чтобы сумма кратчайших расстояний от этого пункта до всех остальных обслуживаемых пунктов была минимально возможной [27]. Такие задачи часто встречаются на практике: при выборе места расположения телефонной станции в телефонной сети, подстанции в электросети, складов, почтовых отделений в сети дорог и т.д. В дальнейшем остановимся на рассмотрении задачи размещения обслуживающих объектов в сети дорог.
Так как расстояние (время проезда, стоимость перевозки и т.п.) между обслуживаемыми объектами может варьироваться в определенных пределах из-за наличия светофоров, уклонов, пробок на дорогах и других факторов, то расстояние может быть представлено как нечеткое число. Кроме того, обслуживаемые пункты на карте могут иметь различную важность, может быть оценена стоимость строительства пункта обслуживания и другие параметры, которые описываются также нечетко. Тогда в таких случаях можно описать пространственные отношения объектов карты в виде нечеткого графа, и, тем самым, осуществить переход от карты местности к ее математической модели в виде нечеткого графа. При этом вершины графа будут представлять полигоны, а ребра графа - дороги, соединяющие полигоны. Оптимальное место расположения центра обслуживания на графе всегда находится в одной из его вершин (принадлежит полигону) и называется его медианой [28].
В общем случае медиана нечеткого графа определяется следующим образом. Для каждой вершины хі є X определим два числа, которые назовем нечеткими передаточными числами.
Здесь d(xn х ) - нечеткое кратчайшее расстояние, проходимое из вершины х, в вершину Xj, d(xj,xi) - нечеткое кратчайшее расстояние из вершины х1 в вершину х,, v,- -нечеткий вес вершины хп характеризующий значимость вершины относительно решаемой задачи. Нечеткие кратчайшие расстояния между вершинами графа могут быть вычислены с помощью алгоритма Дейкстры или с помощью какого-либо другого алгоритма нахождения кратчайших путей в графе. Алгоритм Дейкстры для четкого случая описан, например, в [28]. Этот алгоритм можно легко модифицировать для нечеткого случая. Прежде чем определить понятие нечеткого кратчайшего расстояния в графе, дадим определение пути в графе. Путем (маршрутом) в графе называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей [28]. При рассмотрении пути р в нечетком графе [28], представленного последовательностью дуг (а ,а2,,..,а ), за его нечеткую длину принимается нечеткое число / (р), равное сумме длин всех дуг, входящих в р , т.е.
Под кратчайшим нечетким путем (кратчайшим расстоянием) между вершинами х\ и к понимается путь р\ , для которого называется внешне-внутренней медианой [29]. При переходе от карты к нечеткому графу необходимо сначала определить его тип. Тип нечеткого графа будет определяться наличием тех или иных нечетких критериев. Можно выделить три типа нечетких критериев, подлежащих оптимизации: 1) нечеткие критерии, относящиеся к сетям дорог; 2) нечеткие критерии, относящиеся к полигонам; 3) нечеткие критерии, относящиеся к полигонам и сетям дорог. В связи с этим, будут рассмотрены три ситуации, определяемые тремя видами нечетких графов, при оптимизации размещения центров обслуживания.
В данном разделе будет рассмотрена первая ситуация: между полигонами на карте определяется нечеткое расстояние. В этом случае для описания модели используются нечеткие графы первого вида.
Нечетким графом первого вида называется граф G:=(X,F) [29], в котором X = {xj},iel = {l,2,...,n} - множество вершин графа, F = { сц. / xi,xj »} - нечеткое множество ребер графа; сГ / х,, х; - нечеткое значение атрибута рассматриваемого критерия для ребра х,., х . .
В качестве вершин графа выступают полигоны, ребра графа - это дороги, соединяющие полигоны, а веса ребер графа - это расстояния между полигонами, соединенными дорогами, заданные в виде интервалов [сіІ(хІ,х.),сіг(х„х.)].Здесь с/Дх, ,х;) и dr(x:, х ) соответственно расстояния между наиболее близкими и наиболее удаленными друг от друга точками полигонов х( и х;.
Понятие нечеткого центра и нечеткого радиуса графа
Значения ри, pl5, p2i, р45 больше, чем величина Н, поэтому ребра (xi,x4), (xj,x5), (х2,хз), (х4,х5) рассматриваться не будут, т.е. для них не надо рассчитывать значения Г, и ГД а также не надо строить графики. Поиск абсолютного нечеткого центра нужно производить только на двух ребрах графа - (хі,хз) и (х2,х5) так, как это было показано на рисунках 5.8 и 5.9.
Таким образом, используя оценки, удалось уменьшить поиск в три раза. В результате также получим, что нечеткий абсолютный центр графа лежит на ребре (х2, х5) на расстоянии [1,5; 2,5] от вершины х2. Нечеткий абсолютный радиус равен [4,5; 7,5].
Рассмотрим теперь случай поиска нескольких центров в нечетком графе. Такие центры называются нечеткими кратными центрами или р-центрами, если они расположены в вершинах графа, либо называются нечеткими абсолютными кратными центрами или абсолютными р-центрами (если они могут быть расположены на ребрах нечеткого графа.)
Пусть X р - подмножество, содержащее р вершин множества X нечеткого графа G = (X,F). Пусть d(Xp,xj) - наикратчайшее из расстояний между вершинами множества X и вершиной х1, т.е. называется нечетким р-кратным внешним центром графа G; аналогично определяется нечеткий р-кратный внутренний центр графа , (X pt).
Если не существует ограничения, что центры скорой помощи должны размещаться в вершинах графа, а допускается возможность их размещения на ребрах, то получающееся при этом множество, состоящее из р точек называется абсолютным р-центром [28]. Если исходный граф нечеткий, то и абсолютный р-центр также будет нечетким. Пусть Yp - произвольное множество каких-либо р точек на нечетком графе G и пусть граф G - неориентированный. Тогда число нечеткого разделения 7(Y ) множества Y) определяется следующим образом:
Рассмотрим сначала случай определения нечетких абсолютных р-центров, т.к. этот случай является более общим. Можно выделить две формулировки задачи нахождения нечеткого абсолютного р-центра графа. 1). Найти оптимальное размещение заданного числа р центров при условии, что расстояние или время до самого отдаленного обслуживаемого пункта от ближайшего к нему центра является минимально возможным. 2). Требуется найти абсолютный р-центр нечеткого графа с минимально возможной величиной р и такой, чтобы каждая вершина графа отстояла от одного из этих р-центров на расстоянии, не превосходящем величину А = [А,, Аг ].
Задачу, соответствующую первой формулировке, назовем задачей определения абсолютного р-центра нечеткого графа с заданным числом р, а задачу, соответствующую второй формулировке назовем задачей определения абсолютного р-центра нечеткого графа с заданной константой проникновения.
Далее будут рассмотрены алгоритмы их решения, но сначала введем следующие обозначения. Рассмотрим каждую вершину х, є X графа G и все возможные маршруты, выходящие из нее, длина которых не превышает величину S,=Alv,, (3.35) где А=[А,,АГ] - заданная константа, представляющая собой интервал. Назовем ее нечеткой константой проникновения. Пусть Qr(Xj) - множество всех интервалов у на графе G , из которых вершина хг є X достижима в пределах расстояния J, при заданном значении А . Определим область ф как множество всех интервалов у на графе G, что из каждого интервала у достижимо в пределах расстояния Si (при заданном А) одно и то же множество вершин графа G. Область ф может представлять собой, например, часть ребра. Для четкого случая область фл может представлять собой как часть ребра, так и точку.
Рассмотрим пример для четкого случая. Пусть задан граф, представленный на рисунке 3.14. Пусть веса вершин равны единице, а длины ребер равны с12 = 5, с23 = 8, с13 = 7 и пусть Х=6. @
Теперь перейдем непосредственно к алгоритмам решения задачи об абсолютном р-центре нечеткого графа. 106 Так как длины ребер представлены интервалами и нечеткая константа проникновения Я =[Я,, Яг ] - тоже интервал, то алгоритм сначала выполняется для левых границ длин ребер и интервала Я , затем отдельно для правых границ длин ребер и интервала Я . После этого определяется оптимальное решение задачи как пересечение полученных оптимальных решений для левых и правых границ. Можно также воспользоваться другим способом решения: найти центры всех интервалов, а затем решать задачу, принимая во внимание только центры интервалов.
В любом случае, на начальном этапе решения осуществляется переход от нечеткой к четкой постановке задачи о нахождении р-центра нечеткого графа. Поэтому опишем алгоритм для четкого случая, подразумевая под значением Л либо левую границу, либо правую границу, либо центр интервала Я =[Я,, Яг ].
Описание модуля реализации алгоритмов размещения
Слой «Дороги» состоит из объектов линейного типа. Каждый объект «ЖД» представляет собой участок железной дороги между двумя соседними станциями. Каждый такой объект (участок дороги) также описывается атрибутивными данными: Кодами участка, начальной и конечной станций, Протяженностью участка и другими параметрами (рис. 4.7). Совокупность данных об одном из участков дорог также образует запись, которая затем заносится и хранится в присоединенной таблице «Справочник участков» (см. рис. 4.8). В этой таблице представлена информация обо всех участках темы.
После того, как карта, соответствующая определенной теме загружена и определены все необходимые атрибутивные данные, выделяется область на карте, которая охватывает те станции и участки дорог, где необходимо наилучшим образом расположить центры скорой помощи или центры обслуживания. Объекты, попавшие в эту область, называются селектированными объектами.
Селекция в системе ObjectLand может осуществляться с помощью режимов «по прямоугольнику», «по кругу», «по полигону». Эти режимы позволяют пользователю селектировать или деселектировать сразу группу объектов, расположенных в определенной области окна, а именно - расположенных в заданном прямоугольнике, круге или полигоне (многоугольнике). При включении одного из этих режимов система позволяет задать на экране соответствующую фигуру.
Проводимая в дальнейшем оптимизация размещения центров обслуживания и центров скорой помощи будет осуществляться для объектов, попадающих в заданную область.
В данном случае селекция осуществлялась в режиме прямоугольник. Селектированные объекты показаны на рис. 4.3 красным цветом. Еще раз отметим, что селектированные объекты в данном случае могут относиться только к объектам типов «Станции» и «Железные дороги».
После того, как необходимые объекты на карте селектированы, из соответствующих таблиц ГБД выбираются записи, соответствующие только выделенным объектам «Станции» и «ЖД». Вся информация об этих объектах заносится в буфер системы ObjectLand, где она обрабатывается. Затем из таблиц выбираются необходимые значения атрибутов: названия станций и стоимости проезда между станциями. Эти данные передаются в модуль реализации алгоритмов размещения. На их основе строится модель, которая представляет собой нечеткий граф.
Нечеткий граф задается матрицей смежности его вершин. Число вершин графа соответствует числу селектированных объектов «Станции» рассматриваемой области карты. Для описываемого примера, число селектированных объектов «Станции» равно 23, при общем числе объектов данного типа 290. Вершины нечеткого представлены значениями атрибута «Название» объектов «Станции», например, Ржава, Чаплыжное, Кривцово и т.д.
Ребра графа соответствуют селектированным объектам «ЖД», представляющим участки железной дороги, соединяющие выделенные станции.
Таким образом, осуществляется переход от карты к нечеткому графу, который представлен в виде матрицы смежности вершин. Элементы этой матрицы являются исходными данными для различных задач размещения центров обслуживания и центров скорой помощи. Все задачи решаются с помощью модуля реализации алгоритмов размещения, который включен в разработанную программу оптимизации. Работа этого модуля будет рассмотрена в следующем разделе.
Как было отмечено выше, данный модуль использует данные, переданные системой ObjectLand в матрицу смежности вершин нечеткого графа. Этими данными являются наименования станций, представляющие собой вершины графа, и стоимости путей, соединяющие эти станции. Стоимости путей представлены интервалами.
Модуль реализации алгоритмов размещения позволяет выполнять следующие функции: 1) определить нечеткие кратчайшие пути между станциями; 2) определить место размещения одного центра обслуживания (простую медиану графа); 3) определить места размещения нескольких центров обслуживания; 4) определить место размещения одного центра скорой помощи (простой центр графа); 5) определить места размещения нескольких центров скорой помощи. При этом центры скорой помощи должны располагаться на станциях, либо могут быть расположены на каком-либо участке железной дороги. Рассмотрим каждую из функций в отдельности.
Практически все алгоритмы оптимизации размещения центров обслуживания и центров скорой помощи требуют определения кратчайших путей между всеми вершинами графа. Поэтому, после того, как определена матрица смежности вершин, необходимо вычислить кратчайшие пути. Их вычисление осуществляется при выборе пункта меню «Граф»/«Кратчайшие пути». В данном случае под кратчайшим путем подразумевается путь с наименьшей стоимостью. Кратчайшие пути определяются с помощью алгоритма Дейкстры, обобщенного на случай интервальных значений стоимостей ребер графа. В результате получим матрицу наименьших стоимостей D, которую можно увидеть на
Как было отмечено в главе 2, оптимальное место расположения одного центра обслуживания (простая медиана графа), определяется из матрицы кратчайших путей D. При нажатии кнопок «Простая медиана» и «Выполнить» запускается функция определения медианы и на экран выдается ответ (см. рис. 4.9).
Для рассматриваемого нами примера простая медиана нечеткого графа находится в вершине с именем «Беленихино». То есть, оптимальное место расположения центра обслуживания будет на станции «Беленихино». Тогда суммарная стоимость проезда от этой станции ко всем остальным станциям участка будет минимальной.
