The therapist routing and scheduling problem

In a majority of settings, rehabilitative services are provided at healthcare facilities by skilled therapists who work as independent contractors. Facilities include hospitals, nursing homes, clinics, and assisted living centers and may be located throughout a wide geographic area. To date, the problem of constructing weekly schedules for the therapists has yet to be fully investigated. This article presents the first algorithm for supporting weekly planning at the agencies that do the contracting. The goal is to better match patient demand with therapist skills while minimizing treatment, travel, administrative and mileage reimbursement costs.The problem was modeled as a mixed-integer program but has several complicating components, including different patient classes, optional weekly treatment patterns and a complex payment structure that frustrated the use of exact methods. Alternatively, a parallel (two-phase) greedy randomized adaptive search procedure was developed that relies on an innovative decomposition scheme and a number of benefit measures that explicitly address the trade-off between feasibility and solution quality. In Phase I, daily routes are constructed for the therapists in parallel and then combined to form weekly schedules. In Phase II, a high-level neighborhood search is executed to converge towards a local optimum. This is facilitated by solving a series of newly formulated traveling salesman problems with side constraints. Extensive testing with both real data provided by a U.S. rehabilitation agency and associated random instances demonstrates the effectiveness of the purposed procedure.