Logística. Introducción Casi complicado

A todos nos encanta soñar, especialmente cuando se trata de visitar nuevos lugares o regresar a sus lugares favoritos. Nada inspira tanto como una sensación de anticipación de un evento planificado y se ve eclipsado solo por la presencia de problemas de organización, en particular, la selección y compra de boletos de avión. Y por alguna razón, internamente, siempre posponemos este problema o lo cambiamos a operadores turísticos, metabuscadores u otros agregadores. En la práctica de cada uno, hubo situaciones en las que se mostraba un mensaje en la pantalla: “Desafortunadamente, no se encontró nada para su solicitud. Puede haber vuelos para otros días ".

Como sucede a menudo, está lejos de ser siempre en respuesta a una solicitud con una búsqueda de ruta que se da el resultado deseado con un vuelo, que inmediatamente pasa a la caja. Comenzamos a movernos de un sitio a otro para obtener una respuesta satisfactoria.

La ocurrencia de casos similares se asocia con la falta de comunicación directa o rutas combinadas (conectadas) planificadas previamente, o se propusieron rutas con transferencias que incluyeron el tiempo de espera para el próximo vuelo durante más de 5-6 horas, o incluso un día entero.

¿Cómo es que con toda la variedad de aerolíneas obtenemos respuestas que están lejos de satisfacernos siempre y, en general, cómo se construyen algorítmicamente los algoritmos para encontrar opciones de ruta? En este asunto, las matemáticas aplicadas nos ayudan utilizando algoritmos y criterios de evaluación.


Mapa mundial de aeropuertos

He estado lidiando con problemas logísticos durante mucho tiempo y cuando me enfrenté a la tarea de construir un motor de búsqueda que buscara rutas óptimas, me pareció bastante trivial. Por experiencia, podría decir de antemano que se puede resolver mediante métodos bastante simples y en un tiempo relativamente corto. Sin embargo, si todo fuera tan simple, entonces este artículo no habría aparecido. Por lo tanto, después de unirme al trabajo, después de un tiempo me di cuenta de que no era tan trivial.

El punto de partida, como sucede a menudo cuando viajo, y fue con este enfoque que se me ocurrió, fue la decisión de construir una red de transporte en forma de gráfico. La red de transporte inicialmente incluía datos sobre aeropuertos, aerolíneas, sus horarios de vuelo e indicadores de tiempo de conexión.

Se tomó como base que los aeropuertos se consideran como la parte superior del gráfico, y los vuelos entre ellos son bordes. Como resultado, obtuvimos un esqueleto, como en un esqueleto, en base al cual comencé a imponer un horario que tenía sus propias características: horarios de salida y llegada. Además, el movimiento a lo largo de los bordes siempre es posible solo en un momento determinado, que se caracteriza por opciones particulares para resolver el problema:

• tiempo mínimo de viaje;
• número mínimo (o adecuado en lenguaje sencillo) de trasplantes;
• intervalo de tiempo para la transferencia de un vuelo a otro al elegir rutas complejas.

La dificultad radica en el hecho de que bajo ninguna circunstancia tenemos solo un caso particular, la solicitud siempre contiene criterios de búsqueda relacionados, incluidos uno o dos o más refinamientos. De ello se deduce que la aplicación del criterio impone ciertas condiciones en el cálculo de las opciones de ruta deseadas. Además de los tres enumerados anteriormente, el cálculo incluye el uso de categorías de clases de servicio (primero, negocios, economía), costo, número de pasajeros y sus categorías, así como la disponibilidad de una serie de servicios adicionales que afectan el resultado. Por lo tanto, esto comenzó a encajar completamente en mi concepto de resolver el problema por medio de la optimización de criterios múltiples (optimización de propósitos múltiples), a saber, encontrar el camino más corto por varios criterios (MOSP - camino más corto de múltiples objetivos).

Pero, como todos saben, para probar una hipótesis, se deben citar otras. Como otra opción para resolver el problema, se consideró el uso de programación no lineal.

