Uma das principais tarefas da Yandex.Taxi é como garantir que um carro chegue rapidamente ao usuário e o tempo do motorista para "marcha lenta" seja reduzido (ou seja, o tempo em que ele está na linha sem um passageiro). Parece que tudo é simples: o usuário seleciona a tarifa, indica desejos adicionais (cadeira de criança, por exemplo). Resta filtrar os motoristas na linha de acordo com esses critérios, selecionar o mais próximo e oferecer-lhe um pedido. No entanto, tudo é tão simples apenas à primeira vista.
Hoje direi à comunidade Habr como escolhemos o driver mais adequado e como esse processo evoluiu ao longo do tempo. Você aprenderá sobre duas abordagens para resolver o problema.
Arquitetura de pesquisa geral
Quando o usuário clica no botão "Chamar um táxi", um objeto de pedido é criado no back-end e seu processamento começa de acordo com a máquina de estado. Para que o pedido passe do estado "Pendente" para "O motorista está atribuído", você precisa encontrar o motorista, oferecer um pedido e aguardar a confirmação de que o pedido foi aceito.
Abordagem gananciosa
Durante muito tempo, uma abordagem
gananciosa trabalhou na Yandex.Taxi. Com essa abordagem, na fase de busca pelo contratado, é feita uma solicitação ao microsserviço Tracker, responsável pelos motoristas. O Tracker sabe tudo sobre carros: da cor e da marca à sua
localização atual . O Tracker possui um índice geográfico local para drivers e conectores para serviços de roteamento (roteadores) para a construção de rotas do ponto A ao ponto B (e mesmo através dos pontos B, D, D). Portanto, quando uma solicitação é feita para procurar um motorista, o Tracker determina primeiro os carros mais próximos no índice geográfico local ao longo do raio direto, levando em consideração as restrições de ordem "rígida" (classe de carro, requisitos - cadeira de criança, números amarelos). Em seguida, são especificados o tempo e a duração da rota de fornecimento do veículo e, levando em consideração essas informações, a melhor opção é selecionada.
Mais tarde, essa lógica evoluiu: para cada motorista, eles começaram a contar com sua "pontuação" em ordem - uma função do horário em que o carro foi entregue. E os pilotos já foram classificados pelo valor da pontuação. A função leva em consideração não apenas o tempo de entrega em si, mas também muitos outros fatores: do nível de demanda nos pontos A e B à "experiência" do motorista. Esse compromisso ganancioso é chamado de bônus.
Abordagem de buffer (feixe)
No entanto, com uma abordagem gananciosa, o motorista mais próximo receberá aquele que primeiro pediu um táxi. No entanto, alguns usuários podem até ficar sem carro.
Com o aumento da demanda, quando a competição por artistas começa, a abordagem gananciosa não é boa. Para satisfazer a demanda o máximo possível, mesmo nas horas mais ocupadas, usamos muitas abordagens e algoritmos. Um deles é a designação de buffer (feixe) de drivers em pedidos. Baseia-se na tarefa bem conhecida do campo da otimização combinatória -
o problema de atribuição . Em resumo, sua essência: vamos ter N obras e M artistas, qualquer funcionário pode concluir qualquer tarefa durante o tempo p (i, j) [0 <= i <N, 0 <= j <M]. É necessário atribuir um contratado a cada tarefa para reduzir o tempo total de execução de todo o trabalho (nesse caso, um contratado pode ocupar apenas um trabalho).
Ao resolver esse problema de atribuição, nosso "custo" de executar o trabalho (ordem) pelo executor (frota de táxi e motorista) é o valor da função de pontuação desde o momento em que o carro foi entregue ao usuário. A tarefa pode ser descrita em termos de gráficos bipartidos: por um lado, ordens, por outro, artistas. Entre pedidos e artistas, existem arestas ponderadas (pontuação). Assim, um dos nossos objetivos é minimizar o tempo total de entrega do veículo, maximizando o número de pedidos concluídos (correspondência máxima). Uma das maneiras mais famosas de resolver esse problema é o
algoritmo húngaro .
Obviamente, com um compromisso no buffer, não podemos fornecer um driver mediante solicitação, como em uma abordagem gananciosa. Primeiro, você precisa colocar o pedido na fila, depois reproduzir e depois informar sobre o driver encontrado. Isso não se encaixava na máquina de estado do processamento de pedidos e precisava ser melhorado um pouco. Para testar e criar uma nova solução sem afetar nossos colegas, concordamos imediatamente que faríamos tudo em um microsserviço DriverDispatcher separado. Ele recebe pedidos, faz fila, encontra motoristas e salva os resultados dos comícios.
Primeiro, tivemos que preparar o Tracker para um novo perfil de carga. Se, com uma abordagem gananciosa, as solicitações de drivers simplesmente caíssem individualmente no balanceador do Tracker e fossem redirecionadas para suas instâncias com balanceamento de carga, no destino do buffer todas as solicitações seriam de uma máquina: solicitações individuais simplesmente entupiriam o conjunto de conexões. Portanto, adicionamos ao rastreador a capacidade de processar lotes de solicitações que foram processadas simultaneamente dentro do rastreador. Ao longo do caminho, também tivemos que resolver o problema de um número razoável de solicitações para processamento em lote. No lado do cliente (DriverDispatcher), dividimos o grande lote em vários pequenos e o enviamos para diferentes instâncias do Tracker.
Assim, o rastreador está preparado, a pontuação é considerada no Tracker (compromisso ganancioso) e no novo serviço (DriverDispatcher'e), o algoritmo para resolver o problema de atribuição é depurado e funciona corretamente. Surgiu a questão de como integrar tudo isso à máquina estatal de processamento de pedidos. Adicionamos o envio e a exclusão de meta-informações de pedidos no DriverDispatcher quando o pedido é transferido de um estado para outro. E isso quase funcionou. Quase - porque as iterações de procura de um contratado para encomendar não foram controladas externamente. Poderíamos simplesmente substituir a viagem ao rastreador pelo motorista por uma viagem ao nosso serviço e fornecer ao motorista quando ele for encontrado, e antes fornecer apenas 404. Mas isso é ruim, porque você precisa oferecer um pedido ao motorista assim que encontrarmos um pedido, e até vários segundos de atraso desempenham um papel aqui: o motorista pode simplesmente virar na direção errada, e a ordem se tornará irrelevante. Para isso, foi possível acessar o processo de pesquisa de um artista sem afetar as tarefas planejadas. Então, salvamos a lógica de pesquisa (com solicitações novamente) e adicionamos a capacidade de chamá-la fora do agendador.
Assim, conseguimos combinar a máquina de estado principal de processamento de pedidos com a máquina de estado de processamento no envio de buffer sem afetar a lógica de trabalho e sem correr entre estados. Você pode executar as primeiras experiências em usuários ativos.
Tudo isso é muito legal, mas e quanto à hora de procurar um artista, você pergunta. Se a pesquisa não ocorrer imediatamente após o recebimento do pedido, o tempo de pesquisa aumenta e, como resultado, é compensado por um feed mais rápido? Isso não é inteiramente verdade: com a ajuda de várias técnicas (incluindo o aprendizado de máquina), conseguimos isolar os casos quando a espera faz sentido; em outros casos, o tempo de espera não muda.
Pin draw
Outra maneira de encontrar um artista mais rapidamente é começar a procurá-lo antes de criar um pedido. Quando um novo
pino aparece (ou seja, o usuário insere apenas os dados do pedido no aplicativo), os
algoritmos de aprendizado de máquina avaliam a probabilidade de um pedido seguir e decidem se devem ser levados em consideração ao armazenar em buffer os drivers. Podemos encontrar o carro com antecedência e, quando o usuário clicar no botão de pedido, faça imediatamente uma oferta a um motorista adequado.
Conclusão
A correspondência de pedidos e drivers não é uma tarefa fácil, pois é necessário levar em consideração muitos fatores. Um deles é o contexto dos movimentos dos motoristas na escolha dos candidatos à ordem. Falaremos sobre isso nos próximos posts.
Outras publicações sobre tecnologia de táxi