Источник: http://archvuz.ru/numbers/2010_3/07
Проблема охраны культурного наследия и памятников истории и культуры привлекает сейчас пристальное внимание общественности. Остро стоит эта проблема и в Екатеринбурге, где зафиксированы случаи незаконного сноса исторических зданий [1]. Для противодействия этой тенденции необходимо привлечь общественное внимание к данной проблеме, больше знакомить общественность с имеющимися памятниками культурного наследия, разработать специальные маршруты по оставшейся исторической застройке. Решению задачи разработки маршрута и посвящена настоящая статья.
Формулировка задачи: необходимо построить маршрут в зоне с наибольшей концентрацией памятников архитектуры так, чтобы количество осмотренных памятников было максимальным: M – искомый маршрут, – направления обхода, - количество, расположенных на данном направлении обхода. В задаче возможны два вида ограничений: строгое требуется найти маршрут минимальной длины, на котором находится наибольшее количество памятников; нестрогое требуется обойти максимальное количество памятников по маршруту, длина которого не превышает заданного значения (время обхода ограничено).
В чистом виде такая задача не относится к числу типовых, см., например [2]. Поскольку маршрут обязательно проходит по улично-дорожной сети, разумно поискать подходящие типовые задачи в теории графов.
Наиболее близкой является задача определения оптимального маршрута развозки товаров. Задача формулируется следующим образом: определить оптимальный маршрут для обхода всех вершин графа при минимизации суммы весов пройденных ребер. При использовании данного метода множеству сегментов улиц района, подлежащего обработке, сопоставляется граф Х, задаваемый по следующему правилу (матрица смежности [xij]):
Хij= 1, существует участок дороги, соединяющий перекресток i и j (длиной в 1 квартал), подлежащий обработке;
Xij= 0, не существует такого участка дороги. Также задается матрица весов для ребер С=[cij].
Метод может быть применен для нахождения оптимального маршрута для машин развозки товара, почты, общественного транспорта и других случаев минимизации весов пройденного пути с условием обязательного посещения всех вершин.
Исходная задача (1) может быть сведена к типовой задаче определения оптимального маршрута развозки при соответствующем определении весов ребер графа (улиц, по которым проходит маршрут). Для определения весов используем следующую идею: каждый памятник в городских условиях имеет определенную зону видимости. Если бы длины всех этих отрезков, которые образует пересечение зоны видимости с улично-дорожной сетью, были известны, то суммируя их, мы получили бы вес каждой улицы в графе улично-дорожной сети и могли бы определить оптимальный маршрут.
Практический же алгоритм решения более сложен и выполняется в несколько этапов. Для применения алгоритма мы используем памятники конца XIX – начала XX веков сюда входят и памятники деревянного зодчества, расположенные в центральном районе г. Екатеринбурга). При решении задачи важным является использование ГИС-технологий.
Алгоритм решения:
Создать базу данных по памятникам культурного наследия.
Путем частотного анализы выбрать перспективный район для построения маршрута.
2.1 Выбрать размер ячейки стандартизированной сетки.
2.2 Рассчитать плотность объектов культурного наследия.
2.3 Рассчитать плотность памятников деревянного зодчества.
2.4 Рассчитать плотность памятников конца XIX – начала ХХ веков.
2.5 Выявить район с наибольшей концентрацией памятников.
Построить оптимальный маршрут в пределах района.
3.1 Построить зоны видимости для объектов культурного наследия.
3.2 Определить вес («пропускную способность») каждой улицы.
3.3 Используя метод решения задачи по определению максимального потока, построить оптимальный маршрут.
Создание базы данных по памятникам культурного наследия
Первым этапом при работе с ГИС-пакетами является создание базы данных. Используя перечень объектов культурного наследия, находящихся на территории муниципального образования "город Екатеринбург" [3], была создана база данных ОКН центрального района г. Екатеринбурга. База данных содержит такие атрибутивные данные как адрес, название объекта, время постройки, значение, тип стен (памятник деревянного или каменного зодчества), этажность. База данных была привязана в среде MapInfo к географическим данным [4] путем создания слоя «памятники» на карте центрального района города Екатеринбурга.
Проведение частотного анализа для выбора перспективного района
Для проведения частотного анализа важным моментом является выбор размера сетки, для которой будет подсчитываться плотность памятников. Размер сетки выбирали на основе рекомендаций работы [5]. Он составил 120 м2.
На основе слоя «памятники» для каждой ячейки сетки было посчитано количество памятников, также отдельно для каждой клетки было посчитано количество памятников деревянного зодчества и памятников, построенных в конце XIX – начале ХХ веков. Используя полученные данные, мы смогли построить тематические карты плотности ОКН (рис. 2), памятников деревянного зодчества (рис. 3), памятников конца XIX – начала ХХ веков (рис. 4). При наложении этих слоев мы получили один район, удовлетворяющий всем условиям (рис. 5). Итак, район, благоприятный для построения маршрута, ограничен улицами Малышева, Карла Маркса, Розы Люксембург, Белинского (рис. 6).
Построение оптимального маршрута в пределах района
Для решения задачи построения оптимального района нам необходимо построить зоны видимости для объектов культурного наследия. С помощью универсального транслятора конвертируем данные из формата MapInfo TAB в ESRI Shape для работы в среде ArcGis.
В среде ArcGis с помощью модуля 3D Analist на основе данных о высотных отметках рельефа строим TIN поверхность. Добавляем к поверхности объекты нашего района. Получаем в результате модель поверхности выбранного района города (рис. 7). Создаем слой точек, из которых будем считать видимость. С помощью инструмента «видимость» строим карту зон видимости/невидимости. Она представляет собой растровый слой, для каждой ячейки которого задано значение 0 или 1 (рис. 8).
После получения растрового слоя совмещаем его с картой улично-дорожной сети и получаем величины отрезков на дорогах, вдоль которых открываются виды на памятники культурного наследия (рис. 8).
Итак, мы получили карту с зонами видимости, теперь необходимо определить вес – «пропускную способность» каждой улицы. Для этого накладываем слой с зонами видимости на слой с улицами и с помощью выборки по месторасположению отбираем те участки маршрута, которые пересекаются с зоной видимости (рис. 9). Затем рассчитываем пропускную способность для каждой улицы как отношение суммы длин отрезков, которые являются секторами видимости памятников, к общей длине. Если мы представим каждый перекресток вершиной графа, дороги представим в виде ребер, зададим направление движения транспорта, то получится ориентированный граф улично-дорожной сети (рис. 10), где каждому ребру графа сопоставлен вес – «пропускная способность».
Таким образом, получим следующую задачу: определить оптимальный маршрут для обхода всех вершин графа при максимизации суммы весов, пройденных ребер. В силу малой размерности задачи ее решение тривиально и может быть получено методом перебора. В результате мы получили маршрут 5,4,1,2,3,6 с общей суммой весов 383 из 445 возможных. Это решение задачи с нестрогими ограничениями – формулировка (3). Решением задачи о нахождении маршрута минимальной длины будет маршрут – формулировка (2), содержащий ребра с номерами 3 и 6.
Итак, мы построили оптимальный маршрут в зоне с наибольшей концентрацией памятников архитектуры конца XIX – начала XX веков так, что число осмотренных памятников максимально. Маршрут берет начало на перекрестке улиц Энгельса и Белинского, проходит по участкам улиц Белинского, Малышева, Розы Люксембург и заканчивается на перекрестке улиц Карла Маркса и Белинского. Маршрут включает 20 памятников архитектуры конца XIX – начала XX веков, всего по маршруту расположено 29 памятников архитектуры федерального, областного и местного значения. Несмотря на то, что на конечном этапе задача теории графов решалась методом перебора в силу малой размерности, общности предложенного алгоритма это обстоятельство не умаляет. Кроме того, предложенный алгоритм может использоваться в качестве методического материала в учебных занятиях.
Авторы статьи выражают благодарность заведующему кафедрой градостроительства УралГАХА, профессору Санку С.И. за обсуждение постановки задачи и преподавателю кафедры прикладной информатики Института урбанистики УралГАХА Вдовину С.А. за методическую помощь в использовании ГИС-технологий.