JOPT2025

HEC Montreal, 12 — 14 May 2025

JOPT2025

HEC Montreal, 12 — 14 May 2025

Schedule Authors My Schedule

Network Design I

May 12, 2025 10:30 AM – 12:10 PM

Location: Luc-Poirier (Green)

Chaired by Bita Payami

4 Presentations

  • 10:30 AM - 10:55 AM

    Profit Maximizing Network Design Problem with Location Decisions Considering Incompatible Commodities and Demand Selection

    • Ehsan Mirzaei, presenter, University of Montreal, Tarbiat Modares University
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Walter Rei, Université du Québec à Montréal
    • Ehsan Nikbakhsh, Tarbiat Modares University

    This study focuses on a profit maximization variant of the multi-commodity network design problem with location decisions and incompatible commodities. A novelty of the problem is the restriction of commodity flows for safety and security reasons, as commodities have a predetermined list of other commodities that cannot be shipped together. Therefore, decisions regarding serving commodities should be made simultaneously with design and flow decisions, as demand selection is affected by them. The problem, therefore, is to design a network by selecting both nodes and arcs that maximizes the total profit, including the revenue obtained from selecting demands, design cost (for the selection of nodes and arcs), and the flow costs to transport the commodities. In this research, we assume that commodities are transferred through transshipment locations, and direct shipment between the origin and destination of a commodity is not allowed. The shipment between transshipment nodes is allowed to use several arcs. An accelerated branch & Benders cut algorithm is developed to solve the proposed model. Different decomposition strategies and acceleration techniques have been outlined. Finally, an extensive set of computational experiments is conducted on a set of instances from the literature.

  • 10:55 AM - 11:20 AM

    Machine Learning-Guided Optimization for Stochastic Multicommodity Network Design

    • Mahya Hemmati, presenter, School of Management, Université du Québec à Montréal and CIRRELT, Montreal, Quebec, Canada
    • Teodor Gabriel Crainic, CIRRELT and Département de management et technologie, École des sciences de la gestion, University of Quebec in Montréal
    • Walter Rei, Université du Québec à Montréal
    • Fatemeh Sarayloo, Department of Information and Decision Science, University of Illinois at Chicago, Chicago, USA

    This paper introduces an innovative machine learning (ML)-guided matheuristic approach for solving the stochastic multicommodity capacitated network design (SMCND) problem, which is common in logistics, telecommunications, and transportation. Despite the development of advanced methods, achieving high-quality solutions for large-scale instances remains a significant challenge. To address this, Artificial Recourse Problems (ARPs) are utilized to generate a diverse set of solutions that capture demand variations across multiple scenarios. These solutions are then used to train ML models that predict promising arcs. Feature engineering techniques are applied to identify key attributes of high-quality solutions, guiding the optimization process toward better network configurations. The proposed framework integrates ML predictions with optimization, leveraging learned patterns to enhance the efficiency of the search process.

  • 11:20 AM - 11:45 AM

    Benders Decomposition for Two-layer Network Design with Capacity Decisions

    • Ali Rouhani, presenter, Université de Montréal
    • Teodor Gabriel Crainic, Université du Québec à Montréal
    • Walter Rei, ESG UQAM
    • Walid Klibi, The Centre of Excellence in Supply Chain (CESIT), Kedge Business School, Bordeaux, France

    The Two-Layer Network Design Problem (2LND) represents a specialized class of network optimization problems that involve two interwoven design decisions, each corresponding to a distinct network layer. This study addresses a 2LND variant where the layers are interconnected through design, flow, and capacity constraints. The primary objective is to construct a cost-effective, capacitated two-layer network that meets multicommodity demand while satisfying standard network design constraints and inter-layer coupling requirements.

    We provide a formal definition of the 2LND, including capacity decisions, and present its mathematical formulation. The problem poses significant modeling and algorithmic challenges due to its intricate connectivity relationships. To tackle these challenges, we introduce two reformulations that reduce the number of decision variables and constraints. This is followed by a reduced-cost-based heuristic designed to identify design arcs likely to appear in the optimal two-layer network, thereby enabling a two-layer network reduction. Moreover, we propose two decomposition strategies to solve the model using Benders decomposition. The algorithm is further enhanced through several acceleration techniques, including cutset-based valid inequalities, strengthened classical and generalized cuts, and the generation of multiple feasibility cuts. Extensive computational experiments demonstrate the efficiency of the model reduction procedures and the proposed algorithmic refinements.

  • 11:45 AM - 12:10 PM

    Service Network Design for Intermodal Barge Transport under Water-Level Variability: A Decision-Based Scenario Clustering Analysis Approach

    • Bita Payami, presenter, UQAM
    • Ioana C. Bilegan,
    • Teodor Gabriel Crainic,
    • Walter Rei,

    In this study, we introduce the Water-Level-Constrained Scheduled Service Network Design with Resource and Revenue Management (WL-SSND-RRM) problem, which addresses the challenges of integrating water-level variability into tactical planning for barge transportation systems. To explicitly account for the effects of water level uncertainty in tactical planning for barge transportation, we propose two alternative stochastic models, each defined by a specific approach to handling the impact of randomly changing water level conditions. The first stochastic model relies on the application of penalties directly tied to the amount of demand that cannot be routed under the established tactical plan, reflecting the economic consequences of inadequate capacity due to adverse water levels. The second model, instead, allows demand itineraries to be adjusted based on observed water levels, enabling flows to dynamically adapt to fluctuating conditions and enhancing network flexibility.

    To solve the stochastic models, we apply a general decision-based scenario clustering analysis approach, which enables the computation of a series of alternative bounding techniques aimed at finding feasible solutions and computing the optimality gap. Through numerical experiments, these techniques are shown to significantly outperform high-performance commercial solvers in both computational efficiency and solution quality.
    Furthermore, this study introduces a set of comparative tests designed to evaluate the performance of the proposed models. Compared to the deterministic model, these tests highlight the importance of explicitly accounting for uncertainty in tactical planning. Additionally, the results compare the two stochastic models to assess the structural differences introduced in the tactical plan and their varying effectiveness in handling water level uncertainty. Finally, the study underscores the significant influence of water levels on key tactical decisions, particularly service selection and demand routing, as well as profitability and operational efficiency.

Back