Logistik. Teil 1. Optimierung des Flugverkehrs in Richtungen und Zeitplanbildung

Sicherlich musste jeder in einem halb leeren Flugzeug fliegen oder sich mit einem Flugtransfer treffen. Vielleicht haben Sie über die Kosteneffizienz und Effizienz eines solchen Fluges nachgedacht. Wie viel potenziellen Gewinn verliert die Fluggesellschaft? In der Tat sind Flüge unrentabel und manchmal sogar unrentabel. Können solche Entscheidungen mit dem optimalen Verhalten des Luftfahrtunternehmens erklärt werden? Zum Beispiel in der aktuellen Situation mit Flugstornierung aufgrund von COVID-19: Wie ist die Flotte in andere Richtungen verteilt, was eine lokale Rendite bietet? Versuchen wir, ein dynamisches Modell zu erstellen, das auf externe Veränderungen reagiert und sich bemüht, einen Gleichgewichtszustand zu erreichen. In diesem Artikel nehmen wir nur einen kleinen Satz von Parametern, versuchen die Nachfrage vorherzusagen, senden Flugzeuge mit geringerer Kapazität,Reduzieren Sie die Häufigkeit von Flügen, wenn dies unrentabel ist.



Auf den ersten Blick ist die Aufgabe dem „Rucksackproblem“ sehr ähnlich. In der Tat gibt es$$$n$ Flughäfen$$$a_{1}, a_{2}, .., a_{i}, .., a_{n}$ jeder der Flughäfen, bietet Platz$$$b_{1}, b_{2}, .., b_{i}, .., b_{n}$ Flugzeuge. Die Flugzeuge selbst sind von verschiedenen Typen$$$f_{1}, f_{2}, .., f_{j} .., f_{m}$ . Flugzeugwartungskosten$$$j$ Art in$$$i$ te Flughafenkosten in$$$z_{ij}$ und Gewinn$$$p_{j}$ . Finden Sie solche$$$x_{ij}$ ($$$x_{ij} \geqslant 0, x_{ij} \in \mathbb{Z}$$$$P$::

$$

$$max(P) = \sum_{j = 1}^{m} p_{j}x_{j}\; ; \;\;\; x_{j} = \sum_{i = 1}^{n} x_{ij}$$

und Gesamtkosten $$$Z$ für die Wartung von Flugzeugen an Flughäfen werden minimiert:

$$

$$min(Z) = \sum_{i = 1}^{n} \sum_{j = 1}^{m}z_{ij}x_{ij}$$

Mit Kapazitätsbeschränkungen für jeden Flughafen:

$$

$$\sum_{j = 1}^{m} x_{ij} \leqslant b_{i}$$

Berücksichtigen Sie nun, dass die Flughäfen durch Fluggesellschaften miteinander verbunden sind $$$r_{1}, r_{2}, .., r_{k}, .., r_{l}$. Dann muss die Anordnung von Flugzeugen an Flughäfen nicht nur unter Berücksichtigung ihres Typs durchgeführt werden, sondern auch unter Berücksichtigung der Flugrichtung, d. H. zunächst gesucht$$$x_{ij}$ jetzt werden $$$x_{ijk}$. Darüber hinaus können die Richtungen selbst zu beliebigen Routen kombiniert werden, auf denen die Bewegung von Flugzeugen stattfindet.

Modellbeschreibung

Offensichtlich hängt der Wert des gesamten Gewinns und Verlusts von einer ziemlich komplexen Airline-Strategie ab: den ausgewählten Flugzeugtypen, den erstellten Routen und den Flugplänen für jeden von ihnen. Um jedoch detaillierter über Strategien zu sprechen, müssen Sie viele Klarstellungen vornehmen.

Nachfrage nach Flugreisen

Einer der wichtigsten Parameter für die Entwicklung einer optimalen Strategie ist die Nachfrage nach Flugreisen zwischen einzelnen Städten, aber die gesammelten Daten erlauben keine verlässliche Vorstellung davon. Trotzdem sollten selbst unter solchen Bedingungen der Unsicherheit, wenn neue Informationen eintreffen, einige Maßnahmen ergriffen werden, um die Gewinne zu steigern und die Verluste zu verringern.

Einige indirekte Schlussfolgerungen über die Nachfrage nach einem bestimmten Ziel können auf der Grundlage von Daten über die Anzahl der durch dieses Ziel beförderten Passagiere gezogen werden. Wenn beispielsweise ein Flugzeug 5 Flüge in eine bestimmte Richtung durchgeführt hat und im Durchschnitt zu mehr als 90% ausgelastet war, können wir daraus schließen, dass die Nachfrage in dieser Richtung recht groß ist, und entscheiden, die Anzahl der Verkehrsteilnehmer in diese Richtung zu erhöhen. Wenn andererseits nach diesen fünf Flügen am sechsten die Anzahl der Passagiere stark zurückgegangen ist, wirkt sich dieser Faktor auf lange Sicht auf die „durchschnittliche“ Belegung aus und kann ein guter Grund für Anpassungen sein.

Der einfachste Weg, Entscheidungen auf der Grundlage solcher Zufallsdaten zu treffen, ist die Verwendung von gleitenden Durchschnitten. Das Problem ist jedoch, dass die Fluggesellschaft es sich nicht leisten kann, ihre Hypothesen zur Nachfrage experimentell zu testen. Wenn also nach einem Flug die Passagierlast des Flugzeugs stark zurückgegangen ist, wird dies bereits als Handlungssignal angesehen. In diesem Fall können Sie beispielsweise die Häufigkeit von Flügen in diese Richtung verringern und in einer anderen Richtung mit einer konstant hohen Auslastung erhöhen. Andererseits können wir aufgrund der Kenntnis der durchschnittlichen Auslastung der letzten 10 Flüge mehr oder weniger genau beurteilen, wie stabil die Auslastung des Flugzeugs in dieser Richtung ist. Wenn der Wert der durchschnittlichen Belegungsrate stetig abnimmt, kann dies als Signal für ernsthaftere Maßnahmen dienen, z.Ersetzen eines Flugzeugs durch ein Flugzeug mit geringerer Kapazität, eine dramatischere Änderung der Route des Flugzeugs oder Ersetzen des Flugzeugs und gleichzeitiges Ändern seiner Route.

Um ein Modell zu erstellen, nehmen wir an, dass der Wert der tatsächlichen Nachfrage in jeder Richtung eine Zufallsvariable ist $$$q_{ijt} = \xi(t)$ und kann Werte aus dem Intervall übernehmen $$$[0, q_{ij, max}]$mit der gleichen Wahrscheinlichkeit. Angenommen, ein Flugzeug mit maximaler Kapazität läuft in diese Richtung$$$d_{j,max}$offensichtlich das wenn $$$q_{ijt}$ viel mehr als $$$d_{j,max}$, dann wird das Flugzeug höchstwahrscheinlich fast voll sein. Angenommen, der Wert ist möglich, damit der Modellierungsprozess möglich ist$$$q_{ij, max}$in jeder Richtung kann grob geschätzt werden, zum Beispiel durch die Größe der Städte, die durch diese Richtung verbunden sind. Wir gehen auch davon aus, dass zur Untersuchung des Verhaltens des Modells dieser Wert geändert, aber nicht vorhergesagt werden kann.

Gewinn- und Verlustrechnung für jedes einzelne Flugzeug

Die Wartungskosten jedes Flugzeugs können durch das Verhältnis bestimmt werden:

$$

$$z_{ij}(t) = c_{ij}\Delta t + c_{0ij}$$

Dieses Verhältnis zeigt, dass die Kosten für die Wartung eines Flugzeugtyps $$$f_{j}$ am Flughafen $$$a_{i}$hängen von der Zeit seines Aufenthalts an diesem Flughafen ab. Es gibt eine feste Gebühr$$$c_{0ij}$die für Start und Landung berechnet werden kann. In Zukunft erhöht sich diese feste Gebühr proportional zum Koeffizienten$$$c_{ij}$. Dieses Verhältnis erlaubt kein "Einfrieren" einzelner Flugzeuge an einigen Flughäfen, d. H. spiegelt ein sehr wichtiges Merkmal der Realität wider: " Untätigkeit von Flugzeugen = Verluste ".

Da es sich um einzelne Ebenen handelt, führen wir einen weiteren Index ein, um jede einzelne eindeutig zu identifizieren$$$x = \overline{0, g}$ Wo $$$g = \sum x_{ijk}$. Dann kann der Gewinn für jedes einzelne Flugzeug nach folgender Formel berechnet werden:

$$

$$p_{ijkx} = d_{ijkx}s_{jk} - \beta_{j} \Delta t_{jk}$$

Wert $$$d_{ijkx}$ bestimmt, wie voll die Ebene mit dem Index $ x $ unter natürlichen Einschränkungen ist $$$d_{ijkx} \leqslant d_{j,max}$Dies zeigt, dass die Fülle des Flugzeugs seine maximale Kapazität nicht überschreiten kann. Die Kosten für ein Ticket in die Richtung$$$r_{k}$ Mit dem Flugzeug $$$f_{j}$ wird eingestellt von $$$s_{jk}$. Darüber hinaus berücksichtigt diese Formel, dass die Kosten eines Fluges auch vom Flugzeugtyp und der Zeit abhängen, die für die Durchführung des Fluges benötigt wird:$$$\beta_{j}$ Ist ein Koeffizient, der die Kosten pro Zeiteinheit eines Fluges vom Typ Flugzeug bestimmt $$$f_{j}$, und $$$\Delta t_{jk}$ - Dies ist die Zeit, die dieser Flugzeugtyp benötigt, um die Richtung zu überwinden $$$r_{k}$.

Wenn Sie die Route des Flugzeugs als bezeichnen$$$R_{x} = (r_{1},r_{2},..r_{k})$Dann werden der Gesamtgewinn und die Gesamtkosten aller darin enthaltenen Flüge als erfasst

$$

$$P_{R_{x}} = \sum_{k}(d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk}) \; ; \;\;\;\;\;\;\; Z_{R_{x}} = \sum_{k}(c_{ij} \Delta t_{ijkx} + c_{0ij})$$

