Некоторые алгоритмы оптимизации и визуального представления транспортных потоков
Авторы: Гордийчук Т. В., Ицков А. Г.
Источник: Публикация [Перейти]
Приведен алгоритм поиска оптимального пути на графе с переменными весами. Рассмотрены формулы построения двумерных кубических сплайнов дефекта и их вывод.
Ключевые слова: взвешенный граф, кратчайший маршрут, кубический сплайн.
В транспортных сетях крупных городов существует множество маршрутов, и редко удается определить время прибытия, зная время отправления, и наоборот. Возникает проблема реализации алгоритма нахождения кратчайшего пути при условии, что известно расписание движения общественного транспорта.
В дискретной математике существует ряд алгоритмов оптимизации на графе, в частности, алгоритмов нахождения кратчайших расстояний, но в классической теории они реализованы на статических весах, т. е. вес дуги с течением времени не меняется. На практике же, если граф – это модель движения общественного транспорта, время прохождения пути может быть разным. Это обусловлено тем, что вес дуги будет зависеть не только от скорости движения, но и от времени ожидания и стоянки маршрута.
1. Годийчук Тарас Владимирович, студент Ижевского Государственного Технического Университета.
2. Ицков Александр Григорьевич, кандидат физико-математических наук, доцент.
Проблема поиска кратчайшего пути не является новой. Существует ряд алгоритмов для решения такого рода задач [2]. В сетевом планировании рассматриваются различные проблемы оптимизации на графах со случайными весами. В исследовании операций приводятся алгоритмы поиска максимального динамического потока [3]. В данной работе рассматривается задача поиска оптимального пути на графах, у которых пропускная способность дуг меняется динамически и зависит не только от времени, но и от управления, под действием которого происходит движение.
1. Постановка задачи
Пусть заданы ориентированный граф G = (X, A), где X = {xi,x2,..., xn} – множество вершин, а A = {ai, a2,..., am} – множество дуг; множество допустимых управлений U = {Ui,U2, ...,Uk}, и выполнены следующие условия:
1) G – связный граф и для всех Xi, Xj существует путь из rv > xi, xj.
2) для всех ai существуют функции (t, и) (время выхода из дуги ai) такие, что fi: I х Ui , где I = [0, +бесконечность), Ui = {и1,и2, . . . , Uk}, где Ui – множество допустимых управлений на дуге ai;
3) для всех t0, t1 таких, что t1 > t0 и для всех и Ui выполнено fi(to,u) < fi(ti,u), i = 1, 2,... ,m (при одном и том же управлении – чем раньше произошло попадание в дугу, тем меньше будет время выхода из нее).
Тогда, если заданы начальная хн и конечная хк вершины и время начала движения Тн (время окончания движения Тк), необходимо найти путь из хн в хк – {a}j=i, значения {u} j=i и время Тк (Тн), так чтобы Тк -Тн =min.
При найденных значениях {a0} j=i, {u} j=i и известном времени начала движения Тн время окончания движения Тк.
Управление большими системами
Рассмотрим поставленную задачу на примере движения общественного транспорта. Пусть известен граф и расписание движения маршрутов. Тогда мы будем рассматривать U, как множество всевозможных маршрутов в транспортной сети, а і – множество маршрутов проходящих через дугу с номером і. Функции будут представлять собой сумму времени ожидания маршрута u (которое будет зависеть от времени попадания в начало дуги аі) и времени прохождения дуги на маршруте і.
2.1. ПОИСК ОПТИМАЛЬНОГО ВРЕМЕНИ ПРОХОЖДЕНИЯ ДУГИ
Пусть 0 – исходный
граф, 5 – множество
используемых
маршрутов, 0 – начальное время, аі –
дуга графа 0
(она задается парой чисел (і, j),
где і – номер вершины,
соответствующей началу дуги, а j – номер вершины,
соответствующей
концу дуги). Ф(к) – множество времен прибытия к-го
маршрута в 1-ую
дугу, К – множество времен отправления
к-го
маршрута из дуги с номером 1.
Наборы (к) и 0
упорядочены по возрастанию.
Если не существует такого [р], которое удовлетворяет указанным выше условиям, то к-ый маршрут не проходит через эту дугу при начальном времени 0. Зная индекс р находим время т(к1) = [р] (оптимальное время прибытия в конец дуги аі при использовании маршрута с номером к).
Для дуги аі находим все маршруты, которые проходят через нее и попадают в множество используемых маршрутов 5. Находя для каждого такого маршрута оптимальное время т(к1) и минимизируя его по к, находим минимальное время выхода т(і) из этой дуги и номер маршрута иі, на котором этот минимум достигается.
2.2. ПОИСК ОПТИМАЛЬНОГО ПУТИ
Пусть существует граф 0 (граф со взвешенными вершинами), который задан двумя таблицами: таблицей дуг и таблицей вершин – таблица маршрутов и расписание движения, которое связывает все эти таблицы. Заданы начальное время 0 и две вершины і, j (где j – вершина отправления, i – вершина прибытия, а 0 – время отправления). Построим неявно по этим данным граф 0' – граф с тем же множеством вершин, но с постоянными весами дуг. Обозначим через Сі(к)(i, j), а через С' веса дуг аі и аj графов 0 и 0' соответственно. Будем строить граф 0' по правилу:
1) В графе 0' между вершинами i и j – дуга будет только в том случае, если она является частью какого-либо пути, начинающегося на вершине і.
2) Вес дуги С', который представляет собой пару чисел (ti,tj), будет определяться из дуги аі с помощью описанного выше алгоритма.
Таким образом, зная начальную точку жіга и время 0, находим все дуги аі, выходящие из нее. По алгоритму поиска оптимального времени прохождения дуги определяем веса дуг С'. Из них находим минимальные времена ti попадания во все смежные с tj вершины и номера маршрутов на которых эти минимумы достигаются. При этом для каждой из этих вершин, записывается в качестве предшествующей вершины. Далее для всех соседей находятся все смежные вершины, за исключением предшествующей, и в качестве о берется значение tj. Если на каком-либо шаге текущее минимальное время в некоторой вершине j – меньше ранее вычисленного, то все, что было найдено из этой вершины ранее, становится неверным, а в качестве минимума берется текущее время, соответственно, изменяются предшествующая вершина и номер маршрута, на котором этот минимум был достигнут. Иначе вычисления из вершины ж- прекращаются.
Такая реализация алгоритма позволяет найти кратчайшие (в смысле времени) пути между вершиной и всеми оставшимися вершинами при начальном времени о.
Этот алгоритм не будет эффективным, поскольку при достаточно близких вершинах i и j он будет делать много лишних вычислений. Поэтому необходима его оптимизация.
Примем во внимание то обстоятельство, что если в вершине i найдено время, за которое она может быть достигнута, и текущее время в некоторой вершине j больше этого значения, то дальнейшие вычисления из этой вершины бессмысленны, поскольку в данной формулировке задачи не рассматриваются дуги с отрицательным весом.
Если же нас интересует сам путь, то по множеству предшествующих вершин его однозначно можно восстановить. Возьмем в качестве начальной вершины вершину, равную i*. Пока значение вершины, предшествующей j, не будет равно нулю, то i присваивается значение предшествующей вершины. Если после выполнения алгоритма значение ж стало равным нулю, то это говорит о том, что вершина j не достижима из i при начальном времени о. Иначе, записав все значения, которые принимала переменная p, в обратном порядке, мы получим сам путь. Поскольку для каждой вершины был не только определен минимум, но и найден номер маршрута, на котором этот минимум достигается, то можно восстановить весь путь с точностью до номера маршрута и времени прибытия во все промежуточные вершины.
Пусть заданы те же начальные условия, только 0 – время прибытия в вершину j. Необходимо найти оптимальное время отправление из вершины і. В этом случае существенных изменений в алгоритме не последует.
В алгоритме поиска оптимального пути за начальную точку берется ij; вместо дуг, выходящих из начальной вершины, ищутся дуги, входящие в эту вершину, минимум заменяется на максимум, а в проверке на прекращение вычислений знак неравенства меняется на противоположный. Если в вершине і найдено время, за которое она может быть достигнута, и текущее время в некоторой вершине j меньше этого значения, то дальнейшие вычисления из этой вершины бессмысленны.
Если в такой формулировке задачи нас интересует сам путь, то за начальную вершину берется значение j, равное i, условие выхода – сравнение i с i* и нулем. А последовательность тех значений, которые принимал i, записывается в прямом порядке.
2.3. МОДИФИКАЦИЯ ПОИСКА ОПТИМАЛЬНОГО ПУТИ
Пусть задан граф 0 (такой же, как и в предыдущем алгоритме), начальное время, вершина отправления и вершина прибытия. Проведем преобразование исходного графа.
Граф транспортной сети 0 содержит достаточно много вершин, которым инцидентно ровно два ребра. Будем заменять ориентированную цепь, содержащую такие вершины, одной дугой, для которой начальная и конечная вершины совпадают с начальной и конечной вершинами цепи. Вес дуги будет равен суммарной стоимости всех дуг, входящих в цепь. Далее действуем по вышеописанному алгоритму.
Построенные алгоритмы позволяют найти оптимальный по времени путь. Но возникает проблема иллюстрации результатов работы этих алгоритмов. Для визуального представления найденных маршрутов и различных объектов на карте города был применен метод, основанный на построении двумерных интерполяционных сплайнов. Идея метода состоит в том, что для от-рисовки пути необходимо иметь только набор узловых точек, лежащих вдоль движения маршрута, через которые будет проходить сплайн.
3. Интерполяционный кубический сплайн дефекта 1
Определение. Кубическим сплайном дефекта 1, интерполирующим на отрезке [а, b] данную функцию, называется функция д(ж) = д*(ж) := а*+6*(ж-ж*)+с*(ж-ж*)2+4(ж-ж*)3, при ж е [ж*-1 , ж*]П=1.
4. Построение двумерных сплайнов
4.1. ДВУМЕРНЫЙ НЕЗАМКНУТЫЙ КУБИЧЕСКИЙ СПЛАЙН ДЕФЕКТА 1
Пусть задан упорядоченный набор точек на плоскости р=аж1 а,р2=аж2 а,...,рп=ахп
Построим для этого набора непрерывную функцию f (p), которая проходит через эти точки и имеет непрерывные первую и вторую производные.
4.2. ДВУМЕРНЫЙ ЗАМКНУТЫЙ КУБИЧЕСКИЙ СПЛАЙН ДЕФЕКТА 1
Пусть задан упорядоченный набор точек . Построим для этого набора замкнутую кривую Б^), которая также имеет непрерывные первую и вторую производные.
Стоит заметить, что система не является трехдиагональной, в следствие чего ее приходится решать методом Гаусса, но поскольку матрица системы имеет специфический вид, то прямой ход метода Гаусса необходимо применять лишь для двух последних строк.
Управление большими системами
Заключение
Поставленная задача имеет широкое применение. Алгоритмы для решения этой задачи могут применяться не только для поиска кратчайшего пути на графе транспортных маршрутов, но и для задачи нахождения минимального по времени пути с учетом пробок, для задачи наискорейшей рассылки сообщений в сети, для планирования производства (оптимального времени завершения проекта).
Стоит заметить, что приведенные алгоритмы будут работать, если граф 0 – стохастическая модель движения общественного транспорта. То есть вес дуги будет зависеть не только от времени и управления, но и от некоторой случайной величины £, задающей отклонение от среднего времени прохождения дуги.
Если ведется статистика, то можно определить плотность распределения р (j) случайной величины £.
Стохастической моделью движения общественного транспорта, в граф 0' – граф с детерминированными весами. Далее, находя кратчайшее расстояние между любыми двумя вершинами графа 0' по описанному выше алгоритму, мы найдем наиболее вероятный наименьший по времени путь между теми же вершинами графа 0.
1. ВЕРЖБИЦКИЙ В. М. Основы численных методов. – М.: Высш. шк., 2002. – 840 с.
2. КРИСТОФИДЕС Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
3. МАЙНИКА Э. Алгоритмы оптимизации на сетях и графах. – М.: Мир, 1978. – 324 с.
SOME ALGORITHMS OF OPTIMIZATION AND VISUALIZATION OF TRAFFIC FLOWS
Taras Gordiychuk, Izhevsk state Technical University, student (tsimplex@gmail.com).
Alexander Itskov, Izhevsk state Technical University, Izhevsk, Cand.Sc., assistant professor (pmi.istu@gmail.com).
Abstract: The algorithm is given of optimal path search in a weighted graph with variable weights. The formula are derived for twodimensional cubic splines with defect 1.
Keywords: weighted graph, shortest path, cubic spline.
Статья представлена к публикации членом редакционной коллегии О. П. Кузнецовым