Logistik. Einführung Fast kompliziert

Wir alle lieben es zu träumen, besonders wenn es darum geht, neue Orte zu besuchen oder zu Ihren Lieblingsorten zurückzukehren. Nichts inspiriert so sehr wie das Gefühl der Vorfreude auf eine geplante Veranstaltung und wird nur durch das Vorhandensein organisatorischer Probleme, insbesondere der Auswahl und des Kaufs von Flugtickets, überschattet. Und aus irgendeinem Grund haben wir dieses Problem intern immer verschoben oder auf Reiseveranstalter, Metasuchmaschinen oder andere Aggregatoren verlagert. In der Praxis gab es Situationen, in denen eine Meldung auf dem Bildschirm angezeigt wurde: „Leider wurde für Ihre Anfrage nichts gefunden. Es kann Flüge für andere Tage geben. “

Wie so oft ist es bei weitem nicht immer eine Antwort auf eine Anfrage mit einer Routensuche, dass das gewünschte Ergebnis mit einem Flug angegeben wird, der sofort zur Kasse geht. Wir beginnen von Standort zu Standort zu wechseln, um eine zufriedenstellende Antwort zu erhalten.

Das Auftreten ähnlicher Fälle ist mit dem Mangel an direkter Kommunikation oder vorgeplanten kombinierten (Verbindungs-) Routen verbunden, oder es wurden Routen mit Transfers vorgeschlagen, die eine Wartezeit für den nächsten Flug von mehr als 5 bis 6 Stunden oder sogar einen ganzen Tag beinhalteten.

Wie kommt es, dass wir bei all den verschiedenen Fluggesellschaften Antworten erhalten, die uns bei weitem nicht immer zufrieden stellen, und wie sind die Algorithmen zum Auffinden von Routenoptionen im Allgemeinen algorithmisch aufgebaut? In dieser Angelegenheit hilft uns die angewandte Mathematik mithilfe von Algorithmen und Bewertungskriterien.


Weltflughafenkarte

Ich habe mich schon lange mit logistischen Problemen befasst und als ich vor der Aufgabe stand, eine Suchmaschine zu entwickeln, die nach optimalen Routen sucht, erschien es mir eher trivial. Aus Erfahrung könnte ich im Voraus sagen, dass es mit relativ einfachen Methoden und in relativ kurzer Zeit gelöst werden kann. Wenn jedoch alles so einfach wäre, wäre dieser Artikel nicht erschienen. Nachdem ich mich der Arbeit angeschlossen hatte, wurde mir nach einer Weile klar, dass es nicht so trivial war.

Der Ausgangspunkt war, wie so oft auf Reisen, und mit diesem Ansatz die Entscheidung, ein Transportnetz in Form eines Diagramms aufzubauen. Das Transportnetz umfasste zunächst Daten zu Flughäfen, Fluggesellschaften, deren Flugplänen und Verbindungszeitindikatoren.

Es wurde als Grundlage genommen, dass Flughäfen als oberste Grafik betrachtet werden und Flüge zwischen ihnen Kanten sind. Als Ergebnis erhielten wir ein Skelett wie in einem Skelett, auf dessen Grundlage ich einen Zeitplan aufstellte, der seine eigenen Merkmale hatte: Abfahrts- und Ankunftszeiten. Darüber hinaus ist eine Bewegung entlang der Kanten immer nur zu einem bestimmten Zeitpunkt möglich, der durch besondere Möglichkeiten zur Lösung des Problems gekennzeichnet ist:

• Mindestreisezeit;
• Mindestanzahl (oder angemessene Anzahl von Transplantationen im Klartext);
• Zeitintervall für den Transfer von einem Flug zum anderen bei der Auswahl komplexer Routen.

Die Schwierigkeit liegt in der Tatsache, dass wir unter keinen Umständen nur einen bestimmten Fall verwenden. Die Abfrage enthält immer verwandte Suchkriterien, einschließlich einer oder zwei oder mehr Verfeinerungen. Daraus folgt, dass die Anwendung des Kriteriums bestimmte Bedingungen für die Berechnung der gewünschten Routenoptionen auferlegt. Zusätzlich zu den drei oben aufgeführten Faktoren umfasst die Berechnung die Verwendung von Kategorien von Serviceklassen (First, Business, Economy), Kosten, Anzahl der Passagiere und deren Kategorien sowie die Verfügbarkeit einer Reihe zusätzlicher Services, die sich auf das Ergebnis auswirken. Somit passte dies vollständig zu meinem Konzept, das Problem durch Mehrkriterienoptimierung (Mehrzweckoptimierung) zu lösen, nämlich den kürzesten Weg nach mehreren Kriterien zu finden (MOSP - kürzester Weg mit mehreren Zielen).

