Стохастическое равновесие в транспортных сетях

Ковтанюк А.А.,

Дальневосточный государственный

университет, Владивосток

Введение

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

Важное значение для развития Дальневосточного региона имеет проведение саммита АТЭС в 2012 г. во Владивостоке, где будет создана новая современная транспортная инфраструктура, на реконструкцию и развитие которой в настоящее время выделено около 122 млрд. рублей.

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

Определенный прогресс в решении таких проблем, в том числе в задаче рационального распределения средств финансирования, связан с применением математических методов, основанных на использовании модели загрузки транспортной сети. Далее остановимся на модели стохастической загрузки сети [1].

1. Модели выбора

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

(1)

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

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

(2)

В принятых обозначениях функция выбора обладает всеми свойствами вероятности, а именно

(3)

. (4)

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

Все модели дискретного выбора отличаются друг от друга предположением о типе распределения многомерной случайной величины . Наиболее известными и хорошо изученными среди таких моделей являются так называемые logit-модель и probit-модель выбора.

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

функция полезности представляет собой случайную величину, определенную как (1),
ЛПР стремится максимизировать полезность от выбора альтернативы,
независимые случайные величины подчинены распределению Гумбеля.

В сделанных предположениях вероятность выбора альтернативы рассчитывается по формуле

(5)

где , и .

Основным преимуществом logit-модели является простота ее использования для многомерных моделей дискретного выбора.

2. Стохастическая загрузка сети

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

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

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

(6)

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

(7)

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

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

(8)

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

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

(9)

где - это коэффициент масштабирования.

3. Формулировка стохастического равновесия

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

Теперь рассмотрим ситуацию, когда воспринимаемое время прохождения смоделировано не только как случайная величина, но и как зависимая от потока. Эта зависимость объясняется предположением, что среднее время в пути по каждой дуге это функция от потока по этой дуге. Другими словами , несмотря на то, что , где - это воспринимаемое время прохождение дуги , - поток по дуге .

Условия стохастического равновесия тогда можно описать следующим образом:

(10)

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

(11)

(12)

где и .

Выражение (10) описывает условие стохастического равновесия пользователя (SUE). В SUE ни один водитель не может улучшить свое воспринимаемое время прохождения, изменив маршрут. Стоит отметить, что в равновесии (SUE) измеримое время прохождения на всех используемых путях не является равным. Наоборот, время прохождения будет таким, что (10) удовлетворяет равновесию дорожных потоков.

4. Поиск равновесия

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

Рассмотрим следующую задачу на минимум:

(13)

Поток, который минимизируется в (13), также удовлетворяет SUE условиям [1]. означает, что математическое ожидание берется по заданному уровню потока .

Найдет алгоритмическое решение, применимое к задаче на минимум (13).

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

(14)

где - это значение искомого вектора (в данном случае потоки по дугам) на -ой итерации, - скаляр, представляющий величину шага, а - направление спуска, вычисленное в .

Сформулируем алгоритм.

Шаг 0: Инициализация. Представляем стохастическую загрузку сети, основанную на исходном наборе времени прохождения . Таким образом, сгенерируем набор потоков по дугам . Полагаем .

Шаг 1: Обновление. Полагаем ,.

Шаг 2: Поиск направления. Представляем стохастическую загрузку сети, основанную на текущем наборе времени прохождения по дугам . Это позволяет найти вспомогательное множество потоков по дугам .

Шаг 3: Приближение. Находим новое распределение потоков .

Шаг 4: Критерий сходимости. Если сходимость достигается, то останавливаемся. В противном случае, полагаем и переходим к шагу 1.

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

(15)

5. Численный экcперимент

Рассмотрим простую сеть, состоящую из двух дуг, соединяющих единственную пару источник-сток O-D. Для каждой дуги задана функции задержек, зависящая только от потока по данной дуге

(16)

(17)

Предположим, что общий объем потока для пары O-D равен транспортных средств в час (тс/ч). Условно назовем пути, соединяющие пару O-D ''путь 1'' и ''путь 2''. Потоки по этим путям совпадают с потоками по входящим в них дугам.

Предположим, что выбор пути основывается на logit-модели дискретного выбора. Тогда условия стохастического равновесия будут иметь вид

(18)

(19)

Пусть . Зададим последовательность размеров шагов: .

Воспользуемся программой на языке Octave, реализующей описанный выше алгоритм, и построим график, демонстрирующий величину потока по пути 1 (‘flow1’) и значение невязки (‘deviation’) на каждой итерации. В этом примере функция, описывающая величину потока по пути 1, сходится к величине .

Рис.1. Графики, демонстрирующие величину (‘values’) потока по пути 1 (‘flow1’)

и значение невязки (‘deviation’) на каждой итерации (‘iterations’).

Заключение

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

Литература

Sheffi Y. Urban Transportation Networks.- PRENTICE-HALL,INC., 1985.

PAGE \* MERGEFORMAT 1

Стохастическое равновесие в транспортных сетях