… ist der Titel des 1. Platzes des Roland-Mittermeir-Preises 2015/2016 und wurde vom Förderverein Technische Fakultät mit EUR 1.500,–ausgezeichnet. Dem Autor und Preisträger, Herrn Dipl.-Ing. Benjamin Hackl, wurde der Preis im Rahmen des Festakts 10-jähriges Jubiläum der Fakultät für Technische Wissenschaften übergeben und die Arbeit wird hier kurz vorgestellt:

Zusammenfassung. Während sich die klassische Kombinatorik „nur“ mit dem Abzählen diskreter Objekte beschäftigt, interessieren wir uns im Rahmen der analytischen Kombinatorik für präzise Analysen des entsprechenden asymptotischen Verhaltens. In weniger technischen Worten sind wir also an einer möglichst genauen Charakterisierung des Wachstums von gewissen Klassen kombinatorischer Objekte interessiert. Für eine solche asymptotische Analyse werden Resultate aus einem breiten Spektrum von mathematischen Disziplinen, wie beispielsweise der klassischen Kombinatorik, der Funktionentheorie, und auch der Wahrscheinlichkeitstheorie verwendet.

Innerhalb dieser Masterarbeit spielen neben den im Titel angedeuteten Gitterpfaden auch Bäume, beides klassische diskrete Objekte mit zahllosen Anwendungen in verschiedenen na- turwissenschaftlichen und technischen Bereichen, eine zentrale Rolle. Die Arbeit ist in drei Kapitel gegliedert. In Kapitel 1, Preliminaries, geht es um die für die asymptotische Analy- se nötigen Grundlagen und Werkzeuge aus Kombinatorik (z.B. kombinatorische Klassen und erzeugende Funktionen), Funktionentheorie (Singularitätenanalyse, Mellin-Transformation), sowie Wahrscheinlichkeitstheorie (Grenzverteilungen, Martingale).

Mit Hilfe der in Kapitel 1 skizzierten Techniken geht es dann in Kapitel 2, Analysis of Lattice Paths, um die asymptotische Analyse von Gitterpfaden. Nach einer kurzen Einleitung in Ab- schnitt 2.1, in der die Terminologie geklärt wird, werden in den Abschnitten 2.2 sowie 2.3 di- verse elementare Gitterpfadklassen (Brücken, Mäander, Exkursionen) asymptotisch analysiert.

Abschnitt 2.4 bildet den Kern der Masterarbeit, in ihm werden sogenannte kulminierende Pfade untersucht. Das sind Gitterpfade mit Schritten ↗ und ↘, die auf minimaler Höhe starten und auf maximaler Höhe enden. Zu den wichtigsten Bausteinen dieser Analyse zählen die Erkenntnis, dass die wohlbekannten Chebyshev-Polynome eine zentrale Rolle spielen, sowie die asymptotische Entwicklung von Binomialkoeffizienten (2n,n−α) in einem zentralen Bereich. Neben Resultaten wie der asymptotischen Grenzverteilung und beliebig präzisen asymptotischen Entwicklungen für die Anzahl kulminierender Pfade gegebener Länge, wurde in diesem Kontext auch eine zahlentheoretische Vermutung von Zhao aus dem Jahr 2010 bewiesen.

Die Inhalte dieses Abschnittes wurden in einer geringfügig adaptierten Version 2016 in den Annals of Combinatorics publiziert.

In Kapitel 3, Analysis of Trees, liegt der Fokus schließlich auf der asymptotischen Analyse von Bäumen, wobei besonderer Wert auf das Aufzeigen der Zusammenhänge zwischen Gitterpfaden und Bäumen gelegt wird.

Zuletzt sei noch erwähnt, dass die aufwändigeren Berechnungen (insbesondere in Abschnitt 2.4) mit der Hilfe des quelloffenen Computermathematiksystems SageMath durchgeführt wurden. Der entsprechende Sourcecode findet sich in Anhang A der Arbeit. Im weiteren Umfeld der Arbeit bildete diese Implementation auch einen Teil der Motivation, ein Proposal für ein Google Summer of Code-Projekt einzureichen, welches genehmigt und erfolgreich von mir durch- geführt wurde, sodass ein Modul für asymptotische Entwicklungen mittlerweile zum Basisbestandteil von SageMath gehört.

Das Vehicle Routing Problem ist ein kombinatorisches Optimierungsproblem, welches ein breites Spektrum an Anwendungen im Bereich der Transportlogistik hat. Diverse Varianten kommen unter anderem bei der Planung von effizienten Liefertouren zum Einsatz. Eines der aktuell bekanntesten Anwendungsgebiete, das in der vorgelegten Arbeit im Detail betrachtet wird, findet sich im Online-Lebensmittelhandel. Hierbei wählt der Kunde auf der Website des Supermarktes ein Zeitfenster für die Zulieferung seines Einkaufes. Im Anschluss muss ein Lieferplan erstellt werden, der alle bisherigen Kundenbestellungen in ihren zugewiesenen Zeitfenstern enthält.

