Был как-то проект у меня, который был связан с картой города. И возникла идея, что раз есть карта с маршрутами и соответствующими остановками городского транспорта, то почему бы не сделать поиск пути из пункта А в пункт Б на ней.
Так как железо, где предполагалось размещать софт, имеет крайне узкий канал интернета, то поиск должен был бы полностью осуществляться локально, то есть без привлечения мощностей сервера. Кроме того, конечно же, хотелось не потерять внимание пользователя и выдать ему результат как можно быстрее.
Где-то около часа или двух я сидел и не мог ничего придумать, а потом появилась идея, что я могу рассматривать маршрут, не как множество остановок, а как 1 точку. И если я сверну маршруты в точку, то я получу очень простой граф.
Идея показалось неплохой, и мне понравилась.
Первое что сделал это запарсил с сайтов маршруты транспорта. Далее принялся за граф.
Это оказалась не сложная задача, берем каждую остановку маршрута и смотрим, нет ли остановок любого другого маршрута в заданном нами радиусе. Радиус взял 600м (в последней версии 400м) – предполагаемое расстояние, которое человек может пройти безболезненно пешком от одной остановки до другой в случае необходимости пересадки. Вероятно, это расстояние можно сократить, скажем, до 200м, так как расстояние от одной остановки до другой на перекрестке не превышает эту дистанцию.
Итак, после всех этих манипуляций я получил граф, по которому достаточно быстро можно построить путь от одного маршрута к другому. Таким образом, получился граф, который хранит информацию о переходах с одного маршрута городского транспорта на другой, эдакий, мета-граф.
За несколько месяцев алгоритм переписывался пару раз, далее поподробнее расскажу о последней реализации.
Качество видео ужас, но как сделать получше я так и не обнаружил.
Усредненное время, затрачиваемое на выполнение шагов:
gpt — 0.009с, найти ближайшие остановки к точке клика
grt — 0.001с, найти кратчайший путь от маршрута к маршруту
apt — 0.0001с, добавляем остановки и точки поворота к нашему маршруту
all — 0.01c, суммарное время выполнения поиска пути
Данные:
Мы имеем некую карту города, с нанесенными на нее маршрутами городского транспорта (90 маршрутов) и координатами соответствующих остановок, принадлежащие этим маршрутам.
На карте маршруты выглядят так:
--ishodniki.png "Поиск кратчайшего пути в транспортном графе (концепт) + исходники")
route(
id,
name,
color,
route_type_id
) // информация о маршруте
route_type(
id,
name
) // тип маршрута - трамвай, троллейбус, автобус, метро, маршрутка
route_points(
id,
marker_description_id,
route_id,
marker_order
) // точки, которые принадлежат маршруту
marker(
id,
x,
y,
address
) // геокординаты
marker_category(
id,
name
) // точка поворота или остановка
marker_description(
id,
name,
marker_category_id,
marker_id
)
Что бы каждый раз при поиске маршрута не тратить время на вычисления расстояния между остановками (в рамках 1 маршрута) посчитаем его заранее и запишем в соответствующую таблицу.
Получим таблицу расстояний:
route_distance(
route_id, //ид машрута
roite_point_from_id, //ид остановки откуда едем
roite_point_to_id, //ид остановки до которой едем
distance //сколько потребуется времени что бы доехать между остановками
)
Далее построим мета-граф переходов, то есть мы найдем те остановки маршрута, в радиусе которых есть остановки из других маршрутов. Как уже отмечал, я выбрал радиус 400 метров.
Результат обработки запишем в таблицу:
route_cross_points(
route_from_id, //маршрут с которого пересаживаемся
route_to_id, //маршрут на который пересаживаемся
route_point_from_id, //остановка с которой пересаживаемся
route_point_to_id, //остановка на которую пересаживаемся
distance //затраты едениц времени
) //таблица, которая содержит пересадки
Выгрузка данных в php
Все мои программные реализации, построенные на базе MYSQL были очень медленные. Я решил отойти от базы. Я выгрузил данные в массив и решил работать через сокет. В моем случае, выгруженные данные занимают объем порядка 19MБ оперативной памяти.
Основным массивом является у нас массив $graf. Это трехмерный массив ключи у которого:
- 1-й ключ маршрут с которого пересаживаемся
- 2-й ключ на который пересаживаемся
- 3-й точка пересадки
$r = $this->db->query('
select
routeFrom rf,
routeTo rt,
markerFrom mf,
markerTo mt,
distance d
from
route_cross_points RCP
');
$kf = 0;
foreach($r as $k => $v)
{
$this->graf[(int)($v['rf'])][(int)($v['rt'])][] = array((int)($v['mf']), (int)($v['mt']), (float)($v['d']));
}
$graf[$idFrom][$idTo] = array(
0 => $v1, //с какой остановки, на какую пересаживаться и оценка веса пересадки
1 => $v2 //с какой остановки, на какую пересаживаться и оценка веса пересадки
.....
);
Так как остановка одного маршрута может попасть между 2-мя остановками другого или маршруты соприкасаются в более чем 1 точке, то мы получим множество вариантов пересадок. Итак, $v1, $v2 и являются этими пересадками.
Также в памяти лежит массив с расстояниями внутри маршрута, то есть массив вида:
$routeDistance[$idRoute][$pFrom][$pTo] = (float);
Где:
- $idRoute – ид нашего маршрута,
- $pFrom — остановка с которой ехать,
- $pTo — остановка куда ехать,
- (float) – значение пути в абстрактных еденицах.
$rt = $this->db->query('
select
route_id rni,
POINT1 p1,
POINT2 p2,
distance d
from
route_distance
');
foreach($rt as $k => $v)
{
$this->routeDistance[(int)($v['rni'])][(int)($v['p1'])][(int)($v['p2'])] = (int)($v['d']);
}
Поиск пути
Что бы начать поиск нам нужно найти остановку, с которой мы будем ехать и куда. После того как мы нашли ближайшие остановки откуда($idFrom) и куда($idTo) ехать, установили принадлежность остановок маршрутам, попробуем найти путь.
Чтобы найти путь с 1 пересадкой:
if(isset($graf[$idFrom][$idTo]))
{
//Это значит что можно пересесть с 1 маршрута на другой.
}
Поиск пути, например, с 2 пересадками реализуется вот так:
foreach($graf[$idFrom] as $keyOne => $one)
{
if(isset($graf[$idTo][$keyOne]))
{
//Это означает что у маршрута с которого мы едем, и у маршрута, куда мы едем есть пересадка на общий маршрут.
}
}
Соответственно, чтобы найти путь, например, с 3 пересадками пишем следующим образом:
foreach($graf[$idFrom] as $keyOne => $one) //Тут мы выбираем все маршруты на которые можно пересесть с маршрута откуда едем
{
foreach($graf[$idFrom] as $keyTwo => $two)//выбираем все маршруты на которые можно пересесть из точки куда едем
{
if(isset($graf[$keyOne][$keyTwo])){ }
}
}
После этих операций мы получаем набор маршрутов вида $id1 -> $id2 -> $id3 -> $id4. Где $id* — ид маршрута.
Далее нам нужно понять какой путь самый быстрый. У нас есть остановка старта($pStart) и остановка конца($pEnd). Так же по таблице $graf мы знаем точки пересадок(откуда, куда и расстояние) это наши значени $v1, $v2.
Распишу для $id1 -> $id2. Добавляем к ним данные по всем пересадкам:
$id1($pStart, $v1['from']) -> $id2($v1['to'], $pEnd)
$id1($pStart, $v2['from']) -> $id2($v2['to'], $pEnd)
$id1($pStart, $v3['from']) -> $id2($v3['to'], $pEnd)
Немного очевидного, чтобы оценить маршрут нужно все сложить:
$routeDistance[$id1][$pStart][$v1['from']] + $v1['distance'] + $routeDistance[$id2][$v1['to']][$pEnd];
$routeDistance[$id1][$pStart][$v2['from']] + $v2['distance'] + $routeDistance[$id2][$v2['to']][$pEnd];
$routeDistance[$id1][$pStart][$v3['from']] + $v3['distance'] + $routeDistance[$id2][$v3['to']][$pEnd];
$routeDistance[$id1][$pStart][$v1['from']] – расстояние внутри маршрута.
$v1['distance'] – сколько времени тратится на пересадку, так же в абстрактных единицах.
Соответственно, минимальное значение вычисленных сумм, это и будет наш искомый путь. Дальше восстанавливаем остановки, которые внутри маршрута, но находятся между точкой вхождения в маршрут и выходом из него.
Пример
Для удобства выберем несколько маршрутов:
--ishodniki-2.png "Поиск кратчайшего пути в транспортном графе (концепт) + исходники")
Сворачиваем маршруты в точки и получаем граф:
--ishodniki-3.png "Поиск кратчайшего пути в транспортном графе (концепт) + исходники")
Предположим, что нам нужно доехать от 2 до 5 маршрута.
По нашему графу мы получим такую выборку путей:
--ishodniki-4.png "Поиск кратчайшего пути в транспортном графе (концепт) + исходники")
Далее мы работаем с полученными маршрутами. Нам нужно узнать какой из маршрутов самый «быстрый».
Вычисление значения «привлекательности» маршрута:
- Берем остановку старта маршрута и все возможные остановки пересадки на другой маршрут. По таблице route_distance находим длину пути от остановки старта в рамках маршрута до остановки пересадки.
- Теперь нужно учесть время на пересадку. Добавляем к вычисленной длине в соответствии с таблицей route_cross_point длинны между остановкой с которой пересаживаемся и остановкой, на которую пересаживаемся.
- Повторяем для каждого маршрута.
Возьмем первую строку из нашей выборки
--ishodniki-5.png "Поиск кратчайшего пути в транспортном графе (концепт) + исходники")
$routeDistance[2][p.1][ p.3] + d1 + $routeDistance[3][p.5][ p.6] + d3 + $routeDistance[5][p.7][ p.8] = (float)
$routeDistance[2][p.1][ p.4] + d2 + $routeDistance[3][p.5][ p.6] + d3 + $routeDistance[5][p.7][ p.8] = (float)
$routeDistance – расстояние в рамках маршрута.
d* — время на пересадку.
p.1 – остановка откуда едем.
p.8 – остановка куда едем.
d1 – расстояние между p.3 и p.5
Минимальное число это и есть лучший путь.
Чего не хватает и как можно развивать:
— пока в алгоритме не учитывается существующая сеть дорог и не прокладывает пешеходный маршрут от точки А до остановки транспорта и соответственно от последней остановки городского транспорта из полученного маршрута до точки Б;
— конечно же, можно в дальнейшем считать и стоимости маршрутов и при необходимости вводить опционально выбор критерия, по которому выбирать маршрут (минимум стоимости, времени, пересадок и пр.), пока по умолчанию считаем целевым критерием минимум пересадок;
— если бы ввели тарифы на проезд, зависящие от длины пути, то также в алгоритме не так много нужно было бы добавить;
Исходники скачать. Распаковать. Путь не должен содержать русские символы.
Автор: nirtik
