Aplicações de pesquisa vetorial: otimizando rotas de transporte rodoviário de varejo

Vetores e pesquisa vetorial são componentes-chave de modelos de linguagem grandes (LLMs), mas são úteis em uma série de outros aplicativos em muitos casos de uso que você talvez não tenha considerado. Que tal a maneira mais eficiente de entregar produtos de varejo?

Em dois artigos anteriores desta série, contei a história de um hipotético empreiteiro que foi contratado para ajudar a implementar soluções de IA/ML em um grande varejista e, em seguida, explorei como esse especialista em sistemas distribuídos e IA usou a pesquisa vetorial para gerar resultados com o cliente. promoções na empresa. Agora, explicarei como esse empreiteiro usa a pesquisa vetorial para otimizar rotas de transporte rodoviário.

O problema

Enquanto analisávamos nossas opções para reduzir (e, por fim, desabilitar) o trabalho em lote de recomendação da primeira história desta série, fomos convidados para uma reunião com a equipe de Serviços de Transporte. Eles ouviram como ajudamos a equipe de Promoções e estavam se perguntando se poderíamos dar uma olhada em um problema deles.

A BigBoxCo transporta seus produtos de aeroportos e portos de embarque. Uma vez no centro de distribuição (CD), eles são etiquetados e separados em remessas menores para as lojas físicas individuais. Embora tenhamos semirreboques próprios para esta parte da jornada do produto, a frota não está organizada de forma eficiente.

Atualmente, os motoristas recebem uma lista de lojas no dispositivo digital do caminhão e o supervisor sugere uma rota. No entanto, os motoristas muitas vezes recusam a ordem das paradas nas lojas e muitas vezes ignoram as sugestões de rota dos seus supervisores. Isto, naturalmente, leva a variações nos tempos esperados de envio e reabastecimento, bem como no tempo total gasto.

Sabendo disso, a equipe do CD não consegue encher completamente cada contêiner do caminhão, pois precisa deixar espaço no caminhão para acesso aos paletes de produtos de cada loja. Idealmente, as paletes de produtos seriam encomendadas com a palete da primeira loja na posição mais acessível do reboque.

Melhorando a experiência

A equipe de Serviços de Transporte gostaria que examinássemos os dados disponíveis e identificássemos se existe uma maneira mais inteligente de abordar esse problema. Por exemplo, e se existisse uma forma de pré-determinar o melhor caminho possível a seguir, determinando a ordem em que o motorista deve visitar as lojas?

Isto é semelhante ao “problema do caixeiro viajante” (TSP), um problema hipotético em que um vendedor recebe uma lista de cidades para visitar e precisa descobrir a rota mais eficiente entre elas. Embora as implementações codificadas do TSP possam se tornar bastante complexas, poderemos usar um banco de dados vetorial como o do Apache Cassandra para capacidade de pesquisa vetorial para resolver isso.

A abordagem óbvia é traçar cada uma das coordenadas de geolocalização de cada cidade de destino. No entanto, as cidades estão espalhadas apenas por uma área metropolitana local, o que significa que os números inteiros de latitude e longitude seriam praticamente os mesmos. Isso não levará a muitas variações facilmente detectáveis, portanto, devemos reorientar esses dados considerando apenas os números à direita do ponto decimal do esquema Geo URI.

Por exemplo, a cidade de Rogersville (localização de uma de nossas lojas BigBoxCo) tem um Geo URI de 45.200,-93.567. Seremos capazes de detectar a variação deste e de outros vetores mais facilmente se olharmos para a direita de cada ponto decimal de nossas coordenadas, chegando às coordenadas ajustadas de 200,-567 (em vez de 45,200,-93,567).

Essa abordagem com as cidades metropolitanas locais com nossas lojas nos fornece os seguintes dados:

Implementação

Agora que temos dados, podemos criar uma tabela em nosso cluster Cassandra com um vetor bidimensional. Também precisaremos criar um índice secundário anexado SSTable (SASI) na coluna do vetor:

 CREATE TABLE bigbox.location_vectors ( location_id text PRIMARY KEY, location_name text, location_vector vector<float, 2>); CREATE CUSTOM INDEX ON bigbox.location_vectors (location_vector) USING 'StorageAttachedIndex';

