Methods for intraday scheduling in particle therapy

Abstract

In dieser Arbeit behandeln wir das Intraday Particle Therapy Patient Scheduling Problem (I-PTPSP), ein Planungsproblem für Behandlungstermine von Patienten, das in medizinischen Einrichtungen für Krebstherapien mit Synchrotrons, einem speziellen Typ von Teilchenbeschleunigern für die Strahlentherapie, auftritt. Das Problem beschreibt bevorstehende Behandlungen mit bereits zugewiesenen Terminen auf einen Zeithorizont von maximal einem Tag. Die Problematik liegt darin, dass durch unvorhergesehene Ereignisse diese Behandlungen nicht mehr zu den vorgesehenen Zeitpunkten durchgeführt werden können und deshalb der bestehende Zeitplan an die neue Situation angepasst werden muss. Dieser neue Zeitplan muss möglichst schnell erstellt werden, um negative Auswirkungen auf beispielsweise die Wartezeiten und laufenden Kosten der Einrichtung zu begrenzen. Das I-PTPSP modelliert diese Situation. Eine Besonderheit des I-PTPSP liegt in der Art und Weise wie die Behandlungen durchgeführt werden. Das Synchrotron kann mehrere Behandlungsräume abwechselnd hintereinander bedienen. Das Ziel besteht nun darin, solche Belegungspläne zu finden, in denen Leerlaufzeiten des Beschleunigers möglichst vermieden werden. Neben dem Strahl und den Behandlungsräumen gibt es weitere relevante Ressourcen, die berücksichtigt werden müssen. In dieser Arbeit betrachten wir zunächst verschiedene Varianten von Greedy Konstruktionsheuristiken, um erste Lösungen für das Problem zu erhalten. Die hierfür verwendeten Ansätze nutzen wir anschließend, um ein Branch and Bound (BAB) Verfahren zu entwickeln. Hierbei untersuchen wir sowohl verschiedene Auswahlstrategien der Knoten aus dem BAB-Baum, als auch diverse Techniken um untere Schranken für die Teillösungen zu berechnen. Weiters wird als Referenz ein Constraint Programming (CP) Modell erstellt und mithilfe eines CP Solvers gelöst. Schlussendlich vergleichen wir die Ergebnisse unserer Verfahren mit denen dieser Referenzimplementierung. Hierfür erstellen wir verschiedene Szenarien unterschiedlicher Größe, welche reale Anwendungsfälle, wie eine Verzögerung in einem Behandlungsraum oder eine dringend benötigte Wartung eines medizinischen Gerätes, simulieren. Die so erstellten Problem-Instanzen werden anschließend verwendet, um die Verfahren miteinander zu vergleichen. Während alle drei Methoden ähnlich gute Ergebnisse bei Instanzen kleinerer Größe liefern, zeigt sich, dass der Branch and Bound Algorithmus die anderen beiden Ansätzen bereits bei Problemen ab mittlerer Größe übertrifft.

We consider the Intraday Particle Therapy Patient Scheduling Problem (I-PTPSP), a patient scheduling problem that arises in facilities specialized on cancer treatment with synchrotrons, a device for particle therapy treatments. This problem has a time horizon of a single day and already assigned starting times for the pending treatments from an earlier created weekly or monthly schedule. If unforeseen circumstances occur, these predefined schedules need to be adjusted to adapt to the new situation. Finding these new schedules quickly is essential to limit any negative impacts on the waiting times of the patients or the running costs of the facility. The I-PTPSP models this situation. A specialty of the I-PTPSP is the way how the treatments are processed. The synchrotron can serve multiple treatment rooms alternatingly. The aim is to find schedules of treatments that occupy the different treatment rooms in such a way that avoids idle times of the synchrotron to increase the throughput of the facility. Beside the synchrotron and the treatment rooms, other resources are relevant and need to be considered. In this work, we tackle the I-PTPSP with multiple variants of a greedy construction heuristic first. Then, we solve it with a Branch and Bound approach that incorporates some of the ideas obtained during the development of the construction heuristic. In addition, we examine and develop several traversal strategies of the Branch and Bound node tree, as well as, different techniques to obtain lower bounds for the partial solutions. Furthermore, a constraint programming (CP) model solved by a state-of-the-art CP solver is developed. Finally, we compare our solution to this reference implementation. For that reason, we simulate different scenarios of various sizes that resemble real world use cases like a delay in a treatment room or a suddenly needed maintenance of a medical device. The so obtained problem instances are used to compare the performance of our three approaches. While all three approaches perform almost equally well on the smaller instances, the Branch and Bound approach clearly outperforms the other two on the medium to larger problem inputs.