Logística. Introdução Quase complicado

Todos nós gostamos de sonhar, especialmente quando se trata de visitar novos lugares ou retornar aos seus lugares favoritos. Nada inspira apenas a sensação de antecipação de um evento planejado e é ofuscado apenas pela presença de questões organizacionais, em particular a seleção e compra de passagens aéreas. E, por alguma razão, internamente, sempre adiamos esse problema ou o mudamos para operadores turísticos, mecanismos de meta-pesquisa ou outros agregadores. Na prática de cada um, houve situações em que uma mensagem foi exibida na tela: “Infelizmente, nada foi encontrado para sua solicitação. Pode haver vôos para outros dias.

Como muitas vezes acontece, está longe de sempre em resposta a uma solicitação com uma pesquisa de rota que o resultado desejado com um voo seja fornecido, o que imediatamente ocorre no check-out. Começamos a mudar de site para site para obter uma resposta satisfatória.

A ocorrência de casos semelhantes está associada à falta de comunicação direta ou de rotas combinadas (de conexão) pré-planejadas, ou foram propostas rotas com transferências que incluíam tempo de espera para o próximo vôo por mais de 5-6 horas, ou mesmo um dia inteiro.

Como é que, com toda a variedade de companhias aéreas, obtemos respostas que nem sempre nos satisfazem e, em geral, como são construídos os algoritmos para encontrar opções de rotas? Nesse caso, a matemática aplicada vem em nosso auxílio usando algoritmos e critérios de avaliação.


Mapa dos aeroportos mundiais

Estou lidando com problemas de logística há muito tempo e, quando me deparei com a tarefa de criar um mecanismo de pesquisa que procuraria rotas ideais, me pareceu bastante trivial. Por experiência, eu poderia dizer com antecedência que ele pode ser resolvido por métodos bastante simples e em um tempo relativamente curto. No entanto, se tudo fosse tão simples, esse artigo não teria aparecido. Portanto, depois de me juntar ao trabalho, percebi que não era tão trivial.

O ponto de partida, como costuma acontecer durante as viagens, e foi com essa abordagem que surgiu, foi a decisão de construir uma rede de transporte na forma de gráfico. A rede de transporte inicialmente incluía dados sobre aeroportos, companhias aéreas, seus horários de voo e indicadores de tempo de conexão.

Tomou-se como base que os aeroportos são considerados o topo do gráfico e os vôos entre eles são bordas. Como resultado, adquirimos um esqueleto, como em um esqueleto, com base no qual comecei a impor um cronograma com características próprias: horários de partida e chegada. Além disso, o movimento ao longo das bordas é sempre possível apenas em um determinado momento, o que é caracterizado por opções específicas para resolver o problema:

• tempo mínimo de viagem;
• número mínimo (ou adequado em linguagem simples) de transplantes;
• intervalo de tempo para a transferência de um voo para outro ao escolher rotas complexas.

A dificuldade está no fato de que, sob nenhuma circunstância, temos o uso de apenas um caso específico, a consulta sempre contém critérios de pesquisa relacionados, incluindo um ou dois ou mais refinamentos. Daqui resulta que a aplicação do critério impõe certas condições no cálculo das opções de rota desejadas. Além das três listadas acima, o cálculo inclui o uso de categorias de classes de serviço (primeiro, negócios, economia), custo, número de passageiros e suas categorias, bem como a disponibilidade de vários serviços adicionais que afetam o resultado. Assim, isso começou a se encaixar completamente no meu conceito de resolver o problema por meio da otimização de múltiplos critérios (otimização de múltiplos propósitos), ou seja, encontrar o caminho mais curto de acordo com vários critérios (MOSP - caminho mais curto de múltiplos objetivos).

Mas, como todos sabem, para testar uma hipótese, várias outras devem ser citadas. Como outra opção para solucionar o problema, foi considerado o uso de programação não linear.

Dado que os arcos do gráfico são ponderados por vetores, a solução do problema pode ser reduzida à programação quadrática (não linear). E tudo seria perfeito se não fosse o fato de que os vetores têm apenas duas características: comprimento e projeção nos eixos coordenados, o que significa a presença na função objetiva de variáveis ​​com um grau não superior a dois. No entanto, no meu caso, os componentes dos vetores “conflitam” entre si, o que contradiz a programação não linear (quadrática). Por exemplo: “conflito” pode ser devido ao fato de que cada voo tem uma capacidade específica de aeronave e é impossível vender mais assentos para ele. Devido à presença de “conflitos”, a opção de resolver o problema pela programação não-linear teve que ser abandonada em favor da mesma programação com vários critérios.

