A Sequential GRASP for the Therapist Routing and Scheduling Problem J. F. Bard, Y. Shao, A. I. Jarrah Presented by Nihal Berkta Outline

Motivation About GRASP Problem Definition and Setting MIP model and additions Solution Methodology Phase I Phase II Computations

Motivation Workforce is majority of the costs providing rehabilitative service to patients located at clinics, hospitals, nursing homes and other facilities Physical therapy Independent agent Days available, time windows Demand is known Motivation

Considerable work in scheduling but difficulty remains. Why? Fixed and flexible patients Feasible patterns Multiple sessions Therapist lunch breaks Licensed therapist vs assistant therapist These factors restricts feasible region so far done manually

About GRASP Greedy Randomized Adaptive Search Procedures A GRASP is a multi-start or iterative process (Lin and Kernighan, 1973) each GRASP iteration consists of two phases, a construction phase, in which a feasible solution is produced, and a local search phase, in which a local optimum in the neighborhood of the constructed solution is sought.

The best overall solution is kept as the result. About GRASP In the construction phase, a feasible solution is iteratively constructed, one element at a time. At each construction iteration, the choice of the next element to be added is determined by ordering all candidate elements (i.e. those that can be added to the solution) in a candidate list C with respect to a greedy function g : C !R. The heuristic is adaptive because the benefits associated with every element are updated at each iteration of the construction phase to reflect the changes brought on by the selection of the previous element.

The probabilistic component of a GRASP is characterized by randomly choosing one of the best candidates in the list, but not necessarily the top candidate. The list of best candidates is called the restricted candidate list (RCL). (Festa and Resende 2004) In previous work Parallel GRASP Now constructing tours sequentially to balance feasibility with optimality when selecting the next route to explore design of an adaptive rule which enables us to

trade off solution quality with solution diversity when selecting the next patient to schedule Literature Healthcare work routing Cheng and Rich (1998) Bertels and Fahle (2006) Bennett and Erera (2011) Eveborn et al.(2006) Patients Scheduling Gupta and Denton (2008)

Green and Savin (2008) Muthuraman and Lawley (2008) ayrl et al. (2008) Patrick et al. (2008) Markov Problem Definition TRSP For each k K, construct a weekly schedule that K, construct a weekly schedule that minimizes the total treatment, travel, overtime, administration and mileage costs of providing service to each i K, construct a weekly schedule that I

By specifying the weekly patterns for all flexible patients and by ensuring that the time windows of all patients and therapists are respected, that new patients are seen by a PT during their first treatment, and that route continuity is maintained for all therapists each day of the planning horizon. Indices and sets i, j Index for patients; I Set of patients to be seen I = IFIX IFLEX IFLEX k Index for therapists ; K Set of all therapists; K = {PTs, PTAs} d Index for days

o(k), d(k) Origin, destination of therapist k K(i, d) Set of therapists that can see patient i on day d IC(i, d, k) Set of patients that can follow patient i in a schedule for therapist k on day d IK (k, d) Set of patients that can be seen by therapist k on day d DK(k) Set of days therapist k can be scheduled to work DU(i ) Set of days in the planning horizon that patient i is to be treated (pattern given) Data and parameters ckij :Cost of traveling from patient i to patient j by therapist k ckid :Cost of a visit by therapist k to see patient i on day d sid :Time required to provide treatment to patient i on day d

aid , bid :Earliest, latest time treatment can begin for patient i on day d ij :Travel time between patients i and j (assumed symmetric) ekd , fkd :Earliest start, latest finish time of therapist k on day d Decision variables xkijd 1 if therapist k visits patients i and j in succession on day d, 0 otherwise tid :Time at which patient i begins to receive treatment from a therapist on day d The MIP Model Additional requirements Patient Patterns

+ binary variable for each pattern First visit Two cases : one of the visit and first visit Multiple session per day Multiple records of patients, break between sessions Lunch breaks Half hour between 11am -1 pm binary variable i,j,k,d

continuous variable for starting time k,d Tracking paid time and overtime After 40 hours in a week Solution Methodology Adaptive Sequential Grasp Phase I randomly selecting therapist-day pairs in sequence and finding the optimal route for each turn (250 times) Phase II improves a subset of candidates using a

high level neighborhood search defined by insertions and swaps Sequential vs Parallel Sequential One route at a time Parallel Multiple route simultaneously If feasibility not an issue and optimality is in focus

Phase I Step 1:Fixing (first) visit day when PT is required Step 2: All compatible therapist-day tours are identified and one of them say (k*,d*) selected to built. Step 3: Identify and sort a subset of patients who are eligible for route (k*,d*) and randomly select When a route is no longer extended a new one is started. Termination: When all patients are routed or no feasible threapist-patient pairs are left (very expensive super therapist)

