Блог

Я разрабатываю систему маршрутизации для поиска наилучших маршрутов, используя несколько предложений мобильности, например, общественный транспорт или объединение автомобилей. В основном у меня есть узлы, которые представляют автобусные остановки, остановки поездов и т.д. Эти остановки включают временные графики на каждый день. Кроме того, у меня есть пешеходные остановки. Эти остановки связаны отношениями. Если я переключаюсь с пешехода на автобус или между линиями автобусов, отношение называется SWITCH_TO . Если я проезжаю несколько остановок без изменения линии обслуживания, остановки соединяются отношением, называемым CONNECTED_TO . Если я хочу перейти из точки A в точку Z, и мне нужно пересесть на автобусной остановке C на другую линию обслуживания на автобусной остановке D, путь будет выглядеть следующим образом:

 (A:Stop:Pedestrian)-[SWITCH_TO{switchTime:2}]->
(A:Stop:Bus{serviceLine:1})-[CONNECTED_TO{travelTime:5}]->
(B:Stop:Bus{serviceLine:1})-[CONNECTED_TO{travelTime:6}]->
(C:Stop:Bus{serviceLine:1})-[SWITCH_TO{switchTime:2}]->
(C:Stop:Pedestrian)-[CONNECTED_TO{travelTime:7}]->
(D:Stop:Pedestrian)-[SWITCH_TO{switchTime:2}]->
(D:Stop:Bus{serviceLine:2})-[CONNECTED_TO{travelTime:8}]->(Z:Stop:Bus{serviceLine:2})-[SWITCH_TO{switchTime:2}]->
(Z:Stop:Pedestrian)
  

Я хочу рассчитать на основе желаемого времени отправления (или желаемого времени прибытия) пользователя полное время в пути и получить 5 лучших соединений (меньше времени).
В приведенном выше примере вы можете видеть, что отношение SWITCH_TO имеет время переключения, равное 2. Это означает, что мне нужно 2 минуты, чтобы переключиться с текущего места на автобусную остановку (например, я должен ее искать). Время в пути по отношению CONNECTED_TO — это периоды времени, которые автобус должен пройти от одной остановки до другой.
Предположим, что я хочу начать в 7:00. Для первого переключения требуется 2 минуты. Поэтому я должен посмотреть расписание (A: Stop: Bus), если есть отправление после 7:02. Предположим, что следующее отправление в 7:10. тогда мне нужно подождать 8 минут. Это время ожидания не является фиксированным значением, а переменным периодом времени для каждого конкретного запроса. Я начинаю с 7:10. Мне нужно 5 6 = 11 минут, чтобы дойти до остановки (C: Stop: Bus) и 2 минуты, чтобы выйти из автобуса (переключиться на). Затем мне нужно пройти 7 минут пешком. Итак, если нужно проверить расписание строки обслуживания 2. Если есть отклонение после 7:00 2 8 5 6 2 7 2 = 7:32, возьми это. Если следующий вылет в 7:35, я доберусь до места назначения в 7:00 2 8 5 6 2 7 2 3 8 2= 7:45. Я знаю, я немного сложный. 🙂

Я подготовил пример здесь:

 CREATE (newStop:Stop:Pedestrian {
    stopName : 'A-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'A-Bus',
    mode : 'Bus',
    serviceLine : '1',
    monday:[510,610,710,810,835,910],
    tuesday:[510,610,710,810,835,910],
    wednesday:[510,610,710,810,835,910],
    thursday:[510,610,710,810,835,910],
    friday:[510,610,710,810,835,910],
    saturday:[510,610,710,810,835,910],
    sunday:[510,610,710,810,835,910]
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'B-Bus',
    mode : 'Bus',
    serviceLine : '1',
    monday:[515,615,715,815,840,915],
    tuesday:[515,615,715,815,840,915],
    wednesday:[515,615,715,815,840,915],
    thursday:[515,615,715,815,840,915],
    friday:[515,615,715,815,840,915],
    saturday:[515,615,715,815,840,915],
    sunday:[515,615,715,815,840,915]
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'C-Bus',
    mode : 'Bus',
    serviceLine : '1',
    monday:[521,621,711,821,846,921],
    tuesday:[521,621,711,821,846,921],
    wednesday:[521,621,711,821,846,921],
    thursday:[521,621,711,821,846,921],
    friday:[521,621,711,821,846,921],
    saturday:[521,621,711,821,846,921],
    sunday:[521,621,711,821,846,921]
})
RETURN newStop;

