Google Research ra mắt MilleMiglia: Công cụ mô phỏng logistics chặng trung gian

Làm thế nào một chiếc poffert của Hà Lan có thể đến tận cửa nhà bạn, cách xa 450 dặm (700 km), ngay vào ngày hôm sau? Đó là nhờ vào việc tối ưu hóa logistics cẩn thận — đặc biệt là phân khúc chặng giữa (middle-mile). Phần này của hành trình bao phủ quãng đường dài nhất, chiếm một phần lớn chi phí tổng thể và quan trọng nhất là quyết định liệu chiếc poffert của bạn đến nơi còn tươi mới hay đã ôi thiu.

Nghiên cứu về logistics từ trước đến nay thường tập trung vào chặng đầu (vận chuyển hàng hóa từ nhà sản xuất đến các điểm tập kết ban đầu) và chặng cuối (giao hàng đến người tiêu dùng). Cả hai giai đoạn này thường được mô hình hóa dưới dạng các biến thể của bài toán định tuyến phương tiện (VRP). Tuy nhiên, chặng giữa, nơi xử lý việc vận chuyển khối lượng lớn hàng hóa giữa các trung tâm phân phối ở quy mô khu vực hoặc lục địa, lại nhận được ít sự chú ý hơn đáng kể trong nghiên cứu vận hành, mặc dù nó chiếm một phần đáng kể trong tổng chi phí logistics. Tiến bộ học thuật trong việc tối ưu hóa chặng giữa đã bị cản trở do thiếu dữ liệu công khai, chất lượng cao. Thực tế, hầu hết các công ty logistics coi cấu trúc mạng lưới và khối lượng nhu cầu của họ là thông tin độc quyền có tính bảo mật cao.

Logistics chặng giữa có nhiều ứng dụng trong chuỗi cung ứng. Chúng trải dài từ việc vận chuyển hàng hóa từ nhà máy đến người tiêu dùng trong thương mại điện tử và các nhà bán lẻ ở trung tâm thành phố, cho đến việc vận chuyển các linh kiện phù hợp từ các nhà máy riêng lẻ và kho lưu trữ trung tâm đến các nhà sản xuất ô tô và cửa hàng. Nó cũng bao gồm các hoạt động vận chuyển nhạy cảm với thời gian, như vận chuyển dược phẩm được kiểm soát nhiệt độ giữa các cơ sở lưu trữ và bệnh viện.

Để giải quyết tình trạng thiếu dữ liệu chuẩn hóa cho lĩnh vực này, trong bài báo “A Novel Instance Generator for Simulating Middle-Mile Logistics Networks”, chúng tôi giới thiệu MilleMiglia, một trình tạo dữ liệu mẫu bằng C++ được thiết kế để tạo ra các điểm chuẩn thực tế cho các bài toán giao hàng chặng giữa. Công trình này đóng vai trò là nền tảng để thúc đẩy các kết quả nghiên cứu trong tương lai. Trong bài viết này, chúng tôi khám phá những ràng buộc độc đáo của chặng giữa và cách MilleMiglia nắm bắt chúng thành công để tạo ra dữ liệu thực tế, bảo đảm quyền riêng tư. Mã nguồn và tài liệu hiện đã có sẵn trên GitHub.

Phổ logistics: Chặng đầu, chặng cuối và chặng giữa

Sự khác biệt giữa logistics chặng đầu, chặng giữa và chặng cuối nằm ở hành trình của một lô hàng riêng lẻ. Trong suốt hành trình này, mục tiêu vận hành chính là sử dụng hiệu quả đội xe để ghé thăm nhiều địa điểm. Hãy xem xét ví dụ về một nhà sản xuất bán hàng trên một thị trường trực tuyến thông thường để tiếp cận người tiêu dùng cá nhân.

Trong logistics chặng đầu và chặng cuối, một lô hàng cụ thể vẫn nằm trên một phương tiện duy nhất từ điểm xuất phát (nhà máy ở chặng đầu, trung tâm phân phối ở chặng cuối) đến điểm đến (trung tâm phân phối ở chặng đầu, khách hàng ở chặng cuối). Các bài toán VRP này liên quan đến việc tối ưu hóa một đội xe gồm nhiều phương tiện trong một khoảng thời gian giới hạn, thường là một ngày. Thách thức tối ưu hóa về cơ bản là vấn đề phân công và lập trình tự: xác định phương tiện nào xử lý tập hợp lô hàng nào và theo thứ tự nào.