Wie jeder weiß, müssen jedoch einige andere zitiert werden, um eine Hypothese zu testen. Als weitere Option zur Lösung des Problems wurde die Verwendung nichtlinearer Programmierung in Betracht gezogen.

Da die Bögen des Graphen mit Vektoren gewichtet sind, könnte die Lösung des Problems auf quadratische (nichtlineare) Programmierung reduziert werden. Und alles wäre perfekt, wenn nicht die Tatsache, dass die Vektoren tatsächlich nur zwei Eigenschaften haben: Länge und Projektion auf den Koordinatenachsen, was bedeutet, dass Variablen mit einem Grad von nicht mehr als zwei in der Zielfunktion vorhanden sind. In meinem Fall „widersprechen“ sich jedoch die Komponenten der Vektoren, was der nichtlinearen (quadratischen) Programmierung widerspricht. Zum Beispiel: „Konflikt“ kann auf die Tatsache zurückzuführen sein, dass jeder Flug eine bestimmte Flugzeugkapazität hat und es unmöglich ist, mehr Sitze dafür zu verkaufen. Aufgrund des Vorhandenseins von „Konflikten“ musste die Option zur Lösung des Problems durch nichtlineare Programmierung zugunsten derselben Programmierung mit mehreren Kriterien aufgegeben werden.

Nachdem ich die Optionen zur Lösung des Problems analysiert hatte, entschied ich mich für die klassische Version der Zerlegung mit den folgenden Teilen:

1. Suche basierend auf dem Zeitplan aller „kürzesten“ Routen vom Abflugort bis zum Ankunftsort;
2. Suche unter den "kürzesten" Pfaden der "optimalsten" anhand von Kriterien.

Gleichzeitig folgte nach der Zerlegung die Frage logisch, aber auf welcher Grundlage ist es besser, ein Transportroutennetz aufzubauen? Und welches der verfügbaren Diagramme ist zur Lösung dieses Problems akzeptabler?

Nach den Klassikern des Genres wurde nicht eines gefunden, sondern mehrere Modelle, über die ich nachzudenken begann.

Zeitverlängertes Modell

Ein zeitverlängerter Graph ist ein gerichteter Graph. Die Bögen eines solchen Diagramms sind die Richtungen der Abflug- und Ankunftspunkte von Flügen, und die Spitzen sind die Schlitze (Start- und Landezeiten) von Flügen. Die Verwendung des zeitverlängerten Modells besteht darin, das ursprüngliche Diagramm mit Flughafenspitzen und -bögen zu erweitern, wobei die Beziehung der Routen durch Kombinieren von Flughäfen untereinander gemäß dem Flugplan reflektiert wird:



Bögen werden bezeichnet$$$e_{BC,3}$. Zum Beispiel verbindet ein Bogen einen Flughafen$$$B$ mit Flughafen $$$$C$$und gerichtet von $$$B$zu $$$C$angegeben durch Komma-Index $$$3$zeigt, dass dies nicht der einzige Flug ist, sondern der dritte in Folge. Darüber hinaus kann jeder Bogen leicht gewichtet werden, beispielsweise das Gewicht des Bogens$$$e_{BC,3}$ kann berechnet werden als $$$w_{BC,3} = t_{C,9}-t_{B,6}$. Die Eckpunkte innerhalb eines einzelnen Flughafens können leicht gemäß der Zeitanzeige jedes Fluges angeordnet werden. Außerdem werden Flüge basierend auf der Verbindungszeit innerhalb des Flughafens durch Bögen verbunden, die der verfügbaren Übertragungszeit von einem Flug zum anderen entsprechen.

Der Vorteil eines zeitlich erweiterten Diagramms besteht darin, dass der schnellste Ankunftspfad beispielsweise in kürzester Zeit mithilfe des Dijkstra-Algorithmus gefunden werden kann. Der Nachteil dieses Ansatzes ist die mehrfache Zunahme von Scheitelpunkten und Kanten, die jedoch die Spärlichkeit des Diagramms nicht beeinflusst, da eine Zunahme der Anzahl von Kanten proportional zu einer Zunahme der Anzahl von Eckpunkten ist.