Isso nos permitirá usar uma pesquisa vetorial para determinar a ordem de visita de cada cidade. É importante notar, entretanto, que as pesquisas vetoriais são baseadas em cálculos de distância baseados em cossenos, assumindo que os pontos estão em um plano plano. Como sabemos, a Terra não é um plano plano. O cálculo de distâncias sobre uma grande área geográfica deve ser feito usando outra abordagem como a fórmula de Haversine , que leva em consideração as características de uma esfera. Mas para nossos propósitos em uma pequena área metropolitana local, calcular um vizinho mais próximo (ANN) aproximado deve funcionar perfeitamente.

Agora vamos carregar nossos vetores de cidade na tabela e poderemos consultá-los:

 INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES ('B1643','Farley',[86, -263]); INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES (B9787,'Zarconia',[37, -359]); INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES (B2346,'Parktown',[-52, -348]); INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES ('B1643','Victoriaville',[94, -356]); INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES ('B6789','Rockton',[11, -456]); INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES ('B2345','Maplewood',[73, -456]); INSERT INTO bigbox.location_vectors (location_id, location_name, location_vector) VALUES ('B5243','Rogersville',[200, -567]);

Para iniciar uma rota, consideraremos primeiro o centro de distribuição do armazém em Farley, que armazenamos com um vetor de 86, -263. Podemos começar consultando a tabela ` location_vectors para obter as RNAs do vetor de Farley:

 SELECT location_id, location_name, location_vector, similarity_cosine(location_vector,[86, -263]) AS similarity FROM location_vectors ORDER BY location_vector ANN OF [86, -263] LIMIT 7;

Os resultados da consulta são assim:

 location_id | location_name | location_vector | similarity -------------+---------------+-----------------+------------ B1643 | Farley | [86, -263] | 1 B5243 | Rogersville | [200, -567] | 0.999867 B1566 | Victoriaville | [94, -356] | 0.999163 B2345 | Maplewood | [73, -456] | 0.993827 B9787 | Zarconia | [37, -359] | 0.988665 B6789 | Rockton | [11, -456] | 0.978847 B2346 | Parktown | [-52, -348] | 0.947053 (7 rows)

Observe que também incluímos os resultados da função ` similarity_cosine ', para que a similaridade dos resultados da RNA seja visível para nós. Como podemos ver, depois de desconsiderar Farley no topo (100% correspondente ao nosso ponto de partida), a cidade de Rogersville está voltando como o vizinho mais próximo aproximado.

A seguir, vamos construir um endpoint de microsserviço que essencialmente atravessa as cidades com base em um ponto de partida e a RNA superior retornada. Também precisará desconsiderar as cidades onde já esteve. Portanto, construímos um método para o qual podemos fazer POST, para que possamos fornecer o ID da cidade de partida, bem como a lista de cidades para a rota proposta no corpo da solicitação:

 curl -s -XPOST http://127.0.0.1:8080/transportsvc/citylist/B1643 \ -d'["Rockton","Parktown","Rogersville","Victoriaville","Maplewood","Za rconia"]' -H 'Content-Type: application/json'