Trong ví dụ của chúng tôi, chặng đầu tương ứng với việc thu gom các mặt hàng đã được nhà sản xuất bán (ví dụ: pofferts) trong khi chặng cuối bao gồm việc giao hàng cuối cùng đến tay người tiêu dùng (một số người trong số họ đang khá đói!). Trong cả hai trường hợp, một chiếc xe tải duy nhất vận chuyển hàng hóa đến hoặc đi từ trung tâm phân phối khu vực. Tuy nhiên, nếu nhà sản xuất và người tiêu dùng ở các khu vực khác nhau, logistics chặng giữa sẽ thu hẹp khoảng cách giữa các trung tâm phân phối ở xa. Ví dụ, hàng hóa từ một nhà sản xuất ở Groningen (Hà Lan) trước tiên sẽ chuyển đến trung tâm phân phối khu vực ở Utrecht, sau đó di chuyển đến một trung tâm khác ở Paris (Pháp) trước khi được giao cho người tiêu dùng ở Versailles.

Trái ngược với chặng đầu và chặng cuối, chặng giữa hoạt động như một cuộc đua tiếp sức. Một lô hàng đơn lẻ có thể được vận chuyển bởi nhiều phương tiện khác nhau trên khắp mạng lưới lục địa trước khi đến đích cuối cùng, có thể là một tuần sau khi khởi hành. Tại các trung tâm phân phối trung gian, lô hàng có thể được dỡ xuống, phân loại theo điểm đến và hợp nhất với các loại hàng hóa khác trước khi được xếp lên phương tiện tiếp theo. Điều này tạo ra một vấn đề đồng bộ hóa phức tạp: lô hàng phải đến trung tâm phân phối trong một khung thời gian cụ thể để kịp chuyến xe tải xuất phát theo lịch trình. Nếu bỏ lỡ kết nối đã định, nó sẽ phải nằm lại trung tâm phân phối cho đến chu kỳ tiếp theo, dẫn đến sự chậm trễ đáng kể.

Trong ví dụ của chúng tôi, khi hàng hóa của nhà sản xuất đến trung tâm khu vực Utrecht, chúng được xếp lên chiếc xe tải đầu tiên đi Antwerp (Bỉ) để đến nơi trong cùng ngày. Vì chiếc xe tải gần nhất đi Paris đã đầy, và giả sử khách hàng chọn phương thức vận chuyển tiêu chuẩn, hàng hóa sẽ đi chuyến xe tải thứ hai vào ngày hôm sau từ Antwerp đến Paris. Bưu kiện đến Paris vào đêm ngày thứ hai, nơi nó đi vào mạng lưới chặng cuối để giao hàng lần cuối cho khách hàng vào ngày hôm sau.

Mô hình toán học và hạn chế của bộ giải (solver)

Cấu trúc toán học của việc giao hàng chặng giữa khác với VRP tiêu chuẩn ở một vài điểm chính.

Trong một bài toán VRP truyền thống, chẳng hạn như các bài toán được giải quyết bởi các công cụ mã nguồn mở như OR-Tools hoặc các API chuyên dụng như Google Maps Platform Route Optimization (GMPRO), mục tiêu thường là tối ưu hóa các chuyến đi cho một đội xe. Trọng tâm là định tuyến phương tiện và lập trình tự các điểm dừng để đáp ứng thời hạn chặt chẽ của khách hàng. Không giống như giao hàng chặng cuối, logistics chặng giữa có thêm sự linh hoạt khi di chuyển giữa các xe tải. Chúng tôi mô hình hóa chiều bổ sung này như một bài toán luồng đa hàng hóa (multi-commodity flow problem) trên đồ thị không-thời gian. Trong các mô hình này:

Các ràng buộc cứng

Trong khi nhiều bài toán VRP học thuật được định nghĩa với ít ràng buộc, các ràng buộc vận hành chặng giữa rất khó nới lỏng mà không làm biến dạng cấu trúc của vấn đề vận hành đang xét:

Do những phụ thuộc này, các bộ giải VRP hiện có không thể áp dụng cho chặng giữa. Bài toán đòi hỏi một chuỗi các trung tâm phân phối trung gian và sự phân công trên nhiều phương tiện, thường là trong khung thời gian kéo dài nhiều ngày.

MilleMiglia: Tạo các điểm chuẩn thực tế

Các phân phối dựa trên dữ liệu

MilleMiglia sử dụng nhiều phân phối thống kê để đảm bảo rằng các mạng lưới tổng hợp trông giống như các mạng lưới phân phối thực tế mà không tiết lộ bất kỳ thông tin riêng tư nào:

Các phân phối này nội suy giữa thông tin có sẵn công khai từ các tác nhân công nghiệp và dữ liệu được tiết lộ riêng tư.

Hiệu suất và quy mô

MilleMiglia được viết bằng C++. Nó sử dụng Protocol Buffers để tuần tự hóa dữ liệu, nhờ đó dữ liệu đa dạng có thể được lưu trữ trong một tệp duy nhất cho mỗi trường hợp. Do đó, các trường hợp được tạo ra rất nhỏ gọn và có thể dễ dàng được sử dụng bởi các bộ giải viết bằng các ngôn ngữ lập trình khác nhau.

Không giống như các trường hợp VRP, với nhiều biến thể như CVRP (có sức chứa), VRPTW (có khung thời gian), hoặc PDPTW (nhận và giao hàng có khung thời gian) để nắm bắt các yêu cầu vận hành đa dạng, cấu trúc định dạng dữ liệu chặng giữa của chúng tôi nhúng tất cả các ràng buộc thú vị vào cùng một định dạng tệp: lịch trình phương tiện cố định, giới hạn thông lượng của trung tâm phân phối và các điều kiện tiên quyết về đồng bộ hóa phức tạp đều là những yếu tố cơ bản của cấu trúc bài toán.

Mục đích là cung cấp cho cộng đồng một loạt các trường hợp:

Trình tạo này cũng cho phép các kịch bản học tập, vì nó có thể tạo ra các tập dữ liệu khổng lồ để huấn luyện các thuật toán ML.

Nghiên cứu hợp tác và các bộ giải tương lai

MilleMiglia là bước đầu tiên hướng tới một bộ điểm chuẩn tiêu chuẩn hóa cho logistics chặng giữa, tương tự như những gì CVRPLIB (Capacitated Vehicle Routing Problem Library) cung cấp cho cộng đồng VRP.

Dự án này xuất phát từ sự hợp tác đang diễn ra giữa Google và các đối tác học thuật tại UniBrescia và ENPC Paris. Ngoài việc tạo dữ liệu mẫu, chúng tôi hiện đang làm việc trên một bộ giải chuyên dụng và API được thiết kế đặc biệt cho các bài toán vận hành chặng giữa. Bộ giải này nhằm mục đích tận dụng cấu trúc độc đáo của các luồng chặng giữa.

Bằng cách cung cấp mã nguồn mở cho trình tạo dữ liệu mẫu của mình, chúng tôi hy vọng sẽ khuyến khích cộng đồng nghiên cứu rộng lớn hơn tập trung vào các thách thức vận hành của chặng giữa, dẫn đến các chuỗi cung ứng toàn cầu mạnh mẽ và hiệu quả hơn. Chúng tôi hy vọng sẽ bắt đầu một thử thách về các bài toán chặng giữa để tăng sự quan tâm từ các học giả và các nhà phát triển bộ giải công nghiệp đối với lĩnh vực vốn bị xem nhẹ nhưng đang rất cần được tối ưu hóa này. Bất kỳ ai quan tâm đến lĩnh vực này có thể bắt đầu bằng cách xem một trường hợp mẫu được lưu trữ trong kho GitHub.

Lời cảm ơn

Nghiên cứu này chủ yếu được thực hiện bởi Aymane Lotfi trong thời gian làm Nghiên cứu sinh tại Google và bởi Matteo Petris (hiện tại ở ENPC Paris), như một phần của sự hợp tác đang diễn ra. Cảm ơn Thibaut Cuvelier và Bruno De Backer vì những đóng góp của họ cho công trình này. Đặc biệt cảm ơn Claudia Archetti (hiện tại ở UniBrescia) vì sự lãnh đạo và hỗ trợ của cô.