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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

В крупномасштабной транспортной сети, состоящей из большого количества «узлов» (элементов) при планировании и организации маршрутов перевозок грузов или пассажиров следует подходить с учетом многих экономических и общественных требований, предъявляемых к системе. Следует учитывать изменения, происходящие в структуре этих систем по истечении времени, называемые структурной динамикой [2]. Для описания структурной динамики лучше воспользоваться теоретико-графовыми операциями: добавление (удаление) вершины, добавление (удаление) ребра, стягивание ребра.

С помощью предфрактальных графов [2-4] моделируются структуры растущие в дискретном времени по одним и тем же правилам и состоящие из большого числа элементов.

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

Моделью такого рода карты дорог со свойством самоподобия [4] состоящей из «большого» числа составных частей является предфрактальный граф, в общем случае порожденный множеством затравок.

На рисунке 1 изображена траектория G₁, G₂, G₃ предфрактального графа G₃ порожденного множеством затравок. На рисунке 1 а представлен граф G₁ (см. рисунок 1 а), где вершины v₁, v₂, v₃ есть, к примеру, регионы (районы), а ребра e₁, e₂ - дороги между ними. Граф G₂ (см. рисунок 1 б) представляет собой карту дорог в более крупном масштабе, где в качестве вершин v_i рассматриваются населенные пункты этого региона (района). Аналогично, граф G₃ (см. рисунок 1 в) представляет собой карту дорог с масштабом позволяющим рассмотреть дороги внутри населенных пунктов. «Жирными» линиями нарисованы ребра {e₁, e₂} графа G₃, являющиеся межрегиональными трассами, линии «средней» толщины представляют дороги соединяющие населенные пункты района, а самым «тонким» линиям соответствуют муниципальные дороги. По сути, процедура рассмотрения карты дорог в более крупном масштабе представляет собой операцию ЗВЗ.

Рисунок 1. Схема дорог

транспортный граф алгоритм сеть

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

Необходимые понятия и определения

Недостающие термины и определения теории графов и предфрактальных графов можно найти в [5,4].

В основе процесса порождения предфрактального графа лежит операция замещения вершины затравкой (ЗВЗ) [3], где затравка - произвольный связный граф. Определим поэтапный процесс выполнения операции ЗВЗ. На этапе l=1 графу соответствует затравка . Далее на каждом следующем этапе к каждой вершине полученного на предыдущем шаге графа применяется операция ЗВЗ. В результате на этапе L получим граф из . Полученный граф назовем предфрактальным (n, L) - графом. В общем случае предфрактальный граф порожден множеством затравок. Для предфрактального графа ребра, появившиеся на l-ом этапе, ребрами ранга l.

Предфрактальный граф является взвешенным, если каждому его ребру поставлено в соответствие число , где - ранг ребра, a>0 и .

Постановка задачи

Рассмотрим постановку задачи в терминах теории графов [5] и многокритериальной дискретной оптимизации [6].

Пусть дан взвешенный предфрактальный граф [3] порожденный затравкой [1], |W|=n, |Q|=q.

Покрытием графа назовем подграф , , построенный из множества простых цепей , где между двумя любыми вершинами из покрытия имеется простая цепь [5]. Множество всех покрытий x обозначим через X. Покрытие - связный подграф графа . Покрытие состоит из простых цепей пересекающихся по вершинам либо ребрам.

Максимальной назовем кратчайшую цепь не являющуюся подцепью никакой другой кратчайшей цепи [5].

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

На множестве покрытий графа определим векторно-целевые функции [6]:

 (1)

(2)

где - общий вес покрытия x;

(3)

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

(4)

где N(x) - число всех максимальных цепей в покрытии x;

(5)

для всякой смешенной цепи из покрытия x.

(6)

где для любых вершин графа - расстояние в покрытии , а - расстояние на графе ;

Все покрытия {x} предфрактального графа образуют множество допустимых решений векторно-целевой функции (1) - (6).

В понятиях транспортных систем приведенные критерии векторно-целевой функции (1) имеют определенную содержательную интерпретацию.

Критерий (2) учитывает затраты пассажиров и администрации транспортной системы. При эксплуатации расходы должны быть минимальны.

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

Чтобы доехать до нужного узла транспортной системы с наименьшим числом пересадок, необходимо уменьшить общее количество маршрутов в системе. На это направлен критерий (4).

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

При эксплуатации транспортной системы часто требуется добраться до конечного пункта с наименьшим количеством остановок. Критерий (6) отражает эти требования к построению таких маршрутов.

