A hybrid deep-learning-metaheuristic framework for bi-level network design problems

Bahman Madadi*, Gonçalo Homem de Almeida Correia

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

26 Downloads (Pure)

Abstract

This study proposes a hybrid deep-learning-metaheuristic framework with a bi-level architecture for road network design problems (NDPs). We train a graph neural network (GNN) to approximate the solution of the user equilibrium (UE) traffic assignment problem and use inferences made by the trained model to calculate fitness function evaluations of a genetic algorithm (GA) to approximate solutions for NDPs. Using three test networks, two NDP variants and an exact solver as benchmark, we show that on average, our proposed framework can provide solutions within 1.5 % gap of the best results in less than 0.5 % of the time used by the exact solution procedure. Our framework can be utilized within an expert system for infrastructure planning to determine the best infrastructure planning and management decisions under different scenarios. Given the flexibility of the framework, it can easily be adapted to many other decision problems that can be modeled as bi-level problems on graphs. Moreover, we foreseen interesting future research directions, thus we also put forward a brief research agenda for this topic. The key observation from our research that can shape future research is that the fitness function evaluation time using the inferences made by the GNN model was in the order of milliseconds, which points to an opportunity and a need for novel heuristics that 1) can cope well with noisy fitness function values provided by deep learning models, and 2) can use the significantly enlarged efficiency of the evaluation step to explore the search space effectively (rather than efficiently). This opens a new avenue for a modern class of metaheuristics that are crafted for use with AI-powered predictors.

Original languageEnglish
Article number122814
Number of pages13
JournalExpert Systems with Applications
Volume243
DOIs
Publication statusPublished - 2023

Keywords

  • Bi-level programming
  • Combinatorial optimization
  • Decision support systems
  • Deep learning
  • Graph neural networks
  • Road network design problem
  • User equilibrium traffic assignment problem

Fingerprint

Dive into the research topics of 'A hybrid deep-learning-metaheuristic framework for bi-level network design problems'. Together they form a unique fingerprint.

Cite this