Schriftenreihe Cottbus Mathematical Preprints
Dateiname: COMP-3-2019_GnegelFuegenschuh.pdf [Download]
Titel: An Iterative Graph Expansion Approach for the Scheduling and Routing of Airplanes
Autoren: Fabian Gnegel, Armin Fügenschuh
Zusammenfassung: A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. The task of optimally scheduling the airplanes and tour groups belongs to the class of vehicle routing problems with pickup and delivery and time-windows. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in order to model this problem as a mixed integer linear program. Most of the benchmark problems however could not be solved within a time limit of three hours, which was overcome by formulating the problem for a simplified (time-free) graph and the use of an incumbent callback to check for feasibility in the original graph. While this approach led to very good results for instances, where few time-free solutions were infeasible for the original problem, some instances remained unsolved. In order to overcome this problem we derive two new exact formulations that include time as variables. Although these formulations by themselves are not better than the approach from the literature, they allow for an effective construction of graphs which can be interpreted as intermediate graphs between the graph of airports and the expanded graph with vertices for each visit. Using similar relaxation techniques to the time-free approach and constructing these graphs based on solutions of the relaxations guarantees that only critical airports are expanded. A computational study was performed in order to compare the new formulations to the methods from the literature. Within a time limit of 3 hours the new approach was able to find proven optimal solutions for all previously unsolved benchmark instances. Furthermore the average computation time of all benchmark instances was reduced by 90 percent.
Schlüsselworte: Mixed Integer Linear Programming, Vehicle Routing Problem, Time-Dependent Airplane Routing, Dynamic Graph Expansion
MCS-Klassifikation: 90-XX Operations Research, Mathematical Programming
Datum der Veröffentlichung: 22. März 2019
Schriftenreihe (Bandnummer): Cottbus Mathematical Preprints COMP#3 (2019)
ISSN (Online): 2627-6100
ISSN (Print): 2627-4019
Lizenz: Creative Commons CC BY-NC-ND 3.0 DE - Namensnennung - Nicht-kommerziell - Keine Bearbeitung 3.0 Deutschland
Dateiname: COMP-2-2019_Werger.pdf [Download]
Titel: Eine Anwendung der ganzzahligen Optimierung auf die Stundenplanerstellung einer Unteroffiziersschule der Bundeswehr
Autor: Tabea Werger
Zusammenfassung: Die Bachelorarbeit beschäftigt sich mit der Erstellung eines möglichst guten, zulässigen Stundenplans für eine Unteroffiziersschule der Bundeswehr. Die Bildungseinrichtung kann vorhandene Optimierungsprogramme für Stundenpläne nur teilweise zu Rate ziehen, da hier im Vergleich zu normalen Schulen und Universitäten die Veranstaltungen nicht in einem Wochenzyklus stattfinden. Des Weiteren gibt es Spezialveranstaltungen, die nur an bestimmten Tagen besucht werden können. Zusätzlich haben die zu absolvierenden Kurse eine fest vorgegebene Reihenfolge, die beachtet werden muss.
Schlüsselworte: Mixed-Integer Programming, Operational Research, School Time Table Planning
MCS-Klassifikation: 90-XX Operations Research, Mathematical Programming
Datum der Veröffentlichung: 10. Februar 2019
Schriftenreihe (Bandnummer): Cottbus Mathematical Preprints COMP#2 (2019)
ISSN (Online): 2627-6100
ISSN (Print): 2627-4019
Lizenz: Creative Commons CC BY-NC-ND 3.0 DE - Namensnennung - Nicht-kommerziell - Keine Bearbeitung 3.0 Deutschland
Dateinamen: COMP-1-2019_Meier.pdf [Download], COMP-1-2019_Meier_Supplement.zip [Download]
Titel: Ein gemischt-ganzzahliger Ansatz zur gleichmäßigen Verkehrsauslastung eines Ballungsraums mittels Verschiebung der Schulanfangszeiten
Autor: Yvonne Meier
Zusammenfassung: Die Bachelorarbeit beschäftigt sich mit der gleichmäßigen Auslastung eines Ballungsraums durch die Verschiebung der Schulanfangszeiten. Ein solcher Ballungsraum entsteht immer dann, wenn sich viele Menschen gleichzeitig, meist nah beinander, innerhalb eines Systems bewegen. Insbesondere entsteht ein solcher Ballungsraum bei einem sogenannten Schülertransportproblem, d.h. der Aufgabe, Schüler innerhalb eines Systems zu einer bestimmten Zeit zu ihrer Schule zu transportieren. Die Staffelung der Schulanfangszeiten bietet eine Möglichkeit, dieses hohe Personenaufkommen gezielt zu kontrollieren und zu optimieren. Die gleichmäßigere Auslastung eines Systems beeinflusst auch die Belastung im öffentlichen Nahverkehr. Im Gegensatz zur Schaffung neuer Alternativen können so die vorhandenen Kapazitäten effizienter eingesetzt werden, ohne das Angebot zu reduzieren. Durch das geringere punktuelle Aufkommen von Fahrgästen kann der zur Verfügung stehende Fuhrpark wirksamer genutzt werden. Zusätzlich machen die zu den Stoßzeiten entlasteten Busse und Bahnen den öffentlichen Personennahverkehr für andere Zielgruppen attraktiver. Die Bachelorarbeit entwickelt einen gemischt-ganzzahliger Ansatz zur Realisation dieser Aufgabe. Ein Überblick über verschiedene Betrachtungsweisen und Modelle für Schülertransporte und der Optimierung von Personenaufkommen wird gegeben, und die notwendigen mathematischen Grundlagen, die für den Ansatz wichtig sind, werden vorgestellt. Im Anschluss werden die Modelle konzipiert und erläutert. Die Ergebnisse werden dargestellt und analysiert, worauf abschließend ein Ausblick über die behandelte Problematik folgt.
Schlüsselworte: Mixed-Integer Programming, Operational Research, School Bell Scheduling, Optimization of Public Transportation
MCS-Klassifikation: 90-XX Operations Research, Mathematical Programming
Datum der Veröffentlichung: 16. Januar 2019
Schriftenreihe (Bandnummer): Cottbus Mathematical Preprints COMP#1 (2019)
ISSN (Online): 2627-6100
ISSN (Print): 2627-4019
Lizenz: Creative Commons CC BY-NC-ND 3.0 DE - Namensnennung - Nicht-kommerziell - Keine Bearbeitung 3.0 Deutschland