Depois de analisar as opções para resolver o problema, fui com a versão clássica da decomposição com as seguintes partes:

1. pesquisa com base na programação de todas as rotas “mais curtas” do ponto de partida ao ponto de chegada;
2. procure entre os caminhos "mais curtos" dos mais "ótimos" com base em critérios.

Ao mesmo tempo, após a decomposição, a pergunta seguiu-se logicamente, mas com base em qual abordagem é melhor construir uma rede de rotas de transporte? E qual dos gráficos disponíveis é mais aceitável para resolver esse problema?

De acordo com os clássicos do gênero, não foi encontrado um, mas vários modelos, que comecei a considerar.

Modelo de tempo estendido

Um gráfico com extensão de tempo é um gráfico direcionado. Os arcos desse gráfico são as direções dos pontos de partida e chegada dos vôos, e os picos são os slots (horários de decolagem e pouso) dos vôos. O uso do modelo de tempo estendido é expandir o gráfico original com picos e arcos de aeroportos, refletindo a relação das rotas combinando os aeroportos entre si de acordo com o horário do voo: os



arcos são indicados como$$$e_{BC,3}$. Por exemplo, um arco conecta um aeroporto$$$B$ com aeroporto $$$$C$$e dirigido de $$$B$para $$$C$especificado pelo índice de vírgula $$$3$mostra que este não é o único vôo, mas o terceiro consecutivo. Além disso, cada arco pode ser facilmente ponderado, por exemplo, o peso do arco$$$e_{BC,3}$ pode ser calculado como $$$w_{BC,3} = t_{C,9}-t_{B,6}$. Os vértices dentro de um único aeroporto são facilmente ordenados de acordo com o indicador de tempo de cada voo e, também, com base no tempo de conexão dentro do aeroporto, os vôos são conectados por arcos que correspondem ao tempo disponível de transferência de um voo para outro.

A vantagem de um gráfico com tempo estendido é que o caminho de chegada mais rápido pode ser encontrado no menor tempo possível, por exemplo, usando o algoritmo Dijkstra. A desvantagem de usar essa abordagem é o aumento múltiplo dos vértices e arestas, que, no entanto, não afeta a dispersão do gráfico, porque um aumento no número de arestas é proporcional a um aumento no número de vértices.

Modelo dependente do tempo

Um gráfico dependente do tempo é um gráfico direcionado sem transformações adicionais sobre o gráfico original. Cada arco corresponde a uma rota com conexões entre aeroportos, enquanto o arco possui um conjunto de dados especiais que inclui parâmetros sobre a hora de partida e chegada do voo ao longo da rota. O valor recuperado desse conjunto de dados depende do momento exato em que o acesso ao arco ocorre, daí o nome "dependente do tempo".



A vantagem de um gráfico dependente do tempo é que ele permite encontrar o caminho com o menor número de transferências; a desvantagem é a carga excessiva nos dados de cada arco.

Multigraph

Um multigráfico é um gráfico direcionado com conjuntos de características inerentes a modelos aprimorados e dependentes de tempo.



Existem tantos arcos entre aeroportos quanto durante o modelo estendido, mas esses arcos são "ponderados" pelos horários de partida e chegada, e o tempo de conexão entre os vôos em cada aeroporto terá que ser calculado constante e repetidamente. Por outro lado, em uma representação multigráfica, há exatamente tanta informação sobre voos quanto durante um modelo dependente do tempo, mas todas essas informações são atribuídas a muitos arcos. Encontrar o caminho com o menor número de transferências será tão simples quanto durante o modelo dependente do tempo, mas passar um arco não leva em conta as informações de outros arcos; portanto, depois que o caminho com o menor número de transferências for encontrado, será necessário repetir esse caminho para cálculo de informações sobre outros voos (arcos).

A representação de uma rede de rotas de transporte na forma de multigráficos é um estado bruto para modelos de tempo estendido e dependentes de tempo. A busca pelo caminho com a chegada mais curta será realizada pelas mesmas transformações características do modelo de expansão de tempo e a busca pelo caminho com o menor número de transferências será realizada pelo modelo dependente de tempo. E implica um aumento no tempo de cálculo da rede. No entanto, há uma nuance aqui, porque a busca pelo caminho "mais curto" de acordo com dois critérios, no caso geral, já pertence à classe NP de tarefas difíceis e a modificação do algoritmo de Dijkstra realiza manipulações bastante complexas com a marcação de vértices.

