A Data-Driven Three-Layer Algorithm for Split Delivery Vehicle Routing Problem with 3D Container Loa

Xijun Li (Huawei Noah's Ark Lab); Mingxuan Yuan (Huawei Noah's Ark Lab); Di Chen (Huawei Noah's Ark Lab); Jianguo Yao (Shanghai Jiao Tong University); Jia Zeng (Huawei Noah's Ark Lab)

Split Delivery Vehicle Routing Problem with 3D Loading Constraints (3L-SDVRP) can be seen as the most important problem in large-scale manufacturing logistics. The goal is to devise a strategy consisting of three NP-hard planning components: vehicle routing, cargo splitting and container loading, which shall be jointly optimized for cost savings. The problem is an enhanced variant of the classical logistics problem 3L-CVRP, and its complexity leaps beyond current studies of solvability. Our solution employs a novel data-driven three-layer search algorithm (DTSA), which we designed to improve both the efficiency and effectiveness of traditional meta-heuristic approaches, through learning from data and from simulation.

A detailed experimental evaluation on real data shows our algorithm is versatile in solving this practical complex constrained multi-objective optimization problem, and our framework may be of general interest. DTSA performs much better than the state-of-the-art algorithms both in efficiency and optimization performance. Our algorithm has been deployed in the UAT (User Acceptance Test) environment; conservative estimates suggest that the full usage of our algorithm would save millions of dollars in logistics costs per year, besides savings due to automation and more efficient routing.

Promotional Video