Как мне сделать простую систему поиска автобусных маршрутов?

Question

[Не: пользователь снова спрашивает об этом на Разработка системы железнодорожных запросов, как моделировать поезда, станции и остановки? ] Описание моей проблемы:

Предположим, у меня есть BUS-123 в МАРШРУТ-1 , он будет проезжать через A, B, C, D, E, F, G, H и BUS-321 в МАРШРУТ-2 через D, E, F, X, Y, Z .если кто-то вводит B в качестве исходной точки и F в качестве конечной точки, то в результате должен отобразиться ROUTE-1 с BUS-123.Но если кто-то вводит H в качестве источника, а A в качестве результата назначения не должен отображаться, потому что возвращение может не всегда совпадать с путешествием.Но если человек вводит А в качестве источника и Z в качестве пункта назначения, то BUS-123 с МАРШРУТ-1 и BUS-321 с МАРШРУТ-2 должно отобразиться.

Моя проблема: Как мне сохранить эту информацию о маршруте в базе данных?если я храню в RDBMS, как показано ниже

BUS_NUMBER   ROUTE_NUMBER    VIA_ROUTES
BUS-123      ROUTE-1         A, B, C, D, E, F, G, H
BUS-321      ROUTE-2         D, E, F, X, Y, Z

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

Answer 1

Я бы смоделировал это как циклический граф. Каждая автобусная остановка представлена ​​версией. Каждое прямое соединение между двумя остановками представлено ребром, обозначенным номером маршрута; следовательно, каждый маршрут представляет собой последовательность связанных ребер. Сделайте края тоже направленными. Не все маршруты, идущие от остановки A до остановки B, также обязательно будут идти от остановки B до остановки A в другом направлении.

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

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

• Общее время в пути
• Общее время, потраченное на ожидание вылета следующего этапа.
• Время ожидания на любой отдельной остановке.
• Расстояние

Следует отметить, что слишком большое время ожидания - это плохо (когда-либо тратить 40 минут на ожидание автобуса в январе, когда он -10 F?). Слишком мало это тоже плохо, так как увеличивает вероятность пропуска соединения, учитывая, что автобусы, как правило, имеют довольно большую изменчивость в своих расписаниях, поскольку они очень чувствительны к колебаниям в условиях местного движения.

Вот как бы я это сделал.

Я не верю, что попытался бы решить это напрямую в SQL.

Хотя модель хорошо подходит для SQL. Вам нужны следующие объекты, а затем и некоторые, так как вам нужно будет представлять расписания и т. Д.

• Стоп. A Автобусная остановка. Вершины графа.
• Маршрут. Автобусный маршрут.
• Сегмент . Прямая связь между двумя остановками. Края графика.
• RouteSegment. Ассоциативный объект, представляющий упорядоченную последовательность сегментов, составляющих маршрут.

Answer 2

Я бы имел таблицу route и таблицу route_part.Последний будет содержать ссылку на маршрут плюс порядковый номер для сортировки и ссылку на таблицу stop.Таким образом, вы можете сохранить любой маршрут.

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

Answer 3

Я думаю, что bus_numbers не важны, потому что вы можете посмотреть их позже.Может быть, вам нужно создать 2d-матрицу с bus_stops в большой матрице, имеющей их все, и затем использовать алгоритм обхода графа, такой как dijkstra, чтобы найти кратчайший путь от A до B. Когда вы получили это, вы можете легко найти bus_numbers ипоказать их клиенту.Таким образом, я думаю, что ваша база данных уже очень хорошая.