9. Связность линейных объектов: гамма- индекс и альфа-индекс

Важным аспектом пространственного расположения линий является их способность

образовывать сети. Сети имеют самые разнообразные формы, как естественные, так и соз-

данные человеком. Среди них: автомобильные и железные дороги, телефонные линии, реки,

даже лесозащитные полосы могут играть роль сети, позволяющей мелким млекопитаю-

щим перемещаться по ландшафту, — список можно долго продолжать. И хотя мы можем

интересоваться плотностью и ориентацией объектов, образующих сеть, нам нужна также и15

возможность анализировать реальные связи, образованные этими объектами и степень свя-

занности между различными точками сети. Вы наверняка сталкивались с ситуациями, ко-

гда в городе нет прямой дороги от места до места, и приходится ехать кружным путем. Здесь

мы сталкиваемся с недостатком связности (connectivity) в сети.

Связность является мерой сложности сети. Имеются несколько методов для опре-

деления этой характеристики. Наиболее общими являются гамма-индекс (gamma index) и

альфа-индекс (alpha index).

Гамма-индекс Y является отношением числа существующих связей

между парами узлов сети, L, к максимально возможному числу связей в том

же наборе узлов, Lmax.

Очевидно, что векторно-топологическая модель данных лучше всего подходит для

этих вычислений. Определить же Lmax не так трудно, как может поначалу показаться, оно

однозначно определяется числом узлов V. Например, если мы имеем три узла, то возможны

лишь три связи (Рисунок 8). Если мы добавим еще один узел, то сможем добавить еще три

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

максимальное число связей будет каждый раз увеличиваться на три. То есть,

Lmax = 3(V - 2).

Гамма-индекс тогда определяется как:

Y = L / Lmax = L / 3(V-2)

Он принимает значения от 0 (нет ни одной связи) до 1 (все возможные связи присут-

ствуют).

Рисунок 8 показывает два варианта сети с 16-ю узлами. На одном рисунке (а) имеется

15 связей, что дает связность Y = 15 / 3(16-2) = 0.36. На другом рисунке (b) имеется 20 свя-

зей, поэтому Y = 20 / 3(16-2) = 0.48. Образно говоря, первая сеть связна примерно на треть, а

вторая — наполовину.

Большее количество связей в сети облегчает передвижение по ней, что важно, напри-

мер, для специалистов по транспортному планированию.

Важной характеристикой сетей помимо связности является наличие в ней контуров,

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

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

транзитного транспорта на уличную сеть.

Рисунок 8. Гамма-индекс. Две различные сети на основе одного набора узлов: а) с

минимальной связностью и без контуров, b) с большей связностью и контурами, дающими

альтернативные маршруты перемещения по сети. 16

В качестве меры соединенности узлов контурами альтернативных

маршрутов (circuitry) используется так называемый альфа-индекс (а).

Он является отношением имеющегося в сети числа контуров к максимально воз-

можному числу контуров в этой сети.

а = К/Кmax

Известно, что сеть без контуров имеет связей (L) на одну меньше, чем число узлов (V):

L = V - 1

На Рисунке 8а вы можете видеть такую сеть, — в ней 16 узлов и 15 связей. Она обла-

дает минимальной связностью, в том смысле, что в ней имеется наименьшее возможное чис-

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

связь.

Добавление какой-либо связи создает контур, т. е. когда сеть содержит контуры L

> V - 1. Число же имеющихся контуров можно определить как L-(V-1).

Далее, так как максимальное число связей в сети определяется как 3(V -2), а мини-

мальное (без потери связности) как V - 1, то максимальное число контуров будет 3(V - 2) -

(V - 1), т.е. 2V - 5. Отсюда альфа-индекс :

а = (L - (V - 1)) / (2V - 5)

Диапазон значений альфа-индекса - от 0 (сеть без контуров) до 1 (сеть с макси-

мальным числом контуров).

Теперь мы можем вычислить альфа-индекс для сетей на Рисунке 8:

а = (15-16+ 1)/(2х16-5) = 0

а = (20-16 + 1)/(2х16-5) = 0.19

Таким образом, в сети на Рисунке 8а есть только один вариант для перемещения из

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

разной длины.

Поскольку для создания контуров требуется добавление новых связей, вполне воз-

можно рассматривать альфа-индекс как альтернативную меру связности. Но так как эти

два индекса дают разные взгляды на сеть, будет более уместным объединить их некоторым

образом для создания общей меры сложности сети (network complexity).

Для вычисления данных индексов требуется использование векторной ГИС. Это тре-

бование подчеркивается тем обстоятельством, что вся эта статистика имеет топологическую

основу теории графов, где гораздо важнее связность узлов, нежели их расположение или

длины и формы линий, связывающих их.

Для транспортного моделирования нам нужно знать все-таки больше, чем просто па-

раметры связности. Здесь имеют значение длины связей между узлами, возможные направ-

ления движения по этим линиям, значения сопротивления движению (импеданса). Вдобавок,

существуют и другие простые индексы, пришедшие из теорий транспортировки и связи, ко-

торые также характеризуют связность сетей. Например, возможно определение интенсив-

ности связности (linkage intensity) для каждого узла, числа альтернативных маршрутов

между заданными узлами, поиск центрального узла (central place), т.е. такого, который

имеет наибольшее число связей, а также построение регионов на основе связности и доступ-

ности. И все это можно сочетать друг с другом и с другими характеристиками линий — рас-

положением, ориентацией, дисперсией — для получения более полной картины сети.

МОДЕЛЬ ГРАВИТАЦИИ

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

быть неодинаковой. Но подумайте о городах. Крупные города по сравнению с мелкими дают

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

