Abstract: Take-out delivery is an important part of takeout business, and the delivery cost and on-time delivery rate are the key factors to determine the quality of take-out delivery, so the research on the optimization of take-out delivery routing is particularly important. Based on an emerging drones and riders joint take-out delivery mode, a temporal-spatial distance measurement method is introduced to establish a routing optimization model for drone rider joint take-out delivery to minimize the cost of food delivery, and a two-stage heuristic algorithm is designed to solve the problem. In the first stage, the genetic algorithm combined with K-means is used to cluster customers and form the initial path of riders. In the second stage, the improved variable neighborhood search algorithm and A* algorithm are respectively used to optimize the path of riders and the flight path of drone food delivery. Finally, a case is designed and solved. The experimental results show that, compared with the traditional rider delivery mode, the drones and riders delivery mode considering the temporal-spatial distance can reduce the cost of food delivery and improve the on-time delivery rate.

Key words: take-out delivery, drone, temporal-spatial distance, routing optimization, variable neighborhood search

摘要： 外卖配送是外卖业务中的重要环节，而配送成本和准时送达率是决定外卖配送质量的关键因素，因而对外卖配送路径优化问题的研究尤为重要。基于无人机骑手联合外卖配送模式，引入时空距离度量方法，以最小化送餐成本为目标建立了无人机骑手联合外卖配送的路径优化模型，设计了一种两阶段启发式算法进行求解。第一阶段使用结合K-means的遗传算法对顾客聚类，形成骑手初始路径，第二阶段分别使用改进的变邻域搜索算法和A*算法优化骑手路径和无人机送餐航迹。实验结果表明，与传统骑手配送模式相比，考虑时空距离的无人机骑手联合外卖配送模式能减少送餐成本，提高准时送达率。

关键词: 外卖配送, 无人机, 时空距离, 路径优化, 变邻域搜索算法