Wo $$$k$ läuft durch die Indizes aller in der Route enthaltenen Richtungen und $$$\Delta t_{ijkx}$- Dies ist die Verspätungszeit des Flugzeugs auf jeder Flughafenroute. Dann können der Gesamtgewinn und die Gesamtkosten aller Flugzeuge durch die folgenden Formeln berechnet werden:

$$

$$P = \sum_{x}\sum_{k}(d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk}) \; ; \;\;\;\;\;\;\; Z = \sum_{x}\sum_{k}(c_{ij} \Delta t_{ijkx} + c_{0ij})$$

Wenn andererseits alle Informationen über die Strecken aller Flugzeuge verfügbar sind, können der Gesamtgewinn und die Gesamtkosten anhand der folgenden Formeln berechnet werden:

$$

$$P = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (d_{ijkx}s_{jk}-\beta_{j} \Delta t_{jk})\; ; \;\;\;\;\;Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (w_{ij} \Delta t_{ijkx} + w_{0ij})$$

Verwaltungskosten

Die Ausdrücke zur Berechnung von Gewinnen und Kosten sind möglicherweise bereits für die Modellierung geeignet, berücksichtigen jedoch nicht die wichtige Tatsache, dass sich nach einigen Kontrollmaßnahmen die Funktionsweise des gesamten Systems ändert und die Umstrukturierung des gesamten Systems nicht sofort erfolgen kann. Darüber hinaus sollte verstanden werden, dass die Kontrollaktion selbst nicht „magisch“ sein kann, d. H. Wir können keine Flugzeuge teleportieren, sie tagelang fliegen lassen usw. Um den Flugplan eines Flugzeugs mit dem Flugplan anderer Flugzeuge zu synchronisieren, können Sie den Abflug entweder verzögern oder verzögern. Wenn das Flugzeug in dem Moment, in dem die Kontrollaktion angewendet wurde, in der Luft gefangen wurde, müssen wir noch warten, bis es landet.