нований и т. д. Поэтому они привлекают больше людей. И города - не единственный пример,

когда размер имеет значение. Например, большое озеро привлекает больше водоплавающих

птиц, нежели маленький пруд.

Оба примера показывают, что более крупные объекты привлекают к себе большую

активность, будь то птичью, или человечью. Размер такого притяжения может представлять-

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

масса, тем больше сила притяжения между ним и его соседями.

Перенося идею гравитационного притяжения на взаимодействие между узлами по-

крытия ГИС, мы получим модель гравитации (gravity model), которая в общем виде выра-

жается как:

где Lij

- величина взаимодействия между узлами i и j; Pi

- величина узла i; Pj- величина

узла j; d - расстояние между узлами; К - константа, определяемая природой взаимодейст-

вующих объектов.

Величины узлов могут быть представлены такими их параметрами, как потребность

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

водоема для водных птиц.

Мы видим, что чем больше величины узлов, тем больше сила взаимодействия

между ними, и что с ростом расстояния между узлами сила взаимодействия уменьшает-

ся. На примере города мы можем сказать, что чем больше город, тем более он привлека-

телен для торговли. С другой стороны, если город находится далеко от вас, вряд ли вы в

него поедете, даже несмотря на возможную выгоду от сделки. [Как говорит русская пого-

ворка, "за рекой телушка — полушка, да рубль перевоз".]

Существуют многие варианты данной простой модели притяжения между точками,

как в растровых, так и в векторных системах. И хотя большинство из них используется для

экономического анализа размещения объектов (также как и полигоны Тиссена), возможно и

другое их применение. Исследователи могут использовать их для описания пассажиропото-

ка между городами, объема телефонных вызовов, потоков птиц и семян, которые распро-

страняются птицами между участками леса. В общем, любые потоки между узлами различ-

ной величины могут анализироваться с применением модели гравитации.

МАРШРУТИЗАЦИЯ И АЛЛОКАЦИЯ

Среди наиболее применяемых приложений сетей в ГИС являются родственные задачи

маршрутизации и размещения (аллокации) (routing and allocation).

Простейший вариант маршрутизации включает поиск кратчайшего маршрута

между двумя узлами сети (Рисунок 9). Учитывая, что узлам могут присваиваться весовые

коэффициенты (как в модели гравитации), возможен вариант маршрутизации от некоторой

заданной точки до ближайшей точки с максимальным весом (например, максимальным

спросом на товар).

Каждой связи в сети может быть присвоено значение импеданса (сопротивления,

стоимости), во многом наподобие фрикционной поверхности, но налагаемого только на саму

эту линию. Значение импеданса может быть связано, например, с ограничением скорости

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

на ремонт. Используя нарастающее расстояние (accumulated distance), с учетом как геомет-

рического расстояния, так и значений импеданса, может строиться наиболее эффективный

маршрут, т.е. маршрут наименьшей стоимости, а не просто кратчайший. Узлам также мо-18

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

при определении функциональных расстояний на поверхности и стоимости передвижения,

все это требует априорного знания свойств улиц, перекрестков и других узлов. И нередко

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

Рисунок 9. Кратчайший маршрут в сети. Результат работы алгоритма поиска крат-

чайшего маршрута в простой дорожной сети.

Хотя маршрутизация в принципе может выполняться на растре, она гораздо легче

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

других воспроизводит характеристики графов. Вам также следует знать, что вследствие на-

личия контуров в сети, возможны альтернативные маршруты между двумя заданными точ-

ками, а с учетом различных ограничивающих факторов, как статических (свойства дороги),

так и динамических (наличие уже существующего движения), плюс различные виды опти-

мизации маршрутов (посещение набора узлов в заданном порядке, оптимизация использова-

ния парка транспортных средств, организация работы по обслуживанию множеств постав-

щиков и потребителей грузов, выравнивание нагрузки на дорожную сеть и т. д.) тема мар-

шрутизации заслуживает отдельной толстой книги.

Аллокация (allocation, размещение) это процесс, который может использоваться для

определения, например, положения нового супермаркета, территориального покрытия стан-

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

этом используется сетевая структура в векторной ГИС. Идея состоит в распространении

возможностей заданной службы по сети. Каждая связь (или каждый узел) сети имеет опре-

деленное число обслуживаемых элементов. Например, каждый отрезок улицы имеет некото-

рое число домов, к которым подается вода. Каждый дом может рассматриваться также как

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

ба или каждый торговый центр имеют определенную максимальную нагрузку и предельное

расстояние обслуживания, а срочные службы — ограничение по времени на обслуживание

одного обращения; все это также учитывается при построении зон обслуживания (Рисунок

10). Если бы дорожная сеть была совершенно однородна (без импеданса, запретов, ограни-

чений скорости и т.д.) аллокация была бы просто расчитана.

Например, если бы мы проводили аллокацию для распространителей газет, так чтобы

машина каждого проходила только определенное число километров, программе пришлось

бы просто подсчитывать километры, когда маршрут расширяется от начальной точки, пока

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

вующие коды атрибутов распространителей. 19

Как вы могли догадаться, большинство реальных задач аллокации довольно сложны,

и на эту тему написаны серьезные труды. Здесь только следует еще упомянуть о связи поч-

товых адресов с линейными объектами, образующими покрытие уличной сети. Установ-

ление такого соответствия называется адресным геокодированием (address matching). Оно

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

динатам объекта или топологическим координатам в сети, а также выполнять обратные пре-

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

в то время как ГИС оперирует координатами и топологией.

.

Рисунок 10. Аллокация в сети. Приписывание улиц, каждая из которых имеет по 10 до-

мов к центру обслуживания, способному надежно обслуживать только 100 домов.