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

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

Краткая история организации движения

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

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

Давние техники

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

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

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

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

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

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

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

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

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

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

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

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

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

• т_а = время прохождения свободного потока по ссылке а в единицу времени
• v_а = объем трафика по ссылке а за единицу времени (точнее: поток пытается использовать ссылку а).
• c_а = емкость ссылки а в единицу времени
• S_а(v_а) - среднее время в пути для транспортного средства по ссылке а

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

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

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

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

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

при условии:

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

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

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

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

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

Пример

Пример из Eash, Janson, and Boyce (1979) проиллюстрирует решение проблемы нелинейной программы. Есть два звена от узла 1 к узлу 2, и для каждого звена есть функция сопротивления (см. Рисунок 1). Области под кривыми на рисунке 2 соответствуют интегрированию от 0 до а в уравнении 1 они составляют 220 674 человека. Обратите внимание, что функция для ссылки б наносится в обратном направлении.

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

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

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

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

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

Рисунок 3: Распределение автомобилей, не удовлетворяющих условию равновесия

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обсуждение

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

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

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

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

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

Велосипед

Велосипедисты было установлено, что предпочитают обозначенные велосипедные дорожки и избегайте крутых холмов.^[2]

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

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

Смотрите также

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

Примечания

1. Уордроп, Дж. Г. (1952). Некоторые теоретические аспекты исследования дорожного движения. Учреждение инженеров-строителей. 1. С. 325–378.
2. Худ, Джеффри; Салл, Элизабет; Чарльтон, Билли (2011). «Модель выбора велосипедного маршрута на основе GPS для Сан-Франциско, Калифорния». Транспортные письма. 3 (1): 63–75. Дои:10.3328 / TL.2011.03.01.63-75.
3. Лю, Юйлинь; Бункер, Джонатан; Феррейра, Луис (2010). «Моделирование выбора маршрута транзитными пользователями при назначении транзита: обзор» (PDF). Отзывы о транспорте. 30 (6): 753–769. Дои:10.1080/01441641003744261 - через Тейлор и Фрэнсис Онлайн.
4. Яносикова Людмила; Славик, Иржи; Кохани, Михал (2014). «Оценка модели выбора маршрута для городского общественного транспорта с использованием данных смарт-карты». Транспортное планирование и технологии. 37 (7): 638–648. Дои:10.1080/03081060.2014.935570.

Общие ссылки

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