In Fällen, in denen das Flugzeug in dem Moment, in dem die Steueraktion angewendet wird, an einem der Flughäfen einfängt, tritt eine weitere Einschränkung auf - die Unfähigkeit, das Flugzeug unmittelbar nach der Landung zum Abheben zu zwingen. Für jeden Flugzeugtyp muss eine Mindestzeit am Flughafen verbracht werden$$$\Delta t_{ij,min}$erforderlich für die obligatorische Wartung des Flugzeugs (Auftanken, Reinigen der Kabine usw.)

$$

$$\Delta t_{ijkx} \geqslant \Delta t_{ij,min}$$

Dies bedeutet, dass der Moment der Anwendung der Steueraktion immer noch mit dem Moment der Landung korreliert werden muss.



Nach dem Anwenden der Steueraktion fliegen die Flugzeuge erneut nach einem klaren, periodischen Zeitplan, d.h. Die Zeit, die das Flugzeug am Flughafen verbringt und mit deren Hilfe der Flugplan angepasst wird, kann von allen nachfolgenden gleichen Zeitintervallen abweichen. Dies bedeutet, dass die mit der Kontrollmaßnahme verbundenen Kosten auch von allen nachfolgenden Kosten abweichen können und separate Berechnungen erfordern. Da die Steueraktion immer mit dem Moment der Flugzeuglandung korreliert, können wir dieses Zeitintervall als festlegen$$$\Delta t_{0, ijkx}$ und bestimmen Sie die damit verbundenen Kosten anhand der bekannten Formel

$$

$$z_{ij}(t) = c_{ij}\Delta t_{0, ijkx} + c_{0ij}$$

Die Formel zur Berechnung der Gesamtkosten für alle Flugzeuge ändert sich ebenfalls nicht wesentlich.

$$

$$Z = \sum_{i = 1}^{m} \sum_{j = 1}^{n} \sum_{k = 1}^{l} \sum_{x=1}^{x_{ijk}} (w_{ij} \Delta t_{0, ijkx} + w_{0ij})$$

Flugzeugrouten

Eine sehr wichtige Anforderung für Flugzeugrouten ist die Zyklizität. Diese Anforderung mag unangemessen erscheinen, da eine enge Bindung von Flugzeugen an solche Strecken nachteilig sein kann. Diese Anforderung verpflichtet Flugzeuge jedoch nicht, den gesamten Zyklus zu umgehen. Diese Anforderung ändert auch nichts an der Tatsache, dass der Status des Systems immer noch in zwei Stufen unterteilt ist - "vor" und "nach" der Anwendung der Steueraktion. Dies bedeutet, dass, wenn Änderungen im System aufgetreten sind, beispielsweise die Nachfrage sich in eine der Richtungen geändert hat, eine der Ebenen verzögert oder vollständig unterbrochen wurde (verschwunden ist), nur eine Steueraktion ausgeführt wird, d. H. Alle Flugzeuge beginnen ihre Routen erst nach Abschluss zyklisch auszuführen. Wenn Routenänderungen nach jeder Kontrollaktion sehr häufig auftreten,dann wird es keine Zyklizität auf den Strecken von Flugzeugen geben. Wenn andererseits nach einer gewissen Optimierung die Steuerung der Routenänderungen nicht mehr erfolgt, bedeutet dies, dass das System selbst seinen optimalen und stationären Zustand beibehält.

