Aplicaciones de búsqueda de vectores: optimización de rutas de transporte minorista

Los vectores y la búsqueda de vectores son componentes clave de los modelos de lenguaje grandes (LLM), pero son útiles en muchas otras aplicaciones en muchos casos de uso que quizás no haya considerado. ¿Qué tal la forma más eficiente de entregar productos minoristas?

En dos artículos anteriores de esta serie, conté la historia de un contratista hipotético que fue contratado para ayudar a implementar soluciones de IA/ML en un gran minorista y luego exploré cómo este especialista en sistemas distribuidos e IA utilizó la búsqueda vectorial para generar resultados con el cliente. promociones en la empresa. Ahora, le explicaré cómo este contratista utiliza la búsqueda vectorial para optimizar las rutas de los camiones.

El problema

Mientras analizábamos nuestras opciones para reducir (y, en última instancia, deshabilitar) el trabajo por lotes de recomendaciones de la primera historia de esta serie, nos invitaron a una reunión con el equipo de Servicios de Transporte. Habían oído cómo ayudamos al equipo de Promociones y se preguntaban si podríamos analizar un problema suyo.

BigBoxCo transporta sus productos en camiones desde aeropuertos y puertos de envío. Una vez en el centro de distribución (DC), se etiquetan y separan en envíos más pequeños para las tiendas físicas individuales. Si bien tenemos nuestros propios semirremolques para esta parte del recorrido del producto, la flota no está organizada de manera eficiente.

Actualmente, los conductores reciben una lista de tiendas en el dispositivo digital del camión y el supervisor sugiere una ruta. Sin embargo, los conductores a menudo se resisten al orden de las paradas en las tiendas y a menudo ignoran las sugerencias de ruta de sus supervisores. Esto, por supuesto, genera variaciones en los tiempos esperados de envío y reabastecimiento, así como en el tiempo total empleado.

Sabiendo esto, el personal del DC no puede llenar completamente cada contenedor del camión, porque tiene que dejar espacio en el camión para acceder a las paletas de productos de cada tienda. Lo ideal sería pedir los pallets de productos con el pallet del primer almacén en la posición más accesible del remolque.

Mejorando la experiencia

Al equipo de Servicios de Transporte le gustaría que examináramos los datos disponibles y viéramos si hay una manera más inteligente de abordar este problema. Por ejemplo, ¿qué pasaría si pudiéramos predeterminar la mejor ruta posible determinando el orden en que el conductor debe visitar las tiendas?

Esto es similar al “problema del vendedor ambulante” (TSP), un problema hipotético en el que a un vendedor se le da una lista de ciudades para visitar y necesita encontrar la ruta más eficiente entre ellas. Si bien las implementaciones codificadas del TSP pueden volverse bastante complejas, es posible que podamos utilizar una base de datos vectorial como la de Apache Cassandra para la capacidad de búsqueda vectorial para resolver este problema.

El enfoque obvio es trazar cada una de las coordenadas de geolocalización de cada ciudad de destino. Sin embargo, las ciudades solo están distribuidas en un área metropolitana local, lo que significa que los números enteros de latitud y longitud serían prácticamente iguales. Eso no dará lugar a una gran variación fácilmente detectable, por lo que debemos reenfocar esos datos simplemente considerando los números a la derecha del punto decimal del esquema Geo URI.

Por ejemplo, la ciudad de Rogersville (la ubicación de una de nuestras tiendas BigBoxCo) tiene un Geo URI de 45.200,-93.567. Podremos detectar la variación de este y otros vectores más fácilmente si miramos a la derecha de cada punto decimal de nuestras coordenadas, llegando a las coordenadas ajustadas de 200,-567 (en lugar de 45,200,-93,567).

Tomar este enfoque con las ciudades metropolitanas locales con nuestras tiendas nos da los siguientes datos:

Implementación

Ahora que tenemos datos, podemos crear una tabla en nuestro clúster de Cassandra con un vector bidimensional. También necesitaremos crear un índice secundario adjunto SSTable (SASI) en la columna del vector:

 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';

Esto nos permitirá utilizar una búsqueda vectorial para determinar el orden en el que visitar cada ciudad. Es importante tener en cuenta, sin embargo, que las búsquedas vectoriales se basan en cálculos de distancia basados en cosenos, suponiendo que los puntos están en un plano. Como sabemos, la Tierra no es un plano. El cálculo de distancias en un área geográfica grande debe realizarse utilizando otro enfoque como la fórmula de Haversine , que tiene en cuenta las características de una esfera. Pero para nuestros propósitos en un área metropolitana local pequeña, calcular un vecino más cercano aproximado (ANN) debería funcionar bien.

