Удалить почти параллельный путь кратчайшего пути NetworkX

Я создал путь между точками A и B с ограничением мест, которые я должен пройти, бросая их или близко к ним, поэтому маршрут выглядит так: A -> c1 -> c2 - > B, хотя это не самый короткий путь.

Я использовал for path in nx.all_shortest_paths(UG, source=l1_node_id, target=l2_node_id,weight = 'wgt'):

когда 'wgt' - это расстояние до края / скорость движения по этой дороге.

Я создал список списков, где каждый внутренний список - это node_id, например:

l_list = [
    [n11,n12,n13,n14....]
    [n21,n22,n23,n24....]
         ..
    ]

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

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

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

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


python shortest-path osmnx networkx
person Roy Ancri    schedule 12.01.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Во-первых, вам нужно более кратко или более формально определить, что является «почти параллельным», вам нужно определить функцию подобия.

Выбор функции подобия / расстояния

Существует множество способов определить функцию подобия, вот один из них.

Повторная выборка

Предполагая, что каждый узел n_i имеет координаты x и y (n_i_x,n_i_y). Вы можете выполнить повторную выборку точек на оси x, чтобы новые точки выбирались на 1km.

Затем для каждых 2 маршрутов вы можете суммировать разницу по оси y. Используйте это расстояние для кластеризации маршрутов.

Другие идеи

Кластеризация

После определения функции similarity вы можете использовать алгоритм кластеризации на основе расстояния, я рекомендую использовать агломеративная кластеризация sklearn.

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

person Uri Goren    schedule 19.01.2020
comment
Может быть, я не понял, на самом деле нет двух маршрутов, как вы можете видеть, у меня есть три пути, каждый из которых начинается от маркера и окрашен в черный, красный и синий цвета. Моя цель - преобразовать его в один путь от начала черного пути (слева вверх) до конца синего пути (справа вверх). каждый путь - это отдельный набор идентификаторов узлов, возможно, с некоторыми общими узлами между разными путями. Так что, может быть, я вас не понял, но функция расстояния может мне помочь? - person Roy Ancri; 19.01.2020
comment
да, я понял. Для двух маршрутов определите функцию подобия d (r1, r2), а затем запустите ее для всех маршрутов. у вас есть квадратная матрица формы (N, N), где N - количество маршрутов. Подайте эту матрицу расстояний в алгоритм кластеризации и выберите по одному представителю из каждого кластера. - person Uri Goren; 19.01.2020
comment
Хорошо, теперь я понимаю, о чем ты. Спасибо - person Roy Ancri; 19.01.2020
comment
Я думал, что сделал, как мне это сделать? - person Roy Ancri; 25.01.2020