Das Erfordernis, dass alle Routen zyklisch sein müssen, kann auch durch die Tatsache gerechtfertigt werden, dass keinerlei Informationen über die Notwendigkeit zukünftiger Routenänderungen vorliegen, dh es kann sich herausstellen, dass das Flugzeug ohne eine einzige Anpassung eine beliebige Zeitspanne entlang einer bestimmten Route fliegen wird. Wenn diese Route kein Zyklus ist, hört sie bei einer Iteration auf, sich zu bewegen. Dies bedeutet, dass bei jeder Iteration solche Stopps für jedes Flugzeug verfolgt und einige Entscheidungen über deren weitere Bewegung getroffen werden müssen.

Zusätzlich zu all dem gibt es eine weitere wichtige Anforderung für Routen und Flugpläne - der maximale gleichzeitige Aufenthalt von Flugzeugen an jedem Flughafen sollte ihre Kapazität nicht überschreiten. Daher ist es nach der Erstellung der Route erforderlich, einen Zeitplan zu erstellen, der gewährleisten kann, dass zu keinem Zeitpunkt an einem Flughafen mehr Flugzeuge vorhanden sind, als er aufnehmen kann. Wenn die Flugzeuge sehr lange Routen haben, die keine Zyklen sind, müssen Sie die Anzahl der Flugzeuge an jedem Flughafen dieser Route berechnen. Diese Berechnungen beziehen sich auf die Routen und Flugpläne anderer Flugzeuge. Wenn Flugzeuge hingegen zyklische Routen mit einem bekannten Zeitraum umgehen und die Häufigkeit der Besuche an jedem Flughafen kennen, können Sie sehr einfach Flugpläne erstellen.Dies führt nicht zu Kapazitätsüberschreitungen.

Da es eine strikte Anforderung gibt, dass Routen Zyklen sein müssen, wird klar, dass alle Routen aus einfachen Zyklen eines gerichteten Graphen bestehen müssen, der das Netzwerk modelliert. Um dies zu demonstrieren, werden wir vier Flughäfen darstellen, die wie folgt miteinander verbunden sind:



Diese Grafik besteht aus sechs einfachen Zyklen:$$$(a_{1},a_{2})$, $$$(a_{2},a_{3})$, $$$(a_{3},a_{4})$, $$$(a_{2},a_{4})$, $$$(a_{2},a_{3},a_{4})$, $$$(a_{2},a_{4},a_{3})$. Zyklen, die durch zyklische Verschiebung ihrer Eckpunkte erhalten werden, werden als äquivalent betrachtet. Beispielsweise sind Zyklen äquivalent:$$$(a_{2},a_{4},a_{3})$, $$$(a_{4},a_{3},a_{2})$ und $$$(a_{3},a_{2},a_{4})$.

Wenn jedoch bekannt ist, dass sich ein bestimmtes Flugzeug an einem bestimmten Flughafen befindet, wird die Reihenfolge der Spitzen auf seiner Route wichtig. Das Routing für ein bestimmtes Flugzeug an einem bestimmten Flughafen erfolgt durch Kombinieren von Elementarzyklen, einschließlich einiger Zyklen in anderen, oder durch Eliminieren dieser Zyklen, wenn die Route bereits interne Zyklen enthält.

Betrachten Sie ein einfaches Beispiel, nehmen wir an, ein Flugzeug befindet sich am Flughafen$$$a_{3}$dann kann es in einem von zwei einfachen Zyklen fliegen: $$$(a_{3},a_{2})$ und $$$(a_{3},a_{2},a_{4})$. Zyklus$$$(a_{3},a_{2})$ kann mit einem Zyklus kombiniert werden $$$(a_{1},a_{2})$Das Ergebnis ist ein Zyklus $$$(a_{3},a_{2},a_{1},a_{2})$. Gleicher Zyklus$$$(a_{1},a_{2})$ kann in den Zyklus aufgenommen werden $$$(a_{3},a_{2},a_{4})$ ergebend $$$(a_{3},a_{2},a_{1},a_{2},a_{4})$.

Angenommen, das Flugzeug befindet sich am Flughafen$$$a_{3}$wird durch die Route radeln $$$R_{1}=(a_{3},a_{2},a_{1},a_{2},a_{4})$, aber in diesem Fall ist die Nachfrage in den Richtungen nicht befriedigt $$$(a_{4},a_{2})$, $$$(a_{3},a_{4})$ und $$$(a_{2},a_{3})$ Dies bedeutet, dass Sie der Route Ihres vorhandenen Flugzeugs einen weiteren einfachen Zyklus hinzufügen können $$$(a_{3},a_{4},a_{2})$ und bekomme $$$(a_{3},a_{2},a_{1},a_{2},a_{4},a_{3},a_{4},a_{2})$ oder fügen Sie ein anderes Flugzeug hinzu, das die Route durchläuft $$$R_{2} = (a_{3},a_{4},a_{2})$.

