An Enhanced Neighborhood Search Algorithm for Solving the Split Delivery Vehicle Routing Problem with Two-dimensional Loading Constraints

Abstract The split delivery vehicle routing problem with two-dimensional loading constraints (2L-SDVRP) is a complex practical problem in the field of logistics. It aims at finding the optimal vehicle routes and two-dimensional packing layouts of items in each vehicle to minimize the transportation cost. In this work, we present a mathematical model of 2L-SDVRP with wide-ranging practical considerations. Then we propose an enhanced neighborhood search algorithm (ENS) incorporated with the maximum-space-utilization-based tabu search packing algorithm (MSUTS) to solve the 2L-SDVRP, where the MSUTS examines the feasibility of packing in each route. To accelerate the solving process, a sequence-optimization and random-splitting-based initialization strategy is further proposed. Meanwhile, three classical neighborhood operators are modified to adapt to the 2L-SDVRP with split delivery and two-dimensional packing. The proposed algorithms are tested on a large number of instances varying with scales and properties, which verifies the effectiveness of the proposed algorithm for solving the 2L-SDVRP. Observation of the results also infers the split delivery shows an economic advantage over the non-split case and the advantage becomes significant when the total area of items of each customer increases.