Zeitabhängiges Modell

Ein zeitabhängiger Graph ist ein gerichteter Graph ohne zusätzliche Transformationen gegenüber dem ursprünglichen Graph. Jeder Bogen entspricht einer Route mit Verbindungen zwischen Flughäfen, während der Bogen über einen speziellen Datensatz verfügt, der Parameter über die Abflug- und Ankunftszeit des Fluges entlang der Route enthält. Der aus diesem Datensatz abgerufene Wert hängt vom genauen Zeitpunkt ab, zu dem auf diesen Bogen zugegriffen wird, daher der Name „zeitabhängig“.



Der Vorteil eines zeitabhängigen Diagramms besteht darin, dass Sie den Pfad mit der geringsten Anzahl von Übertragungen finden können. Der Nachteil ist die übermäßige Belastung der Daten jedes Bogens.

Multigraph

Ein Multigraph ist ein gerichteter Graph mit Merkmalen, die zeitverbesserten und zeitabhängigen Modellen eigen sind.



Es gibt so viele Bögen zwischen Flughäfen wie während des erweiterten Modells, aber diese Bögen werden mit den Abflug- und Ankunftszeiten „gewichtet“, und die Verbindungszeit zwischen Flügen an jedem Flughafen muss ständig und wiederholt berechnet werden. Andererseits gibt es in einer Multi-Graph-Darstellung genau so viele Informationen über Flüge wie während eines zeitabhängigen Modells, aber all diese Informationen sind vielen Bögen zugeordnet. Das Finden des Pfads mit der geringsten Anzahl von Übertragungen ist so einfach wie während des zeitabhängigen Modells. Bei der Weitergabe eines Bogens werden jedoch die Informationen anderer Bögen nicht berücksichtigt. Nachdem der Pfad mit der geringsten Anzahl von Übertragungen gefunden wurde, müssen Sie diesen Pfad für wiederholen Berechnung von Informationen über andere Flüge (Bögen).

Die Darstellung eines Transportroutennetzes in Form eines Multigraphen ist ein Rohzustand für zeitlich ausgedehnte und zeitabhängige Modelle. Die Suche nach dem Pfad mit der kürzesten Ankunft wird von denselben Transformationen durchgeführt, die für das zeitlich erweiterte Modell charakteristisch sind, und die Suche nach dem Pfad mit der geringsten Anzahl von Übertragungen wird vom zeitabhängigen Modell durchgeführt. Dies führt zu einer Verlängerung der Netzwerkberechnungszeit. Hier gibt es jedoch eine Nuance, da die Suche nach dem „kürzesten“ Pfad nach zwei Kriterien im allgemeinen Fall bereits zur NP-Klasse schwieriger Aufgaben gehört und die Modifikation des Dijkstra-Algorithmus recht komplexe Manipulationen mit der Markierung von Eckpunkten durchführt.

Die Darstellung der rechnerischen Komplexität des Problems mit dem Multigraph des Modells des Satzes von Routen mit Flughäfen und Flügen kann durch die einfachste Modifikationsmethode betrachtet werden - den Dijkstra-Algorithmus, der nur nach paretooptimalen Pfaden sucht. Die Gesamtanzahl der Kriterien für einen einzelnen Pareto-optimalen Pfad kann nicht schlechter oder besser sein als andere Pareto-optimale Pfade für alle Kriterien gleichzeitig. Beispielsweise ist eine Reihe von Pfaden mit der folgenden Summe von zwei Kriterien {(30, 10), (20, 20), (10, 30)} paretooptimal.

Als anschaulicheres Beispiel betrachten wir die Funktionsweise des Algorithmus in einem kleinen Graphen, dessen Bögen durch zweidimensionale Vektoren gewichtet werden:



Die Operation des modifizierten Dijkstra-Algorithmus in einem solchen Diagramm sowie des normalen Algorithmus für ein reguläres Diagramm besteht aus Iterationen mit aufeinanderfolgendem Auftreffen der Scheitelpunkte, mit der Ausnahme, dass jeder Scheitelpunkt möglicherweise nicht einen Pareto-Optimalwert hat, sondern mehrere. Darüber hinaus müssen Informationen über den Ursprung jedes berechneten Wertes der Summe gespeichert werden.

