2022 Optimization Days

HEC Montréal, Québec, Canada, 16 — 18 May 2022

Schedule Authors My Schedule

TA9 - Applications of stochastic programming

May 17, 2022 10:30 AM – 12:10 PM

Location: Groupe Cholette (yellow)

Chaired by Maryam Daryalal

4 Presentations

  • 10:30 AM - 10:55 AM

    Stochastic consistent home care routing and scheduling

    • Seyede Saeede Hosseini, presenter, Polytechnique Montréal
    • Louis-Martin Rousseau, Polytechnique Montréal
    • Yossiri Adulyasak, HEC Montréal

    We study a home healthcare routing and scheduling problem in which providing a high-level service to patients plays an important role. One of the significant factors in obtaining high-quality service could be service consistency, which means visiting each patient with the same aide at almost the same time on each day they require service. Indeed, this problem is an integration of assignment, routing, and scheduling for home care services. Given the importance of visit time consistency in this problem, we incorporate stochastic service and travel times into the model. We use a chance constraint to address the stochasticity and ensure not violating each patient's assigned visit time. To check the feasibility of the scheduling despite service and travel time variations, first, we sample them by using multiple scenarios. Second, we try to replace scenarios with an estimation of arrival time and start-service time distributions for each patient. We aim to compare these two methods with each other in terms of both solving time and performance quality. To solve this problem, we use an exact optimization method, logic-based Benders decomposition (LBBD).

  • 10:55 AM - 11:20 AM

    Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

    • Margarita Castro, Pontificia Universidad Catolica de Chile
    • Merve Bodur, presenter, University of Toronto
    • Amer Shalaby, University of Toronto

    The multi-depot vehicle scheduling problem (MDVSP) is one of the main planning problems for transit agencies. We present a novel stochastic variant of the MDVSP that guarantees service reliability, measured by on-time performance (OTP) at route terminals. We propose a chance-constrained optimization model and a logic-based Benders decomposition (LBBD) algorithm to solve it. Our experimental evaluation shows the value of our stochastic variant to achieve OTP as well as the computational advantages of our LBBD approach.

  • 11:20 AM - 11:45 AM

    Stochastic Dynamic Lot Sizing with Substitution and Service Level Constraints

    • Narges Sereshti, presenter, HEC Montréal
    • Merve Bodur, University of Toronto
    • Jim Luedtke, University of Wisconsin at Madison

    We consider a multi-stage stochastic lot-sizing problem with service level constraints and product substitution. A firm has multiple products, and it has the option to meet demand from substitutable products at a cost. Considering the uncertainty in future demands, the firm wishes to make ordering decisions in every period such that the probability that all demands can be met in the next period is at least equal to a minimum service level. We propose a rolling horizon policy in which a two-stage chance-constrained stochastic program is solved to make decisions in each time period. We demonstrate how to effectively solve this formulation. In addition, we proposed two policies based on deterministic approximations and demonstrate that the proposed chance constraint policy can achieve the service levels more reliably and at a lower cost. We also explore the value of product substitution in this model, demonstrating that the substitution option allows achieving service levels at significantly reduced costs.

  • 11:45 AM - 12:10 PM

    A chance-constrained model for a Production Routing Problem with uncertain availability of vehicles

    • Alline Zanette, presenter, Polytechnique Montréal
    • Michel Gendreau, Polytechnique Montréal
    • Walter Rei, Université du Québec à Montréal

    Supply chain planning has become a major concern of many companies. While firms have long been optimizing the functions in the supply chain sequentially and separately, it is well known that optimizing one activity of the supply chain often prevents the achievement of better solutions in other areas. One way of coping with this situation is to consider integrated problems, such as the Production Routing Problem (PRP), in which one performs the joint optimization of production, inventory, distribution, and routing decisions.
    While many variants of the PRP can be found in the literature, most of them consider only deterministic data. This is a significant concern, as uncertainty is a major issue in supply chain management. In this talk, we consider a PRP with a single capacitated production facility, multiple products, a fleet of homogeneous vehicles, and uncertainty in the availability of vehicles. This is a problem setting not considered by previous studies, but commonly found in industrial environments.
    We propose a chance-constrained formulation, in which the violation of one or more constraints is allowed with a given probability. The solution scheme is based on Partial Benders Decomposition. Computational experiments are now under way on instances derived from existing benchmark instances.