Dado que los arcos de la gráfica están ponderados por vectores, la solución del problema podría reducirse a la programación cuadrática (no lineal). Y todo sería perfecto si no fuera por el hecho de que los vectores, de hecho, solo tienen dos características: longitud y proyección en los ejes de coordenadas, lo que significa la presencia en la función objetivo de variables con un grado de no más de dos. Sin embargo, en mi caso, los componentes de los vectores "entran en conflicto" entre sí, lo que contradice la programación no lineal (cuadrática). Por ejemplo: "conflicto" puede deberse al hecho de que cada vuelo tiene una capacidad de aeronave específica y es imposible venderle más asientos. Debido a la presencia de "conflictos", la opción de resolver el problema mediante programación no lineal tuvo que ser abandonada en favor de la misma programación de criterios múltiples.

Después de analizar las opciones para resolver el problema, elegí la versión clásica de descomposición con las siguientes partes:

1. búsqueda basada en el horario de todas las rutas "más cortas" desde el punto de partida hasta el punto de llegada;
2. buscar entre los caminos "más cortos" de los más "óptimos" según los criterios.

Al mismo tiempo, después de la descomposición, la pregunta siguió lógicamente, pero ¿en base a qué enfoque es mejor construir una red de rutas de transporte? ¿Y cuál de los gráficos disponibles es más aceptable para resolver este problema?

Según los clásicos del género, no se encontró ninguno, sino varios modelos, que comencé a considerar.

Modelo de tiempo extendido

Un gráfico extendido en el tiempo es un gráfico dirigido. Los arcos de dicho gráfico son las direcciones de los puntos de salida y llegada de los vuelos, y los picos son las franjas horarias (tiempos de despegue y aterrizaje) de los vuelos. El uso del modelo extendido en el tiempo es para expandir el gráfico original con picos y arcos de aeropuertos, reflejando la relación de rutas combinando aeropuertos entre ellos de acuerdo con el horario de vuelo: los



arcos se indican como$$$e_{BC,3}$. Por ejemplo, un arco conecta un aeropuerto$$$B$ con aeropuerto $$$$C$$y dirigido desde $$$B$a $$$C$especificado por el índice de coma $$$3$muestra que este no es el único vuelo, sino el tercero consecutivo. Además, cada arco se puede ponderar fácilmente, por ejemplo, el peso del arco$$$e_{BC,3}$ se puede calcular como $$$w_{BC,3} = t_{C,9}-t_{B,6}$. Los vértices dentro de un solo aeropuerto se organizan fácilmente de acuerdo con el indicador de tiempo de cada vuelo, y también, según el tiempo de conexión dentro del aeropuerto, los vuelos están conectados por arcos que corresponden al tiempo disponible de transferencia de un vuelo a otro.

La ventaja de un gráfico expandido en el tiempo es que la ruta de llegada más rápida se puede encontrar en el menor tiempo, por ejemplo, utilizando el algoritmo Dijkstra. La desventaja de usar este enfoque es el aumento múltiple en vértices y bordes, que, sin embargo, no afecta la escasez del gráfico, porque un aumento en el número de bordes es proporcional a un aumento en el número de vértices.

Modelo dependiente del tiempo

Un gráfico dependiente del tiempo es un gráfico dirigido sin transformaciones adicionales sobre el gráfico original. Cada arco corresponde a una ruta con conexiones entre aeropuertos, mientras que el arco tiene un conjunto especial de datos que incluye parámetros sobre la hora de salida y llegada del vuelo a lo largo de la ruta. El valor recuperado de este conjunto de datos depende del momento exacto en que se produce el acceso a este arco, de ahí el nombre "dependiente del tiempo".



La ventaja de un gráfico dependiente del tiempo es que le permite encontrar la ruta con el menor número de transferencias, la desventaja es la carga excesiva en los datos de cada arco.

Multigrafo

Un multigrafo es un gráfico dirigido con conjuntos de características inherentes en modelos mejorados y dependientes del tiempo.



