Стратегия, чтобы найти свой лучший маршрут только на общественном транспорте?

Question

Найти маршрут для автомобиля довольно легко: вы сохраняете взвешенный график всех дорог, и вы можете использовать алгоритм Джикстры [1]. Автобусный маршрут менее очевиден. С шиной вы должны представлять такие вещи, как «подождите 10 минут до следующей шины» или «пройти один квартал до другой автобусной остановки» и передать их в свой алгоритм поиска пути.

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

Как бы вы эффективно представили этот вид графика, зависящего от времени, и нашли бы маршрут? Нет необходимости доказуемо оптимального решения; если бы путешественник хотел быть вовремя, он купил бы машину. ; -)

[1] Прекрасный алгоритм, который нужно упомянуть в примере, потому что все о нем слышали, хотя A * - более вероятный выбор для этого приложения.

Answer 1

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

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

Одним из ключей к успешному алгоритму было использование функции стоимости пути, основанной на времени в пути и времени ожидания, умноженном на различные веса. Это время называется по-шведски «kresu». Эти взвешенные времена отражают тот факт, что, например, время ожидания в одну минуту обычно «неудобно» эквивалентно двум минутам времени в пути.

Таблица веса KRESU

• x1 - Время в пути
• x2 - Прогулка между остановками
• x2 - Ожидание на остановке во время поездки. Останавливается под крышей, с магазинами и т.д. можно получить немного меньший вес и многолюдные станции выше, чтобы настроить алгоритм.
• Вес для времени ожидания на первой остановке зависит от интенсивности движения и может составлять от 0,5 до 3.

Структура данных

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

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

Ссылки Список с другими остановками, вы можете добраться пешком от этой остановки. Данные: Другая остановка, Время идти к другой остановке

Линии / Туры У вас есть номер в автобусе и пункт назначения. Автобус начинается с одной остановки и проходит несколько остановок по пути к месту назначения. Данные: номер, имя, место назначения

Вершина Обычно у вас есть расписание с наименьшим временем, когда оно должно быть на первой и последней остановке в Туре. Каждый раз, когда автобус / поезд проходит остановку, вы добавляете новый узел в массив. Эта таблица может иметь миллионы значений в день. Данные: линия / тур, остановка, время прибытия, время отправления, допустимая погрешность, следующий узел в туре

Поиск Массив того же размера, что и массив узлов, используемый для хранения информации о том, как вы туда попали, и стоимости пути. Данные: обратная ссылка с предыдущим узлом (не устанавливается, если узел не посещен), стоимость пути (бесконечно для не посещенных)

Answer 2

То, о чем вы говорите, сложнее, чем что-то вроде математических моделей, которые можно описать с помощью простых структур данных, таких как графы, и с помощью «простых» алгоритмов, таких как Джикстра. То, о чем вы просите, - это более сложная проблема, подобная тем, с которыми сталкиваются в мире автоматизированного управления логистикой.

Один из способов думать о том, что вы задаете многомерную задачу, вам нужно уметь вычислять:

1. Оптимизация расстояния
2. Оптимизация времени
3. Оптимизация маршрута
4. Оптимизация "горизонта времени" (если сейчас 5:25, а автобус появляется только в 7:00, выберите другой маршрут.)

Учитывая все эти обстоятельства, вы можете попытаться выполнить детерминированное моделирование, используя сложные многоуровневые структуры данных. Например, вы все еще можете использовать взвешенную диаграмму для представления существующих потенциальных маршрутов, где каждый узел также содержит автоматы конечного состояния, которые добавляют весовое смещение к маршруту в зависимости от значений времени (например, путем пересечения узла в 5:25 вы получите другое значение, чем если бы ваша симуляция пересекла его в 7:00.)

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

Мое предложение будет использовать альтернативную стратегию. Я попытался бы использовать генетический алгоритм, в котором ДНК для отдельного человека рассчитывал потенциальный маршрут, затем я бы создал фитнес-функцию, которая кодировала бы затраты и веса в более удобной для обслуживания форме таблицы поиска. Тогда я бы позволил Генетическому Алгоритму попытаться найти почти оптимальное решение для поиска маршрута общественного транспорта. На современных компьютерах подобный GA, вероятно, будет работать достаточно хорошо, и он должен быть, по крайней мере, относительно устойчивым к динамичности реального мира.