CREATE (newStop:Stop:Pedestrian {
    stopName : 'C-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;

CREATE (newStop:Stop:Pedestrian {
    stopName : 'D-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'D-Bus',
    mode : 'Bus',
    serviceLine : '2',
    monday:[535,635,735,835,935],
    tuesday:[535,635,735,835,935],
    wednesday:[535,635,735,835,935],
    thursday:[535,635,735,835,935],
    friday:[535,635,735,835,935],
    saturday:[535,635,735,835,935],
    sunday:[]
})
RETURN newStop;

CREATE (newStop:Stop:Bus {
    stopName : 'Z-Bus',
    mode : 'Bus',
    serviceLine : '2',
    monday:[543,643,743,843,943],
    tuesday:[543,643,743,843,943],
    wednesday:[543,643,743,843,943],
    thursday:[543,643,743,843,943],
    friday:[543,643,743,843,943],
    saturday:[543,643,743,843,943],
    sunday:[]
})
RETURN newStop;

CREATE (newStop:Stop:Pedestrian {
    stopName : 'Z-Pedestrian',
    mode : 'Pedestrian'
})
RETURN newStop;




MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'A-Pedestrian' AND s2.stopName = 'A-Bus'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'A-Bus' AND s2.stopName = 'B-Bus'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 5 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'B-Bus' AND s2.stopName = 'C-Bus'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 6 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'C-Bus' AND s2.stopName = 'C-Pedestrian'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'C-Pedestrian' AND s2.stopName = 'D-Pedestrian'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 7 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'D-Pedestrian' AND s2.stopName = 'D-Bus'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'D-Bus' AND s2.stopName = 'Z-Bus'
CREATE
    (s1)-[r:CONNECTED_TO{ travelTime : 8 } ]->(s2)
RETURN s1, s2, r;

MATCH (s1:Stop), (s2:Stop)
WHERE s1.stopName = 'Z-Bus' AND s2.stopName = 'Z-Pedestrian'
CREATE
    (s1)-[r:SWITCH_TO{ switchTime : 2 } ]->(s2)
RETURN s1, s2, r;
  

Как вы можете видеть, на некоторых остановках массив времени отправления int также может быть пустым (если в эти дни соединение не предоставляется). Пешеходные остановки, конечно, не включают расписание.
Мой вопрос: как я могу выполнить этот запрос с помощью cypher? Я должен суммировать это время, чтобы выбрать правильное время следующего вылета. Я должен знать, когда я нахожусь в пункте назначения. И я хочу показать пользователю лучшие 5 соединений. Есть ли способ сделать это? Если нет, есть какие-либо предложения, как это решить?

Большое вам спасибо! Стефан

Edit1: Есть ли способ разработать это на Java? В простейшем случае это может быть только один кратчайший путь, но с интеллектуальной функцией затрат? Вместо использования фиксированных значений с использованием функции для вычисления стоимости одного конкретного ребра? Любая помощь будет оценена!

[Заранее извиняюсь, это превратилось в русский роман, когда я не смотрел. И это все равно даст вам только один самый быстрый маршрут, а не 5 самых быстрых, но, надеюсь, кто-то умнее, чем я, сможет улучшить это.]

Вы пытаетесь выполнить какой-то дьявольски сложный путь, основанный на труднорасчетной стоимости . Вам определенно потребуется провести некоторый рефакторинг, чтобы вы могли немного более жестко зафиксировать стоимость, а затем применить apoc.algo.dijkstra , чтобы получить жизнеспособный путь с весом. Для этого вам нужно будет перейти от вашей очень общей модели к какой-то «цепочке» событий, организованной по физическому местоположению. Режимы транзита в сочетании с еженедельным расписанием обеспечат вам некоторую структуру здесь; возможность перехода между местоположениями усложнит это лишь умеренно. Попутно мы удалим некоторые из менее значимых и избыточных узлов. Давайте углубимся.

Перво-наперво, нам нужно иметь возможность конвертировать ваше время во что-то, поддающееся машинному анализу. Вы можете использовать apoc их для преобразования isoformat в или аналогичные, но для циклических периодов времени, которые потребуют частого упорядочения и существуют только в минутном масштабе, я говорю, начните считать полночь в воскресенье утром как минуту 0, а затем посчитайте свой путь оттуда. Итак, в основном, вас будут беспокоить минуты с воскресенья до полуночи, а затем с некоторыми хитростями позже вы сможете справиться с циклической частью.

 MATCH (stop:Stop:Bus)
WITH stop, ['sunday', 'monday', 'tuesday', 'wednesday', 'thursday', 'friday', 'saturday'] AS days
UNWIND RANGE(0, 6) AS day_index
WITH stop, day_index, days[day_index] AS day_key
UNWIND stop[day_key] AS int_time
WITH stop, day_index * 24 * 60 AS day_minutes, int_time % 100 AS minutes, ((int_time - (int_time % 100))/100)*60 AS hour_minutes 
WHERE day_minutes IS NOT NULL
WITH stop, day_minutes   hour_minutes   minutes AS time_since_sunday
MERGE (dep:Departure:Bus {time: time_since_sunday})
MERGE (dep) - [:AT] -> (stop)
WITH stop, time_since_sunday
ORDER BY time_since_sunday
WITH stop, collect(time_since_sunday) AS times
SET stop.departure_times = times
  

Хорошо, это дает нам события отправления вокруг каждой автобусной остановки, которые представляют время, в которое вы можете начать поездку фиксированной длины в другом месте, если вы находитесь на станции до этого времени. Теперь, если бы мы учитывали только движение на основе транзита, мы могли бы подключить каждый :Departure узел по одному :Stop к любому :Departure узлу, который был доступен на следующей остановке по истечении времени прохождения (и учитывать время ожидания). Однако добавление ходьбы (многорежимный транспорт) немного меняет ситуацию, поскольку всякий раз, когда куда-то прибывает транзит, вы можете просто «уйти» на своих двоих мгновенно. Итак, мы должны моделировать :Arrival узлы так, чтобы они соответствовали другому концу :Departure основанных поездок, чтобы мы могли различать ожидание следующего транзитного :Departure перехода и хождение по времени.

 MATCH (stop:Stop:Bus) <- [:AT] - (dep:Departure:Bus)
WITH stop, dep, dep.time AS dep_time
MATCH (stop) - [r:CONNECTED_TO] -> (other:Stop:Bus)
WITH dep, dep_time, dep_time   r.travelTime AS arrival_time, other
MERGE (a:Arrival:Bus {time: arrival_time})
MERGE (a) - [:AT] -> (other)
MERGE (dep) - [:TRAVEL {time: arrival_time - dep_time, mode: 'Bus'}] -> (a)
WITH a, arrival_time, other, other.departure_times AS dep_times
WITH a, other, arrival_time, REDUCE(s = HEAD(dep_times), x IN TAIL(dep_times) | CASE WHEN x < arrival_time THEN s WHEN s < x THEN s ELSE x END) AS next_dep_time
WITH a, other, next_dep_time, next_dep_time - arrival_time AS wait_time
MATCH (other) <- [:AT] - (next_dep:Departure:Bus {time: next_dep_time})
MERGE (a) - [:TRAVEL {time: wait_time, mode: 'Wait'}] -> (next_dep)
  

Хорошо, итак, для каждой отдельной транзитной линии теперь мы можем рассчитать, сколько времени потребуется, чтобы добраться из пункта А в пункт В только по этой транзитной линии, даже если движение не является непрерывным (поезд останавливается на остановке и т. Д.). Теперь самое интересное: интеграция опции ходьбы! Идея «остановки пешехода» не имеет большого смысла (если только вы не моделируете все соответствующее дискретное пространство, и в этом случае удачи и удачи), поэтому мы в основном собираемся полностью отказаться от них. A :SWITCH_TO , который работает между двумя остановками, не являющимися пешеходными, будет просто смоделирован как переход между двумя остановками, в то время :SWITCH_TO как пешеходный переход будет преобразован в длинную прогулку, объединяющую оба переключателя и саму прогулку. Сначала самые простые (которых нет в ваших образцах путей, но я думаю, что в конечном итоге они будут полезны для вас):

 MATCH (stop:Stop:Bus) - [r:SWITCH_TO] -> (other:Stop)
WHERE NOT other:Pedestrian
WITH stop, other, r.switchTime AS walking_time, other.departure_times AS dep_times
MATCH (stop) <- [:AT] - (arr:Arrival)
WITH arr, other, walking_time, dep_times, arr.time   walking_time AS new_arr_time
MERGE (new_arr:Arrival:Pedestrian {time: new_arr_time})
MERGE (new_arr) - [:AT] -> (other)
MERGE (arr) - [:TRAVEL {time:walking_time, mode: 'Pedestrian'}] -> (new_arr)
WITH new_arr, other, new_arr_time, REDUCE(s = HEAD(dep_times), x IN TAIL(dep_times) | CASE WHEN x < new_arr_time THEN s WHEN s < x THEN s ELSE x END) AS next_dep_time
WITH new_arr, other, next_dep_time, next_dep_time - new_arr_time AS wait_time
MATCH (other) <- [:AT] - (next_dep:Departure {time:next_dep_time})
MERGE (new_arr) - [:TRAVEL {time: wait_time, mode: 'Wait'}] -> (next_dep)
  

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

 MATCH (stop:Stop:Bus) - [r1:SWITCH_TO] -> (:Stop:Pedestrian) - [r2:CONNECTED_TO] -> (:Stop:Pedestrian) - [r3:SWITCH_TO] -> (other:Stop)
WITH stop, other, other.departure_times AS dep_times, REDUCE(s = 0 , x IN [r1, r2, r3] | s   COALESCE(x.travelTime, x.switchTime) ) AS walking_time
MATCH (stop) <- [:AT] - (arr:Arrival)
WITH arr, other, dep_times, walking_time, arr.time   walking_time AS new_arr_time
MERGE (new_arr:Arrival:Pedestrian {time:new_arr_time})
MERGE (new_arr) - [:AT] -> (other)
MERGE (arr) - [:TRAVEL {time:walking_time, mode: 'Pedestrian'}] -> (new_arr)
WITH new_arr, new_arr_time, other, REDUCE(s = HEAD(dep_times), x IN TAIL(dep_times) | CASE WHEN x < new_arr_time THEN s WHEN s < x THEN s ELSE x END) AS next_dep_time
WITH new_arr, other, next_dep_time, next_dep_time - new_arr_time AS wait_time
MATCH (other) <- [:AT] - (next_dep:Departure {time:next_dep_time})
MERGE (new_arr) - [:TRAVEL {time: wait_time, mode: 'Wait'}] -> (next_dep)
  

Это дает вам базовую структуру взвешенных отношений для применения dijkstra алгоритма к вашему движению между остановками. Может быть некоторая оценка, чтобы выяснить, какие остановки могут дать хорошие результаты, и как пройти к / от них от / до заданной точки (см. Предыдущее утверждение re: моделирование всего дискретного пространства), но если вы можете точно :Departure :Arrival определить узел or для начала (или несколько кандидатов), иузел :Stop для другого конца вашего запроса:

 MATCH (:Stop {stopName: {begin_id} }) <- [:AT] - (d:Departure {time: {depart_time} })
WITH d
MATCH (end:Stop {stopName: {end_id} })
CALL apoc.algo.dijkstraWithDefaultWeight(d, end, 'TRAVELS>|AT>', 'time', 0) YIELD path, weight
RETURN path