Hier lohnt es sich, einige Klarstellungen zu den Konzepten „Ändern“ und „Ersetzen“ von Routen vorzunehmen. Wenn Sie eine Route ändern, müssen Sie sie ändern, indem Sie die Anzahl ihrer internen Elementarzyklen erhöhen oder verringern. Zum Ersetzen einer Route müssen die Elementarzyklen selbst ersetzt werden.
Offensichtlich können sich Flugzeugrouten überlappen, und dies vorzugsweise in den Teilen des Netzwerks, in denen eine besonders hohe Nachfrage besteht.

Alle einfachen Graphzyklen können mit dem Johnson-Algorithmus ermittelt werden, dessen Komplexität gleich ist$$$O((n+e)(c+1))$wo $$$n$ - Anzahl der Eckpunkte $$$e$ - die Anzahl der Rippen und $$$c$- die Anzahl der Elementarketten. In Zukunft sollten Sie die Routen des Flugzeugs ändern, indem Sie überprüfen, ob die Kanten festgelegt sind. aus denen sie bestehen$$$R_{x}$fiel mit der Menge der Kanten des gesamten Diagramms zusammen $$$E$d.h. wenn die Gesamtzahl der Flugzeuge ist$$$g$, dann sollte die Gleichheit erfüllt sein:

$$

$$\bigcup_{x = 1}^{g} R_{x} = E$$

Einhaltung der Flughafenkapazitätsgrenze

Neben der Tatsache, dass der erstellte Zeitplan den Durchsatz in jeder Richtung beeinflusst, wirkt er sich auch auf die Anzahl der Flugzeuge aus, die gleichzeitig am Flughafen sein können. Stellen Sie sich der Einfachheit halber vor, dass ein bestimmter Flughafen nur zwei Flugzeuge gleichzeitig akzeptieren kann, dieser Flughafen jedoch in den Routen von drei Flugzeugen enthalten ist. Offensichtlich müssen einige strenge Bedingungen erfüllt sein, um die Grenze einzuhalten.

Zunächst werden wir versuchen, einen allgemeinen Ansatz zu bestimmen, der die Tatsache berücksichtigt, dass Flugzeuge ihre Routen zyklisch mit einem bestimmten Zeitraum ausführen und dass Flugplananpassungen nur mit Hilfe einer Steueraktion möglich sind, die mit der Änderung der Abflugzeit des Flugzeugs verbunden ist.



Die rote gestrichelte Linie zeigt den Moment an, in dem das System den optimalen stationären Zustand erreicht. Alles, was bis zu dieser Zeile ist, kann als Zeitintervall betrachtet werden, in dem die Steueraktion ausgeführt wird. In diesem Fall wird gezeigt, wie die Zeitintervalle geändert werden$$$t_{0,1}$ und $$$t_{0,2}$Sie können die Zeiträume steuern, in denen zwei Flugzeuge denselben Flughafen besuchen. Die Abbildung zeigt, dass das Flugzeug eine andere Zeit am Flughafen verbringt, sich diese Zeitintervalle jedoch nicht überschneiden. Dies ist nur möglich, wenn ihre Perioden gleich sind oder wenn das kleinste gemeinsame Vielfache dieser Perioden gleich einer der Perioden ist.

Wenn zum Beispiel die Zeiträume für den Besuch des Flughafens mit zwei Flugzeugen 200 und 600 Stunden betragen, kann deren Versatz relativ zueinander gewählt werden, so dass sie niemals gleichzeitig den Flughafen besuchen. Wenn ihre Zeiträume jedoch 300 und 700 Stunden betragen, werden sie früher oder später zur gleichen Zeit am Flughafen ankommen, unabhängig davon, wie sie relativ zueinander verschoben sind.

Es ist jedoch auch offensichtlich, dass die Steueraktion so sein kann, dass diese Bedingung erfüllt ist, die Intervalle sich jedoch immer noch überschneiden können, was bedeutet, dass die folgenden Bedingungen erfüllt sind (Buchstabe) $$$a$ im Index bedeutet, dass das Flugzeug zum Flughafen geflogen ist; $$$d$ - vom Flughafen geflogen):

$$

