1. Introdução
Plataformas de transporte de passageiros on-line, como Uber, DiDi e Yandex, surgiram recentemente, enquanto atingiram rapidamente tamanhos impressionantes e, apesar de sua pouca idade, modificaram e complementaram significativamente o sistema de transporte da cidade. As tecnologias e modelos teóricos usados por essas plataformas (ou desenvolvidas para elas) são atualmente uma área de pesquisa ativa para uma ampla gama de especialistas na comunidade científica: economistas, matemáticos, programadores e engenheiros.
Neste artigo, nós (como representantes da equipe de otimização do Uber Marketplace) apresentaremos brevemente as principais alavancas do gerenciamento da eficácia das plataformas online: algoritmos responsáveis por enviar decisões (correspondência), preços dinâmicos e também apresentaremos um dos novos conceitos - hora dinâmica de nomeação do carro (espera dinâmica). Com base na experiência prática real, mostraremos que todos os três algoritmos desempenham um papel importante na criação de um sistema com alto desempenho e baixos tempos de espera para pedidos de passageiros e motoristas.
A descrição apresentada dos algoritmos será de natureza exploratória e intencionalmente desprovida de profundidade e rigor técnico. Um leitor interessado é convidado a estudar o artigo original (
Preços dinâmicos e correspondência em plataformas de carona -
N. Korolko , D.Woodard, C.Yan, H.Zhu - 2019), publicado por pesquisadores do Uber Marketplace, com base nos quais esta breve revisão introdutória e criado.
2. Descrição dos principais algoritmos
Na última década, o setor de soluções de transporte vem crescendo rapidamente graças a novas idéias e tecnologias conceituais, como plataformas de transporte on-line de passageiros, o desenvolvimento de carros autônomos e elétricos. A sinergia dessas tecnologias, que muitas empresas e laboratórios estão trabalhando ao mesmo tempo, promete um enorme avanço na redução do custo unitário do transporte de passageiros, não menos que 10 vezes ao longo de duas décadas.
O crescimento mais explosivo dessa lista de tecnologias é atualmente demonstrado pelas plataformas de transporte on-line de passageiros. Por exemplo, o Uber gerou mais de 10 bilhões de viagens em mais de 80 países e 700 cidades ao redor do mundo durante seus 10 anos de existência [Figura 1]. O mercado global desse transporte on-line promete atingir um tamanho incrível de US $ 285 bilhões até 2030. Portanto, não surpreende que a eficácia de tais plataformas que controlam dinamicamente o mercado bilateral de passageiros e motoristas seja de grande importância prática.
Estudos empíricos mostram que algoritmos automatizados para processamento, roteamento, preços e pedidos de dados permitem que as plataformas online obtenham uma maior utilização do horário de trabalho dos motoristas e tempos de espera mais curtos para os passageiros do que um serviço de táxi clássico. Além disso, essas duas características principais do sistema (utilização do tempo do motorista e tempo de espera do passageiro) estão intimamente relacionadas à confiabilidade e à estabilidade do serviço: surtos locais súbitos de demanda (por exemplo, no final de um grande concerto ou na véspera de Ano Novo) podem piorar significativamente as duas métricas, utilizando assim as métricas. serviço pouco atraente para os dois lados do mercado. Isso se deve ao fato de que os condutores da linha na zona de alta demanda recebem rapidamente uma pequena parte do número total de pedidos, e os condutores de áreas remotas são atribuídos à parte restante dos pedidos. Isso aumenta o tempo de entrega do carro, que geralmente não é pago ao motorista (e, portanto, reduz seus ganhos por unidade de tempo) e, ao mesmo tempo, causa uma impressão negativa no passageiro. Assim, ambas as partes que usam a plataforma começam a usá-la menos. Por esse motivo, ambas as métricas começam a se deteriorar ainda mais, girando a espiral descendente do desempenho da plataforma na direção da eficiência zero. Na literatura inglesa, esse fenômeno negativo é chamado de Wild Goose Chase (WGC), cuja tradução literal é “a busca do ganso selvagem”.
Duas tecnologias-chave destinadas a aumentar a estabilidade e a produtividade da plataforma são os algoritmos de distribuição de pedidos e preços dinâmicos. A primeira tecnologia controla as decisões de despacho e os preços dinâmicos em tempo real equilibram a taxa extremamente volátil de oferta e demanda para o transporte de passageiros. O preço dinâmico é essencial para manter o desempenho do sistema, reduzir o tempo de espera de um carro e aumentar o número de motoristas durante períodos de alta demanda. Além disso, estudos empíricos e teóricos mostram que a precificação dinâmica pode reduzir a escala do efeito patologicamente perigoso do WGC.
2.1 Algoritmos para distribuição de ordens (correspondência)
O algoritmo de despacho mais simples para atribuir um driver ao pedido é o chamado protocolo de primeiro despacho. Apesar de sua simplicidade e bons indicadores de desempenho prático, é fácil mostrar que esse algoritmo é ineficaz em um grande número de situações que ocorrem com freqüência. Primeiro, ele seleciona um motorista apenas daquele subconjunto de motoristas que estão livres no momento do pedido, ignorando os motoristas que podem estar perto de concluir uma viagem nas imediações de um novo pedido [Figura 4]. Em segundo lugar, esse algoritmo simples leva em conta apenas as informações sobre o sistema em um determinado período de tempo, enquanto na maioria das vezes a plataforma pode receber informações suficientemente precisas sobre o que acontecerá com o fluxo de pedidos e a distribuição espacial dos drivers em um futuro próximo. Na literatura, uma classe de tarefas semelhantes que fornece receitas práticas de como essas informações podem ser usadas para melhorar a qualidade do algoritmo é chamada de "problema do servidor K".
Outra família popular de algoritmos de despacho baseia-se na idéia de combinar um grupo de ordens de viagem em um curto intervalo de tempo e resolver o problema de otimização agregada da atribuição em pares. Em outras palavras, em vez de atribuir um carro de forma instantânea e sequencial a cada pedido individual, o sistema coleta informações sobre os pedidos recebidos e distribui os pedidos acumulados entre os motoristas da linha com alguma frequência. Se alguns pedidos forem deixados sem um driver designado, eles permanecerão no sistema e participarão da tarefa de distribuição da próxima etapa. A função objetivo da tarefa de otimização a ser resolvida em cada etapa pode incluir uma ampla gama de métricas que caracterizam a qualidade dos compromissos de expedição gerados: tempo de espera do passageiro pelo carro, distância entre o pedido e o motorista designado, probabilidade de cancelamento do pedido pelo passageiro ou motorista, etc.
Na prática, os algoritmos de despacho parecem muito mais complicados, pois precisam levar em consideração um grande número de recursos de diferentes produtos que são apresentados simultaneamente na interface do aplicativo. Por exemplo, os carros registrados na plataforma podem ter diferentes classes de conforto e diferentes capacidades. Alguns produtos de plataformas online implicam o uso simultâneo de um carro por diferentes passageiros (UberPool, Lyft Line), se suas rotas estiverem bastante próximas. Além disso, as decisões de despacho geralmente precisam levar em conta as preferências dos motoristas nas áreas de serviço e as instruções dos pedidos recebidos por eles. Assim, a gama de problemas de otimização que surgem com o objetivo de aumentar a eficiência das decisões de despacho, que também precisam ser resolvidas em tempo real, é continuamente atualizada com novas formulações cada vez mais complexas.
2.2 Algoritmos de preços dinâmicos
Uma das principais dificuldades operacionais no gerenciamento da plataforma de transporte on-line de passageiros é o volume de demanda e oferta de serviços de táxi que mudam constantemente no espaço e no tempo. A figura abaixo [Figura 5] mostra a proporção entre o número de solicitações de viagens on-line dos passageiros e o número de horas que os motoristas passaram na linha em duas áreas de São Francisco: o centro financeiro e a área residencial para dormir nos arredores da cidade. Este gráfico ilustra bem a alta volatilidade e a falta de equilíbrio entre oferta e demanda (cuja proporção às vezes pode levar a valores extremamente altos), bem como a diversidade do comportamento desse equilíbrio, dependendo da localização geográfica.
Para controlar o equilíbrio de oferta e demanda no espaço e no tempo, as plataformas online usam algoritmos dinâmicos de precificação que aumentam a taxa básica em tempo real se o número de pedidos recebidos dos passageiros exceder significativamente o número de motoristas livres. Os benefícios da precificação dinâmica para manter o desempenho estável da plataforma são suportados por um grande número de modelos teóricos, experimentos e observações empíricas associadas a cargas recordes no sistema. Essas cargas podem ocorrer devido a um grande número de razões previsíveis e não muito: condições climáticas adversas, eventos públicos, sistema de transporte público com defeito, etc. No caso de operação incorreta do algoritmo de precificação, com um aumento acentuado no número de solicitações de passageiros (ou com uma diminuição acentuada no número de carros disponíveis), é possível observar uma proporção muito baixa de passageiros a quem o carro está atribuído como resultado e o tempo insatisfatoriamente alto de sua entrega. O papel principal dos preços dinâmicos para uma plataforma online é permitir que qualquer usuário, em qualquer lugar e a qualquer momento, chame um táxi. Mesmo que a tarifa proposta seja mais alta que o normal, será uma opção mais favorável do que informar ao usuário da plataforma (que pode precisar urgentemente de um carro) que não há máquinas disponíveis no momento.
Os métodos populares para modelagem de precificação dinâmica incluem modelos econômicos que descrevem um modelo de estado estacionário, modelos de programação dinâmica, análise de regressão e modelos de otimização que descrevem a otimização da rede. Estudos recentes de economistas (Castillo, 2017) mostraram que um aumento dinâmico de tarifas também permite que a plataforma evite cair na zona de efeito negativo do WGC, sobre o qual falamos acima.
Os preços dinâmicos têm falhas objetivas. Em primeiro lugar, o preço final da viagem, que os passageiros vêem ao pedir um táxi, pode variar significativamente devido à volatilidade da oferta e da demanda, aumentando assim a imprevisibilidade da tarifa na mesma rota. Por outro lado, os drivers de plataformas online geralmente têm acesso a informações no aplicativo sobre as áreas da cidade onde o fator de aumento está ativo. No entanto, devido à alta volatilidade desse coeficiente, quando o motorista passar para a zona de preços mais altos, a tarifa poderá retornar aos valores de linha de base. Além disso, um aumento automático de tarifas pelo algoritmo pode incentivar os motoristas a cooperar e criar artificialmente no mercado local uma situação de escassez de carros disponíveis para pedidos, ativando, assim, coeficientes crescentes para viagens. Obviamente, é fácil detectar um comportamento coordenado dos motoristas em plataformas que processam uma grande quantidade de dados sobre pedidos e realizam as ações de proteção necessárias, mas para os passageiros essa experiência de preços artificialmente altos pode ser insatisfatória.
2.3 Tempo de espera dinâmico do carro (espera dinâmica)
Para evitar problemas associados ao preço dinâmico, na prática, outros algoritmos são usados para equilibrar a oferta e a demanda, além de evitar colocar o sistema na zona do efeito WGC. Isso inclui a ideia de limitar a distância máxima entre o pedido e o motorista designado (Raio Máximo de Despacho), bem como a formação de uma fila de pedidos de viagem (enfileiramento) recebidos no sistema, substituindo a nomeação instantânea do motorista para cada pedido.
Um conceito mais recente, que visa substituir ou complementar um aumento dinâmico de preços, é o mecanismo para controlar dinamicamente o tempo de espera antes de atribuir um carro (espera dinâmica). Uma variante desse mecanismo é usada no produto Express Pool, lançado recentemente pela Uber em alguns grandes mercados. Esse tipo de transporte de passageiros é caracterizado pelas tarifas mais baixas possíveis e implica o uso simultâneo de um único carro por vários passageiros independentes para viajar ao longo do caminho.
A idéia geral do mecanismo de tempo de destino dinâmico é a seguinte. Para um passageiro que está solicitando uma viagem, o aplicativo não nomeia um motorista instantaneamente, mas oferece uma espera, mas não mais do que um certo período de tempo indicado (os limites superiores típicos são 2 ou 5 minutos). Além disso, a nomeação do motorista pode ocorrer a qualquer momento, conveniente para a plataforma: do instante ao limite superior especificado. Nesse caso, o tempo total de espera do passageiro para o carro consiste em duas partes (quase independentes): o tempo até a nomeação do motorista e o tempo desde a sua nomeação até a chegada ao local do pedido. A inconveniência de esperar um passageiro é compensada por uma tarifa mais baixa.
No lado da plataforma, um grau adicional de liberdade ao longo do tempo em que os drivers são atribuídos aos pedidos é usado da seguinte maneira. Como o produto envolve a combinação de pedidos e a nomeação de um carro para o transporte simultâneo de vários passageiros, o tempo adicional para coletar informações permite aumentar o número de opções combinatórias e, como resultado, gerar viagens mais eficientes. Nesse caso, a métrica de eficiência pode ser, por exemplo, a proximidade das rotas de passageiros que caem em um carro. Obviamente, assim que a plataforma encontra uma combinação de viagens suficientemente eficaz, ela imediatamente faz a nomeação necessária para o motorista e notifica todos os participantes. Se uma combinação bem-sucedida e conveniente não for encontrada, a plataforma enviará um motorista individual a cada um dos passageiros que fizeram o pedido.
O mecanismo descrito otimiza principalmente as decisões de despacho e o momento em que essas decisões são tomadas e pode ser usado simultaneamente com a otimização dinâmica de preços. O modelo teórico desenvolvido e analisado no original do artigo principal demonstra que a otimização simultânea de preços e prazos apresenta um grande número de vantagens: permite reduzir a volatilidade tarifária, reduzir os riscos do efeito WGC e também aumentar o número total de viagens geradas pela plataforma por unidade de tempo. Além disso, essas opções de transporte são mais econômicas tanto para os motoristas (que recebem simultaneamente vários passageiros pagando pela viagem) quanto para os passageiros (que recebem um desconto em troca da flexibilidade com o tempo de espera).
3. Conclusão
Neste artigo, descrevemos brevemente as principais tarefas de gerenciamento de otimização que resolvem plataformas de transporte de passageiros on-line para garantir uma operação estável e aumentar sua eficiência. Tais tarefas incluem a construção de algoritmos de despacho, algoritmos de precificação dinâmica e a determinação dinâmica de horários de nomeação de motoristas. O gerenciamento simultâneo dessas alavancas permite alcançar altas taxas de utilização do tempo dos motoristas, baixo tempo de espera para o carro e o número de viagens geradas pela plataforma por unidade de tempo. A classe dessas tarefas é constantemente atualizada com exemplos novos e cada vez mais realistas, abrindo amplos horizontes para a pesquisa teórica e prática.
Todas as referências às fontes citadas podem ser encontradas no artigo original (
Preços dinâmicos e correspondência nas plataformas de carona -
N. Korolko , D. Woodard, C. Yan, H. Zhu - 2019).