Applications: Health Care
Applications: Health Care
Contributed Session
Time Slot: Friday Morning
Room: 002
Chair: Valentina Bonomi
A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints
Time: 9:00
Roberto Bargetto (LIMOS UMR CNRS 6158 Center for Biomedical and Health Care Engineering EMSE), Garaix Thierry, Xie Xiaolan
Operating theater scheduling may be often severely affected by unexpected unavailability of resources.Solving the integrated planning and scheduling problem of an operating theater is an important task to ensure the efficiency of surgical operations.We define an integrated operating room planning and scheduling problem including constraints commonly considered, for similar problems, both in practical contexts and in the literature.We focus particularly on constraints on human resources, i.e., surgeons, and nurses.The defined problem considers surgeries with different infection levels and sequence-dependent operating room cleaning times.For this integrated planning and scheduling problem, we devise a branch-and-price-and-cut algorithm based on a problem’s time-indexed formulation.The proposed column generation scheme relies on a label-correcting algorithm purposely designed for solving the related strongly NP-Hard pricing problems.The pricing problems are formulated as single operating room scheduling problems with time-dependent costs and sequence-dependent cleaning times as required.The efficiency of the label-correcting algorithm is ensured by dominance rules for labels and by two procedures for computing the upper and the lower bound of the labels. The upper-bound computation is based on the linear programming relaxation of a multidimensional 0-1 knapsack problem and the lower-bound is computed by means of a greedy heuristic procedure.For tightening the linear relaxation of the problem, we develop an effective cutting procedure inspired by Benders’ decomposition and based on duality theory for linear programming.We conduct a numerical study both on instances from the literature and on newly generated instances to demonstrate the computational effectiveness of the solution method.The Benders’-like cutting procedure is shown to be effective in tightening the linear programming bound of the problem and improves the linear programming relaxation of the problem even though the computation time is not negligible.The label correcting algorithm is efficient for generating columns.The column generation stops even for large-sized instances (up to 160 surgeries) with a moderately reduced number of columns added to the restricted master problem, typically about thousands of columns.The devised branch-and-price-and-cut algorithm outperforms both competing methods from the literature and a commercial solver.The approach of the Benders’-like cutting procedure is sufficiently generic to be applied in the case of an arbitrary number of resources for the generation of resource-related cuts, surgeon and nurse cuts in our case, improving the linear programming relaxation of the procedure master problem.
A Facility Location Problem to support Helicopter Emergency Medical Services
Time: 9:20
Mirko Cavecchia (Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia), Autelitano Federico, Consolini Luca, Giuliani Felice, Iori Manuel, Locatelli Marco
Locating helipads in strategic positions, especially in mountain areas, is a crucialdecision to reduce transport time of injured people to hospitals. The problem hasbeen largely studied in the literature. Many researches focus on identifying theoptimal set of locations to cover a given population percentage by implementinga maximal covering location problem, while other studies aim to minimize theaverage response time over the entire population or minimize the total rescue time.This work originates from the need of the Parma Helicopter Emergency MedicalService (PHEMS) to identify which existing helipads should be equipped withmodern infrastructures for night landing and, if necessary, where to build newhelipads. PHEMS provided us with the historical data referring to the rescueinterventions carried out in the last years in the province of Parma. We used thislarge data set to build two different bi-objective optimization models: the firstminimizes the cost of equipped helipads and the total rescue time; whereas thesecond minimizes the cost of equipped helipads and the total delay with respect togiven target due-dates identified on the basis of the injured urgency levels. Bothmodels have been solved via an epsilon-constrained method and tested on thePHEMS case. The resulting solutions are characterized by relevant improvementswith respect to the existing real-world solutions, both in terms of total rescue timeand total delay.
Nurse Routing Problem with Incompatible Services and Mini-mum Demand: An ALNS+Kernel Search solution approach
Time: 9:40
Alessandro Gobbi (Dipartimento di Ingegneria Meccanica e Industriale, Università degli Studi di Brescia), Manerba Daniele, Mansini Renata, Zanotti Roberto
In recent decades, the average age of the population has grown steadily along with the number of people suffering from chronic diseases and asking for treat-ments. Hospital care is expensive and often unsafe, especially for older individuals and particularly during a pandemic as the SARS-CoV-2 one. Hence, hospitalization at home has become a valuable alternative for several treatment requests with lower risk to fragile patients [1], while guaranteeing a high quality of service. This new care process clearly requires the redefinition of health services organization and the optimization of scarce resources, such as the available nurses. In this work, we study a Nurse Routing Problem [2] aiming at finding a good balance between hospital costs reduction and the well-being of patients, also considering realistic operational restrictions like maximum working times for the nurses and possible incompatibilities between services jointly provided to the same patient. We first propose a MILP formulation for the problem, strengthened by some cuts. Then, we propose a simple branch-and-cut algorithm to derive ground benchmarks. Finally, to efficiently solve the problem, we develop an ALNS hybridized with a Kernel Search [3]. The algorithm performance is tested over a large set of different realistic working scenarios. Such numerical experiments show that our matheuristic manages to find good solutions in a reasonable amount of time (even for the most difficult instances) and allow us to derive some interesting managerial insights for the healthcare provider.
[1] Landers S. et al. (2016). The future of home health care: A strategic frame-work for optimizing value. Home Health Care Management and Practice 28, 4, 262–278.
[2] Manerba D., Mansini R. (2016). The nurse routing problem with workload constraints and incompatible services. IFAC-PapersOnLine 49, 12, 1192–1197.
[3] Angelelli E., Mansini R., Speranza M.G. (2010). Kernel search: A general heuristic for the multi-dimensional knapsack problem. Computers & Operations Research 37, 11, 2017–2026.
A Two-Stage Stochastic approach for the Integrated Multi-Period Combinatorial Auction and Nurse Routing Problem
Time: 10:00
Valentina Bonomi (University of Brescia), Mansini Renata, Manerba Daniele
We study a Nurse Routing Problem (NRP) where a hospital manages patients’ assignments through a Multi-Period Combinatorial Auction (MPCA) that allows the outsourcing of visits. In the MPCA, external providers’ offers are composed of a subset of visits and the total cost required to perform them. For the patients not externally assigned, the NRP schedules daily routes for each nurse [1]. Additional consistency constraints limit the maximum number of nurses assigned to a patient in performin
g his/her visits [2]. The goal of the hospital is to select external bids to minimize the auction cost and the travelling costs to serve patients. In the deterministic version of the problem, both the hospital and the providers have access, at the beginning of the time horizon, to the exact information regarding patients and their required visits. However, to capture the complexity of real-life application, we introduce a degree of uncertainty in the model. Due to the multi-periodicity of the problem, each day the number of visits and their service time may vary from what previously agreed with the hospital [3]. Thus, we propose a two-stage stochastic formulation where we model the number of visits and their length as stochastic variables while the total number of patients remains deterministic. At the first stage, the hospital needs to make decisions about the bid based on the expected values of the random variables. The quality of these decisions can be evaluated at the second stage with the realization of such variables in a specific scenario. Our objective is to study how different hospital recourse policies affect the final solutions and the overall costs.
[1]A. Gobbi, D. Manerba, R. Mansini, R. Zanotti (2019). A Kernel Search for a patient satisfaction-oriented Nurse Routing Problem with Time Windows. In: IFAC-PapersOnLine 52 (13):1669-1674. Proceedings of MIM2019, 9th IFAC Conference on Manufacturing, Modelling, Management and Control. August 28-30, 2019. Berlin (Germany).
[2]Y. Song, M. W. Ulmer, B. W. Thomas, and S. W. Wallace (2020). Building trust in home services – Stochastic team-orienteering with consistency constraints. Transportation Science, 54(3):823-838.
[3]Lars M. Hvattum, Arne Løkketangen, Gilbert Laporte, (2006) Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic. Transportation Science 40(4):421-438.