关键词: 众包配送, 无人机-卡车协同, 车辆路径问题, 分支定价算法

Abstract: Although online retail has been growing consistently in rural areas, it has issues with costs and delivery efficiency because of poor road infrastructure and scattered population. Moreover, in western rural areas, there are mainly plateaus and mountains. Thus, it is difficult for a truck to provide door-to-door delivery service. As drones are not restricted by road infrastructure, logistics companies, such as JD and ZTO, have used drones for delivery in rural areas. However, drones have limited capabilities and flight range. Hence, trucks carrying drones for collaborative delivery have been used in real-world logistics applications. In addition, logistics companies or local governments introduce crowdsourced delivery systems where ordinary people carry out last-mile deliveries with their own trucks to reduce delivery costs. For example, the logistic service platform, “Cun Ge Huo Di”, developed by the county of Xiushan, in the city of Chongqing, uses crowdsourced vehicles to deliver goods for a fee in rural areas.
Motivated by the above real-life logistics applications in rural areas, we introduce a new variant of the vehicle routing problem, namely, Vehicle Routing Problem with Drones and Crowd-shipping (VRPDC). The contributions of this study are as follows: (1)we propose VRPDC based on the practical delivery applications in rural areas. Compared with the classical VRP, VRPDC integrates more practical requirements, such as capacity restrictions and synchronization constraints for enterprise-owned trucks, crowdsourced trucks, and drones; (2)we formulate VRPDC as an integer linear programming model. Then, we decompose it into a path-based Master problem (MP) model and a pricing Sub-Problem (SP) model based on Danzig-Wolfe decomposition; (3)we propose an exact solution technique, a Branch-and-Price (BP) algorithm. New labeling extension and domination rules for drone-truck paths and crowdsourced trucks are introduced, respectively. Heuristic pricing techniques are developed to speed up the proposed algorithm for the label extension of drone and truck paths. Also, a unique acceleration strategy for crowdsourced trucks is proposed. Thus, the proposed algorithm can solve VRPDC optimally within a reasonable time.
To examine the performance of the proposed branch-and-price algorithm, a large number of experiments are implemented with Python 3.9, where small-scale and large-scale instances are randomly generated based on the instance generation rules proposed by existing studies. The exact solver, Gurobi, and a heuristic algorithm—Adaptive Large Neighborhood Search (ALNS) are used for comparison. In addition, to investigate the performance of the proposed heuristic pricing techniques and acceleration strategy for SPs, experiments are made for comparisons. The results show that the proposed BP performs the best in terms of solution quality and computation time for all instances. Also, the proposed heuristic pricing technique and acceleration strategy are effective. Finally, to examine the impact of introducing crowdsourced vehicles on the total cost of the delivery system, instances of different scales are randomly selected for experiments. Comparisons are made between the drone-truck delivery system with crowdsourced vehicles and one without them. The results show that using crowdsourced vehicles for delivery helps reduce logistics costs. More real-life requirements will be considered in our future work, such as heterogeneous drones and trucks, dynamic demand, the energy consumption of drones, and weather effects.

Key words: crowd-shipping, drone-truck, vehicle routing problem, branch-and-price algorithm