$$\left\{\begin{matrix} t_{1,a} \leqslant t_{2,d} \\ t_{1,d} \geqslant t_{2,a} \end{matrix}\right.$$

Wenn der Flughafen eine Kapazität von 2 Flugzeugen hat, diese jedoch in der Route von drei Flugzeugen enthalten ist, bedeutet die paarweise Erfüllung dieser Bedingungen für alle drei Flugzeuge gleichzeitig, dass das Limit überschritten wird.

Wenn andererseits zwei Flugzeuge Zeiträume haben, die nicht zu ihrem gleichzeitigen Aufenthalt am Flughafen führen, kann das dritte Flugzeug einen beliebigen Zeitraum haben. In diesem Fall ist es jedoch unbedingt erforderlich, dass die Anforderung, dass seine Zeit am Flughafen strikt kürzer ist als das Zeitintervall, in dem die beiden vorherigen Flugzeuge am Flughafen abwesend sind, erfüllt ist.

Dies führt zu zwei einfachen Regeln für die Einhaltung der Flughafenkapazitätsgrenze:

1. Wenn die Flughafenkapazität ist $$$n$dann sollten die Aufenthaltszeiten des Flugzeugs unterteilt werden in $$$n$ . .
2. $$$n$ .

Die strikte Erfüllung dieser Bedingungen kann nur in einem Fall gerechtfertigt werden, wenn mit Sicherheit bekannt ist, dass in Zukunft keine Kontrollmaßnahmen zu erwarten sind. Da es jedoch keine solchen Garantien gibt, können diese Bedingungen etwas geschwächt sein. Darüber hinaus kann die strikte Erfüllung dieser Bedingungen sehr große Verzögerungen des Flugzeugs erfordern, die zum Verschieben von Perioden erforderlich sind, d. H. erweisen sich als sehr teuer. Daher können diese Bedingungen so angepasst werden, dass die Kapazitätsgrenze erst nach einer akzeptablen Zeitspanne überschritten wird, wonach die nächste Zeitplananpassung vorgenommen werden kann. Es gibt jedoch keine Garantie dafür, dass eine solche schrittweise Anpassung immer zu einer Reduzierung der Anpassungskosten führt. All dies deutet darauf hin, dass diese Regeln als Grundlage für komplexere Regeln dienen können.Sie können beispielsweise die Flugpläne von Flugzeugen anpassen, deren Route sich geändert hat, unter den Flugplänen von Flugzeugen, deren Routen unverändert geblieben sind, oder die Kosten für Kombinationen verschiedener aufeinanderfolgender Anpassungen berechnen und die beste auswählen.

Der Modellierungsprozess und die optimale Entscheidungsfindung

Angenommen, zu Beginn sind die Ebenen in einer zufälligen oder vorbestimmten Reihenfolge angeordnet. Da zum ersten Zeitpunkt keine Informationen über die Anzahl der beförderten Passagiere vorliegen, erfolgt in der Anfangsphase eine „Aufklärung der Situation“. In diesem Stadium muss vor Beginn des Simulationsprozesses jedem Flugzeug eine bestimmte Route zugewiesen werden. Offensichtlich sollten alle diese Routen das gesamte Flughafennetz abdecken und dazu beitragen, dass alle Bewegungen zwischen Flughäfen in Bezug auf die Beladung optimal ausgeführt werden.

Der Optimierungsprozess für einige Flugzeuge kann gestartet werden, sobald die Lastwerte in alle Richtungen ihrer Route bekannt sind. Nur zu diesem Zeitpunkt ist es möglich, die Gewinn- und Kostenwerte dieses Flugzeugs auf dieser Route zu berechnen, die für den Optimierungsprozess verwendet werden können. Wenn eine solche Änderung der Route und des Zeitplans möglich ist, die die bekannten Gewinne erhöht und die Kosten senkt, werden sie die vorherigen ersetzen.

Flugzeugrouten können nicht ersetzt werden, bevor alle Workload-Werte in jeder Richtung bekannt gegeben wurden, da dies nicht die Beurteilung des Gesamtgewinns und der Gesamtkosten ermöglicht. Erst wenn alle Workload-Werte in jeder Richtung bekannt sind, können Sie nicht nur die Routen und Flugpläne einzelner Flugzeuge ändern, sondern auch Änderungen in der allgemeinen Transportplanung.

Wir weisen jeder Richtung ein Array zu.$$$W_{ij}$ eine bestimmte Länge (zum Beispiel 5), in die die Belegungswerte der Passagiere jedes Flugzeugs eingegeben werden $$$w_{ijt}$wer machte einen Flug in diese Richtung. Dieses Array ist ein Stapel solcher Werte. Der letzte Wert in diesem Array - die Überlastung des vorherigen Flugs - ermöglicht es uns, Schlussfolgerungen über die Notwendigkeit kleiner taktischer Maßnahmen zu ziehen, und der Durchschnittswert über das gesamte Array wird als Indikator für die Notwendigkeit ernsthafter strategischer Anpassungen dienen.

Wenn der letzte Wert des Arrays$$$W_{ij}$ geht über ein bestimmtes Intervall hinaus $$$w_{ij, min} \leqslant w_{ijt} \leqslant w_{ij, max}$Um die Angemessenheit von Änderungen zu bestimmen, werden geeignete Maßnahmen ergriffen, um die Häufigkeit von Flügen in diese Richtung zu verringern oder zu erhöhen. Zur gleichen Zeit, wenn nach dem Verringern oder Erhöhen der Häufigkeit von Flügen in diese Richtung der Wert$$$\overline{W}_{ij}$Wenn es ohnehin weiter abnimmt oder wächst, kann dies ein Signal dafür sein, dass grundlegendere Änderungen erforderlich sind, beispielsweise die Aufnahme einer bestimmten Richtung in die Routen mehrerer Flugzeuge oder der Ausschluss dieser Richtung von den Routen aller Flugzeuge.

Angenommen, ein Flugzeug fliegt entlang einer zyklischen Route$$$(a_{1},a_{2},a_{3},a_{2})$. Nehmen Sie die nächste Abfahrt vom Flughafen an$$$a_{1}$Die Zahl der Passagiere im Flugzeug ging stark zurück. In diesem Fall bei Ankunft am Flughafen$$$a_{2}$ Es kann eine Entscheidung getroffen werden, die Route zu ändern $$$(a_{1},a_{2},a_{3},a_{2})$ auf der $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2})$. Ein solcher Ersatz ist insofern nützlich, als die Nachfrage in die Richtung sinkt$$$(a_{1},a_{2})$ist kein Unfall, sondern ein stetiger Trend, dann wird zumindest die Häufigkeit von Flügen in diese Richtung abnehmen. Wenn sich beim nächsten Besuch dieses Ziels herausstellte, dass die Anzahl der beförderten Passagiere so gering oder sogar noch geringer war, dann die Route$$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2})$ kann wieder auf Route geändert werden $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2},a_{3},a_{2})$Dies reduziert die Häufigkeit von Besuchsanweisungen $$$(a_{1},a_{2})$noch stärker. Wenn die Richtung$$$(a_{1},a_{2})$ weiterhin stetig abnehmen, können Sie in der Regel die Route ersetzen $$$(a_{1},a_{2},a_{3},a_{2},a_{3},a_{2},a_{3},a_{2})$ auf der $$$(a_{3},a_{2})$ oder jede andere Route, die keine Anweisungen enthält $$$(a_{1},a_{2})$.

