Расчет кратчайшего пути между двумя точками железнодорожной сети

Я хотел бы рассчитать кратчайший путь от шахт до портов по железнодорожной сети. Поскольку шахты и порты не входят непосредственно в сеть, я сначала определил ближайшую железнодорожную станцию ​​для каждой шахты и порта.

Однако сейчас я пытаюсь преобразовать железнодорожную сеть в граф NetworkX и оттуда вычислить кратчайшее расстояние между каждой шахтой и портом. Когда я запустил свой код, он не смог определить ближайший путь, поскольку все расстояния равны нулю. Ниже приведен код, который я написал на данный момент. Железнодорожную сеть можно скачать здесь. Буду признателен за любую помощь, которая может быть оказана. Спасибо.

# Ports
ports = 
[{'port_name': 'Geraldton', 'geometry': POINT (114.59786 -28.77688)},
{'port_name': 'Bunbury', 'geometry': POINT(115.673447 -33.318797)},
{'port_name': 'Albany', 'geometry': POINT(117.895025 -35.032831)}, 
{'port_name': 'Esperance', 'geometry': POINT(121.897114 -33.871834)}]  

# Mine sites
mines = 
[{'mine_name': 'Gold', 'geometry': POINT (117.94568 -34.93467), 
{'mine_name': 'Silver', 'geometry': POINT (115.16923 -29.65613)},
{'mine_name': 'Bronze', 'geometry': POINT (115.11039 -29.51287)}, 
{'mine_name': 'Platinum', 'geometry': POINT (115.11130 -29.42621)}]

# Convert to GeoDataFrame
crs = 'EPSG:4326'
ports = gpd.GeoDataFrame(ports, crs=crs, geometry = 'geometry')
mine_sites = gpd.GeoDataFrame(ports, crs=crs, geometry = 'geometry')

# Column for nearest rail point
ports['nearest_rail_point'] = None
mine_sites['nearest_rail_point'] = None

# Nearest rail point
for index, row in ports.iterrows():
    port_point = row['geometry']
    nearest_point = nearest_points(port_point, rail_network.unary_union)[1] 
    ports.at[index, 'nearest_rail_point'] = nearest_point

for index, row in mine_sites.iterrows():
    mine_site_point = row['geometry']
    nearest_point = nearest_points(mine_site_point, rail_network.unary_union)[1] 
    mine_sites.at[index, 'nearest_rail_point'] = nearest_point

G = momepy.gdf_to_nx(rail_network)

shortest_distances = {}

# Calculate shortest path
for mine_index, mine_row in mines.iterrows():
    mine_name = mine_row['mine_name']
    mine_point = mine_row['geometry']
    
    shortest_distances[mine_name] = {}
    
    for port_index, port_row in ports.iterrows():
        port_name = port_row['port_name']
        port_point = port_row['geometry']

        try:
            shortest_distance = nx.shortest_path_length(G, 
                                                        source=(mine_point.x, mine_point.y), 
                                                        target=(port_point.x, port_point.y), 
                                                        weight='length')
            shortest_distances[mine_name][port_name] = shortest_distance
        except nx.NetworkXNoPath:
            shortest_distances[mine_name][port_name] = float('inf')  # No path found

«Мне трудно» — неправильный вопрос. Как спросить и минимальный воспроизводимый пример

Julien 11.07.2024 02:55

Какая дополнительная информация вам нужна, чтобы иметь возможность помочь?

user15852004 11.07.2024 05:18
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
2
70
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Неясно, нужен ли вам кратчайший путь между каждым мином и соответствующим портом (с тем же индексом) или между всеми портами. В любом случае, одним из вариантов было бы использовать простой подход (с Momempy ) для создания графа и вычисления shortest_path_length (или shortest_path, в зависимости от ожидаемого результата). Однако перед этим нужно привязать мины к ближайшей границе железной дороги:

spots = (pd.concat([
    ports.rename(columns = {"port_name": "spot_name"}),
    mine_sites.rename(columns = {"mine_name": "spot_name"})])
             .to_crs("EPSG:3857"))

import momepy
G = (momepy.gdf_to_nx(
    rail_network[["name", "geometry"]].explode(),
    approach = "primal", multigraph=False, length = "dis"))

def nearest_bnd(p, ls, shp=False):
    sp, *_, ep = ls.coords
    nb = min(map(Point, [sp, ep]), key=p.distance)
    return nb if shp else (nb.x, nb.y)
        
coos = (spots.rename_geometry("geom_sp")
        .sjoin_nearest(rail_network.assign(geom_rn=rail_network["geometry"]))
        .set_geometry("geom_rn").assign(coo=lambda x: [nearest_bnd(p, ls)
        for p, ls in x[["geom_sp", "geom_rn"]].to_numpy()])
        .set_index("spot_name")["coo"])

all_spl = {}
for mn in mine_sites["mine_name"]:
    for pn in ports["port_name"]:
        try:
            uv = map(coos.get, [mn, pn])
            spl = nx.shortest_path_length(G, *uv, weight = "dis")
            spl = round(spl / 1000, 2)
        except nx.NetworkXNoPath:
            spl = float("inf")
        all_spl.setdefault(mn, []).append({pn: spl})

{mn: min(d, key=lambda x: list(x.values())[0]) for mn, d in all_spl.items()}

# {
#     "Gold": {"Albany": 0.0},
#     "Silver": {"Geraldton": 117.85},
#     "Bronze": {"Geraldton": 117.85},
#     "Platinum": {"Geraldton": 117.85},
# }

Другие вопросы по теме