Весам ребер предфрактального графа , могут соответствовать определенные затраты и ограничения при движении транспорта по узлам транспортной системы [7-16].

Алгоритм  выделения наибольших максимальных цепей

Пусть дан предфрактальный граф , с затравкой H=(W, Q), . Алгоритм выделяет на предфрактальном графе покрытие , все цепи которого - простые, .

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

Опишем работу алгоритма ВНМЦ.

АЛГОРИТМ ВНМЦ

Вход: граф .

Выход: остовный подграф .

Шаг 1. Найти множество всех кратчайших цепей между всеми парами вершин графа G. Удалить все те цепи из множества , которые содержатся в других. Оставшиеся цепи заключить в множество . Присвоить цепям из этого множества индексы, где длина -ой цепи меньше длины -ой цепи, . Цепи {u, v} и {v, u}, считать идентичными и включить в множество одну из них. Полученное множество будет составлять множество максимальных цепей графа G, где - диаметральная цепь [3].

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

Шаг 3. Присвоить номера всем цепям в порядке их использования при накрытии: . Пока не останется невыделенных вершин накрывать граф G.

Шаг 4. Множество цепей , использованных для накрытия графа G, образуют покрытие , состоящее из наибольших максимальных цепей . <

Теорема 1. Алгоритм ВНМЦ выделяет на графе покрытие из наибольших максимальных цепей , .

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

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

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

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

Покрытие является связным, так как состоит из наибольших максимальных цепей графа G.

В наихудшем случае, когда в алгоритме ВНМЦ при накрытии каждой цепью будет выделятся только одна новая вершина, тогда число цепей в покрытии J равно , где - число вершин в диаметральной цепи графа G. <

Теорема 2. Вычислительная сложность алгоритма ВНМЦ, выделяющего покрытие на графе , равна .

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

АЛГОРИТМ 

Вход: предфрактальный граф .

Выход: связный остовный подграф .

Шаг 1. Построить множество подграф-затравок ,, , для предфрактального графа . Все ребра предфрактального графа пронумеровать относительно построенного множества .

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

После построения множества цепей , , соединить каждую его цепь с ребрами цепей подграф-затравок . Объединять построенные цепи в множество цепей .

Шаг 3. У цепи подграф-затравки , каждое ребро , присоединять к той цепи из множества , к концу которой она инцидентна. В множество цепей внести построенную цепь.

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

Если концам двух различных цепей и инцидентны обе вершины ребра e, тогда в множество вносить цепь, образованную цепями , и ребром , только в том случае, когда концы цепей и , не инцидентные ребру e, так же не инцидентны концам других цепей из . Иначе, вносить в множество цепи, которые получились из нескольких цепей множества и ребер цепей подграф-затравок (l-1) - го ранга.

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

ШАГ 4. В результате работы ШАГА 3, после обработки цепей всех подграф-затравок, получится множество цепей . Из множества изменением нумерации получить множество , которое определяет искомый остовный подграф .

Теорема 3. Алгоритм выделяющий покрытие на предфрактальном (n, L) - графе , порожденном затравкой H=(W, Q), где , , имеет вычислительную сложность .

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

Теорема 4. Алгоритм строит покрытие , где - кратчайшие цепи одного ранга, на предфрактальном (n, L) - графе , порожденном затравкой H=(W, Q), где , , с оценкой по критерию: .

Доказательство. На предфрактальном графе , порожденном затравкой H, алгоритм строит покрытие принадлежащее множеству допустимых решений X векторно-целевой функции (1) - (6).

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

Построим нижнюю оценку. Покрытием из множества допустимых решений наименьшим по весу должно быть остовное дерево предфрактального графа . Для получения нижней оценки по критерию (2) нужно оценить вес остовного дерева минимального веса , построенного алгоритмом на предфрактальном графе . Поскольку алгоритм строит остовное дерево минимального веса , чтобы получить , , на всех подграф-затравках , то , где - общий вес остовного дерева минимального веса . Согласно определению взвешенного предфрактального графа, каждое ребро подграф-затравки ранга l не может быть меньше чем a. Тогда, a, где (n-1) - количество ребер остовного дерева [2,9]. Общий вес остовного дерева минимального веса подграф-затравок одного ранга , . Для остовного дерева минимального веса T выполняется:

.

Таким образом,

.

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

Доказательство. Для двух произвольных графов и определим операцию «склеивания» [5]. Выбираются две вершины для слияния - и . Граф , полученный из графов и слиянием вершин и в некоторую вершину так, что все ребра инцидентные вершинам и становятся инцидентными вершине , называется склеенным из графов и .

