integrate-road-network（整合道路网络）

Road Network Integration

Integrate real-world street networks from OpenStreetMap into your VRP toolkit using map data.

Integration Workflow

Step 1: Install Dependencies

Install OSMnx and geo-processing libraries.

Using conda (recommended):

conda install -c conda-forge osmnx

Using pip:

pip install osmnx geopandas shapely fiona pyproj

Verify installation:

import osmnx as ox
print(f"OSMnx version: {ox.__version__}")

Troubleshooting: See troubleshooting.md for installation issues.

Step 2: Load Street Network

Choose loading method based on your needs:

Option A: Load by Place Name

For well-known locations (recommended for campuses, cities).

import osmnx as ox

# Load area by name
place_name = "Purdue University, West Lafayette, IN, USA"
G = ox.graph_from_place(
    place_name,
    network_type='drive',  # 'drive', 'walk', 'bike', or 'all'
    simplify=True
)

# Save for reuse (much faster than re-downloading)
ox.save_graphml(G, "data/campus_network.graphml")

print(f"Loaded {len(G.nodes)} nodes and {len(G.edges)} edges")

Option B: Load by Bounding Box

For specific coordinate ranges.

# Define bounding box (north, south, east, west)
north, south, east, west = 40.4300, 40.4200, -86.9100, -86.9250

G = ox.graph_from_bbox(north, south, east, west, network_type='drive')

Data structure details: See maintain-data-structures skill → data_layer.md → OSMnx Graph

More examples: See osmnx_examples.md → Examples 1-2

Step 3: Define VRP Locations

Map your problem locations (depot, customers, pickups, deliveries) to network nodes.

3a. Extract from Points of Interest (POIs)

# Find buildings/amenities as potential locations
tags = {
    'building': ['university', 'dormitory'],
    'amenity': ['cafe', 'restaurant', 'library']
}

pois = ox.geometries_from_place(place_name, tags=tags)

# Extract coordinates
locations = []
for idx, poi in pois.iterrows():
    if poi.geometry.geom_type == 'Point':
        lat, lon = poi.geometry.y, poi.geometry.x
    else:  # Polygon
        lat, lon = poi.geometry.centroid.y, poi.geometry.centroid.x

    locations.append((lat, lon))

print(f"Found {len(locations)} potential customer locations")

3b. Use Manually Defined Locations

# Define locations manually (lat, lon)
depot_loc = (40.4237, -86.9212)

pickup_locs = [
    (40.4280, -86.9145),
    (40.4200, -86.9180)
]

delivery_locs = [
    (40.4250, -86.9100),
    (40.4210, -86.9220)
]

More examples: See osmnx_examples.md → Example 3

Step 4: Map to Network Nodes

Find nearest nodes in the street network for each location.

# Find nearest network nodes
depot_node = ox.distance.nearest_nodes(
    G,
    depot_loc[1],  # X = longitude
    depot_loc[0]   # Y = latitude
)

pickup_nodes = [
    ox.distance.nearest_nodes(G, lon, lat)
    for lat, lon in pickup_locs
]

delivery_nodes = [
    ox.distance.nearest_nodes(G, lon, lat)
    for lat, lon in delivery_locs
]

# All nodes for VRP instance
all_osm_nodes = [depot_node] + pickup_nodes + delivery_nodes

print(f"Mapped to {len(all_osm_nodes)} network nodes")

IMPORTANT: nearest_nodes takes (X, Y) which is (longitude, latitude), NOT (lat, lon)!

Troubleshooting: See troubleshooting.md → Coordinate Issues

More examples: See osmnx_examples.md → Example 4

Step 5: Compute Distance Matrix

Calculate network-based distances between all nodes.

import networkx as nx
import numpy as np

n = len(all_osm_nodes)
distance_matrix = np.zeros((n, n))

for i, origin in enumerate(all_osm_nodes):
    # Compute shortest paths from origin to all destinations
    lengths = nx.single_source_dijkstra_path_length(
        G, origin, weight='length'  # Use 'length' for distance in meters
    )

    for j, dest in enumerate(all_osm_nodes):
        if i != j and dest in lengths:
            distance_matrix[i, j] = lengths[dest]

