Centenas de milhares de rotas por segundo por núcleo. Experiência Yandex.Routing

Há algumas semanas, Danya Tararukhin contou a Habré como nosso serviço apareceu, o Yandex.Routing, e como ele ajuda as empresas na logística. Ao criar a plataforma, resolvemos vários problemas interessantes, um dos quais dedicado ao post de hoje. Eu quero falar sobre o planejamento de rotas e os recursos necessários para isso.

Encontrar a melhor rota entre vários pontos é um problema clássico de otimização discreta. Para resolvê-lo, você precisa conhecer as distâncias e os tempos de viagem entre todos os pontos. Ou seja, conhecer a matriz de distâncias e tempos. Dois anos atrás, um cálculo de matriz longa era um problema muito crítico para nós e bloqueou o desenvolvimento. A busca da solução ideal com a matriz conhecida levou 10 minutos, mas o cálculo de todas as células da matriz para grandes tarefas (para vários milhares de pedidos) levou horas.

Para resolver o problema com cinco mil pedidos, é necessário conhecer as distâncias e os tempos de viagem entre todos os pontos. Essas são duas matrizes de números com uma dimensão de 5000x5000. Planejamos rotas de correio para o dia inteiro e, de manhã, o correio chegará de um ponto a outro em uma vez e à noite - para outra. Portanto, você precisa calcular a matriz de tempos e distâncias para cada hora do dia. Nem todas as horas do dia são únicas, mas o tempo da cortiça (manhã e noite) precisa ser bem coberto. Portanto, chegamos a uma configuração com treze horas. No total, precisamos de dois cubos (tempos e distâncias) cada um, 13x5000x5000. São 325 milhões de rotas, calculadas de acordo com o gráfico real das estradas, nas quais 165 milhões de arestas. O cálculo de uma rota em um algoritmo bem otimizado da equipe Yandex.Maps leva cerca de 10 ms, para um total de 900 horas de cálculos.Mesmo quando paralelo a 900 CPUs, você precisa esperar 1 hora. Não foi possível iniciar esse serviço, precisávamos de um algoritmo mais adequado.

Para uma leitura mais aprofundada, é útil conhecer o algoritmo de Dijkstra para encontrar o caminho mais curto em um gráfico. Pode ser imaginada como uma “onda” que emana do ponto inicial da rota e percorre todo o gráfico até o ponto final. O tempo de execução do algoritmo é proporcional às bordas do gráfico, ou seja, a área coberta pela onda:



quase todo candidato a uma entrevista na entrevista adivinha a primeira etapa da otimização de uma tarefa: você pode iniciar a onda de dois lados e terminar a pesquisa quando as ondas se encontrarem. A área total de duas ondas de meio raio é menor que uma grande.



O gráfico real da estrada é bastante estruturado, e isso pode ser usado. Quando você está procurando a menor distância entre Moscou e São Petersburgo, na clássica Dijkstra, você será forçado a espalhar a onda em um círculo e percorrer todas as ruas e becos de Moscou, as cidades e vilas da região de Moscou, as ruas Tver e Novgorod. Essa é uma quantidade enorme de cálculos, mas você pode preparar antecipadamente e lembrar as rotas ideais entre as cidades (também conhecidas como atalhos) e não repeti-las em tempo de execução. Em seguida, para encontrar a rota entre dois pontos no Dijkstra hierárquico, é necessário calcular as distâncias mais curtas até o atalho desejado. Como os níveis de hierarquia podem não ser dois, mas 5-6, eles reduzem drasticamente o tempo de pesquisa.

A equipe do roteador de cartões implementou essas otimizações por algum tempo. Foram eles que possibilitaram atingir 10 ms para encontrar uma rota entre dois pontos. :) Então, por enquanto, não chegamos perto de resolver o nosso problema.

Como o modo de busca ponto a ponto já está extremamente otimizado, podemos otimizar o cálculo das séries na matriz. Uma linha é a distância de um ponto a todos os outros. Enquanto procuramos a distância até o ponto mais distante, calculamos simultaneamente as distâncias para as mais próximas. Portanto, calcular a série é equivalente a calcular a distância até o ponto mais distante.



