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.

Xiao L., Zhen L., Laporte G., Baldacci R., Wang C. (2022). A column generation-based heuristic for a rehabilitation patient scheduling and routing problem. COMPUTERS & OPERATIONS RESEARCH, 148, 1-10 [10.1016/j.cor.2022.105970].

A column generation-based heuristic for a rehabilitation patient scheduling and routing problem

Baldacci R.;
2022

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.
2022
Xiao L., Zhen L., Laporte G., Baldacci R., Wang C. (2022). A column generation-based heuristic for a rehabilitation patient scheduling and routing problem. COMPUTERS & OPERATIONS RESEARCH, 148, 1-10 [10.1016/j.cor.2022.105970].
Xiao L.; Zhen L.; Laporte G.; Baldacci R.; Wang C.
File in questo prodotto:
File Dimensione Formato  
CAOR-D-21-00939-Unibo.pdf

Open Access dal 04/08/2024

Descrizione: postprint
Tipo: Postprint
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione - Non commerciale - Non opere derivate (CCBYNCND)
Dimensione 1.34 MB
Formato Adobe PDF
1.34 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/897412
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 4
social impact