Привет! На связи команда геоаналитики ecom.tech, мы строим модели машинного обучения на основе пространственных данных для задач ритейла в реальном времени, а также создаем промежуточные инструменты на базе методов прикладной геоаналитики. На наших технологиях работает Самокат и Мегамаркет.
Например, наша команда решает задачу поиска оптимального расположения даркстора (место, где хранятся продукты, а также собираются заказы). Зона покрытия даркстора — радиус в пару километров, и количество их постоянно увеличивается. Мы хотим уметь размещать новый даркстор так, чтобы как можно больше людей получали заказы за минимальное время доставки.
В этой статье мы расскажем, как выбираем локации для новых дарксторов: определимся с постановкой задачи, погрузимся в контекст проекта и покажем, как можно анализировать сотни тысяч разных точек на карте в секунду.
Как устроен поиск локации новых дарксторов?
Для решения задач поиска ближайших объектов и кратчайших расстояний в основном используются решения для работы с графами. Задача поиска кратчайшего пути является одной из самых важных в теории графов, а также в прикладной геоаналитике, поэтому читателям, которые решают похожие задачи, вероятно, будет интересно познакомиться с новыми инструментами.
Рассмотрим внутреннее устройство системы поиска новых локаций дарксторов, которая позволяет быстро получать рекомендации для их размещения с учетом того, что курьеры-партнёры должны доставлять заказы максимально быстро.
Итак, мы получаем новую локацию, где хотим открыть еще один даркстор Самоката. Сначала из всего множества вариантов нужно выбрать наиболее релевантные для аренды. На этом этапе мы получили список зданий, который хотим отранжировать и показать пользователю лучшие места для открытия нового даркстора.
После того, как все релевантные объекты выбраны, начинаем ранжирование потенциальных локаций. Ранжирование происходит в несколько этапов. В данной статье я подробно расскажу про первый этап, который заключается в расчете кратчайшего пути между всеми зданиями. Другими словами, мы считаем матрицу взвешенных попарных расстояний между объектами для новой территории. Данный этап особенно важен, так как позволяет найти локации с более высокой плотностью потенциальных покупателей.
Где будет расположен следующий даркстор?
Если мы окажемся на месте человека который принимает решение, как развивать сеть дарксторов, то очень быстро окажемся перед картой, на которой будут дома, социальные объекты, магазины и все остальное, что мы привыкли искать в городе.
Для анализа мы используем две библиотеки, osmnx и networkx. В связке данные инструменты позволяют визуализировать граф в удобном для восприятия формате, как на примере снизу.
Код для визуализации карты
from osmnx.graph import graph_from_address
from osmnx.plot import plot_graph
from contextily import add_basemap, providers
import matplotlib.pyplot
address = "91, улица Чапаева, Nizhnevartovsk, Khanty-Mansiysk Autonomous Okrug – Ugra, Ural Federal District, 628615, Russia"
G = graph_from_address(address, dist_type="network")
_, ax = plot_graph(
G,
bgcolor="white",
edge_color="black",
node_color="c",
node_alpha=0.0,
edge_alpha=0.0,
edge_linewidth=1,
node_size=25,
show=False,
)
add_basemap(
ax,
source=providers.OpenStreetMap.Mapnik,
crs=G.graph["crs"]
)
matplotlib.pyplot.show()
В качестве примера анализа территории для открытия нового даркстора мы взяли район города Нижневартовска: там пока еще нет Самоката. Для этого района мы хотим провести анализ и предложить точку на карте, где лучше всего разместить даркстор.
Чтобы начать анализ этой территории, надо посмотреть на устройство этого района. Как вариант, мы можем получить все объекты из OpenStreetMap (OSM), как по названию города, района или улицы, так и по координатам.
Код для визуализации узлов на карте
from osmnx.graph import graph_from_address
from osmnx.plot import plot_graph
from contextily import add_basemap, providers
import matplotlib.pyplot
address = "91, улица Чапаева, Nizhnevartovsk, Khanty-Mansiysk Autonomous Okrug – Ugra, Ural Federal District, 628615, Russia"
G = graph_from_address(address, dist_type="network")
_, ax = plot_graph(
G,
bgcolor="white",
edge_color="black",
node_color="c",
node_alpha=0.75,
edge_alpha=0.0,
edge_linewidth=1,
node_size=25,
show=False,
)
add_basemap(
ax,
source=providers.OpenStreetMap.Mapnik,
crs=G.graph["crs"]
)
matplotlib.pyplot.show()
С помощью функции graph_from_address получим все ноды (узлы) из OSM для этого района и отобразим их на карте. Ноды в нашем случае это начала и окончания всех доступных путей в этом районе. На карте мы отметим их бирюзовыми точками.
После мы можем связать все ноды между собой, чтобы посчитать попарные расстояния между всеми объектами для нахождения наиболее перспективных локаций. Поэтому, следующим шагом мы свяжем наши точки с помощью ребер. Итоговый граф отобразим с помощью черных линий между нодами.
Код для визуализации графа карты
from osmnx.graph import graph_from_address
from osmnx.plot import plot_graph
from contextily import add_basemap, providers
import matplotlib.pyplot
address = "91, улица Чапаева, Nizhnevartovsk, Khanty-Mansiysk Autonomous Okrug – Ugra, Ural Federal District, 628615, Russia"
G = graph_from_address(address, dist_type="network")
_, ax = plot_graph(
G,
bgcolor="white",
edge_color="black",
node_color="c",
node_alpha=0.75,
edge_alpha=0.75,
edge_linewidth=1,
node_size=25,
show=False,
)
add_basemap(
ax,
source=providers.OpenStreetMap.Mapnik,
crs=G.graph["crs"]
)
matplotlib.pyplot.show()
Изначально, для решения задачи поиска кратчайшего пути мы использовали библиотеку networkx. В данной библиотеке реализован метод all_pairs_dijkstra_path_length, который вернет нам попарные расстояния для всех доступных нод в нашем графе. Для графа такого размера расчет в среднем займет 30 секунд.
Спойлер
Отвечая на вопрос из названия заголовка – самую лучшую локацию подсветили красным цветом, именно там может быть размещен следующий даркстор.
Отлично, теперь мы можем еще добавить дополнительные показатели для каждой ноды и рассчитать попарные взвешенные расстояния для всех доступных объектов.
В результате получим декартово произведение множества всех доступных точек. Как итог, мы можем поделиться результатами расчетной части алгоритма и отобразить на карте наиболее оптимальные локации для размещения даркстора.
На карте можем наблюдать множество точек разного цвета. Каждая точка – это здание, которое в теории можно арендовать. Соответственно, чем темнее точка, тем выгоднее локация для размещения потенциального даркстора. Мы выводим все точки, т.к. не всегда самая выгодная локация доступна для аренды.
networkx хорошо справляется с небольшими территориями, но если нам нужно анализировать небольшие города или сравнивать большое количество районов, то расчет будет занимать слишком много времени. Проблема networkx в том, что он полностью написан на Python и поэтому не очень производительный.
Зачем ускорять расчет?
На данный момент количество дарксторов Самоката составляет более 2300 в 129 городах присутствия и расчет оптимального расположения новых дарксторов один из самых ресурсоемких сервисов в геоаналитике. Каждый раз, когда приходит запрос, сервис просчитывает более 100 тысяч пеших маршрутов за секунды, чтобы найти наиболее выигрышные локации
Недостаток в скорости сильно влияет на пользовательский опыт, а в условиях роста количества городов для открытия новых дарксторов, растет и потребность в более быстрых вычислениях. Чтобы справляться с нарастающей нагрузкой мы распределили расчеты на несколько CPU, что давало на старте кратный рост в скорости.
Однако этого было недостаточно, поскольку для анализа новой территории пользователю приходилось ждать 5-10 минут, а потенциальных зон для анализа могло быть больше сотни. Конечно, можно было бы продолжать масштабироваться вертикально, но чем больше становились вычислительные машины, тем дороже нам это выходило.
Поэтому перед нами встал вопрос о том, как сделать расчет еще быстрее, но затратить на это минимальное количество ресурсов.
Все быстрее на C++
Написание интерфейсов на Python для оборачивания C/C++ модулей может сильно ускорить код, чего невозможно было бы достичь непосредственно на Python. Такая практика активно внедряется в экосистему Python.
Примером реализации такого интерфейса для работы с графами является библиотека igraph. В данной библиотеке имеется весь необходимый функционал для более быстрого расчета кратчайшего пути.
На момент поиска альтернативных инструментов, которые могли бы быстрее справиться с поставленной задачей, уже существовал «серый кардинал», который успел набрать популярность и зарекомендовать себя, как абсолютный лидер по скорости в решении задачи коммивояжера, а именно rustworkx — о нем и пойдет речь.
Серый кардинал
На сегодня можно сказать, что Rust плотно вошел в экосистему Python. Наверняка вы слышали о таких проектах как pydantic-core и polars, uv и ruff и так далее. Некоторые из них стали революционными для Python.
К таким проектам можно добавить и rustworkx — быстрый, надежный, набирающий популярность и активно поддерживающийся сообществом инструмент для работы с графами и сложными сетями, который отличается более высокой производительностью.
Кто быстрее
Ниже будут приведены примеры сравнений основных операций, которые используются при решении задачи поиска кратчайшего пути, а именно: расчет кратчайшего пути из одной точки в другую и расчет кратчайшего пути для всех доступных точек. Код для получения графа и сравнения скорости работы разных фреймворков доступен в Google Colab.
Поиск кратчайшего пути между двумя нодами
Для сравнения скорости мы взяли уже целый город Нижневартовск. Для каждой библиотеки запустили поиск кратчайшего пути, всего было 100 итераций, на каждой из которой выбирали две случайные ноды из всего графа. Видно, что igraph на два порядка быстрее networkx и на порядок быстрее rustworkx.
Попарный поиск всех расстояний
В данном примере сравниваем время расчета расстояния между всеми узлами графа для одного из районов Нижневартовска. Вы спросите почему не весь город, потому что ресурсов в публичном Google Colab недостаточно для таких расчетов, а хотелось сделать воспроизводимый пример, который был бы доступен каждому.
Кто лучше?
В сравнительном анализе из официальной документации rustworkx показал лучшие результаты для задач поиска кратчайшего пути и попарных расстояний. В нашем случае, для задачи кратчайшего пути лучше оказался igraph. Как и для других инструментов, все новые библиотеки лучше самостоятельно тестировать на своих примерах. Сейчас мы используем igraph и rustworkx под каждую конкретную задачу и потихоньку уходим от networkx. В задаче поиска оптимальной локации переход на rustworkx позволил сократить время расчетов в 1,5 раза и сократить количество используемых ядер с 70 до 1.
rustworkx удобная и быстрая библиотека для работы с большими графами. Стоит учитывать, что данный инструмент довольно молод, поэтому имеет ограниченный функционал по сравнению с аналогами. Библиотеку будет удобно использовать для ускорения той части кода, где идет работа с тяжеловесными графовыми алгоритмами.
Также, благодаря ускорению, данные о рекомендациях из нового расчета «Оптимального расположения» стали использоваться не только для получения таких рекомендаций, но и нашли применение в других наших проектах для анализа пространственных данных. Это расширение области применения алгоритма позволило ускорить обработку и анализ данных как в самом проекте, так и обогатить данные для аналитики в других сервисах.
Не стесняйтесь изучать отличные от дефолтных инструменты, пишите свои и желаем удачи!
