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

Jun. 2018

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 as shown in Figure 1: 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.
Avatar

Figure 1 The proposed problem is comprised of three NP-hard sub-problems.

Figure 2 shows the algorithm implementation as it was deployed in the UAT system. For a given delivery order, we first estimate the minimum number nv of required vehicles with the assumption of container being fully loaded.
Avatar

Figure 2 System architecture of DTSA

The outermost layer of DTSA uses EDA to search for vehicle routing solutions, as shown in Figure 3. We model a random solution generator using a probability matrix of vehicle transitions. By sampling from the generator, we can get a set of routing plans. Given a routing plan, the inner layer further uses EDA to search for cargo-splitting solutions. The splittings are also sampled from a generator, represented as a probability matrix of cargo allocation. Sampling from this generator we obtain a set of candidate solutions, each with a routing plan and a cargo splitting plan. Then, for each candidate solution, the innermost layer uses a container loading module to estimate a 3D loading plan as shown in Figure 4. Finally, based on the loading results, each solution will be evaluated to obtain its fitness.
Avatar

Figure 3 Outermost layer of DTSA uses EDA to search for vehicle routing solutions.

Avatar

Figure 4 Container loading module

The cargo splittings of solutions with good fitness are selected to update the generator distribution for the EDA for cargo splitting. When the inner layer EDA converges, the routing plans of solutions with good fitness are selected to update the generator distribution of the EDA for vehicle routing. The algorithm repeats the above process until the outermost EDA has converged. After that, the optimal cargo transportation strategy found so far for the nv vehicles is output as an intermediate result. The intermediate result is further processed to find the best container category to fit the current transportation strategy. Because the number of vehicles (and therefore containers) is constrained to be nv, not all cargoes may be allocated, and the remaining cargoes are used to generate a `virtual' delivery order, fed as input for the next epoch.
The above will repeat until all intermediate outputs cover all cargoes in the initial delivery order, at which collection point the results are merged as the final output strategy. The benefit of using EDA is that learning the parameters of the probability matrix is more efficient than directly searching for individual solutions, also offering a convenient way to introduce expert knowledge.
Avatar

Figure 5 Accuracy and efficiency evaluation results

Extensive experimental results 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 benchmark algorithms both in efficiency and optimization performance as shown in Figure 5. Dispatch engineers of Huawei's logistics system also confirmed that the proposed algorithm can save more than 8.9% containers over old system, attained by the best strategies by human experts with domain knowledge.

Paper:
Xijun Li, Mingxuan Yuan, Di Chen, Jianguo Yao, and Jia Zeng. 2018. A Data-Driven Three-Layer Algorithm for Split Delivery Vehicle Routing Problem with 3D Container Loading Constraint. In KDD’18: The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, August 19–23, 2018, London, United Kingdom. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3219819.3219872