Chamar este serviço com ` location_id ' “B1643” (Farley) retorna a seguinte saída:

 ["Rogersville","Victoriaville","Maplewood","Zarconia","Rockton","Parktown"]

Portanto, isso funciona muito bem no sentido de fornecer alguma orientação sistemática para nossas rotas de transporte rodoviário. No entanto, nosso terminal de serviço e (por proxy) nossa consulta ANN não entendem o sistema rodoviário que conecta cada uma dessas cidades. Por enquanto, estamos simplesmente assumindo que nossos caminhões podem viajar para cada cidade diretamente “em linha reta”.

Realisticamente, sabemos que este não é o caso. Na verdade, vejamos um mapa da nossa área metropolitana, com cada uma dessas cidades e rodovias de ligação marcadas (Figura 1).

Uma forma de aumentar a precisão aqui seria criar vetores para os segmentos das rodovias. Poderíamos criar uma tabela de rodovias e gerar vetores para cada uma por suas coordenadas inicial e final com base em como elas se cruzam entre si e com nossas cidades.

 CREATE TABLE highway_vectors ( highway_name TEXT PRIMARY KEY, highway_vector vector<float,4>); CREATE CUSTOM INDEX ON highway_vectors(highway_vector) USING 'StorageAttachedIndex';

Podemos então inserir vetores para cada rodovia. Também criaremos entradas para ambas as direções dos segmentos da rodovia para que nossa consulta RNA possa usar qualquer cidade como ponto inicial ou final. Por exemplo:

 INSERT INTO highway_vectors(highway_name,highway_vector) VALUES('610-E2',[94,-356,86,-263]); INSERT INTO highway_vectors(highway_name,highway_vector) VALUES('610-W2',[86,-263,94,-356]);

Partindo do resultado de nossa consulta original, podemos executar outra consulta para recuperar vetores de rodovia com uma RNA das coordenadas para o DC em Farley (86,-263) e nossa loja em Rogersville (200,-567):

 SELECT * FROM highway_vectors ORDER BY highway_vector ANN OF [86,-263,200,-567] LIMIT 4; highway_name | highway_vector --------------+----------------------- 610-W2 | [86, -263, 94, -356] 54NW | [73, -456, 200, -567] 610-W | [94, -356, 73, -456] 81-NW | [37, -359, 94, -356] (4 rows)

Olhando para o mapa mostrado na Figura 1, podemos ver que Farley e Rogersville estão conectadas pelas rodovias 610 e 54. Agora estamos no caminho certo!

Poderíamos construir outro terminal de serviço para construir uma rota rodoviária de uma cidade para outra com base nas coordenadas das cidades iniciais e finais. Para completar este serviço, gostaríamos que ele eliminasse quaisquer rodovias “órfãs” devolvidas (rodovias que não estão em nossa rota esperada) e incluísse quaisquer cidades com lojas nas quais possamos querer parar no caminho.

Se usarmos ` location_ids ' de Farley (B1643) e Rogersville (B5243), deveríamos obter uma saída semelhante a esta:

 curl -s -XGET http://127.0.0.1:8080/transportsvc/highways/from/B1643/to/B5243 \ -H 'Content-Type: application/json' {"highways":[ {"highway_name":"610-W2", "Highway_vector":{"values":[86.0,-263.0,94.0,-356.0]}}, {"highway_name":"54NW", "highway_vector":{"values":[73.0,-456.0,200.0,-567.0]}}, {"highway_name":"610-W", "highway_vector":{"values":[94.0,-356.0,73.0,-456.0]}}], "citiesOnRoute":["Maplewood","Victoriaville"]}

Conclusões e próximos passos

Estes novos serviços de transporte deverão ajudar significativamente os nossos motoristas e a gestão dos centros de distribuição. Agora eles devem estar obtendo resultados matematicamente significativos para determinação de rotas entre lojas.

Um bom benefício colateral é que a equipe do DC pode encher o caminhão com mais eficiência. Com acesso antecipado à rota, eles podem carregar paletes no caminhão em uma abordagem LIFO (primeiro a entrar, último a sair), usando mais espaço disponível.

Embora este seja um bom primeiro passo, poderemos fazer algumas melhorias futuras assim que esta iniciativa for considerada bem-sucedida. A assinatura de um serviço de trânsito ajudará no planejamento e aumento de rotas. Isto permitiria um recálculo da rota com base em eventos de tráfego local significativos em uma ou mais rodovias.

Poderíamos também usar a abordagem de n-vetores para posicionamento de coordenadas em vez de usar a latitude abreviada e as coordenadas longitudinais. A vantagem aqui é que nossas coordenadas já seriam convertidas em vetores, provavelmente levando a aproximações mais precisas do vizinho mais próximo.

Confira este repositório GitHub para obter o código dos endpoints de serviço de transporte de exemplo descritos acima e saiba mais sobre como o DataStax permite IA generativa com pesquisa vetorial .

Por Aaron Ploetz, DataStax