Angesichts der Tatsache, dass das Problem Routen mit Flughafenverbindungen für Flüge berücksichtigt, ist es durchaus angebracht anzunehmen, dass zwischen zwei Eckpunkten ziemlich viele Bögen liegen können und jeder von ihnen mit mindestens einem Dreikomponentenvektor gewichtet werden kann. Mit einer Zunahme der Komponenten der Vektoren kann jedoch auch eine Zunahme der Pareto-optimalen Pfade auftreten. Darüber hinaus können fast alle Bögen zwischen zwei Eckpunkten paretooptimal sein. In diesem Fall enthält die Summe der Pfade noch mehr paretooptimale Pfade. Dies ist an einem kleinen Multigraph zu erkennen, der mit zweidimensionalen Vektoren gewichtet ist:



Die Verwendung des modifizierten Dijkstra-Algorithmus in einem solchen Modell ist zulässig, da er mit Multigraphen arbeiten kann, die Verarbeitungsgeschwindigkeit des Algorithmus jedoch von der Anzahl der Scheitelpunkte abhängt$$$n$und auf die Anzahl der Bögen $$$m$. Für spärliche einfache Graphen und den üblichen Algorithmus liegt die Komplexität in der Größenordnung von$$$O(n\log n+m\log n)$. Es ist jedoch schwierig zu sagen, ob der resultierende Multigraph "spärlich" sein wird, da im allgemeinen Fall die Kantendichte von Multigraphen viel höher sein kann als die eines vollständigen Graphen. Berücksichtigen wir, dass die Anzahl der Kanten eines vollständigen Graphen$$$E$ bestimmt durch die Anzahl seiner Eckpunkte $$$V$nach der Formel:

$$$E={\frac {V(V-1)}{2}}$

Und die Kantendichte ist definiert als:

$$$D={\frac {2E}{V\,(V-1)}}$

Für vollständige Grafiken $$$max(D) = 1$Bei Multigraphen ist der Wert der Kantendichte im Allgemeinen unbegrenzt.

Daher bin ich zu dem Schluss gekommen, dass der kürzeste Weg mit dem Dijkstra-Algorithmus und alle anderen kürzesten Wege mit dem Yen-Algorithmus gefunden werden können. Da wir zu diesem Zeitpunkt mit ungewichteten Bögen arbeiten und Pfade, beispielsweise mit vier Übertragungen, sofort verwerfen können, wird die Suche nach einem kürzesten Pfad garantiert in weniger als durchgeführt$$$O(n^{2})$.



Da dieser Artikel nicht die unmittelbaren Ergebnisse der Implementierung behandelt, kann ich im Voraus davon ausgehen, dass der modifizierte Dijkstra-Algorithmus für ein Multigraph-Modell unter Berücksichtigung des optimalen Zeitintervalls nicht funktioniert.

Daher werde ich zur sofortigen Lösung des ersten Teilproblems übergehen, nämlich zur Lösung der Frage der Multikriteria-Optimierung, die ich nach der Methode der bedingten Optimierung ausgewählt habe. Die Methode besteht darin, dass trotz der Inkonsistenz der Kriterien immer die höchste Priorität besteht und alle anderen gültige Werte haben. Infolgedessen kommt es bei der Optimierung der gesamten Aufgabe auf die Optimierung mit höchster Priorität an.

Ein Merkmal der Aufgabe ist die Tatsache, dass die Berechnung nicht nur Direktflüge umfasst, was die Aufgabe immer erheblich vereinfacht, sondern im Gegenteil Verbindungsflüge oder Transfers. Daher ist das zeitabhängige Diagrammmodell sehr gut zur Lösung des Problems geeignet, da die Anzahl der Übertragungen häufig nicht mehr als 3-4 Segmente in der Route bildet. Das zeitabhängige Diagramm enthält zunächst Informationen über die Gesamtheit der verfügbaren Routen in Form von Flügen mit Verbindungen zwischen Flughäfen. Anschließend wird eine Schätzung der Abfahrts- und Ankunftszeiten für das Andocken unter Berücksichtigung des üblichen ungewichteten Diagramms berechnet. In dieser Phase müssen lediglich alle gültigen Routen zwischen den Flughäfen „A“ und „B“ mit einer festgelegten Anzahl von Transfers gefunden werden, z. B. drei.



