Exact Branch-Price-and-Cut for a Hospital Therapist Scheduling Problem with Flexible Service Locations and Time-Dependent Location Capacity

Alexander Jungwirth (), Guy Desaulniers (), Markus Frey () and Rainer Kolisch ()
Additional contact information
Alexander Jungwirth: BASF SE, Advanced Analytics in Procurement, 67056 Ludwigshafen am Rhein, Germany
Guy Desaulniers: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T 1J4, Canada; Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, Québec H3T 2A7, Canada
Markus Frey: Hilti AG, Advanced Business Analytics Hilti Global Logistics, 9494 Schaan, Liechtenstein
Rainer Kolisch: TUM School of Management, Technical University of Munich, 80333 Munich, Germany

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 1157-1175

Abstract: We study a new variant of the vehicle routing problem, which arises in hospital-wide scheduling of physical therapists. Multiple service locations exist for patients, and resource synchronization for the location capacities is required as only a limited number of patients can be treated at one location at a time. Additionally, operations synchronization between treatments is required as precedence relations exist. We develop an innovative exact branch-price-and-cut algorithm including two approaches targeting the synchronization constraints (1) based on branching on time windows and (2) based on adding combinatorial Benders cuts. We optimally solve realistic hospital instances with up to 120 treatments and find that branching on time windows performs better than adding cutting planes. Summary of Contribution: We present an exact branch-price-and-cut (BPC) algorithm for the therapist scheduling and routing problem (ThSRP), a daily planning problem arising at almost every hospital. The difficulty of this problem stems from its inherent structure that features routing and scheduling while considering multiple possible service locations with time-dependent location capacities. We model the ThSRP as a vehicle routing problem with time windows and flexible delivery locations and synchronization constraints, which are properties relevant to other vehicle routing problem variants as well. In our computational study, we show that the proposed exact BPC algorithm is capable of solving realistic hospital instances and can, thus, be used by hospital planners to derive better schedules with less manual work. Moreover, we show that time window branching can be a valid alternative to cutting planes when addressing synchronization constraints in a BPC algorithm.

Keywords: hospital therapist scheduling; time-dependent location capacity; flexible service locations; vehicle routing; exact branch-price-and-cut (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1119 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:1157-1175

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().