A representação da complexidade computacional do problema com a multigrafagem do modelo do conjunto de rotas com aeroportos e vôos pode ser considerada pelo método de modificação mais simples - o algoritmo de Dijkstra, que busca apenas caminhos ótimos de Pareto. A quantidade total de critérios para um único caminho ideal de Pareto não pode ser pior ou melhor do que outros caminhos ideais de Pareto para todos os critérios simultaneamente. Por exemplo, um conjunto de caminhos com a seguinte soma de dois critérios {(30, 10), (20, 20), (10, 30)} será Pareto ideal.

Como um exemplo mais ilustrativo, consideramos a operação do algoritmo em um pequeno gráfico cujos arcos são ponderados por vetores bidimensionais:



A operação do algoritmo de Dijkstra modificado em um gráfico desse tipo, bem como o algoritmo normal de um gráfico regular, consistirá em iterações com golpes sucessivos dos vértices, exceto que cada vértice pode ter um valor ideal de Pareto, mas vários. Além disso, também é necessário salvar informações sobre a origem de cada valor calculado da soma.

Dado que o problema considera rotas com conexões aeroportuárias para vôos, é bastante apropriado supor que possa haver muitos arcos entre dois vértices, e cada um deles possa ser ponderado por pelo menos um vetor de três componentes. Porém, com um aumento nos componentes dos vetores, também pode ocorrer um aumento nos caminhos ideais de Pareto. Além disso, quase todos os arcos entre dois vértices podem ser ótimos para Pareto. Nesse caso, a soma dos caminhos conterá ainda mais caminhos ideais para Pareto. Isso pode ser visto em uma pequena multigráfica ponderada por vetores bidimensionais:



O uso do algoritmo Dijkstra modificado em um modelo desse tipo é permitido, pois pode funcionar em multigráficas, mas a velocidade de processamento do algoritmo depende do número de vértices$$$n$e no número de arcos $$$m$. Para gráficos simples esparsos e o algoritmo usual, a complexidade é da ordem de$$$O(n\log n+m\log n)$. No entanto, é difícil dizer se a multigráfica resultante será "esparsa", pois, no caso geral, a densidade das bordas das multigráficas pode ser muito maior do que a de um gráfico completo. Se considerarmos que o número de arestas de um gráfico completo$$$E$ determinado pelo número de seus vértices $$$V$de acordo com a fórmula:

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

E a densidade da aresta é definida como:

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

Para gráficos completos $$$max(D) = 1$, mas para multigráficas, o valor da densidade da aresta é geralmente ilimitado.

Portanto, cheguei à conclusão de que o caminho mais curto pode ser encontrado usando o algoritmo Dijkstra, e todos os outros caminhos mais curtos podem ser encontrados usando o algoritmo Yen. Dado que nesta fase operamos com arcos não ponderados e podemos descartar imediatamente caminhos, por exemplo, com quatro transferências, a busca por um caminho mais curto será garantida para ser executada em menos de$$$O(n^{2})$.



Considerando que este artigo não cobre os resultados imediatos da implementação, posso assumir antecipadamente que o algoritmo Dijkstra modificado em um modelo multigráfico não funcionará levando em consideração o intervalo de tempo ideal.

Portanto, passarei à solução imediata do primeiro subproblema, a saber, a solução da questão relacionada à otimização multicritério, que selecionei pelo método de otimização condicional. O método consiste no fato de que, apesar da inconsistência dos critérios, a prioridade mais alta sempre existe e todos os outros têm valores válidos. Como resultado, a otimização de toda a tarefa se resume à otimização na prioridade mais alta.

Uma característica da tarefa é o fato de o cálculo incluir não apenas voos diretos, o que sempre simplifica bastante a tarefa, mas, pelo contrário, conectar voos ou transferências. Portanto, o modelo de gráfico dependente do tempo é muito adequado para solucionar o problema, porque muitas vezes o número de transferências não forma mais do que 3-4 segmentos na rota. O gráfico dependente do tempo, em primeiro lugar, traz informações sobre a totalidade das rotas disponíveis na forma de voos com conexões entre aeroportos. Em seguida, é calculada uma estimativa dos horários de partida e chegada para o encaixe, levando em consideração o gráfico normal não ponderado. Tudo o que precisa ser feito nesta fase é encontrar todas as rotas válidas entre os aeroportos "A" e "B" com um número predeterminado de transferências, por exemplo, três.



