#218 - Ứng dụng Machine Learning vào bài toán định tuyến phương tiện

Bài toán định tuyến phương tiện (vehicle routing) là một dạng của bài toán tối ưu tổ hợp. Một ví dụ tiêu biểu là bài toán giao hàng chặng cuối (last-mile delivery), yêu cầu vận chuyển hàng hóa từ kho trung tâm tới nhiều thành phố, đồng thời vẫn phải giữ chi phí di chuyển ở mức thấp. 

Để giải dạng bài này, ta thường sử dụng các thuật toán heuristic để tìm ra những giải pháp đủ tốt. Các thuật toán được thiết kế trước đây có thể giải quyết vấn đề này cho vài trăm thành phố, nhưng chạy quá chậm ở quy mô lớn hơn. Thường ta không thể tìm được giải pháp tốt nhất để giải quyết vấn đề, đơn giản là vì có quá nhiều giải pháp tiềm năng. 

Các nhà nghiên cứu tại MIT đã ứng dụng ML (Machine Learning) để giải quyết vấn đề này. Trước tiên, họ sử dụng thuật toán để chia bài toán giao hàng ra thành nhiều bài toán con, ví dụ 200 bài toán con cho định tuyến giữa 2000 thành phố. Sau đó, thay vì giải toàn bộ các bài toán con, họ làm giàu tiến trình này bằng cách sử dụng một thuật toán ML mới để nhận diện các bài toán con nào là có giá trị nhất để giải, nhằm tăng chất lượng của giải pháp trong khi sử dụng tài nguyên tính toán thấp hơn nhiều lần. Cụ thể trong bài toán định tuyến phương tiện, họ đã tăng tốc độ giải các thuật toán từ 10 đến 100 lần.

Phương pháp nêu trên, learning-to-delegate, có thể áp dụng cho nhiều bài toán tương tự, ví dụ như điều phối hoặc tìm đường đi cho robot kho vận. Phương pháp này cho phép tự động đẩy nhanh tốc độ heuristics cho những bài toán lớn, bất kể heuristics hay vấn đề là gì.

Trong một cơ sở dữ liệu theo dạng time series, mỗi hàng sẽ gồm các cột chứa thông tin để định danh và phân loại. Trong trường hợp của một hệ thống IoT, do số lượng thiết bị và cảm biến lớn, nên cơ sở dữ liệu thường sẽ có kích thước rất lớn. Giả sử một hệ thống có 1000 thiết bị IoT ở 20 địa điểm, các thiết bị này chạy trên 5 phiên bản firmware, và mỗi thiết bị có 5 loại cảm biến. Khi đó, số phần tử của bộ dữ liệu sẽ là 500,000 (1000 x 20 x 5 x 5). Con số này sẽ tăng theo cấp số mũ khi ta thêm thiết bị hoặc phiên bản firmware mới, điều này rất dễ dẫn tới việc mất kiểm soát về bộ dữ liệu.

Với bộ dữ liệu đa dạng về mặt thuộc tính (high-cardinality) như vậy, cơ sở dữ liệu của sẽ có tính chất sau:

1. Bảng dữ liệu sẽ cần index ở nhiều cột

2. Mỗi cột được index sẽ chứa nhiều giá trị duy nhất

Trong bài viết này, tác giả chứng minh tính hiệu quả của QuestDB bằng cách benchmark với các loại cơ sở dữ liệu dạng time series khác (như ClickHouse, influxdb hay TimescaleDB), và giải thích vì sao QuestDB có thể dễ dàng xử lý dữ liệu dạng time series với lượng dữ liệu lớn và nhiều thuộc tính.

Mời bạn đọc tìm hiểu chi tiết tại link bên dưới.

Trên sàn Ebay, làm sao để người bán hàng tự tạo coupon để chia sẻ công khai ngay trên website hoặc gửi qua các kênh tiếp thị riêng của họ, và in ra để gửi kèm theo gói hàng nhằm khuyến khích khách hàng cũ quay lại? Chỉ trong 5 tháng sau khi phát hành, Coded Coupons Tool (CCT) đã thu hút hơn một triệu khách hàng Ebay sử dụng tính năng này.

CCT được phát triển với tech-stack mới của Ebay như Raptor và NodeJS, sử dụng cơ chế ghi kép (dual-write). Hệ thống quản lý cơ sở dữ liệu quan hệ của Oracle giúp người bán (seller) linh hoạt kiểm soát việc cung cấp các mã chiết khấu và đảm bảo tính nhất quán giao dịch của người mua (buyer), còn MongoDB cluster giúp scale cho hàng tỉ lượt xem, hiển thị thông tin chiết khấu tại các vị trí chiến lược trong quá trình tìm kiếm và giao dịch của người mua.

Mảng Seller. Ebay thiết kế kiến trúc mảng Seller dựa trên nguyên lý backend-for-frontend, hay còn gọi là “Experience Services”. Hệ thống hoạt động song song giữa Java/Scala và NodeJS mang đến trải nghiệm tối ưu cho người dùng, cải thiện thời gian phản hồi và giảm tỉ lệ xảy ra lỗi. Khi buyer tạo và đặt giờ cho coupon, event sẽ được đẩy vào hệ thống BES (Business Event Stream), lưu tại cassini-db phục vụ cho các mục đích tăng trải nghiệm người mua như đánh chỉ mục cho hàng khuyến mãi khi hiển thị kết quả tìm kiếm, cập nhật dữ liệu nhất quán…

Mảng Buyer. Như đã đề cập, kiến trúc mảng Buyer sử dụng cơ chế ghi kép. 

Mời bạn đọc tìm hiểu chi tiết tại link bên dưới.

Reading in Database system, hay còn gọi là The Redbook, là một quyển tổng hợp các bài báo kinh điển trong lĩnh vực Data Management từ năm 1988 đến nay.

Trong quyển sách này, các tác giả tổng hợp lại một vài bài báo mà theo các tác giả là quan trọng và có tầm ảnh hưởng lên các thiết kế của các hệ thống quản trị data hiện đại. Bên cạnh việc liệt kê các bài báo, các tác giả còn đưa ra những nhận định của mình giúp chúng ta có một cái nhìn tổng quan về cách những công nghệ lõi liên quan đến data đã biến đổi như thế nào theo thời gian, từ đó cũng sẽ giúp ta hiểu rõ hơn về những bài toán ở hiện tại.

Trong mỗi phiên bản mới được tái bản sau vài năm, các tác giả lại cập nhật danh sách các bài báo cũng như điều chỉnh các nhận định của mình. 

Bản mới nhất của quyển sách này là quyển được tái bản lần 5, mời các bạn đọc ở link sau.