SQL и Базы Данных

🚗 Как найти кратчайший маршрут с помощью Apache Spark и GraphFrames

Разбираем кейс на реальных данных из OpenStreetMap — ищем оптимальный маршрут

🔍 Что делаем
1. Загружаем граф дорог города с помощью OSMnx
2. Сохраняем вершины и ребра с координатами, скоростями и геометрией
3. Загружаем всё в Spark
4. Находим кратчайший путь с помощью GraphFrames

📍 1. Скачиваем карту и строим граф улиц

import osmnx as ox

# Загрузка данных о дорогах Москвы
G = ox.graph.graph_from_place("Moscow", network_type="drive")

# Отображение дорог на карте
moscow_gdf = ox.geocoder.geocode_to_gdf("Moscow")
fig, ax = ox.plot.plot_graph(G, show=False, close=False, bgcolor="#111111", edge_color="#ffcb00", edge_linewidth=0.3, node_size=0)
moscow_gdf.plot(ax=ax, fc="#444444", ec=None, lw=1, alpha=1, zorder=-1)

# Настройка границ карты
margin = 0.02
west, south, east, north = moscow_gdf.union_all().bounds
margin_ns = (north - south) * margin
margin_ew = (east - west) * margin
ax.set_ylim((south - margin_ns, north + margin_ns))
ax.set_xlim((west - margin_ew, east + margin_ew))
plt.show()

📁 2. Сохраняем геометрическое описание города в формате GeoJSON и данные о вершинах и рёбрах в формате CSV

with open('Moscow.geojson', 'w') as file:
    file.write(moscow_gdf.to_json())

nodes = G.nodes(data=True)
with open('nodes.csv', 'a') as file:
    file.write("id,lat,lonn")
    for (node, data) in nodes:
        file.write("%d,%f,%fn" % (node, data.get("y"), data.get("x")))

edges = G.edges(data=True)
def decode_maxspeed(maxspeed):
    match maxspeed:
        case str():
            match maxspeed.lower():
                case "ru:urban": return 60
                case "ru:rural": return 90
                case "ru:living_street": return 20
                case "ru:motorway": return 110
                case _: return int(maxspeed)
        case list(): return min(list(map(decode_maxspeed, maxspeed)))
        case _: return maxspeed

with open('edges.csv', 'a') as file:
    file.write("src,dst,maxspeed,length,geometryn")
    for (src, dst, data) in edges:
        maxspeed = decode_maxspeed(data.get("maxspeed", 999))
        length = float(data.get("length"))
        geometry = shapely.wkt.dumps(data.get("geometry"))
        file.write("%d,%d,%d,%f,%sn" % (src, dst, maxspeed, length, geometry))

3. Используем библиотеку GraphFrames для обработки графов на Apache Spark

from pyspark.sql import SparkSession

spark = SparkSession.builder 
    .config("spark.jars.packages", "graphframes:graphframes:0.8.4-spark3.5-s_2.12") 
    .master("local[*]") 
    .appName("GraphFrames") 
    .getOrCreate()

nodes = spark.read.options(header=True).csv("nodes.csv")
edges = spark.read.options(header=True).csv("edges.csv")

# Вычисление времени прохождения рёбер
edgesT = edges.withColumn("time", edges["length"] / edges["maxspeed"])

# Построение графа
from graphframes import *

g = GraphFrame(nodes, edgesT)

🧭 4. Ищем кратчайший путь по времени
например, от Измайлово до ЖК Зиларт

src = "257601812"
dst = "5840593081"

paths = g.shortestPaths(landmarks=[dst])
paths.filter(F.col("id") == src).show(truncate=False)

💡 Результат: 40 шагов от точки A до точки B.

Такой подход легко масштабируется на миллионы маршрутов. Используйте Spark и GraphFrames для построения логистических моделей, маршрутизации и городского планирования.

🚀 Хотите прокачаться в работе с Big Data? Изучайте Spark! Записывайтесь на курс Spark Developer от OTUS — учитесь на реальных данных и продвинутых кейсах: https://vk.cc/cNrOCj

🎁Пройдите тест, чтобы успеть воспользоваться 10% скидкой на курс и бонусным промокодом Spark_05. Предложение действует до 6 июля 2025 года.

870 views07:45