In Anbetracht dessen, dass der Graph zu diesem Zeitpunkt ungewichtet ist, ist es möglich, den kürzesten Pfad unter Verwendung der üblichen Breitensuche und alle anderen kürzesten Pfade unter Verwendung des Yen-Algorithmus zu finden. Da die Breitensuche in linearer Zeit durchgeführt wird, können wir sagen, dass die Suchzeit für alle Pfade mit denselben 3 Übertragungen linear ist.

Bei der Beurteilung der Verwendung von Algorithmen zum Finden optimaler Routen und der Verfügbarkeit von Daten zur Häufigkeit der Zeitplanaktualisierungen können wir sagen, dass die Idee einer vorberechneten Matrix mit allen „kürzesten“ Pfaden in Richtungen gerechtfertigt ist. Natürlich wird sich eine solche Lösung in der Anfangsphase der Erstellung der Matrix als mühsame Berechnung herausstellen, aber in Zukunft können Sie fast sofort die „kürzesten“ Pfade finden und umgehend Anpassungen an der Matrix selbst vornehmen.

Es bleibt jedoch die Frage, welche „kürzesten“ Routen mit Verbindungen und Transfers die „kürzesten“ sind. Andernfalls verfügen wir über eine Reihe von Daten, die es uns nicht ermöglichen, eine Entscheidung zu treffen. Eine Reihe von Kriterien wird in diesem Fall häufig auf das Optimum reduziert, nämlich:

• Mindestreisezeit;
• Mindestanzahl von Überweisungen.

Beide Kriterien können anpassbare Intervalle oder Zeitwerte haben. Daher müssen nur die Routen kombiniert und im laufenden Betrieb überprüft werden, ob die zulässigen Werte eingehalten werden:



Da die maximale Anzahl von Transfers zwischen 3 und 4 variiert, werden einige Flugkombinationen sofort ausgeschlossen Dies führt uns zur Lösung des folgenden Teilproblems: Ermittlung der „optimalsten“ Kriterien für die Sorte unter den Routen.

Das Kriteriumsystem ist das Hauptproblem bei der Bildung der Ausgabe von Routen, da das Konzept des "Optimums" von den Präferenzen eines bestimmten Passagiers abhängt und er häufig erst nach Erhalt einer Antwort auf die Anfrage die empfangenen Routen verwalten kann, indem er einen anderen Satz von Filtern einstellt. Und selbst wenn Sie ihm geordnete Routen gemäß den „kürzesten“ Pfaden zur Verfügung stellen, sind die Ergebnisse eine Reihe von Daten, die dem Passagier keine Entscheidung ermöglichen und zu einer endlosen Suche nach Optionen führen. Daher ist die Bildung einer Reihe von Routenoptionen, die verschiedene Kombinationen von Filteranwendungen sowohl gemeinsam als auch einzeln berücksichtigen, ein äußerst wichtiger Parameter, der sich auf die gesamte Aufgabe auswirkt.

Was ist dann zu beachten und wie? Das Erstellen von Ranking-Filtern ist eine sehr zeitaufwändige Aufgabe, da Eine Reihe von Filtern, deren Anzahl und Grad des Einflusses aufeinander können das Ergebnis der Suche nach optimalen Pfaden infolge der Verfeinerung der Suchalgorithmen erheblich verändern. Woraus kann es dann bestehen? Wir alle kennen die wichtigsten Flugparameter - Informationen zu Fluggesellschaften, Daten mit Abflug- / Ankunftszeiten, Abflug- / Ankunftsflughäfen, Zeitzonenversatz, Verbindungen und Transfers, aber wir vergessen häufig Daten wie die notwendige und ausreichende Zeit, um am Flughafen anzukommen oder Reisezeit zwischen Flughäfen, um eine Verbindung herzustellen, falls der spätere Abflug von einem anderen Punkt am Standort erfolgt. Und wir sollten die Kategorie unseres Passagiers nicht vergessen,sowie deren Menge für das nachfolgende Angebot nicht nur der optimalen Route in der Zeit, sondern auch im Preis, abhängig von der Tarifpolitik.

