Patient appointment scheduling at hemodialysis centers: An exact branch and price approach

Mohammad Reihaneh, Sina Ansari and Farbod Farhadi
Additional contact information
Mohammad Reihaneh: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique
Sina Ansari: DePaul University [Chicago]
Farbod Farhadi: RWU - Roger Williams University

Post-Print from HAL

Abstract: Scheduling patient appointments at a hemodialysis center presents a unique setting. Unlike other appointment scheduling problems in healthcare systems, patients are scheduled for a series of dialysis treatment appointments instead of a single appointment. In this study, we formulate this multiple-appointment system as a set-partitioning problem that allows partial schedules to be feasible. We employ a Branch and Price (BP) algorithm to solve the problem, however, the pricing sub-problem proves to be exceedingly challenging for state-of-the-art dynamic programming algorithms. Therefore, we propose a novel decomposition of the sub-problem and design an efficient embedded Column Generation (CG) algorithm to find the optimal solution. We further design a greedy heuristic that enhances the computational efficiency of the BP algorithm. Our proposed BP algorithms efficiently solve challenging instances that are simulated based on the data from a collaborating hemodialysis center. Specifically, the Enhanced CG-embedded BP algorithm accelerates the CPU time on average by 78% compared to the Base BP algorithm (32% and 59% compared to the Enhanced and the CG-embedded BP algorithms, respectively). We also compare the optimal results with the current scheduling policy at the center. Our proposed Enhanced CG-embedded BP algorithm improves the percentage of leftover appointments by 98% on average and the hours of deviations per patient by 46% on average, compared to the current policy.

Date: 2023-08-16
References: Add references at CitEc
Citations:

Published in European Journal of Operational Research, 2023, 309 (1), pp.35-52. ⟨10.1016/j.ejor.2023.01.024⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:hal:journl:hal-04286207

DOI: 10.1016/j.ejor.2023.01.024

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().