下载文档原格式
2021⁃02⁃10计算机应用,Journal of Computer Applications 2021,41(2):390-397ISSN 1001⁃9081CODEN JYIIDU http ：//基于改进遗传算法的无人机路径规划黄书召1*，田军委2，乔路2，王沁2，苏宇2（1.西安工业大学电子信息工程学院，西安710021；2.西安工业大学机电工程学院，西安710021）（∗通信作者1945980733@ ）摘要：针对传统遗传算法收敛速度慢、容易陷入局部最优、规划路径不够平滑、代价高等问题，提出了一种基于改进遗传算法的无人机（UAV ）路径规划方法，该算法对遗传算法的选择算子、交叉算子和变异算子进行改进，从而规划出平滑、可飞的路径。
首先，建立适合UAV 田间信息获取的环境模型，并考虑UAV 的目标函数与约束条件以建立适合本场景的更为复杂、精确的数学模型；然后，提出了混合无重串选择算子、非对称映射交叉算子和启发式多次变异算子，寻找最优路径以及扩大种群搜索范围；最后，采用三次B 样条曲线对规划出的路径进行平滑，得到平滑的飞行路径，并且减少了算法的计算时间。
实验结果表明，与传统遗传算法相比，所提算法的代价值降低了68%，收敛迭代次数减少了67%；相较蚁群优化（ACO ）算法，其代价值降低了55%，收敛迭代次数减少了58%。
通过大量对比实验得出，当交叉率的值为（1/染色体长度）时，算法的收敛效果最好。
在不同环境下进行算法性能测试，结果表明所提算法具有很好的环境适应性，适合于复杂环境下的路径规划。
关键词：遗传算法；无人机；交叉算子；B 样条曲线；路径规划中图分类号：TP181；TP13文献标志码：AUnmanned aerial vehicle path planning based on improved genetic algorithmHUANG Shuzhao 1*，TIAN Junwei 2，QIAO Lu 2，WANG Qin 2，SU Yu 2（1.School of Electronic Information Engineering ，Xi ’an Technological University ，Xi ’an Shaanxi 710021，China ；2.School of Mechatronic Engineering ，Xi ’an Technological University ，Xi ’an Shaanxi 710021，China ）Abstract:In order to solve the problems such as slow convergence speed ，falling into local optimum easily ，unsmoothplanning path and high cost of traditional genetic algorithm ，an Unmanned Aerial Vehicle （UAV ）path planning method based on improved Genetic Algorithm （GA ）was proposed.The selection operator ，crossover operator and mutation operator of genetic algorithm were improved to planning a smooth and effective flight path.Firstly ，an environment model suitable forthe field information acquisition of UAV was established ，and a more complex and accurate mathematical model suitable for this scene was established by considering the objective function and constraints of UAV.Secondly ，the hybrid non -multi -string selection operator ，asymmetric mapping crossover operator and heuristic multi -mutation operator were proposed to find the optimal path and expand the search range of the population.Finally ，a cubic B -spline curve was used to smooth the planned path to obtain a smooth flight path and reduce the calculation time of the algorithm.Experimental results show that ，compared with the traditional GA ，the cost value of the proposed algorithm was reduced by 68%，and the number of convergence iterations was reduced by 67%；compared with the Ant Colony Optimization （ACO ）algorithm ，its cost value was reduced by 55%and the number of convergence iterations was reduced by 58%.Through a large number of comparison experiments ，it is concluded that when the value of the crossover rate is the reciprocal of chromosome size ，the proposed algorithm has the best convergence effect.After testing the algorithm performance in different environments ，it can be seenthat the proposed algorithm has good environmental adaptability and is suitable for path planning in complex environments.Key words:genetic algorithm;Unmanned Aerial Vehicle (UAV);crossover operator;B -spline curve;path planning 0引言近年来，受益于轻型高分子材料的发现以及嵌入式、自动化、信号处理、无线通信等技术的发展与成熟，无人机（Unmanned Aerial Vehicle,UAV)在田间信息获取、农业植保、设施巡检、物流配送［1-2］等场景中广受青睐。
基于遗传算法的无人机航线规划优化研究无人机技术的飞速发展，使得无人机的应用场景越来越广泛。
然而，无人机的飞行路径规划是个重要的问题，因为它关系到无人机飞行的安全、稳定和效率。
在这个问题上，遗传算法是一种可行的解决方案。
遗传算法是基于自然界进化规律的一种计算方法，它模拟了自然选择、基因交叉、突变等过程，能够搜索解空间中的最优解。
基于遗传算法的无人机航线规划优化研究，旨在设计出一套优秀的遗传算法，以便在航线规划中产生优化的策略和路径。
在进行基于遗传算法的无人机航线规划优化研究时，需要先了解问题背景和目标。
这类问题背景具有复杂、不确定、多目标和多约束等特点。
例如，要规划无人机的航线，需要定义好起点、终点和避障点，同时还需要考虑各种约束条件，如速度、高度、能量等，这些条件可能互相作用，相互制约，而且需要实时调整。
因此，在基于遗传算法的无人机航线规划优化研究中，需要根据具体的应用场景和问题情况，制定出相应的适应度函数，从而能够方便地衡量不同航迹生成的优劣情况。
适应度函数的设计与权重的确定是很关键的步骤，不仅需要考虑问题与目标之间的关系，还要兼顾航迹的实用性和计算量。
具体来说，基于遗传算法的无人机航线规划优化研究需要进行以下步骤：1. 定义问题及约束条件。
明确问题的具体背景、需求和要求，并列出所有的约束条件，例如起点和终点、飞行高度和能量消耗等。
如果问题不是典型的发现型问题，可能需要事先进行建模和仿真。
2. 制定遗传算法的流程和遗传算子。
根据问题和约束条件，确定所需的遗传算子，如选择算子、交叉算子和突变算子等。
同时制定遗传算法的基本流程，包括种群初始化、适应度函数计算、选择、交叉、突变及后处理等环节。
3. 设计适应度函数。
基于问题和约束条件，设计适应度函数，并确定适应度函数的权重。
初始的适应度函数可能存在问题，需要经过多次迭代和调整，才能够得到合适的结果。
通常，设计适应度函数是遗传算法的最重要部分，可以反映一个人对问题深度理解的程度。
T互联网+通信Internet Communication3C融合的空天地海一体化通信系统设计与实现文丨韩笑雪王万龙孙尚毛文梁翟益平【摘要】综合考虑物理环境域、社群交互域以及内容资源域，在空天地海一体化网络中，利用多元化终端设备，例如舰艇、无人机、车辆，结合卫星通信技术，实现多元化业务的安全、高效、低时延的传输、存储及计算的协同优化是当前研究重点。
本文考虑天地海一体化通信需求中通信一计算一缓存（3C）协同优化场景提出了一个高可靠的通信系统架构，并利用SDN、机器学习（ML）、边缘计算技术等技术进行了实现，实验结果表明了该架构的可行性。
【关键字】3C融合空天地海协同通信通信系统分布式架构一、介绍作为5G通信技术发展的一个重要方向，层次化云服务的异构云无线接入网络不仅可以满足无线业务对高速计算或大容量存储等服务的要求，还可以扩展通信覆盖范围，增加传输速率，降低传输时延，提高网络容量和用户服务质量。
欧洲电信标准化协会在5G 标准中提岀了多接入边缘计算（MEC）的解决方案，MEC通过在移动网络边缘部署大量的分布式边缘服务器，对网络边缘侧产生的大量数据进行分析、计算与存储，达到降低回程链路流量、缓解核心网拥堵的目的。
近年来，大计算任务处理问题突出，计算卸载/迁移是一个非常有效的手段，其过程极为复杂，需首先判断是否要进行计算任务的卸载/迁移，然后针对要进行卸载/迁移的计算任务确定需要卸载/迁移的比例。
川对于单个任务请求节点，利用…维搜索算法综合考虑了计算应用的缓存队列状态、用户节点计算资源的可用情况，在不考虑能耗的前提下最小化卸载/迁移机制所产生的时延。
然而在空天地海一体化网络中，由于不同设备、用户节点具有不同的物理特征以及通信一存储一计算（3C）能力，例如卫星、舰艇、车辆等具有强算力，而人员所携带设备所具备的存储和算力较小。
因此，如何面向空天地海一体化网络中的多样化业务需求，结合卫星通信技术，设计高效3C协同一体化方案，以满足海量连接、低时延、高可靠的通信技术.仍然是亟待解决的问题。
《基于无人机摄影测量和深度学习的公路边坡病害研究》一、引言随着科技的不断进步，无人机（Drone）技术以及深度学习算法在各个领域得到了广泛应用。
公路边坡病害的检测与评估是公路维护管理中的重要环节，其准确性和效率直接影响到公路的安全运营和维修决策。
本文旨在探讨基于无人机摄影测量和深度学习的公路边坡病害研究，以提高公路边坡病害检测的准确性和效率。
二、无人机摄影测量技术无人机摄影测量技术是一种基于无人机的遥感技术，通过搭载高清摄像头等设备，实现对目标区域的快速、高效、准确的拍摄。
在公路边坡病害检测中，无人机摄影测量技术具有以下优势：1. 高效率：无人机可以快速飞越目标区域，实现大范围、高精度的拍摄。
2. 高清度：高清摄像头可以获取高分辨率的图像，为后续的图像处理和分析提供基础。
3. 灵活性：无人机可以根据实际需求调整拍摄角度和高度，获取不同视角的图像。
三、深度学习算法在公路边坡病害检测中的应用深度学习算法是一种基于人工神经网络的机器学习算法，具有强大的特征学习和模式识别能力。
在公路边坡病害检测中，深度学习算法可以实现对图像的自动分析和识别，提高检测的准确性和效率。
常见的深度学习模型包括卷积神经网络（CNN）、循环神经网络（RNN）等。
在公路边坡病害检测中，深度学习算法可以实现对图像中的裂缝、滑坡、塌方等病害的自动识别和分类。
通过训练大量的图像数据，深度学习模型可以学习到各种病害的特征和模式，从而实现高精度的识别和分类。
此外，深度学习算法还可以实现对图像中的多尺度、多角度、多时相等复杂信息的处理和分析，为公路边坡病害的全面检测和评估提供有力支持。
四、基于无人机摄影测量和深度学习的公路边坡病害研究基于无人机摄影测量和深度学习的公路边坡病害研究，是将无人机摄影测量技术和深度学习算法相结合，实现对公路边坡病害的高效、准确检测。
具体流程如下：1. 数据采集：利用无人机搭载高清摄像头等设备，对公路边坡进行快速、高效的拍摄，获取高分辨率的图像数据。
展路线图”，如陆军《美陆军无人飞行器系统路线图（2010—2035）》、空军的《美空军无人机计划（2009—2047）》《美空军无人机系统发展路线图（2013—2038）》《小型无人机系统飞行计划（2016—2036）》、海军与海军陆战队联合发布的《无人作战框架》、海军的《智能自主系统科技战略》等。
无人作战力量编制规模扩增。
早在2002年3月，美空军就成立了世界上第一个无人攻击机中队，将无人作战力量编制成独立单位。
随着无人装备发展以及着眼作战任务需要，美军不断地优化作战力量结构，增加无人作战系统，提高无人作战力量的编制比例。
据资料显示，截至2013年底，美军空中作战司令部编无人机联队1个、无人机飞行中队7个、无人机训练中队3个，空军国民警卫队编无人机联队1个、无人机飞行中队4个，空军特种作战司令部编无人机中队3个，海军编无人机中队2个，海军陆战队编无人机中队3个。
截至2015年初，已在陆军步兵战斗旅、斯特赖克战斗旅、重型战斗旅下的工兵营中编有1个近程战术无人机排，火力旅下编有1个战术无人机连，师属航空战斗旅下编有1个灰鹰无人机连，第160特种作战航空团编有2个灰鹰无人机连，国家训练中心编有1个灰鹰无人机连。
2017年9月组建了第一个独立的水下无人潜航器中队——UU V RON1，配备各类无人潜航器随舰执行ISR、反水雷和协助反潜等任务。
2020年10月1日，海军又成立第一个舰载无人加油机中队。
拟在2023年夏末前，建立有史以来首支水面无人舰队。
2023年3月7日，美空军部长弗兰克·肯德尔在美国航空航天大会上披露未来美空军战斗机部队将由1000架高度自主的先进无人机、200架下一代空中优势隐形战斗机（NG A D）和300架F-35隐形战斗机组成。
海军陆战队计划2030年左右在团下建立机器人（无人战车）营，并设想无人作战平台分别占到100%、36%～75%、35%以下三种比例的编配模式。
无人机航迹规划中的POMDP问题求解无人机飞行已经成为了现代化社会中各个领域的必要手段。
无人机航迹规划对于保证无人机的安全飞行至关重要。
然而，在实际应用中，无人机航迹规划面临着复杂的环境和情况，传统方法可能难以满足实际需求。
因此，POMDP方法可以作为一种有效的解决方案。
什么是POMDP方法？POMDP是部分可观测的马尔可夫决策过程的英文缩写，指的是当问题存在不确定性的时候，我们可以使用马尔科夫决策过程来建模，以这种方式来利用概率和规划算法来制定最优策略。
在实际应用中，可以通过实时监测和更新环境以及传感器设备来解决不确定性。
POMDP方法在无人机航迹规划中的应用POMDP方法可以应用在无人机的航迹规划中，其主要依靠传感器信息来监控和更新无人机所处的环境信息，以此推断出最优航迹方案。
POMDP方法允许无人机选择最优决策。
为了实现这一目标，无人机需要计算折扣回报值。
然而，在实际应用中，无人机模型被设计为知道其下一步行动的结果，但是它却无法知道未来的情况，这些未知的情况可能会对其下一步行动的结果产生深刻的影响。
因此，当选择无人机航迹时，必须考虑当前环境下的不确定性因素，以避免出现不利的情况。
POMDP求解方法求解POMDP问题最常用的方法是基于值迭代的方案。
基于值迭代的问题解决方案是通过计算每个状态下下一次行动的期望值，然后继续对回报进行迭代，直到找到最优策略。
这种方案虽然计算量大，但可靠，因此常用于实际情况中。
此外，对于某些需要快速求解的问题，可以使用基于策略的求解方法。
基于策略的方法与基于值迭代的方法相比，需要更少的计算时间，因此可以用来求解实时问题。
POMDP方法的应用前景无人机的快速发展推动了人们对其安全问题的认识。
POMDP方法在保证无人机安全飞行方面发挥了重要作用。
未来，无人机技术将会得到更广泛的应用，从而需要更加先进的航迹规划方法来指导其飞行。
POMDP方法在无人机航迹规划中的应用前景广阔。
基于多Agent无人机协同侦察任务规划模型褚政;郭分林;粘松雷【摘要】This paper views programming model of UAV cooperative reconnaissance mission. In the conside of reconnaissance time interval and target load requirement, the paper decipts optimization deployment and attemper tactic of the different base�s UAV, and decipts multi⁃agent based simulation arithmetic of optimization search. The paper realizesde⁃ployment and mission programming model of UAV, and figures out the model�s outcome. The paper analyses some shortages of the model and arithmetic, and puts forward the betterment�s directions of the model lastly.%建立了多无人机协同侦察任务规划模型，在考虑侦察时间间隔约束和目标载荷需求基础上，给出了位于不同基地的无人机优化部署和调度策略，并提出了基于多Agent的优化搜索仿真算法，利用Matlab实现了无人机优化配置和任务规划模型，得出了无人机优化配置和任务规划方案，最后分析了模型算法存在的某些不足，提出了模型改进的方向。
【期刊名称】《指挥控制与仿真》【年(卷),期】2016(038)005【总页数】7页(P21-27)【关键词】无人机;多Agent;协同侦察;任务规划;优化搜索【作者】褚政;郭分林;粘松雷【作者单位】海军航空工程学院，山东烟台 264001;南昌陆军学院，江西南昌330103;海军航空工程学院，山东烟台 264001【正文语种】中文【中图分类】E917;TP18无人机(Unmanned Aerial Vehicle,UAV)是一种具备自主飞行和独立执行任务能力的新型作战平台[1]。
第９卷 第４期Ｖｏｌ．９Ｎｏ．４ 智 能 计 算 机 与 应 用ＩｎｔｅｌｌｉｇｅｎｔＣｏｍｐｕｔｅｒａｎｄＡｐｐｌｉｃａｔｉｏｎｓ ２０１９年７月 Ｊｕｌ．２０１９
文章编号：２０９５－２１６３（２０１９）０４－００２７－０６中图分类号：ＴＰ１８文献标志码：Ａ
基于三支决策的无人机－车协同规划算法研究
刘委青，曲明成，吴翔虎（哈尔滨工业大学计算机科学与技术学院，哈尔滨１５０００１）
摘 要：随着物流车、无人机技术的逐渐成熟以及在运输中的出众表现，车辆与无人机协同作业的路径规划问题（ＶＲＰＵＡＶ）成为当前学术和工程界亟待解决的问题。本文基于车辆与无人机协同作业场景，将运输问题划分为三粒度，即“无人机数量为０”，“无人机数量不足”，“无人机数量充足”。采用蚁群算法和无人机物流车协同运输优化算法对３个子问题分别提出相应的解决策略；最后通过仿真实验证明了算法在行驶成本与时间成本上的优化作用，同时在运输物品总条件一定的前提下，三类子问题的治略方案均能够正确求解出优化解，且第２、３种场景较第１种，第３种场景较第２种具有更优运输成本和客户等待时间成本，充分证明了三粒度分治的合理和有效性。关键词：蚁群算法；三支决策；无人机物流车协同运输；多目标车辆路径问题ＲｅｓｅａｒｃｈｏｎＵＡＶ－Ｃａｒｃｏｌｌａｂｏｒａｔｉｖｅｐｌａｎｎｉｎｇａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｒｅｅ－ｗａｙｄｅｃｉｓｉｏｎｓ
ＬＩＵＷｅｉｑｉｎｇ，ＱＵＭｉｎｇｃｈｅｎｇ，ＷＵＸｉａｎｇｈｕ（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＨａｒｂｉｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ１５０００１，Ｃｈｉｎａ）
【Ａｂｓｔｒａｃｔ】Ｗｉｔｈｔｈｅｇｒａｄｕａｌｍａｔｕｒｉｔｙｏｆｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｓａｎｄｕｎｍａｎｎｅｄａｅｒｉａｌｖｅｈｉｃｌｅｔｅｃｈｎｏｌｏｇｙａｎｄｏｕｔｓｔａｎｄｉｎｇｐｅｒｆｏｒｍａｎｃｅｉｎｔｒａｎｓｐｏｒｔａｔｉｏｎ，ｔｈｅｒｏｕｔｅｐｌａｎｎｉｎｇｐｒｏｂｌｅｍ（ＶＲＰＵＡＶ）ｏｆｖｅｈｉｃｌｅｓａｎｄｄｒｏｎｅｓｃｏｏｐｅｒａｔｉｏｎｈａｓｂｅｃｏｍｅａｐｒｏｂｌｅｍｔｈａｔｎｅｅｄｓｔｏｂｅｓｏｌｖｅｄｉｎｔｈｅｃｕｒｒｅｎｔａｃａｄｅｍｉｃａｎｄｅｎｇｉｎｅｅｒｉｎｇｆｉｅｌｄｓ．Ｂａｓｅｄｏｎｔｈｅｃｏｌｌａｂｏｒａｔｉｖｅｏｐｅｒａｔｉｏｎｓｃｅｎａｒｉｏｏｆｖｅｈｉｃｌｅｓａｎｄｄｒｏｎｅｓ，ｔｈｅｐａｐｅｒｄｉｖｉｄｅｓｔｈｅｔｒａｎｓｐｏｒｔａｔｉｏｎｐｒｏｂｌｅｍｉｎｔｏｔｈｒｅｅｇｒａｎｕｌａｒｉｔｉｅｓ，ｎａｍｅｌｙ，“ｔｈｅｎｕｍｂｅｒｏｆｄｒｏｎｅｓｉｓ０”，“ｔｈｅｎｕｍｂｅｒｏｆｄｒｏｎｅｓｉｓｓｕｆｆｉｃｉｅｎｔ，”ａｎｄ“ｔｈｅｎｕｍｂｅｒｏｆｄｒｏｎｅｓｉｓｉｎｓｕｆｆｉｃｉｅｎｔ”，ａｎｄｕｓｅｓａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍａｎｄｔｈｅｃｏｏｐｅｒａｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｏｆｄｒｏｎｅａｎｄｕｎｍａｎｎｅｄｖｅｈｉｃｌｅｔｏｐｒｏｐｏｓｅｃｏｒｒｅｓｐｏｎｄｉｎｇｓｏｌｕｔｉｏｎｓｔｏｅａｃｈｏｆｔｈｅｔｈｒｅｅｓｕｂ－ｐｒｏｂｌｅｍｓ．Ｆｉｎａｌｌｙ，ｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｓａｒｅｃｏｎｄｕｃｔｅｄｔｏｖｅｒｉｆｙｔｈｅｏｐｔｉｍｉｚａｔｉｏｎｅｆｆｅｃｔｏｆｔｈｅａｌｇｏｒｉｔｈｍｏｎｄｒｉｖｉｎｇｃｏｓｔａｎｄｔｉｍｅｃｏｓｔ．Ｕｎｄｅｒａｃｅｒｔａｉｎｐｒｅｍｉｓｅ，ｔｈｅｇｏｖｅｒｎａｎｃｅｓｏｌｕｔｉｏｎｓｆｏｒｔｈｅｔｈｒｅｅｓｕｂ－ｐｒｏｂｌｅｍｓｃａｎｃｏｒｒｅｃｔｌｙｓｏｌｖｅｔｈｅｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ，ａｎｄｔｈｅｓｅｃｏｎｄａｎｄｔｈｉｒｄｓｃｅｎａｒｉｏｓｈａｖｅｂｅｔｔｅｒｔｒａｎｓｐｏｒｔａｔｉｏｎｃｏｓｔｓａｎｄｃｕｓｔｏｍｅｒｗａｉｔｉｎｇｔｉｍｅｔｈａｎｔｈｅｆｉｒｓｔａｎｄｔｈｉｒｄｓｃｅｎａｒｉｏｓｉｓａｌｓｏｂｅｔｔｅｒｔｈａｎｔｈｅｓｅｃｏｎｄｉｎｔｈｅｓｉｍｉｌａｒｖａｒｉａｂｌｅｓ．Ｔｈｅｃｏｓｔｈａｓｆｕｌｌｙｐｒｏｖｅｄｔｈｅｒｅａｓｏｎａｂｌｅｎｅｓｓａｎｄｅｆｆｅｃｔｉｖｅｎｅｓｓｏｆｔｈｅｔｈｒｅｅ－ｗａｙｄｅｃｉｓｉｏｎｓａｎｄｔｒｅａｔｍｅｎｔ．【Ｋｅｙｗｏｒｄｓ】ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；ｔｈｒｅｅ－ｗａｙｄｅｃｉｓｉｏｎｓ；ＵＡＶｌｏｇｉｓｔｉｃｓｖｅｈｉｃｌｅｃｏｏｒｄｉｎａｔｅｄｔｒａｎｓｐｏｒｔａｔｉｏｎ；ｍｕｌｔｉ－ｄｅｐｏｔｓｖｅｈｉｃｌｅ
ｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓ
哈尔滨工业大学主办学术研究与应用作者简介：刘委青（１９９６－），男，硕士研究生，主要研究方向：群组智能、无人机－车协同规划算法、群组智能；曲明成（１９８０－），男，博士，讲师，硕士生导师，主要研究方向：自动化软件工程、嵌入式计算；吴翔虎（１９６８－），男，博士，教授，ＣＣＦ高级会员，主要研究方向：嵌入式计算、操作系统、高可靠软件工程。收稿日期：２０１９－０５－３１
１ 研究概述１．１ 带无人机的车辆路径问题车辆路径问题（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＶＲＰ）是在现代物流配送领域具有重大研究意义的一类问题。目前来说，对于单车场车辆路径问题研究已然取得了较为可观的研究成果［１］。对于多车场车辆开放式车辆路径问题（Ｍｕｌｔｉ－ＤｅｐｏｒｔＯｐｅｎＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍ，ＭＤＯＶＲＰ）的研究也逐渐增多［２］。陈美军等人［３］提出了自适应的最大－最小蚁群算法来解决多约束下多车场车辆路径问题（Ｍｕｌｔｉ－ＤｅｐｏｔｓＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｗｉｔｈＭｕｌｔｉｐｌｅＣｏｎｓｔｒａｉｎｔｓ，ＭＤＶＲＰＭＣ），同时在车辆行驶路径长度方面进行了优化。而对于时间成本的优化，王征等人［４］提出的变邻域搜索算法取得了实质性的提高。曾正洋等人［５］在应急物流中的累计时间式多车场车辆路径问题中提出的多起始点变邻域下降快速求解方法对客户累积等待时间成本也起到了一定程度的优化作用。凌海峰等人［６］提出的结合Ｋ－ｍｅａｎｓ与细菌觅食算法改进的蚁群算法对带软时间窗的多车场开放式车辆调度问题（Ｍｕｌｔｉ－ＤｅｐｏｔＯｐｅｎＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｗｉｔｈＳｏｆｔＴｉｍｅＷｉｎｄｏｗｓ，ＭＤＯＶＲＰＳＴＷ）也
在相当程度上优化了算法效率。随着无人技术的日益发展，众多国内外物流公司已陆续开始将无人技术应用到运输行业中。亚马逊、谷歌等公司于业界最早提出研发无人机空管系统的计划，并于２０１６年利用无人机首次完成货物送达任务。而在２０１７年又领先提出利用地面车辆与空运无人机协同运输的货物运输方式［７］。然而随着无人驾驶技术日益发展和无人机在快递行业的拓展应用，此前对于车辆路径问题的求解方法也已显出一些不足，无人技术使得车辆路径问题有了更好的求解方法。但是经研究可知，目前学术界对于无人技术在车辆路径问题研究较少。其中，Ｌｕｏ等人［８］采用启发式优化算法对区域内单车载无人机与地面车辆执行巡航任务的路线问题提出了优化方法，Ｙｕ等人［９］利用单无人机与移动充电车辆协同配合解决了区域内点遍历任务的广义旅行商问题（ＧｅｎｅｒａｌｉｚｅｄＴｒａｖｅｌｉｎｇＳａｌｅｓｐｅｒｓｏｎＰｒｏｂｌｅｍ）模型向ＴＳＰ（ＴｒａｖｅｌｉｎｇＳａｌｅｓｐｅｒｓｏｎＰｒｏｂｌｅｍ）问题模型的转化。然而这些文献主要目标拟在实现对区域内点的访问任务研究，并没有考虑无人机的承载能力和货物运输能力。为此，本文提出了一种新的研究场景：利用无人机和物流车协同运输完成对区域内各点的货物送达任务，即带无人机的车辆路径问题（ＶｅｈｉｃｌｅＲｏｕｔｉｎｇＰｒｏｂｌｅｍｗｉｔｈＵｎｍａｎｎｅｄＡｅｒｉａｌＶｅｈｉｃｌｅ，ＶＲＰＵＡＶ）。并借鉴二级车辆路径问题的解决思路对ＶＲＰＶＡＶ问题提出了解决方法。１．２ 三支决策三支决策是由姚一豫教授提出的对于复杂问题求解典型方法之一［１０］。该方法的主要思想为“三分而治”，按照分治法将复杂问题转化为３个规模较小的问题，有针对性地解决３个小问题，从而提高决策质量，减少决策成本和降低决策时间。“三分”将全局“一”划分成“三”个独立的部分，即“一分为三”。“治略”针对各个部分开发相应的治理策略，以达到解决问题的成本最小化或利益最大化。在ＶＲＰＵＡＶ问题中，系统性能与无人机的运输能力密切相关，而无人机运输能力与天气、损坏情况密切相关。例如在天气较差，能见度较低时，无人机不能完成飞行任务。而当无人机损坏，或者定期保养时，会导致无人机数量不足。只有当天气正常，所有无人机均无损坏情况时，方可正常飞行。所以无人机运输能力同样也涉及到３个粒度的问题。本文中，在该领域首次提出基于三支决策理论解决无人机物流车协同运输的优化算法，结合三支决策的“三分而治”的基本思想，将无人机的运输能力作为分治的依据，将问题三分为“无人机数量为０”、“无人机数量充足”、“无人机存在且不足”三个子问题，针对这三个部分提出相应的治理策略实现等待时间成本和行驶成本的最小化。并通过实验数据证明了本文方法的有效性。对此拟展开研究论述如下。２ 带无人机协助运输的快件运输算法
２．１ ＶＲＰＵＡＶ问题描述本文的研究场景可以概括为：在仅有一个快件分发中心的区域中，对ｍ个快件收货点进行快递分发，且ｍ个快件收货点上需要送达的总重量不同；同时根据无人机的最大配送重量Ｋ将快件收货点划分为重件点和轻件点。其中，无人机可完成轻件点的快递送达，物流车可完成任意快件点的送达任务。对于各个快件点而言，均具备最晚送达时间的不同要求和超时惩罚系数ｐｕｎｉ
。每个快件点的时
间成本为其超时时长Ｔ∗ｐｕｎｉ
。物流车携带区域内
所有快件和ｎ（ｎ≥０）架无人机从快件分发中心出发，协同运输，以最小的行驶代价和最小的总时间成本，完成区域内所有快件点的送达任务。最后均回到快件分发中心。２．２ 求解过程
由于无人机有着最大配送半径的耐力限制，需要不断地往返于物流车进行充电，假设无人机可以直接更换电池后再次开始下一快件点的访问，且其时间忽略不计。这是一类二级车辆路径问题的变形，其中二级交通工具无人机的行驶路径是建立在物流车的行驶基础之上，因此借鉴二级车辆路径问题的求解思路，将区域内物流车和无人机行驶路径进行分层次求解。由于无人机飞行速度较快，以空间直线距离行驶，不受地面交通状态影响，且单位行驶成本远低于物流车，因此要充分发挥无人机的配送优势。并根据此原则，依据无人机的数量，采用三支决策的主要思想，将问题整体分为３个部分，而且根据三分的结果，有针对性地设计策略和动作，达到成本的最小化。在本文中，由于无人机数量不同时，需要采取不同的处理策略，因此研究将无人机数量作为分治的依据。将问题划分为“无人机数量为０”、“无人机数量充足”、“无人机数量存在且不足”，并采用不同的策略进行解决，以达到行驶成本和时间成本的最小化。问题分治求解流程如图１所示。对以上３个子部分的处理策略可做阐释分述如下。
