Назначение маршрута

Эта статья о транспортном моделировании. Информацию о компьютерных сетях см. в разделе маршрутизация .

Назначение маршрута , выбор маршрута или распределение трафика касается выбора маршрутов (альтернативно называемых путями) между пунктами отправления и назначения в транспортных сетях . Это четвертый шаг в традиционной модели прогнозирования перевозок , следующий за созданием поездок , распределением поездок и выбором вида транспорта . Зональный анализ распределения поездок позволяет получить таблицы поездок из пункта отправления в пункт назначения. Анализ выбора режима показывает, какие путешественники каким видом транспорта будут пользоваться . Чтобы определить потребности, затраты и выгоды объекта, нам необходимо знать количество путешественников на каждом маршруте и звене сети (маршрут — это просто цепочка звеньев между пунктом отправления и пунктом назначения). Нам нужно выполнить задание по трафику (или поездке). Предположим, существует сеть автомагистралей и транзитных систем, а также предлагаемое дополнение. Сначала мы хотим узнать нынешнюю картину задержки трафика , а затем, что произойдет, если будет сделано добавление.

Общие подходы

Давние методы

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

Исследователи исследования общественного транспорта в районе Чикаго (CATS) разработали кривые отклонения от автомагистралей по сравнению с местными улицами. В Калифорнии тоже было много работы, поскольку Калифорния уже имела ранний опыт планирования автострад. Помимо отвлекающих действий, CATS решал некоторые технические проблемы, возникающие при работе со сложными сетями. Одним из результатов стал алгоритм Беллмана-Форда-Мура для поиска кратчайших путей в сетях.

Проблема, которую не решил метод перенаправления, заключалась в обратной связи с объемом трафика на каналах и маршрутах. Если много транспортных средств пытаются воспользоваться объектом, он становится перегруженным и время в пути увеличивается. Из-за отсутствия какого-либо способа учитывать обратную связь, ранние исследования планирования (фактически большинство из них в период 1960-1975 годов) игнорировали обратную связь. Они использовали алгоритм Мура для определения кратчайших путей и распределяли весь трафик по кратчайшим путям. Это называется назначением «все или ничего», потому что либо весь трафик от i до j перемещается по маршруту, либо нет.

Назначение «все или ничего» или кратчайшего пути не является тривиальным с технико-вычислительной точки зрения. Каждая зона движения соединена с n - 1 зонами, поэтому необходимо учитывать множество путей. Кроме того, нас в конечном итоге интересует трафик по ссылкам. Ссылка может быть частью нескольких путей, и трафик по путям необходимо суммировать по ссылкам.

Можно привести аргументы в пользу подхода «все или ничего». Это происходит следующим образом: исследование планирования направлено на поддержку инвестиций, чтобы обеспечить хороший уровень обслуживания на всех каналах. Используя время в пути, связанное с запланированным уровнем обслуживания, расчеты показывают, как будет двигаться трафик после внедрения улучшений. Зная объемы трафика на каналах, можно рассчитать емкость, которую необходимо предоставить для достижения желаемого уровня обслуживания.

Эвристические процедуры

Для учета влияния транспортной нагрузки на время в пути и транспортное равновесие было разработано несколько эвристических процедур расчета. Одна эвристика действует постепенно. Назначаемый трафик делится на части (обычно 4). Назначьте первую часть трафика. Рассчитайте новое время в пути и назначьте следующую часть трафика. Последний шаг повторяется до тех пор, пока не будет назначен весь трафик. CATS использовала вариацию этого подхода; он назначал строку за строкой в ​​таблице OD.

Эвристика, включенная в FHWA коллекцию компьютерных программ , действует по-другому.

• 0. Начните с загрузки всего трафика, используя процедуру «все или ничего».
• 1. Рассчитайте полученное время в пути и переназначьте трафик.
• 2. Теперь начните переназначать веса. Вычислите взвешенное время прохождения для двух предыдущих загрузок и используйте их для следующего задания. Последняя итерация получает вес 0,25, а предыдущая — 0,75.
• 3. Продолжайте.

Кажется, что эти процедуры работают «очень хорошо», но они не точны.

Алгоритм Франка-Вульфа