Hay tantos arcos entre aeropuertos como durante el modelo extendido, pero estos arcos están "ponderados" por los horarios de salida y llegada, y el tiempo de conexión entre vuelos en cada aeropuerto deberá calcularse de manera constante y repetida. Por otro lado, en una representación de múltiples gráficos hay exactamente tanta información sobre vuelos como durante un modelo dependiente del tiempo, pero toda esta información se asigna a muchos arcos. Encontrar la ruta con el menor número de transferencias será tan simple como durante el modelo dependiente del tiempo, pero pasar un arco no tiene en cuenta la información de otros arcos, por lo que después de encontrar la ruta con el menor número de transferencias, tendrá que repetir esta ruta para cálculo de información sobre otros vuelos (arcos).

La representación de una red de rutas de transporte en forma de multigrafo es un estado sin procesar para los modelos de tiempo extendido y dependientes del tiempo. La búsqueda de la ruta con la llegada más corta se realizará mediante las mismas transformaciones características del modelo expandido en el tiempo, y la búsqueda de la ruta con el menor número de transferencias se realizará mediante el modelo dependiente del tiempo. Y conlleva un aumento en el tiempo de cálculo de la red. Sin embargo, hay un matiz aquí, porque la búsqueda del camino "más corto" de acuerdo con dos criterios, en el caso general, ya pertenece a la clase NP de tareas difíciles y la modificación del algoritmo de Dijkstra realiza manipulaciones bastante complejas con el marcado de vértices.

La representación de la complejidad computacional del problema con la multigrafía del modelo del conjunto de rutas con aeropuertos y vuelos puede considerarse a través del método de modificación más simple: el algoritmo de Dijkstra, que busca solo las rutas óptimas de Pareto. La cantidad total de criterios para una sola ruta óptima de Pareto no puede ser peor o mejor que otras rutas óptimas de Pareto para todos los criterios simultáneamente. Por ejemplo, un conjunto de rutas con la siguiente suma de dos criterios {(30, 10), (20, 20), (10, 30)} será óptimo para Pareto.

Como un ejemplo más ilustrativo, consideramos la operación del algoritmo en un gráfico pequeño cuyos arcos son ponderados por vectores bidimensionales:



La operación del algoritmo de Dijkstra modificado en dicho gráfico, así como el algoritmo normal para un gráfico regular, consistirá en iteraciones con sucesivos golpes de los vértices, excepto que cada vértice puede tener un valor óptimo de Pareto, sino varios. Además, también es necesario guardar información sobre el origen de cada valor calculado de la suma.

Dado que el problema considera rutas con conexiones al aeropuerto para vuelos, es bastante apropiado asumir que puede haber muchos arcos entre dos vértices, y cada uno de ellos puede ser ponderado por al menos un vector de tres componentes. Pero con un aumento en los componentes de los vectores, también puede ocurrir un aumento en las rutas óptimas de Pareto. Además, casi todos los arcos entre dos vértices pueden ser óptimos para Pareto. En este caso, la suma de las rutas contendrá aún más rutas óptimas de Pareto. Esto se puede ver en un pequeño multigrafo ponderado por vectores bidimensionales:



el uso del algoritmo de Dijkstra modificado en dicho modelo es permisible, ya que puede funcionar en multigrafos, pero la velocidad de procesamiento del algoritmo depende del número de vértices$$$n$, y en el número de arcos $$$m$. Para gráficos simples dispersos y el algoritmo habitual, la complejidad es del orden de$$$O(n\log n+m\log n)$. Sin embargo, es difícil decir si el multigrafo resultante será "escaso", ya que en el caso general la densidad del borde de los multigrafos puede ser mucho mayor que la de un gráfico completo. Si tenemos en cuenta que el número de aristas de un gráfico completo$$$E$ determinado por el número de sus vértices $$$V$de acuerdo con la fórmula:

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

Y la densidad del borde se define como:

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

Para gráficos completos $$$max(D) = 1$, pero para los multigrafos, el valor de la densidad del borde es generalmente ilimitado.

