时变路网下多中心电动车-无人机协同配送路径优化

Multi-depot electric vehicle routing problem with drones under time-dependent networks

针对车辆行驶时间依赖配送区域路网速度变化的多中心电动车-无人机协同配送路径问题,本文综合考虑配送区域路网交通信息,无人机最大飞行距离、承重能力,配送过程中电动车电池的荷电状态,以及车辆行驶速度、载重量等对电动车能耗的影响等,以总配送成本最小化为目标建立多中心车辆-无人机协同配送路径优化模型。根据问题特征,本文设计遗传大邻域搜索混合算法求解模型,该算法在传统遗传算法基础上,采用整数编码随机生成初始种群,通过无人机最大承重能力、飞行距离筛选无人机可服务的客户,然后确定车辆及无人机的配送路径生成初始解,并嵌入2组摧毁和重建算子进行进化操作。本文通过多组算例验证了算法及模型的有效性,并分析了车辆搭载的无人机数量以及车辆行驶速度对配送方案制定的影响。研究成果丰富和拓展了车辆路径优化的研究领域,可为交通、物流企业优化决策配送方案提供理论依据。

With environmental strategies employed for reducing carbon emissions, the future development trend of electric-vehicle utilisation can gradually lead to fuel-vehicle replacement. Due to the limitation of the cruising range, power must be replenished by charging or replacing batteries during the delivery process to complete delivery, which requires a low delivery efficiency and high costs.The delivery efficiency of drones is high, and their cost is low;however, their weight-bearing capacity and flight mileage are low and short, respectively. Moreover, long-distance and multi-customer deliveries cannot be completed by using only drones. To reduce delivery costs and improve the delivery efficiency of logistics enterprises with multiple depots in a delivery area, this paper proposes a multi-depot electric vehicle routing problem with drones under time-dependent networks. The vehicle leaves the depot and carries multiple drones. When the vehicle arrives at a customer, it can provide services to the customer while flying the drones to other customers. The vehicle can wait for the drone to complete the specified task at the current node to return to the vehicle or visit subsequent customers. After the drone completes the delivery task, it returns to the vehicle at the subsequent node. When the delivery task is completed, the vehicle returns to the nearest depot. During delivery, the vehicle is jointly distributed with the drone and serves as a temporary warehouse, apron, and a charging and replacement platform for the drone.To overcome the problem specified in this paper and to comprehensively consider the delivery area road network traffic information, maximum flight distance and load capacity of drones, state of charge of electric vehicle batteries, and influence of factors such as travel speed and load capacity on the energy consumption of electric vehicles, an optimisation model was formulated for the multi-depot electric vehicle routing problem with drones fulfilling the goal of minimising delivery costs. This model optimises vehicle and drone routing in a multi-depot network. Because the proposed problem involves the characteristics of multi-depot and electric vehicle routing problem with drones, the problem-solving process is complex. Solving the problem with an accurate algorithm is difficult. Therefore, according to problem characteristics, a hybrid genetic algorithm with large neighbourhood search(GA_LNS) was proposed to solve the mathematical model. Based on the traditional genetic algorithm, the initial population was randomly generated using integer coding. The customers, which the drone could serve, were screened using the maximum loading capacity and flight distance of the drone. Then, the routes of vehicles and drones were determined to obtain the initial solution. Moreover, two groups of destruction and repair operators were employed for evolutionary operations. Currently, there is no benchmark instance of this problem,and determining the vehicle route is the key to solve the proposed problem. Therefore, this study first selected multi-depot vehicle routing problem to test the solution performance of the proposed algorithm. Subsequently, a problem example was designed to solve it,and the impacts of the number of drones carried by the vehicle and the speed of the vehicle on delivery scheme formulation were analysed.The following conclusions were obtained. First, the model considers the delivery area road network traffic information as well as the maximum flight distance and load capacity of the drone. Although the model further complicates the problem, making it difficult to solve;the model is close to the reality of delivery production activities and expands and deepens vehicle routing problem research. In addition, based on the traditional genetic algorithm, two groups of destruction and repair operators are embedded to design GA_LNS,where customer points are purposefully removed and inserted, which can solve low-efficiency and time-consumption problems, ensure solution quality, and improve the convergence speed of the algorithm. Finally, according to sensitivity analyses for determining the effect of the number of drones carried by the vehicle and vehicle speed on delivery plan formulation, the use of coordinated delivery of vehicles and drones can considerably reduce the delivery cost and delivery time. Different vehicle speeds substantially affect the formulation of delivery plans and delivery costs. Reasonably restricting the vehicle speed during delivery can effectively reduce the delivery costs. Our results can enrich and expand the research of vehicle-routing problems and provide a theoretical basis for transportation and logistics enterprises to optimise their decision-making delivery schemes.