如何在NetworkX路径规划图中实现窄通道同进同出约束？

我正在用Python开发仓库多拣选点路径规划系统，仓库布局包含宽通道和超窄通道。现实场景里，超窄通道要求拣选员把推车留在入口，原路返回——也就是必须从同一侧（顶部或底部）进出，只有指定交叉通道可以完全穿行。

我现在用的是2D可行走区域方案，基于0.5m分辨率的允许点生成NetworkX图，用nx.shortest_path计算拣选点间的最短路径。

核心需求 #

• 指定超窄通道必须满足：从一侧进入则从同一侧退出；
• 仅交叉通道允许双向穿行。

有没有有效方法在NetworkX或者图结构本身中约束遍历行为，给特定区域强制执行这种「仅可掉头」的规则？

补充说明与简化代码 #

给定四个拣选点，期望路线是：从底部进入112通道访问P1，再前往113通道的P2，之后从底部离开通道，再进入114通道分别访问P3和P4。

# -*- coding: utf-8 -*-

import pandas as pd
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
import networkx as nx


# ------------------- 定义仓库布局 -------------------
# 垂直货架通道的可视化X坐标
visual_positions = {
    111: -5.4,
    112: -4.8,
    113: -3.2,
    114: -2.6,
}

# 仅允许单侧访问的通道
shelf_access_side = {
    111: "left",
    112: "right",
    113: "left",
    114: "right"
}

# 生成垂直通道的拣选Y坐标
pick_locations = {
    111: [round(2.9 + i * (1.3 / 3), 3) for i in range(48)],
    112: [round(2.9 + i * (1.3 / 3), 3) for i in range(48)],
    113: [round(2.9 + i * (1.3 / 3), 3) for i in range(48)],
    114: [round(2.9 + i * (1.3 / 3), 3) for i in range(48)],
}

# 可行走区域（开放空间+窄通道入口）
walkable_areas = [
    ((-7, 0), (0, 2.9)),            # 底部走道
    ((-7, 24), (-2, 24.8)),         # 顶部走道
    ((-7, 0), (-5.4, 24)),          # 左侧交叉通道
    ((-2, 0), (0, 24.8))            # 右侧交叉通道
]

x_positions = sorted([visual_positions[a] for a in shelf_access_side])
for i in range(len(x_positions) - 1):
    left, right = x_positions[i], x_positions[i+1]
    if right - (left + 0.6) >= 0.5:
       x_start = round(round((left + 0.6) * 2) / 2, 2)
       x_end = round(round((right) * 2) / 2, 2)
       if x_start < (left+0.6):
           x_start += 0.5
       if x_end > right:
           x_end -= 0.5
       
       y_start, y_end = 2.5, 24
       walkable_areas.append(((x_start, y_start), (x_end, y_end)))


# ------------------- 输入拣选点 -------------------
user_picks = ['112.6', '113.33', '114.43', '114.16']

def parse_user_picks(user_picks):
    parsed = []
    for p in user_picks:
        aisle_str, loc_str = p.split(".")
        aisle = int(aisle_str)
        location = int(loc_str)
        pick_slot_height = round(1.3 / 3, 3)  # ~0.433m
        pick_location = round(2.9 + (location - 1) * pick_slot_height, 3)
        parsed.append((aisle, pick_location))
    return parsed

parsed_picks = parse_user_picks(user_picks)

df = pd.DataFrame(list(parsed_picks), columns=['通道', '拣选位置'])


# ------------------- 绘图函数 -------------------
def plot_pick_locations(ax, pick_locations, visual_positions, aisles):
    for aisle in aisles:
        pos = visual_positions[aisle]
        for location in pick_locations[aisle]:
            rect = Rectangle((pos, location), 0.6, round(1.3 / 3, 3), color='blue', alpha=0.3)
            ax.add_patch(rect)

def plot_selected_picks(ax, df, visual_positions):
    for _, row in df.iterrows():
        pos = visual_positions[row['通道']]
        rect = Rectangle((pos, row['拣选位置']), 0.6, round(1.3 / 3, 3), color='red')
        ax.add_patch(rect)

def plot_walkable_areas(ax, walkable_areas):
    for (x_start, y_start), (x_end, y_end) in walkable_areas:
        width = x_end - x_start
        height = y_end - y_start
        ax.add_patch(Rectangle((x_start, y_start), width, height, color='lightgrey'))


# ------------------- 图结构生成函数 -------------------
# 构建可行走图
def generate_walkable_graph(walkable_areas, resolution=0.5):
    walkable_points = set()
    for (x_start, y_start), (x_end, y_end) in walkable_areas:
        x = x_start
        while x <= x_end:
            y = y_start
            while y <= y_end:
                point = (round(x, 3), round(y, 3))
                walkable_points.add(point)
                y += resolution
            x += resolution
    G = nx.Graph()
    directions = [(resolution, 0), (-resolution, 0), (0, resolution), (0, -resolution)]
    for x, y in walkable_points:
        for dx, dy in directions:
            neighbor = (round(x + dx, 3), round(y + dy, 3))
            if neighbor in walkable_points:
                G.add_edge((x, y), neighbor, weight=resolution)
    return G, walkable_points

walkable_graph, walkable_points = generate_walkable_graph(walkable_areas)

