Содержание к диссертации
Введение
Глава 1. Анализ современного состояния в области оперативного управления маршрутизацией транспортных средств 11
1.1. Техническая постановка задачи оптимизации оперативных транспортных перевозок 11
1.2. Обзор задач поиска оптимальных путей в транспортных сетях и алгоритмов их решения 19
1.3. Обзор задач уменьшения размерности графа транспортной сети 38
Выводы по 1-й главе 44
Глава 2. Задача поиска оптимальных путей между всеми парами узлов транспортной сети 45
2.1. Алгоритм разборки-сборки графа транспортной сети 45
2.2. Доказательство получения точного оптимального решения с помощью алгоритма разборки-сборки графа транспортной сети 58
2.3. Примеры решения задачи поиска оптимальных путей с помощью алгоритма разборки-сборки графа транспортной сети 62
Выводы по 2-й главе 80
Глава 3. Поиск метрических характеристик и уменьшение размерности графа транспортной сети 82
3.1. Задача поиска метрических характеристик транспортной сети 82
3.2. Метод и алгоритм поиска центра и радиуса транспортной сети 83
3.3. Метод и алгоритм поиска диаметра транспортной сети 90
3.4. Уменьшение размерности графа транспортной сети 109
Выводы по 3-й главе 120
Глава 4. Программная реализация разработанных алгоритмов и анализ полученных результатов 122
4.1. Данные и методика тестирования 122
4.2. Поиск оптимальных путей между всеми парами узлов транспортной сети 127
4.3. Поиск метрических характеристик транспортной сети 137
4.4. Уменьшение размерности графа транспортной сети 151
4.5. Внедрение разработанного программного обеспечения 166
Выводы по 4-й главе 174
Заключение 176
Список литературы 178
- Обзор задач поиска оптимальных путей в транспортных сетях и алгоритмов их решения
- Доказательство получения точного оптимального решения с помощью алгоритма разборки-сборки графа транспортной сети
- Метод и алгоритм поиска центра и радиуса транспортной сети
- Поиск оптимальных путей между всеми парами узлов транспортной сети
Обзор задач поиска оптимальных путей в транспортных сетях и алгоритмов их решения
Формулировки задачи, отличающиеся разнообразными Классическая задача о кратчайшем пути (shortest path problem, SP) [243] в наиболее общем виде формулируется как «найти пути между элементами двух множеств вершин \\,У2 графа так, чтобы длины найденных путей являлись минимальными в данном графе между соответствующими вершинами». Задача о кратчайшем пути является одной из важнейших в алгоритмической теории графов. Существуют различные сочетаниями мощностей множеств вершин графа, между которыми требуется найти кратчайшие пути, возможностью динамического изменения весов ребер графа. Классификацию задач можно также производить по наложенным дополнительным ограничениям. Другими разновидностями задачи являются: поиск почти кратчайших путей (almost shortest path), когда требуется найти путь между вершинами, не превышающий кратчайший на некоторую величину 8 и задача к кратчайших путей, в которой ищется к различных кратчайших путей между данными вершинами.
Различный выбор множеств вершин У\У2- между которыми ищутся пути, порождает различные постановки задачи. В табл. 1.1 приведена классификация классических задач о кратчайшем пути, основанная на различии мощностей множеств Vi,V2.
Для неориентированных графов задачи пар (SSSP, SDSP), (SSMDSP, MSSDSP) и (MSSP, MDSP) являются эквивалентными. Для ориентированных графов задачи SDSP, MSSDSP и MDSP сводятся, соответственно, к задачам SSSP, SSMDSP и MSSP сменой направления у всех дуг графа. В таблице задачи (за исключением MPSP, сложность поиска решения которой зависит от мощностей множеств 1{и У2) расположены по не убыванию сложности. Решение каждой из более сложных задач позволяет получить решение для каждой из менее сложных, но с дополнительными вычислительными затратами. В постановке задачи о динамическом кратчайшем пути (задачи о кратчайшем пути в динамическом графе, dynamic shortest path, DSP) [188] учитывается возможность получения информации о кратчайших путях графа, связь между вершинами и веса ребер которого изменяются во времени.
Нестационарная задача DSP с применением техник для задачи SP разрешима за полиномиальное время на графах, обладающих свойством FIFO [155], и NP-трудна на графах этим свойством не обладающих (в том числе на графах моделирующих перемещение автотранспорта) [187]. Задачи DSP с периодическим изменением графа могут быть решены сведением к соответствующим задачам из табл. 1.1 и вычислением кратчайших путей графа «с нуля» при каждой необходимости или с использованием техники реоптимизации кратчайших путей [184]. Подходы к решению нестационарной задачи рассматриваются в [76, 93, 129], задачи с периодическим изменением графа в [89, 113].
Задачи из табл. 1.1 могут быть видоизменены для удовлетворения объективным условиям, налагаемым рассматриваемой проблемой, путем введения дополнительных ограничений. Класс таких задач принято называть задачами о кратчайшем пути с ограничениями. Ограничения могут накладываться на состав и количественные характеристики, как вершин, так и дуг (ребер) графа, обходимых в кратчайшем пути.
К наиболее известным задачам класса можно отнести следующие:
- Задачи с ограничением на множество обходимых в кратчайшем пути вершин [3, с. 139-142], как частный случай, - задача коммивояжера (traveling salesman problem) [170], когда ищется кратчайший путь от некоторой исходной вершины до нее же и обязательным прохождением в кратчайшем пути каждой вершины графа хотя бы раз.
- Задачи о кратчайшем пути с ограничением на ресурсы (shortest path problem with resource constraints, SPPRC) [144]. В этих задачах задано множество ресурсов, для каждого из которых определена функция (REF), меняющая свои значения на каждой вершине и дуге (ребре) графа; требуется найти путь минимальной длины с ограничением на ресурсы (минимальное время пути, объем загружаемых в вершинах графа грузов не превышает вместимости транспортного средства, вершина v. должна быть посещена раньше вершины v. и т.д.).
Многие из задач о кратчайшем пути с ограничениями являются гораздо более вычислительно сложными (зачастую NP-трудными [134, 152]), чем классические задачи о кратчайшем пути без ограничений. В этой связи нахождение точных решений для большинства из них при сколько-нибудь больших размерностях графов является невозможным за приемлемое время. Поэтому вместо точного решения, как правило, ведется поиск приближенного с использованием эвристических методов [123, 176, 91, 145, 65, 233].
Доказательство получения точного оптимального решения с помощью алгоритма разборки-сборки графа транспортной сети
Рассмотрим неориентированный связный или ориентированный сильно связный или односторонне связный граф. Разборка графа
Лемма 1. На каждом шаге разборки оптимальный путь между любой парой оставшихся в подграфе вершин проходит через вершины этого подграфа. Его длина равна длине оптимального пути между этими вершинами в исходном графе, а сам путь может быть восстановлен с учетом матрицы Р.
Доказательство. Выберем две разные произвольные вершины v;- в v1. Для сильно связного исходного графа существуют оптимальные пути из v.- в v1 и из Vj в Vj (обозначим их П -j и Пу). Для односторонне связного существует хотя бы один из них. Пусть это для определенности П , (для Ни меняются только индексы). Докажем лемму по индукции. Пусть для (g-l)-ro шага утверждение справедливо. Пусть на q-тош шаге удаляется вершина vi (не совпадающая с v, и v}, которые входят в подграф Gq). Возможны три варианта: 1) оптимальный путь П а не проходит через v{ и смежные с ней вершины (или только через одну из них); 2) оптимальный путь П л не проходит через Vj, но проходит через две или более смежных с ней вершин; 3) оптимальный путь П а проходит через v{ (и через пару или более смежных с ней вершин). В случае 1) удаление вершины v{ не затрагивает путь П а. В случае 2) никаких изменений участков пути, проходящих через смежные с Vj вершины, не происходит (иначе это бы противоречило оптимальности этих участков).
В случае 3) при удалении вершины vt вводится фиктивная дуга/ребро, соединяющая две смежные с vt вершины подграфа vt и v= , имеющая суммарный вес дуг/ребер \Vj, Vj) и \Vj, Vj } (равный, допустим s). В матрице М это изменение фиксируется присвоением элементу m\Vj ,Vj J значения 5, а в матрице F -присвоением элементу p[Vj ,Vj ) значения p[Vj ,Vj). Это значение либо равно vt, либо какому-то vk, если последователем в пути из Vj в vt является vk. В любом случае путь из vt в v= полностью восстанавливается с помощью матрицы F.
Если в случае 3) сумма весов дуг/ребер щ , vf\ и \yf, Vj } совпадает с весом дуги/ребра ]Vj , Vj ], то изменений в матрицах не происходит, что эквивалентно замене одного оптимального пути на другой, содержащий на одну вершину (vt) меньше, т.е подпуть Vj \Vj Vj\,Vj,\Vj,Vj \,Vj заменяется на равный по весу Существующий В ПОДГрафе ПОДПуТЬ Vj , [Vj , Vj \ Vj .
Итак, доказано, что после удаления вершины в оставшемся подграфе содержатся оптимальные пути, которые могут быть найдены каким-либо способом. При этом, если входящие в подграф дуги/ребра составные, то промежуточные вершины (не входящие в подграф) могут быть восстановлены по матрице Р.
Следствие 1. Допустим, что в конце этапа разборки в подграфе (из двух вершин) остались вершины v, и v1. Тогда в результате преобразований на этапе разборки матрица М содержит оптимальные элементы m[Vj,Vj) и m[vj,Vj).
Лемма 2. В подграфе из двух вершин v, и v1 по матрице последователей F можно восстановить соответствующие оптимальные пути между Vj и v} и между Vj и Vj (или только один из них в односторонне связном графе).
Доказательство. Если после разборки элемент p[vj,vj) содержит Vj, то это означает, что оптимальным путем из v, в v} является дуга/ребро {v/,V/ исходного графа GQ (если элементу p[vj,vj) не было присвоено имя какой-нибудь другой вершины, то между Vj И VJ не вставлялась дуга на этапе разборки.
Если элемент матрицы p[vj,vj) содержит не v}, а какую-то вершину vt , то это означает, что в оптимальном пути Vj...vj последователем вершины Vj является вершина, имя которой содержится в элементе p\yj,vj). Допустим, то оптимальный путь vjVj vj уже сформирован. Если элемент матрицы р[у, , vj) содержит не v}, а какую-то вершину vt , то проверяется значение p[Vj , vj) и т.д. В конце концов, приходим к элементу матрицы последователей p\Vj , vj) равному vj. На этом путь заканчивается. Число вершин в пути не может быть больше п, так как это число вершин в графе. Не может оказаться на пути не заполненного элемента p[vj ,vj), так как это противоречило бы лемме 1.
Это означает, что любой оптимальный путь (если он существует) может быть восстановлен по матрице последователей Р, а его длина содержится в элементе m\yh vA матрицы M. Примеры решения задачи поиска оптимальных путей с помощью алгоритма разборки-сборки графа транспортной сети Решение задачи для неориентированного графа Рассмотрим неориентированный нагруженный граф (рис. 2.13). Пример неориентированного нагруженного графа Дана матрица его весов, необходимо найти минимальные пути между каждой парой вершин. На начальном этапе множество VQ содержит все вершины графа VQ = {vhv2,v3,v4,v5,v6}.
Метод и алгоритм поиска центра и радиуса транспортной сети
Вычисляем эксцентриситет претендента є(с2)=15. Так как ги=\1 є(с2), полагаем ru = є(с2) = 15. В данном случае нижняя и верхние границы совпадают ги = г} = 15, значит, вершина c2=v6 является центральной, при этом радиус графа равен г = ги = 15.
Таким образом найден центр графа (в данном случае центр состоит из одной вершины) и его радиус. При этом задача SSSP решена для 5 вершин, против 6 решений SSSP при поиске радиуса обычным способом. В данном примере коэффициент уменьшения числа решений SSSP разработанным алгоритмом составил 5/6, однако на реальных графах большой размерности, как показывают приведенные в 4 гл. эксперименты, этот показатель значительно ниже - до 1% и менее.
Теперь найдем диаметр графа, используя алгоритм Д1. Для начальной оценки нижней dj и верхней du границ диаметра используется информация о кратчайших расстояниях от вершин, для которых решена задача SSSP во время поиска радиуса. В данном примере таких вершин пять: v\, v$, v4, v5 и v6. Обходим эти вершины по порядку и итерационно уточняем значения нижней и верхней границ диаметра, а также исключаем из рассмотрения вершины, чей эксцентриситет удовлетворяет условиям (3.11), (3.12).
Из рассмотрения при этом исключаются вершины v\ и v4, так как &vi)=u(vi) и ziy )=dJ2. Матрица границ эксцентриситетов принимает вид
Далее рассматриваем вершину v3. Эксцентриситет вершины v3 не изменяет значений нижней и верхней границ диаметра: =тах(с/Лє(Уз))=(17,17)=17, а и=тіп(с/и,2-є(уз))=(34,34)=34. Уточняем нижние и верхние границы эксцентриситетов не исключенных вершин:
Теперь рассматриваем вершину v4. Эксцентриситет вершины v4 не изменяет значений нижней и верхней границ диаметра: d=max(c4s(v4))=(17,17)=17, а =тіп( ,2-8( ))=(34,34)=34. Уточняем нижние и верхние границы эксцентриситетов не исключенных вершин:
Наконец рассматриваем вершину v . Значение нижней границы диаметра не изменяется: о і=тах(о і,є( ))=(18,15)=18, верхняя граница уменьшается: du=mm( с/ц,2-є( ))=(34,30)=30. Уточняем нижнюю и верхнюю границы эксцентриситета вершины v6:
Таким образом из рассмотрения исключены все вершины и найден диаметр графа d=d[=\8 и две периферийные вершины - v2 и vs (запомненные при нахождении эксцентриситета наибольшей величины s(V5))- В данном примере дальнейших ход алгоритма с попарной проверкой вершин оказался не нужным.
Рассматривается задача аппроксимации нагруженного графа большой размерности графом меньшей размерности с целевой функцией на минимум максимума разностей расстояний между вершинами исходного графа и соответствующими им вершинами полученного малого графа. Исследуются два варианта задачи, приводятся их формулировки в терминах задачи аппроксимации и задачи разбиения графа. Основные результаты данного подраздела опубликованы в [17, 33]. Постановка задачи и определения
Рассматривается простой связный неориентированный нагруженный граф G=(V,E,U) , где мощность множества вершин \V\ = п. Рассматриваемые задачи аппроксимации состоят в сопоставлении исходному графу G аппроксимирующего графа Ga = (Va,Ea,Ua) меньшей размерности: \Va\ = па\, где \ па п. Будем называть вершины аппроксимирующего графа метавершинами и обозначать \yf,i = 1,...,]. Метавершины могут быть подмножеством исходного множества вершин VaczV или не содержаться в V (как частично, так и полностью). Вес ребра между метавершинами vf и va, графа Ga будем обозначать ua(Vj,Vj), расстояние между этими же метавершинами ma\ybvX Будем обозначать У5Л метавершину графа Ga, аппроксимирующую вершину vi графа G. Погрешностью аппроксимации будем называть величину
Будем аппроксимировать вершины подмножеств разбиения Vj центрами этих подмножеств vc. =c(Vj). Веса ребер в графе Ga между этими центрами будем полагать равными расстояниям между центрами в исходном графе G ua[cj,Cj)= m[yc.,vc.j. Дополнительно будем требовать связность всех подграфов разбиения GJ[VJ). При выполнении всех этих условий для погрешности аппроксимации справедливо dmax /2 Ле гщ + rmi. Здесь dmax = max d( Ц), гщ максимальный, а гт - второй по величине радиусы множеств разбиения Vj. Действительно, в этом случае погрешность аппроксимации внутри подграфов не превосходит c/max 12 гт , а погрешность аппроксимации между вершинами Vj и Vj из разных подграфов не превосходит суммы расстояний от этих вершин до центров соответствующих подграфов, т.е. Ле Гщ + гт .
При такой оценке для Ае задачи разбиения графа, соответствующие поставленным задачам аппроксимации, выглядят следующим образом. Задача 1 . Дан простой связный графа неориентированный нагруженный граф G = (V,E,U) с неотрицательной вещественной весовой функцией на ребрах U:E [0,о) и вещественное число етах 0. Найти разбиение множества вершин на попарно непересекающиеся подмножества {Vi,V2,...,Vk}\ этими множествами, связны, rm + rm етах и к —» min.
Поиск оптимальных путей между всеми парами узлов транспортной сети
Тестирование алгоритма (А1) для первой задачи аппроксимации -минимизации размерности аппроксимирующего графа при заданном допуске етах - проводилось на группах графов дорожных сетей OSM120, USA120, RU. Было проведено четыре группы тестов при разных заданных допусках - 1%, 2%, 5% и 10% от величины диаметра графа. Время работы алгоритма замерялось как время нахождения аппроксимирующего графа, время поиска фактической ошибки аппроксимации при этом не учитывалось. При восстановлении связности метавершин аппроксимирующего графа относительно исходного графа в качестве алгоритма поиска кратчайших расстояний использовался алгоритм Дейкстры с двоичной кучей из библиотеки BGL. Результаты экспериментов представлены в табл. 4.17 - 4.19, во всех таблицах представлены средние по данной группе графов значения.
Данные из табл. 4.17, 4.18 позволяют сделать некоторые выводы по разработанному алгоритму для первой задачи аппроксимации.
1) В среднем при увеличении размерности графа относительная размерность аппроксимирующего графа уменьшается независимо от допуска. Это, вероятно, связано с ростом числа «степеней свободы» при росте размерности графа - возможность удаление большего числа вершин при заданном допуске.
2) Выбранный способ оценки погрешности аппроксимации графа, возникающей при удалении вершин, позволяет получать аппроксимирующие графы, фактическая погрешность которых меньше допуска в среднем не более чем на 6% при допуске равном 1% и 2% от величины диаметра графа и 27% при допуске равном 10% от диаметра графа. На рис. 4.22 и 4.23 изображены графики средней относительной размерности /Уд/Z/V/ получаемых аппроксимирующих графов при разных величинах допуска етах.
При максимальном тестируемом показателе допуска - етах равном 10% от диаметра графа - аппроксимирующие графы содержат в среднем на -76% и -93% меньше, чем исходные графы, вершин при размерности графов равных, соответственно, 103 и 2-Ю4. Из графиков на рис. 4.22 видно, что при увеличении допуска с 1% до 2% от величины диаметра графа, размерность аппроксимирующих графов уменьшается относительно размерности исходного графа в среднем на -14,5%. При таком же двукратном увеличении допуска с 5% до 10% от величины диаметра графа размерность аппроксимирующих графов уменьшается относительно размерности исходного графа в среднем лишь на -7,5%. Это можно связать с тем, что распределение длин расстояний между вершинами графов реального мира подчиняется некоторой закономерности, напоминающее по своей форме гамма-распределение. После некоторого момента дальнейшее увеличение допуска будет давать незначительный выигрыш в размерности аппроксимирующего графа.
155 Для графов групп OSM120 (рис. 4.23) наблюдаются аналогичные результаты. Допуск равный 1% от диаметра графа позволяет получить аппроксимирующие графы, содержащие в среднем на -47% и -74% меньше вершин, чем исходные графы, при размерности графов равных, соответственно, 103 и 2-Ю4. При величине допуска равной 10% от диаметра графа аппроксимирующие графы содержат в среднем на -85% и -95% меньше, чем исходные графы, вершин при размерности графов равных, соответственно, 10 и 2-Ю4. Увеличение допуска в 10 раз с 1% до 10% от величины диаметра графа позволяет уменьшить размерность аппроксимирующих графов относительно размерности исходного графа на -27,5%.
Время аппроксимации предложенным алгоритмом (табл. 4.19) сравнимо со временем работы существующих способов ее оценки и не превосходит в худшем случае 135с (на графе с 2-Ю4 вершин). При увеличении допуска наблюдается увеличение времени работы алгоритма, что связано с большим числом операций удаления вершин и ростом времени работы части алгоритма по восстановлению связности метавершин по отношению к исходному графу, связанного с ростом их размерности.
Цель поставленной нами второй задачи аппроксимации состоит в поиске аппроксимирующего графа заданной размерности к при минимизации погрешности аппроксимации Ае. В проведенных тестах предложенный итеративный алгоритм (А2) для постановки задачи в форме А2 сравнивался с алгоритмом (АР2) для постановки задачи в форме А2 , основанном на разбиении графа с использованием FM-эвристики [105, 33]. Приведем краткое описание общего алгоритма А-разбиения графа с использованием FM-эвристики и укажем основные особенности модификации алгоритма для решения задачи А2 .
Алгоритм Ж-разбиения графа для задачи А2 Алгоритм А-разбиения графа [157] состоит в улучшении начального разбиения графа с использованием FM-эвристики. В общем случае начальное разбиение графа может быть произвольным, однако, его выбор значительным образом влияет на качество конечного решения, поэтому существует ряд способов позволяющих получать «хорошие» начальные разбиения: итеративная бисекция, рост подмножеств разбиения графа и другие [156]. Во многих из способов построения начального разбиения используется элемент случайности, поэтому, как правило, производится несколько начальных разбиений и для дальнейшего улучшения выбирается разбиение обладающее лучшим качеством.