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

Модели выбора Предположим что перед лицом принимащим решения ЛПР стоит задача выбора одной из альтернатив. С каждой из альтернатив можно связать некоторую полезность которую ЛПР получает в случае выбора альтернативы . Если известно распределение значений то можно вычислить вероятность выбора ЛПР отдельной альтернативы. Функцию будем называть функцией выбора.

2015-09-03

73.81 KB

4 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


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

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

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

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

Введение

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

Важное значение для развития Дальневосточного региона имеет проведение саммита АТЭС в 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’).

 

Заключение

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

Литература

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

PAGE   \* MERGEFORMAT 1



 

Другие похожие работы, которые могут вас заинтересовать.
12013. Технология автоматической классификации транспортных средств на базе анализа видеоизображений, получаемых средствами видеофиксации (видеокамерами). Автоматический классификатор транспортных средств АКТС-4 1.02 MB
  Автоматический классификатор транспортных средств АКТС4. Разработка в качестве сенсора использует четыре видеокамеры видимого диапазона установленные перпендикулярно движению транспортных средств две – на въезде на полосу движения пункта взимания платы две другие – на выезде. Используемые в настоящее время в европейских странах автоматические классификаторы транспортных средств представляют собой оптические пары инфракрасных излучателей и датчиков.
3454. Модель коллективного риска (стохастическое уравнение динамики страховых резервов). Вероятность разорения страховой компании как функция начального капитала и рисковой надбавки 16.62 KB
  Вероятность разорения страховой компании как функция начального капитала и рисковой надбавки. Ставится задача: как параметры договоров величина страховой премии зависящей от страхового тарифа и капитала стартовая величина влияют на вероятность разорения компании то есть момент когда резервы станут 0 Yt – дискретная переменная – стартовый капитал страховщика у ct с – страховая премия т.надбавка C=1 из Т = Т0 Тr Тогда вероятность разорения при стартовом капитале Y0 =pYt Если Y0 0 то =1 Величину можно получить решая...
7451. Рыночное равновесие 89.02 KB
  Эластичность спроса. Взаимодействие спроса и предложения. Объём спроса это то количество товара которое потребители готовы купить при данной цене в единицу времени. Закон спроса.
9028. ПОТОКИ В СЕТЯХ 87.87 KB
  Графы и сети. Определение сети потока и разреза. В этом примере решение задачи о максимальном потоке укажет также ту часть сети дорог которая насыщена и образует узкое место в отношении потока между двумя указанными концевыми пунктами. Эта задача возникает если в сети имеется несколько источников и стоков между которыми протекают потоки различных продуктов.
21266. Химическая кинетика и равновесие 23.79 KB
  Цель работы: изучение влияние температуры на скорость реакции концентрации на сдвиг химического равновесия. Теоретическое обоснование: Скоростью химической реакции называется количество вещества вступающего в реакцию или образующегося в результате реакции за единицу времени в единице объёма для гомогенных реакций или на единице поверхности раздела фаз для гетерогенных реакций. Если за промежуток времени...
3093. Макроэкономическое равновесие в модели “AD-AS” 6.72 KB
  Совокупный спрос – это суммарное количество товаров и услуг которые намерены купить домашние хозяйства бизнес государство заграница при различном уровне цен в стране. Кривая D иллюстрирует изменение совокупного уровня всех расходов домашних хозяйств бизнеса государства и заграницы в зависимости от изменения уровня цен. Отрицательный наклон кривой D объясняется: эффектом процентной ставки если происходит повышение уровня цен в стране то происходит повышение ставки процента и как следствие – сокращение инвестиционного спроса I...
3500. Равновесие на рынке. Равновесная цена 9.97 KB
  На конкурентном рынке происходит взаимодействие спроса и предложения в результате чего устанавливается рыночное равновесие. При наложении кривых спроса и предложения определяется равновесная цена E т. оптимальное соотношение спроса и предложения т. Для определения краткосрочной или долгосрочной перспективы развития спроса и предложения вводится фактор времени.
13374. Долгосрочное равновесие конкурентной фирмы 31.87 KB
  Структура издержек типичной фирмы в краткосрочном периоде имеет вид кривых STC1 и SMC1 рис.9 Долгосрочное равновесие совершенно конкурентной отрасли Механизм формирования долгосрочного равновесия При этих условиях оптимальный объем выпуска фирмы в краткосрочном периоде составит q1 единиц. Производство данного объема обеспечивает фирме положительную экономическую прибыль поскольку рыночная цена Р1 превышает средние краткосрочные издержки фирмы SТC1.
17157. Оценка рекламы в социальных сетях 74.12 KB
  Реклама услуг с помощью сети Интернет и соц.сетях и Интернете. Задачи исследования: - ознакомить с понятием рекламы и её видами; - Рассмотреть и проанализировать роль Интернет рекламы; - Разработать анкету опроса и провести опрос респондентов.
3774. Перспективы развития СМИ в социальных сетях 98.24 KB
  Для большинства пользователей блоги - единственное доступное и безопасное средство выражения собственного мнения. Актуально это и для России, учитывая то, что в последнее время, по словам самих журналистов, давление на них усилилось
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.