All dies kann anhand des folgenden Schemas demonstriert werden, das zeigt, wie sich die Häufigkeit des Besuchs eines Ziels ändert, dessen Rentabilität stark verringert ist:


Ein Indikator zur Verringerung der Häufigkeit von Flügen in einem Ziel$$$(a_{1},a_{2})$ dient der Bedeutung $$$w_{1,2}$Jedes Mal, wenn es weniger als 50 wird, wird die Entscheidung getroffen, diese Richtung mit weniger Häufigkeit zu besuchen. Nach dem Wert$$$\overline{W}_{ij}$Wenn der Mindestwert des zulässigen Intervalls unterschritten wird, ist diese Richtung im Allgemeinen von der Route des Flugzeugs ausgeschlossen.

Außerdem können Sie für jeden Flugzeugtyp Ihr ​​zulässiges Intervall für den Durchschnittswert der Array-Elemente bestimmen$$$W_{ij}$. Wenn dieser Wert in dem akzeptablen Intervall für einen bestimmten Flugzeugtyp enthalten ist, jedoch nicht für ein Flugzeug, das bereits entlang des Flugzeugs fliegt, werden sukzessive Routenänderungen vorgenommen, die dazu führen, dass Flugzeugtypen durch geeignetere ersetzt werden.

Es scheint, dass sich im Laufe der Zeit alle Flugzeuge auf nur eine, die rentabelste Route konzentrieren werden, sobald sich alle Durchschnittswerte der Anzahl der Passagiere in jeder Richtung im Gleichgewicht befinden. Dies wäre in der Tat der Fall, wenn die Kapazität jedes Flughafens unbegrenzt wäre. Aber aufgrund der Tatsache, dass jeder Flughafen eine Kapazität hat$$$b_{i}$Einige Flugzeuge müssen auf weniger profitablen Strecken fliegen. Offensichtlich ist es sinnvoll, Maßnahmen zur Optimierung eines oder mehrerer Flugzeuge erst nach Änderungen durchzuführen$$$w_{ijt}$ oder wie etwas Wert $$$\overline{W}_{ij}$wechselt von einem Intervall zum anderen. All dies kann wie folgt dargestellt werden:



Dieses Diagramm zeigt, wie Routen für fünf Flugzeuge von vier verschiedenen Typen (mit unterschiedlichen Kapazitäten) geändert werden. Anfangs führen einige Flugzeuge nicht die rentabelsten Flüge durch, aber wenn mehr Informationen über die beförderten Passagiere erscheinen, ändern sich ihre Routen, um ihren Kapazitäten am besten zu entsprechen. Letztendlich wird ein Gleichgewichtszustand erreicht, in dem jede Ebene den größten Gewinn bringt, d.h. läuft auf seinen Strecken mit der höchstmöglichen Frequenz. Die Kapazität der Flughäfen wird ebenfalls berücksichtigt, wodurch sich die Strecken nicht vollständig überschneiden können.

