Local search methods for the particle therapy patient scheduling problem

Abstract

Das Partikeltherapienpatientenplanungsproblem (PTPSP) entsteht in modernen Krebstherapieeinrichtungen, die eine Partikeltherapie anbieten, und besteht aus der Planung von Therapien innerhalb eines Planungshorizonts von mehreren Monaten. Eine Besonderheit des PTPSP im Vergleich zur klassischen Strahlentherapieplanung besteht darin, dass die Therapien nicht nur auf Tagesebene, sondern auch innerhalb der Tage geplant werden müssen, da sich alle Therapien denselben Partikelstrahl teilen. In einer vorhergehende Arbeit führten Maschler et al. diese neuartige Problemstellung ein und präsentierten erste Algorithmen, inklusive einer Iterated-Greedy-Metaheuristik (IG). In dieser Arbeit bauen wir auf dem IG auf und tauschen zwei Hauptkomponenten aus: die Konstruktionsphase und den lokalen Suchalgorithmus. Die resultierende Metaheuristik verbessert den bestehenden Ansatz und liefert für alle betrachteten Benchmark-Instanzen wesentlich bessere Ergebnisse. Außerdem präsentieren wir einen 2-Phasen-Ansatz, der mittels einer Variable-Neighbourhood-Descent-Methode (VND) die Tagesund Zeitzuordnungen nacheinander optimiert. Schlussendlich, verbessern wir unsere IG-Metaheuristik, indem wir die lokale Suche durch eine VND ersetzen. Diese Methode liefert für alle Benchmark-Instanzen noch bessere Ergebnisse. Da die in der Praxis vorkommenden Probleminstanzen sehr groß sein können, ist eine möglichst effiziente Dursuchung der Nachbarschaften bei der lokalen Suche notwendig. Um den Aufwand der Suche zu reduzieren, definieren wir verschiedene Filter, die die Nachbarschaften auf die vielversprechendsten Lösungen einschränken, wodurch kostspielige Evaluierungen von wahrscheinlich schlechteren Lösungen vermieden werden. Die eigentliche Evaluierung wird inkrementell durchgeführt, indem nur jene Terme der Zielfunktion neu ausgewertet werden, deren Werte sich geändert haben. Eine Schwierigkeit bei diesem Ansatz besteht darin, dass alle Therapieeinheiten einer Therapie ungefähr zur selben Uhrzeit stattfinden müssen. Zu diesem Zweck hängt die Zielfunktion von Variablen ab, die für jede Therapie und Woche die sogenannte nominelle Startzeit repräsentieren. Die Berechnung dieser Variablen ist jedoch recht aufwendig. Daher führen die VNDs zuerst eine lokale Suche mit fixierten nominellen Startzeiten durch und berechnen im Anschluss die nominellen Startzeiten mittels linearer Programmierung. Wir haben die einzelnen Nachbarschaften auf 40 verschiedenen Benchmark-Instanzen ausgewertet und mittels statistischer Methoden verglichen. Basierend auf den Ergebnissen zeigen wir, welche Nachbarschaften für die Verwendung in unseren Metaheuristiken geeignet sind. Danach haben wir mit dem automatisierten Parameterkonfigurationsprogramm irace Nachbarschaftskombinationen und alle anderen Parameterwerte für unsere Metaheuristiken ausgewählt. Schließlich haben wir die Metaheuristiken auf den Benchmark-Instanzen ausgewertet und die Ergebnisse mit statistischen Tests verglichen. Teile dieser Arbeit wurden bereits veröffentlicht.

The Particle Therapy Patient Scheduling Problem (PTPSP) arises in modern cancer treatment facilities that provide particle therapy and consists of scheduling a set of therapies within a planning horizon of several months. A particularity of PTPSP compared to classical radiotherapy scheduling is that therapies need not only be assigned to days but also scheduled within each day because all therapies share the same particle beam. In an earlier work Maschler et al. introduced this novel problem setting and provided first algorithms including an Iterated Greedy (IG) metaheuristic. In this work we build upon this IG and exchange two main components: the construction phase and the local search algorithm. The resulting metaheuristic enhances the existing approach and yields substantially better results for all of the considered benchmark instances. Moreover, we present a 2-Phase Approach (2PA) that uses a Variable Neighborhood Descent (VND) to first optimize the day assignments and then the time assignments. Finally, we improve our IG metaheuristic by replacing the local search algorithm with a VND. This method provides even better results on all benchmark instances. Since the problem instances occurring in practice can be very large, an efficient exploration of the local search neighbourhoods is necessary. In order to reduce the computational effort, we define various filters that limit the neighbourhoods to the most promising solutions, thus, preventing expensive evaluations of solutions which are most likely worse. The actual evaluation is done incrementally by re-computing only those terms of the objective function whose values have changed. A difficulty with this approach is that all daily treatments of a therapy have to start approximately at the same time. To that end, the objective function depends on variables representing the so-called nominal starting time of each therapy and week. The computation of these variables, however, is quite costly. Therefore, the VNDs first perform a local search with fixed nominal starting times, and compute the nominal starting times afterwards using linear programming. We evaluated the individual neighbourhoods on 40 different benchmark instances and compared them using statistical methods. Based on the results, we show which neighbourhoods are suitable for being used in our metaheuristics. We then used the automated parameter configuration tool irace to select neighbourhood combinations and all other parameter values for our metaheuristics. Finally, we evaluated the metaheuristics on the benchmark instances and compared the results with statistical tests. Parts of this thesis were already published.