The aim of this project is to explore how graph neural networks (GNNs) can aid in solving Network Design Problems (NDPs). The NDP is a combinatorial optimization problem that involves finding the optimal (topological) design of a network (e.g., road network, telecommunication network) to minimize some objective function (e.g., total travel cost, total latency). In this case, we will focus on the road network design problem, where the goal is to find the optimal link capacities to minimize the total travel time on the network. In other words, given a certain budget for capacity expansion, the objective is to allocate the budget to a selection of roads optimally to minimize (in this case) the total travel time.

NDPs are generally bi-level programming problems where the upper level represents the network design decisions (e.g., link capacities) and the lower level represents the user equilibrium traffic assignment problem. The user equilibrium traffic assignment problem is a non-linear optimization problem that assigns traffic flows to the network based on the link costs (e.g., travel time) and the user behavior (e.g., route choice). The NDP is challenging due to the non-linear interactions between the network design and the traffic assignment and different objective functions of the upper level and the lower level problems, which makes it difficult to solve using traditional optimization methods, particularly for large-scale networks.

One common solution is to break the problem into the upper level and the lower level and solve them iteratively. We can use metaheuristic algorithms like Genetic Algorithms (GAs) for this approach. However, this approach can be computationally expensive too and may not scale well to large networks since we need repeated traffic assignment simulations for each design iteration.

This is where GNNs come into play. GNNs can learn the underlying patterns and relationships in the network data and can be used to predict link flows based on the network structure and demand distribution. By training a GNN to predict link flows, we can use the predicted flows to find good solutions for the NDP without the need for repeated traffic assignment simulations. This can significantly reduce the computational cost and make the solution process more scalable. This is essentially using the GNN as a surrogate model for the traffic assignment model, which requires solving an optimization problem. The trained GNN can predict link flows for different network designs, and we can use these predicted flows to evaluate the network performance and optimize the link capacities using metaheuristics like GAs. But when we use GNNs for the NDP, we need to be careful about the accuracy of the predictions since the quality of the solutions depends on the accuracy of the predicted link flows.

During the lecture on Friday, we will cover the fundamentals of NDPs and GNNs and how they can be combined to solve the NDP efficiently, and this notebook should give you a head start by demonstrating a simple example. But for in-dept information, you can consult the following article (for theory), github repository (for code), and figshare repository (for datasets):

• Article: A hybrid deep-learning-metaheuristic framework for bi-level network design problems
• Code: GitHub Repository: HDLMF_GIN-GA
• Dataset: Dataset repository

The python environemnt simply needs pytorch and pytorch geometric (plus numpy, pickle and matplotlib, which come preinstalled with scipy environments). But the requirements.txt file is added in case you want to automate creation of the python environment.

This repository will be updated in time based on student contributions and additional projects and exercises. Feel free to contribute by opening a pull request.