装卸一体的无人机配送线路和航迹双层协同规划模型

    A bi-level cooperative planning model of UAV distribution routes and Trajectories with integrated loading and unloading

    • 摘要: 无人机航迹是无人机配送线路的基础,两者相互影响,局部最优未必整体最优,其协同规化问题引起国内外学者的广泛关注。在GIS栅格化基础上,考虑客户需求的多样性,根据调度中心、客户、障碍物和高空坠落代价的单元格位置空间分布,建立装卸一体的无人机配送线路和航迹双层协同规划模型,寻求无人机航迹和机队调度成本之间的最佳耦合关系。根据问题特征,设计求解该问题的嵌入A*算法的Q-Learning两阶段算法,在第1阶段利用Q-Learning完成订单分配的基础上构建无人机配送线路,在第2段将A*算法嵌入寻找无人机访问任意两点之间航迹,通过两阶段算法交互分别求解双层规划模型的解。最后,结合真实案例,计算最优调度方案,分析模型参数的灵敏度,并对比启发式算法和本算法的求解性能,从而验证模型和算法的有效性。

       

      Abstract: UAV trajectories are the foundation of UAV distribution route planning. The two are interdependent, where local optimization does not necessarily guarantee global optimization. A bi-level cooperative planning model of UAV distribution routes and trajectories with integrated loading and unloading is established based on GIS rasterization and considering the diversity of customer demand. The model aims to find the optimal coupling relationship between UAV trajectories and fleet scheduling cost considering the spatial distribution of scheduling centers, customers, obstacles and high fall-cost cells. According to the characteristics of the problem, a bi-level Q-Learning algorithm embedded with A* algorithm is designed to solve the problem. At the first level, Q-Learning is used to complete the order distribution and generate UAV distribution routes. At the second level, A* algorithm is embedded to find trajectories between any two points visited by UAVs. The solution of the bi-level model is obtained by the proposed algorithm. Finally, a real case is used to verify the effectiveness of the model and algorithm, by calculating the optimal scheduling plan, analyzing parameter sensitivity, and comparing the solving performance between heuristic algorithms and the proposed algorithm.

       

    /

    返回文章
    返回