Considerando que, nesta fase, o gráfico não está ponderado, é possível encontrar o caminho mais curto usando a pesquisa geral da primeira largura e todos os outros caminhos mais curtos usando o algoritmo Yen. Como a primeira pesquisa de largura é realizada em tempo linear, podemos dizer que o tempo de pesquisa para todos os caminhos, com as mesmas três transferências, será linear.

Ao avaliar o uso de algoritmos para encontrar rotas ideais e a disponibilidade de dados sobre a frequência das atualizações de cronograma, podemos dizer que a idéia de uma matriz pré-calculada com todos os caminhos "mais curtos" nas direções é justificada. Obviamente, no estágio inicial de criação da matriz, essa solução se tornará cálculos trabalhosos, mas, no futuro, permitirá encontrar quase instantaneamente os caminhos "mais curtos" e fazer ajustes na própria matriz.

No entanto, a questão permanece e quais rotas de rotas “mais curtas” com conexões e transferências são as mais “curtas”? Caso contrário, temos uma matriz de dados que não nos permitirá tomar uma decisão. Um conjunto de critérios costuma ser reduzido ao mais ótimo nesse caso, a saber:

• tempo mínimo de viagem;
• número mínimo de transferências.

Ambos os critérios podem ter intervalos personalizáveis ​​ou valores de tempo, portanto, resta apenas combinar as rotas e verificar "em tempo real" a conformidade com os valores permitidos:



dado que o número máximo de transferências varia entre 3-4, algumas combinações de voos serão imediatamente excluídas , levando-nos à solução do seguinte subproblema - identificar entre as rotas os critérios mais "ideais" para a variedade.

O sistema de critérios é o principal problema na formação da emissão de rotas, porque o conceito de "ótimo" dependerá das preferências de um passageiro em particular e, muitas vezes, somente após o recebimento de uma resposta à solicitação, é possível gerenciar as rotas recebidas definindo um conjunto diferente de filtros. E mesmo que você forneça rotas ordenadas de acordo com os caminhos "mais curtos", os resultados serão uma matriz de dados que não permitirá que o passageiro decida e levará a uma busca interminável de opções. Portanto, a formação de uma variedade de opções de rota que levem em consideração várias combinações de aplicação de filtro, coletivamente e individualmente, é um parâmetro extremamente importante que afeta toda a tarefa.

O que precisa ser considerado e como? Criar filtros de classificação é uma tarefa muito demorada, porque um conjunto de filtros, seu número e o grau de influência um sobre o outro podem alterar significativamente o resultado da pesquisa de caminhos ideais como resultado do refinamento dos algoritmos de pesquisa. Então em que consiste? Todos conhecemos os principais parâmetros de vôo - informações sobre companhias aéreas, datas com horários de partida / chegada, aeroportos de partida / chegada, compensações de fuso horário, conexões e transferências, mas geralmente esquecemos esses dados como o tempo necessário e suficiente para chegar ao aeroporto ou tempo de viagem entre aeroportos para fazer uma conexão no caso em que a partida subsequente é de outro ponto do local. E não devemos esquecer a categoria do nosso passageiro,bem como sua quantidade para a oferta subsequente não apenas da rota ideal no tempo, mas também no preço, dependendo da política tarifária.

Uma variedade de ofertas deve incutir um certo grau de confiança em todo viajante, por mais paradoxal que isso possa parecer. Confiança baseada em princípios matemáticos e consistindo no fornecimento de um conjunto mínimo de propostas com opções de rota que levam em conta as preferências e reduzem o risco de força maior. E, neste caso, força maior não é apenas a probabilidade de atraso no voo ou mudança de horário e aeroporto de partida / chegada, mas também indicadores como situações naturais, tecnológicas e epidemiológicas que implicam o cancelamento total ou parcial de voos.

A capacidade de gerenciar dados em nossas realidades envolve muitas perguntas de cada vez: tudo é levado em consideração, o que mais pode ser adicionado. E nesse desejo de construir uma rede de rotas de transporte, surge um paradoxo relacionado ao fato de que o algoritmo deve ser ótimo e simples ao mesmo tempo. Mas muitas vezes você tem que sacrificar alguma coisa, daqui em algum lugar a minimização dos critérios iniciais até a quantidade mínima me pareceu mais aceitável.

