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

摘要： 针对农村配送存在道路条件较差、配送成本高等问题,考虑到无人机配送不受道路条件限制,但飞行能力有限,物流企业开始尝试采用卡车搭载无人机进行农村地区的配送。为进一步降低配送成本,盘活农村闲置运力,地方政府引入众包模式。因此,本文提出众包车辆和无人机与卡车混合配送的车辆路径问题,构建了该问题的0-1整数规划模型和集合划分模型,并根据问题特征,设计了改进的分支定价算法求解。通过与Gurobi和已有启发式算法的对比,验证了模型和算法的正确性和有效性,并就众包模式对成本的影响提出了相应的管理建议。

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