# 寻找最近可行走点的辅助函数
def nearest_walkable_point(x, y, walkable_points, resolution=0.5):
    rounded_x = round(round(x / resolution) * resolution, 3)
    rounded_y = round(round(y / resolution) * resolution, 3)
    candidate = (rounded_x, rounded_y)
    if candidate in walkable_points:
        return candidate
    min_dist = float('inf')
    nearest = None
    for point in walkable_points:
        dist = (point[0] - x)**2 + (point[1] - y)**2
        if dist < min_dist:
            min_dist = dist
            nearest = point
    return nearest

def get_visual_coords(pick):
    aisle, location = pick
    if shelf_access_side[aisle] == 'left':
        x = visual_positions[aisle]
        y = location
    else:
        x = visual_positions[aisle] + 0.6
        y = location
    return x, y


# ------------------- 生成路径 -------------------

# TODO: 我想禁止完全穿行112–113通道。
# 例如，如果从底部进入113通道，就不能从顶部出去。


pick_nodes = []
for aisle, loc in parsed_picks:
    x, y = get_visual_coords((aisle, loc))
    node = nearest_walkable_point(x, y, walkable_points)
    pick_nodes.append(node)


depot_coords = (-2.0, -2.0)
depot_node = nearest_walkable_point(*depot_coords, walkable_points)
stops = [depot_node] + pick_nodes + [depot_node]

# 构建完整路径
full_path = []
for i in range(len(stops) - 1):
    segment = nx.shortest_path(walkable_graph, stops[i], stops[i+1], weight='weight')
    if full_path:
        full_path += segment[1:]
    else:
        full_path += segment

# 路径总长度
path_length = sum(
    walkable_graph[full_path[i]][full_path[i + 1]]['weight']
    for i in range(len(full_path) - 1)
)


# ------------------- 绘图展示 -------------------
plt.figure(figsize=(14, 10))
ax = plt.gca()

# 绘制现有布局和拣选点
plot_walkable_areas(ax, walkable_areas)
plot_pick_locations(ax, pick_locations, visual_positions, shelf_access_side)
plot_selected_picks(ax, df, visual_positions)


if full_path:
    path_x, path_y = zip(*full_path)
    ax.plot(path_x, path_y, color='red', linewidth=2, label='规划路径')

    # 绘制起点
    ax.plot(depot_node[0], depot_node[1], 'ks', markersize=8, label='起点')

    # 绘制拣选点
    for node in pick_nodes:
        ax.plot(node[0], node[1], 'o', color='purple', markersize=8)

for i, node in enumerate(pick_nodes):
    ax.text(node[0] + 0.3, node[1], f"P{i+1}", color='black', fontsize=9)

plt.xticks(
    [visual_positions[a] for a in visual_positions],
    [f"{a}" for a in visual_positions],
    rotation=45
)

ax.set_aspect("equal")
plt.show()

解决方案 #

要实现超窄通道的「单侧进出」约束，有三种直接可行的方案：

方案1：修改图结构，移除违规边

针对每个超窄通道，直接切断其与非允许侧交叉通道的连接：

1. 根据X/Y坐标范围，标记出超窄通道对应的所有节点；
2. 移除超窄通道节点与非允许侧交叉通道节点之间的所有边（比如仅允许底部进出的通道，就删除其与顶部走道的连接边）；
3. 路径规划时自然无法从非允许侧穿出。

示例代码片段：

# 以112通道为例，仅允许从底部进出
aisle_112_x_min = visual_positions[112] + 0.6  # 右侧访问的X起始
aisle_112_x_max = visual_positions[113]
top_y_threshold = 24  # 顶部走道的Y坐标

# 收集需要移除的违规边
edges_to_remove = []
for u, v in walkable_graph.edges():
    # 判断是否是112通道顶部与顶部走道的连接边
    u_in_aisle_top = (aisle_112_x_min <= u[0] <= aisle_112_x_max) and (u[1] >= top_y_threshold - 0.5)
    v_in_aisle_top = (aisle_112_x_min <= v[0] <= aisle_112_x_max) and (v[1] >= top_y_threshold - 0.5)
    u_in_top_walkway = (u[1] >= top_y_threshold)
    v_in_top_walkway = (v[1] >= top_y_threshold)
    
    if (u_in_aisle_top and u_in_top_walkway) or (v_in_aisle_top and v_in_top_walkway):
        edges_to_remove.append((u, v))

walkable_graph.remove_edges_from(edges_to_remove)

方案2：使用有向图（DiGraph）替代无向图

将原来的无向图改为有向图，为超窄通道节点设置单向边：

1. 超窄通道内的节点仅保留朝向入口方向的边（比如从拣选点指向底部走道）；
2. 只有入口处的节点保留进入通道的边；
3. 这样拣选员进入通道后只能原路返回，无法穿行到另一侧。

方案3：自定义路径权重惩罚

如果不想修改图结构，可以在路径搜索时对违规路径设置极高权重：

• 定义自定义权重函数，当路径试图从超窄通道的非允许侧穿出时，赋予这条边极大的权重（比如1e9）；
• 使用nx.shortest_path时传入该权重函数，最短路径会自动避开违规路线。

内容的提问来源于stack exchange，提问作者Pim Mulder