Applications de recherche de vecteurs : optimisation des itinéraires de camionnage pour le commerce de détail

Les vecteurs et la recherche de vecteurs sont des composants clés des grands modèles de langage (LLM), mais ils sont utiles dans une multitude d'autres applications dans de nombreux cas d'utilisation que vous n'avez peut-être pas envisagés. Que diriez-vous du moyen le plus efficace de livrer des marchandises au détail ?

Dans deux articles précédents de cette série, j'ai raconté l'histoire d'un entrepreneur hypothétique qui a été embauché pour aider à mettre en œuvre des solutions d'IA/ML chez un détaillant à grande surface, puis j'ai exploré comment ce spécialiste des systèmes distribués et de l'IA a utilisé la recherche vectorielle pour générer des résultats avec les clients. promotions dans l'entreprise. Je vais maintenant vous expliquer comment cet entrepreneur utilise la recherche vectorielle pour optimiser les itinéraires de camionnage.

Le problème

Pendant que nous examinions nos options pour réduire (et finalement désactiver) le travail par lots de recommandations du premier article de cette série, nous avons été invités à une réunion avec l'équipe des services de transport. Ils avaient entendu comment nous avions aidé l'équipe de promotion et se demandaient si nous pouvions examiner un de leurs problèmes.

BigBoxCo fait transporter ses produits par camion depuis les aéroports et les ports d'expédition. Une fois arrivés au centre de distribution (DC), ils sont étiquetés et séparés en expéditions plus petites pour les magasins physiques individuels. Bien que nous disposions de nos propres semi-remorques pour cette partie du parcours du produit, la flotte n'est pas organisée efficacement.

Actuellement, les chauffeurs reçoivent une liste de magasins sur l'appareil numérique du camion et le superviseur suggère un itinéraire. Cependant, les chauffeurs hésitent souvent à respecter l'ordre des arrêts dans les magasins et ignorent souvent les suggestions d'itinéraire de leurs superviseurs. Bien entendu, cela entraîne des variations dans les délais d’expédition et de réapprovisionnement prévus, ainsi que dans le temps total nécessaire.

Sachant cela, le personnel de DC n'est pas en mesure de remplir complètement chaque conteneur du camion, car il doit laisser de l'espace dans le camion pour accéder aux palettes de produits de chaque magasin. Idéalement, les palettes de produits seraient commandées avec la palette du premier magasin dans la position la plus accessible dans la remorque.

Améliorer l'expérience

L'équipe des services de transport aimerait que nous examinions les données disponibles et voyons s'il existe une façon plus intelligente d'aborder ce problème. Par exemple, et s’il existait un moyen de prédéterminer le meilleur itinéraire possible à emprunter en déterminant l’ordre dans lequel le conducteur doit visiter les magasins ?

Ceci est similaire au « problème du voyageur de commerce » (TSP), un problème hypothétique dans lequel un vendeur reçoit une liste de villes à visiter et doit trouver l'itinéraire le plus efficace entre elles. Bien que les implémentations codées du TSP puissent devenir assez complexes, nous pourrions être en mesure d'utiliser une base de données vectorielles comme celle d'Apache Cassandra pour la capacité de recherche vectorielle afin de résoudre ce problème.

L’approche évidente consiste à tracer chacune des coordonnées de géolocalisation de chaque ville de destination. Cependant, les villes ne sont réparties que sur une zone métropolitaine locale, ce qui signifie que les nombres entiers de latitude et de longitude seraient pour l’essentiel les mêmes. Cela n'entraînera pas beaucoup de variance facilement détectable, nous devrions donc recentrer ces données en considérant simplement les nombres à droite du point décimal du schéma Geo URI.

Par exemple, la ville de Rogersville (l'emplacement de l'un de nos magasins BigBoxCo) a un URI géographique de 45.200,-93.567. Nous serons en mesure de détecter plus facilement la variance par rapport à ce vecteur et à d'autres vecteurs si nous regardons à droite de chaque point décimal de nos coordonnées, pour arriver à des coordonnées ajustées de 200,-567 (au lieu de 45,200,-93,567).

Adopter cette approche avec les villes métropolitaines locales avec nos magasins nous donne les données suivantes :

Mise en œuvre

Maintenant que nous avons des données, nous pouvons créer une table dans notre cluster Cassandra avec un vecteur bidimensionnel. Nous devrons également créer un index secondaire attaché SSTable (SASI) sur la colonne 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';

Cela nous permettra d'utiliser une recherche vectorielle pour déterminer l'ordre dans lequel visiter chaque ville. Il est important de noter, cependant, que les recherches vectorielles sont basées sur des calculs de distance basés sur le cosinus, en supposant que les points se trouvent sur un plan plat. Comme nous le savons, la Terre n’est pas un plan plat. Le calcul des distances sur une vaste zone géographique doit être effectué en utilisant une autre approche comme la formule de Haversine , qui prend en compte les caractéristiques d'une sphère. Mais pour nos besoins dans une petite zone métropolitaine locale, le calcul du voisin le plus proche (ANN) devrait très bien fonctionner.