Eine Reihe von Angeboten sollte jedem Reisenden ein gewisses Maß an Vertrauen vermitteln, egal wie paradox dies klingen mag. Vertrauen basiert auf mathematischen Prinzipien und besteht in der Bereitstellung eines Mindestsatzes von Vorschlägen mit Routenoptionen, die Präferenzen berücksichtigen und das Risiko höherer Gewalt verringern. In diesem Fall ist höhere Gewalt nicht nur die Wahrscheinlichkeit einer Flugverspätung oder einer Änderung der Zeit und des Abflug- / Ankunftsflughafens, sondern auch Indikatoren wie natürliche, technologische und epidemiologische Situationen, die eine vollständige oder teilweise Annullierung von Flügen zur Folge haben.

Die Fähigkeit, Daten in unserer Realität zu verwalten, wirft jedes Mal viele Fragen auf: Wird alles berücksichtigt, was kann noch hinzugefügt werden? Und in diesem Wunsch, ein Transportroutennetz aufzubauen, entsteht ein Paradoxon in Bezug auf die Tatsache, dass der Algorithmus gleichzeitig optimal und einfach sein sollte. Aber man muss oft etwas opfern, von hier aus schien es mir am akzeptabelsten, die anfänglichen Kriterien auf den Mindestbetrag zu minimieren.

Wenn wir den Weg der Auswahl von Kriterien beschreiten und dann die sekundären weglassen, können wir solche Optionen unterscheiden, die nicht nur die Zeit der gesamten Reise, Kosten und Komfort, die Anzahl der Transfers und deren Dauer der Transfers berücksichtigen, sondern beispielsweise Informationen über die Überlastung von Flughäfen und Daten zur Kommunikation zwischen Flughäfen beim Wechsel eines Flughafens zu einem anderen. Dies wird durch die Tatsache gerechtfertigt, dass beim Aufbau von Verbindungen unter Berücksichtigung des Vorhandenseins mehrerer Flughäfen in einer Stadt, die unterschiedliche Kommunikation mit externen Flughäfen haben, nicht nur der Flugverkehr, sondern auch der Zeitpunkt der Bewegung, wenn eine solche Situation auftritt, bei der Berechnung der Zeit und der Routenbildung berechnet wird. Und sie haben einen Ort zu sein ...

Das Entscheidungssystem bei der Auswahl der „optimalen“ Routen in Situationen, in denen wir eine Reihe von Kriterien haben, die sich auf die Präferenzen auswirken, ist nur dieser Stolperstein, über den ich in der Anfangsphase überhaupt nicht nachgedacht habe. Selbst wenn sie zu einer bestimmten Systematisierung führen, gibt es ziemlich viele Unterschiede in ihrer Anwendung, so dass wir sie separat betrachten werden.

Komfort

Die Bedeutung des Begriffs "Komfort" wird von jedem anders verstanden, aber die folgenden Ebenen werden von den Fluggesellschaften akzeptiert:

• erste Klasse;
• Business Class;
• Economy Class.

In meinem Ansatz gab ich zu, dass der Parameter „Komfort“ gemessen werden kann und Werte von 1 bis 10 annehmen kann, und bildete die folgende Bedingung: Je niedriger dieser Indikator für einen bestimmten Flug ist, desto weniger komfortabel ist er im Rangsystem. In diesem Fall tritt sofort ein Problem auf, das mit der Nichtadditivität einer solchen Menge zusammenhängt, d.h. Die Summe der Komfortindikatoren der beiden Flüge spiegelt nicht ihren Gesamtkomfort wider. Zum Beispiel gibt es zwei Routenkombinationen:

• die erste Route mit zwei Segmenten, die erste mit Komfort 10, die zweite mit Komfort 1;
• die zweite Route mit zwei Segmenten, die erste mit Komfort 6, die zweite mit Komfort 5.

