A column generation-based heuristic for a rehabilitation patient scheduling and routing problem. (December 2022)

• Record Type: Journal Article
• Authors: Xiao, Liyang; Zhen, Lu; Laporte, Gilbert; Baldacci, Roberto; Wang, Chenghao
• Is Part Of: Computers & operations research. Volume 148(2022)
• Publication Date: 2022-12
• Subjects: Rehabilitation patient scheduling -- Traveling salesman problem -- Time windows -- Integer linear program -- Column generation; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105970
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Rehabilitation is an important branch of the modern healthcare system. Every day, rehabilitation patients move in hospital campus to receive treatments from therapists. The long timespan of these treatment routes leads to several patients' complaints and results in negative effects. However, scheduling the treatment routes for patients is a complex task for hospital managers. This study investigates a rehabilitation patient scheduling and routing problem, which focuses on reducing the timespan of patients' treatment routes. This real-life motivated problem can be described as a combination of several interrelated traveling salesman problems with time windows (TSPTWs) and is difficult to solve. We formulate the problem as an integer linear program (ILP) and we develop a greedy heuristic called "route-first, schedule-second". Then a column generation solution method is proposed on a set partitioning-based reformulation of the original model. Specifically, a tailored genetic algorithm and several effective accelerating strategies are developed within the column generation method. Numerical experiments are conducted on 30 instances devised from real data to validate the efficiency of the proposed solution approaches. Experimental results show that our methodology can generate high-quality solutions efficiently and is therefore suitable to be applied in practice. Highlights: We introduce the rehabilitation scheduling and routing problem with real-life requirements. We formulate the problem as an integer linear program. We propose a column generation approach on a set partitioning-based reformulation. The derived pricing problem is solved efficiently by a tailored genetic algorithm. We use instances based on real data to test the performance of our proposed solution methods.