Traffic Flow Example

Download Notebook

Traffic Flow optimization chooses one route per car through a road network so that total congestion across all road segments is minimised. It models real-world traffic routing and network load balancing.

import getpass
import os

from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.traffic_flow import (
    TrafficFlowCollection,
    TrafficFlowData,
    TrafficFlowFormulation,
    TrafficFlowInstance,
)

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define 3 cars each with 2 route options over a 5-segment road network.

car_routes = [
    [[0, 1, 2], [0, 3, 4]],  # Car 0: route via 0-1-2 or 0-3-4
    [[1, 3], [2, 4]],  # Car 1: route via 1-3 or 2-4
    [[0, 2, 4], [1, 3]],  # Car 2: route via 0-2-4 or 1-3
]
data = TrafficFlowData.from_values(car_routes=car_routes)
print(data.to_string())

Traffic Flow Data:
  Cars: 3
  Total routes: 6
  Unique segments: 5

Plot Data

Visualize car route options on the road network.

data.plot()

<Axes: title={'center': 'Traffic Flow - Route Structure'}, xlabel='Segment'>

Create Formulation

Assign routes to cars minimizing total road segment congestion.

formulation = TrafficFlowFormulation()
print(formulation.to_string(data))

Traffic Flow Formulation:
  Cars: 3
  Unique segments: 5

Decision Variables:
  y[c,r] in {0,1} for each car c and route r
  y[c,r] = 1 if car c takes route r
  Total: 6 binary variables

Objective:
  minimize sum_s load_s^2
  where load_s = sum_{{(c,r) using s}} y[c,r]

Constraints:
  1. One route per car (3 constraints):
     sum_r y[c,r] == 1  for all c = 0, ..., 2

Create Instance

Combine data and formulation into a solvable instance.

instance = TrafficFlowInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Traffic Flow Data:
  Cars: 3
  Total routes: 6
  Unique segments: 5
Formulation:Traffic Flow Formulation:
  Cars: 3
  Unique segments: 5

Decision Variables:
  y[c,r] in {0,1} for each car c and route r
  y[c,r] = 1 if car c takes route r
  Total: 6 binary variables

Objective:
  minimize sum_s load_s^2
  where load_s = sum_{{(c,r) using s}} y[c,r]

Constraints:
  1. One route per car (3 constraints):
     sum_r y[c,r] == 1  for all c = 0, ..., 2

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Traffic Flow Solution:
  Total congestion: 11
  Valid: True
  Selected routes: [0 1 1]

Plot Solution

Visualize the optimal solution.

uc_solution.plot(data)

<Axes: title={'center': 'TF Solution - total congestion 11'}, xlabel='Segment'>

Collections

Generate a benchmark collection of random instances for batch processing.

collection = TrafficFlowCollection.from_random(min_cars=2, max_cars=4, n_segments=5, seed=42)
model = collection.instances[0].formulate()
print(model)

Model: traffic_flow<traffic_flow>
Minimize
  2 * y_0_0 * y_0_1 + 2 * y_0_0 + y_0_1 + y_1_0 + 2 * y_1_1
Subject To
  one_route_c0: y_0_0 + y_0_1 == 1
  one_route_c1: y_1_0 + y_1_1 == 1
Binary
  y_0_0 y_0_1 y_1_0 y_1_1