Das diesem Prozess zu Grunde liegende Optimierungsproblem ist das sogenannte capacitated Vehicle Routing Problem with Time Windows (cVRPTW). Es beschreibt die Herausforderung Routen ausgehend von einem Depot kosten-minimal zu planen. Die Ladekapazität der genutzten Lieferfahrzeuge und die maximale Fahrzeit der Fahrer darf hierbei nicht überschritten werden. Des weiteren muss jeder Kunde genau einmal innerhalb des ihm zugewie- senen Zeitfensters besucht werden.

Das cVRPTW gehört zur Klasse der NP-schweren Optimierungsprobleme. Für größere Probleminstanzen, wie sie in der Praxis auftreten, sind daher exakten Methoden, die stets die optimale Lösung liefern, nicht anwendbar. Da es die Online-Anwendung erfordert Lösungen in Echtzeit zu generieren, wurden im Rahmen dieser Arbeit nicht- exakte Methoden, sogenannte Heuristiken, entwickelt, mit deren Hilfe sehr gute Lösungen innerhalb kürzester Zeit gefunden werden können.

Die Basis unserer Methoden bilden lokale Suchheuristiken, welche die aktuelle Lösung mittels einfacher Ver- tauschoperationen iterativ verbessern. Bei der von uns betrachteten Anwendung besitzen die Zeitfenster, die als strukturierte Zeitfenster bezeichnet werden, spezielle Eigenschaften: Es wird angenommen, dass sich die Zeitfenster nicht überlappen und groß genug sind, damit mehrere Kunden innerhalb eines Zeitfensters besucht werden können. Diese Eigenschaften können ausgenutzt werden um den Suchraum der lokalen Operationen einzuschränken und somit unsere Heuristiken entscheidend zu beschleunigen.

Neben Lösungsqualität und Geschwindigkeit und der damit verbundenen ausgezeichneten Skalierbarkeit unserer Algorithmen, wurde von uns besonderer Wert auf die Flexibilität der entwickelten theoretischen Grundlagen gelegt. Dadurch können unsere Methoden jederzeit mit geringem Aufwand an eine Vielzahl von zusätzlichen spezifischen Bedingungen (sogenannte Business-Constraints), die es in der Praxis häufig und oftmals auch erst zu einem späteren Projektzeitpunkt zu berücksichtigen gilt, adaptiert werden.

Die vorgelegte Masterarbeit diente bisher als Ausgangspunkt mehrerer Konferenzvorträge und Publikationen. Bis dato sind zwei Konferenzpapiere entstanden, wobei eines davon bereits zur Veröffentlichung akzeptiert wurde [3] und das andere sich aktuell im Reviewprozess befindet [2]. Außerdem befindet sich derzeit ein Journalartikel [1] in Begutachtung, während ein weiterer Journalartikel in Kürze fertiggestellt wird.

Neben diesen akademischen Resultaten wurde die Praxisrelevanz der erarbeiten Ergebnisse bereits mehrfach unter Beweis gestellt. Die in dieser Arbeit entwickelten Methoden bilden die Grundlagen der Optimierungskom- ponente eines Systems für Online-Lebensmittelbestellungen, welches gemeinsam mit der britischen Firma Satalia für eine der weltweit größten Supermarktketten entwickelt wurde. Mit heutigem Tage befindet sich dieses System bereits in Betrieb und wird derzeit stufenweise in ganz Großbritannien eingeführt. Für weitere Details verweisen wir auf den folgenden, vor Kurzem veröffentlichten Artikel: http://tinyurl.com/cVRPsTW-article.

Literatur

[1] P. Hungerländer, K. Maier, J. Pöcher, A. Rendl, and C. Truden. Solving an on-line capacitated vehicle rou- ting problem with structured time windows. Technical Report TR-AAUK-M-O-16-12-30, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, 2016. A preprint is available from http://www.optimization-online.org/DB_HTML/2017/02/5859.html.

[2]  P. Hungerländer, A. Rendl, and C. Truden. On the slot optimization problem in on-line vehicle routing. Technical Report TR-AAUK-M-O-17-04-13, Alpen-Adria Universität Klagenfurt, Mathematics, Optimization Group, 2016. A preprint is available from http://www.optimization-online.org/DB_HTML/2017/04/ 5962.html.

[3]  P. Hungerländer, K. Maier, J. Pöcher, A. Rendl, and C. Truden. Solving an on-line capacitated vehicle routing problem with structured time windows. In Operations Research Proceedings 2016, 2017. Accepted, a preprint is available from http://www.optimization-online.org/DB_HTML/2016/12/5764.html.