Exact branch-price-and-cut for a hospital therapist scheduling problem with flexible service locations and time-dependent location capacity

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.     «

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 approa...     »