Observamos o momento de calcular as séries usando esse algoritmo e lembramos que o cálculo seqüencial de 5000 rotas levaria cerca de 5000 * 10 ms = 50 s:


O gráfico mostra o tempo de cálculo de uma linha em uma matriz de distância de tamanho 1 * N para N diferente (de acordo com dados reais). Pode-se ver que o cálculo da linha de tamanho 1 * 5000 de interesse para nós se encaixa em 1,3 segundos. Uma linha de tendência foi adicionada ao gráfico, que mostra que o tempo de cálculo está crescendo um pouco mais lentamente que o linearmente em N, na ordem de N ** 0,74

Já não é ruim! Com esse algoritmo, podemos calcular nosso cubo em 13 * 5000 * 1,3 s = 84 500 s = quase 24 horas. É facilmente paralelo em linhas e, ao usar 50 CPUs, as distâncias são calculadas em meia hora. A ordem da complexidade do algoritmo de cálculo do cubo é O (N ** 1,74):


13 N*N 50 CPU ( 13*N/50). , 5000 , . 10 000, : .

Neste formulário, há dois anos e meio, lançamos a primeira versão da nossa API, que resolve o problema de logística. Os clientes costumam reclamar de um longo tempo de decisão e são fáceis de entender: você iniciou uma tarefa a ser resolvida, espera 1 hora, obtém uma solução e entende que esqueceu de fixar o horário do turno com o motorista, corrige-o e tudo começa novamente. Os motoristas começam a ficar nervosos, porque correm o risco de entrar na hora do rush da manhã ou até não têm tempo para entregar o pedido no prazo. Era necessário fazer alguma coisa. Não queríamos "jogar" o problema com o ferro: estávamos nos preparando para cargas pesadas, isso exigiria muito ferro e a compra de servidores não está acontecendo de uma só vez.

Um estudo de artigos acadêmicos mostrou que, ao que parece, existem algoritmos com complexidade linear para esta tarefa *! (No artigo de referência, há uma grande visão geral de todos os tipos de métodos modernos de aceleração de Dijkstra, inclusive para o caso da matriz.) O cálculo da matriz em tempo linear não se encaixava na minha cabeça. Um de nossos desenvolvedores se ofereceu para escrever um protótipo, e foi o que aconteceu: O


tempo para calcular uma matriz de tamanho N * N em uma CPU usando o algoritmo "matriz rápida". A complexidade é obtida na ordem de O (N ** 1,1). Ns altos são eliminados da linha de tendência, já que a geração da resposta e seu download pela rede já estão influenciando mais o tempo.

115 segundos por matriz de 5000 x 5000, usando um único núcleo e uma dependência quase linear de N. Ficção se tornou realidade! A idéia do algoritmo combina as duas idéias descritas acima: Dijkstra para pesquisa em série e hierárquica. Obviamente, começando a calcular a segunda linha, em algum momento iremos novamente contornar a mesma área do gráfico que acabamos de passar, calculando a linha anterior. Portanto, vamos memorizar as distâncias mais curtas para todos os destinos nos nós do gráfico hierárquico. Quando começamos a calcular a próxima série, então, tendo atingido esse nó, obteremos imediatamente quase todas as distâncias para outros pontos.



Um ano e meio atrás, isso nos permitiu economizar meia hora de tempo com eLogística e reduz significativamente a ingestão de ferro. Anteriormente, para uma solicitação grande, precisávamos de 50 núcleos por meia hora, mas agora - 13 núcleos por 2 minutos. Isso representa aproximadamente 200.000 rotas por segundo por núcleo. Esse raro caso em que o novo algoritmo não fecha apenas a classe de problemas, mas expande nossas idéias sobre o possível.

---

_{^{* Artigo "Planejamento de rotas em redes de transporte", consulte o parágrafo 2.7.2 "Caminhos mais curtos em lote"}}