The traveling therapist scheduling problem

This article presents a new model for constructing weekly schedules for therapists who treat patients with fixed appointment times at various healthcare facilities throughout a large geographic area. The objective is to satisfy the demand for service over a 5-day planning horizon at minimum cost subject to a variety of constraints related to time windows, overtime rules, and breaks. Each therapist works under an individually negotiated contract and may be full-time or part-time. Patient preferences for specific therapists and therapist preferences for assignments at specific facilities are also taken into account when they do not jeopardize feasibility. To gain an understanding of the computational issues, the complexity of various relaxations is examined and characterized. The results indicated that even simple versions of the problem are NP-hard. The model takes the form of a large-scale mixed-integer program but was not solvable with CPLEX for instances of realistic size. Subsequently, a branch-and-price-and-cut algorithm was developed and proved capable of finding near-optimal solutions within 50 minutes for small instances. High-quality solutions were ultimately found with a rolling horizon algorithm in a fraction of that time. The work was performed in conjunction with Key Rehab, a company that provides physical, occupational, and speech therapy services throughout the U.S. Midwest. The policies, practices, compensation rules, and legal restrictions under which Key operates are reflected in the model formulation.