Abstract: As the future development of the express delivery industry requires a greater focus on user experience, the integration of drones into vehicle delivery systems can serve as an effective solution to city last-mile logistics and green logistics. In order to ensure the feasibility of loading before the drone-assisted vehicles distribution and the absence of outbound relocating during the delivery process, and considering the three-dimensional loading constraint and the customer service deadline, the Two-echelon Vehicle Routing Problem with Drones Considering Three-dimensional Loading Constraints (3L-2E-VRP-D) is a new optimization problem, which is a combination of a loading problem and a two-echelon vehicle routing problem with drones. Distribution operations are jointly completed by vehicles carrying drones, each of which departs from the depot with some drones and the goods demanded by customers, and returns to the depot after completing distribution services for each customer on the path in turn before the service deadline. The drone loaded with goods takes off from the vehicle, flies to the customer nodes that drone could service and completes the order, and finally returns to the original vehicle via the original route. During the drone distribution period, the vehicle is needed to stay at the departure point of the drone and wait for the drone to fly back. There are several constraints for 3L-2E-VRP-D: (1)the demand of customers served by a vehicle or drone; (2)a feasible placement of items within the loading space; and (3)each customer’s service deadline. Loading items into trucks and successive routing of vehicles and drones along the road network are the most important problems in distribution management.
This paper addresses an important problem combining three-dimensional loading and a two-echelon vehicle routing problem with drones. A mixed integer programming model is established for 3L-2E-VRP-D. Both a two-echelon vehicle routing problem with drones and a three-dimensional loading problem are NP-hard problems. Thus, the combinatorial problem 3L-2E-VRP-D is clearly also the case. Exact algorithmic methodologies are not expected to solve the real-world problems of large customers and item sets in a reasonable time. Therefore, we solve the problem by using a hybrid algorithm based on the Adaptive LargeNeighborhood Search (ALNS). ALNS as the outer algorithm optimizes the vehicle routing through destroy and repair operations. For the goods of customers along the route, the innerImproved Heuristic Loading Algorithm (IHLA) verifies the feasibility of the optimized routes by attempting to construct loading solutions that satisfy three-dimensional packing constraints.
The algorithm is tested and numerically experimented using the Cardiff dataset, a famous VRPTWDR dataset. Information about customer goods is randomly generated. The accuracy of the model and the effectiveness of the algorithm are verified by solving small-scale arithmetic cases by Gurobi and the algorithm. The results show that for 10 sets of small-scale examples, the hybrid algorithm is able to find the optimal solution for 7 of them, with an average GAP value of-1.11% compared to the exact algorithm solver, Gurobi, and the average solution time is reduced by 66.6%. In addition to this, an improvement of the final solution over the initial solution is consistently above 60% using the hybrid algorithm to solve the 25 to 150 customers’ arithmetic cases. Sensitivity analyses are also carried out for four parameters in the problem: the maximum number of drones that can be carried by the vehicle, the average size of the cargo and the parameters of the different types of drones including the maximum load and maximum flight distance. The results show that as the maximum number of drones that can be carried by the vehicle increases, the optimization rate gradually increases, however, its marginal benefit decreases; an increase in the average size of the cargo has a greater impact on the larger number of customers of the algorithm when the average size of the cargo increases to a certain value. With an increase of maximum load and maximum flight distance of the drones, the total delivery time decreases, but the marginal benefit diminishes.
3L-2E-VRP-D considers the realistic loading and unloading problem based on the drone assisted vehicle distribution problem, which is of great significance in the distribution process because, up to the present time in research, it is the closest to the realistic application of drone assisted vehicle distribution in reality, which ensures that a feasible loading plan is available before the distribution and that there is no outbound relocating of the boxes during the distribution process.
Follow-up studies can be carried out in the following aspects: (1)This paper assumes that the goods are not rotatable, and future studies may consider adding the case of the goods being rotatable. (2)The hybrid algorithm is based on the adaptive large neighborhood search, adding an improved heuristic loading algorithm. Future research can design a hybrid algorithm based on the exact algorithm for solving medium-scale problems with higher quality.

Key words: three-dimensional loading, two-echelon vehicle routing problem with drones, hybrid algorithm

摘要： 快递业在将来的发展须更注重用户体验,无人机协助车辆配送系统可以作为城市最后一公里物流与绿色物流的有效解决方案。为保证无人机协助车辆配送前装箱可行和配送过程中不出现翻箱现象,考虑三维装箱约束和客户服务截止时间,建立混合整数规划模型。根据问题提出以自适应大邻域搜索算法为框架的混合算法:外层采用自适应大邻域搜索算法求解路径问题,内层采用改进的启发式装箱算法对路径上客户的货物尝试生成三维装箱方案,检验优化后路径的可行性。数值实验结果表明:通过Gurobi和算法分别求解小规模算例验证模型的准确性和算法的有效性;随着车辆最大可携带无人机数量的增加,优化率逐渐增加,但其边际效益是递减的;当货物平均尺寸增加到一定值时,货物平均尺寸的增大对越大客户数的算例的影响越大;随着无人机的最大载重和单次最大飞行距离的增加,无人机与车辆的总配送时间减少,但边际效益都是递减的。

关键词: 三维装箱, 无人机二级车辆路径, 混合算法