Contents of the Repository

This repository contains the optimization model of RPP executed by Danilo Buttu for the Bachelor's Thesis "Bilevel model for tool optimization" in Matematica per l'ingegneria (Politecnico di Torino)

Road Pricing Problem (RPP) - Documentation

The executed model is the MILP RPP formulation that is contained in the article "A Bilevel Model for Toll Optimization on a Multicommodity Transportation Network" (November 2001) by Luce Brotcorne, Martine Labbé, Patrice Marcotte and Gilles Savard.

Table of Contents

• Contents of the Repository
• Road Pricing Problem (RPP) - Documentation
  • Table of Contents
  • Project Overview
  • Directory Structure
  • Core Components
    • 1. Main Execution (main.py)
    • 2. Graph Generation (graph_generator.py)
    • 3. Optimization Model (optimizer.py)
    • 4. Solution Reporting (reporter.py)
    • 5. Visualization (visualizer.py)
  • Usage Example
  • Output Examples

---

Project Overview

The Road Pricing Problem (RPP) is a bilevel optimization problem where a "leader" (e.g. a government) sets tolls on road network edges to maximize revenue, while "followers" (users) choose paths to minimize travel costs. This project:

• Generates random network instances with toll/free edges.
• Solves the RPP using Gurobi for Mixed-Integer Linear Programming (MILP).
• Provides summary statistics and visualizations of optimal solutions.

---

Directory Structure

Road_Pricing_Problem/
├── data/
│   ├── network_edges.csv         # List of connections of the generated graph
│   └── random_commodities.csv    # Goods to be transported (commodities)
├── instances/
│   └── graph_generator.py        # Generator of network and commodities 
└── solver/
    ├── model/
    │   └── optimizer.py          # Optimization logic with Gurobi
    └── utils/
        ├── reporter.py           # Solution report
        └── visualizer.py         # Graphic solution report

---

Core Components

1. Main Execution (main.py)

Initializes the network, solves the RPP, and displays results.

Key Parameters:

num_nodes = 100      # Number of nodes in the network
num_comm = 90        # Number of commodities to transport
max_cost = 3         # Base cost for toll/free edges
fuel_cost = 1        # Fuel cost multiplier for sensitivity analysis

g = NetworkGraph(num_nodes, max_cost, num_comm)
sol = Solver(path_edges, path_commodities, show_log=False)
sol.summary_solution()   # Print optimization summary
sol.graph_solution()     # Plot solution paths

2. Graph Generation (graph_generator.py)

Generates a directed graph with toll/free edges and random commodities.

Class: NetworkGraph

• _init_: initializes the graph and commodities.

• _generate_commodities: creates random origin-destination pairs with demands.

• _generate_edges: adds toll/free edges between nodes.

Example:
# Generate a network with 100 nodes and save to CSV
g = NetworkGraph(100, 3, 90)
g.dump_file(<network_edges.csv path> , <random_commodities.csv path>)

The class NetworkGraph has two public methods that can be used:

• dump_file: writes the graph information into the csv files contained in the Data folder using the Pandas library;
• plot: print the graph on the screen using the matplotlib library, representing the tolled arcs in blue and the free arcs in black.

3. Optimization Model (optimizer.py)

Solves the RPP using Gurobi. Key components include:

Class: Solver

• Variables: toll values (T_a), flow variables (x, y), dual variables (lamb);

• Objective: maximize toll revenue (with a backwards mechanism, the customer's spending can be traced automatically);

• Constraints: flow conservation, dual feasibility, and big-M constraints.

4. Solution Reporting (reporter.py)

Formats and prints optimization results by terminal following a compact layout.

Class: SolutionReporter

• summary: displays network statistics, objective values, and runtime.

5. Solution Visualization (visualizer.py)

Uses NetworkX and Matplotlib to visualize a graph solution where you can see how the various commodities were transported in the network.

Class: SolutionVisualizer

Usage Example

• Generate Network:

# Generate a network with 100 nodes and save to CSV
g = NetworkGraph(100, 3, 90)
g.dump_file(<network_edges.csv path> , <random_commodities.csv path>)

• Solve RPP:

sol = Solver(<network_edges.csv path>, <random_commodities.csv path>, show_log=True)
sol.summary_solution()

• Visualize Solution:

sol.graph_solution()

Output Examples

• Summary Output

----------------------------------------------------------------------------------------------------
Network with 15 nodes and 41 edges (22 toll, 19 free)
----------------------------------------------------------------------------------------------------
Leader's objective function value: 481.47
----------------------------------------------------------------------------------------------------
Total cost associated to the user to transport 10 commodities is: 934.93
----------------------------------------------------------------------------------------------------
Optimization time: 0.02 seconds
----------------------------------------------------------------------------------------------------

• Visulization

sol.graph_solution()

The graphical representation of the solution follows these rules:

• As in the network representation, blue edges represent toll roads, while black edges indicate free roads.
• The path followed by each commodity is tracked using oriented edges, each labeled with the commodity that used that specific edge (e.g., K0, K1, etc.).
• Additionally, for blue edges, a second label indicates the toll imposed on that specific road.