Heuristic approaches for solving the interdependent lock scheduling problem

Abstract

In der vorliegenden Diplomarbeit wird das verflochtene Schleusenplanungsproblem (Interdependent Lock Scheduling Problem) präsentiert. Es ist ein komplexes Optimierungsproblem, bei dem Schiffe zu Schleusungen an aufeinanderfolgenden Staudämmen entlang ihrer Route zugewiesen werden. Innerhalb einer Schleusung muss darüber hinaus die Reihenfolge der Schiffe spezifiziert werden. Die Komplexität des Problems entsteht dabei durch die Abhängigkeit zwischen aufeinanderfolgenden Schleusungen am selben Staudamm und die Verflechtung zwischen Schleusungen an benachbarten Dämmen, welche dieselben Schiffe befördern. Nach einer detaillierten Beschreibung des Problems im Allgemeinen und der spezifischen Situation an der Donau in Österreich werden existierende Lösungsansätze für ähnliche oder verwandte Probleme analysiert. Mehrere deterministische und randomisierte Konstruktionsheuristiken, sowie verschiedene Nachbarschaftsstrukturen werden vorgestellt, die letztendlich in unterschiedlichen Metaheuristiken zur Anwendung kommen. Als Datenstruktur für den Schleusenplan dient dabei ein Abhängigkeitsgraph, der die Abhängigkeiten zwischen den einzelnen Schleusungen verwaltet und es somit erlaubt bei Änderungen am Plan Neuberechnungen auf ein notwendiges Minimum zu reduzieren. Um anpassbare VNS Konfigurationen jenseits von einfachen Variable Neighborhood Descent oder Token-Ring Neighborhood Search zu erstellen wird ein neues Framework namens Neighbourhood Search with Configurable Neighbourhood Iteration eingeführt. Konstruktionsheuristiken und unterschiedliche VNS Konfigurationen werden anhand von zwei vielfältigen Sets von Probleminstanzen getestet: kleine synthetische Testinstanzen und große Instanzen mit Echtdaten, die auf Basis von Verkehrsdaten ganzer Tage erstellt wurden. Experimente zeigen, das das Interdependent Lock Scheduling Problem mit heuristischen Verfahren effektiv und mit annehmbaren Ressourcenverbrauch gelöst werden kann.

This thesis introduces the Interdependent Lock Scheduling Problem. It is a complex optimization problem where ships need to be assigned to a lockage operation at consecutive water gates along their journey. Within a lockage operation, the order of ships has to be specified. The complexity of the problem arises from the interdependency between subsequent lockage operations at a single water gate and dependent operations at neighboring gates that serve the same ships. After a detailed description of the problem in general and of the specific situation at the Austrian Danube, an analysis of existing approaches to similar or related problems is conducted. Several deterministic and randomized construction heuristics are proposed as well as various neighborhoods structures that are eventually used in different metaheuristics. A dependency graph serves as backing data structure of the schedule, keeps track of the interdependence between lockage operations and allows to reduce the necessary recalculations when altering the schedule to the necessary minimum. To create highly customizable VNS configurations beyond simple Variable Neighborhood Descent or Token-Ring Neighborhood Search, a framework called Neighbourhood Search with Configurable Neighbourhood Iteration is introduced. Construction heuristics and different configurations of VNS are tested on two diverse sets of instances: small synthetic test instances and large real life instances that are build on a full days traffic information. Experiments show that the Interdependent Lock Scheduling Problem can be solved effectively with heuristic methods using a reasonable amount of computing resources.