Structural insights and efficient algorithms for the patient-to-room assignment problem with equal rooms

Brandt, Tabea Claudia; Knust, Sigrid; Büsing, Christina Maria Katharina

doi:44597

Structural insights and efficient algorithms for the patient-to-room assignment problem with equal rooms

Brandt, Tabea Claudia^RWTH*

2025

Verantwortlichkeitsangabevorgelegt von Tabea Claudia Brandt, M. Sc.

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Büsing, Christina Maria Katharina (Thesis advisor)^RWTH* ; Knust, Sigrid (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2025-06-27

Online
DOI: 10.18154/RWTH-2025-06846
URL: https://publications.rwth-aachen.de/record/1016252/files/1016252.pdf

Einrichtungen

Projekte

Inhaltliche Beschreibung (Schlagwörter)
combinatorial optimization (frei) ; patient-to-room assignment (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Krankenhäuser sind ein essenzieller Bestandteil unseres Gesundheitswesens und Teil der kritischen Infrastruktur. Zurzeit stehen immer mehr Krankenhäuser aufgrund von Personalmangel oder knappem finanziellen Budget vor großen Herausforderungen. Zusätzlich werden viele Planungsaufgaben auch heute noch händisch von erfahrenem medizinischen Personal erledigt wird. Dies bindet dringend benötigte Kapazitäten in der Patientenversorgung. Eine der alltäglichen Aufgaben in Krankenhäusern, für die bisher noch keine automatische Planung oder Entscheidungsunterstützung existiert, ist die Zuweisung von Patienten zu Räumen. Bei diesem sogenannte Patienten-Raum-Zuweisungsproblem (PRA) werden die Patienten anhand verschiedener Bedingungen und Zielen für die Zeit ihrer Krankenhausaufenthalte zu Räumen zugewiesen. Dabei wird u.A. auf geschlechtergetrennte Räume geachtet, Patientenverlegungen versucht zu vermeiden, Einzelzimmeransprüche soweit möglich erfüllt, und möglichst sich verstehende Zimmernachbarn gewählt. In der Literatur existieren bereits viele verschiedene Heuristiken für PRA. Eine Analyse der zugrunde liegenden kombinatorischen Strukturen ist dagegen bisher vernachlässigt worden. Hinzu kommt, dass die am häufigsten in der Literatur verwendete Problemdefinition nur bedingt auf die übliche Situation in deutschen Krankenhäusern zutrifft. In dieser Arbeit analysieren wir das kombinatorische Optimierungsproblem, dass dem Patienten-Raum-Zuweisungsproblem, so wie wir es in unseren lokalen Krankenhäusern vorfinden, zugrunde liegt. Wir vervollständigen unsere kombinatorischen Resultate für PRA mit der Entwicklung eines effizienten Algorithmus, der innerhalb von Sekunden nahezu optimale Lösungen für reale Instanzen findet.

Hospitals are an essential part of our health care system and provider of critical services. Currently, most hospitals face serious challenges due to staff shortage or a tight budget. Efficient planning is therefore essential in every day life of hospitals. However, many planning tasks are still performed manually by experienced medical staff which takes up valuable time. One of those every-day tasks for which no automated planning or decision support exists is the assignment of patients to rooms. This so-called patient-to-room assignment problem (PRA) is a fundamental task in hospitals and, especially, within wards. It consists of assigning patients to rooms during their stay at a hospital according to certain conditions and objectives, e.g., ensuring gender-separated rooms, avoiding transfers, respecting single-room requests, and finding suitable roommates. Over the last years, many heuristics have been proposed for PRA with a large variety of different practical constraints. However, a thorough investigation of the problem’s structure itself has been neglected so far. Additionally, the setting mostly considered in literature does not fit well to the common situation in German hospitals. In this thesis, we present insights about the basic, underlying combinatorial problem of PRA with a focus on the setting of our local hospitals. We complement our combinatorial insights with an efficient solution approach for PRA that solves real-world instances to a high degree of optimality within seconds.

OpenAccess:
PDF
(additional files)