Combining supervised learning and local search for the multicommodity capacitated fixed-charge network design problem

• Published in: Transportation research. Part E, Logistics and transportation review Logistics and transportation review, 2024-12, Vol.192, p.103805, Article 103805
• Main Authors: Robinson La Rocca, Charly, Cordeau, Jean-François, Frejinger, Emma
• Format: Article
• Language: English
• Subjects: Heuristics; Local search; Machine learning; Multicommdity capacitated fixed charge network design; Supervised learning; Transportation
• ISSN: 1366-5545
• DOI: 10.1016/j.tre.2024.103805

The multicommodity capacitated fixed-charge network design problem has been extensively studied in the literature due to its wide range of applications. Despite the fact that many sophisticated solution methods exist today, finding high-quality solutions to large-scale instances remains challenging. In this paper, we explore how a data-driven approach can help improve upon the state of the art. By leveraging machine learning models, we attempt to reveal patterns hidden in the data that might be difficult to capture with traditional optimization methods. For scalability, we propose a prediction method where the machine learning model is called at the level of each arc of the graph. We take advantage of off-the-shelf models trained via supervised learning to predict near-optimal solutions. Our experimental results include an algorithm design analysis that compares various integration strategies of predictions within local search algorithms. We benchmark the ML-based approach with respect to the state-of-the-art heuristic for this problem. The findings indicate that our method can outperform the leading heuristic on sets of instances sampled from a uniform distribution. •Proposes a framework for the integration of supervised learning and CO.•Develops an algorithm design analysis for the integration of ML predictions in LS.•Demonstrates that ML-enhanced problem reductions accelerate the benchmark heuristic.