print("Distance matrix computed (in meters)")
print(distance_matrix)

Optional: Convert to time matrix

average_speed_kmh = 30  # km/h
average_speed_ms = average_speed_kmh * 1000 / 3600  # m/s

time_matrix_seconds = distance_matrix / average_speed_ms
time_matrix_minutes = time_matrix_seconds / 60

Data structure details: See maintain-data-structures skill → runtime_formats.md → Distance Matrix

Troubleshooting: See troubleshooting.md → Routing Issues

More examples: See osmnx_examples.md → Examples 5-6

Step 6: Create Node Objects

Create VRP toolkit Node objects from OSMnx nodes.

from vrp_toolkit.problems import Node

nodes = []

# Depot
depot_data = G.nodes[depot_node]
nodes.append(Node(
    node_id=0,
    x=depot_data['x'],  # longitude
    y=depot_data['y'],  # latitude
    node_type='depot'
))

# Pickups and deliveries (paired)
for idx, (p_node, d_node) in enumerate(zip(pickup_nodes, delivery_nodes), 1):
    pickup_id = idx * 2 - 1
    delivery_id = idx * 2

    # Pickup node
    p_data = G.nodes[p_node]
    nodes.append(Node(
        node_id=pickup_id,
        x=p_data['x'],
        y=p_data['y'],
        demand=10.0,  # Adjust as needed
        time_window=(8.0, 17.0),  # 8am - 5pm
        service_time=0.25,  # 15 minutes
        node_type='pickup',
        pair_node_id=delivery_id
    ))

    # Delivery node
    d_data = G.nodes[d_node]
    nodes.append(Node(
        node_id=delivery_id,
        x=d_data['x'],
        y=d_data['y'],
        demand=-10.0,  # Negative for delivery
        time_window=(8.0, 17.0),
        service_time=0.25,
        node_type='delivery',
        pair_node_id=pickup_id
    ))

print(f"Created {len(nodes)} Node objects")

Data structure details: See maintain-data-structures skill → problem_layer.md → Node

Step 7: Create PDPTW Instance

Combine everything into a problem instance.

from vrp_toolkit.problems import PDPTWInstance

instance = PDPTWInstance(
    nodes=nodes,
    battery_capacity=100.0,
    max_route_time=480.0,  # 8 hours in minutes
    vehicle_capacity=50.0
)

# Attach distance matrix
instance.distance_matrix = distance_matrix

# Optionally attach time matrix
instance.time_matrix = time_matrix_minutes

# Save instance for later use
import pickle
with open('data/campus_pdptw_instance.pkl', 'wb') as f:
    pickle.dump(instance, f)

print("PDPTW instance created successfully!")

Complete example: See osmnx_examples.md → Example 7

Data structure details: See maintain-data-structures skill → problem_layer.md → PDPTWInstance

Step 8: Validate and Solve

Test the instance and solve.

from vrp_toolkit.algorithms.alns import ALNSSolver, ALNSConfig

# Validate instance
print(f"Number of nodes: {len(instance.nodes)}")
print(f"Number of pickup-delivery pairs: {len(instance.pickup_delivery_pairs)}")
print(f"Distance matrix shape: {instance.distance_matrix.shape}")

# Solve
config = ALNSConfig(max_iterations=1000)
solver = ALNSSolver(config)
solution = solver.solve(instance)

# Check solution
if solution.is_feasible():
    print(f"Feasible solution found!")
    print(f"Objective value: {solution.objective_value()}")
    solution.plot()
else:
    print("Solution is infeasible")

Advanced Features

Visualize Routes on Street Network

Plot solution routes on the actual map.

import matplotlib.pyplot as plt

# Plot base network
fig, ax = ox.plot_graph(
    G,
    bgcolor='white',
    node_size=0,
    edge_color='gray',
    edge_linewidth=0.5,
    show=False,
    close=False
)

# Plot solution routes (assuming routes contain OSM node IDs)
colors = ['blue', 'red', 'green', 'orange']