Chargeons maintenant nos vecteurs de ville dans la table, et nous devrions pouvoir l'interroger :

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

Pour commencer un itinéraire, nous considérerons d'abord le centre de distribution de l'entrepôt de Farley, que nous avons stocké avec un vecteur de 86, -263. Nous pouvons commencer par interroger la table ` location_vectors ` pour les ANN du vecteur 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;

Les résultats de la requête ressemblent à ceci :

 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)

Notez que nous avons également inclus les résultats de la fonction ` similarity_cosine ', afin que la similarité des résultats ANN nous soit visible. Comme nous pouvons le constater, après avoir ignoré Farley en haut (correspondance à 100 % à notre point de départ), la ville de Rogersville revient comme la voisine la plus proche.

Ensuite, construisons un point de terminaison de microservice qui traverse essentiellement les villes en fonction d'un point de départ et de l'ANN supérieur renvoyé. Il devra également ignorer les villes où il est déjà allé. Par conséquent, nous construisons une méthode sur laquelle nous pouvons POST, afin de pouvoir fournir l'ID de la ville de départ, ainsi que la liste des villes pour l'itinéraire proposé dans le corps de la requête :

 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'

L'appel de ce service avec le « location_id » « B1643 » (Farley) renvoie le résultat suivant :

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

Cela fonctionne donc très bien dans le sens où cela fournit des conseils systématiques pour nos itinéraires de camionnage. Cependant, notre point de terminaison de service et (par proxy) notre requête ANN n'ont pas une compréhension du système routier qui relie chacune de ces villes. Pour l’instant, nous supposons simplement que nos camions peuvent se rendre directement dans chaque ville « à vol d’oiseau ».

En réalité, nous savons que ce n’est pas le cas. En fait, regardons une carte de notre région métropolitaine, avec chacune de ces villes et autoroutes de connexion marquées (Figure 1).

Une façon d’augmenter la précision ici serait de créer des vecteurs pour les segments d’autoroutes. Nous pourrions créer une table d'autoroutes et générer des vecteurs pour chacun d'eux en fonction de leurs coordonnées de début et de fin en fonction de la manière dont ils se croisent et se croisent avec nos villes.

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

Nous pouvons ensuite insérer des vecteurs pour chaque autoroute. Nous créerons également des entrées pour les deux directions des segments d'autoroute afin que notre requête ANN puisse utiliser l'une ou l'autre ville comme point de départ ou d'arrivée. Par exemple:

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

En partant du résultat de notre requête d'origine, nous pouvons exécuter une autre requête pour extraire les vecteurs d'autoroute avec un ANN des coordonnées du DC de Farley (86,-263) et de notre magasin à 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)

En regardant la carte présentée à la figure 1, nous pouvons voir que Farley et Rogersville sont reliées par les autoroutes 610 et 54. Nous voilà maintenant sur quelque chose !

Nous pourrions construire un autre point de terminaison de service pour construire un itinéraire autoroutier d'une ville à une autre en fonction des coordonnées des villes de départ et d'arrivée. Pour rendre ce service complet, nous souhaiterions qu'il élimine toutes les autoroutes « orphelines » renvoyées (les autoroutes qui ne se trouvent pas sur notre itinéraire prévu) et qu'il inclue toutes les villes avec des magasins dans lesquels nous pourrions vouloir nous arrêter en cours de route.

Si nous utilisons les ` location_ids ' de Farley (B1643) et Rogersville (B5243), nous devrions obtenir un résultat qui ressemble à ceci :

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

Conclusions et prochaines étapes

Ces nouveaux services de transport devraient aider considérablement nos chauffeurs et la direction de DC. Ils devraient désormais obtenir des résultats mathématiquement significatifs pour la détermination des itinéraires entre les magasins.

Un avantage secondaire intéressant est que le personnel de DC peut remplir le camion plus efficacement. Ayant accès à l'itinéraire à l'avance, ils peuvent charger les palettes dans le camion selon une approche LIFO (premier entré, dernier sorti), en utilisant davantage l'espace disponible.

Bien qu’il s’agisse d’un premier pas dans la bonne direction, nous pourrions apporter quelques améliorations futures une fois que cette initiative sera jugée réussie. Un abonnement à un service de trafic aidera à la planification et à l'augmentation des itinéraires. Cela permettrait un recalcul d'itinéraire basé sur des événements de circulation locaux importants sur une ou plusieurs autoroutes.

Nous pourrions également utiliser l’approche n-vecteur pour le positionnement des coordonnées au lieu d’utiliser les coordonnées abrégées de latitude et de longitude. L’avantage ici est que nos coordonnées seraient déjà converties en vecteurs, ce qui conduirait probablement à des approximations plus précises du plus proche voisin.

Consultez ce référentiel GitHub pour le code des exemples de points de terminaison de service de transport décrits ci-dessus et découvrez comment DataStax permet l'IA générative avec la recherche vectorielle .

Par Aaron Ploetz, DataStax