Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 7
Текст из файла (страница 7)
При этом выигрыш начинается до области54неразличимости задачи линейного программирования и ЭЛП. Показаныслабые места ASTM и метода балансировки, а также представлен способускорения ASTM «умным» стартом.5.8Связь моделей стабильной динамики и моделиБэкманаПолучим модель стабильной динамики в результате предельного перехода из модели Бэкмана. Будем рассматривать функции τe (ye ) видаτe (ye ) = t¯e 1 + γ y µ1!e.y¯eФункции такого вида относятся к классу BPR-функций. Для модельБэкмана полагают µ = 0.25.
Найдем σe ∗ (te ):σe ∗ (te ) = sup te ye −yeyeZt¯e 1 + γ0= sup (te − t¯e )ye − γ t¯e z µ1!y¯eZ ye 1z µye0= sup (te − t¯e )ye − t¯e γyey¯e!dz!dz1+ µ1µ ye1 + µ y¯e µ1!Аналогично рассуждая:1+ µ1∂µ ye(te − t¯e )ye − t¯e γ∂ye1 + µ y¯e µ1!11+ µye= te − t¯e − t¯e γ=01µy¯e t − t¯ µee.ye = y¯et¯e γТогда1+ µ1µ yeσe (te ) = sup (te − t¯e )ye − t¯e γ1 + µ y¯e µ1ye∗55! t − t¯ µ t − t¯eeee= y¯et¯e γ1+µВ итоге получаем:"# t − t¯ µ t − t¯hXieeeeµ→0+maxρw Tw (t)−y¯eρw Tw (t)−hȳ, t−t̄i .=maxt¯e γ1+µt≥t̄w∈We∈Ew∈W(69)XXЗапишем задачу поиска стохастического равновесия Нэша-Вардропав модели Бэкмана равновесного распределения потоков по путям:Xσe (ye ) + γXXwe∈Exp lnpxp→ miny=Θx,x∈XρwАналогичным предельным переходом, получаем задачу ЭЛП, которую можно решать с помощью ASTM:Xe∈E5.9ye t¯e + γXXwxp lnpxp→miny=Θx,x∈X,y≤ȳρwОптимальный транспортПусть даны два вектора L̃ и W̃ .
Пусть также дана матрица затратлинейного размера n. Стоимость отображения L̃ в W̃ с использованиемтранспортной матрицы (матрицы совместного распределения) X будемобозначать hX, Ci, где h·, ·i. Тогда задачуdC (L̃, W̃ ) = minhX, CiX(70)будем называть задачу нахождения оптимального транспортного расстояния между векторами L̃ и W̃ с матрицей затрат C.В мемуаре Монжа 1781 года описан вопрос о наиболее рациональныхпутях перевозки из насыпи в выемку. Была поставлена задача разбитьдва равновеликих объема на бесконечно малые частицы и сопопоставитьих между собой так, чтобы сумма произведений длин путей на объемчастиц была наименьшей.
В 1940 году задача была сведена к задаче ЛП(70) Л.В. Кантаровичем [13]. Добавив энтропийную регуляризацию, эту56задачу можно свести к задаче ЭЛП и решать с помощью ASTM.Вариацией задачи Монжа-Кантаровича является поиск расстояниямежду мерами, которые в дискретном случае задаются суммой дельтафункций с весами.
Частным случаем является задача поиска расстояниймежду изображениями, которая возникает, например, в задаче классификации. Мнемонически нахождение регуляризованного оптимальноготранспортного расстояния можно понимать как минимальную работу поперемещению одной картинки в другую.Ещё одним приложением является задача по определению распределения выборки.
То есть, нужно понимать из одного ли распределениявзяты данные или из разных. Для этого все данные оптимально транспортируются на единичный шар, и, если данные из разных распределений, то на шаре распределение будет неравномерным. Таким образом,вывод о распределении делается на сравнении расстояния между образом данных и равномерным распределением на шаре.5.10СкаляризацияПусть решается система линейных уравненийAx = b,(71)где A = {aij }ni,j=1 , aij ≥ 0, i, j = 1, n. Эта задача решается методомГаусса за O(n3 ).Домножим слева обе части (71) на диагональную матрицу D1 , получим:D1 Ax = D1 b.Представим x в виде:x = D2 y,57(72)где D2 - некоторая диагональная матрица.
Тогда имеемDAD}2 y = |{z}D1 b| 1{zÃb̃Ãy = b̃(73)Во многих приложениях стараются рассматривать дважды стохастические матрицы, поэтому получаем 2n уравнений:nXãij = 1,j = 1, ni=1nX(74)ãij = 1,i = 1, nj=1Условия на элементы матриц D1 и D2 (74) дают на самом деле 2n − 1ограничение, а оставшееся линейно-зависимо с ними. Отметим, что вданной постановке применима теорема Синкхорна, которая гласит, чтовсегда найдутся такие диагональные матрицы D1 и D2 , что преобразуютA в дважды стохастическую.Оказывается, что задача нахождения этих матриц может быть сведена к оптимизационной задаче и соответственно решена, например, ASTM.В контексте двойственной задачи (34) диагональные элементы D1 - этовектор exp( λγ ), а D2 есть ничто иное как exp( µγ ). Вектора L̃ = W̃ = 1,а матрица A из (71) совпадает c exp( −Cγ ).
Запуская алгоритм с этимиданными получим решение задачи.Таким образом, получили ещё одно приложение для применения ASTM.6Модель расщепления потоковВ данной главе будет предложена простейшая модель расщепленияпотоков для трудовых миграций (четвертый блок 4-х стадийной модели).586.1ВведениеРасщепление спроса на ежедневные трудовые передвижения, удовлетворяемого, соответственно, поездкам на личных автомобилях и на общественном транспорте (Modal Split), базируется на стандартной гипотезе, о выборе людьми способа передвижения по критерию минимумаобобщенной цены поездки (Generalized Cost), складывающейся из двухкомпонент:• денежных затрат на совершение поездки (Monetary Cost),• «немонетарных затрат» (Non-Monetary Cost), исчисляемых как произведение времени поездки на цену единицы времени горожанина(Value of Time), вообще говоря, сугубо индивидуальную для каждого.Денежные затраты на совершение поездки трактуются в практикетранспортного планирования как «траты из кармана» (Out of PocketPrice).
Для общественного транспорта это плата за проезд на тех илииных маршрутах и видах транспорта. Для автомобильной поездки – траты на моторное топливо и парковочные платежи; условно-постоянныекомпоненты затрат (амортизация транспортного средства, налоги и т.п.)в учет обычно не берутся, так как они слабо влияют на ежедневные решения горожанина по выбору способа совершения поездки. Способы оценкивремени поездки на одно и то же расстояние различается для общественного транспорта и личного автомобиля принципиальным образом. Дляобщественного транспорта это время можно считать фиксированным:применительно к внеуличным видами транспорта это очевидный факт,для наземного транспорта, работающего в общем потоке транспортныхсредств, неизбежные задержки в движении, обусловленные плотностьютрафика, учтены в маршрутных расписаниях.
Для автомобильных поездок ключевым фактором является зависимость времени поездки отплотности трафика, то есть, от количества претендентов на пользованиеулично-дорожной сетью.В данной работе я представлю результаты, полученные в процессерешении задачи моделирования расщепления транспортного потока по59типам передвижения (более подробно [2]). Будет предложена эволюционная модель поведения жителей простейшего города, состоящего из двухрайонов: спального и рабочего. У каждого жителя есть выбор, как совершить поездку: на личном транспорте или на общественном.
Отличительной особенностью является не просто описание равновесного расщепления горожан по выбору способа передвижения, но и описание процесса «нащупывания» этого равновесия. Исследуется вопрос устойчивостиравновесия.6.2Простейшая эволюционная модель расщепленияИтак, рассматривается город, состоящий из двух районов: спальногои рабочего.
Каждый день жители города (все они живут в спальномрайоне, а работают, естественно, в рабочем) ездят на работу. Каждый изних имеет личный автомобиль. Кроме того, в городе имеется развитаясеть общественного транспорта. Таким образом, каждый житель имеетдве альтернативные возможности для ежедневных трудовых поездок:личный автомобиль и общественный транспорт.Ежедневные потери пользователей личного транспорта, оценивающих единицу (минуту) своего времени в p ≥ 1 рублей, могут быть рассчитаны следующим образомAp (x) = a + pT (x) ,где a > 0 – характеризует постоянные затраты (цена топлива и т.п.),x ∈ [0, 1] – доля жителей города, использующих личный автомобиль,T (x) – функция, характеризующее то, как пользователи транспортнойсети оценивают свои временные затраты.
Обычно T (x) выбирают видаBPR-функций 1 , т.е. T (x) = T0 + γx4 .Ежедневные потери пользователей общественного транспорта, оценивающих единицу (минуту) своего времени в p ≥ 1 рублей, могут бытьрассчитаны следующим образом1Функции данного типа были введены на основе обширных эмпирических обследований аме-риканским Bureau of Public Roads (BPR) и много лет применяются в работах по транспортномупланированию и теории транспортного потока.60Bp (x) ≡ b1 + pb2 ,где b1 > 0 – характеризует постоянные затраты (цена билета и т.п.), аb2 > 0 можно понимать как время, потерянное в пути. В отличие отавтомобильной поездки, для общественного транспорта считается, чтоb2 не зависит от x (метро, электропоезда, выделенные полосы и т.п.).Будем считать, что жителей в городе много.
Они расслоены по тому,во сколько рублей каждый из них оценивает единицу своего времени (потерянного в пути). Обычно это колеблется от 1 руб/мин до 10 руб/мин(это максимальное значение будем обозначать далее через pmax ). Введемзависимость x (p) – доля жителей города, оценивающих одну минуту своего времени не меньше чем в p рублей. Эта зависимость естественным образом восстанавливается из рангового закона распределения населенияпо доходу Ципфа–Парето.
Обычно эту зависимость считают степеннойx (p) = p−η , где η выбирают из диапазона 1 – 2.Наложим теперь физически правдоподобные ограничения. Во-первых,будем считать, что денежная цена автомобильной поездки (постоянныезатраты) дороже, чем в случае общественного транспортаb1 < a.(75)Это предположение не так очевидно, как это представляется на первый взгляд.
К примеру, в Москве до введения платной парковки в 2013году «Out of Pocket Price» автомобильной поездки была заметно нижецены пересадочной поездки «метро + трамвай». Понятно, что в такихусловиях общественный транспорт предпочитало в основном «безлошадное» население. Ограничение (75) автоматически выполняется немедленно после введения платной парковки даже по самому щадящему тарифу.Во-вторых, будем считать, что «на автомобиле всегда быстрее»:T (1) < b2 .(76)Для справедливости этого предположения принципиально наличиепоправочного коэффициента, связывающего времена, потерянные на лич61ном и общественном транспорте (важно считать эти времена не равноценными).
Понятно, что в условиях затора, практически неизбежногопри x близких к единице, время поездки на метро заведомо будет меньше, чем на автомобиле T (1) > b2 . Вопрос, однако, заключается в том, чтовремя, проведенное, соответственно, в вагоне общественного транспорта и в собственном автомобиле, трудно считать равноценным. Другимисловами, под b2 понимается время, потерянное в пути на общественномтранспорте, приведенное к масштабу времени, потерянному в автомобильной поездке. Такое приведение увеличивает «физическое» время ввиду различной комфортности перемещений.Для жителей с наиболее высокой ценой времени обобщенная ценаавтомобильной поездки всегда ниже, чем на общественном транспорте:a + pmax T (1) < b1 + pmax b2 .(77)Предположим, также, что для горожан с наиболее низкой ценой времени дело обстоит прямо противоположным образом: даже при самойнизкой загрузке улично-дорожной сети обобщенная цена поездки на общественном транспорте ниже, чем у автомобильной поездки:a + T (0) > b1 + b2 .(78)Определим зависимость p (x), как корень уравнения Ap (x) = Bp , т.е.p (x) =a − b1.b2 − T (x)При условиях (75) – (78) выписанная формула корректно определяетмонотонную гладкую зависимость p (x) ∈ (1, pmax ) при x ∈ [0, 1].Представим себе такую динамику (повторяющуюся изо дня в день).Каждый житель в (k + 1)-й день смотрит на то, какая доля жителей xkиспользовала личный автомобиль в k-й день.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
