Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428)
Текст из файла
Государственное образовательноеучреждение высшегопрофессионального образования«Московский физико-техническийинститут (государственныйуниверситет)»Кафедра информатики ивычислительной математикиВыпускная квалификационная работаРешениеэнтропийно-регуляризованнойтранспортной задачи прималом параметререгуляризацииВыпускник:Омельченко С.С.Научный руководитель:д.ф.-м.н. Гасников А.В.г. Москва2017Содержание1 Введение31.1 Актуальность работы .
. . . . . . . . . . . . . . . . . . . .31.2 Преследуемые цели и достигнутые результаты . . . . . . .52 Модели прогноза загрузки транспортных сетей72.1 Формальное описание . . . . . . . . . . . . . . . . . . . . .82.2 Численные методы . . . . . . . . . . . . .
. . . . . . . . . .102.3 Проекционные методы решения задачи транспортного равновесия . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 Равновесное распределение потоков11123.1 Модель Бэкмана . . . . . . . . . . . . . . . . . . . . . . . .123.2 Обзор подходов к построению многостадийных моделей транспортных потоков . . . . . . . . . . . . . . . . .
. . . . . . .133.3 Модель стабильной динамики . . . . . . . . . . . . . . . . .164 Построение матрицы корреспонденций174.1 Гравитационная модель . . . . . . . . . . . . . . . . . . . .174.2 Энтропийная модель . . . . . . . . . . . . . . . . . . . . . .184.2.1Обоснование на основе обменов . . . . .
. . . . . . .4.2.2Обоснование на основе модели равновесного распре-4.2.319деления потоков . . . . . . . . . . . . . . . . . . . .21Облачная модель . . . . . . . . . . . . . . . . . . . .235 Задача энтропийно-линейного программирования5.1 Введение . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .24245.2 Связь решений исходной и энтропийнорегуляризованной задач . . . . . . . . . . . . . . . . . . . .265.3 Энтропийная регуляризация транспортной задачи . . . . .265.4 Метод балансировки . . . . . .
. . . . . . . . . . . . . . . .275.5 Обсуждение метода балансировки . . . . . . . . . . . . . .305.6 ASTM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .315.6.1Алгоритм и анализ сложности . . . . . . . . . . . .1335.7 Сравнение ASTM и метода балансировки . . . . .
. . . . .415.7.1Условия экспериментов . . . . . . . . . . . . . . . .415.7.2ASTM vs STM . . . . . . . . . . . . . . . . . . . . .435.7.3Преимущество подбора точки старта . . . . . . . . .455.7.4Сравнение метода балансировки с ASTM с «умным»стартом . . . . . . . . . . . . . . . . . . . . . . .
. .475.7.5Сравнение методов на датасете MNIST . . . . . . .525.7.6Обсуждение результатов . . . . . . . . . . . . . . . .545.8 Связь моделей стабильной динамики и модели Бэкмана . .555.9 Оптимальный транспорт . . . . . . . . . . . . . . . . . . . .565.10 Скаляризация . . . . . . . . . . . . . . . . . . . .
. . . . . .576 Модель расщепления потоков586.1 Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . .596.2 Простейшая эволюционная модель расщепления . . . . . .606.3 Численные эксперименты . . . . . . . . . . . . . . . . . . .6521Введение1.1Актуальность работыВ последние два десятилетия во многих крупных городах России возникла проблема пробок, которая не имеет архитектурного решения. Всвязи с этим особую важность приобретает оптимальное планированиесетей и оптимизация системы общественного транспорта. Для решенияэтих задач необходимо математическое моделирование, главными целями которого являются определение и прогноз всех параметров транспортной сети, например, объемы перевозок в сети, загруженность дороги потери времени. Наиболее яркими примерами применения транспортных моделей на практике можно назвать:• оценку необходимости ввода маршрута общественного транспорта• оценку последствий ввода выделенных полос• оценку стоимости проезда по платной дороге• оценку стоимости платной парковки• принятие решения о строительстве новой автомобильной дороги ивыбор её параметров• организацию дорожного движения на основе интенсивностей транспортных потоков• оптимизацию светофорных цикловУсловно транспортная модель делится на два блока: транспортныйспрос и транспортное предложение.
Модель транспортного предложения включается в себя описание транспортной сети: узлы (перекрестки) и ребра (дороги). Эта модель описывает пути возможных перемещений и соответсвущие им затраты для всех участников движения. Модельтранспортного спроса описывает перемещения с учётом причин их возникновения для разных типов транспорта и всех возможных путей.3Классическим подходом к расчету модели транспортного спроса является четырёхшаговая модель:1. расчёт объёмов прибытий-отпралений (для каждого района высчитывается сумма по строкам и столбцам матрицы корреспонденций)2.
расчёт межрайонных корреспонденций (для каждой пары районоввысчитывается объём перемещений, и в результате получится матрица корреспонденций)3. расщеплений межрайонных корреспонденций по способу передвижений (личный транспорт, общественный транспорт, пешие перемещения)4. распределение корреспонденций по транспортной сети (определение всех путей, выбираемых участниками движения, и установление количества перемещений по ним)На практике для повышения точности расчёта корреспонденций и ихрасщепления необходимо предпосчитанное распределение потоков, которое требует вычисленную матрицу корреспонденций и информацию орасщеплении потоков. Поэтому задача решается в итеративном режимепоследовательными приближениями - шаги повторяются один за одним.Такой подход оказывается предпочтительным для соотношения затраты/ качество.Вышеописанная четырёхстадийная модель имеет значительную практическую ценность, она зашита во многие транспортные пакеты.
Наиболее ярким представителем является пакет PTV Vision, на котором считались транспортные модели для крупных российских городов (например,Москва, Санкт-Петербург, Пермь, Тверь, Новый Уренгой и др.). В частности, он используется в рамках проекта «Разработка научно обоснованных предложений по развитию транспортной системы Санкт-Петербургаи Ленинградской области на период до 2020 года». Подробное описаниеопыта использования PTV Vision можно найти в [1].41.2Преследуемые цели и достигнутые результатыВ данной дипломной работе дан обзор задачи транспортного равновесия, описаны методы построения матрицы корреспонденций, получены результаты в шаге 3 четырёхстадийной модели - расщеплении межрайонных корреспонденций на личный и общественный транспорт. Была построена динамическая модель бимодального спроса на городскиепередвижения, отличительной особенностью которой является хорошаямасштабируемость (добавление экономических факторов и увеличениечисла районов) и учет эволюционной составляющей в механизме расщепления.
В работе [2] была доказана и экспериментально подтверждена сходимость процесса «нащупывания» равновесия, при котором людиопределялись с предпочтительным видом транспорта.Для выполнения шага 2 четырехстадийной модели в транспортныхпакетах часто применяют приём энтропийной регуляризации задачи. Тоесть, решается не классическая транспортная задача линейного программирования:f (X) =nXi,j=1Cij Xij → Pn(1)minPnX=L̃iji,j=1i=1 Xij =W̃jXij ≥0,i,j=1,n(n - число районов, C - матрица затрат на перемещение между районами, L̃i - число жителей в i-ом районе, W̃j - число жителей j-ого района),а регуляризованная задача:fγ (X) =nXi,j=1Cij Xij + γnXi,j=1Xij ln Xij → Pnj=1minPnXij =L̃i ,i=1.(2)Xij =W̃jXij ≥0,i,j=1,nМотивировка и корректность данной регуляризации описана в работе.
Сложность задачи (1) в общем случае - O(n3 ln n). Основным же преимуществом задачи энтропийно-линейного программирования (ЭЛП) (2)над задачей линейного программирования (ЛП) (1) является то, что при5не малых γ > 0 она может быть решена намного эффективнее методомбалансировки [3]. Этот метод используется и в транспортных пакетах, однако при малых γ время работы метода экспоненциально растет, поэтомузадача ЭЛП (2) при малых γ попросту не решается. Но если первоначальной целью было решение задачи (1), то в регуляризованной задаче(2) параметр γ будет малым. Также его малость может быть объясненаразличными «шумами», возникающими при расчёте матрицы корреспонденций.Для решения этой проблемы в работе предлагается использовать метод подобных треугольников (Adaptive Similar Triangular Method) (далееASTM).
Он решает проблему малых γ. Кроме того, в отличие от метода балансировки, который применим только для транспортных ограничений, ASTM можно использовать для решения задач ЭЛП любымиафинными ограничениями. Это может быть применимо, например, дляпоиска равновесного распределения по путям из шага 4 четырёхстадийной модели.Если γ ≤ε4 ln n ,то из того, чтоεfγ (X N ) − fγ∗ ≤ ,2следуетf0 (X N ) − f0∗ ≤ ε.Для балансировки неизвестна точная оценка времени работы, но естьзавышенная [4]:∼ n2 max expi,j,p,q=1,n1ε0(Ciq + Cpj − (Cij + Cpq )) ln( )2γε(3)Для ASTM время работы:s2∼n6nR2,γε(4)где R - евклидов размер решения двойственной задачи для (2).
А этаоценка в свою очередь соответствует реальным трудозатратам. В связис этим возникает задача определения реального порога γ ∗ , зависящегоот параметров задачи, меньше которого ASTM начинает доминироватьметод балансировки.Насколько автору известно, впервые подобное исследование проводится в данной работе. Кроме того, оказывается, что балансировка становится хуже до того момента, как стоит переходить к решению задачиЛП, например, симплекс-методом.Другим интересным приложением, в котором метод балансировки может быть заменен ASTM, является задача расчёта барицентра Вассерштейна.
Вариации данной задачи известны со времен Монжа (задача опереносе массы за минимальную работу). Также стоит отметить задачупоиска расстояний между картинками, которая возникает при их классификации. В работе произведено сравнение быстродействия алгоритмовASTM и балансировки и предложен способ ускорения ASTM, связанныйс выбором точки старта.2Модели прогноза загрузки транспортныхсетейДля моделирования загрузки транспортных сети необходимо выбратьповеденчиские принципы её участников. Существует два главных подхода (принципы Вардропа):1. Пользователи сети независимо друг от друга минимизируют собственные транспортные издержки.2. Пользователи сети выбирают маршруты в целях минимизации общих расходов в сети.7Под издержками здесь понимается целый комплекс затрат: финансовые, временные, моральные и др.Первый принцип предполагает два допущения:1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