Por lo tanto, llegué a la conclusión de que la ruta más corta se puede encontrar usando el algoritmo Dijkstra, y todas las demás rutas más cortas se pueden encontrar usando el algoritmo Yen. Dado que en esta etapa operamos con arcos no ponderados y podemos descartar rutas inmediatamente, por ejemplo, con cuatro transferencias, entonces se garantizará que la búsqueda de una ruta más corta se realice en menos de$$$O(n^{2})$.



Teniendo en cuenta que este artículo no cubre los resultados inmediatos de la implementación, puedo suponer de antemano que el algoritmo Dijkstra modificado en un modelo multigráfico no funcionará teniendo en cuenta el intervalo de tiempo óptimo.

Por lo tanto, pasaré a la solución inmediata del primer subproblema, es decir, a la solución de la pregunta relacionada con la optimización multicriterio, que seleccioné por el método de optimización condicional. El método consiste en el hecho de que a pesar de la inconsistencia de los criterios, la prioridad más alta siempre existe, y todos los demás tienen valores válidos. Como resultado, la optimización de toda la tarea se reduce a la optimización con la máxima prioridad.

Una característica de la tarea es el hecho de que el cálculo incluye no solo vuelos directos, lo que siempre simplifica enormemente la tarea, sino, por el contrario, vuelos o transferencias de conexión. Por lo tanto, el modelo gráfico dependiente del tiempo es muy adecuado para resolver el problema, porque a menudo el número de transferencias no forma más de 3-4 segmentos en la ruta. El gráfico dependiente del tiempo, en primer lugar, contiene información sobre la totalidad de las rutas disponibles en forma de vuelos con conexiones entre aeropuertos. Luego, se calcula una estimación de los tiempos de salida y llegada para el atraque teniendo en cuenta el gráfico no ponderado habitual. Todo lo que debe hacerse en esta etapa es encontrar todas las rutas válidas entre los aeropuertos "A" y "B" con un número predeterminado de transferencias, por ejemplo, tres.



Teniendo en cuenta que en esta etapa el gráfico no está ponderado, es posible encontrar la ruta más corta utilizando la búsqueda de amplitud habitual, y todas las demás rutas más cortas utilizando el algoritmo Yen. Dado que la búsqueda de amplitud se realiza en tiempo lineal, podemos decir que el tiempo de búsqueda para todas las rutas, con las mismas 3 transferencias, será lineal.

Al evaluar el uso de algoritmos para encontrar rutas óptimas y la disponibilidad de datos sobre la frecuencia de las actualizaciones de horarios, podemos decir que la idea de una matriz precalculada con todas las rutas "más cortas" en las direcciones está justificada. Por supuesto, en la etapa inicial de creación de la matriz, dicha solución resultará en cálculos laboriosos, pero luego, en el futuro, le permitirá encontrar casi instantáneamente los caminos "más cortos" y realizar ajustes rápidamente en la matriz.

Sin embargo, la pregunta sigue siendo, y ¿qué rutas de ruta "más cortas" con conexiones y transferencias son las más "más cortas"? De lo contrario, tenemos una serie de datos que no nos permitirán tomar una decisión. Un conjunto de criterios a menudo se reduce al más óptimo en este caso, a saber:

• tiempo mínimo de viaje;
• Número mínimo de transferencias.

Ambos criterios pueden tener intervalos de tiempo o valores de tiempo personalizables, por lo que solo queda combinar las rutas y verificar "sobre la marcha" el cumplimiento de los valores permitidos:



dado que el número máximo de transferencias varía entre 3-4, algunas combinaciones de vuelo se excluirán inmediatamente , que nos lleva a la solución del siguiente subproblema: identificar entre las rutas los criterios más "óptimos" para la variedad.

