Two-stage robust combinatorial optimization problems with consistent decisions under discrete demand uncertainty and an application to appointment scheduling in primary health care

Schmitz, Sabrina; Koster, Arie Marinus; Büsing, Christina Maria Katharina; Krumke, Sven O.

doi:10.18154/RWTH-2024-03455

Two-stage robust combinatorial optimization problems with consistent decisions under discrete demand uncertainty and an application to appointment scheduling in primary health care

Schmitz, Sabrina^RWTH*

2024

Verantwortlichkeitsangabevorgelegt von Sabrina Schmitz, M.Sc.

ImpressumAachen : RWTH Aachen University 2024

Umfang1 Online-Ressource : Illustrationen

Dissertation, RWTH Aachen University, 2024

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Büsing, Christina Maria Katharina (Thesis advisor)^RWTH* ; Koster, Arie Marinus (Thesis advisor)^RWTH* ; Krumke, Sven O. (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2024-02-02

Online
DOI: 10.18154/RWTH-2024-03455
URL: https://publications.rwth-aachen.de/record/983480/files/983480.pdf

Einrichtungen

Projekte

Inhaltliche Beschreibung (Schlagwörter)
appointment scheduling (frei) ; discrete demand uncertainty (frei) ; primary health care (frei) ; robust minimum cost flow problem (frei) ; robust minimum weight perfect b-matching problem (frei) ; robust representative (multi-)selection problem (frei) ; robust shortest path problem (frei) ; robust transshipment problem (frei) ; robust two-stage optimization (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In Gesundheitssytemen spielen Hausärzt*innen eine zentrale Rolle, da sie die erste Anlaufstelle für Patient*innen mit medizinischen Anliegen bilden. Wegen der sinkenden Zahl der Hausärzt*innen und der steigenden Nachfrage, stehen diese Systeme derzeit jedoch vor Herausforderungen. Aus diesem Grund zielt der erste Teil dieser Arbeit darauf ab, die Behandlungsnachfrage durch eine maßgeschneiderte Terminvergabe effizient zu steuern. Mithilfe mathematischer Modellierung der kombinatorischen Optimierung, entwickeln wir ein robustes Terminplanungssystem, das Schwankungen in der Nachfrage einbezieht. Zu diesem Zweck analysieren wir im zweiten Teil dieser Arbeit ein zweistufiges robustes Optimierungskonzept für kombinatorische Optimierungsprobleme unter diskreter Nachfrageunsicherheit. Die Resultate dieser Arbeit lassen sich in zwei Hauptteile gliedern. Im ersten Teil entwickeln wir Terminsystemen für Hausärzt*innen, die auf sogenannten Masken basieren. Wir berücksichtigen Patient*innen, die auf eine Terminvereinbarungen verzichten und ohne Vorankündigungen in die Praxis kommen, und konzentrieren uns auf die ausgeglichene Arbeitsbelastung eines*r Hausarztes oder Hausärztin in Form des Maskendesignproblems. Um verschiedene Unsicherheiten in der Behandlungsnachfrage zu berücksichtigen, erweitern wir das Maskendesignproblem zum robusten Maskendesign- und zum robusten Multimaskendesignproblem. Für alle drei Probleme liefern wir eine kombinatorische Interpretation durch ein Netzwerkfluss- und Designmodell. Wir nutzen einen Lösungsansatz, der binäre Suche mit kompakten Formulierungen von kostenminimalen Flussproblemen kombiniert. Schließlich führen wir eine Fallstudie mithilfe agentenbasierter Simulation durch, um die maskenbasierten Terminplanungssysteme mit Systemen aus der Literatur zu vergleichen. Im zweiten Teil führen wir ein zweistufiges robustes Konzept für kombinatorische Optimierungsprobleme unter diskreter Nachfrageunsicherheit ein. Kombinatorische Optimierungsprobleme basieren auf einer endlichen Menge von Elementen, die wir in sogenannte fixe und freie Elemente unterteilen. In einer ersten Phase entscheiden wir trotz unsicherer Nachfrage unwiderruflich, welche der fixen Elemente Teil einer Lösung sind. Nachdem ein Nachfrageszenario realisiert wurde, entscheiden wir in einer zweiten Phase, ob und welche der freien Elemente die Lösung vervollständigen. Ziel ist es, eine robuste Lösung zu finden, welche die Worst-Case-Kosten über die diskreten Nachfrageszenarien minimiert. Wir betrachten dieses Konzept sowohl im Allgemeinen als auch für fünf kombinatorische Optimierungsprobleme: das repräsentative Mehrfachauswahl-, das kostenminimale Fluss-, das Umlade-, das kürzeste Wege- und das gewichtsminimale perfekte b-Matching Problem. Wir analysieren sowohl die Struktur der Probleme sowie die Komplexität in Abhängigkeit von verschiedenen Graphenklassen und erhalten einige NP-Schwere Ergebnisse. Darüber hinaus geben wir Spezialfälle an, die in pseudo-polynomialer und polynomialer Zeit lösbar sind.

In primary health care systems, primary care physicians (PCP) play a pivotal role as they are the initial point of contact for patients seeking medical care and they also coordinate ongoing access to medical care. However, these systems currently face challenges due to declining numbers of PCPs and increasing demand. To address this, the first part of this thesis aims at efficiently managing a PCP's demand for treatment through a tailored appointment scheduling. Using mathematical modeling of combinatorial optimization, we develop a robust appointment scheduling system that incorporates fluctuations in demand for treatment. Motivated by this and further applications, we study a two-stage robust optimization concept for combinatorial optimization problems under discrete demand uncertainty in the second part of the thesis. The contributions of this thesis can be divided into two main parts summarized in the following. In the first part, we study appointment scheduling systems based on so-called masks and focus on the balanced workload of the PCP in form of the mask design problem. Our study considers three different types of patients, including walk-ins who forgo scheduling an appointment and seek immediate care by walking into the practice without prior notice. To account for different uncertainties in demand for treatment, we extend the mask design problem to the robust mask design and the robust multimask design problem. For all three problems, we provide a combinatorial interpretation by a network flow and design model. We use a solution approach that combines binary search with compact formulations (of extensions) of minimum cost flow problems. Finally, we conduct an extensive case study by agent-based simulation, comparing the mask-based appointment scheduling systems with five appointment scheduling systems from the literature. In the second part, we introduce a two-stage robust concept for combinatorial optimization problems under discrete demand uncertainty. Combinatorial optimization problems are based on a finite set of elements for which we decide whether they are part of a solution. We divide the elements into two types, the so-called fixed and free elements. In a first stage, we irrecoverably decide whether some fixed elements are part of a solution despite uncertain demand. In a second stage, we decide whether some free elements complete a solution after a demand scenario is realized. The objective is to find a robust solution that minimizes the worst-case cost over a finite scenario set. We consider this concept both in a general context and for five combinatorial optimization problems: the representative multi-selection, the minimum cost flow, the transshipment, the shortest path, and the minimum weight perfect b-matching problem. We analyze the structure of the problems as well as the complexity depending on different graph classes and obtain some NP-hardness results. In addition, we provide special cases solvable in pseudo-polynomial and polynomial-time.

OpenAccess:
PDF
(additional files)