Logistique. introduction À peu près compliqué

Nous aimons tous rêver, surtout quand il s'agit de visiter de nouveaux endroits ou de retourner dans vos endroits préférés. Rien n'inspire autant qu'un sentiment d'anticipation d'un événement planifié et n'est éclipsé que par la présence de problèmes d'organisation, en particulier la sélection et l'achat de billets d'avion. Et pour une raison quelconque, en interne, nous différons toujours ce problème ou le reportons sur les voyagistes, les moteurs de recherche ou d'autres agrégateurs. Dans la pratique de chacun, il y avait des situations où un message était affiché à l'écran: «Malheureusement, rien n'a été trouvé pour votre demande. Il peut y avoir des vols pour d'autres jours. »

Comme cela arrive souvent, c'est loin d'être toujours en réponse à une demande de recherche d'itinéraire que le résultat souhaité avec un vol est donné, qui passe immédiatement à la caisse. Nous commençons à passer d'un site à l'autre pour obtenir une réponse satisfaisante.

La survenue de cas similaires est associée à l'absence de communication directe ou d'itinéraires combinés (de correspondance) préprogrammés, ou des itinéraires avec transferts ont été proposés qui incluaient un temps d'attente pour le prochain vol de plus de 5 à 6 heures, voire une journée entière.

Comment se fait-il qu'avec toute la variété des compagnies aériennes, nous obtenions des réponses qui sont loin de toujours nous satisfaire, et en général, comment les algorithmes pour trouver des options d'itinéraire sont-ils construits de manière algorithmique? Dans ce domaine, les mathématiques appliquées viennent à notre aide à l'aide d'algorithmes et de critères d'évaluation.


Carte des aéroports du monde

Je fais face à des problèmes logistiques depuis longtemps et lorsque j'ai été confronté à la tâche de construire un moteur de recherche qui recherchera des itinéraires optimaux, cela m'a semblé plutôt trivial. Par expérience, je pourrais dire à l'avance qu'il peut être résolu par des méthodes assez simples et en un temps relativement court. Cependant, si tout était si simple, cet article n'aurait pas été publié. Par conséquent, après avoir rejoint le travail, après un certain temps, j'ai réalisé que ce n'était pas si trivial.

Le point de départ, comme cela arrive souvent en voyage, et c'est avec cette approche que j'ai trouvé, a été la décision de construire un réseau de transport sous forme de graphique. Le réseau de transport comprenait initialement des données sur les aéroports, les compagnies aériennes, leurs horaires de vol et les indicateurs de temps de correspondance.

Il a été pris comme base que les aéroports sont considérés comme le haut du graphique, et les vols entre eux sont des bords. En conséquence, nous avons obtenu un squelette, comme dans un squelette, sur la base duquel j'ai commencé à imposer un horaire qui avait ses propres caractéristiques: les heures de départ et d'arrivée. De plus, le mouvement le long des bords n'est toujours possible qu'à un certain moment, ce qui se caractérise par des options particulières pour résoudre le problème:

• temps de voyage minimum;
• nombre minimum (ou adéquat en langage clair) de transplantations;
• intervalle de temps pour le transfert d'un vol à un autre lors du choix d'itinéraires complexes.