El sistema de criterios es el principal problema en la formación de la emisión de rutas, porque el concepto de "óptimo" dependerá de las preferencias de un pasajero en particular, y a menudo solo al recibir una respuesta a la solicitud puede administrar las rutas recibidas al establecer un conjunto diferente de filtros. E incluso si le proporciona rutas ordenadas de acuerdo con las rutas "más cortas", los resultados serán una serie de datos que no permitirán que el pasajero decida y conducirá a una búsqueda interminable de opciones. Por lo tanto, la formación de una variedad de opciones de ruta que tengan en cuenta varias combinaciones de aplicación de filtro, tanto colectiva como individualmente, es un parámetro extremadamente importante que afecta a toda la tarea.

¿Qué hay que tener en cuenta y cómo? Crear filtros de clasificación es una tarea que consume mucho tiempo, porque un conjunto de filtros, su número y el grado de influencia entre ellos pueden cambiar significativamente el resultado de la búsqueda de rutas óptimas como resultado del refinamiento de los algoritmos de búsqueda. Entonces, ¿en qué puede consistir? Todos conocemos los parámetros clave de vuelo: información sobre aerolíneas, fechas con horarios de salida / llegada, aeropuertos de salida / llegada, compensaciones de zona horaria, conexiones y transferencias, pero a menudo olvidamos datos como el tiempo necesario y suficiente para llegar al aeropuerto o tiempo de viaje entre aeropuertos para establecer una conexión en el caso de que la salida posterior sea desde otro punto de la ubicación. Y no debemos olvidarnos de la categoría de nuestro pasajero,así como su cantidad para la oferta posterior de no solo la ruta óptima en el tiempo, sino también en el precio, dependiendo de la política de tarifas.

Una variedad de ofertas debe inculcar un cierto grado de confianza en cada viajero, sin importar cuán paradójico pueda sonar. Confianza basada en principios matemáticos y consistente en la provisión de un conjunto mínimo de propuestas con opciones de ruta que tengan en cuenta las preferencias y reduzcan el riesgo de fuerza mayor. Y en este caso, la fuerza mayor no es solo la probabilidad de un retraso en el vuelo o un cambio en el horario y el aeropuerto de salida / llegada, sino también indicadores tales como situaciones naturales, tecnológicas y epidemiológicas que implican la cancelación total o parcial de los vuelos.

La capacidad de gestionar datos en nuestras realidades conlleva muchas preguntas cada vez: se tiene todo en cuenta, qué más se puede agregar. Y en este deseo de construir una red de rutas de transporte, surge una paradoja relacionada con el hecho de que el algoritmo debe ser tanto óptimo como simple al mismo tiempo. Pero a menudo tienes que sacrificar algo, desde aquí, en algún lugar, minimizar el criterio inicial a la cantidad mínima me pareció lo más aceptable.

Si seguimos el camino de selección de criterios, omitiendo los secundarios, podemos distinguir esas opciones que tienen en cuenta no solo el tiempo de todo el viaje, el costo y la comodidad, el número de transferencias y su duración, sino, por ejemplo, información sobre la congestión de aeropuertos y datos sobre comunicación entre aeropuertos. al cambiar de un aeropuerto a otro. Esto se justifica por el hecho de que cuando se forman conexiones, teniendo en cuenta la presencia de varios aeropuertos en una ciudad que tienen diferentes comunicaciones con aeropuertos externos, no solo el tráfico aéreo, sino el tiempo de movimiento cuando surge tal situación se calculará en el cálculo del tiempo y la formación de la ruta. Y tienen un lugar para estar ...

El sistema de toma de decisiones al elegir las rutas "óptimas" en situaciones en las que tenemos un conjunto de criterios que afectan las preferencias es solo ese obstáculo en el que no pensé en absoluto en las etapas iniciales. Incluso llevándolos a una cierta sistematización, hay muchas diferencias en su aplicación entre ellos, por lo que los consideraremos por separado.

Confort

El significado del concepto de "confort" es entendido por todos de manera diferente, pero las aerolíneas aceptan los siguientes niveles:

• primer grado;
• Clase de negocios;
• Clase de economia.

