Road Network Optimization

Overview

This project was built as part of CSCE 5210 at the University of North Texas. The goal was to build a system that simulates traffic across a weighted road network and identifies the highest-value unconnected roads to add based on projected travel-time reduction.

The full implementation is available in the Google Colab notebook.

The core tools used are Python and NetworkX. The system uses A* pathfinding to compute shortest paths, samples random trips to build a traffic profile, scores potential new roads by their network-wide benefit, and iteratively recommends the best additions using a greedy approach.

Architecture

A* Pathfinding Core

The foundation of the system is A* pathfinding via NetworkX. These wrapper functions are used throughout the project to compute shortest paths and distances between locations:

def get_shortest_path(network, locations):
  return nx.astar_path(network, *locations)

def get_shortest_path_distance(network, locations):
  return nx.astar_path_length(network, *locations)

Traffic Simulation

Traffic is simulated by randomly sampling origin-destination pairs and tracking which edges get traversed. For each tick, a set number of random trips are generated, A* paths are computed, and edge traversal counts are accumulated into a traffic profile:

def get_traffic_data(network, ticks, trips):
  nodes = list(network.nodes())
  traffic_data = {}
  for i in range(0, ticks):
    for j in range(0, trips):
      x = random.choice(nodes)
      y = random.choice(nodes)
      while y is x:
        y = random.choice(nodes)

      path = get_shortest_path(network=network, locations=(x,y))
      edges_from_path = list(nx.utils.pairwise(path))

      for edge in edges_from_path:
        if edge not in traffic_data:
          traffic_data[edge] = 0
        traffic_data[edge] += 1

  return traffic_data

With 36,000 ticks and 100 trips per tick, this generates a robust usage profile of the network that captures which routes carry the most traffic.

Benefit Scoring

Each potential new road is scored by the travel-time reduction it would provide. The key idea is a shrinkage factor — a new direct road between two locations is assumed to be shorter than the existing shortest path by a configurable factor f. The benefit for a road is the time saved multiplied by the number of trips:

def get_road_benefit_value(network, locations, shrinkage_factor, trips):
  return (
    get_shortest_path_distance(network=network, locations=locations) -
    get_distance(network=network, shrinkage_factor=shrinkage_factor, locations=locations)
  ) * trips

The total benefit also accounts for neighbor spillover — adding a road between nodes A and B can also reduce travel time for trips between A and B's neighbors. The get_benefit_value function sums both direct and neighbor benefits for a complete picture.

Iterative Recommendation Loop

The system uses a greedy approach to recommend roads one at a time. After scoring all unconnected location pairs, the highest-benefit road is selected, added to the network with its shrinkage-reduced weight, and removed from the candidate list. Then the remaining candidates are re-scored with the updated network:

for i in range(0, k):
  cost_matrix = get_unnoncected_locations_cost_matrix(
    network=network,
    traffic_data=traffic_data,
    shrinkage_factor=f,
    unconnected_locations=unconnected_locations,
  )
  sorted_road_recommendations = get_sorted_road_recommendations(cost_matrix)

  if len(sorted_road_recommendations):
    top_recommendations = sorted_road_recommendations[0]
    recommended_road = top_recommendations[0]
    recommendations.append(recommended_road)
    network.add_edge(
      recommended_road[0],
      recommended_road[1],
      weight=get_distance(
        network=network, shrinkage_factor=f, locations=recommended_road
      )
    )
    unconnected_locations.remove(recommended_road)

This re-scoring step is important because adding one road changes the shortest paths in the network, which can shift the relative value of remaining candidates.

Scaling Scenarios

The project explores multiple scenarios of increasing complexity:

• R2: A fixed 5-node graph with known edge weights, recommending 2 roads with shrinkage factor 0.6
• R3: A random 60-node graph with connectivity probability 0.05, recommending 3 roads
• R4: Same network as R3 but with a higher shrinkage factor of 0.8, showing how less aggressive road shortening changes recommendations
• R5: A random 60-node graph with higher connectivity (p=0.1), compared against R3 to study how denser networks affect which roads provide the most benefit