Se seguirmos o caminho da seleção de critérios e, em seguida, da omissão dos secundários, podemos distinguir opções que levem em conta não apenas o tempo de toda a viagem, custo e conforto, o número de transferências e sua duração, mas também, por exemplo, informações sobre congestionamento de aeroportos e dados sobre comunicação entre aeroportos. ao mudar um aeroporto para outro. Isso se justifica pelo fato de que, ao formar conexões, levando em consideração a presença de vários aeroportos em uma cidade que possuem comunicações diferentes com aeroportos externos, não apenas o tráfego aéreo, mas o tempo de movimento em que essa situação ocorre será calculado no cálculo de tempo e formação de rotas. E eles têm um lugar para estar ...

O sistema de tomada de decisão na escolha das rotas “ótimas” em situações em que temos um conjunto de critérios que afetam as preferências é exatamente esse obstáculo, sobre o qual eu não pensava nos estágios iniciais. Mesmo levando-os a uma certa sistematização, existem muitas diferenças em suas aplicações entre si, portanto as consideraremos separadamente.

Conforto

O significado do conceito de "conforto" é entendido por todos de maneira diferente, mas os seguintes níveis são aceitos pelas companhias aéreas:

• primeira série;
• Classe executiva;
• Classe econômica.

Na minha abordagem, admiti que o parâmetro “conforto” pode ser medido e assumir valores de 1 a 10, e formou a seguinte condição: quanto menor esse indicador para um voo específico, menos confortável ele será no sistema de classificação. Nesse caso, surge imediatamente um problema relacionado à não aditividade de tal quantidade, ou seja, a soma dos indicadores de conforto dos dois voos não refletirá seu conforto geral. Por exemplo, existem duas combinações de rotas:

• a primeira rota com dois segmentos, a primeira invasão com conforto 10, a segunda com conforto 1;
• o segundo percurso com dois segmentos, o primeiro ataque com conforto 6, o segundo com conforto 5.

Como resultado, a soma e o valor médio aritmético do parâmetro "comfort" de cada caminho serão os mesmos, mas eles não refletirão o verdadeiro estado das coisas. No entanto, dada a necessidade de considerar o conforto agregado das duas rotas, é mais aconselhável, nessa situação, usar seus valores médios juntamente com o desvio padrão, o que nos permitiria estimar a “propagação” dos níveis de conforto. Ou seja, na consideração inicial, prestamos atenção ao conforto médio e, em seguida, pela magnitude do desvio padrão, consideramos como esses confortos diferem muito um do outro. Assim, esse critério se divide em dois muito "próximos". Embora, por outro lado, mesmo sem um exame minucioso, fique claro que a suposição de um nível de conforto "mensurável" está muito longe da realidade,porque temos níveis de classe conhecidos. E, em segundo lugar, também é óbvio que o conforto de toda a viagem depende de algum tipo de dependência funcional de outros critérios, por exemplo, a duração do voo, o número de transferências com sua duração, a classificação da companhia aérea e sua frota aérea. Se faz sentido focar nesse critério é uma questão. Afinal, a abordagem é baseada em um sistema de contabilização da totalidade de maneiras “ótimas”. Portanto, no futuro, usaremos a representação de conforto na forma de dois indicadores: a média aritmética dos indicadores de conforto de voos e seu desvio padrão.O número de transferências com a sua duração, a classificação da companhia aérea e da sua frota aérea. Se faz sentido focar nesse critério é uma questão. Afinal, a abordagem é baseada em um sistema de contabilização da totalidade de maneiras “ótimas”. Portanto, no futuro, usaremos a representação de conforto na forma de dois indicadores: a média aritmética dos indicadores de conforto de voos e seu desvio padrão.O número de transferências com a sua duração, a classificação da companhia aérea e da sua frota aérea. Se faz sentido focar nesse critério é uma questão. Afinal, a abordagem é baseada em um sistema de contabilização da totalidade de maneiras “ótimas”. Portanto, no futuro, usaremos a representação de conforto na forma de dois indicadores: a média aritmética dos indicadores de conforto de voos e seu desvio padrão.

Duração das transferências

Existem dois tipos de coordenação de rotas:

• transferências (pré-acordadas entre companhias aéreas);
• encaixe.

Interessante nessa lista é o conceito de "conexão", que é o resultado de uma combinação de duas ou mais companhias aéreas na mesma rota com períodos acordados, com base no tempo mínimo de conexão necessário, mas nem sempre suficiente para transferir de um voo para outro. Portanto, para combinar vôos, nessa rota, é necessário calcular o tempo suficiente necessário para concluir a conexão.