Предфрактальный граф , порожденный затравкой , таков, что смежность его старых ребер в процессе порождения не нарушалась. Тогда предфрактальный граф можно получить склеиванием всех , подграф-затравок , , [1,2]. Сначала подграф-затравка первого ранга склеивается в каждой своей вершине с подграф-затравками второго ранга, . Далее, каждый порожденный таким образом на l-ом, , шаге предфрактальный граф склеивается в каждой своей вершине с подграф-затравками , . В итоге на -ом шаге получаем предфрактальный граф , смежность старых ребер которого не нарушается.

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

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

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

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

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

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

Литература

1. Цвиркун А.Д. Управление развитием крупномасштабных систем в новых условиях // Проблемы управления. - 2003. - №1. - С. 34-43

2. Кочкаров А.А. Структурная динамика: свойства и количественные характеристики предфрактальных графов: монография / А.А. Кочкаров. - М.: Вега-Инфо, 2012. - 120 с.

3. Kochkarov A.M., Perepelitsa V.A., Sergienko I.V. Recognition of fractal graphs. Cybernetics and Systems Analysis, T.35, №4, 1999, pp. 572-585.

4. Kigami J. Analisys on fractals / Volume 143 of Cambridge Tracts in Mathematics. Cambridge University Press. Cambridge, 2001.

5. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - М.: Наука, 1990. - 383 с.

6. Перепелица В.А. Многокритериальные модели и методы для задач оптимизации на графах / В.А. Перепелица // LAP LAMBERT Academic Publication, 2013. - 333 с.

7. Лихобабин Е.Г. Моделирование транспортной сети на предфрактальных графах // Глобализация науки: проблемы и перспективы: сб. статей Междунар. науч.-практ. конф. - Уфа: РИО МЦИИ Омега Сайнс, 2015. - С. 3-6.

8. Павлов Д.А. Многокритериальная задача покрытия предфрактального графа цепями типа . Черкесск, КЧГТИ, 2003, Деп. в ВИНИТИ, №670-В2003. - С. 1-17.

9. Павлов Д.А. Многокритериальная задача покрытия фрактальных и предфрактальных графов простыми цепями. Черкесск, КЧГТА, 2004, Деп. в ВИНИТИ, №1248-В2004. - С. 1-12.

10. Павлов Д.А. Оценка покрытия предфрактального графа кратчайшими простыми цепями // VI Всероссийский симпозиум «Математическое моделирование и компьютерные технологии». Тез. докл. Кисловодск: КИЭП, 2004. - С15-16.

11. Павлов Д.А., Кочкаров А.А. Об одной многокритериальной задачи покрытия минимального веса предфрактального графа простыми пересекающимися цепями. Препринт №200. РАН САО. Нижний Архыз. 2004.-12 с.

12. Павлов Д.А., Кочкаров А.А. Узденов А.А. Об одной многокритериальной задаче выделения наибольших максимальных цепей на предфрактальных графах. Препринт №198. РАН САО. Нижний Архыз. 2004.-27 с.

13. Павлов Д.А., Кочкаров Р.А. Алгоритм с оценками построения покрытий непересекающимися простыми цепями на предфрактальном графе. Препринт №199. РАН САО. Нижний Архыз. 2004.-24 с.

14. Павлов Д.А., Салпагаров С.И. Многокритериальная задача выделения маршрутов на предфрактальном графе // Известия ТРГУ. - Таганрог: ТРГУ, 2004.

15. Павлов Д.А. Многокритериальная задача поиска оптимальных путей в крупномасштабной транспортной системе / Д.А. Павлов, Е. Г Лихобабин // Политематический сетевой электронный научный журнал Кубанского государственного аграрного университета (Научный журнал КубГАУ) [Электронный ресурс]. - Краснодар: КубГАУ, 2015. - №09 (113). - IDA [article ID]: 1131509046. - Режим доступа: http://ej.kubagro.ru/2015/09/pdf/46.pdf, 1,125 у.п.л.

16. Павлов Д.А. Особенности многокритериальной оптимизации на предфрактальных графах: задача покрытия простыми цепями: монография / Д.А. Павлов. - Краснодар: КубГАУ, 2016. - 122 с.

17. Кочкаров А.М., Кочкаров А.А., Никищенко С.П. Структурная динамика и исследование структурно-временных характеристик дискретных систем // Известия ТРТУ. Тематический выпуск «Перспективные системы и задачи управления». - Таганрог: ТРТУ, 2006. - №3. - С. 235-238.

Размещено на Allbest.ru