Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 2
Текст из файла (страница 2)
полная информированность участников движения о ситуации в транспортной сети2. несущественное влияние одного участника на состояние транспортной сетиПервое допущение не кажется критичными, учитывая нынешнее развитие online-карт и навигаторов. Второе также является довольно естественным, если не учитывать аварийные ситуации и грузовые автомобили на некоторых участках дорог.Второй принцип предполагает централизированное управление движением в дорожной сети. Примером может служить движение маршрутизированного транспорта. Однако наибольшую нагрузку дают именнолегковые автомобили, совершая, так называемые, «маятниковые» поездки (дом-работа-дом). Кроме того, естественно предполагать эгоизм водителей. Поэтому при исследовании загрузки транспортной сети будемследовать первому принципу Вардропа.2.1Формальное описаниеОпишем транспортную сеть в виде ориентированного графа G(V, E),где V - множество вершин, а E - множество дуг сети.
Вершинам соответствуют, например, перекрестки, а дугам - дороги. Направлению дугисоответствует ход следования автотранспорта. Назовем множество вершин S ∈ V , порождающих потоки, источниками, а множество вершинD ∈ V , поглощающих потоки, - стоками. Для задачи моделированиятрудовых миграций источниками являются спальные районы, а стоками- деловые районы города.
Запишем множество потокообразующих пар ввиде декартова произведения:8W = S × D = w = (i, j) : i ∈ S, j ∈ D.Путём из i в j в сети G назовём последовательность дуг:e1 = (i → k1 ), e2 = (k1 → k2 ), . . . , (km → j),где eq ∈ E∀q = 1, m.Обозначим через Pw множество альтернативных маршрутов, связывающих пару w ∈ W . А совокупность всех путей сети G обозначим черезP = ∪Pw . Введем ещё обозначение xp - величина потока, идущего по пути p ∈ P . Тогда загрузка всей сети задаётся вектором x = (xp : p ∈ P ).Введем удельные затраты Cp пользователей, выбравших путь p. В основном рассматриваются затраты финансовые и временные. Так как наних может влиять загрузка других путей, то, вообще говоря, это функция загрузки сети Cp = Cp (x).По первому принципу Вардропа водители выбирают путь с минимальными транспортными издержками, поэтому ненулевой поток x̄p попути p ∈ Pw означает, что затраты на этом пути минимальны:если x̄p > 0,то Cp (x̄) = min Cq (x̄) = uw (x̄),q∈Pw(5)где uw (x̄) - минимальные транспортные затраты по маршрутам, соединяющим пару w ∈ W , при загрузке сети, определяемой вектором x̄.Соотношения (5) задают условия равновесия транспортных потоков.
Потоки x̄ = (x̄p : p ∈ P ), удовлетворяющие (5), называются равновесными. Введём ограничения на допустимость потоков. Для каждойпары источник-сток w = (i, j) ∈ W существует на перевозку ρw - общий объем пользователей, перемещающихся из пункта i в пункт j. Набор(ρw : w ∈ W ) называется матрицей корреспонденций.9Для транспортных задач потоки должны удовлетворять балансовымограничениям и быть неотрицательными. Для трудовых миграций естественно полагать, что объемы корреспонденций стационарны, поэтомудопустимое множество потоковых переменных будет иметь вид:X=x≥0:Xx p = ρw , w ∈ W .(6)p∈PwПроблема поиска равновесных потоков x̄ ∈ X(x̄) называется задачейтранспортного равновесия с эластичным спросом.
При заданных корреспонденциях проблема поиска равновесных потоков x̄ ∈ X называетсязадачей транспортного равновесия с фиксированным спросом. Основнойподход к решению задач транспортного равновесия - это сведение к эквивалентной оптимизационной задаче или к вариационному неравенству.В данной работе остановимся на первом подходе.2.2Численные методыОбозначим через ye величину потока по дуге e ∈ E. Зная распределение потоков по путям можно рассчитать загрузку каждой дуги:ye =Xθep xp ,(7)p∈Pгде1,θep =0,если путь p проходит через дугу e,(8)иначеПодход к построению алгоритмов для поиска равновесных потоковзависит от того, в каком пространстве переменных рассматривается исходная задача. Если равновесие моделируется через потоковые переменные по дугам ye , то алгоритмы будут дуговыми. Если же переменные потоки по путям xp , то алгоритмы называются маршрутными.Поиск равновесия в маршрутных переменных xp имеет ряд преимуществ, например, зная распределение потоков по маршрутам xp и, ис10пользуя соотношение (7), всегда можно установить загрузку по дугам.Обратное преобразование, конечно же, не однозначно.Ещё одним преимуществом решения задачи в потоковых переменныхпо путям xp является возможность непосредственной проверки условия(5), при поиске равновесия в переменных yp такой возможности нет.
Ещёодним аргументом в пользу потоковых переменных по путям являетсятот факт, что функция затрат Cp (x) может складываться не только иззатрат на перемещение по дугам, но тогда переформулировка условияравновесия (5) в терминах yp невозможна.Существенным недостатком такого подхода можно назвать необходимость априорного задания множества всех возможных маршрутов Pв сети. Для крупных городов эта задача очень трудоемка, поэтому напрактике зачастую оставляют лишь наиболее вероятные маршруты.2.3Проекционные методы решения задачи транспортного равновесияПусть задано отображение G : X → Rn . В самой простой формепроекционный метод строит последовательность xk ∈ X, задающуюсяреккурентным соотношением:xk+1 = πX (xk − λk G(xk )),λk > 0,k = 0, 1, 2, .
. .(9)В данной работе не будем останавливаться на условиях сходимостиэтого процесса. Скажем лишь, что для гарантированной сходимости ставятся достаточно жёсткие ограничения на выбор шага λk , что на практике делает скорость сходимости очень медленной.Ускорением (9) может служить так называемый экстраградиентныйметод:11uk = πX (xk − λk G(xk )),xk+1 = πX (xk − λk G(uk )),λk > 0,(10)k = 0, 1, .
. .Сходимость этого метода гарантируется, например, при монотонности и липшецовости отображения G с константой L, λk ∈ (0, L1 ).О том, как борются с недостатками решения задачи транспортногоравновесия в переменных потока по путям, применяя проекционные методы, можно прочитать в [1].3Равновесное распределение потоковЭто один из шагов четырехстадийной модели расчёта транспортногоспроса. Выделим две модели, а позже опишем их связь и покажем, каквозникает задача ЭЛП.3.1Модель БэкманаВходные параметры модели описаны в разделах 2.1 и 2.2.
Введемудельные затраты на проезд по дуге e - τe (ye ). Обычно их полагают возрастающими, гладкими функциями от ye . Напомним, что Cp (x) - временные или финансовые на проезд по пути p. ПолагаемCp (x) =Xτe (ye (x))δep .e∈EПусть известно количество перемещений в единицу времени ρw , соответсвующее корреспонденции w. Тогда вектор x должен лежать в множестве (6).
Подробно о построении модели и её эволюционном выводеможно найти в [12].Заметим, что12∂Cq∂Cp X ∂τe ∂ye X∂τe=δep=δep δeq=∂xq∂ye ∂xq∂ye∂xpe∈Ee∈Eпоэтому равновесное распределение потоков определяется как решеRyPния оптимизационной задачи f (x) → minx∈X , где f (x) = e∈E 0 e τe (z)dz.3.2Обзор подходов к построению многостадийныхмоделей транспортных потоковКак говорилось во введении, наиболее часто используемым подходомк моделированию транспортных систем является «4-стадийная» модель.В рамках этой модели ведется поиск равновесия спроса и предложенияна перемещения. При этом рассматривается общая задача генерации трафика, его распределения по типам передвижения и распределение помаршрутам.Равновесие ищется последовательной прогонкой четырех этапов, последние три и из которых отрабатывают циклично для получения самосогласованных результатов.
На вход модели подается транспортныйграф с заданными функциями издержек, разделение города на транспортные зоны с их параметрами (количество рабочих мест, мест дляжительства). На выходе модели получаем оценку матрицы корреспонденций для каждого типа передвижений, загрузку элементов сети и издержки, соответствующие данному уровню загрузки.
В силу огромныхразмерностей задачи в модели обычно используют три типа передвижений (и их комбинации): личный транспорт, общественный транспорт ипешие передвижения.Алгоритм расчета «4-стадийной» модели можно записать так:1. На первом шаге из данных о транспортных зонах, которые получают, например, из социальных опросов, находят вектора отправления и прибытия для всех транспортных зон (вектора L̄ и W̄ ).132.
Высчитывается первая оценка матрицы корреспонденций (с помощью гравитационной или энтропийной модели).3. Рассчитывается расщепление корреспонденций по типам передвижений.4. Для каждого типа передвижений рассчитывается распределениепотоков по маршрутам.5. Находится оценка матрицы издержек корреспонденций и векторзагрузки сети.6. Проверяется критерий остановки.7. Если критерий выполнен, то останавливаются с найденным решением.8. Если критерий не выполнен, то возвращаются на шаг 2 с переоцененной матрицей издержек.Первый этап стоит особняком, потому что не входит в итерационнуючасть алгоритм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
