Instacart: rota do shopper

01 · CONTEXTO

Entregar mercado no prazo

O Instacart entrega compras de supermercado e assume o desafio de concluir cada entrega no prazo e com os produtos certos.

Ao longo de poucas horas há milhares de pedidos a entregar, e fazer isso com eficiência é o trabalho dos sistemas de logística. Este caso se baseia em um post de 2017 escrito por um ex-VP de Data Science da empresa, que descreve um problema clássico de otimização combinado com aprendizado de máquina.

02 · O PROBLEMA

De TSP a SCVRPTWMT

A formulação mais simples é um problema do caixeiro viajante em que o shopper precisa ir primeiro à loja. Com uma frota, cada shopper recebe um lote de pedidos para comprar e depois entregar em sequência, e o problema vira um VRP, que generaliza o TSP.

Existem algoritmos exatos para TSP até dezenas de milhares de entregas, e mesmo com milhões de entregas heurísticas ficam a 2–3% do ótimo.

A soma de todas as restrições é descrita no post como um SCVRPTWMT.

03 · DO GULOSO AO NOVO

O motor de fulfillment

O ponto de partida foi uma variação de um algoritmo guloso: ordenar os pedidos por prazo, achar o shopper livre que faz o primeiro pedido mais rápido, procurar pedidos que cabem sem atraso e despachar.

Desde então a empresa introduziu abordagens novas, com grande impacto na velocidade. No post, os minutos por entrega em São Francisco foram reduzidos pela metade, sem comprometer entregas atrasadas nem a qualidade dos pedidos.

1. Uma das mudanças é decompor o problema em subproblemas, e um deles é agrupar as entregas.

2. Um modelo de aprendizado de máquina prevê a distribuição de tempo esperada para cada combinação de shopper e atribuição.

3. Outro subproblema é a atribuição de shoppers; os subproblemas são resolvidos quase até o ótimo.

4. Heurísticas limitam o espaço de busca, tratam anomalias, refinam as soluções e ajudam a se adaptar à incerteza.

5. O plano de lotes é recalculado a cada minuto e a decisão de despacho é tomada na hora certa.

04 · O SISTEMA AO REDOR

O motor é só uma peça

A aplicação que decide quais pedidos cada shopper atende é o motor de fulfillment, mas ele é apenas um componente do sistema de logística, que também prevê demanda e comportamento, gerencia capacidade e preço de pico e planeja a escala.

1. O motor de fulfillment é apenas um dos componentes do sistema de logística.

2. Outro componente prevê a demanda e o comportamento dos shoppers.

3. Outro gerencia a capacidade e o preço de pico.

4. Outro planeja e adapta a escala dos shoppers.

5. Os sistemas são altamente interdependentes, e a empresa usa cada vez mais simulações para otimizá-los em conjunto.

05 · DADOS DE GPS

Enxergar o sistema com dados de localização

Para otimizar a atribuição e a rota dos shoppers, e para se comunicar com os consumidores, o Instacart coleta um fluxo de dados de GPS. A cada 10 segundos, aproximadamente, o dispositivo informa carimbo de tempo, latitude e longitude, velocidade, direção e precisão, e o conjunto soma dezenas de milhões de atualizações por dia no país.

1. O dispositivo do shopper reporta periodicamente carimbo de tempo, posição, velocidade, direção e precisão.

2. A plataforma coleta esse fluxo de dados de localização.

3. A localização serve para otimizar a atribuição e o roteamento dos shoppers.

4. Os dados também servem para se comunicar bem com os consumidores.

5. O datashader transforma milhões de pontos em visualizações que geram hipóteses e confirmam mudanças em produção.

Em resumo, o caso combina otimização com restrições reais, aprendizado de máquina para estimar tempos e dados de campo para analisar o sistema.