Infolgedessen sind die Summe und der arithmetische Mittelwert des Parameters „Komfort“ jedes Pfades gleich, spiegeln jedoch nicht den tatsächlichen Stand der Dinge wider. Angesichts der Notwendigkeit, den Gesamtkomfort der beiden Routen zu berücksichtigen, ist es in dieser Situation am ratsamsten, ihre Durchschnittswerte zusammen mit der Standardabweichung zu verwenden, um die „Streuung“ der Komfortniveaus abschätzen zu können. Das heißt, wir achten bei der ersten Überlegung auf den durchschnittlichen Komfort und berücksichtigen dann anhand der Größe der Standardabweichung, wie stark sich diese Annehmlichkeiten voneinander unterscheiden. Somit teilt sich dieses Kriterium in zwei sehr "enge". Obwohl andererseits auch ohne sorgfältige Prüfung klar ist, dass die Annahme eines solchen „messbaren“ Komfortniveaus sehr weit von der Realität entfernt ist,weil wir bekannte Klassenstufen haben. Und zweitens ist es auch offensichtlich, dass der Komfort der gesamten Reise in irgendeiner funktionalen Abhängigkeit von anderen Kriterien besteht, beispielsweise der Flugdauer, der Anzahl der Transfers mit ihrer Dauer, der Bewertung der Fluggesellschaft und ihrer Luftflotte. Ob es sinnvoll ist, sich auf dieses Kriterium zu konzentrieren, ist eine Frage. Schließlich basiert der Ansatz auf einem System zur Berücksichtigung der Gesamtheit der „optimalen“ Wege. Daher werden wir in Zukunft die Komfortdarstellung in Form von zwei Indikatoren verwenden: dem arithmetischen Mittel der Komfortindikatoren von Flügen und ihrer Standardabweichung.die Anzahl der Transfers mit ihrer Dauer, die Bewertung der Fluggesellschaft und ihrer Luftflotte. Ob es sinnvoll ist, sich auf dieses Kriterium zu konzentrieren, ist eine Frage. Schließlich basiert der Ansatz auf einem System zur Berücksichtigung der Gesamtheit der „optimalen“ Wege. Daher werden wir in Zukunft die Komfortdarstellung in Form von zwei Indikatoren verwenden: dem arithmetischen Mittel der Komfortindikatoren von Flügen und ihrer Standardabweichung.die Anzahl der Transfers mit ihrer Dauer, die Bewertung der Fluggesellschaft und ihrer Luftflotte. Ob es sinnvoll ist, sich auf dieses Kriterium zu konzentrieren, ist eine Frage. Schließlich basiert der Ansatz auf einem System zur Berücksichtigung der Gesamtheit der „optimalen“ Wege. Daher werden wir in Zukunft die Komfortdarstellung in Form von zwei Indikatoren verwenden: dem arithmetischen Mittel der Komfortindikatoren von Flügen und ihrer Standardabweichung.

Dauer der Transfers

Es gibt zwei Arten der Routenkoordination:

• Transfers (zwischen Fluggesellschaften im Voraus vereinbart);
• Docking.

Von Interesse aus dieser Liste ist das Konzept der „Verbindung“, das das Ergebnis einer Kombination von zwei oder mehr Fluggesellschaften auf derselben Route mit vereinbarten Zeiträumen ist, basierend auf der erforderlichen Mindestverbindungszeit, die jedoch nicht immer ausreicht, um von einem Flug zum anderen zu wechseln. Um Flüge auf einer solchen Route zu kombinieren, muss daher die ausreichende Zeit berechnet werden, die zum Herstellen der Verbindung erforderlich ist.

Hier haben wir eine Dissonanz, weil solche Flüge oft von den Optionen für das Angebot ausgeschlossen werden können, aber aufgrund des Vorhandenseins eines solchen Kriteriums gibt es Situationen, in denen die Verbindung mit einer vorübergehenden Wartezeit von mehr als einem Tag für unseren Passagier „optimal“ ist. Daher ist es sinnvoll, Routen mit zu langen Transplantationszeiten nicht zu verwerfen, da sie, wenn auch selten, immer noch gefragt sind.

Flughafen

Staus Der Indikator Flughafen Staus kann abgeschätzt werden , wenn sie mit einer Beurteilung des Grades ihrer Füllung auf den Verkauf von Tickets für Flüge , die „optimale“ Berechnung von Routen, unter Berücksichtigung der Beteiligung eines Flughafens in der Route. Unter dieser Annahme hängt die minimale Verbindungszeit offensichtlich von der Überlastung des Flughafens ab.

Anzahl der Überweisungen