Step 1:Fixing (first) visit day when PT is required Ex 1: Assume patient i has feasible patterns (1, 2, 3),(1, 2, 4), (2, 3, 4) and (3, 4, 5). Thus, the candidate set D1 ={1, 2, 3}, so the first visit would be randomly fixed at day 1,2 or 3 with probability 1/3. Ex 2: or assign probabilities according to the frequencies Frequency set (2,1,1) so the probabilities of selecting days 1, 2 or 3 for the first visit are 2/4, 1/4, and 1/4, respectively. More sophisticated rules can be used such as looking PT s time

left for each day Step 2: Route Selection Step 2.1: Determining candidate list of days Total amount of available therapist time for day d available remaining time for therapists for each day (fixed patients, already assigned patients, flexible patients who must be seen on that day due to their patterns) Level the days Ex 3: days {1,2,3,4,5} total time {12,8,4,16,8} Treatment, travel and adm. time so remaining {5,0,4,0,2}

first level day 1,3 second level day 5, third level day 2,4 so the candidate day list is D={1,3} Step 2: Route Selection Step 2.2: Selecting next route (k,d) Having candidate day list, list all therapist-day pairs R={(k,d): d in D and k in K(d)} Sort increasing order of wage rates Restricted candidate list Take first m entries so selecting one has prob 1/m Ex 4: D={1,3} therapists k1,k2,k3 with wage rates 40,50,35

k1 and k2 work on day1, k3 works on day 3 so candidate routes R={(k1,1)(k2,1)(k3,3)}, CL= {(k3,3)(k1,1)(k2,2)} if m=2 then RCL= {(k3,3)(k1,1)} with prob of selecting one is 0.5 Step 3: Route Construction

So (k,d) pair is selected Determine candidate patients I(k,d) k is certified to treat patient i? Feasible pattern of patient i includes d? Assigning one patient at a time to the route (starting and ending o(k), d(k)) Step 3.1 Decide on the length of RCL for selecting next patient Within a certain distance from therapists home

Not fixing it to be some value, instead giving an interval Step 3.2 Construct RCL by calculating earliest time that next treatment can start Step3.3 Benefit measure computed for each patient in RCL Step 3.4 one of the top candidates are randomly selected Step 3: Route Construction Step 3.2 Construct RCL by calculating earliest time that next treatment can start ti: starting treatment time sid : treatment time ij : travel time t^j = ti + Sid + ij

Tj: {ajd if j is Fixed, max(ajd,t^j) if j is flex} Ex5: Current patients treatment starts at 13.50 and treat. Time 0.5 hours therapist works (8.00 -17.00) Also if patient has multiple sessions more tj s and checking lunch break Step 3: Route Construction Step 3.3 Benefit measure computed for each patient in RCL Considering idle time, travel times, treatment times Step 3.4 Selecting next patient j So here the RCL is {2,1,5} If m=2 then then patients 1 and 2 will be

selected with probability 0.45 and 0.55 respectively. Phase 2 Not called after every Phase 1 iteration Two procedures Insertion: moving one patient from her current location to another one in the same route or in a different route Swapping: exchanging two patients who are either in the same route or in different routes Slack block: pieces of a sequence

Starts with a fixed patient or o(k) Ends with a fixed patient or d(k) Any patient in between is flexible So the change of patient i only causes changes in the patients after i in his block Phase 2

Route Feasibility after modification Pattern feasibility Therapist Day in patients pattern Ex 9: Assume patient i requires 3 treatment during week on each separate days. Current (1,2,3) if we want to move treatment on day 3 to day 2 it would be infeasible Time feasibility Calculate idle time in new sequence, if negative then infeasible

Also lunch break should be shifted like treatment times Phase 2 Cost efficiency of modification Regular (treatment)

Administrative Travel Travelling millage reimbursement Overtime cost If the change in cost is higher than the treshold then the modification is efficient Phase 2 Insertion

Swapping Computations Real data 5 datasets from Key Rehab Single week operations in Eureka and Wichita May, Nov, Dec. 2010 and March, April 2011 Table of patient and therapist characteristics Computations

Computations Implemented in C++ and run on a PC with 12GB of memory and an Intel i7 950 processor that has 4 3.06 Ghz cores After many experiment parameters are set as follows

No of iteration 250 Frequency in phase II iteration is 5 No of candidate routes in RCL is 10 Parameters to determine length of RCL Imin=1, Istd=10 Imax=20 No of top candidate patients considered in RCL, 3 Benefit function =1 =2 =0.0001 Improvement threshold (for cost) 1 No time limit

Computations To be able to compare the solution with real schedules jhjh Computations Comparision Eff = treatment cost / total cost Computations Sequencial vs Parallel vs LP

Computations Random data to compare seq and parallel Conclusion Average cost reduction of 18% wrt current practise 5.58% improvement over parallel Grasp Further Decomposing therapists and patients by region Specialized clustering algortihm

Column generation algorithm Thank you for your attention! Any questions or comments?