The traveling therapist scheduling problem

Jonathan Bard, Yufen Shao, Xiangtong Qi and Ahmad Jarrah

IISE Transactions, 2014, vol. 46, issue 7, 683-706

Abstract: 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.

Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1080/0740817X.2013.851434 (text/html)
Access to full text is restricted to subscribers.

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:taf:uiiexx:v:46:y:2014:i:7:p:683-706

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/0740817X.2013.851434

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().