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

被引:0
|
作者
La Rocca, Charly Robinson [1 ]
Cordeau, Jean-Francois [2 ]
Frejinger, Emma [1 ]
机构
[1] Univ Montreal, Dept Comp Sci & Operat Res, 2900 Boul Edouard Montpetit, Montreal, PQ H3T 1J4, Canada
[2] HEC Montreal, Dept Logist & Operat Management, 3000 Cote St Catherine Rd, Montreal, PQ H3T 2A7, Canada
关键词
Heuristics; Supervised learning; Multicommdity capacitated fixed charge; network design; Local search; Transportation; Machine learning; CYCLE-BASED NEIGHBORHOODS; MODELS;
D O I
10.1016/j.tre.2024.103805
中图分类号
F [经济];
学科分类号
02 ;
摘要
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.
引用
收藏
页数:16
相关论文
共 50 条
  • [1] A parallel local search framework for the Fixed-Charge Multicommodity Network Flow problem
    Munguia, Lluis-Miquel
    Ahmed, Shabbir
    Bader, David A.
    Nemhauser, George L.
    Goel, Vikas
    Shao, Yufen
    COMPUTERS & OPERATIONS RESEARCH, 2017, 77 : 44 - 57
  • [2] On the Use of Guided Design Search for Discovering Significant Decision Variables in the Fixed-Charge Capacitated Multicommodity Network Design Problem
    Lewis, Mark W.
    NETWORKS, 2009, 53 (01) : 6 - 18
  • [3] A local branching heuristic for the capacitated fixed-charge network design problem
    Rodriguez-Martin, Inmaculada
    Salazar-Gonzalez, Juan Jose
    COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (03) : 575 - 581
  • [4] A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem
    Yaghini, Masoud
    Karimi, Mohammad
    Rahbar, Mohadeseh
    Sharifitabar, Mohammad Hassan
    INFORMS JOURNAL ON COMPUTING, 2015, 27 (01) : 48 - 58
  • [5] Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem
    Thiongane, Babacar
    Cordeau, Jean-Francois
    Gendron, Bernard
    COMPUTERS & OPERATIONS RESEARCH, 2015, 53 : 1 - 8
  • [6] MIP Neighborhood Search Heuristics for a Capacitated Fixed-Charge Network Design Problem
    Katayama, Naoto
    ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH, 2020, 37 (03)
  • [7] Cycle-based neighbourhoods for fixed-charge capacitated multicommodity network design
    Ghamlouche, I
    Crainic, TG
    Gendreau, M
    OPERATIONS RESEARCH, 2003, 51 (04) : 655 - 667
  • [8] An Efficient Matheuristic for the Multicommodity Fixed-Charge Network Design Problem
    Gendron, Bernard
    Hanafi, Said
    Todosijevic, Raca
    IFAC PAPERSONLINE, 2016, 49 (12): : 117 - 120
  • [9] Node-based Lagrangian relaxations for multicommodity capacitated fixed-charge network design
    Kazemzadeh, Mohammad Rahim Akhavan
    Bektas, Tolga
    Crainic, Teodor Gabriel
    Frangioni, Antonio
    Gendron, Bernard
    Gorgone, Enrico
    DISCRETE APPLIED MATHEMATICS, 2022, 308 : 255 - 275
  • [10] Combining Exact and Heuristic Approaches for the Capacitated Fixed-Charge Network Flow Problem
    Hewitt, Mike
    Nemhauser, George L.
    Savelsbergh, Martin W. P.
    INFORMS JOURNAL ON COMPUTING, 2010, 22 (02) : 314 - 325