Я думаю, что большинство систем, которые делают подобные вещи, выбирают «легкий путь» и просто делают что-то вроде алгоритма поиска A *, или что-то похожее на жадный алгоритм взвешенного диграфа с затратами. Следует помнить, что пользователи общественного транспорта сами не знают, каким будет оптимальный маршрут , поэтому оптимальное решение на 90% все еще будет отличным решением для среднего случая.

Answer 3

Некоторые данные, которые необходимо знать на арене общественного транспорта:

1. Каждая передача влечет за собой 10-минутный штраф (если это не временная передача) в уме гонщиков. То есть мысленно поездка на одном автобусе, которая занимает 40 минут, примерно эквивалентна поездке на 30 минут, которая требует трансфера.
2. Максимальное расстояние, на которое большинство людей готовы идти до автобусной остановки, составляет 1/4 мили. Железнодорожный вокзал / скоростной трамвай около 1/2 мили.
3. Расстояние не имеет значения для водителя общественного транспорта. (Важно только время)
4. Частота имеет значение (если соединение пропущено, как долго до следующей шины). Наездники предпочтут более частые варианты обслуживания, если альтернатива в течение часа останавливается для следующего экспресса.
5. Железнодорожный транспорт имеет более высокий приоритет, чем автобусный (больше уверенности, что поезд придет и будет двигаться в правильном направлении)
6. Необходимость оплаты нового тарифа - большой успех. (добавить около 15-20 минут штрафа) * ​​1014 *
7. Общее время в пути также имеет значение (с указанными выше штрафами)
8. Насколько беспрепятственно соединение? Должен ли гонщик существовать на железнодорожной станции, пересекающей оживленную улицу? Или это просто сойти с поезда и пройти 4 шага до автобуса?
9. Пересечение оживленных улиц - еще один большой штраф на пересадках - может пропустить соединение, потому что не может пересечь улицу достаточно быстро.

Answer 4

, если стоимость каждого этапа поездки измеряется во времени, то единственное осложнение заключается в учете графика - который просто меняет стоимость в каждом узле на функцию текущего времени t, где t - это просто сумма время поездки (при условии, что расписание нормализовано для начала при t = 0).

поэтому вместо стоимости узла 10, стоимость которой равна 10 минутам, стоимость f (t) определяется как:

• t1 = nextScheduledStop (t); // чтобы получить время следующей остановки в или после времени t
• baseTime для ноги = 10 // например, 10-минутное путешествие
• return (t1-t) + baseTime

время ожидания, таким образом, динамически включается в стоимость каждого этапа, а прогулки между автобусными остановками - это просто дуги с постоянными временными затратами

с этим представлением вы сможете напрямую применить алгоритм A * или Дейкстры

Answer 5

Найти маршруты для автомобиля довольно легко: вы храните взвешенный график все дороги, и вы могли бы использовать Алгоритм Джикстры. Автобусный маршрут менее очевидно.

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

Например, вы помечаете автобусы, время которых прошло, бесконечно дорого - тогда они не включаются в расчет.

Затем вы решаете, как взвесить каждый аспект.

Время перехода может быть взвешено на 1 Время ожидания может быть взвешено на 1 Переводы могут быть взвешены на 0,5 (так как я предпочел бы добраться туда раньше и получить дополнительный перевод)

Затем вы рассчитываете все маршруты на графике, используя любой обычный алгоритм затрат с добавлением бесконечной стоимости:

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

Другими словами, существует новое ограничение: «текущее время», которое является временем запуска первого автобуса, суммируется со всеми временами прохождения и ожидания автобусов и пройденных остановок.

Это немного усложняет алгоритм, но алгоритм все тот же. Вы можете видеть, что большинство алгоритмов могут быть применены к этому, некоторые могут потребовать многократных проходов, и некоторые не будут работать, потому что вы не можете добавить время -> бесконечное вычисление стоимости в линию. Но большинство должно работать просто отлично.

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

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