Die Anzahl der Transplantationen an sich ist ein widersprüchlicher Betrag. In der Tat können Sie auf diese Weise häufig die Kosten für die gesamte Route senken. Auf der anderen Seite gibt es eine Kategorie von Passagieren, für die das Vorhandensein einer einzigen Änderung eine Reihe von Problemen verursacht. Vergessen Sie nicht die Situationen, in denen die Transferroute am „optimalsten“ ist, da teure Business Class-Tickets auf der gewünschten Route verbleiben oder es beispielsweise Tickets mit einem Tarif ohne Umtausch- / Rückgabemöglichkeit gibt, was die Wahrscheinlichkeit einer Ablehnung mit sich bringt die vorgeschlagene Option.

Bei der Anzahl der Überweisungen wird jedoch ein anderes Unterkriterium festgelegt - dies ist die Wahrscheinlichkeit, von einem Flughafen zum anderen zu wechseln. Daher ist die Bildung von Verbindungen oft eine schwierige Aufgabe, da bei der Berechnung der Route die Zeit für den Wechsel zwischen Flughäfen festgelegt werden muss und daher Tickets für den Transport innerhalb der Stadt für den Umzug in Unterabsätze bestellt werden müssen.

Die Kriterien „Reisezeit“ und „Kosten“ sind absolut additive Mengen, daher stützen sie sich auf direkte Indikatoren mit einem Ranking-System. Und alles wäre in Ordnung, wenn nicht die Gesamtreisezeit in die Berechnung der Ankunftszeit am Flughafen oder der Abflugzeit vom Zielort sowie bei der Verknüpfung der Buchhaltung für die Notwendigkeit zusätzlicher Kosten für den Wechsel zwischen Flughäfen einbezogen werden müsste. Lassen Sie mich an dieser Stelle diese Klarstellung vernachlässigen.

Die hierarchische Struktur des globalen Ziels

Angenommen, die Definition von „Optimalität“ sollte immer und für alle als die beste verstanden werden, und zwar nicht nur für Passagiere, sondern auch für Fluggesellschaften, Flughäfen und möglicherweise andere Reisedienstleister.

In diesem Fall ist die Aufteilung eines einzelnen, sehr komplexen Ziels in Unterziele der einzige Ausweg. Eine solche Aufteilung mag folgendermaßen aussehen:



Es ist ziemlich offensichtlich, dass man weniger „globale“, aber teilweise widersprüchliche Ziele erreichen muss, um alle Interessenbereiche zu befriedigen. Wie erreicht man das? Vielleicht ist dies ein großartiges Thema für einen anderen Artikel. Mit Blick auf die Zukunft können wir jedoch sagen, dass die Aufteilung eines komplexen Ziels in einfachere Unterziele auch mit Optimierung und Graphentheorie verbunden ist, nämlich der Suche nach optimalen hierarchischen Strukturen.

Das Entscheidungssystem ist ziemlich eng mit Methoden wie den Kriterien von Laplace, Wald, Savage und Hurwitz verbunden. Da es eine Reihe von „kürzesten“ Routen gibt, konnte ich nicht anders, als zu wissen, welche davon auf dieser Grundlage die „optimalsten“ sind.

Einer der universellsten Ansätze zur Lösung von Mehrzweckoptimierungsproblemen ist die Suche nach optimalen Lösungen von Pareto und Slater. Wenn wir das Array der "kürzesten" Routen gemäß dem Optimalitätskriterium von Slater bewerten, wird der optimale Pfad als derjenige angesehen, der nach allen Kriterien gleichzeitig der beste ist. Ein Pfad wird als Pareto-optimal angesehen, wenn alle anderen Pfade in einem Parameter besser als er sind, in einem anderen jedoch schlechter, d. H. man kann einen Weg nicht um mindestens ein Kriterium verbessern, ohne ihn durch den Rest zu verschlechtern.

Alle Pareto- und Slater-Optimalitätslösungen können für das Minimierungsproblem mit zwei Kriterien leicht grafisch dargestellt werden: Die



Punktmenge mit den Parametern der Pareto-Optimalkriterien wird grün und die Slater-Optimalkriterien gelb angezeigt. Die Menge der Slater-optimalen Punkte enthält auch die Menge der Paretto-optimalen Punkte. Im Rahmen des betrachteten Problems sind alle diese Punkte die Enden der Vektoren, beginnend am Ursprung des siebendimensionalen Raums.

Zusammenfassend kann ich sagen, dass dies nur die Spitze des Eisbergs ist, die es Ihnen ermöglicht, eine erste Vorstellung davon zu geben, auf was Suchmaschinen bei der Bildung optimaler Routen stoßen.