Дафермос (1968) применил алгоритм Франка-Вольфа (1956, Флориан 1976), который можно использовать для решения проблемы равновесия дорожного движения. Предположим, мы рассматриваем сеть автомобильных дорог. Для каждого звена существует функция, определяющая взаимосвязь между сопротивлением и объемом трафика. Бюро дорог общего пользования (BPR) разработало функцию перегрузки канала (дуги) (или задержки объема, или производительности канала), которую мы назовем S _a (va ₎ .

$S_{a}\left({v_{a}}\right)=t_{a}\left({1+0.15\left({\frac {v_{a}}{c_{a}}}\right)^{4}}\right)$

• t _a = время свободного движения по звену a в единицу времени
• v _a = объем трафика по каналу a в единицу времени (более точно: поток при попытке использовать канал a ).
• c _a = пропускная способность канала a в единицу времени
• S _a (v _a ) — среднее время в пути транспортного средства по ссылке a.

Есть и другие функции перегрузки. CATS уже давно использует функцию, отличную от той, что используется в BPR, но, похоже, разница между результатами при сравнении функций CATS и BPR незначительна.

Назначение равновесия

Чтобы распределить трафик по путям и ссылкам, нам нужны правила, а также известные условия равновесия Уордропа . Суть этого состоит в том, что путешественники будут стремиться найти кратчайший путь (с наименьшим сопротивлением) от пункта отправления до места назначения, а сетевое равновесие наступает, когда ни один путешественник не может уменьшить усилия, потраченные на путешествие, перейдя на новый путь. Такие условия называются оптимальными для пользователя, поскольку ни один пользователь не выиграет от изменения траектории движения, если система находится в равновесии.

Оптимальное равновесие пользователя можно найти, решив следующую нелинейного программирования. задачу

$\min \sum _{a}{\int _{0}^{v_{a}}{S_{a}\left(x\right)}}dx$

подлежит:

$v_{a}=\sum _{i}{\sum _{j}{\sum _{r}{\alpha _{ij}^{ar}x_{ij}^{r}}}}$

$\sum _{r}{x_{ij}^{r}=T_{ij}}$

$v_{a}\geq 0,\;x_{ij}^{r}\geq 0$

где $x_{ij}^{r}$— количество транспортных средств на пути r от пункта отправления i до пункта назначения j . Итак, ограничение (2) говорит, что все перемещения должны иметь место – i = 1... n; j = 1...n

$\alpha _{ij}^{ar}$ = 1, если ссылка a находится на пути r от i до j; в противном случае ноль. Таким образом, ограничение (1) суммирует трафик по каждому каналу. Для каждой ссылки в сети существует ограничение. Ограничение (3) гарантирует отсутствие отрицательного трафика.

Пример

Пример Иша, Янсона и Бойса (1979) иллюстрирует решение проблемы нелинейной программы. Есть две связи от узла 1 до узла 2, и для каждой связи существует функция сопротивления (см. рисунок 1). Площади под кривыми на рисунке 2 соответствуют интегрированию от 0 до а в уравнении 1, их сумма равна 220 674. Обратите внимание, что функция для связи b построена в обратном направлении.

$S_{a}=15\left({1+0.15\left({\frac {v_{a}}{1000}}\right)^{4}}\right)$

$S_{b}=20\left({1+0.15\left({\frac {v_{b}}{3000}}\right)^{4}}\right)$

$v_{a}+v_{b}=8000$

Рисунок 1: Сеть с двумя маршрутами

Figure 1 - Two Route Network

Рисунок 2. Графическое решение задачи назначения равновесия.

Figure 2 - Graphical Solution to the Equilibrium Assignment Problem

Рисунок 3. Распределение транспортных средств, не удовлетворяющих условию равновесия

Figure 3 - Allocation of Vehicles not Satisfying the Equilibrium Condition

находится 2152 автомобиля В равновесии на звене a , а на звене b — 5847 . Время в пути одинаковое на каждом маршруте: около 63.

Рисунок 3 иллюстрирует распределение транспортных средств, которое не соответствует равновесному решению. Кривые не изменяются. Но при новом распределении транспортных средств по маршрутам заштрихованная область должна быть включена в решение, поэтому решение на рисунке 3 больше, чем решение на рисунке 2, по площади заштрихованной области.

Интеграция вариантов путешествий

Модель планирования городского транспорта развивалась как набор шагов, которым необходимо следовать, и модели развивались для использования на каждом этапе. Иногда были шаги внутри шагов, как в случае с первым утверждением модели Лоури . Было отмечено, что в некоторых случаях этапы могут быть интегрированы. В более общем смысле, эти шаги абстрагируются от решений, которые могут быть приняты одновременно, и было бы желательно лучше воспроизвести это в анализе.

Модели дезагрегированного спроса были впервые разработаны для решения проблемы выбора способа передвижения. Эта задача предполагает, что кто-то решил отправиться в путешествие, куда оно будет идти и в какое время оно будет совершено. Они использовались для рассмотрения подразумеваемого более широкого контекста. Обычно разрабатывается вложенная модель, начиная с вероятности совершения поездки, затем исследуя выбор мест, а затем выбор вида транспорта. Ко времени путешествия относиться немного сложнее.

Модель Уилсона с двойным ограничением энтропии стала отправной точкой для усилий на совокупном уровне. Эта модель содержит ограничение

$t_{ij}c_{ij}=C$

где $c_{ij}$ стоимость проезда по ссылке, $t_{ij}$ относится к трафику по ссылке, а C — это ограничение ресурса, размер которого необходимо определить при настройке модели данными. Вместо использования этой формы ограничения можно использовать монотонно возрастающую функцию сопротивления, используемую при назначении трафика. Результат определяет перемещение между зонами и распределяет трафик по сетям, и это имеет большой смысл с точки зрения того, как можно представить себе работу системы: трафик между зонами зависит от сопротивления, вызванного перегрузкой.

Альтернативно, функция сопротивления линии связи может быть включена в целевую функцию (и функция общей стоимости исключена из ограничений).

Подход к обобщенному дезагрегированному выбору эволюционировал, как и обобщенный агрегированный подход. Большой вопрос заключается в отношениях между ними. Когда мы используем макромодель, нам хотелось бы знать, какое дезагрегированное поведение она представляет. Если мы проводим микроанализ, мы хотели бы знать совокупные последствия анализа.

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

Интеграция спроса на поездки с назначением маршрута

Давно признано, что спрос на поездки зависит от сетевого предложения. Пример открытия нового моста там, где раньше его не было, что привело к дополнительному движению транспорта, отмечалось на протяжении веков. Было проведено много исследований по разработке методов, позволяющих системе прогнозирования напрямую учитывать это явление. Эванс (1974) опубликовал докторскую диссертацию о математически строгом сочетании модели гравитационного распределения с моделью равновесного распределения. Самая ранняя ссылка на эту интеграцию - это работа Ирвина и Фон Кубе, описанная Флорианом и др. (1975), которые комментируют работу Эванса:

«Работа Эванса чем-то напоминает алгоритмы, разработанные Ирвином и Фон Кубом ['Ограничение пропускной способности в программах назначения с несколькими режимами передвижения', Бюллетень HRB 347 (1962)] для исследования транспорта в Торонто . Их работа позволяет установить обратную связь между перегруженными заданиями и распределение поездок, хотя они применяют последовательные процедуры. Начиная с первоначального решения задачи распределения, межзональные поездки назначаются начальным кратчайшим маршрутам. Для последующих итераций вычисляются новые кратчайшие маршруты, и их длины используются в качестве времени доступа для входных данных. Затем новые межзональные потоки назначаются в некоторой пропорции к уже найденным маршрутам. Процедура останавливается, когда межзональные времена для последующих итераций квазиравны.

Флориан и др. предложил несколько иной метод решения задачи комбинированного распределения, непосредственно применяя алгоритм Франка-Вулфа. Бойс и др. (1988) суммируют исследования по проблемам сетевого равновесия, включая задание с эластичным спросом.

Обсуждение

Задачу с тремя звеньями невозможно решить графически, и большинство задач транспортной сети связаны с большим количеством узлов и связей. Иш и др., например, изучили дорожную сеть округа ДюПейдж, где было около 30 000 односторонних соединений и 9 500 узлов. Поскольку проблемы большие, для решения задачи о назначениях необходим алгоритм, и используется алгоритм Франка-Вульфа (с различными современными модификациями с момента первой публикации). Начните с присваивания «все или ничего», а затем следуйте правилу, разработанному Франком-Вулфом, для итерации в направлении минимального значения целевой функции. (Алгоритм применяет последовательные допустимые решения для достижения сходимости к оптимальному решению. Он использует эффективную процедуру поиска для быстрого продвижения вычислений к оптимальному решению.) Время прохождения соответствует двойственным переменным в этой задаче программирования.

Интересно, что алгоритм Франка-Вульфа появился в 1956 году. Его применение было разработано в 1968 году, и прошло еще почти два десятилетия, прежде чем первый алгоритм назначения равновесия был встроен в обычно используемое программное обеспечение для планирования перевозок ( Emme и Emme/2 , разработанные Флорианом и другими в Монреале). Нам не хотелось бы делать какие-либо общие выводы из наблюдений за медленным применением, главным образом потому, что мы можем найти противоположные примеры относительно темпов и закономерностей развития техники. Например, симплексный метод решения задач линейного программирования был разработан и широко применялся до разработки большей части теории программирования.

Постановка задачи и алгоритм имеют общие приложения в гражданском строительстве – гидравлике, конструкциях и строительстве. (См. Хендриксон и Янсон, 1984).

Эмпирические исследования выбора маршрута

Модели назначения маршрутов основаны, по крайней мере, в некоторой степени на эмпирических исследованиях того, как люди выбирают маршруты в сети . Такие исследования обычно сосредоточены на определенном режиме и используют либо модели заявленных предпочтений , либо модели выявленных предпочтений .

Велосипед

велосипедисты Было обнаружено, что предпочитают выделенные велосипедные дорожки и избегают крутых холмов.

Общественный транспорт

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

См. также

• Выбор маршрута (значения)

Общие ссылки

• Дафермос, Стелла. К. и Ф.Т. Спэрроу. Проблема распределения трафика для общей сети. Журнал исследований Национального бюро стандартов, 73B, стр. 91–118. 1969.
• Флориан, редактор Майкла, «Методы равновесия трафика», Springer-Verlag, 1976.
• Иш, Рональд, Брюс Н. Янсон и Дэвид Бойс. Назначение равновесной поездки: преимущества и последствия для практики, Transportation Research Record 728, стр. 1–8, 1979.
• Эванс, Сюзанна П. . «Вывод и анализ некоторых моделей для объединения распределения и назначения поездок». Транспортные исследования, том 10, стр. 37–57, 1976 г.
• Хендриксон, Коннектикут и Б. Н. Янсон, «Формулировка общего сетевого потока для решения нескольких проблем гражданского строительства», Системы гражданского строительства 1 (4), стр. 195–203, 1984 г.