ベクトル検索アプリケーション: 小売トラック輸送ルートの最適化

ベクトルとベクトル検索は、大規模言語モデル (LLM) の主要なコンポーネントですが、これまで考慮されていなかった多くの使用例にわたる他の多数のアプリケーションでも役立ちます。小売商品を配達する最も効率的な方法はどうでしょうか?

このシリーズの前 2 回の記事では、大手小売店で AI/ML ソリューションの実装を支援するために雇われた架空の請負業者の話をしました。その後、この分散システムと AI のスペシャリストがベクトル検索を使用して顧客の結果を促進する方法を探りました。会社での昇進。次に、この請負業者がベクトル検索を使用してトラック輸送ルートを最適化する方法について説明します。

問題

このシリーズの最初の記事で紹介したレコメンデーション バッチ ジョブをスケールダウンする (最終的には無効にする) オプションを検討しているときに、運輸サービス チームとのミーティングに招待されました。彼らは私たちがプロモーション チームをどのように支援したかを聞いており、私たちが彼らの問題を解決できないかと考えていました。

BigBoxCo は、空港や出荷港から製品をトラックで運び込んでいます。配送センター (DC) に到着すると、タグが付けられ、個々の実店舗向けに小さな荷物に分けられます。当社では製品輸送のこの部分のために独自のセミトレーラーを用意していますが、車両は効率的に編成されていません。

現在、ドライバーにはトラックのデジタルデバイスにある店舗のリストが与えられ、監督者がルートを提案している。しかし、運転手は店に立ち寄る順番について躊躇することが多く、上司のルート提案を無視することもよくあります。当然、これにより、予想される出荷時間や再入荷時間、さらには所要時間の合計にもばらつきが生じます。

このことを知っている DC スタッフは、各店舗の製品パレットにアクセスするためにトラックにスペースを残しておく必要があるため、各トラックのコンテナを完全に埋めることができません。理想的には、製品パレットは、最初の店舗のパレットがトレーラーの最もアクセスしやすい位置にある状態で注文されます。

エクスペリエンスの向上

Transportation Services チームは、入手可能なデータを調査し、この問題に対処するより賢明な方法がないかどうかを確認したいと考えています。たとえば、ドライバーが店舗を訪問する順序を決定することで、最適なルートを事前に決定できる方法があればどうなるでしょうか。

これは、セールスマンが訪問する都市のリストを与えられ、それらの間の最も効率的なルートを見つけ出す必要があるという仮説的な問題である「巡回セールスマン問題」(TSP) に似ています。 TSP のコード化された実装は非常に複雑になる可能性がありますが、Apache Cassandra のようなベクトル データベースをベクトル検索機能に使用すると、これを解決できる可能性があります。

明らかなアプローチは、各目的地の都市のそれぞれの地理位置座標をプロットすることです。ただし、都市は地方の大都市圏にのみ分散しているため、緯度と経度の整数はほぼ同じになります。これでは、簡単に検出できるほどの差異は生じないため、Geo URI スキームの小数点の右側の数字だけを考慮して、そのデータに焦点を絞り直す必要があります。

たとえば、ロジャーズビル市 (BigBoxCo ストアの 1 つの所在地) の地域 URI は 45.200,-93.567 です。座標の各小数点の右側を見て、調整された座標 200,-567 (45.200,-93.567 ではなく) に到達すると、このベクトルと他のベクトルの分散をより簡単に検出できるようになります。

店舗のある地方の大都市に対してこのアプローチを採用すると、次のデータが得られます。

実装

データが揃ったので、Cassandra クラスター内に 2 次元ベクトルを使用してテーブルを作成できます。ベクター列に SSTable Attached Secondary Index (SASI) を作成する必要もあります。

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

これにより、ベクトル検索を使用して各都市を訪問する順序を決定できるようになります。ただし、ベクトル検索は、点が平面上にあると仮定して、コサインベースの距離計算に基づいていることに注意することが重要です。私たちが知っているように、地球は平面ではありません。広い地理的領域にわたる距離を計算するには、球の特性を考慮するHaversine 公式のような別のアプローチを使用して行う必要があります。ただし、小規模なローカル大都市圏での目的の場合、近似最近傍 (ANN) の計算は問題なく機能するはずです。