Ahora carguemos los vectores de nuestra ciudad en la tabla y deberíamos poder consultarla:

 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 comenzar una ruta, consideraremos primero el centro de distribución del almacén en Farley, que hemos almacenado con un vector de 86, -263. Podemos comenzar consultando la tabla ` location_vectors para las ANN del vector 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;

Los resultados de la consulta se ven así:

 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)

Tenga en cuenta que también hemos incluido los resultados de la función ` similarity_cosine ', de modo que la similitud de los resultados de ANN sea visible para nosotros. Como podemos ver, después de ignorar a Farley en la parte superior (100% de coincidencia con nuestro punto de partida), la ciudad de Rogersville regresa como el vecino más cercano aproximado.

A continuación, creemos un punto final de microservicio que esencialmente atraviese las ciudades según un punto de partida y la ANN superior devuelta. También deberá ignorar las ciudades en las que ya ha estado. Por lo tanto, creamos un método en el que podemos PUBLICAR, de modo que podamos proporcionar el ID de la ciudad de inicio, así como la lista de ciudades para la ruta propuesta en el cuerpo de la solicitud:

 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'

Llamar a este servicio con ` location_id ' “B1643” (Farley) devuelve el siguiente resultado:

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

Esto funciona muy bien en el sentido de que proporciona una guía sistemática para nuestras rutas de camiones. Sin embargo, nuestro punto final de servicio y (por proxy) nuestra consulta de ANN no comprenden el sistema de carreteras que conecta cada una de estas ciudades. Por ahora, es simplemente asumir que nuestros camiones pueden viajar a cada ciudad directamente "en línea recta".

Siendo realistas, sabemos que este no es el caso. De hecho, veamos un mapa de nuestra área metropolitana, con cada una de estas ciudades y carreteras de conexión marcadas (Figura 1).

Una forma de aumentar la precisión aquí sería crear vectores para los segmentos de las carreteras. Podríamos crear una tabla de carreteras y generar vectores para cada una según sus coordenadas iniciales y finales en función de cómo se cruzan entre sí y con nuestras ciudades.

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

Luego podemos insertar vectores para cada carretera. También crearemos entradas para ambas direcciones de los segmentos de la carretera para que nuestra consulta ANN pueda utilizar cualquiera de las ciudades como punto inicial o final. Por ejemplo:

 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]);

Partiendo del resultado de nuestra consulta original, podemos ejecutar otra consulta para recuperar los vectores de la autopista con una ANN de las coordenadas del DC en Farley (86,-263) y nuestra tienda en 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)

Al observar el mapa que se muestra en la Figura 1, podemos ver que Farley y Rogersville están conectados por las autopistas 610 y 54. ¡Ahora estamos en algo!

Podríamos construir otro punto final de servicio para construir una ruta de autopista de una ciudad a otra en función de las coordenadas de las ciudades inicial y final. Para que este servicio sea completo, queremos que elimine cualquier carretera "huérfana" devuelta (carreteras que no están en nuestra ruta esperada) e incluya cualquier ciudad con tiendas en las que queramos detenernos en el camino.

Si usamos ` location_ids ' de Farley (B1643) y Rogersville (B5243), deberíamos obtener un resultado similar a este:

 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"]}

Conclusiones y próximos pasos

Estos nuevos servicios de transporte deberían ayudar significativamente a nuestros conductores y a la administración del DC. Ahora deberían obtener resultados matemáticamente significativos para la determinación de rutas entre tiendas.

Un buen beneficio adicional es que el personal de DC puede llenar el camión de manera más eficiente. Al tener acceso a la ruta con anticipación, pueden cargar paletas en el camión con un enfoque de primero en entrar, último en salir (LIFO), utilizando más espacio disponible.

Si bien este es un buen primer paso, podríamos realizar algunas mejoras futuras una vez que esta iniciativa se considere exitosa. Una suscripción a un servicio de tráfico ayudará a planificar y aumentar las rutas. Esto permitiría volver a calcular la ruta en función de eventos de tráfico locales importantes en una o más carreteras.

También podríamos usar el enfoque de n-vectores para el posicionamiento de coordenadas en lugar de usar las coordenadas abreviadas de latitud y longitud. La ventaja aquí es que nuestras coordenadas ya estarían convertidas en vectores, lo que probablemente conduciría a aproximaciones más precisas del vecino más cercano.

Consulte este repositorio de GitHub para obtener el código de los puntos finales de servicio de transporte de ejemplo descritos anteriormente y obtenga más información sobre cómo DataStax permite la IA generativa con búsqueda vectorial .

Por Aaron Ploetz, DataStax