Ứng dụng tìm kiếm Vector: Tối ưu hóa các tuyến đường vận tải đường bộ bán lẻ

Vectơ và tìm kiếm vectơ là thành phần chính của mô hình ngôn ngữ lớn (LLM), nhưng chúng hữu ích trong nhiều ứng dụng khác trong nhiều trường hợp sử dụng mà bạn có thể chưa xem xét. Làm thế nào về cách hiệu quả nhất để giao hàng bán lẻ?

Trong hai bài viết trước của loạt bài này, tôi đã kể câu chuyện về một nhà thầu giả định được thuê để giúp triển khai các giải pháp AI/ML tại một nhà bán lẻ lớn, sau đó khám phá cách hệ thống phân phối và chuyên gia AI này sử dụng tìm kiếm vectơ để mang lại kết quả với khách hàng. khuyến mại tại công ty. Bây giờ, tôi sẽ hướng dẫn bạn cách nhà thầu này sử dụng tìm kiếm vectơ để tối ưu hóa các tuyến đường vận tải đường bộ.

Vấn đề

Trong khi chúng tôi đang xem xét các lựa chọn để giảm quy mô (và cuối cùng là vô hiệu hóa) công việc hàng loạt đề xuất từ câu chuyện đầu tiên trong loạt bài này, chúng tôi đã được mời tham dự một cuộc họp với nhóm Dịch vụ Vận tải. Họ đã biết cách chúng tôi hỗ trợ nhóm Khuyến mại và đang tự hỏi liệu chúng tôi có thể xem xét vấn đề của họ hay không.

BigBoxCo có sản phẩm được vận chuyển bằng xe tải từ các sân bay và cảng vận chuyển. Khi đến trung tâm phân phối (DC), chúng sẽ được gắn thẻ và tách thành các lô hàng nhỏ hơn cho các cửa hàng truyền thống riêng lẻ. Mặc dù chúng tôi có sơ mi rơ moóc riêng cho phần này của hành trình sản phẩm nhưng đội xe này không được tổ chức hiệu quả.

Hiện tại, các tài xế được cung cấp danh sách các cửa hàng trên thiết bị kỹ thuật số của xe tải và người giám sát gợi ý lộ trình. Tuy nhiên, các tài xế thường ngần ngại về thứ tự các điểm dừng tại cửa hàng và họ thường bỏ qua gợi ý về lộ trình của người giám sát. Tất nhiên, điều này dẫn đến sự khác biệt về thời gian vận chuyển và bổ sung hàng dự kiến cũng như tổng thời gian thực hiện.

Biết được điều này, nhân viên DC không thể chất đầy từng container xe tải vì họ phải chừa chỗ trống trong xe tải để tiếp cận các pallet sản phẩm cho mỗi cửa hàng. Lý tưởng nhất là các pallet sản phẩm sẽ được đặt hàng với pallet của cửa hàng đầu tiên ở vị trí dễ tiếp cận nhất trong xe kéo.

Cải thiện trải nghiệm

Nhóm Dịch vụ Vận tải muốn chúng tôi kiểm tra dữ liệu hiện có và xem liệu có cách nào thông minh hơn để tiếp cận vấn đề này hay không. Ví dụ: điều gì sẽ xảy ra nếu có một cách mà chúng ta có thể xác định trước tuyến đường tốt nhất có thể đi bằng cách xác định thứ tự mà tài xế nên ghé thăm các cửa hàng?

Điều này tương tự như “bài toán người bán hàng du lịch” (TSP), một bài toán giả định trong đó người bán hàng được đưa cho một danh sách các thành phố sẽ ghé thăm và cần tìm ra con đường hiệu quả nhất giữa chúng. Mặc dù việc triển khai TSP được mã hóa có thể trở nên khá phức tạp, nhưng chúng ta có thể sử dụng cơ sở dữ liệu vectơ như khả năng tìm kiếm vectơ của Apache Cassandra để giải quyết vấn đề này.

