JOPT2025

HEC Montreal, 12 — 14 May 2025

JOPT2025

HEC Montreal, 12 — 14 May 2025

Schedule Authors My Schedule

Network Design III

May 14, 2025 10:15 AM – 12:00 PM

Location: Luc-Poirier (Green)

Chaired by Antoine Legrain

4 Presentations

  • 10:15 AM - 10:40 AM

    Consensus, upgrade and skeleton clustering in transport logistics

    • Samah Abdalrhaman, presenter, ESG-UQAM
    • Janosch Ortmann, UQAM
    • Walter Rei, Université du Québec à Montréal

    In stochastic programming, scenarios approximate distributions of unknown parameters, but in many applications the number of scenarios required to realistically model the uncertainty makes the optimisation problem numerically intractable. This motivates the scenario reduction problem: by finding a smaller subset of scenarios, reduce the numerical complexity while keeping the error at an acceptable level.

    Recently, problem-based scenario reduction methods based on opportunity cost dissimilarities have shown to be effective. In this setting, opportunity cost means the cost of wrongly predicting scenario 1 when actually scenario 2 happens and can be viewed as a measure of how different these two scenarios are with respect to the optimisation problem at hand.

    In this talk, I will discuss new distance matrices on the scenario set that are based on the idea of giving the decision maker some flexibility to change the first-stage decisions after the uncertainty has been revealed. We then apply clustering on the scenario set equipped with these distances.

    Preliminary result indicate promising bounds and reveal interesting new structures on the scenario set.

  • 10:40 AM - 11:05 AM

    Competitive Dynamic Single Facility Location with Cumulative Customer Demand

    • Warley Almeida Silva, presenter, Université de Montréal
    • Margarida Carvalho, Université de Montréal
    • Sanjay Dominik Jena, Université du Québec à Montréal

    Dynamic facility location problems seek to place one or more valuable resources over a discrete planning horizon to capture customer demand. Existing literature commonly assumes that (i) unmet customer demand at each period vanishes, thus not affecting location decisions of subsequent periods, and that (ii) the decision maker has a monopoly over the market, thus not being able to lose customers to other service providers. In many planning contexts, however, unmet customer demand may carry over to future periods, accumulating until being served by a service provider, and the decision maker may be in a competitive setting, fighting against a competitor for the same set of customers. This work studies a novel location problem, where the decision maker places a single facility over the planning horizon, anticipating that a competitor does the same, to capture cumulative customer demand. We propose an exact combinatorial optimization approach to obtain high-quality location policies for the decision maker. We assess our exact and heuristic solution methods using a benchmark based on the province of Quebec to derive insights into optimal location policies. Our preliminary results show that our exact algorithm performs better than using a state-of-the-art general-purpose solver, and indicate that ignoring competition leads to low-quality location policies.

  • 11:05 AM - 11:30 AM

    Decomposition Algorithms for Dynamic Capacitated Multiple Allocation Hub Location under Demand Uncertainty

    • Ziyuan Sun, presenter, Concordia University
    • Claudio Contardo, Concordia University
    • Jean-François Cordeau, HEC Montréal, GERAD, CIRRELT

    Hub location problems play a key role in designing efficient distribution systems across various disciplines, including logistics, transportation, and telecommunications. This work investigates dynamic (multi-period) capacitated multiple allocation hub location problems under demand uncertainty. We first present a two-stage stochastic mixed-integer programming formulation (MIP) for the problem. Given the NP-hard nature of the problem and the difficulty of solving this MIP with general-purpose solvers for large-scale instances, we address it by means of Benders decomposition. Due to the distinctive feature of the model, involving a large number of integer variables for the modular capacities of hubs in the Benders primal subproblem, linear programming duality theory cannot be applied directly to generate Benders cuts. We propose a heuristic Benders decomposition algorithm combined with combinatorial Benders cuts to ensure that a high-quality, feasible integer solution can be found. Additionally, acceleration techniques for solving the Benders master problem and subproblem, as well as for selecting strong unified Benders cuts, are introduced.

  • 11:30 AM - 11:55 AM

    The Hub Transportation Problem with chance constrained Due Dates

    • Antoine Legrain, presenter, Polytechnique Montréal
    • Quentin Cappart, Polytechnique Montréal
    • Öykü Naz Attila, Polytechnique Montreal
    • Max Bourgeat, Polytechnique Montréal

    Railway transportation offers an efficient and reliable service between stations. However, in remote areas, reduced accessibility due to large distances between stations and passengers' origin/destination points presents a significant challenge for railway companies.
    In low-density areas and in the countryside in particular, the supply of complementary transport to the train is often limited, or even nonexistent during off-peak hours, and does not always allow for an intermodal journey. It is essential to be able to offer public transport authorities a complementary offer to provide this feeder transport service to or from stations to make the journey as seamless as possible. A key aspect to operate this service successfully is to ensure that shuttles arrive at the train station before the time that passengers are due to take their train.
    Consequently, finding an optimal routing plan for shuttles is a highly time-sensitive problem. Besides, an inaccurate representation of travel times can easily lead to infeasible routing decisions with respect to meeting the due date that passengers are required to be at the train station.
    An algorithm based on column generation is proposed to address the problem. The pricing problem incorporates a chance constrained approach, deeming a route feasible if the shuttle can reach the train station before the passengers' due date. Travel time uncertainty is modeled using a discrete and finite uncertainty set to represent various travel time scenarios. The chance constrained approach ensures that the final decision remains feasible by meeting the passengers' due date in at least a specified proportion of the travel time scenarios

Back