for route_idx, route in enumerate(solution.routes):
    # Map VRP node IDs back to OSM node IDs
    osm_route = [all_osm_nodes[node_id] for node_id in route]

    # Get coordinates
    xs = [G.nodes[node]['x'] for node in osm_route]
    ys = [G.nodes[node]['y'] for node in osm_route]

    # Plot
    ax.plot(xs, ys,
            color=colors[route_idx % len(colors)],
            linewidth=3,
            alpha=0.7,
            label=f'Route {route_idx + 1}')

ax.legend()
plt.title("VRP Solution on Real Street Network")
plt.show()

More examples: See osmnx_examples.md → Example 8

Cache for Performance

Save processed graphs to avoid re-downloading.

import os

cache_file = "data/campus_network.graphml"

if os.path.exists(cache_file):
    # Load from cache (instant!)
    G = ox.load_graphml(cache_file)
    print("Loaded from cache")
else:
    # Download and save
    G = ox.graph_from_place(place_name)
    ox.save_graphml(G, cache_file)
    print("Downloaded and cached")

More examples: See osmnx_examples.md → Example 9

Handle Graph Connectivity

Ensure all nodes can reach each other.

import networkx as nx

# Check connectivity
if not nx.is_weakly_connected(G):
    print("Graph has multiple disconnected components")

    # Keep only largest connected component
    largest_component = max(
        nx.weakly_connected_components(G),
        key=len
    )
    G = G.subgraph(largest_component).copy()
    print(f"Using largest component with {len(G.nodes)} nodes")

Troubleshooting: See troubleshooting.md → Routing Issues

Creating Tutorials with OSMnx

When creating a tutorial that uses OSMnx:

1. Choose recognizable location

- Use well-known places (e.g., university campus, downtown area) - Easier for readers to relate to

1. Cache the graph

- Include downloaded graph in tutorial repository - Avoids download delays for users

1. Use small areas

- Keep examples fast (<30 seconds to run) - Small bounding boxes or specific places

1. Provide visualization

- Plot the network with routes overlaid - Makes results more tangible

1. Handle edge cases

- Show what to do if node unreachable - Demonstrate connectivity checks

Common Patterns

Pattern 1: Campus Routing

# 1. Load campus
G = ox.graph_from_place("University Name, City, State, USA")

# 2. Find buildings as customer locations
pois = ox.geometries_from_place(place_name, tags={'building': True})

# 3. Create distance matrix
# 4. Build PDPTW instance
# 5. Solve and visualize on map

Pattern 2: City-Wide Delivery

# 1. Load city with bounding box
G = ox.graph_from_bbox(north, south, east, west)

# 2. Use address geocoding for customer locations
# 3. Compute network distances
# 4. Create VRP instance
# 5. Solve at scale

Pattern 3: Benchmark Comparison

# Create two instances:
# - Euclidean distance (traditional)
# - Network distance (OSMnx)
# Compare solution quality and computation time

Integration with Other Skills

Works with:

• maintain-data-structures: Reference OSMnx data structures (Graph, GeoDataFrame, distance matrices)
• migrate-module: When migrating real_map.py from old codebase
• tutorial-creator: When creating real-world VRP tutorials (when that skill exists)

Example:

You: "Create a real-world PDPTW instance for Purdue campus"
→ osmnx-integration skill triggers
→ References maintain-data-structures for OSMnx Graph structure
→ Creates instance following workflow

Reference Materials

• Examples: osmnx_examples.md - 10 complete examples
• Troubleshooting: troubleshooting.md - Common issues and solutions
• Data Structures: See maintain-data-structures skill for OSMnx structure details

Key Reminders

1. ⚠️ Coordinate order: nearest_nodes(G, lon, lat) not (lat, lon)!
2. 💾 Cache graphs: Save downloaded graphs to avoid re-downloading
3. 🔗 Check connectivity: Ensure all nodes can reach each other
4. 📏 Distance units: OSMnx uses meters, convert as needed
5. 🗺️ Simplify graphs: Use simplify=True for faster processing unless you need exact geometry