次に、都市ベクトルをテーブルにロードしましょう。これでクエリを実行できるようになります。

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

ルートを開始するために、まずファーリーにある倉庫配送センターを検討します。これはベクトル 86, -263 で保存されています。まず、Farley のベクトルの ANN について ` location_vectors ` テーブルをクエリすることから始めます。

 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;

クエリの結果は次のようになります。

 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)

ANN の結果の類似性が見えるように、「 similarity_cosine 」関数の結果も含めていることに注意してください。ご覧のとおり、トップのファーリーを無視した後 (開始点と 100% 一致)、ロジャーズビル市がほぼ最近隣として戻ってきています。

次に、開始点と返された最上位の ANN に基づいて基本的に都市を横断するマイクロサービス エンドポイントを構築しましょう。すでに訪れたことのある都市も無視する必要があるだろう。したがって、リクエストの本文で開始都市の ID と、提案されたルートの都市のリストを提供できるように、POST できるメソッドを構築します。

 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'

` location_id ' “B1643” (Farley) を使用してこのサービスを呼び出すと、次の出力が返されます。

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

したがって、これはトラック輸送ルートに体系的なガイダンスを提供するという意味で非常に効果的です。ただし、サービス エンドポイントと (プロキシによる) ANN クエリは、これらの各都市を接続する高速道路システムを理解していません。今のところ、私たちのトラックが「飛ぶように」各都市に直接移動できると単純に想定しています。

現実的には、そうではないことはわかっています。実際に、これらの各都市と接続する高速道路がマークされた大都市圏の地図を見てみましょう (図 1)。

ここで精度を高める 1 つの方法は、高速道路のセグメントのベクトルを作成することです。高速道路テーブルを作成し、それらが互いにどのように交差するか、また都市とどのように交差するかに基づいて、開始座標と終了座標によってそれぞれのベクトルを生成できます。

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

次に、各高速道路にベクトルを挿入できます。また、ANN クエリでどちらかの都市を開始点または終了点として使用できるように、高速道路セグメントの両方向のエントリも作成します。例えば：

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

元のクエリの結果から離れて、別のクエリを実行して、ファーリー (86,-263) の DC とロジャーズビル (200,-567) の店舗の座標の ANN を使用して高速道路ベクトルをプルバックできます。

 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)

図 1 に示す地図を見ると、ファーリーとロジャーズビルが高速道路 610 号線と 54 号線で接続されていることがわかります。

別のサービス エンドポイントを構築して、開始都市と終了都市の座標に基づいて、ある都市から別の都市への高速道路ルートを構築できます。このサービスを完全なものにするためには、返還された「孤立した」高速道路 (予想ルート上にない高速道路) をすべて削除し、途中で立ち寄りたいと思われる店舗のある都市を含める必要があります。

Farley (B1643) と Rogersville (B5243) の「 location_ids 」を使用した場合、次のような出力が得られるはずです。

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

結論と次のステップ

これらの新しい交通サービスは、ドライバーと DC の管理に大きく役立つはずです。店舗間のルート決定に関して数学的に重要な結果が得られるはずです。

素晴らしい副次的な利点は、DC スタッフがより効率的にトラックに荷物を積むことができることです。事前にルートにアクセスできるため、利用可能なスペースをより多く使用して、先入れ後出し (LIFO) アプローチでパレットをトラックに積み込むことができます。

これは良い第一歩ですが、この取り組みが成功したと判断されれば、将来的にはいくつかの改善を加えることができます。交通サービスのサブスクリプションは、ルートの計画と拡張に役立ちます。これにより、1 つ以上の高速道路での重要なローカル交通イベントに基づいてルートを再計算できます。

省略された緯度と経度の座標を使用する代わりに、座標の位置決めに n ベクトルのアプローチを使用することもできます。ここでの利点は、座標がすでにベクトルに変換されており、より正確な最近傍近似が得られる可能性が高いことです。

この GitHub リポジトリで上記の交通サービス エンドポイントの例のコードを確認し、 DataStax がベクトル検索を使用して生成 AI を実現する方法について詳しく学習してください。

DataStax、Aaron Ploetz 著