Es stellt sich eine sehr wichtige Frage: Wie findet man ein optimierendes Aktionssystem? Diese Frage steht in direktem Zusammenhang mit der globalen Optimierung, d. H. Sie müssen solche Kombinationen von Flugzeugrouten, deren Typen und Flugplänen auswählen, bei denen der Gesamtgewinn maximal und die Kosten minimal sind. Wenn wir nur über Flugzeuge und ihre Routen sprechen würden, wäre selbst in diesem Fall der Lösungssuchbereich extrem groß, da die Größe des Bereichs von der Anzahl der einfachen Zyklen im Flughafennetz faktoriell und exponentiell von der Anzahl der Flugzeuge abhängt. Da die Routen unterschiedlich lang sein können und eine unterschiedliche Anzahl interner Zyklen enthalten, sieht die optimistischste Schätzung der Größe des Lösungsraums so aus$$$(n!)^m$wo $$$n$ Ist die Anzahl der einfachen Zyklen und $$$m$- die Anzahl der Flugzeuge. Durch die Hinzufügung von Kombinationen von Flugzeugtypen und deren Flugplänen wird der Entscheidungsraum faktoriell noch größer.

Natürlich ist die Suche nach optimalen Aktionen nur mit Hilfe von metaheuristischen Algorithmen möglich, und diese Suche wird nach einer starken Änderung der Anzahl der besetzten Sitze eines einzelnen Flugzeugs durchgeführt, was ziemlich häufig vorkommen kann. Der Optimierungsprozess ist zweistufig: Zuerst wird die Suche nach optimalen Routen für jeden Flugzeugtyp durchgeführt, dann werden deren Flugpläne optimiert. Gleichzeitig kann die Zeitplanoptimierung ein absolut deterministischer Prozess sein, und dank der Kenntnis der Anzahl der Passagiere, die in getrennten einfachen Zyklen befördert werden, kann das Ändern oder Ersetzen von Routen durch optimalere Routen viel schneller erfolgen als das einfache Aussortieren. Sie sollten sich jedoch auch an die möglichen lokalen Maxima und Minima erinnern, z. B. an die Route mit dem höchsten Belastungsgrad, d. H.Die rentabelsten erfordern möglicherweise Flugpläne mit sehr langen Verspätungen an Flughäfen, d. h. erhöhen die Kosten für die Wartung stark.

Die folgende Frage stellt sich: "Welche Metaheuristik sollte ich wählen: Ameise, simuliertes Tempern oder evolutionär?" Der Ant-Algorithmus ist gut in der Suche nach profitablen Routen, aber in einem bestimmten Stadium der Modellierung verschwindet die Notwendigkeit für diese Suche und eine andere erscheint - das Ändern und Ersetzen von Routen und nicht unbedingt mit der größten Passagierlast.
Der evolutionäre Algorithmus garantiert nicht das Erreichen des globalen Maximums und ist gleichzeitig durch die Regeln der Mutations- und Kreuzungsprozesse sehr kompliziert.
Einige vorteilhafte Teile der Routen können bei der nächsten Iteration durch eine Mutation zerstört oder nicht mit profitablen Teilen anderer Bevölkerungsmitglieder gekreuzt werden. Die Dimension des Problems ist jedoch nicht so groß, dass es sehr schwierig wäre, dies tatsächlich als Tatsache vorherzusagen und vorherzusagen, wie sich dieser Algorithmus verhalten wird.

Die einfachste und vielversprechendste Methode zur Suche nach optimalen Aktionen ist ein Annealing-Simulationsalgorithmus. Die Implementierung und Konfiguration von Parametern ist sehr einfach. Mit diesem Algorithmus können Sie auch verschiedene empirische Richtlinien anwenden, um optimalere Routen zu generieren. Beispielsweise können die rentabelsten einfachen Routenzyklen schneller abkühlen als weniger vorteilhafte, d. H. kleinere Änderungen vornehmen, die zur schnellsten Konvergenz beitragen.

Fazit

Das betrachtete Problem ist natürlich nur die Spitze des Eisbergs, und das erstellte Modell ist nichts anderes als die Grundlage für weitere Forschungen in den nächsten Teilen der Artikelserie. Zum Beispiel müssen Sie berücksichtigen, dass es auf dem zivilen Luftverkehrsmarkt viele Fluggesellschaften gibt, d. H. sie müssen miteinander konkurrieren. Im Modell wird die Nachfrage durch eine absolut zufällige Variable dargestellt, tatsächlich sollte sie jedoch in gewisser Weise von der Preispolitik der Fluggesellschaften abhängen. Es muss auch berücksichtigt werden, dass der Betrieb von Flughäfen viel komplizierter ist, da die Flugzeuge in ihnen so etwas wie Warteschlangen bilden. Darüber hinaus gibt es viele verschiedene Einschränkungen, die durch verschiedene Vereinbarungen und Gesetze geregelt werden.

In Zukunft kann ein genaues Modell zu einem unverzichtbaren zentralen Instrument werden, um die Analyse und Prognose des zivilen Luftverkehrsmarktes zu erleichtern und die bestmöglichen Entscheidungen zu treffen.