MB2 - Prix François-Soumis Award

In this paper, we study the stochastic casualty response planning problem (CRP) in the context of providing treatments to multiple classes of patients with different types of injuries. In this general setting, both patients’ demands and hospitals’ treatment capacity are considered uncertain. To the best of our knowledge, this is the first time that this problem is solved. We propose a novel two-stage stochastic mixed-integer programming model which, in the first stage, determines the location of the Alternative Care Facilities (ACFs) and allocates different resources, such as rescue vehicles, medical equipment, and physicians, to them. In the second stage, this model helps decide how to allocate patients with multiple injuries to either ACFs or hospitals, considering their care itineraries and available resources. Moreover, it recommends potential patient transfers between ACFs and hospitals when required. Furthermore, we introduce an alternative two-stage stochastic model that is more compact than the first. This formulation significantly reduces solution times. We also provide an equivalency proof between the two formulations. As the solution method, we develop both the L-shaped algorithm, a pure cutting-plane method tailored to our stochastic mathematical model, and the branch-and-Benders-cut (B&BC) algorithm. To further enhance the efficiency of these algorithms, we develop a wide range of acceleration techniques, including Benders dual decomposition, Lagrangian dual decomposition, a multi-cut reformulation, Pareto-optimal cuts, and the inclusion of lower bounding functional valid inequalities. We carry out extensive computational experiments demonstrating that these algorithmic enhancements dramatically improve the performance of the B&BC algorithm, reducing the average optimality gap from 7898% in the standard B&BC algorithm to just 0.92% in the enhanced version. Additionally, we benchmark our approach against the progressive hedging algorithm (PHA), a widely used decomposition method in disaster response operations, to further assess its effectiveness. Finally, we present a case study from the 2011 Van earthquake in Turkey, demonstrating the applicability and efficiency of our optimization methods.

This paper focuses on developing a solution approach for a large-scale ridesharing system that is simultaneously scalable in real-time and capable of making high-quality decisions over long horizons. We propose an accelerated column-generation method embedded in a rolling-horizon framework, rather than relying on insertion-based heuristics, which lack guarantees on solution quality. To make this framework scalable in real-time, we introduce a set of acceleration strategies that not only reduce computational overhead but also guide the search toward solution structures that preserve flexibility for future decisions. Additionally, to further enhance long-term performance, we evaluate various user-centric objectives to quantify their impact on the flexibility trade-off, identifying which indicators provide better short-term decisions without adverse long-term effects. Extensive empirical experiments on historical taxi trip data from New York City demonstrate the robustness of this approach, which is capable of handling up to 30,000 requests per hour while outperforming state-of-the-art benchmarks in terms of average passenger waiting time.

Dynamic facility location problems predominantly suppose a monopoly over the service or product provided. Nonetheless, this premise can be a severe oversimplification in the presence of market competitors, as customers may prefer facilities installed by one of them. The monopolistic assumption can particularly worsen planning performance when demand depends on prior location decisions of the market participants, namely, when unmet demand from one period carries over to the next. Such a demand behaviour creates an intrinsic relationship between customer demand and location decisions of all market participants, and requires the decision-maker to anticipate the competitor's response. This work studies a novel competitive facility location problem that combines cumulative demand and market competition to devise high-quality solutions. We propose bilevel mixed-integer programming formulations for two variants of our problem, prove that the optimistic variant is $\Sigma^{p}_{2}$-hard, and develop branch-and-cut algorithms with tightened value-function cuts that significantly outperform general-purpose bilevel solvers. Our results quantify the severe cost of planning under a monopolistic assumption (profit drops by half on average) and the gains from cooperation over competition (6% more joint profit), while drawing managerial guidelines on how instance attributes and duopolistic modelling choices shape robust location schedules.