Learning large neighborhood search for the staff resortering problem

Abstract

In dieser Arbeit stellen wir eine mit Machine Learning (ML) erweiterte Large Neighborhood Search (LNS) vor, um das Staff Rerostering Problem (SRRP) zu lösen. Das SRRP ist ein kombinatorisches Zeitplanungsproblem, das sich mit Störungen eines bestehenden Arbeitsplans befasst, z. B. Krankenstand von Arbeitnehmer:innen oder Änderung des Personalbedarfs. Das Ziel des SRRPs ist es, einen neuen Arbeitsplan unter Berücksichtigung dieser Störungen zu erstellen und so wenige Änderungen wie möglich am ursprünglichen Plan vorzunehmen. Eine LNS besteht aus sich wiederholenden Anwendungen einer Zerstör- und einer Reparaturmethode. Zuerst hebt die Zerstörmethode die zugewiesenen Werte einer Teilmenge von Entscheidungsvariablen (Zerstörmenge) auf und fixiert die Werte der anderen Variablen. Danach versucht die Reperaturmethode, die vorherige Lösung durch das Suchen von besseren Werten für die Variablen aus der Zerstörmenge zu verbessern. Der Hauptbeitrag dieser Arbeit ist eine ML-basierte Zerstörmethode. Wir trainieren ein Conditional Generative Model, das eine Wahrscheinlichkeitsverteilung lernt. Diese Verteilung gibt an, welche Variablen in die Zerstörmenge aufgenommen werden sollten. Um hochwertige Zerstörmengen aus diesen Wahrscheinlichkeiten zu erstellen, präsentieren wir eine auf das SRRP zugeschnittene Strategie. Das verwendete Neuronale Netz ist ein Graph Neural Network (GNN), das als Eingabe einen Graphen verwendet, der eine SRRP-Instanz modelliert. Wir wenden Imitation Learning an, um das Neuronale Netz zu trainieren und dabei ein spezielles gemischt-ganzzahliges lineares Programm (MILP) nachzuahmen. Dieses MILP berechnet optimale Zerstörmengen. Es benötigt aber zu viel Zeit, um in tatsächlichen Anwendungen verwendet zu werden. Die Reparaturmethode unserer LNS besteht darin, ein vorgeschlagenes MILP für das SRRP zu lösen. Unsere ML-basierte LNS liefert mehr als doppelt so gute Resultate in Bezug auf die durchschnittliche Optimalitätslücke als das Lösen des SRRP-MILPs mit Gurobi. Sie übertrifft sogar die Ergebnisse einer leistungsstarken LNS, ausgestattet mit einer manuell gestalteten Zerstörmethode. Sehr bedeutungsvoll ist, dass die ML-basierte LNS auf unterschiedliche Zeitpläne mit unterschiedlicher Anzahl von Mitarbeitern generalisieren kann und auch die anderen Ansätze hierbei deutlich übertrifft.

We propose a large neighborhood search (LNS) enhanced with machine learning (ML) for the staff rerostering problem (SRRP). The SRRP is a combinatorial timetabling problem and deals with disruptions to an existing schedule, e.g., illness of employees or change in demand for staff. The goal of the SRRP is to construct a new schedule considering these disruptions and introducing as few changes as possible to the original schedule. An LNS consists of repeated applications of a destroy and a repair operator. First, the destroy operator induces a subproblem by unassigning a subset of decision variables (destroy set) and fixing the others. Then, by solving this subproblem, the repair operator tries to improve the previous solution by finding better assignments for the unassigned variables. The main contribution of this thesis is an ML-based destroy operator. We train a conditional generative model to estimate probabilities indicating which variables should be destroyed. We propose a refined sampling strategy tailored to the SRRP to build high-quality destroy sets from these probabilities. Our model is a graph neuralnetwork (GNN), which takes a custom graph modeling an SRRP instance as an input. To train our neural network, we apply imitation learning to mimic a mixed-integer linear program (MILP) based approach that can compute optimal destroy sets but is far too expensive to use in actual applications. We utilize an additional GNN to learn optimal parameters for the destroy set sampling process. The repair operator of our LNS consists of solving a proposed MILP. Our learning-based LNS outperforms solving the MILP with Gurobi by a factor greater than 2.65 in terms of optimality gap. It even surpasses the results of a well-performing LNS with a meaningful manually designed destroy operator in all respects. Most importantly, it generalizes to different schedules with various numbers of employees and also comfortably outperforms the other approaches on this test set.