En mi enfoque, admití que el parámetro "confort" se puede medir y tomar valores del 1 al 10, y formé la siguiente condición: cuanto más bajo sea este indicador para un vuelo en particular, menos cómodo será en el sistema de clasificación. En este caso, surge inmediatamente un problema relacionado con la no aditividad de dicha cantidad, es decir, La suma de los indicadores de confort de los dos vuelos no reflejará su confort general. Por ejemplo, hay dos combinaciones de ruta:

• la primera ruta con dos segmentos, la primera incursión con comodidad 10, la segunda con comodidad 1;
• la segunda ruta con dos segmentos, la primera incursión con comodidad 6, la segunda con comodidad 5.

Como resultado, la suma y el valor medio aritmético del parámetro "confort" de cada ruta serán los mismos, pero no reflejarán el verdadero estado de cosas. Sin embargo, dada la necesidad de considerar la comodidad agregada de las dos rutas, es más aconsejable en esta situación usar sus valores promedio junto con la desviación estándar, lo que nos permitiría estimar la "extensión" de los niveles de comodidad. Es decir, en la consideración inicial, prestamos atención a la comodidad promedio, y luego, por la magnitud de la desviación estándar, consideramos cómo estas comodidades difieren mucho entre sí. Por lo tanto, este criterio se divide en dos muy "cercanos". Aunque, por otro lado, incluso sin un examen minucioso, está claro que la suposición de un nivel de confort tan "medible" está muy lejos de la realidad,porque tenemos niveles de clase bien conocidos. Y en segundo lugar, también es obvio que la comodidad de todo el viaje depende de algún tipo de dependencia funcional de otros criterios, por ejemplo, la duración del vuelo, el número de transferencias con su duración, la calificación de la aerolínea y su flota aérea. Si tiene sentido centrarse en este criterio es una pregunta. Después de todo, el enfoque se basa en un sistema de contabilidad para la totalidad de las formas "óptimas". Por lo tanto, en el futuro utilizaremos la representación de confort en forma de dos indicadores: la media aritmética de los indicadores de confort de los vuelos y su desviación estándar.el número de transferencias con su duración, la calificación de la aerolínea y su flota aérea. Si tiene sentido centrarse en este criterio es una pregunta. Después de todo, el enfoque se basa en un sistema de contabilidad para la totalidad de las formas "óptimas". Por lo tanto, en el futuro utilizaremos la representación de confort en forma de dos indicadores: la media aritmética de los indicadores de confort de los vuelos y su desviación estándar.el número de transferencias con su duración, la calificación de la aerolínea y su flota aérea. Si tiene sentido centrarse en este criterio es una pregunta. Después de todo, el enfoque se basa en un sistema de contabilidad para la totalidad de las formas "óptimas". Por lo tanto, en el futuro utilizaremos la representación de confort en forma de dos indicadores: la media aritmética de los indicadores de confort de los vuelos y su desviación estándar.

Duración de los traslados

Hay dos tipos de coordinación de ruta:

• transferencias (previamente acordadas entre aerolíneas);
• unión cósmica.

De esta lista es interesante el concepto de "conexión", que es el resultado de una combinación de dos o más aerolíneas en la misma ruta con períodos de tiempo acordados, en función del tiempo mínimo de conexión requerido, pero no siempre suficiente para transferir de un vuelo a otro. Por lo tanto, para combinar vuelos, en tal ruta, es necesario calcular el tiempo suficiente requerido para completar la conexión.

Aquí tenemos una disonancia, porque a menudo dichos vuelos pueden excluirse de las opciones de la oferta, pero, debido a la presencia de dicho criterio, hay situaciones en las que conectarse con una espera temporal de más de un día es "óptimo" para nuestro pasajero. Por lo tanto, tiene sentido no descartar rutas con tiempos de trasplante demasiado largos, ya que, aunque raramente, todavía pueden estar en demanda.

Aeropuerto