La difficulté réside dans le fait qu'en aucun cas nous n'avons recours à un seul cas particulier, la requête contient toujours des critères de recherche associés, y compris un ou deux raffinements ou plus. Il s'ensuit que l'application du critère impose certaines conditions au calcul des options d'itinéraire souhaitées. En plus des trois énumérés ci-dessus, le calcul comprend l'utilisation de catégories de classes de services (d'abord, affaires, économie), le coût, le nombre de passagers et leurs catégories, ainsi que la disponibilité d'un certain nombre de services supplémentaires qui affectent le résultat. Ainsi, cela a complètement commencé à s'intégrer dans mon concept de résolution du problème au moyen de l'optimisation multicritères (optimisation polyvalente), à ​​savoir trouver le chemin le plus court selon plusieurs critères (MOSP - chemin le plus court multi-objectif).

Mais, comme chacun le sait, pour tester une hypothèse, il faut en citer plusieurs autres. Comme autre option pour résoudre le problème, l'utilisation de la programmation non linéaire a été envisagée.

Étant donné que les arcs du graphique sont pondérés par des vecteurs, la solution du problème pourrait être réduite à une programmation quadratique (non linéaire). Et tout serait parfait sans le fait que les vecteurs, en fait, n'ont que deux caractéristiques: la longueur et la projection sur les axes de coordonnées, ce qui signifie la présence dans la fonction objective de variables avec un degré ne dépassant pas deux. Cependant, dans mon cas, les composants des vecteurs «entrent en conflit», ce qui contredit la programmation non linéaire (quadratique). Par exemple: le «conflit» peut être dû au fait que chaque vol a une capacité d'avion spécifique et qu'il est impossible de lui vendre plus de sièges. En raison de la présence de «conflits», l'option de résoudre le problème par une programmation non linéaire a dû être abandonnée au profit de la même programmation multicritères.

Après avoir analysé les options pour résoudre le problème, je suis allé avec la version classique de décomposition avec les parties suivantes:

1. recherche basée sur le calendrier de tous les itinéraires «les plus courts» du point de départ au point d'arrivée;
2. rechercher parmi les chemins les plus "courts" des plus "optimaux" en fonction de critères.

Dans le même temps, après la décomposition, la question a logiquement suivi, mais sur la base de quelle approche vaut-il mieux construire un réseau de voies de transport? Et lequel des graphiques disponibles est le plus acceptable pour résoudre ce problème?

Selon les classiques du genre, pas un seul, mais plusieurs modèles, que j'ai commencé à considérer.

Modèle à extension de temps

Un graphique étendu dans le temps est un graphique dirigé. Les arcs d'un tel graphique sont les directions des points de départ et d'arrivée des vols, et les pics sont les créneaux horaires (décollage et atterrissage) des vols. Le modèle à extension de temps permet d'étendre le graphique d'origine avec les pics et les arcs des aéroports, reflétant la relation des itinéraires en combinant les aéroports entre eux conformément au programme de vol: les



arcs sont indiqués comme suit :$$ . Par exemple, un arc relie un aéroport$e_{BC,3}$$$ avec aéroport$B$$$ et envoyé depuis$$C$$$$ à$B$$$ , index séparé par des virgules$C$$$ montre que ce n'est pas le seul vol, mais le troisième de suite. De plus, chaque arc peut être facilement pondéré, par exemple, le poids de l'arc$3$$$ peut être calculé comme$e_{BC,3}$$$ . Les sommets à l'intérieur d'un seul aéroport sont facilement disposés en fonction de l'indicateur de temps de chaque vol, et également, en fonction du temps de correspondance à l'intérieur de l'aéroport, les vols sont reliés par des arcs qui correspondent au temps de transfert disponible d'un vol à l'autre.$w_{BC,3} = t_{C,9}-t_{B,6}$

L'avantage d'un graphique étendu dans le temps est que le chemin d'arrivée le plus rapide peut être trouvé dans les plus brefs délais, par exemple, en utilisant l'algorithme de Dijkstra. L'inconvénient de cette approche est l'augmentation multiple des sommets et des arêtes, qui, cependant, n'affecte pas la rareté du graphique, car une augmentation du nombre d'arêtes est proportionnelle à une augmentation du nombre de sommets.

Modèle dépendant du temps

Un graphe dépendant du temps est un graphe orienté sans transformations supplémentaires par rapport au graphe d'origine. Chaque arc correspond à un itinéraire avec des connexions entre les aéroports, tandis que l'arc possède un ensemble de données spécial qui comprend des paramètres sur l'heure de départ et d'arrivée du vol le long de l'itinéraire. La valeur extraite de cet ensemble de données dépend du moment exact où l'accès à cet arc se produit, d'où le nom «dépendant du temps».



L'avantage d'un graphe dépendant du temps est qu'il permet de trouver le chemin avec le moins de transferts, l'inconvénient est la charge excessive sur les données de chaque arc.

Multigraph

Un multigraphe est un graphique dirigé avec des ensembles de caractéristiques inhérentes aux modèles améliorés et dépendants du temps.



Il y a autant d'arcs entre les aéroports que pendant le modèle étendu, mais ces arcs sont «pondérés» par les heures de départ et d'arrivée, et le temps de correspondance entre les vols de chaque aéroport devra être calculé constamment et à plusieurs reprises. En revanche, dans une représentation multi-graphes, il y a exactement autant d'informations sur les vols que dans un modèle dépendant du temps, mais toutes ces informations sont affectées à de nombreux arcs. Trouver le chemin avec le moins de transferts sera aussi simple que pendant le modèle dépendant du temps, mais passer le long d'un arc ne prend pas en compte les informations des autres arcs, donc après avoir trouvé le chemin avec le moins de transferts, vous devrez répéter ce chemin pour calcul des informations sur les autres vols (arcs).

La représentation d'un réseau de voies de transport sous la forme d'un multigraphe est un état brut pour les modèles étendus et dépendants du temps. La recherche du chemin avec l'arrivée la plus courte sera effectuée par les mêmes transformations caractéristiques du modèle étendu dans le temps, et la recherche du chemin avec le moins de transferts sera effectuée par le modèle dépendant du temps. Et entraîne une augmentation du temps de calcul du réseau. Cependant, il y a une nuance ici, car la recherche du chemin «le plus court» selon deux critères, dans le cas général, appartient déjà à la classe NP des tâches difficiles et la modification de l'algorithme de Dijkstra effectue des manipulations assez complexes avec le marquage des sommets.

La représentation de la complexité de calcul du problème avec le multigraphe du modèle de l'ensemble des routes avec les aéroports et les vols peut être considérée par la méthode de modification la plus simple - l'algorithme de Dijkstra, qui ne recherche que les chemins Pareto-optimaux. La quantité totale de critères pour un seul chemin optimal de Pareto ne peut pas être pire ou meilleure que les autres chemins optimaux de Pareto pour tous les critères simultanément. Par exemple, un ensemble de chemins avec la somme suivante de deux critères {(30, 10), (20, 20), (10, 30)} sera Pareto optimal.

Comme exemple plus illustratif, nous considérons le fonctionnement de l'algorithme sur un petit graphe dont les arcs sont pondérés par des vecteurs bidimensionnels:



Le fonctionnement de l'algorithme de Dijkstra modifié sur un tel graphique, ainsi que l'algorithme habituel pour un graphique régulier, consistera en itérations avec suppression successive des sommets, sauf que chaque sommet peut avoir non pas une valeur Pareto-optimale, mais plusieurs. En outre, il est également nécessaire de sauvegarder des informations sur l'origine de chaque valeur calculée de la somme.

Étant donné que le problème considère les itinéraires avec des connexions aéroportuaires pour les vols, il est tout à fait approprié de supposer qu'il peut y avoir beaucoup d'arcs entre deux sommets, et chacun d'eux peut être pondéré par au moins un vecteur à trois composantes. Mais avec une augmentation des composants des vecteurs, une augmentation des chemins optimaux de Pareto peut également se produire. De plus, presque tous les arcs entre deux sommets peuvent être Pareto-optimaux. Dans ce cas, la somme des chemins contiendra encore plus de chemins Pareto-optimaux. Cela peut être vu sur une petite multigraphe pondérée par des vecteurs bidimensionnels:



l'utilisation de l'algorithme de Dijkstra modifié dans un tel modèle est autorisée, car elle peut fonctionner sur des multigraphes, mais la vitesse de traitement de l'algorithme dépend du nombre de sommets$$ , et le nombre d'arcs$n$$$$m$ . Pour les graphes simples clairsemés et l'algorithme habituel, la complexité est de l'ordre de$$$O(n\log n+m\log n)$ . Cependant, il est difficile de dire si le multigraphe résultant sera "clairsemé", car dans le cas général, la densité des bords des multigrammes peut être beaucoup plus élevée que celle d'un graphique complet. Si l'on prend en compte que le nombre d'arêtes d'un graphe complet$$$E$ déterminé par le nombre de ses sommets$$$V$ par la formule:

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

Une densité de côtes est définie comme:

$$Pour des graphiques complets$D={\frac {2E}{V\,(V-1)}}$

$$, mais pour les multigraphes, la valeur de la densité des bords est généralement illimitée. Par conséquent, je suis arrivé à la conclusion que le chemin le plus court peut être trouvé en utilisant l'algorithme Dijkstra, et tous les autres chemins les plus courts peuvent être trouvés en utilisant l'algorithme Yen. Étant donné qu'à ce stade, nous fonctionnons avec des arcs non pondérés et pouvons immédiatement ignorer les chemins, par exemple avec quatre transferts, alors la recherche d'un chemin le plus court sera garantie d'être effectuée en moins de$max(D) = 1$

$$. Étant donné que cet article ne couvre pas les résultats immédiats de la mise en œuvre, je peux supposer à l'avance que l'algorithme de Dijkstra modifié sur un modèle multigraph ne fonctionnera pas en tenant compte de l'intervalle de temps optimal. Je vais donc passer à la solution immédiate du premier sous-problème, à savoir à la solution de la question relative à l'optimisation multicritères, que j'ai choisie par la méthode de l'optimisation conditionnelle. La méthode consiste dans le fait que malgré l'incohérence des critères, la priorité la plus élevée existe toujours, et tous les autres ont des valeurs valides. Par conséquent, l'optimisation de l'ensemble de la tâche se résume à une optimisation de la plus haute priorité.$O(n^{2})$







Une caractéristique de la tâche est le fait que le calcul inclut non seulement les vols directs, ce qui simplifie toujours considérablement la tâche, mais, au contraire, les vols de correspondance ou les transferts. Par conséquent, le modèle de graphique dépendant du temps est très approprié pour résoudre le problème, car souvent le nombre de transferts ne forme pas plus de 3-4 segments sur l'itinéraire. Le graphique dépendant du temps, tout d'abord, contient des informations sur la totalité des itinéraires disponibles sous forme de vols avec correspondances entre aéroports. Ensuite, une estimation des heures de départ et d'arrivée pour l'accostage est calculée en tenant compte du graphique habituel non pondéré. Tout ce qui doit être fait à ce stade est de trouver toutes les routes valides entre les aéroports «A» et «B» avec un nombre prédéterminé de transferts, par exemple trois.



Étant donné qu'à ce stade, le graphique n'est pas pondéré, il est possible de trouver le chemin le plus court en utilisant la recherche en largeur d'abord habituelle, et tous les autres chemins les plus courts en utilisant l'algorithme Yen. Étant donné que la recherche en largeur est effectuée en temps linéaire, nous pouvons dire que le temps de recherche pour tous les chemins, avec les mêmes 3 transferts, sera linéaire.

Lors de l'évaluation de l'utilisation d'algorithmes pour trouver des itinéraires optimaux et de la disponibilité des données sur la fréquence des mises à jour d'horaires, nous pouvons dire que l'idée d'une matrice précalculée avec tous les chemins les plus "courts" dans les directions est justifiée. Bien sûr, au stade initial de la création de la matrice, une telle solution se révélera être des calculs laborieux, mais à l'avenir, elle vous permettra de trouver presque instantanément les chemins les plus «courts» et d'apporter rapidement des ajustements à la matrice elle-même.

Cependant, la question demeure, et quels itinéraires «plus courts» avec correspondances et transferts sont les plus «courts»? Sinon, nous avons un tableau de données qui ne nous permettra pas de prendre une décision. Un ensemble de critères est souvent réduit au plus optimal dans ce cas, à savoir:

• temps de voyage minimum;
• nombre minimum de transferts.

Les deux critères peuvent avoir des intervalles ou des valeurs de temps personnalisés, il ne reste donc qu'à combiner les itinéraires et vérifier à la volée la correspondance des valeurs admissibles:



Étant donné que le nombre maximal de transferts varie en valeurs de 3-4, certaines combinaisons de vols seront immédiatement exclues , nous conduisant à la solution du sous-problème suivant - identifier parmi les itinéraires les critères les plus «optimaux» pour la variété.

Le système de critères est le principal problème dans la formation de l'émission des itinéraires, car le concept d '"optimal" dépendra des préférences d'un passager particulier, et il ne peut souvent, à la réception d'une réponse à la demande, gérer les itinéraires reçus qu'en définissant un ensemble différent de filtres. Et même si vous lui fournissez des itinéraires ordonnés selon les chemins «les plus courts», les résultats seront un tableau de données qui ne permettra pas au passager de décider et conduira à une recherche infinie d'options. Par conséquent, la formation d'un tableau d'options d'itinéraire qui prennent en compte diverses combinaisons d'application de filtre, à la fois collectivement et individuellement, est un paramètre extrêmement important qui affecte l'ensemble de la tâche.

Que faut-il alors considérer et comment? La création de filtres de classement est une tâche très longue, car un ensemble de filtres, leur nombre et le degré d'influence les uns sur les autres peuvent modifier considérablement le résultat de la recherche de chemins optimaux grâce au développement d'algorithmes de recherche. En quoi cela peut-il consister? Nous connaissons tous les principaux paramètres de vol - informations sur les compagnies aériennes, dates avec heures de départ / d'arrivée, aéroports de départ / arrivée, décalages de fuseau horaire, correspondances et transferts, mais nous oublions souvent des données telles que le temps nécessaire et suffisant pour arriver à l'aéroport ou le temps de trajet entre les aéroports pour établir une correspondance dans le cas où le départ ultérieur se fait depuis un autre point du lieu. Et nous ne devons pas oublier la catégorie de notre passager,ainsi que leur quantité pour l'offre ultérieure non seulement de l'itinéraire optimal dans le temps, mais aussi dans le prix, en fonction de la politique tarifaire.

Un éventail d'offres devrait inspirer une certaine confiance à chaque voyageur, aussi paradoxal que cela puisse paraître. Confiance basée sur des principes mathématiques et consistant à fournir un ensemble minimum de propositions avec des options d'itinéraire qui tiennent compte des préférences et réduisent le risque de force majeure. Et dans ce cas, la force majeure n'est pas seulement la probabilité d'un retard de vol ou de changements d'heure et d'aéroport de départ / arrivée, mais aussi des indicateurs tels que les situations naturelles, technologiques et épidémiologiques qui entraînent l'annulation totale ou partielle des vols.

La capacité à gérer les données dans nos réalités soulève à chaque fois de nombreuses questions: tout est-il pris en compte, quoi d'autre peut être ajouté. Et dans cette volonté de construire un réseau de voies de transport, un paradoxe se pose lié au fait que l'algorithme doit être à la fois optimal et simple à la fois. Mais il faut souvent sacrifier quelque chose, d'ici quelque part en minimisant les critères initiaux au montant minimum me semblait le plus acceptable.

Si nous suivons le chemin de la sélection des critères, puis de l'omission des critères secondaires, nous pouvons distinguer de telles options qui prennent en compte non seulement la durée de l'ensemble du voyage, le coût et le confort, le nombre de transferts et leur durée, mais aussi, par exemple, des informations sur la congestion des aéroports et des données sur la communication entre les aéroports lors du passage d'un aéroport à un autre. Cela se justifie par le fait que lors de l'établissement de correspondances, compte tenu de la présence de plusieurs aéroports dans une ville qui ont des communications différentes avec les aéroports extérieurs, non seulement le trafic aérien, mais le temps de déplacement lorsqu'une telle situation se produit sera calculé dans le calcul du temps et de la formation de l'itinéraire. Et ils ont un endroit où être ...

Le système de prise de décision dans le choix des itinéraires «optimaux» dans les situations où nous avons un ensemble de critères qui affectent les préférences n'est que cette pierre d'achoppement à laquelle je n'ai pas du tout pensé aux étapes initiales. Même en les menant à une certaine systématisation, il y a beaucoup de différences dans leur application les uns avec les autres, nous les considérerons donc séparément.

Confort

La signification du concept de "confort" est comprise par tous différemment, mais les niveaux suivants sont acceptés par les compagnies aériennes:

• première année;
• Classe affaire;
• Classe économique.

Dans mon approche, j'ai admis que le paramètre «confort» peut être mesuré et prendre des valeurs de 1 à 10, et a formé la condition suivante: plus cet indicateur est bas pour un vol particulier, moins il sera confortable dans le système de classement. Dans ce cas, un problème se pose immédiatement qui est lié à la non-additivité d'une telle quantité, c'est-à-dire la somme des indicateurs de confort des deux vols ne reflétera pas leur confort global. Par exemple, il existe deux combinaisons d'itinéraire:

• le premier itinéraire avec deux segments, le premier raid avec confort 10, le second avec confort 1;
• le deuxième itinéraire avec deux segments, le premier raid avec confort 6, le second avec confort 5.

Par conséquent, la somme et la valeur moyenne arithmétique du paramètre «confort» de chaque chemin seront les mêmes, mais elles ne refléteront pas la véritable situation. Cependant, étant donné la nécessité de prendre en compte le confort global des deux itinéraires, il est préférable dans cette situation d'utiliser leurs valeurs moyennes conjointement avec l'écart-type, ce qui nous permettrait d'estimer la «dispersion» des niveaux de confort. Autrement dit, à la considération initiale, nous prêtons attention au confort moyen, puis, par l'ampleur de l'écart-type, nous considérons comment ces conforts diffèrent considérablement les uns des autres. Ainsi, ce critère se divise en deux très «proches». Bien que, d'autre part, même sans un examen minutieux, il est clair que l'hypothèse d'un tel niveau de confort "mesurable" est très loin de la réalité,parce que nous avons des niveaux de classe bien connus. Et d'autre part, il est également évident que le confort de l'ensemble du voyage est dans une sorte de dépendance fonctionnelle à d'autres critères, par exemple, la durée du vol, le nombre de transferts avec leur durée, la note de la compagnie aérienne et de sa flotte aérienne. Il est judicieux de se concentrer sur ce critère. Après tout, l'approche repose sur un système de prise en compte de l'ensemble des voies «optimales». Par conséquent, à l'avenir, nous utiliserons la représentation du confort sous la forme de deux indicateurs: la moyenne arithmétique des indicateurs de confort des vols et leur écart type.le nombre de transferts avec leur durée, la note de la compagnie aérienne et de sa flotte aérienne. Il est judicieux de se concentrer sur ce critère. Après tout, l'approche repose sur un système de prise en compte de l'ensemble des voies «optimales». Par conséquent, à l'avenir, nous utiliserons la représentation du confort sous la forme de deux indicateurs: la moyenne arithmétique des indicateurs de confort des vols et leur écart type.le nombre de transferts avec leur durée, la note de la compagnie aérienne et de sa flotte aérienne. Il est judicieux de se concentrer sur ce critère. Après tout, l'approche repose sur un système de prise en compte de l'ensemble des voies «optimales». Par conséquent, à l'avenir, nous utiliserons la représentation du confort sous la forme de deux indicateurs: la moyenne arithmétique des indicateurs de confort des vols et leur écart type.

Durée des transferts

Il existe deux types de coordination des itinéraires:

• transferts (accord préalable entre les compagnies aériennes);
• amarrage.

Le concept de «correspondance» présente un intérêt dans cette liste, qui est le résultat de la combinaison de deux ou plusieurs compagnies aériennes sur la même route avec des périodes convenues, sur la base du temps de correspondance minimum requis, mais pas toujours suffisant pour un transfert d'un vol à un autre. Par conséquent, pour combiner des vols, dans une telle route, il est nécessaire de calculer le temps suffisant nécessaire pour terminer la connexion.

Nous avons ici une dissonance, car souvent de tels vols peuvent être exclus des options de l'offre, mais, en raison de la présence d'un tel critère, il existe des situations où la connexion avec une attente temporaire de plus d'une journée est «optimale» pour notre passager. Par conséquent, il est logique de ne pas rejeter les itinéraires avec des délais de transplantation trop longs, car, bien que rarement, ils peuvent toujours être demandés.

Aéroport

congestion L'indicateur de congestion de l' aéroport peut être estimée lors du calcul des routes « optimales » avec une évaluation du degré de leur remplissage lors de la vente de billets pour des vols, en tenant compte de la participation d'un aéroport sur la route. Évidemment, dans cette hypothèse, le temps de correspondance minimum aura une certaine dépendance fonctionnelle à la congestion de l'aéroport.

Nombre de transferts

Le nombre de transplantations en soi est un montant contradictoire. En effet, c'est souvent de cette façon que l'on peut réduire le coût de l'ensemble du parcours. D'un autre côté, il existe une catégorie de passagers pour laquelle la présence d'un seul changement crée un certain nombre de problèmes. N'oubliez pas les situations où l'itinéraire de transfert est le plus «optimal» en raison du fait que les billets chers en classe affaires restent sur l'itinéraire souhaité ou, par exemple, il y a des billets avec un tarif sans possibilité d'échange / remboursement, ce qui implique la probabilité de refus l'option proposée.

Mais dans le nombre de transferts, un autre sous-critère est défini - c'est la probabilité de passer d'un aéroport à un autre. Par conséquent, la création de connexions est souvent une tâche difficile, car lors du calcul de l'itinéraire, il est nécessaire de prévoir le temps de déplacement entre les aéroports, ce qui implique la nécessité de commander des billets pour le transport dans la ville pour se déplacer en sous-paragraphes.

Les critères «temps de trajet» et «coût» sont des quantités absolument additives, ils reposent donc sur des indicateurs directs avec un système de classement. Et tout irait bien s'il n'y avait pas la nécessité d'inclure le temps de trajet total avec le calcul de l'heure d'arrivée à l'aéroport ou de départ de celui-ci à la destination, ainsi que lors de la connexion de la comptabilité pour le besoin de dépenses supplémentaires pour se déplacer entre les aéroports. À ce stade, permettez-moi de négliger cette clarification.

La structure hiérarchique de l'objectif global

Supposons que la définition de «l'optimalité» doit être comprise comme la meilleure toujours et pour tous, et pas seulement pour les passagers, mais aussi pour les compagnies aériennes, les aéroports et, éventuellement, d'autres prestataires de services de voyage.

Dans ce cas, la division d'une cible unique et très complexe en sous-objectifs est la seule issue. Une telle ventilation peut ressembler à ceci:



Il est bien évident que pour satisfaire tous les domaines d'intérêt, il faudra atteindre des objectifs moins «globaux», mais dans une certaine mesure contradictoires. Comment y parvenir? C'est peut-être un excellent sujet pour un autre article. Mais pour l'avenir, nous pouvons dire que la division d'un objectif complexe en sous-objectifs plus simples est également associée à l'optimisation et à la théorie des graphes, à savoir la recherche de structures hiérarchiques optimales.

Le système de prise de décision est assez étroitement lié à des méthodes telles que les critères de Laplace, Wald, Savage et Hurwitz.

L'une des approches les plus universelles pour résoudre les problèmes d'optimisation polyvalents est la recherche de solutions optimales par Pareto et Slater. Si nous évaluons le tableau des itinéraires les plus "courts" selon le critère d'optimalité de Slater, alors le chemin optimal sera considéré comme étant le meilleur par tous les critères en même temps. Un chemin est considéré comme optimal de Pareto si tous les autres chemins sont meilleurs que lui dans un paramètre, mais pire dans un autre, c'est-à-dire on ne peut pas améliorer un chemin par au moins un critère sans l'aggraver par le reste.

Toutes les solutions d'optimalité Pareto et Slater peuvent être facilement démontrées graphiquement pour le problème de minimisation avec deux critères: L'



ensemble des points avec les paramètres des critères optimaux Pareto sont indiqués en vert et les optimaux Slater sont indiqués en jaune. L'ensemble des points optimaux Slater contient également l'ensemble des points optimaux Paretto. Dans le cadre du problème considéré, tous ces points seront les extrémités des vecteurs à partir de l'origine de l'espace à sept dimensions.

En conclusion, je peux dire que ce n'est que la pointe de l'iceberg, ce qui vous permet de donner une première idée de ce que rencontrent les moteurs de recherche lors de la formation de routes optimales.