Aqui temos uma dissonância, porque muitas vezes esses voos podem ser excluídos das opções da oferta, mas, devido à presença desse critério, há situações em que a conexão com uma espera temporária de mais de um dia é "ideal" para o passageiro. Portanto, faz sentido não descartar rotas com tempo de transplante muito longo, pois, embora raramente, elas ainda possam estar em demanda.

Aeroporto de

congestionamento O indicador de saturação dos aeroportos pode ser estimado no cálculo das rotas “ótimas” com uma avaliação do grau de enchimento sobre a venda de bilhetes para os voos, tendo em conta a participação de um aeroporto na rota. Obviamente, nesse pressuposto, o tempo mínimo de conexão terá alguma dependência funcional do congestionamento do aeroporto.

Número de transferências

O número de transplantes em si é uma quantidade contraditória. Afinal, geralmente dessa maneira você pode reduzir o custo de todo o percurso. Por outro lado, há uma categoria de passageiros para quem a presença de uma única alteração cria vários problemas. Não se esqueça das situações em que a rota de transferência é a mais "ideal", porque os bilhetes caros da classe executiva são deixados na rota desejada ou, digamos, há bilhetes com tarifa sem a possibilidade de troca / devolução, o que implica a probabilidade de recusa a opção proposta.

Mas no número de transferências, outro subcritério é estabelecido - essa é a probabilidade de mudar de um aeroporto para outro. Portanto, a formação de conexões costuma ser uma tarefa difícil, porque, no cálculo da rota, é necessário reservar um tempo para a movimentação entre aeroportos, o que implica a necessidade de solicitar passagens para o transporte dentro da cidade para a movimentação nos parágrafos.

Os critérios “tempo de viagem” e “custo” são quantidades absolutamente aditivas, portanto, dependem de indicadores diretos com um sistema de classificação. E tudo ficaria bem se não fosse a necessidade de incluir o tempo total da viagem com o cálculo do tempo de chegada ao aeroporto ou partida para o destino, bem como ao conectar a contabilidade pela necessidade de despesas adicionais para a movimentação entre aeroportos. Nesta fase, deixe-me negligenciar este esclarecimento.

A estrutura hierárquica do objetivo global

Suponha que a definição de “otimização” seja entendida como a melhor de sempre e para todos, e não apenas para passageiros, mas também para companhias aéreas, aeroportos e, possivelmente, outros provedores de serviços de viagem.

Nesse caso, dividir um alvo único e muito complexo em subobjetivos é a única saída. Esse colapso pode se parecer com o seguinte:



É bastante óbvio que, para satisfazer todas as áreas de interesse, será necessário alcançar objetivos menos "globais", mas, até certo ponto, conflitantes. Como conseguir isso? Talvez este seja um ótimo tópico para outro artigo. Mas, olhando para o futuro, podemos dizer que dividir um objetivo complexo em subobjetivos mais simples também está associado à otimização e à teoria dos grafos, a saber, a busca de estruturas hierárquicas ideais.

O sistema de tomada de decisão está intimamente ligado a métodos como os critérios de Laplace, Wald, Savage e Hurwitz, portanto, tendo uma série de rotas "mais curtas", não pude deixar de saber qual delas seria a mais "ideal" com base nelas.

Uma das abordagens mais universais para solucionar problemas de otimização multiuso é procurar soluções ideais de acordo com Pareto e Slater. Se avaliarmos o conjunto de rotas "mais curtas" de acordo com o critério de otimização de Slater, o caminho ideal será considerado o melhor para todos os critérios ao mesmo tempo. Um caminho é considerado Pareto ideal se todos os outros caminhos forem melhores que em um parâmetro, mas pior em outro, ou seja, não se pode melhorar um caminho por pelo menos um critério sem piorá-lo pelo resto.

Todas as soluções de otimização de Pareto e Slater podem ser facilmente demonstradas graficamente para o problema de minimização com dois critérios: O



conjunto de pontos com os parâmetros dos critérios ótimos de Pareto são indicados em verde e os ótimos do Slater são indicados em amarelo. O conjunto de pontos ótimos para Slater também contém o conjunto de pontos ótimos para Paretto. Dentro da estrutura do problema em consideração, todos esses pontos serão os fins dos vetores começando na origem do espaço sete-dimensional.

Concluindo, posso dizer que essa é apenas a ponta do iceberg, o que permite que você dê uma idéia inicial do que os mecanismos de pesquisa encontram ao formar rotas ideais.