-Adam

Answer 6

Я думаю об этой проблеме так: в конечном итоге вы пытаетесь оптимизировать среднюю скорость от начальной точки до конечной. В частности, вас не волнует общая пройденная дистанция, если выход [хорошо] с вашего пути экономит время. Таким образом, основная часть пространства решений должна будет идентифицировать эффективные доступные маршруты, которые покрывают нетривиальные части общего расстояния на относительно высоких скоростях между стартом и финишем.

К исходной точке, типичные автомобильные алгоритмы маршрута, используемые GPS-навигаторами для совершения поездки на автомобиле, являются хорошим ориентиром для определения оптимального общего времени и оптимальных оценок маршрута. Другими словами, ваша поездка на автобусе была бы действительно полезной, чтобы приблизиться к автомобильному решению. Очевидно, что система, основанная на автобусном маршруте, будет иметь гораздо больше ограничений, чем автомобильные решения, но наличие автомобильного решения в качестве эталона (время и расстояние) дает алгоритму шины основу для оптимизации против *. Итак, в общем, вы хотите итеративным образом преобразовать автомобильное решение в набор возможных шинных решений или, возможно, с большей вероятностью принять возможные шинные решения и сравнить их с вашим автомобильным решением, чтобы узнать, делаете ли вы «хорошо» или нет .

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

Когда у вас есть набор возможных основных сегментов, доступных в качестве возможных ответов в решении, вам нужно соединить их вместе с другими возможными путями ходьбы и ожидания ... или, если достаточно далеко друг от друга, рекурсивный выбор дополнительных короткие автобусные рейсы. Интуитивно, кажется, что из-за Парадокс ограничений здесь действительно не будет запретительного набора вариантов (см. Сноску ниже). Даже если вы не можете перебрать все возможные комбинации оттуда, оставшиеся должны быть в состоянии оптимизироваться с использованием алгоритма типа имитация отжига (SA). Метод Монте-Карло был бы другим вариантом.

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

* Примечание: я обычно называю это «парадоксом ограничений» - мой термин. Хотя люди, естественно, могут думать о более ограниченных проблемах как о более трудных для решения, ограничения уменьшают выбор, а меньший выбор означает более легкую грубую силу. Когда вы можете использовать грубую силу, тогда доступно даже оптимальное решение.

Answer 7

Я думаю, что ваша проблема сложнее, чем вы ожидаете. Недавние действия COST направлены на решение этой проблемы: http://www.cost.esf.org/domains_actions/tud/Actions/TU1004: «Моделирование пассажирских потоков общественного транспорта в эпоху интеллектуальных транспортных систем».

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

Я думаю, что здесь нужен новый поликритериальный подход (время, надежность, стоимость, комфорт и другие критерии). Его необходимо вычислять в реальном времени, чтобы: 1) публиковать информацию для конечного пользователя в течение короткого времени; 2) иметь возможность корректировать маршрут в режиме реального времени (на основе условий трафика в реальном времени - из ITS).

Я собираюсь подумать об этой проблеме в течение следующих нескольких месяцев (возможно, даже в течение докторской диссертации).

С уважением Рафал

Answer 8

По сути, узел на вашем графике должен представлять не только местоположение, но и самое раннее время, когда вы можете туда добраться. Вы можете думать об этом как об исследовании графа в (месте, времени) пространстве. Кроме того, если у вас есть (место, t1) и (место, t2), где t1

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

Вам также понадобится некоторая эвристика, чтобы рассмотреть перспективные маршруты перед менее перспективными - если маршрут уходит от пункта назначения, менее вероятно (но не совсем вероятно), что он будет хорошим.

Answer 9

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

Я собрал искатель маршрута метро в качестве упражнения на пути к графу, найдя некоторое время назад:

http://gfilter.net/code/pathfinderDemo.aspx

Answer 10

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

Эти ребра являются затратами, но я думаю, что вы можете расширить понятие / понятие затрат, и они могут иметь разные относительные значения.