含分叉/汇合节点的街道网络施工区域警告标志布设技术问询

Alright, let's break down how to tackle this street network construction warning sign deployment problem step by step. I’ve worked on similar graph-based routing projects before, so here’s a practical, implementable approach:

First, we need to translate the real-world street system into a data structure computers can work with:

• Represent the network as an undirected graph where:
  • Nodes = Fork/Convergence points (intersections, merges, splits)
  • Edges = Individual street segments (each edge can have attributes like length, directionality if needed)
• Tag construction zones as a set of edges (since a single zone can cover multiple street segments) — add a is_construction boolean attribute to these edges, plus a construction_id to group segments belonging to the same zone.

We need to identify the "entry points" to the construction zone — the first street segments a driver would encounter when approaching the zone from any valid path:

• For each construction zone (group of edges):
  1. Run a reverse traversal from all edges in the zone: start at every node connected to a construction edge, and move outward away from the zone.
  2. The start positions are the nodes where the traversal first hits non-construction edges. These are the "gateway" nodes leading into the construction zone.
  3. If a construction edge is directly connected to the network’s boundary (like a dead end or highway on-ramp), that edge’s boundary node is also a start position.

The goal is to place at least 5 warning signs on every path leading to the construction zone. Here’s how to prioritize sign placement:

• For each gateway start position identified above:
  1. Find all simple paths from network entry points (major roads, highway connections) to the gateway node.
  2. On each path, place signs at these critical points (prioritize nodes that serve multiple paths to maximize coverage):
     • Node 1: First major intersection leading towards the construction zone (at least 1km away, adjust based on speed limits)
     • Node 2: A split/merge point where drivers might take an alternate route (warn them to stay on the construction-bound path)
     • Node 3: A mid-point node halfway between the first sign and the gateway
     • Node 4: The last major intersection before the gateway (500m from construction)
     • Node 5: The gateway node itself (immediately before the construction zone starts)
  3. If a path is shorter than needed to fit 5 signs, overlap signs at high-traffic nodes or add extra signs on longer street segments (not just nodes) — just ensure every approaching driver sees at least 5 warnings.

Using the networkx library for graph operations (it’s perfect for this kind of spatial routing):

import networkx as nx

# Step 1: Build the street graph
street_graph = nx.Graph()
# Add nodes with coordinate attributes (example data)
street_graph.add_nodes_from([
    (1, {"x": 100, "y": 200}),
    (2, {"x": 150, "y": 200}),
    (3, {"x": 200, "y": 200}),
    (10, {"x": 50, "y": 200})  # Major entry node
])
# Add edges (street segments) — mark construction edges
street_graph.add_edge(1, 2, is_construction=False, length=500)
street_graph.add_edge(2, 3, is_construction=True, length=300, construction_id="zone_1")
street_graph.add_edge(10, 1, is_construction=False, length=1000)

# Step 2: Identify construction gateway nodes
construction_zones = {}
for u, v, attrs in street_graph.edges(data=True):
    if attrs.get("is_construction"):
        zone_id = attrs["construction_id"]
        construction_zones[zone_id] = construction_zones.get(zone_id, set())
        construction_zones[zone_id].update([u, v])

gateway_nodes = set()
for zone_nodes in construction_zones.values():
    for node in zone_nodes:
        for neighbor in street_graph.neighbors(node):
            edge_data = street_graph.get_edge_data(node, neighbor)
            if not edge_data.get("is_construction"):
                gateway_nodes.add(neighbor)

# Step 3: Calculate sign positions for each reachable path
def place_signs_on_path(path):
    signs = []
    path_length = len(path)
    
    # Handle longer paths: pick evenly spaced nodes
    if path_length >= 5:
        step = path_length // 5
        for i in range(0, path_length, step):
            signs.append(path[i])
        # Ensure gateway is included
        if path[-1] not in signs:
            signs.append(path[-1])
    # Handle short paths: repeat high-priority nodes and add segment markers
    else:
        signs = path.copy()
        # Add a mid-point marker on the longest edge
        longest_edge = max(zip(path[:-1], path[1:]), key=lambda x: street_graph.get_edge_data(x[0], x[1])["length"])
        signs.append(f"segment_{longest_edge[0]}_{longest_edge[1]}_mid")
        # Fill to 5 signs
        while len(signs) < 5:
            signs.append(path[-2])
    return signs

# Example: Process paths from major entry node to gateways
entry_node = 10
for gateway in gateway_nodes:
    if nx.has_path(street_graph, entry_node, gateway):
        all_paths = nx.all_simple_paths(street_graph, entry_node, gateway)
        for idx, path in enumerate(all_paths):
            sign_locations = place_signs_on_path(path)
            print(f"Path {idx+1} ({path}): Sign locations = {sign_locations}")

• Coverage Check: Use graph traversal to verify every node leading to the construction zone has a clear path with at least 5 signs.
• Traffic Priority: Add a traffic_volume attribute to edges, then prioritize placing signs on high-traffic paths first to maximize visibility.
• Dynamic Updates: If the construction zone expands, re-run the reverse traversal to update gateway nodes and adjust sign positions in real time.

内容的提问来源于stack exchange，提问作者Mohammed Al-Huneidi