Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 3
Текст из файла (страница 3)
Для получения векторов прибытия и отправления могут быть использованы регрессионные модели на параметрах зон.Рассмотрим более подробно итерционную часть. На m-й итерации навтором шаге формируется m-я оценка матрицы корреспонденций. Дляеё построения необходимо знание о стоимости проезда между всеми парами районов - матрицы издержек. Если m 6= 1, то используются значения полученные на (m − 1)-й итерации.
Иначе используют издержки,соответствующие незагруженной сети. Если в сети есть несколько типовпередвижений, то для оценки издержек берутся средние значения длякаждой конкретной корреспонденции.О построении матрицы корреспонденций рассказано в следующейглаве. Рассмотрим, как отрабатывает модель при наличии различныхслоев спроса и типов передвижений. После первого этапа становится14известно, сколько людей выезжает из каждого района и сколько въезжает в каждый район.
Кроме того, известно распределение поездок потипам (слои спроса). Для каждого слоя спроса формируется своя матрица корреспонденций. При её формировании используется одна и та жематрица издержек, но с различными параметрами моделей построения.После этого матрицы корреспонденций суммируются. Полученная матрица корреспонденций используются для расщепления корреспонденцийпо типам передвижений. До новой итерации алгоритм работает только сэтой суммарной матрицей корреспонденций.
Далее все повторяется.Расщепление корреспонденций по типам передвижений происходитс использованием моделей дискретного выбора. На выходе (шага 3) получаются матрицы корреспонденций для каждого типа передвижений.Стоит отметить, что нет универсальных методов подбора моделей дискретного выбора. Даже при одинаковых видах транспорта в системах,если в одной из систем есть дифференциация одного из видов транспорта, например, по цвету, а в другой системе нет, то модели дискретноговыбора будут разными.Порядок шагов 2 и 3 зависит от описываемого слоя спроса. Типичнымпримером слоя спроса можно назвать «людей, совершающих выходныепоездки за покупками».
В этом слое агенты выбирают место покупокпосле выбора типа передвижений, поэтому шаги 2 и 3 можно поменятьместами.На шаге 4 происходит расчет равновесного распределения потоковдля каждого типа передвижения. Это наиболее вычислительно сложныйэтап алгоритма. На выходе этого шага получаются вектора загрузки сети(потоки по ребрам транспортного графа) и на шаге 5 матрица издержек.Последующие шаги обеспечивают создание обратной связи в модели,которая позволяет учесть взаимное влияние матрицы корреспонденций иматрицы издержек.
На шаге 2 из матрицы издержек получается матри15ца корреспонденций, а на шаге 4 используется матрица корреспонденцийдля получения матрицы издержек. При этом нужно требовать близостьэтих матриц.Алгоритм остановится при равенстве средних издержек для матрицыиздержекКритерием остановки служит равенство средних издержек для матрицы издержек, полученных по модели расчета матрицы корреспонденций, и средних издержек, полученных эмпирическим путем.3.3Модель стабильной динамикиВ данной модели выполнен первый принцип Вардропа. Задан ориентированный граф G(V, E). Каждому ребру e ∈ E ставится в соответствиепара (y¯e , t¯e ), где y¯e - максимальная пропускная способность ребра e, а t¯e минимальные временные издержки на прохождение ребра e.
Пусть вектор y - распределение потоков по рёбрам, получающееся из равновесноераспределения потоков по путям, а t - вектор временных издержек, соответствующий y. Тогда, если система находится в стабильном состоянии,то выполняются неравенства: f ≤ f¯ и t ≥ t̄. Заметим, что, если fe = f¯e ,то временные издержки агентов на ребре e могут быть бесконечно большими.Введем функцию издержек для самого быстрого маршрута из Pw :Tw (t) = minp∈PwXδep te .e∈E∗Оказывается [12], что, если y - равновесное распределение потоков вPмодели, а t∗ соответсвенно вектор временных издержек, то y ∗ = w∈W yw ∗ ,где yw ∗ - вектор распределения потока, порождаемого потокообразующейпарой, при этомyw ∗ ∈ ρw ∂Tw (t)Основные постулаты модели стабильной динамики:161. te ≥ t¯e , ye ≤ y¯e , e ∈ E;2.
(te − t¯e )(y¯e − ye ) = 0, e ∈ E;3. y ∈ ∂Pw∈Wρw Tw (t)(принцип Нэша-Вардропа).На их основании сформулируем оптимизационную задачу для поискаy ∗ и t∗ :maxt≥0;{Tw };C4hiXXC − hȳ, t − t̄i; Tw ≤δep te ; C =ρ w Tw .e∈E(11)w∈WПостроение матрицы корреспонденцийВ задаче транспортного равновесия с фиксированным спросом каж-дой корреспонденции ρij соответствует средний поток пользователей, которые должны переместиться из источника i ∈ S в сток j ∈ D.
Наиболеечасто используемыми моделями для построения матрицы корреспонденций являются гравитационная и энтропийная. Обе модели взяты изфизики.4.1Гравитационная модельГравитационная модель подсмотрена в законе тяготения: корреспонденция из района i в район j пропорциональна общему объему отправления из i, общему объему прибытия в j и некоторой функции C(tij ), зависящей от транспортного расстояния tij между районами. Транспортноерасстояние стоит понимать как меру близости между районами, которая зависит от скорости передвижения, удобства использования и других особенностей транспортной сети. Функция C(t) может иметь разныйвид в зависимости от варианта модели. В простейшем случае корреспонденция из района i в район j выглядит так:ρij = α17si dj,t2ij(12)где α > 0, si - объем выезжающих из района i, dj - объем въезжающихв район j.Однако один в один использование модели тяготения (12) имеет очевидный недостаток. Допустим поток si увеличился в 2 раза, и потокdj увеличился в два раза.
Согласно (12) корреспонденция ρij должнаувеличиться в 4 раза, что нелогично. Поэтому в модель добавляют такназываемые балансовые ограничения, вместе с которыми модификацияимеет вид:si dj,ρij =C(tij )Xρij = si ,(13)jXρij = dj ,iρij ≥ 0,i ∈ S, j ∈ DИногда функцию C(t) называют априорной вероятностью зарождения корреспонденции в зависимости от расстояния, хотя в общем случаеона не должна удовлетворять никаким условиям нормировки. В ходебольшого количества исследований для реальных городов на практикеобычно используют следующую аппроксимацию:C(t) = exp(−αtβ ),α ≥ 0, β ≥ 0,(14)где для трудовых миграций используют α ≈ 0.065, β ≈ 1.4.2Энтропийная модельЭнтропийная модель получается из мотивов второго закона термодинамики, который гласит, что любая замкнутая физическая системастремится достичь устойчивого равновесного состояния, которое характеризуется максимумом энтропии системы.Транспортную систему можно считать замкнутой системой с некоторыми допущениями.
А именно допускаем: неизменность затрат по марш18рутам и неизменность топологии улично-дорожной сети. С этими допущениями задачу определения корреспонденций ρij можно ставить какзадачу максимизации энтропии в замкнутой системе. Отмечу, что использование концепции энтропии для решения транспортных задач было впервые предложено Вильсоном [6].4.2.1Обоснование на основе обменовКаждой паре источник-сток соответствует величина корреспонденции ρij - число людей, выезжающих из района i и приезжающих в районj.
Существует множество состояний, приводящих к одной матрице корреспонденций ρ = ρij : i ∈ S, j ∈ D. Поиск значений ρij основывается напринципе нахождения максимума P (ρ) - функции, которая определяетвероятность реализации состояния системы для ρ.Пусть в некотором городе имеется n районов, Li > 0 - число жителей i-го района, Wj > 0 - число работающих в j-м районе.
ВыполненоPPN = ni=1 Li = nj=1 Wj - общее число жителей города. Значения Li иWj обычно не моделируются, и требуется иметь прогноз этих значений.Обозначим через dij (t) ≥ 0 - число жителей, живущих в i-м районе иработающих в j-ом районе в момент времени t. ∀t ≥ 0:dij (t) ≥ 0,nXdij (t) ≡ Li ,j=1nX(15)dij (t) ≡ Wj ,i=1i, j = 1, n.Основным стимулом к обмену является удобство поездки на работу:далекие поездки увеличивают транспортные издержки. Введем функцию затрат: R(t) =βT2 ,где T > 0 и β > 0. По T стоит понимать затраты19связанные с личными оценками времени и комфортности поездки пользователями транспортной системы, например, одно и то же время, проведенное в личном транспорте и общественном транспорте дают разныеиздержки. β - это настраиваемый параметр модели.Перейдем к описанию динамики.
Будем считать, что мы умеем идентифицировать жителей, например, по паспорту. Также введем некоторую политику обменов местами жительства (работы). Например, по объявлениям люди ищут более выгодные места жительства, и обмен тем вероятнее, чем выгоднее обмен для участников. Пусть в момент времени tr-й житель живет в районе k и работает в районе m, а s-й житель живетв районе p, а работает в q. Тогда вероятность того, что произойдет обменквартирами между этими жителями в промежуток времени (t; t + ∆t)(заметим, что вероятность обмена не зависит от времени):λk,m;p,q =λexp( (R(Tkm ) + R(Tpq ))|{z}Nсуммарные затраты до обмена−(R(Tpm ) + R(Tkq ))|{z}) > 0,суммарные затраты после обмена(16)где коэффициент λ характеризует интенсивность обменов.Эргодическая теорема для марковских цепей гласит, что предельноераспределение совпадает со стационарным (вне зависимости от начальной конфигурации dij (0)ni,j=1 ):lim P (dij = dij ) = Zt→inf−1nYexp(−2R(Tij )dij ) · (dij !)−1 = p({dij }ni,j=1 ),i,j=1(17)где статсумма Z находится из условия нормировки получившейсяпуассоновской вероятностной меры.
При N >> 1 распределение p({dij }ni,j=1 )√экспоненциально сконцентрированно на множестве (15) в O( N ) окрестности наиболее вероятного значения d∗ij . Оно определяется как решениезадачи энтропийно-линейного программирования:20ln p({dij }ni,j=1 )∼−nXdnijln(dij ) − βi,j=1nXdij Tij → max(18)i,j=1Стоит отметить, что ln p({dij }ni,j=1 ) есть энтропия, а отличие от гравитационной модели состоит лишь в аналитическом задании функции тяготения f (Cij ).
Эквивалентными эти модели будут при f (Cij ) = νij exp(−γCij ),где νij - вероятность выбора индивидуумом коммуникации dij .4.2.2Обоснование на основе модели равновесного распределения потоковПусть в терминах главы 2 задан ориентированный транспортныйграф G(V, E). Выберем две вершины: источник и сток. Множество путей из источника в сток обозначим через P. Пусть также xp - величинапотока по пути p ∈ P , а ye - величина потока по ребру e ∈ E, котораяудовлетворяет (7) и (8).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
