Applied Science, Faculty of
Engineering, School of (Okanagan)
DSpace
UBCO
Pourrezaiekhaligh, Pooya
Master of Applied Science - MASc
University of British Columbia
Uncertainty is an inherent characteristic of healthcare due to the complexity and variability of the healthcare system. The healthcare industry constantly evolves, and new medical technologies and treatments are being developed, leading to new challenges and opportunities. Managing uncertainty is critical for healthcare providers as it can impact the quality of care provided to patients and the financial performance of healthcare organizations. Therefore, developing effective strategies for managing uncertainty is essential for achieving better patient outcomes and optimizing resource allocation in healthcare. This thesis explores the application of the regret minimization model to deal with demand uncertainty in a home health care location problem and uncertainty of surgery duration in an operating room planning problem. The objective is to find a balance between being conservative and being computationally efficient in decision-making under uncertainty. The literature review highlights the limitations of robust optimization models, which tend to be overly conservative and ignore the potential benefits of more optimistic scenarios. In contrast, regret minimization models provide a framework that accounts for potential regret in decision-making, leading to less conservative solutions. In the home health care planning problem, the regret minimization model is applied to determine the optimal location of home health care facilities, considering demand uncertainty. The results show that the regret minimization model yields solutions that are less conservative than those obtained using the robust optimization model. In the operating room planning problem, the regret minimization model is applied to optimize the allocation of surgeries to operating rooms, considering the uncertainty of surgery duration. The results show that the regret minimization model outperforms the robust optimization model regarding conservatism. Overall, this thesis demonstrates the effectiveness of the regret minimization model to deal with uncertainty in the home health care location and operating room planning problems.
Minimax Regret Optimization withApplications in Healthcare OperationsbyPooya PourrezaiekhalighB.Sc., The Babol Noshirvani University of Technology, 2016M.Sc., The University of Tehran, 2019A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Mechanical Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)July 2023© Pooya Pourrezaiekhaligh, 2023The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis entitled:Minimax Regret Optimization with Applications in Health-care Operationssubmitted by Pooya Pourrezaiekhaligh in partial fulfilment of the re-quirements of the degree of Master of Applied ScienceDr. Babak Mohamadpour Tosarkani, School of EngineeringSupervisorDr. Amir Ardestani-Jaafari, Faculty of ManagementCo-supervisorDr. Qian Chen, School of EngineeringSupervisory Committee MemberDr. Eric Li, Faculty of ManagementSupervisory Committee MemberDr. Sumi Siddiqua, School of EngineeringUniversity ExamineriiAbstractUncertainty is an inherent characteristic of healthcare due to the com-plexity and variability of the healthcare system. The healthcare industryconstantly evolves, and new medical technologies and treatments are beingdeveloped, leading to new challenges and opportunities. Managing uncer-tainty is critical for healthcare providers as it can impact the quality of careprovided to patients and the financial performance of healthcare organiza-tions. Therefore, developing effective strategies for managing uncertaintyis essential for achieving better patient outcomes and optimizing resourceallocation in healthcare.This thesis explores the application of the regret minimization modelto deal with demand uncertainty in a home health care location problemand uncertainty of surgery duration in an operating room planning prob-lem. The objective is to find a balance between being conservative andbeing computationally efficient in decision-making under uncertainty. Theliterature review highlights the limitations of robust optimization models,which tend to be overly conservative and ignore the potential benefits ofmore optimistic scenarios. In contrast, regret minimization models providea framework that accounts for potential regret in decision-making, leadingto less conservative solutions.In the home health care planning problem, the regret minimization modelis applied to determine the optimal location of home health care facilities,considering demand uncertainty. The results show that the regret minimiza-tion model yields solutions that are less conservative than those obtainedusing the robust optimization model. In the operating room planning prob-lem, the regret minimization model is applied to optimize the allocation ofsurgeries to operating rooms, considering the uncertainty of surgery dura-tion. The results show that the regret minimization model outperforms therobust optimization model regarding conservatism.Overall, this thesis demonstrates the effectiveness of the regret minimiza-tion model to deal with uncertainty in the home health care location andoperating room planning problems.iiiLay SummaryHealthcare operations involve high uncertainty due to various factorssuch as demand, resource availability, patient outcomes, and unexpectedevents such as natural disasters or pandemics. These uncertainties can sig-nificantly impact the design and planning of healthcare systems and thedelivery of care.This thesis focuses on dealing with uncertainty in two specific problemsin the healthcare system. The first problem is the home health care locationproblem, where there is uncertainty about demand. The second problemis the operating room planning problem, with uncertain surgery duration.In both cases, the proposed regret minimization approach aims to makeinformed decisions under uncertainty while reducing the conservatism of theexisting robust optimization methods. The results demonstrate that thesolutions generated by the regret minimization model are less conservative.Hence, this research can serve as a stepping stone for implementing theregret minimization model in addressing uncertainty in various healthcareproblems.ivPrefaceThis thesis was conducted under the supervision of Dr.Babak Mohamad-pour Tosarkani at the Industrial & Systems Engineering (ISE) ResearchGroup and Dr. Amir Ardestani-Jaafari at the Operation Management Group(OMG) at the University of British Columbia,A version of Chapter 2, which focuses on the home health care locationproblem, received revisions from INFOR: Information Systems and Opera-tional Research:− Pourrezaie-Khaligh, P., Ardestani-Jaafari, A., & Tosarkani, BM.(2023). Home health care facility location problem under demanduncertainty. First revision submitted to INFOR: Information Systemsand Operational Research, TINF-2022-0096220032720.Moreover, a version of Chapter 3, which focuses on the operating roomplanning problem, has been submitted to Operations Research for HealthCare:− Pourrezaie-Khaligh, P., Ardestani-Jaafari, A., & Tosarkani, BM.(2023). Operating room planning problem under uncertainty: a regretminimization model. Submitted to Operations Research for HealthCare.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . xList of Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . 3Chapter 2: Home Health Care Location Problem . . . . . . . 42.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 72.2.1 Home Health Care under Uncertainty . . . . . . . . . 72.2.2 Two-stage Robust Facility Location . . . . . . . . . . 82.2.3 Two-stage Regret Minimization . . . . . . . . . . . . . 102.2.4 Research Gaps and Contributions . . . . . . . . . . . . 11viTABLE OF CONTENTS2.3 Problem Definition and Formulation . . . . . . . . . . . . . . 132.3.1 Deterministic Model . . . . . . . . . . . . . . . . . . . 132.3.2 Robust Formulation . . . . . . . . . . . . . . . . . . . 152.3.3 Regret Formulation . . . . . . . . . . . . . . . . . . . 162.4 Solution Methodology . . . . . . . . . . . . . . . . . . . . . . 172.4.1 C&CG Algorithm for the RO Model . . . . . . . . . . 182.4.2 C&CG Algorithm for the RM Model . . . . . . . . . . 232.5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . 262.5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . 262.5.2 Computational Analysis . . . . . . . . . . . . . . . . . 272.5.3 Comparison of Robust and Regret Policies . . . . . . . 302.5.4 Operational Implications . . . . . . . . . . . . . . . . 362.5.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . 39Chapter 3: Operating Room Planning Problem . . . . . . . . 403.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 433.3 Problem Definition and Formulation . . . . . . . . . . . . . . 453.3.1 Deterministic Model . . . . . . . . . . . . . . . . . . . 453.3.2 Robust Formulation . . . . . . . . . . . . . . . . . . . 473.3.3 Regret Formulation . . . . . . . . . . . . . . . . . . . 483.4 Solution Methodology . . . . . . . . . . . . . . . . . . . . . . 503.4.1 C&CG Algorithm for the RO Model . . . . . . . . . . 513.4.2 C&CG Algorithm for the RM Model . . . . . . . . . . 543.5 Numerical Results . . . . . . . . . . . . . . . . . . . . . . . . 573.5.1 Computational Analysis . . . . . . . . . . . . . . . . . 573.5.2 Comparison of Robust and Regret Policies . . . . . . . 603.5.3 Concluding Remarks . . . . . . . . . . . . . . . . . . . 64Chapter 4: Conclusions and Future Works . . . . . . . . . . . 674.1 Research Summary . . . . . . . . . . . . . . . . . . . . . . . . 674.2 Research Contributions . . . . . . . . . . . . . . . . . . . . . 684.3 Research Limitations . . . . . . . . . . . . . . . . . . . . . . . 694.4 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . 69Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80A.1 Proof of Proposition 3.3 . . . . . . . . . . . . . . . . . . . . . 80viiList of TablesTable 2.1 A summary of related works in HHC optimization prob-lems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13Table 2.2 Parameters used for generating instances. . . . . . . . 26Table 2.3 Average computational time (in seconds) and the num-ber of iterations for medium-sized instances. . . . . . . 28Table 2.4 Average computational time (in seconds) and optimal-ity gap (in %) for large-sized instances. . . . . . . . . . 29Table 2.5 Average suboptimality gap (in %) of RO and RMmodels. 31Table 2.6 Mean number of opened HHC facilities. . . . . . . . . 33Table 3.1 Number of variables and constraints of RO and RMmodels. . . . . . . . . . . . . . . . . . . . . . . . . . . 50Table 3.2 Average computational time (in seconds) and the num-ber of iterations of RO and RM models with cν = 0.0333. 58Table 3.3 Average computational time (in seconds) and the num-ber of iterations of RO and RM models with cν = 0.0083. 59Table 3.4 Average suboptimality gap (in %) of RO and RMmodels. 61Table 3.5 Average worst-case cost and absolute regret. . . . . . . 62Table 3.6 Overtime of RO and RM models (in minutes). . . . . . 63Table 3.7 Mean number of opened ORs. . . . . . . . . . . . . . . 64viiiList of FiguresFigure 2.1 Two-stage HHC location problem. . . . . . . . . . . . 14Figure 2.2 Impact of uncertainty budget on the worst-case profit. 32Figure 2.3 Impact of uncertainty budget on worst-case absoluteregret. . . . . . . . . . . . . . . . . . . . . . . . . . . . 32Figure 2.4 Impact of uncertainty budget on the number of care-givers. . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Figure 2.5 Illustration of the solution for the generated instanceunder deterministic environment. . . . . . . . . . . . 36Figure 2.6 Illustration of the solution for the generated instancewhen Γ = 0.1n. . . . . . . . . . . . . . . . . . . . . . . 37Figure 2.7 Illustration of the solution for the generated instancewhen Γ = n. . . . . . . . . . . . . . . . . . . . . . . . 38Figure 3.1 Impact of uncertainty level on worst-case cost in Sce-nario 1. . . . . . . . . . . . . . . . . . . . . . . . . . . 65Figure 3.2 Impact of uncertainty level on worst-case cost in Sce-nario 2. . . . . . . . . . . . . . . . . . . . . . . . . . . 66ixList of AbbreviationsARO Adjustable robust optimizationBD Benders decompositionCG Constraint generationC&CG Column-and-constraint generationDEM Deterministic equivalent modelHHC Home health careKKT Karush–Kuhn–TuckeLP Linear programmingMCBD Multi-cut benders decompositionMCPBD Multi-cut partial benders decompositionMIP Mixed-integer programmingMILP Mixed-integer linear programmingMRFLP Multi-period robust facility location problemOM Operations managementOR Operating roomRHS Right-hand sideRM Regret minimizationRO Robust optimizationSP Stochastic programmingTRFLP Two-stage robust facility location problemxList of SymbolsHome Health Care Location Problemm Set of the HHC facilities location indexed by in Set of the demand nodes indexed by jfi Fixed cost of opening HHC facility ici Variable cost of opening HHC facility iηij The unit revenued¯j The demand of node jΓ Budget of uncertaintyε Maximum deviation ratioIi A binary variable indicating whether an HHCfacility is opened at location izi The number of caregivers in HHC facility iyij The number of caregivers travelled from HHCfacility i to demand node jOperating Room Planning Problemm Set of the ORs indexed by jn Set of the surgeries indexed by iT Planned session length for ORscf The fixed cost of opening an ORcν The variable cost per unit of time for keepingan OR open past time Tζi The duration of surgery ixj The binary variable that represents the openingstatus of OR jyij A variable that represents the allocation ofsurgery i to OR joj The overtime of OR jxiAcknowledgementsI would like to express my sincere gratitude to my supervisors, Dr. BabakMohamadpour Tosarkani and Dr. Amir Ardestani-Jaafari, for their guid-ance, support, and encouragement throughout my research. Their expertise,constructive feedback, and valuable insights were essential in shaping mywork.I would also like to thank my friends, who have been a constant sourceof support and encouragement. Their kindness, understanding, and supporthave been invaluable during the challenging moments.Despite the physical distance, my family has always been my rock, and Icannot thank them enough for their love and support. My parents, who arethousands of kilometres away, have always been my guiding light, and theirunwavering belief in my abilities has been my driving force. I am gratefulfor their sacrifices, dedication, and encouragement throughout my academicjourney.Thank you all for your contribution and support.xiiDedicationTo my mother, whose unwavering love, support, and belief in me havebeen the driving force behind my academic journey. This thesis is dedicatedto you with heartfelt gratitude.xiiiChapter 1IntroductionThis introduction is intended to provide the rationale for the researchundertaken and the objectives that will be achieved throughout this thesis.An outline of the thesis will be presented to provide an overview of theupcoming chapters.1.1 MotivationHealthcare systems play a vital role in ensuring the well-being of individ-uals and communities. They are responsible for providing medical care topatients, managing healthcare facilities, and developing policies to improvepublic health. One of the critical challenges in designing an efficient health-care system is optimizing the use of resources, such as healthcare facilities,medical staff, and medical equipment. Optimization problems such as facil-ity location and scheduling have been widely used to improve the efficiencyof healthcare systems.However, uncertainty is an inherent aspect of healthcare systems, whichcan significantly impact the performance of optimization models. Uncer-tainty can arise due to various factors, such as the availability of resources,patient demand, and data reliability. Uncertainty plays a crucial role inhealthcare optimization problems because it reflects the reality of the health-care system. In other words, healthcare systems are complex and often un-predictable, with many factors that can affect the quality of care and theefficiency of the system. Therefore, it is essential to account for uncertaintyin the design and optimization of healthcare systems to ensure that theycan adapt to unexpected situations and changes.In the case of home health care (HHC) services, for example, the demandcan vary significantly due to many factors, such as demographic changes andshifts in health policies. If we don’t consider this uncertainty, we may end upwith suboptimal solutions that can affect the long-term performance of thesystem. Similarly, The duration of surgeries can vary due to many factors,such as the patient’s condition and the complexity of the procedure. Ignor-ing this uncertainty we may end up with inefficient operating room (OR)11.1. MOTIVATIONschedules that do not account for unexpected changes in surgery duration.To deal with uncertainty in healthcare operations, robust optimization(RO) methods have been widely used to make informed decisions even withlimited information about uncertain parameters. Indeed, RO is an approachto optimization that aims to find solutions that are robust to uncertainty inthe input parameters. In other words, it seeks to find solutions that workwell under a range of possible scenarios, rather than just optimizing for asingle, specific scenario.However, these methods are too conservative and lead to suboptimalsolutions. Generally, in decision-making problems under uncertainty, be-ing overly conservative can be detrimental to achieving optimal outcomes.Being overly conservative means that one may be excessively cautious andassume the worst-case scenario when dealing with uncertainty. This canresult in overly restrictive decisions that do not take into account the po-tential benefits of more optimistic scenarios. Specifically, in the context ofHHC planning decisions, being overly conservative can result in suboptimalallocation of resources, which can reduce the number of patients who can betreated and increase costs. Similarly, in OR planning decisions, being overlyconservative can lead to reduced utilization of surgical units, hindering thetreatment of a larger group of patients and increasing waiting times andsurgical operating costs.In recent years, researchers have proposed regret minimization (RM)methods that aim to minimize the maximum regret associated with a givenuncertainty set. Simply speaking, RM is a decision-making strategy thatseeks to minimize the regret or the difference between the actual outcome ofa decision and the best possible outcome that could have been achieved inhindsight. As shown in the literature, RM models have been found to yieldless conservative solutions compared to those obtained from RO models(see, e.g., Mausser and Laguna, 1999; Natarajan et al., 2014; Caldenteyet al., 2017). However, the main barrier to employing the RM models is thecomputational complexity of these models.The computational complexity of HHC location and OR planning prob-lems is a critical consideration due to their large-scale nature and the needfor real-time decision-making. These problems involve numerous locations,caregivers, patients, procedures, and factors that contribute to exponen-tial growth in computational resources required for finding optimal solu-tions. Efficiently managing computational complexity is crucial for makingtimely decisions, optimizing resource allocation, ensuring cost-effectiveness,and accommodating scalability and generalizability. By developing efficientalgorithms, decision-makers can overcome the challenges posed by compu-21.2. OBJECTIVEStational complexity and make informed, resource-efficient decisions that en-hance patient care and operational performance in the dynamic healthcareenvironment.1.2 ObjectivesThis thesis aims to investigate the application of RM models for deal-ing with uncertainty in two specific healthcare problems: the HHC locationproblem and the OR planning problem. The study first explores the chal-lenges posed by uncertainty in healthcare and the limitations of traditionalRO models in decision-making.In Chapter 2, we apply the RM model to solve the HHC location prob-lem considering demand uncertainty. The objective is to determine optimallocation and allocation decisions that are less conservative, thereby enhanc-ing the quality of solutions in terms of flexibility. Additionally, we develop asolution scheme to address the computational complexity of the RM model,enabling us to strike a balance between conservatism and computationalefficiency.In Chapter 3, the RM method is employed to address the uncertaintyassociated with surgery duration in the OR planning problem. The primaryobjective of this study is to assign surgeries to ORs in a flexible manner, aim-ing to reduce overtime and the costs associated with OR openings. For bothproblems, we compare the performance of the RM and RO models to assesswhether the RM model can enhance the quality of solutions. Additionally,we analyze the impact of uncertainty on the obtained solutions.1.3 Thesis OutlineThe structure of this thesis is as follows. Chapter 2 presents the firststudy, which addresses demand uncertainty in an HHC location problem.Chapter 3 presents the second study, which addresses the uncertainty ofsurgery duration in an OR planning problem. Finally, Chapter 4 summarizesthe main findings, contributions and limitations of our research and outlinespotential avenues for future research.3Chapter 2Home Health Care LocationProblemIn this chapter, the application of an RM model to deal with demanduncertainty in an HHC location problem is investigated.2.1 IntroductionThe number of older adults receiving various healthcare services has sig-nificantly increased, particularly in many low and middle-income countries.This trend is expected to continue as the population aged 60 years and overis projected to double by 2050 (World Health Organization, 2015). In re-sponse, HHC services, which emerged around 1950, have become an effectiveway for health systems to reduce costs and improve patient’s quality of life.Over the years, the number of HHC service providers and demand for theseservices has increased, making HHC a rapidly growing sector in medical ser-vices. For instance, in Canada, 6% of the population received HHC servicesin 2021 (Statistics Canada, 2021). HHC services are particularly suitablefor the elderly, people with disabilities, and other vulnerable groups in so-ciety who may not be able or willing to use traditional healthcare facilities.HHC companies offer this service with the aim of helping patients recoverfrom illness or injury in the comfort of their own homes (Liu et al., 2014).In 2011, approximately 143,600 employees worked for 12,200 HHC serviceproviders to meet the needs of over 4.7 million patients in the United States(Fikar and Hirsch, 2017). HHC services can enhance the healthcare systemby reducing hospitalization rates and demand for hospital admissions (Cisse´et al., 2017).Developing an efficient HHC system is a relatively new and challengingarea of study in operations management (OM). As such, OM has addressedseveral challenges, such as scheduling, routing, and resource allocation prob-lems in designing an HHC system (Grieco et al., 2021). However, only a fewstudies have addressed the location of HHC facilities, even though it is a42.1. INTRODUCTIONcrucial strategic decision in designing a healthcare system (Ahmadi-Javidet al., 2017). Optimizing the location of HHC facilities can help healthcaresectors efficiently meet demand. This boosts HHC providers’ revenues andimproves equity, which is the primary goal in designing a healthcare servicesnetwork. Therefore, it is crucial to pay more attention to location manage-ment and strategic planning at the healthcare facility level (Gutie´rrez et al.,2013).Determining the location of healthcare facilities becomes critical in healthsystems because the improper location of facilities can seriously affect thepublic. Poorly designed healthcare systems make it difficult for patients toaccess facilities, leading to increased morbidity and mortality rates. There-fore, modelling the healthcare facility location is more critical than similarmodelling for other OM areas. Constructing a new facility takes a signifi-cant amount of time and is costly. Consequently, when a facility is built, itis expected to remain active for a long time. However, many uncertaintiessuch as natural disasters, technological disruptions, and population shiftscan affect facility performance. Therefore, it is critical to consider potentialsources of uncertainties to make strategic decisions efficiently (e.g., facilitylocation) and keep the system away from high recourse costs in the opera-tional stage. Uncertainty is also prevalent in healthcare systems and cannotbe ignored. For example, surgery duration, staff availability, and urgentor emergency arrivals are the primary sources of uncertainty in OR plan-ning and staffing problems (Breuer et al., 2020). Additionally, emergencyvehicle routing problems can be uncertain due to the availability of ambu-lances (Ziya-Gorabi et al., 2022). Uncertainty also arises in managing HHCservices.To tackle uncertainty in HHC optimization problems, stochastic pro-gramming (SP) is a well-known approach that is widely applied by re-searchers, where the probability distribution of uncertain parameters is as-sumed to be known (Nikzad et al., 2021). However, in many practical health-care optimization problems, such as the problem given in this study, theremay only be very limited available information about uncertain parameters.Moreover, SP models involve generating multiple scenarios and solving aseparate optimization problem for each scenario. This can make the prob-lem computationally complex, especially when dealing with a large numberof scenarios. To overcome these challenges, RO models have been developedin the literature, where the goal is to produce a robust solution that canwithstand adverse realizations of uncertainty (Gabrel et al., 2014b). ROmodels do not require as much data since it does not rely on the probabilitydistribution of uncertainty parameters. Furthermore, these models typically52.1. INTRODUCTIONinvolve solving a single optimization problem that incorporates all possiblescenarios, which can be more computationally efficient than SP models.Specifically, strategic decisions such as determining the location of HHCfacilities and tactical decisions such as the number of caregivers must bemade prior to the operational lifetime of the facilities. Therefore, the decision-making process should commence before the exact size of demand is ob-served. Caregivers should then be allocated to the demand node based onthe observed demand. Classical RO methods make decisions under a staticsetting, where all decision variables represent “here-and-now” decisions thatneed to make before the uncertain parameters are realized (Jeyakumar et al.,2023). Multi-stage versions of decision-making have been developed in thecontext of RO, called adjustable robust optimization (ARO), where the pri-mary assumption is that decisions are made at different points in time. In ad-dition to “here-and-now” decisions, this approach involves other types of de-cisions, called “wait-and-see” decisions that can be adjusted after the uncer-tain parameters have been realized. While ARO models are tractable, theycan generate over-conservative solutions and do not consider non-extremescenarios (Ng, 2013). Being overly conservative in HHC planning decisionscan result in suboptimal allocation of resources, reducing the number of pa-tients that can be treated and increasing costs. On the other hand, findingthe right balance between conservatism and tractability is challenging, as adecrease in conservatism can lead to a decrease in tractability.There is also a well-known alternative approach to cope with uncertaintyin the optimization context called RM. As investigated in the literature, RMmodels resulted in less conservative solutions compared to those derivedfrom RO models (see, e.g., Mausser and Laguna, 1999; Natarajan et al.,2014; Caldentey et al., 2017). However, computational complexity is themain barrier to employing RM models, while RO models are computation-ally tractable. Considerable efforts were invested in removing this barrierby developing exact and approximation methods, but most of them focusedon single-stage mixed-integer programming (MIP) models. Recently, someresearchers investigated two-stage MIP formulations and tried to developapproximation solution schemes to derive tractable solutions for these formsof models. However, less attention has been paid to developing tractablesolution methods for two-stage RM problems than for two-stage RO prob-lems. No studies, to our knowledge, employed RM to deal with uncertaintyin HHC optimization problems. Accordingly, no attempt has been made topropose a general tractable conservative solution scheme for the RM modelof HHC optimization problems.The aim of this study is to develop a two-stage minimax regret model62.2. LITERATURE REVIEWfor locating HHC facilities. To solve the problems, a column-and-constraintgeneration (C&CG) algorithm has been developed. In addition, extensivenumerical experiments have been conducted to compare the RO and RMmodel’s performance.The rest of this chapter is organized as follows. In Section 2.2, relatedstudies are reviewed to identify research gaps and address them accordingly.Section 2.3 presents two-stage RO and RM models for the HHC problem.Section 2.4 describes an exact solution method developed to solve the prob-lem. In Section 2.5, the performance of the RO and RM models is comparedand some managerial insights are derived based on the results obtained.2.2 Literature ReviewThis section reviews studies in three main research streams related to ourstudy: HHC under uncertainty, two-stage robust facility location problem(TRFLP), and two-stage RM. After reviewing these studies, we analyze theresearch gaps and explain how our study contributes to the literature.2.2.1 Home Health Care under UncertaintyAlthough the HHC problem has been extensively studied in the literature(see, e.g., Fikar and Hirsch, 2017; Cisse´ et al., 2017), very few studies haveaddressed the uncertainty of this problem. Therefore, in this section, wereview the most relevant papers related to our research in the context ofHHC.Several studies have addressed scheduling and routing problems in HHCthat involve stochastic service/travel times (see, e.g., Yuan et al., 2018; Shiet al., 2018; Nikzad et al., 2021; Du and Zhang, 2022). Additionally, a fewstudies have considered other sources of uncertainty, such as demand, inHHC optimization problems (see, e.g., Rodriguez et al., 2015; Yuan et al.,2015). However, only a few papers have applied RO methods to deal withdemand uncertainty in HHC optimization problems. For instance, Carelloand Lanzarone (2014) proposed a robust cardinality-constrained method fornurse-to-patient assignment under demand uncertainty. Similarly, Cappan-era et al. (2018) applied the same method to handle patient demand uncer-tainty while also considering scheduling and routing decisions in addition toassignment decisions.Another study, Shi et al. (2017), used a fuzzy chance-constrained modeland a hybrid genetic algorithm to address demand uncertainty in HHC.72.2. LITERATURE REVIEWSome studies considered uncertainty in service/travel times, such as Fathollahi-Fard et al. (2020), which studied a bi-objective HHC problem in a fuzzyenvironment where travel and service times and patient satisfaction wereuncertain. Shahnejat-Bushehri et al. (2021) used an RO method to handleuncertain service and travel times. Similarly, Shiri et al. (2021) proposed anRO method to handle uncertainty in a multi-objective HHC problem.Moreover, Ziya-Gorabi et al. (2022) used a hybrid model of expectedvalue and fuzzy chance-constrained programming to handle uncertainty ina multi-objective green HHC problem. Li et al. (2022) studied a multi-objective HHC problem with priorities and fuzzy service and travel times,while Shiri et al. (2022) proposed a multi-objective mixed-integer linearprogramming (MILP) model for an HHC network design problem underuncertainty, using a robust-fuzzy approach to tackle uncertain parameters,such as costs, social factors, and service time.2.2.2 Two-stage Robust Facility LocationIn real-world scenarios, the locations of facilities are often determinedwith limited information about demand, and transportation decisions aremade after demand is revealed. Two-stage RO methods have been widelyused to formulate such optimization problems. For instance, Atamtu¨rk andZhang (2007) developed a TRFLP aimed at minimizing the worst-case cost.They sampled 200 scenarios to capture the demand distribution and com-pared the two-stage RO model with a two-stage SP model that aimed tominimize the sum of the first-stage cost and the expected value of the second-stage cost. Their numerical experiments revealed that while the two-stageRO model led to a slight increase in expected cost, it significantly reducedthe cost of the worst-case scenario.As shown in the literature, TRFLP is an NP-hard problem, and it re-quires polynomial-time algorithms to be solved efficiently. Hence, severalstudies have been conducted to address the computational complexity ofTRFLP using exact and approximation methods.Several researchers have developed tractable approximation models toaddress the computational complexity of TRFLP. For example, Baron et al.(2011) proposed an RO approach, which can be considered the first tractableconservative approximation of the multi-period robust facility location prob-lem (MRFLP). The proposed RO approach was used to handle demanduncertainty, and two models were considered, including box and ellipsoidaluncertainty. The main objective of the problem was to evaluate the potentialbenefits of the RO approach to a facility location problem. A comprehen-82.2. LITERATURE REVIEWsive numerical study was conducted, in which three different models weresolved. The results showed that considering box and ellipsoidal uncertaintycan significantly improve the underlying network and increase the profit.In another study, Ardestani-Jaafari and Delage (2018) proposed threeapproximation models that make a trade-off between tractability and con-servatism to improve the quality of approximate solutions for MRFLP, es-pecially compared to Baron et al. (2011). They presented a row genera-tion method to solve large-scale instances under the budgeted uncertaintyset. The findings revealed that the presented approximation models out-performed previous models proposed for the facility location problem in theliterature.Recently, there have been improvements in approximation models fortwo-stage adjustable RO problems. For instance, in their previous study,Ardestani-Jaafari and Delage (2018) proposed three approximation modelsthat trade-off between tractability and conservatism, but their computa-tional time was an issue. To overcome this problem, Ardestani-Jaafari andDelage (2021) developed new tractable conservative approximation modelsusing a linearization scheme, and evaluated their performance in a TRFLP.Their results showed that the proposed model outperformed the traditionalC&CG method in large-scale instances.Additionally, Bertsimas and de Ruiter (2016) proposed an equivalentdualized model for general two-stage adaptive linear optimization problems,including the TRFLP. They showed that the dual formulation is significantlyfaster than the primal formulation with affine policies and that using the dualformulations’ affine policy could strengthen lower bounds on the optimalityof affine policies. This approach was empirically tested on TRFLP.Some efforts were also conducted to propose exact methods to solve TR-FLP in a tractable way. Atamtu¨rk and Zhang (2007) and Gabrel et al.(2014a) developed an iterative cutting-plane method to exactly solve the ro-bust version of the facility location problem under the budgeted uncertaintysets. More specifically, they showed that it is possible to reformulate theadversarial problem in the proposed two-stage robust problem as a MILP.Consequently, Kelley’s cutting-plane algorithm could be used to deal withthe master problem of TRFLP. They also showed that the recourse problemis the most demanding part of TRFLP. However, proposing a tight boundallowed them to solve large-scale problems.Compared to previous studies, Zeng and Zhao (2013) proposed a C&CGalgorithm for TRFLP, rather than using Benders-style cutting-plane meth-ods (e.g., Kelley’s cutting-plane algorithm) to increase computation speed.In another advancement on cutting-plane algorithms, Lei et al. (2016) im-92.2. LITERATURE REVIEWproved a two-level cutting-plane method to tackle the computational com-plexity of the two-stage RO model for mobile-facility fleet sizing and rout-ing problems. Numerical experiments showed that their developed solutionmethod efficiently solved the problem and outperformed other solution ap-proaches. Additionally, Simchi-Levi et al. (2019) proposed constraint gen-eration (CG) and C&CG methods for solving two-stage robust minimumcost flow problems under general polyhedral uncertainty sets. Firstly, theyreformulated separation problems as MILPs by exploiting the network-flowstructure. Their new MILP formulations are more concise than those ex-isting in the literature and do not require a big-M approach, making themeasier to solve using MILP solvers. They then applied their new MILPformulations to CG and C&CG methods to solve two-stage RO problems.Finally, they used their approach to solve a facility location problem and aproduction postponement problem in numerical experiments.In the same research line, Cheng et al. (2021b) implemented the C&CGmethod to solve the TRFLP under disruption risk. They used a budgetuncertainty set to formulate the risk of facilities disruption. To evaluatethe performance of the C&CG method, they proposed an approximationscheme and obtained results showed that the C&CG algorithm outperformsthe approximation method. Cheng et al. (2021a) contributed to their pre-vious studies by considering demand uncertainty (receiver side) in additionto facility disruption risk (provider side). Then, they applied the C&CG al-gorithm to solve the proposed TRFLP. Considering in-between uncertaintyis another improvement on two previous papers that have been made by Luand Cheng (2021). In this study, the authors used a budget uncertainty setto capture the interaction between the demand uncertainty and faculties’disruption risk. In addition to C&CG, they employed the benders decom-position (BD) method to solve the problem exactly.2.2.3 Two-stage Regret MinimizationIn addition to considering tractability, conservatism is a crucial factorthat must be taken into account, and striking a balance between them isvital. However, achieving this balance is challenging because producing lessconservative solutions could result in intractability. In the robust facilitylocation problem literature, some studies have addressed both tractabilityand conservatism (see, e.g., Baron et al., 2011; Ardestani-Jaafari and De-lage, 2018, 2021). As mentioned in Section 2.1, RM is a viable alternativeto RO as it results in less conservative solutions. Nevertheless, fewer studieshave employed RM models than RO models because they are too complex102.2. LITERATURE REVIEWto solve in polynomial time. In recent years, the two-stage RM methodhas been applied to several optimization problems, such as the newsvendorproblem (Perakis and Roels, 2008) and lot sizing (Zhang, 2011). However,to our knowledge, only a few studies have employed a two-stage RM modelfor a facility location problem, so most related studies that offer ideas totackle the complexity of the two-stage RM are reviewed.Assavapokee et al. (2008b) developed an iterative algorithm called thescenario relaxation algorithm for two-stage absolute and relative regret opti-mization with min-max criteria and scenario-based uncertainty. They tack-led a two-stage decision-making problem in which the first-stage problemis a MILP model with binary variables, while the second-stage problem isan LP model. The authors also proved that their solution method con-verges to an optimal solution if one is obtainable within a limited numberof iterations. In another study, Assavapokee et al. (2008a) applied theirscenario relaxation algorithm to a two-stage decision-making problem underinterval-based uncertainty (box uncertainty set), where uncertainty affectsthe right-hand side (RHS) of constraints and coefficients used to formulatethe decisions of the first-stage problem. They solved the recourse problemusing two MILP reformulations, generating feasibility and optimality cuts,respectively. Furthermore, Jiang et al. (2013) and Chen et al. (2014) alsoapplied this scenario relaxation algorithm to a two-stage RM problem withpolyhedral uncertainty. Ng (2013) proposed a two-stage RM with polyhe-dral uncertainty for linear programs where uncertainty affects RHS and theobjective function. The author developed a conservative approximation ofthe regret function, in the form of a two-stage RO problem. Their proposedsolution scheme was based on an iterative relaxation and cut generationmethod.More recently, Ning and You (2018) reformulated a two-stage RM modelwith polyhedral uncertainty, affecting RHS, as a two-stage RO model totake advantage of tractable solution methods. In addition, they proposeda C&CG algorithm to solve large-scale problems. Poursoltani and Delage(2021) developed the study of Ning and You (2018) by considering rela-tive regret and objective uncertainty. Moreover, authors numerically andtheoretically proved that using affine decision rules leads to obtaining high-quality first-stage decisions.2.2.4 Research Gaps and ContributionsTable 2.1 summarizes relevant papers related to our study, which aimsto identify research gaps in the literature on designing HHC systems. Upon112.2. LITERATURE REVIEWobservation, it becomes clear that most studies have solely focused on rout-ing, allocation, and scheduling decisions, disregarding the crucial role oflocation decisions in designing an effective HHC system. Although somestudies have addressed the location management of HHC facilities (see, e.g.,Rodriguez et al., 2015), only a few have done so under uncertainty, and theyhave only considered the location decisions for a single-stage HHC problem(see, e.g., Ziya-Gorabi et al., 2022). In reality, determining the locationof facilities is critical, particularly when demand information is unavailable.Consequently, it is essential to address this issue in a two-stage environ-ment. To our knowledge, the RM method has not been applied to HHCoptimization problems, and only a few studies have applied single-stage ROand SP to address uncertainty in this field. Furthermore, only a handful ofstudies have proposed exact solution methods for solving large-scale HHCoptimization problems.Overall, this study aims to overcome three barriers in the literature.First, addressing the location decisions in the HHC problem under uncer-tainty. Second, proposing an uncertainty method to improve the quality ofsolutions in a two-stage environment. Finally, reformulating the two-stageRM problem with the MILP recourse problem as RO benefits from trace-ability (interested readers are referred to Poursoltani and Delage, 2021).Initially, our study contributes to the literature in the following ways:(i) A two-stage facility location problem is proposed to address the loca-tion decisions in the HHC problem where we determine the location ofHHC facilities before observing the demand and number of caregiversto transport to demand nodes after receiving orders.(ii) RO and RMmodels are formulated for an HHC location problem underdemand uncertainty. Our proposed RM model provides less conserva-tive solutions compared to the RO formulation proposed by previousstudies.(iii) The given two-stage RM model is reformulated as an RO model, and aC&CG is proposed to tackle the computational intractability. This al-lows for solving the large-scale instances of the HHC location problemin a tractable way.(iv) An extensive set of numerical experiments is presented to provide in-sights into the two-stage RM model. In this way, the performance ofthe RM model is analyzed in terms of tractability and conservatism.122.3. PROBLEM DEFINITION AND FORMULATIONTable 2.1: A summary of related works in HHC optimization problems.Reference Modeling scheme Problem Solution methodCarello and Lanzarone (2014) RO A CPLEXYuan et al. (2015) SP R & S Branch-and-priceShi et al. (2017) FP R MetaheuristicsCappanera et al. (2018) RO A & S Decomposition methodFathollahi-Fard et al. (2020) FP R & S MetaheuristicsBazirha et al. (2021) SP R & S MetaheuristicsShahnejat-Bushehri et al. (2021) RO R & S MetaheuristicsShiri et al. (2021) RO R & S CPLEXNikzad et al. (2021) SP A, R & S CPLEXZiya-Gorabi et al. (2022) FP R MetaheuristicsLi et al. (2022) FP A Goal attainmentThis study RO & RM FL C&CGNotes. A: Assignment; R: Routing; S: Scheduling; FL: Facility location; FP: Fuzzy programming2.3 Problem Definition and FormulationIn this section, first, the given two-stage HHC location problem is de-fined. Then, the problem formulation is presented under a deterministicsetting. Finally, two-stage RO and RM models are presented.2.3.1 Deterministic ModelA two-stage HHC location problem under demand uncertainty is ad-dressed in this study. An HHC facility is a base of operations from whichHHC providers begin their journeys to clients’ homes. In essence, it is acenter that manages the assignment of caregivers with varying skills andavailability to patients. There are potential locations to open the HHC fa-cilities and some demand nodes that caregivers should serve. The study’smain goal is to determine the optimal location of HHC facilities so that theprofit is maximized while some constraints are satisfied. Figure 2.1 showshow strategic and operational decisions are made in two stages under de-mand uncertainty. In the first stage, the location of HHC facilities and thenumber of caregivers in each facility are determined without observing thedemand. Once HHC facilities start their operational life, they receive theorders of clients needed for HHC services. With this information in hand,the number of caregivers that should be transported from each facility toeach demand node is determined in the second stage.132.3. PROBLEM DEFINITION AND FORMULATIONDemand revealingHHC facilityDemand nodeSecond stageFisrt stageFigure 2.1: Two-stage HHC location problem.The OR planning problem can be formulated as a deterministic optimiza-tion problem, where i and j are the indices for locations of HHC facilitiesand demand nodes, respectively. I ∈ Rm is a binary variable indicatingwhether an HHC facility is opened at location i. Decision variable z ∈ Rmdenotes the caregivers in HHC facility i. y ∈ Rm×n denotes the numberof caregivers travelled from HHC facility i to demand node j. Parameterdj is a demand of node j, and ηij > 0 denotes the unit revenue assigningcaregivers of HHC facility i to demand node j. It should be mentioned thatthe travelling time is considered in revenue as well. Indeed, the ηij decreasesas the travel distance increases because as the travel time increases, the costof providing the care services also increases. Moreover, ci and fi denotethe variable and fixed capacity costs for HHC facility i. The following MIPmodel is the formulation of a deterministic HHC location problem with mand n locations of HHC facilities and demand nodes, respectively:maximizey,z,I∑i∑jηijyij − (c⊤z + f⊤I ) , (2.1a)subject to∑iyij ≤ dj , ∀ j , (2.1b)∑jyij ≤ zi , ∀ i , (2.1c)yij ≥ 0 , ∀ i , ∀ j , (2.1d)z ≥ 0 , z ≤ MI , I ∈ {0, 1}m . (2.1e)The objective function (2.1a) maximizes the total profit, which is equalto the service revenue deducted by total expected costs: fixed and variablecapacity costs. Constraint (2.1b) guarantees that the sum of allocated care-givers to demand node j is less than the demand of the node. Constraint142.3. PROBLEM DEFINITION AND FORMULATION(2.1c) states that the sum of allocated caregivers from HHC facility i shouldbe less than the number of caregivers in that facility. Finally, Constraints(2.1d) and (2.1e) are the integrality and non-negativity constraints.2.3.2 Robust FormulationProblem (2.1) is defined under a deterministic setting and assumes thatthe demand is already known at the time of decision-making. However,the decisions to open HHC facilities and the number of caregivers be madebefore the demand is revealed. Ignoring this aspect can adversely impactthe system’s performance by disregarding worst-case scenarios. RO modelsgenerally use minimax or maximin criteria to optimize the system’s perfor-mance in a worst-case scenario. Because of their practical relevance, thesecriteria have broadly been used in OM problems under uncertainties, e.g., ,network design problems (Akbarpour et al., 2020), facility location problems(Berglund and Kwon, 2014), and vehicle routing problems (Golden et al.,1997). The main reason for the popularity of these approaches is that re-formulations can be used for many robust models based on minimax andmaximin to be solved efficiently. Ensuring the traditional RO models, thetwo-stage robust HHC location problem with a maximin criterion is definedasmaximizeI,zmind∈Uh(z, d)− (c⊤z + f⊤I ) (2.2a)subject to z ≥ 0 , z ≤ MI , I ∈ {0, 1}m, (2.2b)where h(z, d) is the second stage profit and is defined ash(z, d) := maxy∑i∑jηijyij (2.3a)subject to∑iyij ≤ dj , ∀ j , (2.3b)∑jyij ≤ zi , ∀ i , (2.3c)yij ≥ 0 , ∀ i , ∀ j . (2.3d)The objective function (2.2a) optimizes the sum of the first-stage costsand second-stage profit. The demand lies in uncertainty set U that is definedas152.3. PROBLEM DEFINITION AND FORMULATIONU :=d ∈ Rn : dj = d¯j + (δ+j − δ−j )dˆj , 0 ≤ δ+ , δ− ≤ 1 ,∑j(δ+j + δ−j ) ≤ Γ ,where d¯j and dˆj represent the nominal demand and maximum allowabledeviation of nominal demand, respectively. Moreover, δ+j and δ−j are non-negative variables. Finally, the budget of uncertainty, denoted by Γ, wasintroduced by Bertsimas and Sim (2004) and used to control the level ofrobustness.2.3.3 Regret FormulationProblem (2.2) aims to optimize the HHC location problem decisions thatmaximize the system’s profit over the worst-case scenario. This method isfrequently viewed as more risk-averse since it concentrates exclusively onreducing the adverse consequences of a decision. Although this can mit-igate potential risks for decision-makers, it may also result in excessivelyconservative decisions that could have a detrimental impact on the system’sperformance. Conversely, the RM model evaluates a decision x based onthe worst-case absolute RM, which considers the maximum potential regretthat could occur in the future when comparing decision x to the optimaldecision that could have been made, as outlined in Savage (1951) work ondecision theory. As previously mentioned, the RM approach can lead to lessconservative solutions. We apply the worst-case absolute regret criterion,which is a difference between the system’s performance with full and partialinformation about an uncertain parameter. The worst-case absolute RM isdefined asminimizeI,zmaxd∈UmaxI′,z′Π(I ′, z′, d)−Π(I, z, d) , (2.4)where Π(I, z, d) = h(z, d)− (c⊤z + f⊤I).minimizeI ,zmaxd∈U ,(I′ ,z′)∈X ,y′∈Y(d,z′)∑i∑jηijy′ij − (c⊤z′ + f⊤I ′)+ (c⊤z + f⊤I)− h(z, d) (2.5a)subject to z ≥ 0 , z ≤ MI , I ∈ {0, 1}m , (2.5b)162.4. SOLUTION METHODOLOGYwhereX := {(I, z) ∈ Rm × Rm : z ≥ 0 , z ≤ MI , I ∈ {0, 1}m} ,Y(d, z) :=Y ∈ Rm×n :∑iyij ≤ dj , ∀ j ,∑jyij ≤ zi , ∀ i , y ≥ 0 .The objective function minimizes (2.5a) the worst-case absolute regretwhere Π(I ′, z′, d) is a profit function, achieved when the first stage decisionsare made with full information, and Π(I, z, d) is the profit achieved by thedecisions I and z that were implemented. X and Y are the sets of the con-straints associated with the first and second stages problems, respectively.2.4 Solution MethodologyRecently, it has been shown that C&CG algorithms, also known as row-and-column or scenario generation algorithms, are effective for solving two-stage robust optimization problems. The C&CG algorithm decomposes theproblem into a master problem and a second-stage (recourse) problem foreach scenario. It has demonstrated superior performance in various ap-plications compared to other algorithms. For instance, Zeng and Zhao(2013) demonstrated that the C&CG algorithm outperforms the Branch-and-Determine (BD) algorithm by an order of magnitude in solving a two-stage robust location-transportation problem with demand levels in a poly-hedral uncertainty set. Similarly, To¨nissen et al. (2019) showed that theC&CG algorithm outperforms both BD and multi-cut Benders decompo-sition (MCBD) by two orders of magnitude in solving a two-stage robustmaintenance site routing problem for rolling stock with discrete scenarios.Moreover, the C&CG algorithm has been successfully applied to solve avariety of other problems, including routing problems, network flow prob-lems, and facility location problems (Lei et al., 2016; Simchi-Levi et al., 2019;Chan et al., 2018). By decomposing the problem into a master problem anda recourse problem, the C&CG algorithm enables the iterative addition ofscenarios to the master problem, generating Benders optimality cuts us-ing the other scenarios. This iterative process allows for enhanced solutionquality and convergence towards optimality.In summary, the C&CG algorithm contributes significantly to the field oftwo-stage robust optimization by offering improved computational efficiencyand solution quality compared to other algorithms such as BD and MCBD.172.4. SOLUTION METHODOLOGYIts versatility and effectiveness have been demonstrated in various applica-tion domains, making it a valuable tool for solving complex decision-makingproblems under uncertainty.Recently, more studies applied the C&CG method to solve the two-stageRO problems. For example, Cheng et al. (2021b) implemented the C&CGmethod to solve the TRFTP under disruption risk. They used a budgetuncertainty set to formulate the risk of facilities disruption. To evaluatethe performance of the C&CG method, they proposed an approximationscheme and obtained results showed that the C&CG algorithm outperformsthe approximation method. Cheng et al. (2021a) contributed to their pre-vious studies by considering demand uncertainty (receiver side) in additionto facility disruption risk (provider side). They again applied the C&CGalgorithm to solve the proposed TRFTP problem. Considering in-betweenuncertainty is another improvement on two previous papers that have beenmade by Lu and Cheng (2021). In this study, the authors used a budgetuncertainty set to capture the interaction between the demand uncertaintyand faculties’ disruption risk. In addition to C&CG, they employed the BDmethod to solve the problem exactly.2.4.1 C&CG Algorithm for the RO ModelIn this section, Karush–Kuhn–Tucker (KKT) conditions are applied tothe Problem (2.2) to derive the subproblem, and the subproblem is linearizedusing big-M values, which are set via a dual problem of h(z, I). Finally, theC&CG algorithm is applied to solve the given problem.Based on the KKT condition, h(z, d) can be reformulated asminimizey,λ,γ∑i∑jηijyij (2.6a)subject to∑iyij ≤ dj , ∀ j , (2.6b)∑jyij ≤ zi , ∀ i , (2.6c)yij ≥ 0 , ∀ i , ∀ j , (2.6d)λj + γi ≥ ηij , ∀ i , ∀ j , (2.6e)λ ≥ 0 , γ ≥ 0 , (2.6f)(dj −∑iyij)λj = 0 , ∀ j , (2.6g)182.4. SOLUTION METHODOLOGYzi −∑jyij γi = 0 , ∀ i , (2.6h)(λj + γi − ηij) yij = 0 , ∀ i , ∀ j . (2.6i)where Constraints (2.6b-2.6f) hold the primal and dual feasibility con-ditions. Moreover, Equations (2.6g-2.6i) holds the complementary slacknessconditions.In the next step, Problem (2.6) can be linearized asminimizey,λ,γθ1 ,θ2 ,θ3∑i∑jηijyij (2.7a)subject to∑iyij ≤ dj , ∀ j , (2.7b)∑jyij ≤ zi , ∀ i , (2.7c)yij ≥ 0 , ∀ i , ∀ j , (2.7d)λj + γi ≥ ηij , ∀ i , ∀ j , (2.7e)λ ≥ 0 , γ ≥ 0 , (2.7f)dj −∑iyij ≤M1j (1− θ1j ) , ∀ j , (2.7g)λj ≤M2j θ1j , ∀ j , (2.7h)zi −∑jyij ≤M3j (1− θ2i ) , ∀ i , (2.7i)γi ≤M4j θ2i , ∀ i , (2.7j)λj + γi − ηij ≤M5j (1− θ3ij) , ∀ i , ∀ j , (2.7k)yij ≤M6j θ3ij , ∀ i , ∀ j , (2.7l)θ1 ∈ {0, 1}n , θ2 ∈ {0, 1}m , θ3 ∈ {0, 1}m×n . (2.7m)where variables θ1, θ1, and θ3 and big-M parameters are defined tolinearize the complementary slackness conditions.To set the value of big-M parameters, the dual of h(z, I) can be refor-mulated asminimizeλ,γ∑jdjλj +∑iziγi (2.8a)subject to λj + γi ≥ ηij , ∀ i , ∀ j , (2.8b)λ ≥ 0 , γ ≥ 0 . (2.8c)192.4. SOLUTION METHODOLOGYTherefore,dj −∑iyij <=M1j = d¯j + dˆj , ∀ j ,λj ≤M2j = maxi{ηij} , ∀ j ,zi −∑jyij ≤M3j =∑jd¯j + dˆj , ∀ j ,γi ≤M4j = maxj{ηij} , ∀ i ,λj + γi − ηij ≤M5j = maxi{ηij}+maxj{ηij} − ηij , ∀ i , ∀ j ,yij ≤M6j = d¯j + dˆj , ∀ i , ∀ j .Then, the RO problem can be reformulated asmaximizeI ,zc⊤z + f⊤I + g(I ,z) (2.9a)subject to z ≥ 0 , z ≤ MI , I ∈ {0, 1}m , (2.9b)where g(I ,z) is defined asmaxδ+ ,δ− ,y,λ,γ,θ1 ,θ2 ,θ3∑i∑jηijyij (2.10a)subject to∑iyij ≤ dj , ∀ j , (2.10b)∑jyij ≤ zi , ∀ i , (2.10c)yij ≥ 0 , ∀ i , ∀ j , (2.10d)λj + γi ≥ ηij , ∀ i , ∀ j , (2.10e)λ ≥ 0 , γ ≥ 0 , (2.10f)dj −∑iyij ≤M1(1− θ1j ) , ∀ j , (2.10g)λj ≤M2θ1j , ∀ j , (2.10h)zi −∑jyij ≤M3(1− θ2i ) , ∀ i , (2.10i)202.4. SOLUTION METHODOLOGYγi ≤M4θ2i , ∀ i , (2.10j)λj + γi − ηij ≤M5(1− θ3ij) , ∀ i , ∀ j , (2.10k)yij ≤M6θ3ij , ∀ i , ∀ j , (2.10l)0 ≤ δ+ , δ− ≤ 1 ,∑j(δ+j + δ−j ) ≤ Γ , (2.10m)θ1 ∈ {0, 1}n , θ2 ∈ {0, 1}m , θ3 ∈ {0, 1}m×n . (2.10n)The C&CG algorithm is specifically designed for solving two-stage ROproblems and is particularly advantageous for solving MIP problems with alarge number of variables and relatively few constraints, such as the HHClocation problem given in this study. Due to its effectiveness, the C&CGalgorithm has recently become a popular choice among researchers for solv-ing well-known optimization problems, such as the facility location problem(Lei et al., 2016), network flow problems (Simchi-Levi et al., 2019), andtransportation problem (Cheng et al., 2021b).212.4. SOLUTION METHODOLOGYAlgorithm 1: C&CG algorithm for RO model.Set UB ←∞ and LB ← −∞;Initialize with κ← 1;Let (δ˙+)(κ) ← 0n×1 and (δ˙−)(κ) ← 0n×1;while UB − LB ≤ ϵ doSolve the MP defined as follows:(MP-RO) maximizeI ,z,y,ρρ+ (c⊤z + f⊤I )subject to∑i∑jηijy(l)ij ≥ ρ , ∀ l ∈ {1, 2, . . . , κ} ,∑iy(l)ij ≤ d¯j + dˆj((δ˙j+)(l) − (δ˙j−)(l)),∀ j , ∀ l ∈ {1, 2, . . . , κ} ,∑jy(l)ij ≤ zi , ∀ i , ∀ l ∈ {1, 2, . . . , κ} ,y(l)ij ≥ 0 , ∀ i , ∀ j , ∀ l ∈ {1, 2, . . . , κ} ,z ≥ 0 , z ≤ MI , I ∈ {0, 1}m .Update LB ← ρ˙(κ) + (c⊤z˙(κ) + f⊤I˙ (κ)) where I˙ (κ), z˙(κ), andρ˙(κ) are the optimal values of the MP; Set κ← κ+ 1 and solvethe SP defined as follows:(SP-RO) maxI′ ,z′ ,y′ ,δ+ ,δ− ,y,λ,γ,θ1 ,θ2 ,θ3∑i∑jηijyijsubject to (2.10b)− (2.10n) .Set (δ˙+)(κ), (δ˙−)(κ) to their respective values based on theoptimal solution of the above SP ;Let ρ∗ be the optimal value of the above SP;Update UB ← min{UB, ρ∗ + (c⊤z˙(κ) + f⊤I˙(κ))};endreturn z˙(κ), I˙(κ)and ρ(κ) as the optimal solution.Algorithm 1 provides the detailed procedures of the C&CG algorithmfor the RO model. First, the initial values of location decisions z and I are222.4. SOLUTION METHODOLOGYset to zero. By doing so, the initial solution for the master problem (MP)cannot be infeasible since all constraints would be satisfied. Next, the MP issolved to obtain optimal locations and capacities of facilities and pass themto the sub-problem. The lower bound is also updated in this step. Then, thesub-problem (SP) is solved with given z and I to find the worst-case scenarioand the optimal value of the SP is used to update the upper bound. Thealgorithm stops if the stopping criterion is met. Otherwise, the determinedworst-case scenario and its associated variables and constraints are addedto the MP.2.4.2 C&CG Algorithm for the RM ModelAll steps of applying the C&CG method for the RO model are taken inthis section for the RM model. Therefore, the RM problem can be reformu-lated asminimizeI ,zc⊤z + f⊤I + g(I ,z) (2.11a)subject to z ≥ 0 , z ≤ MI , I ∈ {0, 1}m , (2.11b)where g(I ,z) is defined asmaxI′ ,z′ ,y′ ,δ+ ,δ− ,y,λ,γ,θ1 ,θ2 ,θ3∑i∑jηij(y′ij − yij)− (c⊤z′ + f⊤I ′) (2.12a)subject to∑iyij ≤ dj , ∀ j , (2.12b)∑jyij ≤ zi , ∀ i , (2.12c)yij ≥ 0 , ∀ i , ∀ j , (2.12d)λj + γi ≥ ηij , ∀ i , ∀ j , (2.12e)λ ≥ 0 , γ ≥ 0 , (2.12f)dj −∑iyij ≤M1(1− θ1j ) , ∀ j , (2.12g)λj ≤M2θ1j , ∀ j , (2.12h)zi −∑jyij ≤M3(1− θ2i ) , ∀ i , (2.12i)232.4. SOLUTION METHODOLOGYγi ≤M4θ2i , ∀ i , (2.12j)λj + γi − ηij ≤M5(1− θ3ij) , ∀ i , ∀ j , (2.12k)yij ≤M6θ3ij , ∀ i , ∀ j , (2.12l)∑iy′ij ≤ d¯j + (δ+j − δ−j )dˆj , ∀ j , (2.12m)∑jy′ij ≤ z′i , ∀ i , (2.12n)y′ij ≥ 0 , ∀ i , ∀ j , (2.12o)z′ ≥ 0 , z′ ≤ MI ′ , I ′ ∈ {0, 1}m , (2.12p)0 ≤ δ+ , δ− ≤ 1 ,∑j(δ+j + δ−j ) ≤ Γ , (2.12q)θ1 ∈ {0, 1}n , θ2 ∈ {0, 1}m , θ3 ∈ {0, 1}m×n . (2.12r)Algorithm 2 presents the steps of the C&CG algorithm for the RMmodel.242.4. SOLUTION METHODOLOGYAlgorithm 2: C&CG algorithm for RM model.Set UB ←∞ and LB ← −∞;Initialize with κ← 1;Let (δ˙+)(κ) ← 0n×1, (δ˙−)(κ) ← 0n×1, (z′)(κ) ← 0m×1, (I ′)(κ) ← 0m×1and (y′)(κ) ← 0(nz ·nd)×1;while UB − LB ≤ ϵ do(MP-RM) minimizeI ,z,y,ρρ+ (c⊤z + f⊤I )subject to∑i∑jηij(y′(l)ij − y(l)ij )−∑iciz′(l)i + fiI′(l)i ≤ ρ ,∀ l ∈ {1, 2, . . . , κ} ,∑iy(l)ij ≤ d¯j + dˆj((δ˙j+)(l) − (δ˙j−)(l)),∀ j , ∀ l ∈ {1, 2, . . . , κ} ,∑jy(l)ij ≤ zi , ∀ i , ∀ l ∈ {1, 2, . . . , κ} ,y(l)ij ≥ 0 , ∀ i , ∀ j , ∀ l ∈ {1, 2, . . . , κ} ,z ≥ 0 , z ≤ MI , I ∈ {0, 1}m .Update LB ← ρ˙(κ) + (c⊤z˙(κ) + f⊤I˙ (κ)) where I˙ (κ), z˙(κ), and ρ˙(κ)are the optimal values of the MP;Set κ← κ+ 1 and solve the SP defined as follows:(SP-RM) maxI′ ,z′ ,y′ ,δ+ ,δ− ,y,λ,γ,θ1 ,θ2 ,θ3∑i∑jηij(y′ij − yij)− (c⊤z′ + f⊤I ′)subject to (2.12b)− (2.12r) .Set (δ˙+)(κ), (δ˙−)(κ), (z′)(κ), (I ′)(κ) and (y′)(κ) take on the valuesof the optimal solution of the above SP;Let ρ∗ be the optimal value of the above SP model;Update UB ← min{UB, ρ∗ + (c⊤z˙(κ) + f⊤I˙(κ))};endreturn z˙(κ), I˙(κ)and ρ(κ) as the optimal solution.252.5. NUMERICAL RESULTS2.5 Numerical ResultsIn this section, test instances are randomly generated to compare theperformance of RO and RM models in terms of computational time andsolution quality. Moreover, the impact of uncertainty on the performance ofthe two models is analyzed. Then, a small-sized instance is implemented toanalyze the topology of solutions produced by RO and RM models. Finally,managerial implications by analyzing the impact of uncertainty on objectivefunctions and decisions are offered to assist HHC managers in selecting asuitable policy.2.5.1 Experimental SetupWe set the number of potential locations to open an HHC facility to 10and demand nodes to 20 and generated 100 test instances for the problem.The parameter setting is the same as that of Ardestani-Jaafari and Delage(2021). Table 2.2 shows the procedure used to generate the parameters’values for each instance. The fixed cost of opening HHCs and variable costsof employing caregivers are uniformly generated for each HHC facility. Inthe same way, marginal revenue related to allocating caregivers to patientsand nominal demand of each demand node is generated. Five uncertaintybudgets (Γ) and three levels of maximum deviation of demand (ε) are definedto evaluate the impact of uncertainty on the performance of RO and RMmodels. For each level, all test instances are implemented. Therefore, thereare 100 × 5 × 3 test instances in total. Both algorithms, considering theoptimality tolerance of 10−3 are implemented in MATLAB R2021a usingthe YALMIP toolbox and Gurobi 9.5.0 as the solver.Table 2.2: Parameters used for generating instances.Parameter Description Valuef Fixed cost of opening a HHC [0,50000]c Variable cost of opening a HHC [0,0.6]η Marginal revenue [1.5,2.5]d¯ Nominal demand [0,20000]dˆ Maximum demand deviation εd¯Γ Budget of uncertainty {0n, 0.1n, 0.3n, 0.5n, n}ε Maximum deviation ratio {0.15,0.30,0.45}I ∈ Rm is a binary variable indicating whether an HHC facility is opened262.5. NUMERICAL RESULTSat location i. Decision variable z ∈ Rm denotes the caregivers in HHC facilityi. y ∈ Rm×n denotes the number of caregivers travelled from HHC facility ito demand node j. Parameter dj is a demand of node j, and ηij > 0 denotesthe unit revenue assigning caregivers of HHC facility i to demand node j.It should be mentioned that the travelling time is considered in revenue aswell. Indeed, the ηij decreases as the travel distance increases because as thetravel time increases, the cost of providing the care services also increases.Moreover, ci and fi denote the variable and fixed capacity costs for HHCfacility i. The following MIP model is the formulation of a deterministicHHC location problem withm and n locations of HHC facilities and demandnodes, respectively:2.5.2 Computational AnalysisIn this section, we evaluate the performance of the proposed algorithmfor RO and RM models in medium-sized and large-sized instances.Results for Medium-sized InstancesTo computationally evaluate the algorithms’ performance, the problem’ssize is increased to 30 potential locations for HHC facilities and 60 demandnodes. Then the mean of computational time on ten randomly generatedinstances is measured. Table 2.3 presents the computational time of ROand RM models for different levels of uncertainty. The table reports thecomputational metrics for RO and RM, which include the total computa-tional time, the computational time of solving MP and SP, and the numberof iterations. The average computational time for the RO and RM modelsis 147.03 and 579.02 seconds. These results indicate that the RM modelis more complex and requires more computation time than the RO model.However, by reformulating the RM model into an RO model and apply-ing the C&CG algorithm, the RM model is made into a polynomial-timealgorithm.The results also show that as ε increases, the computational time andnumber of iterations for both models also increase. For instance, this is evi-dent when Γ = 50% of the total number of demand nodes, where increasingε from 0.15 to 0.30 causes an average increase of 6.34 and 41.42 secondsin computational time for RO and RM respectively. Solving the problembecomes more difficult when Γ = 50% of n, as δ+ ≥ 0 and δ− ≥ 0 must bothsum up to less than or equal to the uncertainty budget (δ++δ− ≤ 1). Thereare(nΓ)possible combinations for the values of δ+ and δ− , with the highest272.5. NUMERICAL RESULTSnumber of combinations occurring when Γ = n/2, indicating that the levelof uncertainty is at 50% of n. The number of iterations also increases asthe level of uncertainty rises and reaches its maximum at Γ = 50% of n.Furthermore, in the RO model, the average time needed to solve SP andMP is 70.55 and 76.48 seconds, respectively, whereas it takes 192.09 and386.92 seconds to solve these problems in the RM model. This implies thatsolving MP necessitates more time than resolving SP, primarily due to thelarger number of second-stage constraints present in the models.Table 2.3: Average computational time (in seconds) and the number ofiterations for medium-sized instances.ε ΓRO RMTotal MP SP # Iter Total MP SP # Iter0.15 0% 14.44 6.91 7.52 1.00 32.88 11.17 21.70 2.0010% 119.85 56.89 62.95 6.47 322.84 105.27 217.56 6.9130% 69.75 31.25 38.49 20.12 818.29 285.99 532.29 21.4450% 77.20 33.75 43.44 28.32 891.74 1319.44 572.29 27.94100% 65.61 30.41 35.19 8.10 710.93 237.55 473.37 10.480.3 0% 15.90 7.65 8.24 1.00 33.25 10.65 22.59 2.0010% 125.96 59.43 66.52 9.98 325.76 104.81 220.94 410.5730% 76.52 34.19 42.32 28.42 850.09 291.94 558.14 29.4550% 83.54 36.03 47.50 50.02 933.66 337.41 596.24 45.81100% 47.41 21.86 25.54 6.09 771.56 259.13 512.42 8.450.45 0% 19.31 9.80 9.50 1.00 50.40 14.73 35.66 2.0010% 370.87 186.01 184.85 11.43 326.41 97.02 229.38 11.1430% 377.37 183.36 194.00 29.38 866.15 267.72 598.42 31.2650% 480.44 229.40 251.03 54.50 927.97 294.27 633.69 53.07100% 261.39 131.33 130.05 7.49 823.45 244.32 579.12 9.00Avg 147.03 70.55 76.48 17.78 579.02 192.09 386.92 18.65Results for Large-sized InstancesIn this section, we test larger-sized instances to assess the efficiency of theC&CG algorithm. To do this, we modified the instances to include 40 poten-tial locations for opening HHC facilities and 80 demand nodes. In practicalapplications, HHC decision-makers require a feasible computational time tosolve HHC problems. Therefore, we set a maximum computational timelimit of one hour for each model to meet this requirement. Table 2.4 reportsthe average computational time and optimality gap. The results indicate282.5. NUMERICAL RESULTSthat the computational time for the RO and RM models significantly in-creases as the number of potential locations and demand nodes increases.While in some cases, solving the RM model results in an unacceptable com-putational time, in most instances, the model is solved in a reasonable time.The RO and RM models have an average computational time of 527.49 and2474.99 seconds, respectively. This confirms that the RM model is morecomputationally complex than the RO model. Additionally, the RO modelhas an average optimality gap of 0%, indicating that all instances are solvedwithin one hour. On the other hand, the RM model has an average optimal-ity gap of 2.76%, demonstrating the computational efficiency of the C&CGalgorithm and the reformulation of the RM model.Table 2.4: Average computational time (in seconds) and optimality gap (in%) for large-sized instances.ε ΓRO RMCPU time Gap CPU time Gap0.15 0% 57.47 0.00 141.05 0.0010% 424.26 0.00 1291.36 0.0030% 274.11 0.00 3584.11 1.0850% 277.14 0.00 — 5.36100% 261.78 0.00 2993.01 0.000.3 0% 48.97 0.00 146.96 0.0010% 496.28 0.00 1381.22 0.0030% 266.28 0.00 — 2.0650% 332.48 0.00 — 10.67100% 186.79 0.00 3232.83 0.000.45 0% 77.24 0.00 209.16 0.0010% 1145.98 0.00 1331.73 0.0030% 1313.24 0.00 3577.20 1.3350% 1743.99 0.00 — 12.54100% 1006.35 0.00 — 8.41Avg 527.49 0.00 2474.99 2.76Note. — denotes that the model cannot find the finalsolution within one hour.292.5. NUMERICAL RESULTS2.5.3 Comparison of Robust and Regret PoliciesIn this subsection, both models’ impact of Γ and ε on the quality ofsolutions, worst-case profit and regret, and first-stage decision variables areanalyzed. The performance of RO and RM models under different levels ofuncertainty are also compared.Suboptimality Gap AnalysisThe quality of solutions produced by the RM and RO models are com-pared to see whether it values to solve the RM model with more complexity.For this purpose, the relative suboptimality gap is measured for each model.The suboptimality gap is the relative difference between optimal worst-caseand worst-case profit associated with reoptimizing the given problem byoptimal facility location decisions of the regret model. Similarly, the ROgap equals the difference between optimal worst-case absolute regret andworst-case absolute regret achieved when implementing the RO decisions.Simply speaking, it measures the relative difference between optimal worst-case and worst-case performance for the RM and RO models, where a largergap indicates a larger deviation from optimal performance.For different levels of uncertainty, the average suboptimality gap of ROand RM models is reported in Table 2.5. According to this table, it can beconcluded that there are apparent dissimilarities between the concepts of thetwo models. First, implementing the location decisions produced by RO forthe RM model significantly increases, 31%, 39%, and 46%, the average of theworst-case absolute regret performance for different values of ε. Conversely,relying on RM decisions result in a slight decrease in the worst-case profit by0.83%, 2%, and 4%. It should be noted that, as expected, the suboptimalitygap is equal to zero when the deterministic equivalent problem (Γ = 0% ofn) is solved. Moreover, the gap increases for both models as the Γ and theε increase. However, the increase is slightly more in the RM than in the ROmodel.302.5. NUMERICAL RESULTSTable 2.5: Average suboptimality gap (in %) of RO and RM models.ε ModelBudget of Uncertainty (in % of n)Average10 30 50 1000.15 RO 12.78 22.57 32.36 56.82 31.13RM 0.24 0.65 1.00 1.43 0.830.3 RO 20.67 30.46 40.25 64.72 39.03RM 0.51 1.47 2.43 3.83 2.060.45 RO 28.57 38.35 48.14 72.61 46.92RM 0.77 2.54 4.66 8.10 4.02Overall, it is clear that the RO model produces decisions that may con-tradict what leads to low absolute regret. For instance, RO decisions arewell known to boost worst-case profits while ignoring all likely opportunitiesto create larger profits, which might cause significant regret in the future.However, RM decisions will take a less conservative approach, attemptingto be well-positioned to take advantage of chances while forgoing the assur-ance of a bigger possible worst-case profit. It suggests that RO decisionsmay prioritize short-term profit maximization at the cost of potential regretin the future. On the other hand, RM decisions may take a less conservativeapproach, aiming to capitalize on potential opportunities while acceptingthe risk of lower worst-case profit.Worst-case Profit and Regret AnalysisThe impact of Γ and ε on worst-case profit and regret are studied. Theresults are presented in Figures 2.2 and 2.3 and show that the objectivefunctions are getting worse for both models by increasing the level of uncer-tainty. This means as the Γ increases, the worst-case profit decreases andthe worst-case absolute regret increases. Furthermore, these figures showthat worst-case profit decreases as the ε increases. On the other hand, theworst-case absolute regret increases by increasing this ratio. The differencein the behaviour of the RO and RM models can be explained by their ap-proaches to managing uncertainty. In the RO model, the worst-case profitis optimized by conservatively assuming a low-demand scenario. Therefore,increasing the level of uncertainty reduces the number of caregivers assigned,leading to a decrease in profit. On the other hand, the RM model aims tominimize the gap between the optimal worst-case profit and the worst-caseprofit. Thus, the number of caregivers assigned increases as the level of un-312.5. NUMERICAL RESULTScertainty increases to reduce this gap, resulting in an increase in profit. Insummary, it can be concluded increasing the uncertainty negatively affectsthe objective functions of RO and RM models.0 10 30 50 100Level of uncertainty (%)22.22.42.62.833.23.43.63.84Worst-case profit105=0.15=0.3=0.45Figure 2.2: Impact of uncertainty budget on the worst-case profit.0 10 30 50 100Level of uncertainty (%)00.20.40.60.811.21.41.61.8Worst-case relative regret104=0.15=0.3=0.45Figure 2.3: Impact of uncertainty budget on worst-case absolute regret.Decisions AnalysisThe impact Γ on first-stage decision variables for both models is studied.Specifically, we calculate the average number of HHC facilities opened and322.5. NUMERICAL RESULTSthe total capacity of these facilities across 100 generated instances, at variouslevels of ε.Table 2.6 reveals that Γ has a negligible effect on the average numberof opened HHC facilities in both models. However, the declining trendobserved in the RO model is more pronounced. For example, for ε = 0.45, byincreasing the Γ from 30% to 100% of n, the number of opened HHC facilitiesdecreases by 0.28 on average. One possible reason for this behaviour is thatas the level of uncertainty increases, the model becomes more conservativeand opens fewer HHC facilities to ensure that worst-case profit is achieved.Moreover, a slight impact on the number of opened HHC facilities in bothmodels can be observed with an increase in the value of ϵ. For example, forΓ = 30% of n, by increasing the ε from 0.15 to 0.3, the number of openedHHC facilities decreases by 0.03 and is constant for RO and RM respectively.Thus, it can be concluded that this variable is not significantly affected bythe level of uncertainty.Table 2.6: Mean number of opened HHC facilities.ε ModelBudget of Uncertainty (in % of n)0 10 30 50 1000.15 RO 2.20 2.21 2.19 2.18 2.10RM 2.20 2.20 2.18 2.17 2.170.3 RO 2.20 2.20 2.16 2.08 1.99RM 2.20 2.19 2.18 2.18 2.180.45 RO 2.20 2.20 2.11 1.99 1.83RM 2.20 2.20 2.16 2.19 2.18Looking at Figure 2.4, one can notice that increasing the uncertaintybudget affects the number of caregivers in RO and RM models in two op-posite ways. Indeed, the HHC facilities employ fewer caregivers as demanduncertainty increases in the RO model. On the other hand, the numberof caregivers increases as the uncertainty budget increases in RM. The ROmodel optimizes the worst-case scenario of profit when demand is low. Theidea behind this model is to be conservative when it comes to the worst-casescenario, so the model typically assumes that demand is lower than its ex-pected value, resulting in a smaller number of assigned caregivers. Therefore,by increasing the level of uncertainty, the number of caregivers decreases tobe conservative about worst-case profit. This is while in the RM model, thenumber of caregivers increases as the level of uncertainty increases to reduce332.5. NUMERICAL RESULTSthe gap between optimal worst-case profit and worst-case profit. This allowsfor a more flexible approach to demand uncertainty management, where themodel can adapt to changing conditions by assigning more caregivers asneeded to meet the expected demand.This discrepancy in the behaviour of the two models highlights the dif-ferences between the concepts of RO and RM and suggests that the ROmodel tends to be more conservative in its decision-making. The RO modelprioritizes mitigating the risk of low-demand scenarios, while the RM modelfocuses on reducing the potential profit loss in worst-case scenarios. Theseinsights provide valuable implications for decision-makers in managing HHCfacilities under different levels of uncertainty.342.5. NUMERICAL RESULTS0 10 30 50 100Level of uncertainty (%)1.822.22.42.62.83Number of caregivers107 (a) =0.15RORM0 10 30 50 100Level of uncertainty (%)1.21.41.61.822.22.42.62.83Number of caregivers107 (b) =0.3RORM0 10 30 50 100Level of Uncertainty (%)1.21.41.61.822.22.42.62.83Number of caregivers107 (c) =0.45RORMFigure 2.4: Impact of uncertainty budget on the number of caregivers.352.5. NUMERICAL RESULTS2.5.4 Operational ImplicationsThe topology of solutions produced by RO and RM models and howthey differ from nominal solutions are studied. For this purpose, the num-ber of HHC facilities opened, the number of caregivers employed, and theconnectivity of the nodes for a small-sized randomly generated instance arecompared. The network is comprised of 10 potential locations for openingthe HHC facilities and 15 demand nodes. These randomly generated nodesrepresent the demand nodes and potential HHC facility locations. The nom-inal demand at each demand node and fixed costs of opening an HHC aredrawn from the uniform distributions, U [0, 200] and U [0, 1000]. We let theε = 0.3 and η = 0.6.Figure 2.5 presents the underlying network of the nominal model. Inthis figure, a star represents an open HHC facility, and the size of the star isproportional to the number of caregivers at that HHC facility. The numberbehind each star shows the number of caregivers working in that HHC fa-cility. Each circle denotes a demand node, each of which is connected to anHHC facility with a line. According to this figure, seven HHC facilities servethe 15 demand nodes. The HHC facilities with larger capacity supply thedemand of 9 nodes, and the other one supplies what demand nodes remain.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1X coordinate00.10.20.30.40.50.60.70.80.91Y coordinate1333431116515491344595934Figure 2.5: Illustration of the solution for the generated instance underdeterministic environment.Figure 2.6 represents the underlying network of the solutions producedby RO and RM models when the Γ = 10% of n. Looking at this figure, onecan observe that the topology of the network of both models is precisely362.5. NUMERICAL RESULTSsimilar but differ from the nominal model. Indeed, both RO and RM mod-els open five HHC facilities in the same locations, which is less than thenominal model opens. Moreover, the connection of the supply and demandnodes is the same. However, the number of caregivers working at each HHCfacility is different. Compared to the nominal model, the RO model opensHHC facilities with fewer caregivers. On the other hand, the RM modelestablished two HHC facilities with a larger number of caregivers than thenominal and RO models.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1X coordinate00.10.20.30.40.50.60.70.80.91Y coordinate(a) RO23091834688 5291350 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1X coordinate00.10.20.30.40.50.60.70.80.91Y coordinate(b) RM32992617982755192Figure 2.6: Illustration of the solution for the generated instance when Γ =0.1n.Figure 2.7 presents the network topology of solutions produced by ROand RM models when Γ = 100% of n. Looking at the figure, one can no-372.5. NUMERICAL RESULTStice that both models open fewer HHC facilities as the level of uncertaintyincreases. In the RO model, the number of caregivers in HHC facilitiesdecreases as the uncertainty level increases. Conversely, the RM model pro-duced a solution in which the number of caregivers working in HHC facilitiesis larger than the solution with Γ = 10% of n. Furthermore, the underly-ing network of the RO and RM models has been changed by increasing theuncertainty level while they are similar to each other at each level.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1X coordinate00.10.20.30.40.50.60.70.80.91Y coordinate(a) RO744 3205962 11240 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1X coordinate00.10.20.30.40.50.60.70.80.91Y coordinate(b) RM1063 4571 13731608Figure 2.7: Illustration of the solution for the generated instance when Γ =n.The results reconfirm that the quality of solutions produced by the RMmodel is better than those of the RO model. That is, the RO model sacrificesthe solutions with higher profit for those more conservative. On the other382.5. NUMERICAL RESULTShand, the RM model increases the profit by decreasing the gap betweenoptimal profit and worst-case profit by increasing the number of caregivers ateach facility. Furthermore, the number of caregivers is significantly changedby increasing the uncertainty budget. It can also be concluded that an HHCfacility can supply the demand in a region further away that has a higherdemand and a higher revenue per visit, which may make it more profitableto provide services in that region despite the longer travel time. All in all,these examples support the ideas in the literature that the RM is a lessconservative model than the RO model.2.5.5 Concluding RemarksThe comparison of gaps between RM and ROmodels can provide insightsinto the trade-offs between worst-case regret and worst-case profit. Thedecision on which model to use depends on the specific goals and constraintsof the problem at hand, as well as the risk tolerance of the decision-maker.The results also presented show that even though there is a declining trendin the RO model, the impact of Γ on the average number of opened HHCfacilities is relatively small in both models. Additionally, the impact of ϵ onthe number of opened HHC facilities in both models is also slight. Therefore,decision-makers can be reassured that the level of uncertainty, representedby Γ, has a negligible effect on the average number of opened HHC facilitiesin both models.Furthermore, as the RO model tends to be more conservative in itsdecision-making, the number of caregivers decreases this model as the Γincreases. On the other hand, the RM model tends to focus on reducingthe potential profit loss in worst-case scenarios. Therefore, the number ofcaregivers increases in the RM model as the Γ increases. This means thatmanagers can use these models to make informed decisions on the optimalnumber of HHC facilities to open, without worrying too much about theimpact of uncertainty.These insights have important implications for decision-makers manag-ing HHC facilities under different levels of uncertainty. If minimizing regretis a top priority, then the RM model may be preferred despite potentiallylower worst-case profit. However, if short-term profit maximization is themain concern, then the RO model may be preferred, even though it mayresult in higher regret in uncertain situations. In other words, if the goal isto minimize the risk of low-demand scenarios, then the RO model may bemore appropriate. However, if the focus is on reducing potential profit lossin worst-case scenarios, then the RM model may be more suitable.39Chapter 3Operating Room PlanningProblemThis chapter describes our second study, which investigates the applica-tion of RM to deal with surgery duration uncertainty in an OR planningproblem.3.1 IntroductionThe utilization of operating rooms (ORs) is a crucial aspect of hospitaladministration and financial stability. Studies have shown that ORs con-stitute a significant portion of hospitals’ operating costs and revenue, withestimates ranging from 20-40% of operating costs (Viapiano andWard, 2000)and 40-70% of hospitals’ income (Freeman et al., 2016). Furthermore, a sub-stantial number of hospital admissions involve surgical procedures. Efficientplanning of these procedures helps hospitals utilize their resources, such asORs, surgeons, and nurses, efficiently, leading to an increase in revenue. Forinstance, according to the Healthcare Financial Management Association,medium-sized hospitals may earn an additional annual income of $4-7 mil-lion by performing one more surgery per day in the OR (Fu¨gener et al.,2017).Although ORs are vital in providing healthcare services, many health-care systems struggle to make optimal use of these resources. This challengeis especially prevalent in Canada, where ORs typically operate at only 70%of their capacity (Roshanaei et al., 2020), while the optimal utilization rateranges between 85-90% (Tyler et al., 2003). Additionally, the uncertaintythat accompanies surgical operations further exacerbates the underutiliza-tion of ORs. Therefore, it is crucial to implement effective OR managementstrategies that prioritize scheduling and resource allocation to improve ORs’utilization.OR planning involves the design, organization, and scheduling of ORsin hospitals or surgical centers. The primary objective of OR planning is to403.1. INTRODUCTIONoptimize the utilization of resources, including staff, equipment, and space,to ensure the efficient and safe performance of surgeries. OR planning is anoptimization problem that involves determining the optimal number of ORsto open, allocating surgeries to ORs, and sequencing surgeries to minimizeoperational and overtime costs while maximizing OR utilization (Zhu et al.,2019). However, one of the most significant challenges in addressing thisproblem is the inherent uncertainty of surgical operations, which makesresource allocation a difficult task. This uncertainty poses several challenges,such as scheduling conflicts, patient anxiety, and staffing issues, for both thepatient and the OR units.The duration of surgery is a significant source of uncertainty in surgi-cal operations. This is due to various factors, such as the complexity ofthe procedure, the patient’s medical history and health status, unforeseencomplications during the surgery, and the proficiency and expertise of thesurgeon and surgical team. According to Samudra et al. (2016), the broadrange of surgery duration poses a considerable challenge in scheduling ORseffectively since it is difficult to predict the duration of a particular surgery.Ignoring these uncertainties can result in inefficient use of ORs and addi-tional costs for overtime staffing.The study of OR planning problems is typically carried out in a de-terministic framework, where the input data and parameters are known inadvance. To model and solve these problems under uncertainty, two commonapproaches are SP and RO (Cardoen et al., 2010). Although SP and ROmethods are tractable, they often generate over-conservative solutions anddo not consider non-extreme scenarios (Ng, 2013). Specifically, being overlyconservative in OR planning decisions can result in decreased utilization ofsurgical units, hindering the treatment of a larger group of patients andincreasing waiting times and surgical operating costs. Furthermore, conser-vative planning can increase the risk of delays and cancellations, negativelyimpacting the patient’s quality of care and satisfaction. However, findingthe right balance between conservatism and tractability can be challengingbecause they have a direct relationship, where a decrease in conservatismleads to a decrease in tractability.RM is a decision-making framework that aims to minimize the differencebetween the best possible and the actual outcomes of a decision, known asregret. In many optimization problems, such as the OR planning problem,MIP formulations are frequently used to find optimal solutions. However,in these situations, decision-makers often have to make long-term decisionsbefore the values of uncertain parameters are revealed. RM is particularlyuseful in these types of problems because it allows the decision-maker to413.1. INTRODUCTIONmake the best possible decision given the limited information available atthe time of the first-stage decision, and to minimize regret after the uncertainparameters are revealed. By using RM, decision-makers can make better-informed decisions considering the likelihood of different scenarios and theirpotential consequences. This approach can help increase the flexibility ofOR planning decisions, leading to more efficient utilization of resources andimproved patient outcomes.In the literature, it has been observed that RM generates less conser-vative solutions than those obtained from SP and RO methods (see e.g.,Mausser and Laguna, 1999; Natarajan et al., 2014; Caldentey et al., 2017).This is because RM focuses on minimizing regret, which is the differencebetween the performance of the chosen solution and the optimal solutionover a period of time. This allows for the possibility of initially taking asuboptimal decision with the aim of compensating for it later. In contrast,RO aims to identify a solution that performs well across a worst-case sce-nario, which can lead to restrictive and suboptimal solutions. However,the computational complexity of implementing RM is hindered by it beingNP-hard (Averbakh and Lebedev, 2005). On the other hand, RO and SPformulations are computationally tractable in a linear program (Poursoltaniand Delage, 2022). To address this challenge, several exact and approximatemethods have been developed. Nonetheless, to the best of our knowledge,no studies have yet employed RM and developed a solution method to tacklethe uncertainty and complexity of the OR planning problem.In this study, we develop an RM model to address uncertainty in surgeryduration in the OR planning problem. We reformulate the RM model toan RO model and develop a C&CG algorithm to handle the computationalcomplexity. We evaluate the effectiveness of this approach through an ex-tensive set of numerical experiments, comparing the performance of robustand regret policies.This study aims to answer the following questions:(i) Does the reformulation and application of the C&CG algorithm ef-fectively mitigate the computational complexity of the RM model?(Section 3.5.1)(ii) Has the implementation of the RM model resulted in a significantimprovement in the quality of solutions, particularly in terms of con-servatism? (Section 3.5.2)(iii) What is the impact of uncertainty in surgery duration on managingcosts and decision-making in ORs? (Sections 3.5.2 and 3.5.2)423.2. LITERATURE REVIEW(iv) What are the implications of the uncertainties mentioned above formanaging costs and decision-making in ORs? (Section 3.5.3)The rest of this chapter is structured as follows. In Section 3.2, we reviewrelevant literature to identify research gaps and address them accordingly.Section 3.3 introduces the RO and RM models for the OR planning problem.Subsequently, Section 3.4 develops an exact solution approach to solve theproblem. In Section 3.5, we compare the computational time and solutionquality of the RO and RM models.3.2 Literature ReviewThe OR planning problem has been extensively studied from variousmethodological perspectives and aspects (see, eg Cardoen et al., 2010; Zhuet al., 2019; Wang et al., 2021). One critical aspect that has received signifi-cant attention is uncertainty. This term refers to the parameters that are notknown beforehand but affects the decision-making process in the OR. Theseuncertainties result in delays, additional costs, and lower utilization due topatient cancellations, emergency events, and unexpected surgical complica-tions. Other uncertainties taken into account by researchers include patientarrival (see, e.g., Rachuba and Werners, 2017; Kroer et al., 2018), resourceavailability (see, e.g., Vancroonenburg et al., 2015; Hashemi Doulabi et al.,2016), and patient care needs (see, e.g., Holte and Mannino, 2013; Kim andMehrotra, 2015). Studies have shown that surgery duration uncertainty hasa significant impact on the decision-making process in OR planning (Zhuet al., 2019).The optimization of OR planning problems under uncertainty is tackledthrough two commonly used approaches: SP and RO. The SP approach isemployed when the probability distribution of unknown parameters is well-defined, as seen in previous studies (see e.g., Lamiri et al., 2009; Shylo et al.,2013; Batun et al., 2011; Shehadeh et al., 2019). However, limited availabledata can pose challenges for OR managers in making decisions, as noted inDenton et al. (2007) and Macario (2010).RO, which generally addresses uncertainty through a limited understand-ing of the distribution, has become a well-established approach in OR plan-ning problems. Its computational efficiency makes it a preferred choice overSP, especially in cases where data is scarce or the distributions are unknown.Denton et al. (2010) introduced an RO method for handling the uncertaintyof surgery duration in an OR planning problem, and their results indicatedthat the RO method is significantly faster computationally than the SP433.2. LITERATURE REVIEWmethod on average and enhances performance in worst-case scenarios. Sub-sequently, several studies have applied the RO method to address surgeryduration uncertainty (see e.g., Holte and Mannino, 2013; Neyshabouri andBerg, 2017; Breuer et al., 2020; Shehadeh, 2022).As discussed in Thiele (2010), over-conservatism can be problematic inthe RO approach, particularly when the uncertainty set is polyhedral witha budget uncertainty constraint. RM, as an alternative, does not solelyprotect the decision-maker against the worst-case scenario but balances theconservatism level and the quality of solutions. This property makes itparticularly suitable for dynamic and quickly changing environments, suchas OR planning problems. By applying RM to an OR planning problem,OR managers can minimize resource utilization by making decisions thatoptimize the utilization of the OR while maintaining sufficient flexibility toaccommodate the uncertainty of surgery duration. Despite the challenge offinding a polynomial-time solution method for RM models, they have gainedattention for their ability to solve various optimization problems, such asthe newsvendor problem (Perakis and Roels, 2008) and lot sizing (Zhang,2011). However, there has been a lack of research on RM applications toOR planning problems.Assavapokee et al. (2008b) proposed an iterative algorithm called thescenario relaxation algorithm for two-stage absolute and relative RM prob-lems with min-max criteria and scenario-based uncertainty. They addresseda decision-making problem in which the first-stage problem is a MIP modelwith binary variables, and the second-stage problem is a linear programming(LP) model. The authors proved that their solution method converges toan optimal solution within a finite number of iterations if it exists. Subse-quently, Assavapokee et al. (2008a) applied the scenario relaxation algorithmto a two-stage decision-making problem under interval-based uncertainty(i.e., a box uncertainty set) with uncertainty on the RHS of constraints.They solved the second-stage problem using two MIP reformulations, gen-erating feasibility and optimality cuts. Jiang et al. (2013), and Chen et al.(2014) also applied the scenario relaxation algorithm to a two-stage RMproblem with polyhedral uncertainty.Ng (2013) extended the work of Assavapokee et al. (2008a) by consideringlinear programs in which uncertainty affects the objective function in addi-tion to the RHS. The author developed a conservative approximation of theregret function in the form of a two-stage RO problem. The proposed solu-tion scheme was based on iterative relaxation and a cut-generation approach.More recently, Ning and You (2018) reformulated a two-stage RM modelwith polyhedral uncertainty as a two-stage RO model to take advantage of443.3. PROBLEM DEFINITION AND FORMULATIONits tractability. They proposed a cutting-plane and column-generation algo-rithm to solve large-scale problems. Poursoltani and Delage (2022) extendedthe work of Ning and You (2018) by further generalizing the reformulationto include relative regret or problems with objective uncertainty.Our research aims to address two major challenges in the existing liter-ature. First, we develop a method to handle the surgical duration uncer-tainty to improve the solutions that are not over-conservative. Second, weaim to reformulate the RM model as RO and develop a traceability solutionmethod. To the best of our knowledge, there has been no study using RMin OR planning problems. In addition, not many studies have proposed anexact solution method to solve large-scale instances. Our study makes aninitial contribution to the OR planning literature by:(i) A proposed OR planning problem addresses the uncertainty of surgeryduration with the aim of determining the number of ORs to open andthe allocation of surgeries.(ii) This study contributes to OR planning literature by formulating ROand RM models under uncertainty, providing more flexible solutionswith less conservative results compared to previous studies.(iii) The RM model is reformulated as an RO model, and a C&CG algo-rithm is introduced to handle computational difficulties and enable thesolving of large-scale instances of the OR planning problem.(iv) A comprehensive set of numerical experiments is carried out to gaininsight into the RO and RM model, evaluating its performance intractability and conservatism.3.3 Problem Definition and FormulationThis section presents a deterministic mathematical model for the ORplanning problem, along with its RO and RM formulations.3.3.1 Deterministic ModelThe proposed OR planning problem involves making decisions regardingthe number of ORs to open and allocating surgeries to these ORs with theobjective of minimizing costs related to OR opening and overtime. Thesedecisions are interdependent since having fewer open ORs tends to increaseovertime costs, as fitting procedures within the limited available OR time453.3. PROBLEM DEFINITION AND FORMULATIONbecomes more challenging. Conversely, having more open ORs reduces over-time costs but at the expense of having more ORs open. According to Den-ton et al. (2010), it is assumed that the ORs are homogeneous since mostequipment can be easily transferred between them. Additionally, it is as-sumed that the cost of overtime per unit is lower than the fixed cost ofopening an OR. Without this assumption, the optimal decision would beto allocate all surgeries to a single OR, as the cost of overtime per unit oftime would be lower than opening an OR. Furthermore, it is assumed thatthe duration of each surgery is shorter than the planned session length foreach OR, implying that each surgery can be completed within the regularoperating hours of an OR.The OR planning problem can be formulated as a deterministic opti-mization problem, where i and j are the indices for surgeries and ORs,respectively. The binary variable x ∈ Rm represents the opening status ofOR j, and y ∈ Rm×n represents the allocation of surgery i to OR j. Theovertime of OR j is represented by o ∈ Rm. The fixed cost of opening anOR is cf , and the variable cost per unit of time for keeping an OR openpast time T is denoted by cν . The duration of surgery i is denoted by ζi.The deterministic problem can be defined asminimizex,y,ocf∑jxj + cν∑ioj (3.1a)subject to yij ≤ xj , ∀ i , ∀ j , (3.1b)∑iyij = 1 , ∀ j , (3.1c)oj ≥∑iζiyij − Txj , ∀ j , (3.1d)x ∈ {0, 1}m , y ∈ {0, 1}n×m , (3.1e)o ≥ 0 . (3.1f)The objective function (3.1a) minimizes the fixed costs of opening ORsand the variable penalty costs of overtime. Constraint (3.1b) guarantees thatsurgeries can only be performed in opened ORs. Constraint (3.1c) ensuresthat each surgery is allocated to an OR. Constraint (3.1d) calculates theovertime of OR j. Constraints (3.1e) and (3.1f) ensure that the decisionvariables are binary and non-negative.Since each OR has the same planned session length, the ORs exhibit com-plete symmetry. As a result, any solution can be obtained by interchangingthe sets of surgeries assigned to any two ORs, leading to an increase in463.3. PROBLEM DEFINITION AND FORMULATIONcomputational time. This results in m! equivalent solutions to the deter-ministic problem based on permutations of surgeries for each given plannedallocation. To address this symmetry, Denton et al. (2010) proposed a setof constraints listed in Proposition 3.1.Proposition 3.1 (See Denton et al. (2010)). The following symmetry-breaking constraints are applied to the OR problem under a realistic assump-tion of n > m.xj ≥ xj+1 , ∀ j ∈ {1, 2, ...,m− 1} . (3.2)yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j . (3.3)min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j . (3.4)3.3.2 Robust FormulationProblem (3.1) operates within a deterministic framework and assumesthat the surgery duration is already known at the time of decision-making.However, the decisions to open ORs and allocate surgeries must be madebefore the surgery duration is revealed. Failing to consider this aspect cannegatively impact the system’s performance by disregarding worst-case sce-narios. As a well-known optimization method, RO often employs eitherminimax or maximin criteria to optimize the system’s performance in theworst possible scenario. These criteria ensure that the system can handleand respond effectively to any potential negative outcomes or adverse con-ditions. Due to their practical applicability, these criteria have been widelyapplied to optimization problems under uncertainties, such as network de-sign problems (Akbarpour et al., 2020), facility location problems (Basciftciet al., 2021), and vehicle routing problems (Ghosal and Wiesemann, 2020).Accordingly, the robust counterpart of the OR problem with a minimaxobjective under the uncertainty of surgery duration can be formulated as:minimizex,ymaxζ∈Ucf∑jxj + h(x, y, ζ) (3.5a)subject to yij ≤ xj , ∀ i , ∀ j , (3.5b)∑iyij = 1 , ∀ j , (3.5c)473.3. PROBLEM DEFINITION AND FORMULATIONxj ≥ xj+1 , ∀ j ∈ {1, 2, ...,m− 1} , (3.5d)yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.5e)min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.5f)x ∈ {0, 1}m , y ∈ {0, 1}n×m , (3.5g)where h(x, y, ζ) is the second stage problem, and is defined as follows:h(x, y, ζ) := minocν∑joj (3.6a)subject to oj ≥∑jζjyij − Txj , ∀ j , (3.6b)o ≥ 0 . (3.6c)The surgery duration lies in uncertainty set U that is defined asU :={ζ ∈ Rn : ζi = ζ¯i + (δ+i − δ−i )ζˆi, δ+ ≥ 0, δ− ≥ 0 , δ+ + δ− ≤ 1 ,∑i(δ+i + δ−i ) ≤ Γ},where ζ¯ and ζˆ are the nominal surgery duration and the maximum de-viation from the nominal surgery duration. Moreover, δ+ and δ− are non-negative variables indicating surgery duration’s perturbation. Finally, Γ in-dicates the budget of uncertainty introduced by Bertsimas and Sim (2004)and is extensively used to control the level of robustness.3.3.3 Regret FormulationProblem (3.5) aims to find the OR planning decisions that minimize thesystem’s cost over the worst-case scenario. This approach is often consideredmore conservative as it focuses solely on minimizing the negative outcomesof a decision. While this can minimize potential risks for decision-makers,it may also lead to overly conservative decisions that can adversely affectthe utilization of ORs. On the other hand, the worst-case absolute RM, asdescribed in Savage (1951), evaluates the performance of a decision x byconsidering the ”worst-case regret” that may be experienced in the futurewhen x is compared to the best possible decision that could have been made.As discussed, the RM model can produce less conservative solutions.483.3. PROBLEM DEFINITION AND FORMULATIONLet minΠ(x′, y′, ζ) be the minimum cost that can be achieved throughfirst-stage decisions made with complete information and Π(x, y, ζ) be theactual cost associated with the decisions x and y after the realization of ζ.To determine the worst-case regret, the difference between the actual andoptimal costs is maximized within the uncertainty set U . The optimizationof worst-case absolute regret is achieved over x and y asminimizex,ymaxζ∈Uminx′,y′Π(x, y, ζ)−Π(x′, y′, ζ), (3.7)where Π(x, y, ζ) = cf∑j xj+h(x, y, ζ), and Π(x′, y′, ζ) = cf∑j x′j+h(x′, y′, ζ).Proposition 3.2. Problem (3.7) can be reformulated asminimizex,ymaxζ∈U ,(x′ ,y′)∈X ,o′∈Y(ζ ,x′ ,y′)cf∑jxj + h(x, y, ζ)+ cf∑jx′j − cν∑jo′j (3.8a)where X and Y are the feasible regions related to the first and second stages’decision variables and defined asX :={(x, y) ∈ Rm × Rn×m : yij ≤ xj , ∀ i , ∀ j ,∑iyij = 1 , ∀ j , x ∈ {0, 1}m , y ∈ {0, 1}n×m},Y(ζ, x, y) :={Y ∈ Rm : oj ≥∑iζizij − Txj , ∀ j , o ≥ 0}.Proof. The minimization problem can be transformed into a maximiza-tion problem by multiplying it by −1. As a result, −minΠ(x′, y′, ζ) isequivalent to maxΠ(x′, y′, ζ). This transformation can be expressed asmax(cf∑j x′j + h(x′, y′, ζ)), where h(x′, y′, ζ) represents min cν∑j o′j overo′. Similarly, min cν∑j o′j can be re-framed as max−cν∑j o′j . Finally, bycombining the maximization of Π(x′, y′, ζ) and o′, we obtain the objectivefunction (3.8a).Based on Proposition 3.2, the RM model is equivalent to the followingminimax RO model:minimizex,ymaxζ∈U ,(x′ ,y′)∈X ,o′∈Y(ζ ,x′ ,y′)cf∑jxj + h(x, y, ζ)+ cf∑jx′j − cν∑jo′j (3.9a)493.4. SOLUTION METHODOLOGYsubject to yij ≤ xj , ∀ i , ∀ j , (3.9b)∑iyij = 1 , ∀ j , (3.9c)xj ≥ xj+1 , ∀ j ∈ {1, 2, ...,m− 1} , (3.9d)yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.9e)min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.9f)x ∈ {0, 1}m , y ∈ {0, 1}n×m . (3.9g)Table 3.1 presents the size of the RO and RM models in terms of thenumber of variables and constraints. It can be observed that the numberof binary variables in the OR planning problem is larger than the numberof continuous variables, making it more challenging to solve. The numberof first-stage constraints in the RO model may be greater or less than thesecond-stage constraints, depending on the number of ORs (m) and surgeries(n). In contrast, the number of second-stage constraints in the RM modelis significantly larger than the first-stage constraints. As a result, solvingthe second-stage model is expected to be more time-consuming than thefirst-stage model. Furthermore, the RM model has more constraints thanthe RO model, highlighting its computational complexity.Table 3.1: Number of variables and constraints of RO and RM models.RO RM# Binary variables 3m+mn 4m+ 2mn# Continuous variables 2m+ 2n 3m+ 2n# First-stage constraints 3mn+m+ n−m(m+ 1) 3mn+m+ n−m(m+ 1)# Second-stage constraints 6m+ 2 mn+ 6m+ 2n+ 13.4 Solution MethodologyThe C&CG algorithm, developed by Zeng and Zhao (2013), is a decom-position based approach designed specifically for two-stage RO problems.This algorithm is particularly useful for solving MIP problems that involvea large number of variables and relatively few constraints, such as the ORplanning problem at hand. Thus, the C&CG algorithm has recently gained503.4. SOLUTION METHODOLOGYattention from researchers to solve well-known optimization problems, suchas the facility location problem (Lei et al., 2016), network flow problems(Simchi-Levi et al., 2019), and transportation problem (Cheng et al., 2021b).In this study, we apply the C&CG algorithm to the RO and RM models pre-sented in Problems (3.5) and (3.9).3.4.1 C&CG Algorithm for the RO ModelFirst, we reformulate the problem (3.5) using the following proposition:Proposition 3.3. Problem (3.5) is equivalent tominimizex,y, ρρ+ cf∑jxj (3.10a)subject to ρ ≥ g(x,y, ζ) , (3.10b)yij ≤ xj , ∀ i , ∀ j , (3.10c)∑iyij = 1 , ∀ j , (3.10d)xj ≥ xj+1 , ∀ j ∈ {1, 2, ...,m− 1} , (3.10e)yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.10f)min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.10g)x ∈ {0, 1}m , y ∈ {0, 1}n×m , (3.10h)where g(x,y, ζ) is defined asmaxo,δ+ ,δ− ,λ,θ1 ,θ2cν∑joj (3.11a)subject to oj ≥∑i(ζ¯i + (δ+i − δ−i )ζˆi)yij − Txj , ∀ j , (3.11b)λj ≤ cν , ∀ j , (3.11c)λ ≥ 0 , o ≥ 0 , (3.11d)oj −∑i(ζ¯i + (δ+i − δ−i )ζˆi)yij + Txj ≤M1j (1− θ1i ) ,∀ j , (3.11e)513.4. SOLUTION METHODOLOGYλj ≤M2j θ1j , ∀ j , (3.11f)λj − cν ≤M3j (1− θ2j ) , ∀ j , (3.11g)oj ≤M4j θ2j , ∀ j , (3.11h)0 ≤ δ+ + δ− ≤ 1 ,∑i(δ+i + δ−i ) ≤ Γ , (3.11i)θ1 , θ2 ∈ {0, 1}m . (3.11j)Proof. Appendix A.1Remark 3.4. To set the appropriate value of big-M parameters, the knowl-edge of the upper bound on dual and primal variables is used. Therefore,the value of big-M parameters are set as follows:oj −∑i(ζ¯i + (δ+i − δ−i )ζˆj)yij + Txj ≤M1j =∑i(ζ¯i + ζˆi)+ T , ∀ j ,λj ≤M2j = cν , ∀ j ,λj − cν ≤M3j = cν , ∀ j ,oj ≤M4j =∑i(ζ¯i + (δ+i − δ−i )ζˆi), ∀ j .Then, we develop the C&CG algorithm for the RO model, formulatedin Problem (3.5). Algorithm 3 outlines the detailed procedures of this al-gorithm. In the initialization step, the initial values of the opening andallocation decisions x and y are set to zero, as the problem is completelyrecourse based on Lemma A.1. This means that the initial solution for theMP cannot be infeasible, as all constraints would be satisfied. Therefore,it is not required to add any feasibility cuts, as in the C&CG algorithmdeveloped by Zeng and Zhao (2013). In the second step, the MP is solved toobtain optimal decisions for OR openings and surgery allocation facilities.These decisions are then passed to the subproblem, and the lower bound isupdated. The SP is solved with the given x and y to find the worst-casescenario, and the optimal value of the SP is used to update the upper bound.The algorithm stops if the stopping criterion is met (UB − LB ≤ ϵ). Oth-erwise, the determined worst-case scenario and its associated variables andconstraints are added to the MP. The algorithm iteratively repeats thesesteps until convergence.523.4. SOLUTION METHODOLOGYAlgorithm 3: C&CG algorithm for RO model.Set UB ←∞ and LB ← −∞;Initialize with κ← 1;Let (δ˙+)(κ) ← 0n×1 and (δ˙−)(κ) ← 0n×1;while UB − LB ≤ ϵ doSolve the MP defined as follows:(MP-RO) minimizex,y,o,ρρ+ cf∑ixjsubject to cν∑jo(l)j ≤ ρ , ∀ l ∈ {1, 2, . . . , κ} ,o(l)j ≥∑i(ζ¯i +((δ˙i+)(l) − (δ˙i−)(l))ζˆi)yij − Txj ,∀ j , ∀ l ∈ {1, 2, . . . , κ} ,o(l)j ≥ 0 , ∀ j , ∀ l ∈ {1, 2, . . . , κ} ,yij ≤ xj , ∀ i , ∀ j ,∑iyij = 1 , ∀ j ,xj ≥ xj+1 , ∀ i ∈ {1, 2, ...,m− 1} ,yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j ,min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j ,x ∈ {0, 1}m , y ∈ {0, 1}n×m .Update LB ← ρ˙(κ) + cf∑j x˙j(κ) where x˙(κ) and ρ˙(κ) are theoptimal values of the MP; Set κ← κ+ 1 and solve the SPdefined as follows:(SP-RO) maxζ ,o,λ,δ+ ,δ− ,θ1 ,θ2cν∑jojsubject to (3.11b)− (3.11j) .Set (δ˙+)(κ), (δ˙−)(κ) to their respective values based on theoptimal solution of the above SP ;Let ρ∗ be the optimal value of the above SP;Update UB ← min{UB, ρ∗ + cf∑j x˙j(κ))};endreturn x˙(κ), y˙(κ) and ρ(κ) as the optimal solution.533.4. SOLUTION METHODOLOGY3.4.2 C&CG Algorithm for the RM ModelUsing the same procedure as before, the RM model represented by Prob-lem (3.9) can be reformulated asProposition 3.5. Problem (3.9) is equivalent tominimizex,y, ρρ+ cf∑ixi (3.12a)subject to ρ ≥ g(x,y, ζ) , (3.12b)yij ≤ xj , ∀ i , ∀ j , (3.12c)∑iyij = 1 , ∀ j , (3.12d)xj ≥ xj+1 , ∀ j ∈ {1, 2, ...,m− 1} , (3.12e)yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.12f)min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j , (3.12g)x ∈ {0, 1}m , y ∈ {0, 1}n×m . (3.12h)where g(x,y, ζ) is defined asmaxx′ ,y′ ,o′ ,δ+ ,δ− ,ζ ,o,λ,θ1 ,θ2cν∑i(oj − o′j) + cf∑ix′j (3.13a)subject to oj ≥∑i(ζ¯i + (δ+i − δ−i )ζˆi)yij − Txj , ∀ j , (3.13b)λj ≤ cν , ∀ j , (3.13c)λ ≥ 0 , o ≥ 0 , (3.13d)oj −∑i(ζ¯i + (δ+i − δ−i )ζˆi)yij + Txj ≤M1j (1− θ1j ) ,∀ j , (3.13e)λj ≤M2j θ1j , ∀ j , (3.13f)d− λj ≤M3j (1− θ2j ) , ∀ j , (3.13g)oj ≤M4j θ2j , ∀ j , (3.13h)o′j ≥∑i(ζ¯i + (δ+i − δ−i )ζˆi)y′ij − Tx′j , ∀ j , (3.13i)543.4. SOLUTION METHODOLOGYo′ ≥ 0 , (3.13j)y′ij ≤ x′j , ∀ i , ∀ j , (3.13k)∑iy′ij = 1 , ∀ j , (3.13l)x′ ∈ {0, 1}m , y′ ∈ {0, 1}n×m , (3.13m)0 ≤ δ+ + δ− ≤ 1 ,∑i(δ+i + δ−i ) ≤ Γ , (3.13n)θ1 , θ2 ∈ {0, 1}m . (3.13o)Algorithm 4 presents the steps of the C&CG algorithm for the RMmodel.553.4. SOLUTION METHODOLOGYAlgorithm 4: C&CG algorithm for RM model.Set UB ←∞ and LB ← −∞;Initialize with κ← 1;Let κ = 1 and set (δ˙+)(κ) = (δ˙−)(κ) = 0n×1. (x′)(κ) = 0m×1,(y′)(κ) = 0(m·n)×1 and (o′)(κ) = 0m×1;while UB − LB ≤ ϵ do(MP-RM) minimizex,y,o,ρρ+ cf∑ixisubject to cν∑j(o(l)j − o′(l)j ) + c∑jx′(l)j ≤ ρ ,∀ l ∈ {1, 2, . . . , κ} ,o(l)j ≥∑j(ζ¯i +((δ˙i+)(l) − (δ˙i−)(l))ζˆi)yij − Txj ,∀ i , ∀ l ∈ {1, 2, . . . , κ} ,o(l)j ≥ 0 , ∀ j , ∀ l ∈ {1, 2, . . . , κ} ,yij ≤ xj , ∀ i , ∀ j ,∑iyij = 1 , ∀ j ,xj ≥ xj+1 , ∀ i ∈ {1, 2, ...,m− 1} ,yij ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j ,min{i,m}∑u=jyiu ≤i−1∑r=j−1yr,j−1 , ∀(i, j) : i ≥ j ,x ∈ {0, 1}m , y ∈ {0, 1}n×m .Update LB ← ρ˙(κ) + cf∑j x˙j(κ) where x˙(κ) and ρ˙(κ) are theoptimal values of the MP;Set κ← κ+ 1 and solve the SP defined as follows:(SP-RM) maxx′ ,y′ ,o′ ,δ+ ,δ− ,ζ ,o,λ,θ1 ,θ2cν∑j(oj − o′j) + cf∑jx′jsubject to (3.13b)− (3.13o) .Set (δ˙+)(κ), (δ˙−)(κ), (x′)(κ), (y′)(κ) and (o′)(κ) take on the valuesof the optimal solution of the above SP;Let ρ∗ be the optimal value of the above SP model;Update UB ← min{UB, ρ∗ + cf∑j x˙j(κ))};endreturn x˙(κ), y˙(κ) and ρ(κ) as the optimal solution.563.5. NUMERICAL RESULTS3.5 Numerical ResultsIn this section, our focus is on comparing the performance of RO andRM models, while also exploring how uncertainty affects their performance.The following are our main goals:(i) Section 3.5.1 compares the computational time required to solve theRO and RM models, assessing the complexity of the models and eval-uating the efficiency of the C&CG algorithm.(ii) Section 3.5.2 presents a comparison of the performance of the mod-els. We will evaluate the optimality gap, the impact of uncertaintyon worst-case cost and absolute regret, as well as the OR planningdecisions.(iii) Finally, Section 3.5.3 offers managerial implications by analyzing theimpact of uncertainty on objective functions and decisions, aiming toassist OR managers in selecting a suitable policy.We set the number of ORs to 7 and surgeries to 15 and generated 100test instances for the problem. Five uncertainty budgets (Γ) and threelevels of maximum deviation of nominal surgery duration (ε) are definedto evaluate the impact of uncertainty on the performance of RO and RMmodels. The parameter setting is the same as that of Denton et al. (2010).Two values for the overtime cost per unit: cν = 0.0083, which represents twohours of overtime being equivalent to opening a new OR, and cν = 0.0333,representing 30 minutes of overtime being equivalent to opening a new OR,are considered. The planned session length for each OR is set to 480 minutes,and the fixed cost is cf = 1. The YALMIP toolbox and Gurobi 9.5.0 solverwere utilized in MATLAB R2021a to implement the algorithms, with atolerance for optimality set to 10−3.3.5.1 Computational AnalysisTables 3.2 and 3.3 report the computational results obtained from solv-ing the RO and RM models under varying levels of uncertainty that aver-aged over 100 randomly generated test instances. The tables present thecomputational metrics for MP and SP, the total computational time andthe number of iterations. The average computational time of the RO modelwith cν = 0.0333 and cν = 0.0083 is 8.96 and 26.83 seconds while for the RMmodel, these are 15.45 and 52.50 seconds. The findings demonstrate that573.5. NUMERICAL RESULTSthe RM model is more computationally demanding than the RO model,implying that RM models have greater inherent complexity. However, byconverting the RM model into an RO model and utilizing the C&CG algo-rithm, the RM model can be transformed into a polynomial-time algorithm.Table 3.2: Average computational time (in seconds) and the number ofiterations of RO and RM models with cν = 0.0333.ε ΓRO RMTotal MP SP # Iter Total MP SP # Iter0.15 0% 0.48 0.25 0.23 1.00 1.56 0.53 1.03 2.0010% 1.58 0.83 0.75 3.13 2.76 0.90 1.86 3.3930% 5.20 2.87 2.33 9.45 9.07 3.17 5.90 10.6750% 6.93 3.90 3.03 12.55 11.25 4.03 7.22 13.18100% 1.92 1.03 0.89 3.84 4.07 1.36 2.71 5.040.3 0% 1.08 0.56 0.52 1.00 3.59 1.15 2.44 2.0010% 6.04 3.19 2.85 4.69 9.51 3.06 6.45 4.7430% 15.91 8.80 7.11 13.22 27.40 9.41 17.99 14.3750% 28.40 16.15 12.25 22.74 45.63 16.49 29.14 22.46100% 3.86 2.08 1.78 2.99 7.92 2.66 5.26 3.660.45 0% 1.32 0.65 0.67 1.00 4.48 1.31 3.17 2.0010% 6.42 3.20 3.22 5.37 10.90 3.24 7.66 5.1630% 18.81 9.67 9.14 13.42 33.42 10.33 23.09 14.9650% 32.42 16.94 15.48 24.01 52.00 16.49 35.51 24.30100% 4.06 2.02 2.04 3.39 8.19 2.43 5.76 4.35Avg 8.96 4.81 4.15 8.11 15.45 5.10 10.34 8.81Regarding the impact of uncertainty, Tables 3.2 and 3.3 illustrate thatboth models’ computational time and the number of iterations increase asthe nominal surgery duration’s deviation ratio rises on average. For example,when Γ = 50% of the number of surgeries, increasing ε from 0.15 to 0.30increases the computational time by 21.47 and 34.38 seconds for RO andRM on average. Moreover, the problem becomes increasingly challengingto solve and takes the maximum computational time when Γ = 50% ofn. This is because the variables δ+ ≥ 0 and δ− ≥ 0 must sum up to lessthan or equal to the uncertainty budget (δ+ + δ− ≤ 1). There are (nΓ)potential combinations for the values of δ+ and δ− . The greatest numberof combinations is obtained when Γ = n/2, indicating that the degree ofuncertainty is at 50% of n. Likewise, the number of iterations rises as the583.5. NUMERICAL RESULTSlevel of uncertainty grows, and it peaks at Γ = 50%.In addition, when cν equals 0.0333 and 0.0083, the average time requiredto solve SP and MP is 4.81 and 4.15 seconds, respectively. Moreover, whencν equals 0.0083, it takes 17.14 and 5.35 seconds to solve the same problemsin the RO model. This indicates that in the RO model, solving the MP re-quires more time compared to solving the SP, mainly because of the greaterquantity of second-stage constraints. On the other hand, the solution timesfor the SP and MP in the RM model with cν = 0.0083 are 5.10 and 10.34 sec-onds, and with cν = 0.0333 are 15.59 and 36.91 seconds, respectively. Theseresults illustrate that the SP is more computationally intricate than the MPin the RM model, mainly because of the higher number of constraints.Table 3.3: Average computational time (in seconds) and the number ofiterations of RO and RM models with cν = 0.0083.ε ΓRO RMTotal MP SP # Iter Total MP SP # Iter0.15 0% 1.95 0.58 1.00 1.00 6.64 1.94 4.70 2.0010% 6.36 3.42 3.21 3.16 12.04 3.53 8.51 3.5830% 29.41 22.98 14.28 14.01 52.22 16.08 36.14 15.1050% 68.26 32.91 17.46 17.02 60.37 18.77 41.60 17.01100% 7.89 1.65 3.95 3.89 16.53 4.88 11.65 4.840.3 0% 1.16 0.95 0.58 1.00 4.09 1.20 2.89 2.0010% 6.73 3.15 3.31 5.03 11.27 3.33 7.94 5.0130% 41.31 15.13 18.33 21.89 69.89 23.86 46.03 23.2250% 57.62 50.80 24.71 36.57 92.22 32.70 59.52 36.43100% 3.29 3.94 1.64 2.03 5.59 1.65 3.94 2.690.45 0% 3.33 1.61 1.72 1.00 11.65 3.29 8.36 2.0010% 17.46 8.62 8.84 5.51 29.55 8.46 21.09 5.5430% 77.93 39.70 38.23 30.58 139.30 41.75 97.55 32.3050% 131.67 67.93 63.74 42.56 260.32 67.94 192.38 43.37100% 7.82 3.81 3.99 2.85 15.83 4.49 11.34 2.81Avg 26.83 17.14 5.35 12.55 52.50 15.59 36.91 13.12Finally, when overtime costs are decreased, it substantially increasesthe computational complexity for both models. To be precise, decreasingovertime costs causes the average computation time for the RO and RMmodels to increase by 17.87 and 37.05 seconds, respectively. This shows thatfinding the optimal solution becomes more challenging when there are fewer593.5. NUMERICAL RESULTSORs, and reducing overtime costs is equivalent to expanding the feasiblesolution space by opening a new OR, making the optimal solution moredifficult to find. Conversely, if overtime is more expensive, it would besimpler to decide to open more ORs.3.5.2 Comparison of Robust and Regret PoliciesIn this section, we explore how the quality of solutions, objective func-tions, and decision variables are affected by the uncertainty budget andmaximum deviation ratio.Optimality Gap AnalysisTo determine whether solving the RM model with more complexity isbeneficial, the solutions generated by the RM and RO models are compared.This comparison involves calculating the relative suboptimality gap for eachmodel as a percentage. The suboptimality gap is the difference betweenthe optimal worst-case cost and the cost resulting from reoptimizing theOR planning problem using the regret model’s optimal first-stage decisions(i.e., opening ORs and allocating surgeries). Likewise, the RO gap is thedifference between the optimal worst-case absolute regret and the regretresulting from implementing the RO decisions.Table 2.5 reports the average suboptimality gap for the RO and RMmodels under varying levels of uncertainty where Scenarios 1 and 2 repre-sent cν = 0.0333 and cν = 0.0083, respectively. Based on this table, theaverage suboptimality for the RO model in Scenarios 1 and 2 is 6.43% and3.65% while for the RM model, are 1.28% and 1.10%. The results highlightthe fundamental differences between the two models. Using the first-stagedecisions generated by RO for the RM significantly worsens the worst-caseabsolute regret performance on average. Conversely, implementing the first-stage decisions of RM for RO results in only a slight increase in the worst-case cost. It is crucial to note that for all ε the suboptimality gap is zerowhen solving the deterministic equivalent problem (Γ = 0% of n). More-over, as the uncertainty budget increases, the gap increases for both models,reaching its maximum when the uncertainty budget is equal to 50% of n.When the problem becomes less complex at a 100% of n, the suboptimalitygap significantly decreases and, at some point, becomes nearly zero. Thisindicates that both models perform similarly under less complex conditions.603.5. NUMERICAL RESULTSTable 3.4: Average suboptimality gap (in %) of RO and RM models.ε ΓRO RMScenario 1 Scenario 2 Scenario 1 Scenario 20.15 10% 11.74 7.24 0.00 0.3230% 5.06 1.14 0.38 0.0150% 8.13 5.85 0.42 1.00100% 0.00 0.01 0.00 0.000.3 10% 9.00 5.83 0.00 0.5330% 3.19 3.14 0.96 0.9850% 5.25 5.38 1.35 4.16100% 0.00 0.00 0.00 0.000.45 10% 15.16 2.84 0.00 0.0030% 7.25 5.62 5.02 1.7950% 12.44 6.84 7.32 4.48100% 0.00 0.02 0.00 0.00Avg 6.43 3.65 1.28 1.10Worst-case Costs and Regret AnalysisIn this section, we analyze the impact of uncertainty budget and maxi-mum deviation ratio on the worst-case cost and worst-case absolute regret.As shown in Table 3.5, both models experience a decline in their objectivefunctions as the level of uncertainty increases. This indicates that increasingthe Γ leads to higher worst-case costs and worst-case absolute regret. Specif-ically, when the Γ is increased from 10% to 100% of n, the worst-case costincreases by [5% − 10%] and [5% − 12%] for high and low overtime costs,respectively. For worst-case absolute regret, it increases by [13% − 20%]and [8%− 27%] for Scenarios 1 and 2, respectively. Additionally, the studyfound that increasing the ε results in higher worst-case costs and worst-caseabsolute regret. For example, for Scenario 1 with Γ = 50% of n, when theε is increased from 0.15 to 0.45, the worst-case cost and absolute regret in-crease by 12% and 29%. Finally, it can be observed that reducing overtimeleads to lower worst-case costs and worst-case absolute regret. In particu-lar, when cν = 0.0083, the average worst-case cost and worst-case absoluteregret decrease by 3% and 6%.613.5. NUMERICAL RESULTSTable 3.5: Average worst-case cost and absolute regret.ε ΓRO RMScenario 1 Scenario 2 Scenario 1 Scenario 20.15 0% 2.97 2.92 0.00 0.0010% 8.08 7.98 3.08 2.9830% 8.49 8.20 3.49 3.2050% 8.54 8.31 3.54 3.31100% 8.57 8.47 3.57 3.470.3 0% 2.97 2.92 0.00 0.0010% 8.36 8.11 3.36 3.1130% 9.10 8.75 4.10 3.7550% 9.15 8.89 4.15 3.89100% 9.19 9.03 4.19 4.030.45 0% 2.97 2.92 0.00 0.0010% 8.56 8.23 3.56 3.2330% 9.53 9.13 4.53 4.1350% 9.58 9.31 4.58 4.31100% 9.59 9.44 4.59 4.44Avg 7.71 7.50 3.11 2.92Decisions AnalysisTable 3.6 presents the average overtime for the RO and RM models.According to this table, the average overtime of the RO model for Scenario1 is 2.62 and 26.79 minutes and these for the RM model are 2.60 and 23.55minutes. It shows that, on average, the RM model incurs less overtimecompared to the RO model, which can be explained by the fundamentaldifferences between the two models. The RO model aims to optimize theproblem under the worst-case uncertainty Scenario of surgery duration, thatis the Scenario with worst-case cost. Therefore, this approach leads to moreconservative decisions and a lower risk of suboptimal solutions but higherovertime costs. In contrast, the RM model aims to minimize the maximumregret or the difference between the actual and optimal solution, leadingto less conservative OR opening and surgery allocation decisions, whichbalances the risk of suboptimal solutions with the benefit of reducing theaverage overtime. Thus, the lower overtime costs in the RM model can beattributed to its less conservative approach. Furthermore, upon comparingScenarios 1 and 2, it can be concluded that the reduction of overtime costs623.5. NUMERICAL RESULTSby 0.025 increases the average overtime by 24.50 and 21.07 minutes for ROand RM models.With regard to the effect of uncertainty, the results reported in Table 3.6show that increasing the ε increases the average of overtime. For example,for Scenario 2 with Γ = 50% of n, increasing ε from 0.15 to 0.30 increasesthe average overtime by 25.36 and 23.71 minutes for RO and RM. Moreover,for Scenario 2 with ε = 0.3, by increasing the Γ from 30% to 50% of n,the average overtime increases by 20.13 and 18.16 minutes, reaching theirmaximums, for RO and RM models. However, after the 50%n budget, asubstantial decline in overtime can be observed.Table 3.6: Overtime of RO and RM models (in minutes).ε ΓRO RMScenario 1 Scenario 2 Scenario 1 Scenario 20.15 0% 0.21 8.75 0.21 8.7510% 1.78 10.09 1.71 9.0130% 2.97 29.92 2.96 24.8450% 4.05 30.39 4.01 26.12100% 0.72 15.81 0.64 13.980.3 0% 0.21 8.75 0.21 8.7510% 4.55 19.69 4.53 16.5630% 4.15 35.62 4.11 31.6750% 5.11 55.75 5.11 49.83100% 1.75 14.53 1.72 12.660.45 0% 0.21 8.75 0.21 8.7510% 3.58 32.75 3.52 27.9430% 3.03 43.45 3.01 36.8150% 5.06 70.07 5.06 60.27100% 2.03 19.66 2.01 17.42Avg 2.62 26.79 2.60 23.55The average number of opened ORs for RO and RM models are reportedin Table 3.7. According to this table, the mean number of opened ORs inthe RM model is slightly less than in the RO model. For Scenario 1, theaverage number of opened ORs in RO and RM models is 5.63 and 5.60,and these are 5.29 in the RO model and 5.28 in the RM model for Scenario2. Furthermore, increasing the level of uncertainty generally increases themean number of opened ORs for both RO and RM models. For instance, in633.5. NUMERICAL RESULTSScenario 1 with Γ = 50% of n and ε = 0.3, the mean number of opened ORsis 6.06 for the RO model and 6.04 for the RM model, while for the sameScenario and ε with Γ = 100% of n those are 6.13. Looking at these tables,one can also observe that reducing the overtime costs leads to opening fewerORs because opening more ORs to undergo all surgeries puts more cost intothe system compared to overtime penalty cost.Table 3.7: Mean number of opened ORs.ε ΓRO RMScenario 1 Scenario 2 Scenario 1 Scenario 20.15 0% 4.96 4.85 4.96 4.8510% 5.02 4.90 4.98 4.8730% 5.36 4.96 5.30 4.9550% 5.44 5.06 5.40 5.06100% 5.55 5.34 5.55 5.320.3 0% 4.96 4.85 4.96 4.8510% 5.21 4.95 5.20 4.9530% 6.00 5.32 5.91 5.3050% 6.06 5.60 6.04 5.60100% 6.13 5.91 6.13 5.910.45 0% 4.96 4.85 4.96 4.8510% 5.44 4.96 5.40 4.9530% 6.37 5.59 6.31 5.5650% 6.49 5.97 6.45 5.94100% 6.52 6.28 6.52 6.25Avg 5.63 5.29 5.60 5.283.5.3 Concluding RemarksThis section provides insights to OR decision-makers by further analyz-ing the impact of uncertainty on objective functions and decisions. Addi-tionally, it offers a comparison between the RO and RM models to assistOR managers in selecting the appropriate uncertainty approach.To determine if OR planners can improve their operations with moreprecise surgery duration estimations, the effect of estimation errors on worst-case costs is being examined. To accomplish this, the impact of ε on worst-case costs is being analyzed from a different perspective. Figures 3.1 and3.2 illustrate the effect of estimation errors on managing costs in the OR643.5. NUMERICAL RESULTSby showcasing the maximum deviation of nominal surgery duration for Sce-narios 1 and 2, respectively. By analyzing the worst-case cost range among100 test instances for different levels of Γ and ε, we observe that higherestimation error leads to greater costs and deviations for all uncertaintybudget levels. Therefore, it is crucial to improve the accuracy of surgeryduration estimation, as the difference between accurate and inaccurate es-timation is significant. OR managers can reduce costs by investing in moreaccurate estimation methods. Additionally, reducing overtime costs couldbe a viable alternative to investing in estimation, as it mitigates the impactof estimation errors, as evidenced by the results obtained.10 30 50 100Level of uncertainty (%)7.58.08.59.09.510.010.5Worst-case costꜪ0.150.30.Ꜫ5Figure 3.1: Impact of uncertainty level on worst-case cost in Scenario 1.Furthermore, results show that reducing overtime costs leads to the cre-ation of an OR plan that includes a higher level of overtime, which alignswith what was expected. The increase in overtime is likely due to the factthat lowering the cost of overtime makes it more financially feasible to sched-ule additional surgeries beyond regular working hours. However, it is impor-tant to note that increases over time can have negative impacts on OR staff,such as fatigue and burnout, and it can also lead to higher costs associatedwith staffing and equipment maintenance. Therefore, OR managers must653.5. NUMERICAL RESULTScarefully weigh the potential benefits of reducing overtime costs against thepotential drawbacks of increased overtime before making a decision.10 30 50 100Level of uncertainty (%)7.58.08.59.09.510.0Worst-case costꜪ0.150.30.Ꜫ5Figure 3.2: Impact of uncertainty level on worst-case cost in Scenario 2.Finally, the results indicate that for both the RO and RM models, theaverage overtime and the mean number of opened ORs increase as the levelof uncertainty increases. Additionally, lowering overtime costs may resultin opening fewer ORs as opening more ORs incurs higher system costs thanpaying the overtime penalty. These findings highlight the importance ofcarefully balancing cost and risk in OR planning, taking into account theuncertainty of the surgery duration as well as the effects of cost-saving mea-sures on OR utilization and overtime costs.In conclusion, the developed RM model is more appropriate for risk-tolerant decision-makers who aim to minimize the costs of ORs under un-certainty, despite its higher computational complexity. Meanwhile, the ROmodel is a better choice for risk-averse OR managers who want to protectagainst extreme situations. Both models have their pros and cons, and thedecision between them depends on the individual needs and objectives ofeach decision-maker. It is crucial to thoroughly evaluate both models beforemaking a final choice and to seek expert advice if necessary.66Chapter 4Conclusions and FutureWorksThis chapter provides an overview of the main findings and contributionsof this thesis. Additionally, potential future research directions and areasfor further investigation will be discussed.4.1 Research SummaryThe thesis examined the use of RM models to address uncertainty inHHC location and OR planning problems. Chapter 2 specifically addressedan HHC location problem that deals with demand uncertainty. In real-worldscenarios, the locations of HHC facilities and the number of caregivers ateach facility are determined before demand is observed. Then, caregiversare allocated to demand nodes based on the available demand information.In Chapter 3, we investigated an OR planning problem that involves un-certainty in surgery duration, where decisions regarding opening ORs andassigning surgeries must be made before the surgery duration is known.To address the two-stage decision-making environment of these problems,we developed two-stage RO and RMmethods to handle the uncertainty. Themain objective of the RM method is to generate less conservative solutions,but the computational complexity is a significant challenge. As a solution,we reformulated the RM model as an RO model and used the C&CG al-gorithm to solve the large-scale instances of both problems efficiently. Weconducted extensive numerical experiments to compare the performance ofthe two methods and analyze the impact of uncertainty on the solutionsfor each problem. The results indicated that the RM model produces lessconservative solutions. Although the RO model performs better compu-tationally, the reformulation and use of the C&CG algorithm enhance theperformance of the RM method. Additionally, the results showed that theproblems become more complex as the uncertainty level increases.Overall, the findings suggest that the RM model is a more practical674.2. RESEARCH CONTRIBUTIONSand effective approach for HHC location and OR planning problems underuncertainty as it balances the risk of suboptimal solutions with the benefitof increasing profits and reducing average overtime costs for HHC and ORmanagers, respectively.4.2 Research ContributionsThe study overcame several barriers in the existing literature and madesignificant contributions in the following areas:(i) Addressed location decisions in the HHC problem under uncertainty:Proposed a novel two-stage location problem to determine the loca-tion of HHC facilities before observing the demand and number ofcaregivers required. This approach accounted for demand uncertainty,providing a more robust and practical solution.(ii) Improved solution quality in a two-stage environment: Formulated theRM model for both the HHC location problem and the OR planningproblem. Compared to previous studies that utilized RO formulations,the developed RM model offered less conservative solutions.(iii) Leveraged reformulation and traceability for enhanced decision-making:Reformulated the two-stage RM problems as RO models, incorpo-rating traceability benefits. This reformulation allowed for improveddecision-making in both the HHC location problem and the OR plan-ning problem.(iv) Developed an exact solution method for large-scale instances: Solvedthe reformulated RM models as RO models using the C&CG algo-rithm, addressing computational difficulties and enabling efficient plan-ning.(v) Performed extensive numerical experiments to evaluate the proposedmodels: Conducted a comprehensive set of numerical experiments toassess the performance of the RM and RO models in terms of tractabil-ity and conservatism in both problems. These experiments providedvaluable insights into the practical implications.By addressing these challenges and contributing novel approaches to theliterature, this thesis advanced the understanding and application of the RMmodel for decision-making under uncertainty in the domains of HHC andOR planning.684.3. RESEARCH LIMITATIONS4.3 Research LimitationsThe research presented in this thesis, while making significant contribu-tions to the field of healthcare operations management, also exhibits certainlimitations that should be considered for a comprehensive understanding ofits findings. Some potential limitations of the research are as follows:(i) Simplified Assumptions: Like any research study, this thesis is basedon certain assumptions to facilitate modelling and analysis. Theseassumptions may simplify the real-world complexities of the HHC lo-cation problem and OR planning problem. For instance, the modelsmay assume fixed travel times and availability of surgeons disregardingother sources of uncertainties that exist in practice.(ii) Assumptions in Human Factors: Although the potential future re-search direction includes the consideration of human factors, the spe-cific modelling of these factors may involve certain assumptions. Forinstance, the models may assume that staff preferences are consistentand quantifiable, which may oversimplify the complexity of humandecision-making processes. Additionally, the models may not captureall relevant human factors, such as cognitive biases or social dynamics,which can influence decision-making in healthcare operations.(iii) Data Availability and Quality: The research heavily relies on dataavailability and quality to validate the proposed models and algo-rithms. Obtaining accurate and reliable data for healthcare operationscan be challenging due to privacy concerns, limited access, or incom-plete records. The limitations in data availability and quality mayimpact the accuracy and robustness of the developed models.Addressing these limitations in future studies can contribute to the ad-vancement and practical application of decision-making models and algo-rithms in healthcare operations.4.4 Future ResearchOne potential direction for future research on the HHC location problemcould be to develop a multi-objective optimization model that considers mul-tiple factors, such as travel times, caregiver skills, and demand types, simul-taneously. Similarly, multiple factors, such as surgeons’ skills and surgerytypes, can be addressed in the OR planning problem. Moreover, while this694.4. FUTURE RESEARCHstudy focuses on the specific problems of HHC location and OR planning,the models we developed can be easily adapted and applied to other health-care location and scheduling problems.Another possible direction is to explore the impact of multiple sourcesof uncertainty on both the provider and receiver sides, such as travellingtime and caregivers’ availability on the decision-making process of the HHCproblems. For OR planning problems, it could be surgeons’ availability andpatient demand.Moreover, the developed methods in this research can be applied toreal-world healthcare problems. This could involve working with healthcareproviders to collect data on patient demand and other relevant factors andusing this data to build models that can help optimize resource allocationand improve patient outcomes.Another important aspect to consider in future studies is the incorpo-ration of human factors into the decision-making process. Human factorsplay a crucial role in healthcare operations and can significantly impact theeffectiveness of resource allocation and planning decisions. Factors such asstaff preferences, workload, and skill levels can influence the performanceand efficiency of healthcare systems.Future research can explore the integration of human factors into theHHC location problem and OR planning problem. This can involve devel-oping models that account for staff preferences and workload distributionto optimize the assignment of caregivers or surgeons to specific locations orprocedures. By considering human factors, decision-makers can better alignthe capabilities and preferences of healthcare professionals with the needsand demands of patients, ultimately improving the overall quality of care.The thesis also highlights the potential for further development of com-putational methods to solve RM models more efficiently. While the C&CGalgorithm used in the thesis is effective for solving large-scale instances,there may be opportunities to develop more specialized algorithms that cantake advantage of the structure of specific RM models to achieve even betterperformance.Finally, the thesis underscores the importance of continued research inthis area, given the ongoing challenges posed by uncertainty in healthcareplanning and other OM problems. By developing new models and meth-ods for dealing with uncertainty, researchers can help healthcare providersmake more informed decisions and improve patient outcomes in a constantlyevolving healthcare landscape.70BibliographyAhmadi-Javid, A., Seyedi, P., and Syam, S. S. (2017). A survey of healthcarefacility location. Computers & Operations Research, 79:223–263. → pages5Akbarpour, M., Torabi, S. A., and Ghavamifar, A. (2020). Designing an in-tegrated pharmaceutical relief chain network under demand uncertainty.Transportation Research Part E: Logistics and Transportation Review,136:101867. → pages 15, 47Ardestani-Jaafari, A. and Delage, E. (2018). The value of flexibility in robustlocation–transportation problems. Transportation Science, 52(1):189–209.→ pages 9, 10Ardestani-Jaafari, A. and Delage, E. (2021). Linearized robust counterpartsof two-stage robust optimization problems with applications in operationsmanagement. INFORMS Journal on Computing, 33(3):1138–1161. →pages 9, 10, 26Assavapokee, T., Realff, M. J., and Ammons, J. C. (2008a). Min-max regretrobust optimization approach on interval data uncertainty. Journal ofOptimization Theory and Applications, 137(2):297–316. → pages 11, 44Assavapokee, T., Realff, M. J., Ammons, J. C., and Hong, I.-H. (2008b).Scenario relaxation algorithm for finite scenario-based min–max regretand min–max relative regret robust optimization. Computers & operationsresearch, 35(6):2093–2102. → pages 11, 44Atamtu¨rk, A. and Zhang, M. (2007). Two-stage robust network flow anddesign under demand uncertainty. Operations Research, 55(4):662–673.→ pages 8, 9Averbakh, I. and Lebedev, V. (2005). On the complexity of minmax re-gret linear programming. European Journal of Operational Research,160(1):227–231. → pages 4271BibliographyBaron, O., Milner, J., and Naseraldin, H. (2011). Facility location: A ro-bust optimization approach. Production and Operations Management,20(5):772–785. → pages 8, 9, 10Basciftci, B., Ahmed, S., and Shen, S. (2021). Distributionally robust facilitylocation problem under decision-dependent stochastic demand. EuropeanJournal of Operational Research, 292(2):548–561. → pages 47Batun, S., Denton, B. T., Huschka, T. R., and Schaefer, A. J. (2011). Op-erating room pooling and parallel surgery processing under uncertainty.INFORMS journal on Computing, 23(2):220–237. → pages 43Bazirha, M., Kadrani, A., and Benmansour, R. (2021). Stochastic homehealth care routing and scheduling problem with multiple synchronizedservices. Annals of Operations Research, pages 1–29. → pages 13Berglund, P. G. and Kwon, C. (2014). Robust facility location problemfor hazardous waste transportation. Networks and spatial Economics,14(1):91–116. → pages 15Bertsimas, D. and de Ruiter, F. J. (2016). Duality in two-stage adaptivelinear optimization: Faster computation and stronger bounds. INFORMSJournal on Computing, 28(3):500–511. → pages 9Bertsimas, D. and Sim, M. (2004). The price of robustness. Operationsresearch, 52(1):35–53. → pages 16, 48Breuer, D. J., Lahrichi, N., Clark, D. E., and Benneyan, J. C. (2020). Ro-bust combined operating room planning and personnel scheduling underuncertainty. Operations research for health care, 27:100276. → pages 5,44Caldentey, R., Liu, Y., and Lobel, I. (2017). Intertemporal pricing underminimax regret. Operations Research, 65(1):104–129. → pages 2, 6, 42Cappanera, P., Scutella`, M. G., Nervi, F., and Galli, L. (2018). Demanduncertainty in robust home care optimization. Omega, 80:95–110. →pages 7, 13Cardoen, B., Demeulemeester, E., and Belie¨n, J. (2010). Operating roomplanning and scheduling: A literature review. European journal of opera-tional research, 201(3):921–932. → pages 41, 4372BibliographyCarello, G. and Lanzarone, E. (2014). A cardinality-constrained robustmodel for the assignment problem in home care services. European Journalof Operational Research, 236(2):748–762. → pages 7, 13Chan, T. C., Shen, Z.-J. M., and Siddiq, A. (2018). Robust defibrillatordeployment under cardiac arrest location uncertainty via row-and-columngeneration. Operations Research, 66(2):358–379. → pages 17Chen, B., Wang, J., Wang, L., He, Y., and Wang, Z. (2014). Robust opti-mization for transmission expansion planning: Minimax cost vs. minimaxregret. IEEE Transactions on Power Systems, 29(6):3069–3077. → pages11, 44Cheng, C., Adulyasak, Y., and Rousseau, L.-M. (2021a). Robust facil-ity location under demand uncertainty and facility disruptions. Omega,103:102429. → pages 10, 18Cheng, C., Adulyasak, Y., and Rousseau, L.-M. (2021b). Robust facility lo-cation under disruptions. INFORMS Journal on Optimization, 3(3):298–314. → pages 10, 18, 21, 51Cisse´, M., Yalc¸ındag˘, S., Kergosien, Y., S¸ahin, E., Lente´, C., and Matta, A.(2017). Or problems related to home health care: A review of relevantrouting and scheduling problems. Operations Research for Health Care,13:1–22. → pages 4, 7Denton, B., Viapiano, J., and Vogl, A. (2007). Optimization of surgerysequencing and scheduling decisions under uncertainty. Health care man-agement science, 10(1):13–24. → pages 43Denton, B. T., Miller, A. J., Balasubramanian, H. J., and Huschka, T. R.(2010). Optimal allocation of surgery blocks to operating rooms underuncertainty. Operations research, 58(4-part-1):802–816. → pages 43, 46,47, 57Du, G. and Zhang, J. (2022). Cross-regional manpower scheduling and rout-ing problem with stochastic service times in home health care. Computers& Industrial Engineering, 173:108668. → pages 7Fathollahi-Fard, A. M., Ahmadi, A., Goodarzian, F., and Cheikhrouhou, N.(2020). A bi-objective home healthcare routing and scheduling problemconsidering patients’ satisfaction in a fuzzy environment. Applied softcomputing, 93:106385. → pages 8, 1373BibliographyFikar, C. and Hirsch, P. (2017). Home health care routing and scheduling:A review. Computers & Operations Research, 77:86–95. → pages 4, 7Freeman, N. K., Melouk, S. H., and Mittenthal, J. (2016). A scenario-basedapproach for operating theater scheduling under uncertainty. Manufac-turing & Service Operations Management, 18(2):245–261. → pages 40Fu¨gener, A., Schiffels, S., and Kolisch, R. (2017). Overutilization and un-derutilization of operating rooms-insights from behavioral health care op-erations management. Health care management science, 20(1):115–128.→ pages 40Gabrel, V., Lacroix, M., Murat, C., and Remli, N. (2014a). Robust loca-tion transportation problems under uncertain demands. Discrete AppliedMathematics, 164:100–111. → pages 9Gabrel, V., Murat, C., and Thiele, A. (2014b). Recent advances in robustoptimization: An overview. European journal of operational research,235(3):471–483. → pages 5Ghosal, S. and Wiesemann, W. (2020). The distributionally robust chance-constrained vehicle routing problem. Operations Research, 68(3):716–732.→ pages 47Golden, B. L., Laporte, G., and Taillard, E´. D. (1997). An adaptive memoryheuristic for a class of vehicle routing problems with minmax objective.Computers & Operations Research, 24(5):445–452. → pages 15Grieco, L., Utley, M., and Crowe, S. (2021). Operational research appliedto decisions in home health care: A systematic literature review. Journalof the Operational Research Society, 72(9):1960–1991. → pages 4Gutie´rrez, E. V., Gutie´rrez, V., and Vidal, C. J. (2013). Home health carelogistics management: Framework and research perspectives. Interna-tional Journal of Industrial Engineering and Management, 4(3):173. →pages 5Hashemi Doulabi, S. H., Rousseau, L.-M., and Pesant, G. (2016). Aconstraint-programming-based branch-and-price-and-cut approach for op-erating room planning and scheduling. INFORMS Journal on Computing,28(3):432–448. → pages 4374BibliographyHolte, M. and Mannino, C. (2013). The implementor/adversary algorithmfor the cyclic and robust scheduling problem in health-care. EuropeanJournal of Operational Research, 226(3):551–559. → pages 43, 44Jeyakumar, V., Li, G., Woolnough, D., and Wu, H. (2023). Affinely ad-justable robust optimization for radiation therapy under evolving datauncertainty via semi-definite programming. Optimization, pages 1–26. →pages 6Jiang, R., Wang, J., Zhang, M., and Guan, Y. (2013). Two-stage minimaxregret robust unit commitment. IEEE Transactions on Power Systems,28(3):2271–2282. → pages 11, 44Kim, K. and Mehrotra, S. (2015). A two-stage stochastic integer program-ming approach to integrated staffing and scheduling with application tonurse management. Operations Research, 63(6):1431–1451. → pages 43Kroer, L. R., Foverskov, K., Vilhelmsen, C., Hansen, A. S., and Larsen, J.(2018). Planning and scheduling operating rooms for elective and emer-gency surgeries with uncertain duration. Operations research for healthcare, 19:107–119. → pages 43Lamiri, M., Grimaud, F., and Xie, X. (2009). Optimization methods for astochastic surgery planning problem. International Journal of ProductionEconomics, 120(2):400–410. → pages 43Lei, C., Lin, W.-H., and Miao, L. (2016). A two-stage robust optimizationapproach for the mobile facility fleet sizing and routing problem underuncertainty. Computers & Operations Research, 67:75–89. → pages 9, 17,21, 51Li, Y., Ye, C., Wang, H., Wang, F., and Xu, X. (2022). A discrete multi-objective grey wolf optimizer for the home health care routing and schedul-ing problem with priorities and uncertainty. Computers & Industrial En-gineering, page 108256. → pages 8, 13Liu, R., Xie, X., and Garaix, T. (2014). Hybridization of tabu search withfeasible and infeasible local searches for periodic home health care logis-tics. Omega, 47:17–32. → pages 4Lu, X. and Cheng, C. (2021). Locating facilities with resiliency to capacityfailures and correlated demand uncertainty. Transportation Research PartE: Logistics and Transportation Review, 153:102444. → pages 10, 1875BibliographyMacario, A. (2010). Is it possible to predict how long a surgery will last?medscape. → pages 43Mausser, H. E. and Laguna, M. (1999). Minimising the maximum relativeregret for linear programmes with interval objective function coefficients.Journal of the Operational Research Society, 50(10):1063–1070. → pages2, 6, 42Natarajan, K., Shi, D., and Toh, K.-C. (2014). A probabilistic modelfor minmax regret in combinatorial optimization. Operations Research,62(1):160–181. → pages 2, 6, 42Neyshabouri, S. and Berg, B. P. (2017). Two-stage robust optimizationapproach to elective surgery and downstream capacity planning. EuropeanJournal of Operational Research, 260(1):21–40. → pages 44Ng, T. S. (2013). Robust regret for uncertain linear programs with applica-tion to co-production models. European Journal of Operational Research,227(3):483–493. → pages 6, 11, 41, 44Nikzad, E., Bashiri, M., and Abbasi, B. (2021). A matheuristic algorithm forstochastic home health care planning. European Journal of OperationalResearch, 288(3):753–774. → pages 5, 7, 13Ning, C. and You, F. (2018). Adaptive robust optimization with minimax re-gret criterion: Multiobjective optimization framework and computationalalgorithm for planning and scheduling under uncertainty. Computers &Chemical Engineering, 108:425–447. → pages 11, 44, 45Perakis, G. and Roels, G. (2008). Regret in the newsvendor model withpartial information. Operations research, 56(1):188–203. → pages 11, 44Poursoltani, M. and Delage, E. (2021). Adjustable robust optimization re-formulations of two-stage worst-case regret minimization problems. Op-erations Research. → pages 11, 12Poursoltani, M. and Delage, E. (2022). Adjustable robust optimization re-formulations of two-stage worst-case regret minimization problems. Op-erations Research, 70(5):2906–2930. → pages 42, 45Rachuba, S. and Werners, B. (2017). A fuzzy multi-criteria approach forrobust operating room schedules. Annals of Operations Research, 251:325–350. → pages 4376BibliographyRodriguez, C., Garaix, T., Xie, X., and Augusto, V. (2015). Staff dimension-ing in homecare services with uncertain demands. International Journalof Production Research, 53(24):7396–7410. → pages 7, 12Roshanaei, V., Booth, K. E., Aleman, D. M., Urbach, D. R., and Beck,J. C. (2020). Branch-and-check methods for multi-level operating roomplanning and scheduling. International Journal of Production Economics,220:107433. → pages 40Samudra, M., Van Riet, C., Demeulemeester, E., Cardoen, B.,Vansteenkiste, N., and Rademakers, F. E. (2016). Scheduling operat-ing rooms: achievements, challenges and pitfalls. Journal of scheduling,19(5):493–525. → pages 41Savage, L. J. (1951). The theory of statistical decision. Journal of theAmerican Statistical association, 46(253):55–67. → pages 16, 48Shahnejat-Bushehri, S., Tavakkoli-Moghaddam, R., Boronoos, M., andGhasemkhani, A. (2021). A robust home health care routing-schedulingproblem with temporal dependencies under uncertainty. Expert Systemswith Applications, 182:115209. → pages 8, 13Shehadeh, K. S. (2022). Data-driven distributionally robust surgery plan-ning in flexible operating rooms over a wasserstein ambiguity. Computers& Operations Research, 146:105927. → pages 44Shehadeh, K. S., Cohn, A. E., and Epelman, M. A. (2019). Analysis of mod-els for the stochastic outpatient procedure scheduling problem. EuropeanJournal of Operational Research, 279(3):721–731. → pages 43Shi, Y., Boudouh, T., and Grunder, O. (2017). A hybrid genetic algorithmfor a home health care routing problem with time window and fuzzy de-mand. Expert Systems with Applications, 72:160–176. → pages 7, 13Shi, Y., Boudouh, T., Grunder, O., and Wang, D. (2018). Modeling andsolving simultaneous delivery and pick-up problem with stochastic traveland service times in home health care. Expert systems with applications,102:218–233. → pages 7Shiri, M., Ahmadizar, F., and Mahmoudzadeh, H. (2021). A three-phasemethodology for home healthcare routing and scheduling under uncer-tainty. Computers & Industrial Engineering, 158:107416. → pages 8, 1377BibliographyShiri, M., Ahmadizar, F., Thiruvady, D., and Farvaresh, H. (2022). A sus-tainable and efficient home health care network design model under un-certainty. Expert Systems with Applications, page 118185. → pages 8Shylo, O. V., Prokopyev, O. A., and Schaefer, A. J. (2013). Stochastic op-erating room scheduling for high-volume specialties under block booking.INFORMS Journal on Computing, 25(4):682–692. → pages 43Simchi-Levi, D., Wang, H., and Wei, Y. (2019). Constraint generation fortwo-stage robust network flow problems. INFORMS Journal on Opti-mization, 1(1):49–70. → pages 10, 17, 21, 51Statistics Canada (2021). Home care use and unmet home care needs incanada, 2021. Report, Statistics Canada. → pages 4Thiele, A. (2010). A note on issues of over-conservatism in robust opti-mization with cost uncertainty. Optimization, 59(7):1033–1040. → pages44To¨nissen, D. D., Arts, J. J., and Shen, Z.-J. (2019). Maintenance loca-tion routing for rolling stock under line and fleet planning uncertainty.Transportation Science, 53(5):1252–1270. → pages 17Tyler, D. C., Pasquariello, C. A., and Chen, C.-H. (2003). Determiningoptimum operating room utilization. Anesthesia & Analgesia, 96(4):1114–1121. → pages 40Vancroonenburg, W., Smet, P., and Berghe, G. V. (2015). A two-phaseheuristic approach to multi-day surgical case scheduling considering gener-alized resource constraints. Operations Research for Health Care, 7:27–39.→ pages 43Viapiano, J. and Ward, D. S. (2000). Operating room utilization: the needfor data. International anesthesiology clinics, 38(4):127–140. → pages 40Wang, L., Demeulemeester, E., Vansteenkiste, N., and Rademakers, F. E.(2021). Operating room planning and scheduling for outpatients and in-patients: A review and future research. Operations Research for HealthCare, 31:100323. → pages 43World Health Organization (2015). World report on ageing and health.Report 9789241565042, World Health Organization. → pages 478BibliographyYuan, B., Liu, R., and Jiang, Z. (2015). A branch-and-price algorithmfor the home health care scheduling and routing problem with stochasticservice times and skill requirements. International Journal of ProductionResearch, 53(24):7450–7464. → pages 7, 13Yuan, B., Liu, R., and Jiang, Z. (2018). Daily scheduling of caregiverswith stochastic times. International Journal of Production Research,56(9):3245–3261. → pages 7Zeng, B. and Zhao, L. (2013). Solving two-stage robust optimization prob-lems using a column-and-constraint generation method. Operations Re-search Letters, 41(5):457–461. → pages 9, 17, 50, 52Zhang, M. (2011). Two-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertainty. Operations research letters,39(5):342–345. → pages 11, 44Zhu, S., Fan, W., Yang, S., Pei, J., and Pardalos, P. M. (2019). Operatingroom planning and surgical case scheduling: a review of literature. Journalof Combinatorial Optimization, 37(3):757–805. → pages 41, 43Ziya-Gorabi, F., Ghodratnama, A., Tavakkoli-Moghaddam, R., and Asadi-Lari, M. S. (2022). A new fuzzy tri-objective model for a home health careproblem with green ambulance routing and congestion under uncertainty.Expert Systems with Applications, 201:117093. → pages 5, 8, 12, 1379Appendix AA.1 Proof of Proposition 3.3The proof proceeds in two three. First, we show that the problem (3.6)meets the condition of relatively complete recourse as follows:Lemma A.1. Problem (3.6) has relatively complete recourse.Proof. It can be proven using the fact that o = 0m is feasible for all x, y,δ+ , and δ− .Then, based on lemma (A.1), the second-stage problem is always feasi-ble. Therefore, because the uncertainty set is bounded and non-empty, itsoptimal value is finite. The KKT condition can be used to derive the SPbecause strong duality holds. Hence, the inner problem of problem (2.2) isequivalent tomaximizeo,λcν∑joj (A.1a)subject to oj ≥∑iζiyij − Txj , ∀ j , (A.1b)λj ≤ cν , ∀ j , (A.1c)λ ≥ 0 , o ≥ 0 , (A.1d)(oj −∑iζiyij − Txj)λj = 0 , ∀ j , (A.1e)(cν − λj) oj = 0 , ∀ j . (A.1f)where λ is a dual variable associated with primal and dual feasibility condi-tions (A.1b)-(A.1d) and slackness conditions (A.1e)-(A.1f).Finally, to obtain a tractable solution for problem (A.1), the bilinearterms in the constraints (A.1e) and (A.1f) are first identified and then lin-earized using new variables and big-M constraints that capture the inter-action between the original variables. Therefore, Problem (A.1) can belinearized as80A.1. Proof of Proposition 3.3maximizeo,δ+ ,δ− ,λ,θ1 ,θ2cν∑joj (A.2a)subject to oj ≥∑i(ζ¯i + (δ+i − δ−i )ζˆj)yij − Txj , ∀ j , (A.2b)λj ≤ cν , ∀ j , (A.2c)λ ≥ 0 , o ≥ 0 , (A.2d)oj −∑i(ζ¯i + (δ+i − δ−i )ζˆj)yij + Txj ≤M1j (1− θ1j ) ,∀ j , (A.2e)λj ≤M2j θ1j , ∀ j , (A.2f)λj − cν ≤M3j (1− θ2j ) , ∀ j , (A.2g)oj ≤M4j θ2j , ∀ j , (A.2h)θ1 , θ2 ∈ {0, 1}m . (A.2i)Binary variables θ1 and θ2 are defined to linearize the complementaryslackness conditions.81
Thesis/Dissertation
eng
Mechanical Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Tosarkani, Babak Mohamadpour
Ardestani-Jaafari, Amir
Minimax Regret Optimization with Applications in Healthcare Operations
Text