矢量搜索应用：优化零售货运路线

向量和向量搜索是大型语言模型 (LLM) 的关键组件，但它们在许多您可能没有考虑到的用例中的许多其他应用程序中都很有用。最有效的零售商品配送方式怎么样？

在本系列的前两篇文章中，我讲述了一个假设的承包商的故事，他被雇用来帮助在大型零售商实施 AI/ML 解决方案，然后探讨了这个分布式系统和 AI 专家如何使用矢量搜索来驱动客户结果公司的促销活动。现在，我将向您介绍该承包商如何使用矢量搜索来优化货运路线。

问题

当我们在本系列第一个故事中考虑缩小（并最终禁用）推荐批处理作业的选项时，我们被邀请参加与运输服务团队的会议。他们听说了我们如何协助促销团队，并想知道我们是否可以看看他们的问题。

BigBoxCo 的产品从机场和港口用卡车运来。一旦到达配送中心 (DC)，它们就会被贴上标签并分成较小的货物运送到各个实体店。虽然我们有自己的半挂车用于这部分产品运输，但车队的组织效率不高。

目前，卡车的数字设备上会向司机提供商店列表，主管会建议一条路线。然而，司机们常常对商店停靠的顺序犹豫不决，并且常常无视主管的路线建议。当然，这会导致预期发货和补货时间以及总时间的差异。

知道这一点后，配送中心的工作人员无法完全装满每个卡车集装箱，因为他们必须在卡车上留出空间，以便取放每个商店的产品托盘。理想情况下，订购产品托盘时，第一家商店的托盘应位于拖车中最容易接近的位置。

改善体验

运输服务团队希望我们检查可用数据，看看是否有更明智的方法来解决这个问题。例如，如果有一种方法可以通过确定司机访问商店的顺序来预先确定最佳可能的路线，该怎么办？

这类似于“旅行推销员问题”（TSP），这是一个假设的问题，其中向推销员提供了要访问的城市列表，并且需要找出它们之间最有效的路线。虽然 TSP 的编码实现可能变得相当复杂，但我们也许可以使用 Apache Cassandra 等矢量数据库来实现矢量搜索功能来解决这个问题。

显而易见的方法是绘制出每个目的地城市的每个地理位置坐标。然而，这些城市仅分布在当地的大都市区，这意味着纬度和经度的整数大部分是相同的。这不会导致大量容易检测到的差异，因此我们应该通过仅考虑 Geo URI 方案小数点右侧的数字来重新关注该数据。

例如，罗杰斯维尔市（我们的 BigBoxCo 商店之一的位置）的 Geo URI 为 45.200,-93.567。如果我们查看坐标的每个小数点的右侧，得到调整后的坐标 200,-567（而不是 45.200,-93.567），我们将能够更轻松地检测此向量和其他向量的方差。

对设有我们商店的当地大都市采取这种方法，我们可以得到以下数据：

执行

现在我们有了数据，我们可以在 Cassandra 集群中使用二维向量创建一个表。我们还需要在向量列上创建一个 SSTable 附加二级索引 (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';

这将使我们能够使用矢量搜索来确定访问每个城市的顺序。然而，值得注意的是，矢量搜索基于基于余弦的距离计算，假设点位于平面上。众所周知，地球不是一个平面。计算大地理区域的距离应该使用另一种方法来完成，例如半正弦公式，它考虑了球体的特征。但就我们在小型本地都市区的目的而言，计算近似最近邻 (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)

请注意，我们还包含了“ similarity_cosine ”函数的结果，以便我们可以看到 ANN 结果的相似性。正如我们所看到的，在忽略顶部的法利（与我们的起点 100% 匹配）之后，罗杰斯维尔市重新成为近似最近的邻居。

接下来，让我们构建一个微服务端点，该端点基本上根据起点和返回的顶部 ANN 遍历城市。它还需要忽略它已经去过的城市。因此，我们构建了一个可以 POST 的方法，以便我们可以在请求正文中提供起始城市的 ID 以及建议路线的城市列表：

 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）。

提高准确性的一种方法是为高速公路路段创建矢量。我们可以创建一个高速公路表，并根据它们彼此以及我们的城市的相交方式，通过其起始和结束坐标为每个高速公路生成向量。

 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 中所示的地图，我们可以看到 Farley 和 Rogersville 通过 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) 的方式将托盘装载到卡车上，从而利用更多的可用空间。

虽然这是一个很好的第一步，但一旦该举措被认为成功，我们可以在未来做出一些改进。订阅交通服务将有助于路线规划和增强。这将允许根据一条或多条高速公路上的重要本地交通事件重新计算路线。

我们还可以使用 n 向量方法进行坐标定位，而不是使用缩写的纬度和经度坐标。这里的优点是我们的坐标已经转换为向量，可能会导致更准确的最近邻近似值。

查看此 GitHub 存储库，获取上述示例运输服务端点的代码，并了解有关DataStax 如何通过矢量搜索实现生成式 AI 的更多信息。

作者：Aaron Ploetz，DataStax