Abstract: In order to solve the problem of the optimal path and shortest delivery time for truck-drone collaborative distribution in flooded areas with waterlogged obstacle zones, an integer programming model is established and a two-stage heuristic algorithm is proposed. The first phase grids the waterlogged obstacle areas in two dimensions and determines the safe waiting points for trucks when drones are transporting relief supplies and the collection of drone-delivery customers at each waiting point. In the second stage, a stage planning algorithm is proposed, which combines an improved A-star algorithm with a simulated annealing whale algorithm with a nonlinear convergence factor to optimize the delivery route of freight cars bypassing the stagnant area. This algorithm combines the global search optimality of the A-star algorithm with the local search accuracy of the whale algorithm, ensuring the safety of truck driving. It solves the problem of distributing disaster relief supplies in waterlogged areas. Finally, an example shows that this method can quickly and safely solve the problem of obstacle avoidance and disaster relief materials distribution in flood disasters.

Key words: disaster relief material avoidance distribution, truck-drone collaboration, two-stage heuristic algorithm, improved [k]-means algorithm, simulated annealing whale algorithm

摘要： 针对洪涝灾害中存在积水障碍区的卡车-无人机协同配送的最优路径及最短配送时间问题，建立了一种整数规划模型，并提出了一种两阶段启发式算法，第一阶段将积水障碍区进行二维网格化处理并确定无人机运输救灾物资时卡车的安全等待点以及各等待点无人机运送客户的集合，第二阶段提出阶段性规划算法，结合改进A*算法与非线性收敛因子的模拟退火鲸鱼算法对卡车绕积水障碍区的配送路径进行优化，在确保卡车行使安全的前提下，将A*算法的全局寻优性及鲸鱼算法的局部搜索精确性结合。解决存在积水障碍区的救灾物资配送问题，最后通过实例验证了所提出方法可以快速安全地解决洪涝灾害中救灾物资的避障配送问题。

关键词: 救灾物资避障配送, 卡车-无人机协同, 两阶段启发式算法, 改进[k]-means算法, 模拟退火鲸鱼算法