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

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