Cách tiếp cận rõ ràng là vạch ra từng tọa độ định vị địa lý của từng thành phố đích. Tuy nhiên, các thành phố chỉ trải rộng trên một khu vực đô thị, địa phương, điều đó có nghĩa là các số nguyên vĩ độ và kinh độ sẽ gần như giống nhau. Điều đó sẽ không dẫn đến nhiều khác biệt dễ dàng phát hiện, vì vậy chúng ta nên tập trung lại dữ liệu đó bằng cách chỉ xem xét các số ở bên phải dấu thập phân của lược đồ Geo URI.

Ví dụ: thành phố Rogersville (địa điểm của một trong các cửa hàng BigBoxCo của chúng tôi) có URI địa lý là 45.200,-93.567. Chúng ta sẽ có thể phát hiện phương sai từ vectơ này và các vectơ khác dễ dàng hơn nếu chúng ta nhìn sang bên phải từng dấu thập phân của tọa độ, đạt đến tọa độ được điều chỉnh là 200,-567 (thay vì 45,200,-93,567).

Áp dụng phương pháp tiếp cận này với các thành phố đô thị địa phương với các cửa hàng của chúng tôi sẽ cung cấp cho chúng tôi dữ liệu sau:

Thực hiện

Bây giờ chúng ta có dữ liệu, chúng ta có thể tạo một bảng trong cụm Cassandra bằng vectơ hai chiều. Chúng ta cũng sẽ cần tạo chỉ mục phụ đính kèm SSTable (SASI) trên cột vectơ:

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

Điều này sẽ cho phép chúng tôi sử dụng tìm kiếm vectơ để xác định thứ tự ghé thăm từng thành phố. Tuy nhiên, điều quan trọng cần lưu ý là tìm kiếm vectơ dựa trên các phép tính dựa trên cosine cho khoảng cách, giả sử rằng các điểm nằm trên một mặt phẳng. Như chúng ta đã biết, Trái đất không phải là một mặt phẳng. Việc tính toán khoảng cách trên một khu vực địa lý rộng lớn nên được thực hiện bằng cách sử dụng một phương pháp khác như công thức Haversine , có tính đến các đặc điểm của hình cầu. Nhưng đối với mục đích của chúng tôi trong một khu vực đô thị địa phương nhỏ, việc tính toán hàng xóm gần nhất (ANN) gần đúng sẽ hoạt động tốt.

Bây giờ chúng ta hãy tải các vectơ thành phố vào bảng và chúng ta có thể truy vấn nó:

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

Để bắt đầu một lộ trình, trước tiên chúng ta sẽ xem xét trung tâm phân phối kho hàng ở Farley, nơi chúng ta đã lưu trữ với vectơ 86, -263. Chúng ta có thể bắt đầu bằng cách truy vấn bảng ` location_vectors cho ANN của vectơ 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;

Kết quả của truy vấn trông như thế này:

 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)

Lưu ý rằng chúng tôi cũng đã bao gồm các kết quả của hàm ` similarity_cosine ', để chúng tôi thấy được sự giống nhau của các kết quả ANN. Như chúng ta có thể thấy, sau khi bỏ qua Farley ở vị trí đầu tiên (phù hợp 100% với điểm xuất phát của chúng ta), thành phố Rogersville đang trở lại với tư cách là người hàng xóm gần nhất gần nhất.

Tiếp theo, hãy xây dựng một điểm cuối vi dịch vụ về cơ bản đi qua các thành phố dựa trên điểm xuất phát và ANN hàng đầu được trả về. Nó cũng sẽ cần phải bỏ qua các thành phố mà nó đã từng đến. Do đó, chúng tôi xây dựng một phương thức mà chúng tôi có thể POST tới để có thể cung cấp ID của thành phố xuất phát cũng như danh sách các thành phố cho tuyến đường được đề xuất trong nội dung yêu cầu:

 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'