congestión El indicador de congestión de los aeropuertos se puede estimar la hora de calcular las rutas “óptimas” con una evaluación de su grado de llenado en la venta de boletos para los vuelos, teniendo en cuenta la participación de un aeropuerto en la ruta. Obviamente, en este supuesto, el tiempo mínimo de conexión tendrá cierta dependencia funcional de la congestión del aeropuerto.

Numero de transferencias

El número de trasplantes per se es una cantidad contradictoria. De hecho, a menudo es así como puede reducir el costo de toda la ruta. Por otro lado, hay una categoría de pasajeros para quienes la presencia de un solo cambio crea una serie de problemas. No olvide las situaciones en las que la ruta de transferencia es la más "óptima" debido al hecho de que los boletos caros de clase ejecutiva se dejan en la ruta deseada o, por ejemplo, hay boletos con una tarifa sin la posibilidad de cambio / devolución, lo que implica la probabilidad de rechazo La opción propuesta.

Pero en el número de transferencias, se establecen otros subcriterios: esta es la probabilidad de trasladarse de un aeropuerto a otro. Por lo tanto, la formación de conexiones es a menudo una tarea difícil, porque al calcular la ruta, es necesario establecer el tiempo para moverse entre aeropuertos, y esto implica la necesidad de pedir boletos para el transporte dentro de la ciudad para moverse en subpárrafos.

Los criterios "tiempo de viaje" y "costo" son cantidades absolutamente aditivas, por lo tanto, se basan en indicadores directos con un sistema de clasificación. Y todo estaría bien si no fuera por la necesidad de incluir el tiempo total de viaje con el cálculo del tiempo de llegada al aeropuerto o de salida del mismo al destino, así como al conectar la contabilidad de la necesidad de gastos adicionales para moverse entre aeropuertos. En esta etapa, permítanme descuidar esta aclaración.

La estructura jerárquica del objetivo global.

Suponga que la definición de "óptima" debe entenderse como la mejor siempre y para todos, y no solo para los pasajeros, sino también para las aerolíneas, los aeropuertos y, posiblemente, otros proveedores de servicios de viaje.

En este caso, dividir un objetivo único y muy complejo en submetas es la única salida. Tal desglose puede verse así:



es bastante obvio que para satisfacer todas las áreas de interés, uno tendrá que lograr objetivos menos "globales", pero en cierta medida conflictivos. ¿Cómo lograr esto? Quizás este es un gran tema para otro artículo. Pero mirando hacia el futuro, podemos decir que dividir un objetivo complejo en objetivos secundarios más simples también está asociado con la optimización y la teoría de grafos, es decir, la búsqueda de estructuras jerárquicas óptimas.

El sistema de toma de decisiones está estrechamente relacionado con métodos como los criterios de Laplace, Wald, Savage y Hurwitz, por lo tanto, al tener una serie de rutas "más cortas", no pude evitar saber cuál de ellas sería la más "óptima" en función de ellas.

Uno de los enfoques más universales para resolver problemas de optimización multipropósito es la búsqueda de soluciones óptimas por parte de Pareto y Slater. Si evaluamos el conjunto de rutas "más cortas" de acuerdo con el criterio de optimización de Slater, la ruta óptima se considerará la mejor según todos los criterios al mismo tiempo. Una ruta se considera óptima de Pareto si todas las demás rutas son mejores que en un parámetro, pero peor en otro, es decir. uno no puede mejorar un camino por al menos un criterio sin empeorarlo por el resto.

Todas las soluciones de optimización de Pareto y Slater se pueden demostrar gráficamente fácilmente para el problema de minimización con dos criterios: el



conjunto de puntos con los parámetros de los criterios óptimos de Pareto se indican en verde, y los óptimos de Slater se indican en amarillo. El conjunto de puntos óptimos de Slater también contiene el conjunto de puntos óptimos de Paretto. Dentro del marco del problema en consideración, todos estos puntos serán los extremos de los vectores que comienzan en el origen del espacio de siete dimensiones.

En conclusión, puedo decir que esta es solo la punta del iceberg, que le permite dar una idea inicial de lo que los motores de búsqueda encuentran al formar rutas óptimas.