计算机科学与探索

作者：朱烨娜, 刘敏, 赵肄江, 陈萱霖

单位：1. 湖南科技大学 计算机科学与工程学院，湖南 湘潭 4112012. 服务计算与软件服务新技术湖南省重点实验室，湖南 湘潭 411201

关键词：无人机卡车协同配送,带无人机的旅行商问题,混合遗传算法,多臂赌博机

基金：国家自然科学基金（62372168, 62107013）；教育部人文社会科学研究规划基金项目（24YJAZH237）；湖南省教育厅科学研究重点项目（22A0341）。

无人机与卡车协同配送新模式凭借其高效、环保、不受地形限制等优势，正在改变传统的物流配送方式。带无人机的旅行商问题（TSP-D）是上述配送新模式中的一种经典问题，比纯卡车物流配送更为复杂，需要从无人机和卡车间的协同交互中寻找最优的配送组合，带来了新的挑战。提出了一种基于多臂赌博机的混合遗传算法来求解TSP-D。采用了自然数排列的染色体编码，并应用基于动态规划的精确划分方法对其解码，以生成无人机与卡车协同配送解方案。新设计了一种多臂赌博机局部搜索策略,将局部搜索算子池中的五种不同搜索算子视作赌博机的多个“臂”。先通过赌博机摇臂搜索后解方案适应值的提升程度来计算奖励，再根据[ε]-greedy强化学习方法计算各个“臂”被选中的概率，以便选择合适的搜索算子来增强算法的局部搜索能力。实验结果表明，提出的算法与其他主流的算法相比，在不同分布与不同规模的多数测试实例上均有更低的解方案成本。进一步的实验分析验证了多臂赌博机局部搜索策略比其他局部搜索策略具有更好的自适应能力，能显著提升算法的性能。最后，将提出的算法应用于长沙市一个实际的配送案例，展示了其现实应用效果。

来源：2025年第8期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2025年第8期