Gọi dịch vụ này bằng ` location_id ' “B1643” (Farley) trả về kết quả đầu ra sau:

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

Vì vậy, tính năng này hoạt động hiệu quả ở chỗ nó cung cấp một số hướng dẫn có hệ thống cho các tuyến đường vận tải đường bộ của chúng tôi. Tuy nhiên, điểm cuối dịch vụ của chúng tôi và (theo proxy) truy vấn ANN của chúng tôi không hiểu rõ về hệ thống đường cao tốc kết nối từng thành phố này. Hiện tại, giả định đơn giản là xe tải của chúng tôi có thể di chuyển trực tiếp đến từng thành phố “theo đường chim bay”.

Trên thực tế, chúng tôi biết đây không phải là trường hợp. Trên thực tế, chúng ta hãy nhìn vào bản đồ khu vực đô thị của chúng ta, với từng thành phố và đường cao tốc kết nối được đánh dấu (Hình 1).

Một cách để tăng độ chính xác ở đây là tạo vectơ cho các đoạn đường cao tốc. Chúng ta có thể tạo bảng đường cao tốc và tạo vectơ cho từng vectơ theo tọa độ bắt đầu và kết thúc của chúng dựa trên cách chúng giao nhau với nhau và với các thành phố của chúng ta.

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

Sau đó chúng ta có thể chèn vectơ cho từng đường cao tốc. Chúng tôi cũng sẽ tạo các mục nhập cho cả hai hướng của các đoạn đường cao tốc để truy vấn ANN của chúng tôi có thể sử dụng thành phố làm điểm bắt đầu hoặc điểm kết thúc. Ví dụ:

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

Ngoài kết quả từ truy vấn ban đầu, chúng tôi có thể chạy một truy vấn khác để kéo lại các vectơ đường cao tốc bằng ANN tọa độ cho DC ở Farley (86,-263) và cửa hàng của chúng tôi ở 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)

Nhìn vào bản đồ trong Hình 1, chúng ta có thể thấy Farley và Rogersville được nối với nhau bằng đường cao tốc 610 và 54. Bây giờ chúng ta đang tiến tới một điều gì đó!

Chúng tôi có thể xây dựng một điểm cuối dịch vụ khác để xây dựng tuyến đường cao tốc từ thành phố này sang thành phố khác dựa trên tọa độ của thành phố bắt đầu và kết thúc. Để hoàn thiện dịch vụ này, chúng tôi muốn nó loại bỏ mọi đường cao tốc “mồ côi” được trả lại (các đường cao tốc không nằm trên tuyến đường dự kiến của chúng tôi) và bao gồm bất kỳ thành phố nào có cửa hàng mà chúng tôi có thể muốn dừng lại trên đường đi.

Nếu chúng ta sử dụng ` location_ids ' của Farley (B1643) và Rogersville (B5243), chúng ta sẽ nhận được kết quả đầu ra giống như thế này:

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

Kết luận và các bước tiếp theo

Những dịch vụ vận chuyển mới này sẽ giúp ích đáng kể cho các tài xế và quản lý DC của chúng tôi. Bây giờ họ sẽ nhận được kết quả có ý nghĩa về mặt toán học để xác định tuyến đường giữa các cửa hàng.

Một lợi ích phụ tuyệt vời là nhân viên DC có thể lấp đầy xe tải hiệu quả hơn. Với quyền truy cập vào tuyến đường trước thời hạn, họ có thể chất pallet vào xe tải theo phương pháp nhập trước xuất trước (LIFO), sử dụng nhiều không gian có sẵn hơn.

Mặc dù đây là bước khởi đầu tốt nhưng chúng tôi có thể thực hiện một số cải tiến trong tương lai khi sáng kiến này được coi là thành công. Việc đăng ký dịch vụ giao thông sẽ giúp lập kế hoạch và mở rộng tuyến đường. Điều này sẽ cho phép tính toán lại tuyến đường dựa trên các sự kiện giao thông địa phương quan trọng trên một hoặc nhiều đường cao tốc.

Chúng ta cũng có thể sử dụng phương pháp vectơ n để định vị tọa độ thay vì sử dụng tọa độ dọc và vĩ độ viết tắt. Ưu điểm ở đây là tọa độ của chúng ta đã được chuyển đổi thành vectơ, có thể dẫn đến các phép tính gần đúng lân cận gần nhất chính xác hơn.

Hãy xem kho lưu trữ GitHub này để biết mã cho các điểm cuối dịch vụ vận tải mẫu được mô tả ở trên và tìm hiểu thêm về cách DataStax kích hoạt AI tổng hợp với tìm kiếm vectơ .

Bởi Aaron Ploetz, DataStax