基于强化学习协同进化算法的低空载人调度方法

崔世亚 ,  刘强 ,  刘辉 ,  廖峻晨 ,  薛轲奕

科学技术与工程 ›› 2026, Vol. 26 ›› Issue (31) :13689-13699

PDF (7021KB)
科学技术与工程 ›› 2026, Vol. 26 ›› Issue (31) :13689-13699 DOI: 10.12404/j.issn.1671-1815.2600018
论文:航空、航天

基于强化学习协同进化算法的低空载人调度方法

作者信息 +

Low-altitude Manned Scheduling Method Based on Reinforcement Learning Co-evolutionary Algorithm

Author information +
文章历史 +

摘要

电动垂直起降航空器(electric vertical take-off and landing,eVTOL)的高效调度是低空交通高质量发展的关键,为解决当前低空调度研究中存在的约束模型构建不全面、传统算法易陷入局部最优问题,开展了管制低空场景下以能耗和延误为优化目标的多目标调度方法研究。首先,基于任务时空、资源分配、序列关系和冲突避免等多维度约束构建了eVTOL调度模型。其次,提出了一种融合强化学习与禁忌搜索的改进多目标遗传算法求解该模型,通过任务串预处理策略降低问题复杂度,引入基于Q-learning的参数自适应策略动态调整交叉与变异率,同时设计基于关键任务串的局部禁忌搜索策略以增强算法跳出局部最优的能力。最后,构建仿真场景,通过实验验证了关键策略的有效性与算法整体的有效性,相较于传统NSGA-Ⅱ算法在反世代距离与超体积指标上分别取得了36.2%与25.6%的提升。研究成果可为低空交通调度系统的优化设计提供参考。

Abstract

Efficient scheduling of electric vertical take-off and landing (eVTOL) aircraft is regarded as the key to high-quality low-altitude traffic. However, incomplete constraint models are found in current scheduling research. Additionally, local optima issues are easily encountered by traditional algorithms. Therefore, a multi-objective scheduling method regarding energy consumption and delay was investigated for controlled low-altitude scenarios. First, an eVTOL scheduling model was constructed. Multi-dimensional constraints were included, such as task spatio-temporal factors, resource allocation, sequence relationships, and conflict avoidance. Second, an improved multi-objective genetic algorithm was proposed. Reinforcement learning and Tabu search were integrated into the algorithm. The problem complexity was reduced by a task string preprocessing strategy. A parameter adaptive strategy based on Q-learning was introduced to adjust crossover and mutation rates dynamically. Meanwhile, a local Tabu search strategy based on critical task strings was designed. The ability to escape local optima was enhanced by this strategy. Finally, simulation scenarios were constructed. The effectiveness of the key strategies and the overall algorithm is verified through experiments. Compared with the traditional NSGA-Ⅱ algorithm, an improvement of 36.2% is achieved in the inverted generational distance (IGD) metric. Additionally, an improvement of 25.6% is obtained in the hypervolume (HV) metric. A reference is provided by these research results for the optimization of low-altitude traffic scheduling systems.

Graphical abstract

关键词

低空交通 / 遗传算法 / 强化学习 / eVTOL调度 / 多目标优化

Key words

low-altitude air traffic / genetic algorithm / reinforcement learning / eVTOL scheduling / multi-objective optimization

引用本文

引用格式 ▾
崔世亚, 刘强, 刘辉, 廖峻晨, 薛轲奕. 基于强化学习协同进化算法的低空载人调度方法[J]. 科学技术与工程, 2026, 26(31): 13689-13699 DOI:10.12404/j.issn.1671-1815.2600018
CUI Shi-ya, LIU Qiang, LIU Hui, LIAO Jun-chen, XUE Ke-yi. Low-altitude Manned Scheduling Method Based on Reinforcement Learning Co-evolutionary Algorithm[J]. Science Technology and Engineering, 2026, 26(31): 13689-13699 DOI:10.12404/j.issn.1671-1815.2600018

登录浏览全文

4963

注册一个新账户 忘记密码

随着全球城市化进程的不断加速,传统地面交通系统日益饱和,构建城市空中交通(urban air mobility, UAM)体系,已成为实现城市交通立体化、提升整体运行效率的关键战略方向[1]。在经济发达地区,低空载人交通已进入由研发向商业化落地的过渡期。以粤港澳大湾区为例,深圳市出台了全国首部低空经济产业促进条例,并建设低空智能融合系统(smart integrated lower airspace system,SILAS)以支撑高密度飞行;广州市则依托广州南站等交通枢纽,积极探索“枢纽-枢纽”间的空地联运模式,培育了亿航、小鹏汇天等具备先发优势的头部企业,其载人飞行器已率先进入适航审定与商业化试运营阶段。与此同时,以上海、合肥为代表的长三角地区也在积极布局,通过峰飞等企业实现跨海跨城航线首飞,并开辟了多条电动垂直起降飞行器(electric vertical take-off and landing,eVTOL)商业试航线。然而,随着航线密度的增加和运行规模的扩大,现有的空中交通管理系统主要为传统民航设计,难以适应UAM高密度、网络化的运行需求;而地面物流领域的调度算法虽有借鉴意义[2],却未能充分考虑空域的三维特性、飞行器的能量模型[3]以及安全间隔等关键航空因素。因此,如何为城市eVTOL设计智能调度策略,已成为UAM领域一个亟待解决的关键问题。
目前,国内外学者对低空交通调度问题进行了广泛研究。机器学习与强化学习为解决该复杂问题提供了思路。Pang等[4]针对飞机着陆调度问题,提出融合机器学习的优化方法,用梯度提升机预测相关时间并纳入旅行商问题求解。Paul等[5]将城市空中交通机队调度问题建模为图空间上的马尔可夫决策过程,设计基于图神经网络和多头注意力机制的策略网络,利用近端策略优化算法训练。Murthy等[6]提出一种多智能体强化学习方法,通过动态调整飞行高度来实时管理空中交通,以在保障飞行安全间隔与降低社区噪声影响这两个冲突目标之间取得平衡。
但深度学习与强化学习在运算时长与算力上都有极高要求,部分研究侧重于构建调度问题的顶层框架与数学模型。Shihab等[7]比较了按需调度和预定调度两种模式的优缺点,提出了混合运营概念。Fatule等[8]针对eVTOL在城市空中交通中的路由和调度问题提出了一种eVTOL调度数学模型,通过优化相关决策变量,实现电力消耗、未满足需求的惩罚以及充电端口成本的最小化。钟罡等[9]针对城市低空无人机飞行计划调度问题,提出基于复杂网络的两阶段优化调度方法,先规划单机四维航迹生成初始计划,再识别关键飞行计划,建立融合多种策略的优化调度模型。针对调度模型,学者采用多种启发式与智能优化算法进行求解,Pradeep等[10]针对eVTOL飞行汽车到达排序和调度问题,提出插入和局部搜索启发式算法,结合混合整数线性规划和时间推进算法进行优化,通过数值模拟验证了算法的实时调度能力。Ge[11]设计了一种智能调度和管理系统,采用蚁群算法解决了eVTOL在城市空中交通环境下的机库调度问题。
以上低空交通调度的研究,多数仅考虑有限简单的约束条件,传统优化算法求解这类复杂问题时容易陷入局部最优。以第二代非支配排序遗传算法(non-dominated sorting genetic algorithm Ⅱ,NSGA-Ⅱ)为代表的传统多目标优化算法具有优势[12],在应用于本文构建的eVTOL调度模型时仍面临容易过早收敛于局部最优解的情况,限制了求解效率和求解质量。
因此,针对管制低空场景下的eVTOL调度问题,提出一种融合强化学习与禁忌搜索的改进多目标遗传算法(reinforcement learning tabu search improved non-dominated sorting genetic algorithm Ⅱ,RLTS-NSGA-Ⅱ)。研究构建一个包含任务时空约束、资源分配、序列关系和冲突避免的多维约束模型,并引入任务串预处理策略以降低问题复杂度。设计一种高效的三段式整数编码方案,通过将设计的基于关键任务串的局部禁忌搜索策略和基于Q-learning的参数自适应策略引入传统NSGA-Ⅱ算法对其进行改进,增强算法跳出局部最优的能力,使交叉率和变异率能够根据种群进化状态动态调整。最后,通过与算法自身变体及与其他算法的仿真对比,验证本文所提模型与算法在求解eVTOL调度问题上的有效性。所构建的多维约束调度模型与RLTS-NSGA-Ⅱ改进算法,可为城市低空载人调度优化提供理论依据与技术参考。

1 模型构建

1.1 问题描述与基本假设

根据《国家空域基础分类方法》[13]规定, 300~1 000 m为低空管制空域,此区间基本无高楼障碍,适合作为低空载人等低空交通调度的主要应用场景。eVTOL调度的目标是根据垂直起降机场和空域运力限制制定最佳飞行计划,飞行计划通常包括任务选用哪架航空器、计划出发-到达时间表、计划出发-到达地点表和使用的空域航线。完整的 eVTOL 调度业务涉及多方主体与多类信息交互,调度运营框架如图1所示。

管制低空场景下eVTOL调度问题可描述为:n个任务在m架eVTOL上执行,每个任务需要从指定起点飞行至终点。飞行任务在其可选eVTOL集中的任意一架eVTOL上进行执行,为了保障eVTOL之间的时空安全间隔,将空域分为三个高度层进行层级划分,并在此基础上设置航线。调度完成后,明确所有任务的合理执行时间,以及每个任务选择的执行eVTOL和飞行航线,最终达到总能耗最小化、总延误最低且保证飞行隔离安全的目的。

模型的基本假设如下:

(1)低空空域被划分为三个标准化高度层,每对起降点之间有六条互不干扰的单向航线。

(2)因研究考虑飞行高度于建筑层之上,且研究为调度层面,故航线设计类似无人机物流调度设置为直线。

(3)同一eVTOL连续任务间需要40 min间隔时间用于机组人员休息与eVTOL充电。

(4)eVTOL都为同一型号,初始状态满电。

(5)所有输入参数(任务需求、任务耗时、任务能耗等)是确定性的,不考虑随机扰动因素。

1.2 模型参数及符号说明

相关变量与参数的符号定义如表1所示。

1.3 目标函数

为实现低空交通合理调度,本模型以能耗最小化和时刻表任务延误量最小化为目标函数。表达式为

min[f(x)]=f1(x)+f2(x)

第一个优化目标为最小化系统总能量消耗,表达式为

f1(x)=${\sum }_{\mathit{i}}^{}{\sum }_{\mathit{h}}^{}$pihbzih

式(2)中:pihb为任务i选择航线h时的电量消耗;zih为二进制决策变量,当任务i选择航线h时为1,否则为0。

第二个优化目标为最小化任务总延误时间,是提升调度服务质量的重要指标。利用任务实际开始时刻减去任务信息的期望开始时刻,所有任务求和即可得到总延误时间。表达式为

f2(x)=${\sum }_{\mathit{i}}^{}$(tsi-${\mathit{t}}_{\mathit{i}}^{\mathrm{e}\mathrm{x}\mathrm{p}}$)

1.4 约束条件

约束可分为任务时空约束、资源分配约束、序列关系约束和冲突避免约束。

(1)任务时空约束。

此类约束定义了任务执行的时空要求。

${\sum }_{\mathit{h}}^{}$zih=1, ∀ i∈R
Tsc=${\sum }_{\mathit{k}}^{}{\sum }_{\mathit{t}}^{}$tyckt, ∀ c∈C
Tfc=tfc(-1), ∀c∈C
${\mathit{t}}_{\mathit{i}}^{\mathrm{e}\mathrm{x}\mathrm{p}}$≤tsi≤${\mathit{t}}_{\mathit{i}}^{\mathrm{e}\mathrm{x}\mathrm{p}}$+Δtih, ∀ i∈R
tfi=tsi+${\sum }_{\mathit{h}}^{}$Δtihzih, ∀i∈R

式(4)表示每个任务必须选择唯一的航线;式(5)与式(6)定义了任务串开始时刻和结束时刻,开始时刻是核心决策变量的直接体现,结束时刻是衍生结果变量的表达,等于任务串中最后一个任务的结束时刻;式(7)说明任务的开始时间必须在其预定义的时间窗内;式(8)说明任务的结束时间由开始时间和所选航线的飞行时长决定。

(2)资源分配约束。

确保任务串被合理分配给eVTOL资源,每个任务串必须有且只能被分配给一架eVTOL。

${\sum }_{\mathit{k}}^{}{\sum }_{\mathit{t}}^{}$yckt=1, ∀ c∈C

(3)序列关系约束。

序列约束保证了任务串内部及不同任务串之间的执行逻辑。对于任务串内部,式(10)表示首个任务的开始时间,定义了整个任务串的开始时间,式11说明了后续任务必须在前序任务完成后,并经过一个最小周转间隔(如40 min)方可开始。式(12)~式(14)定义变量bck与Ac1,c2,k,为式(15)与式(16)的核心间隔约束做准备,式(15)与式(16)说明对于分配给同一架eVTOL的两个不同任务串c1和c2,它们之间也必须满足最小时间间隔Ic。

tsi1=Tsc
tsij≥tfij-1+40, j>1
bck=${\sum }_{\mathit{t}\in \mathit{T}}^{}$yckt ∀ c∈C,∀k∈K
Ac1,c2,k≤bc1,k, ∀c1,c2∈C,c1≠c2,∀k∈K
$\begin{aligned}A_{c_{1}, c_{2}, k} & \geqslant b_{c_{1}, k}+b_{c_{2}, k}-1, \quad \forall c_{1}, c_{2} \in C, \\c_{1} & \neq c_{2}, \forall k \in K\end{aligned}$
Tfc1+Ic≤Tsc2+M(1-Oc1,c2,k)+M(1-Ac1,c2,k)
Tfc2+Ic≤Tsc1+MOc1,c2,k+M(1-Ac1,c2,k)

式中:i1,i2,…,${\mathit{i}}_{\left|{\mathit{T}}_{\mathit{c}}\right|}$为任务串c中任务顺序。

(4)冲突避免约束。

为保障运行安全,需要避免资源在时空上的冲突。式(17)定义了任何一架eVTOL在任意时刻最多只能执行一个任务串;同时,为避免空中碰撞,式(18)定义了在任意时刻的任一航线,最多只能有一架eVTOL在执行任务。

${\sum }_{\mathit{c}}^{}{\sum }_{\mathit{t}:\mathit{t}\in [\mathit{\tau }-{\mathit{D}}_{\mathit{c}}+1,\mathrm{ }\mathit{\tau }]}^{}$yckt≤1, ∀τ,∀k∈K
${\sum }_{\mathit{i}\in {\mathit{S}}_{\mathit{h}}}^{}{\sum }_{\mathit{k}}^{}{\sum }_{\mathit{t}\mathit{\text{'}}:\mathit{\tau }\in [{{\mathit{t}}^{\mathrm{s}}}_{\mathit{i}},{{\mathit{t}}^{\mathrm{s}}}_{\mathit{i}}+\mathrm{\Delta }{\mathit{t}}_{\mathit{i}\mathit{h}}-1]}^{}$ycktzih≤1, ∀τ

式中:Dc为任务串c的最大可能持续时间,定义为Dc=${\sum }_{\mathit{i}\in {\mathit{T}}_{\mathit{c}}}^{}$maxhΔtih+15(|Tc|-1)。

2 算法设计

2.1 算法框架

设计了融合Q-learning与变邻域搜索的改进NSGA-Ⅱ算法(Q-learning and variable neighborhood search based NSGA-Ⅱ,QVNSGA-Ⅱ)。该算法通过设计问题特化的高效整数编码、引入增强局部搜索能力的变邻域搜索算子,构建基于强化学习的参数自适应调节机制,实现对复杂解空间的有效探索,算法框架如图2所示。

2.2 任务串提前构建策略

借鉴民航领域的“航班串”概念[14],在算法主流程开始前引入了任务串预处理策略,用于降低遗传算法的求解空间维度。核心思想是将原问题从为每一个独立任务分配资源,转化为在逻辑上起降场连续的任务串分配资源。策略中采用了基于空间连续性与时间兼容性的贪心启发式算法。具体实现步骤如下:

步骤1 初始化与排序。将所有待调度的独立任务,按照各自的期望出发时间进行升序排序。这一操作确保了算法在构建任务串时,能够优先处理时间上更早的任务,符合调度的自然逻辑。

步骤2 迭代构建任务串。算法首先筛选出起飞点与前序任务降落点相同的任务,以此作为满足空间连续性的硬性约束候选集;然后,再依据时间兼容性启发式,从候选集中选择期望开始时间与当前任务串理论结束时间最匹配的最优任务进行追加。

步骤3 构建终止与循环。当任务串无法找到任何满足空间连续性的后续任务,或长度达上限时,任务串构建过程终止。随后,算法会返回至总任务列表,选择下一个未被分配的、排序最靠前的任务。直至所有任务均被成功分配到一个任务串中。

通过上述步骤,原始的、离散的任务集合被重组为一系列有序且内部连续的任务串。如表2所示为一组离散、无序的原始飞行任务。

经过任务串提前构建策略执行之后,生成了5个任务串,覆盖30个任务,任务之间保持了位置逻辑的连续性,如图3所示。

2.3 三段式编码

研究中设计了一种纯整数向量编码方案,将一个完整复杂的调度方案映射为一个一维整数染色体,以适应遗传算法操作。每个染色体由三个功能不同的基因段线性拼接而成,具体构成如下。

第一部分为任务串分配与执行基因,针对每一个任务串,均采用两个整数进行描述,分别代表执行该任务串的eVTOL编号和其计划开始时间。第二部分为航线选择基因,对每一个独立任务,使用单个整数来指定其执行的航线编号。第三部分是任务开始时刻基因,直接为每个任务编码一个绝对的开始执行时刻。其余的变量均能由编码信息计算或结合约束得到,因此一个染色体就是一个完整的调度解决方案。一个由五个任务构成的两个任务串的编码形式如图4所示。

2.4 基于关键任务串的局部搜索策略

为增强算法的局部精细搜索能力,设计了一种基于关键任务串的局部禁忌搜索(tabu search,TS)策略。

策略核心在于识别并优化调度方案中的“瓶颈”环节。与传统关键路径法关注时间最长路径不同,将“关键路径”定义为对多目标函数综合恶化影响最大的关键任务串。通过对每个任务串的总延误惩罚、总能耗以及潜在的空中飞行冲突进行加权求和,得到综合评估分。分值最高的任务串即被识别为当前解的关键路径,成为局部搜索的焦点。其评估分数S的计算公式为

S=wdelayPdelay(c)+wenergyE(c)+wconflictPconflict(c)

式(19)中:Pdelay(c)为任务串c的总延误惩罚;E(c)为其总能耗;Pconflict(c)为任务串c与其他任务串的潜在冲突惩罚;w为对应的权重系数。

在识别出关键任务串后,算法通过邻域移动算子(图5)来探索其邻近的解空间,以寻找更优的配置,邻域移动主要包括四种操作。

(1)任务串eVTOL重分配:尝试将关键任务串从当前分配的eVTOL上,重新指派给另一架负载较轻或时间窗口更合适的eVTOL,以缓解资源瓶颈。

(2)任务串时间调整:在不改变eVTOL分配的前提下,将关键任务串的整体开始时间在时间轴上进行小范围的前移或后移,以规避与其他任务串的时序冲突。

(3)航线调整:调整关键任务串中某个或某几个任务的飞行高度层以切换不同航线,以寻求更低的能耗组合或进一步降低空中相遇的风险。

(4)任务时间微调:对任务串内部单个任务的开始时间进行小范围的调整,实现更精细的时间调度,减少个体任务的延误。

为避免在邻域搜索过程中因移动操作的往复执行而陷入循环(图6),该策略引入了禁忌表机制。该机制保证了搜索过程具有方向性,能有效引导算法持续探索新的解空间区域。

在算法的进化过程中,该局部搜索策略会以预设的频率,选择种群中适应度排名靠前的一部分优秀个体来执行。通过这种方式,算法在保持全局进化趋势的同时,实现全局探索与局部开发的有效平衡。

2.5 基于Q-learning的自适应策略

传统遗传算法中交叉率和变异率的静态策略难以适应优化过程中种群在不同进化阶段的动态变化需求。文献[15]通过结合强化学习与遗传算法实现自适应遗传策略。引入强化学习理论,将Q-learning算法与NSGA-Ⅱ框架深度融合,构建了一种参数自适应调节机制,训练智能体学习最优交叉变异率组合策略。

2.5.1 状态空间

采用一种相对性能评估方法,构建了一个基于种群综合评价值的离散状态空间。首先将多维目标函数值加权转化为单一的综合适应度值,并记录第一代种群的平均适应度${\stackrel{-}{\mathit{f}}}_{1}$及最佳适应度f1best作为性能参照基线。在后续的每一代进化中,通过计算当前第t代种群对应指标${\stackrel{-}{\mathit{f}}}_{\mathit{t}}$与ftbest和基线值的比率,并进行加权求和,得到一个反映种群相对进化程度的评价值F。其计算公式为

Ft=0.5$\frac{{\stackrel{-}{\mathit{f}}}_{\mathit{t}}}{{\stackrel{-}{\mathit{f}}}_{1}}$+0.5$\frac{{{\mathit{f}}_{\mathit{t}}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}{{{\mathit{f}}_{1}}_{\mathrm{b}\mathrm{e}\mathrm{s}\mathrm{t}}}$

式(20)中:$\stackrel{-}{\mathit{f}}$为种群的平均适应度;fbest代表种群的最佳适应度。该评价值最终被均匀离散化为20个状态(s∈{0,1,…,19}),使智能体能够清晰地感知种群性能的细微动态变化,为后续的决策学习提供可靠依据。

2.5.2 动作空间

在本研究中,动作空间由交叉率Pc和变异率Pm的一组离散候选值构成。这些候选值的选取覆盖了遗传算法从保守到激进的常用参数范围,共有25种可能选择的动作,每一种交叉率都可以与另外五种变异率进行组会。具体的动作空间定义如表3所示。

2.5.3 奖惩机制

采用二元奖励策略。通过比较当前t代的评价值Ft与上一代t-1的评价值Ft-1来确定奖励值。该反馈机制能够直接关联上一代所选动作与当前种群的进化结果。具体定义为

Rt=$\left\{\begin{array}{lll}+1,& {\mathit{F}}_{\mathit{t}}<{\mathit{F}}_{\mathit{t}-1}& \mathrm{ }\\ -1,& \mathrm{其}\mathrm{他}& \mathrm{ }\end{array}\right.$

当种群性能得到改善时,智能体获得正向奖励;反之,若性能停滞或恶化,则施以负向奖励。

2.5.4 动作选择与Q表更新

在动作选择策略上,为平衡强化学习中的“探索-利用”矛盾,智能体以概率∊随机探索动作空间,发掘潜在的更优策略;同时以概率1-∊基于当前Q表选取价值最大的动作,利用已有经验。为促进算法在进化前期进行广泛探索、后期稳定收敛,探索率∊将随迭代代数g的增加而从一个较高的初始值线性衰减至一个较小的预设值。探索率的计算公式为

∊g=∊start-g$\frac{{\mathit{ϵ}}_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}-{\mathit{ϵ}}_{\mathrm{e}\mathrm{n}\mathrm{d}}}{{\mathit{G}}_{\mathrm{m}\mathrm{a}\mathrm{x}}}$

式(22)中:∊g为第g代的探索率;∊start与∊end分别为预设的初始和终止探索率;Gmax为最大进化代数。

Q存储了状态s下采取动作a的长期期望回报。在每次动作执行并获得奖励后,Q表依据经典的时序差分更新,即

$\begin{array}{l}Q(s, a) \leftarrow Q(s, a)+\alpha\left[R+\gamma \max _{a^{\prime}} Q\left(s^{\prime}, a^{\prime}\right)-\right. \\\quad Q(s, a)]\end{array}$

式(23)中:s与a为当前的状态-动作对;s'为执行动作后转移的下一状态,a'为下一状态下可选动作;R为即时奖励;学习率α∈[0,1]控制着新信息对Q值更新的权重;折扣因子γ∈[0,1]则用于权衡即时奖励与未来长期回报的重要性。

3 仿真实验设计

3.1 实验场景构建

3.1.1 地理与空域结构

为验证本文所提出的强化学习协同进化算法在求解eVTOL调度问题时的有效性与可扩展性,以广州为算例,开展仿真实验。实验场景设定在广州南站区域附近,其地理分布参考了城市核心功能区,包含高铁站、商业区、居民区与旅游区,起降场之间的直线距离通过地图工具测量获得,如图7所示。

如图8所示,空域结构在垂直维度上被划分为三个离散的高度层,基于空域构型任意两个起降场之间都预设了六条具有不同飞行剖面的航线,分别对应不同的飞行时间与能量消耗。eVTOL的单次飞行任务被简化为爬升、巡航、降落三个阶段。

3.1.2 飞行时间与能耗模型

飞行时间的计算基于某公司生产的某款eVTOL性能参数与起降点信息,爬升速度2 m/s,巡航速度90 km/h,降落速度2 m/s,总电量45 kWh,飞行功率143 kW,20 min内能完成充电。

单次任务的总飞行时间是通过对飞行剖面进行分段建模来确定的,总时间分为垂直爬升时间Tc、水平巡航时间Tcr与垂直降落时间Td三个核心航段累加之和,而每个航段的持续时间则由其对应的特征距离与平均飞行速度共同决定。

Ttotal=Tc+Tcr+Td

基于此得到两两起降场之间一共十八条航线的飞行所需消耗时间,为适应以分钟为精度的一天调度时刻表,消耗时间依据分钟指标取整,如表4所示。

能量消耗的计算基于简化的线性放电模型,公式为

E=Pt
η=$\frac{\mathit{E}}{{\mathit{E}}_{\mathrm{t}\mathrm{o}\mathrm{t}\mathrm{a}\mathrm{l}}}$×100%

式中:η为电量消耗百分比;E为已消耗的电量;Etotal为总电量。经过数据处理得到两两起降点任务之间的百分比电量消耗。

预先计算出的所有起降场组合在十八条不同航线下的飞行时间与电量百分比消耗,将作为调度算法输入的基础数据信息,如表5所示。

3.1.3 任务需求生成

由于低空交通调度并未规模化市场应用,缺乏真实低空eVTOL交通出行数据,随机生成小规模(30个任务、4架航空器)、中规模(50个任务、5架航空器)、大规模(70个任务、6架航空器)三个出行任务数据算例,用于数学模型与算法的验证。

这些任务是乘客通过手机提前一天以上在手机App订阅的出行服务。具体的任务生成规则设定如下:首先,在一个20 km×20 km的广州城市区域内,预设4个固定的起降点。每个任务的出发点和目的地从这4个起降点中随机选择。其次,将一天的运营时间设定为06∶00—18∶00。为了模拟城市交通的“潮汐”特性,任务的期望出发时间并非均匀分布,而是集中在早高峰(07∶00—09∶00)、午高峰(11∶00—13∶00)和晚高峰(15∶30—17∶30)三个时段,这三个时段内生成任务的概率更高。每个任务设置一个时间窗以反映乘客对出行时间的容忍度。

3.1.4 实验平台与参数设置

仿真实验在Windows操作系统的台式计算机上进行,硬件配置为i5-12490F CPU @3.00 GHz,32 GB RAM。为消除随机性对结果的影响并确保数据的统计有效性,每种算法均独立重复运行20次,最终的性能指标取20次运行结果的平均值进行分析。在算法中学习率α、折扣因子γ、初始贪婪因子∊这三个参数直接决定了Q-learning部分的性能,选用中规模算例利用田口正交实验设计选取最优参数组合,根据表6可得最优参数组合为α=0.8,γ=0.7,∊=0.6。在种群初始化阶段,为了确保算法有足够的搜索空间来寻找最优解,设定个体数量为30,最大遗传代数为300代[16]。

3.2 策略有效性检测

为验证策略有效性构建两个QVNSGA-Ⅱ变体,即融合变邻域搜索的非支配排序遗传算法 Ⅱ[variable neighborhood search non-dominated sorting genetic algorithm Ⅱ,VNSGA-Ⅱ(A)]和Q 学习增强型非支配排序遗传算法 Ⅱ[Q-learning enhanced non-dominated sorting genetic algorithm Ⅱ,QNSGA-Ⅱ(B)]。VNSGA-Ⅱ(A)代表没有采用Q-learning算法进行参数的自适应,QNSGA-Ⅱ(B)代表没有采用局部搜索策略。

通过两个方面指标来评价帕累托前沿质量,分别是反世代距离(inverted generational distance,IGD)与超体积指标(hypervolume,HV)[17]。但是由于真实的帕累托前沿在许多实际工程问题中是难以获取的,本文的调度问题也面临同样的问题。采用生成近似的帕累托前沿方案解决此问题,选择多个当前公认性能强、不同类型的多目标优化算法,将这些算法多次独立运行后得到的所有非支配解合并在一起,再从这个合并的解集中筛选出新的非支配解[18]。这个最终筛选出的集合就被当作“真实帕累托前沿”的近似,用于计算IGD。如表7所示为不同策略IGD和HV值的对比。

对比QVNSGA-Ⅱ与VNSGA-Ⅱ(A)可以看出, QVNSGA-Ⅱ在三种算例情况下的IGD小于 VNSGA-Ⅱ(A), 分别在小、中、大规模算例上降低了27.1%、20.3%和6.6%,总体降低了18%,HV指标在三种算例上分别提升了10.1%、22.1%和6.3%,总体提升了12.8%,这验证了基于关键任务串移动操作的局部搜索策略的有效性。对比 QVNSGA-Ⅱ与QNSGA-Ⅱ (B)可以看出, QVNSGA-Ⅱ在所有情况下的IGD均小于 QNSGA-Ⅱ (B), 在三种算例上分别降低了32.8%、22.0%和7.1%,总体降低了20.6%,并在所有情况下HV指标均大于QNSGA-Ⅱ(B),分别提升了4.6%、13.5%和17.3%,总体提升了11.8%,证明了使用Q-learning去调整Pc、Pm值的有效性,提升了算法性能。

3.3 对比实验

将QVNSGA-Ⅱ与现有算法进行比较,分别为NSGA-Ⅱ、基于分解的多目标进化算法(multiobjective evolutionary algorithm based on decomposition,MOEA/D)和增强型强度帕累托进化算法(strength Pareto evolutionary algorithm Ⅱ,SPEA-Ⅱ),图9展示了四种算法的帕累托解集对比情况。

可以看出在小、中、大规模三种不同任务场景的测试下,本文提出的QVNSGA-Ⅱ算法所获得的帕累托前沿在结果上均优于其他三种对比算法。在“能耗-延误”二维目标空间中,整体上完全支配了其他算法的解集,更加逼近理想目标点。这表明不同的问题规模QVNSGA-Ⅱ均能找到在总能耗和总延误上性能更优的非支配调度方案。

如表8所示,在三个问题规模下使用 IGD和 HV评价指标对QVNSGA-Ⅱ、NSGA-Ⅱ、MOEA/D和SPEA-Ⅱ四种算法进行评价的结果比较。在三种测试算例下,本文提出的QVNSGA-Ⅱ算法在两项指标上均表现出相比其他算法更好的性能。在反映算法收敛性的IGD指标上,QVNSGA-Ⅱ获得了所有对比算法中的最小值。在反映解集分布性和多样性的HV指标上,QVNSGA-Ⅱ则取得了所有对比算法中的最大值。QVNSGA-Ⅱ算法相较于传统NSGA-Ⅱ在IGD与HV指标上分别取得了36.2%与25.6%的提升。为了更直观地展示数据,利用表8的相关实验数据绘制了图10所示的箱线图,展示20次测试的统计结果。

综上所述,本文QVNSGA-Ⅱ在求解本文提出的调度模型上优于NSGA-Ⅱ、MOEA/D和SPEA-Ⅱ算法。QVNSGA-Ⅱ算法最终还会得到结果调度表。调度表是对调度结果精确、量化的详细记录,提供具体的执行指令,作为空管系统向eVTOL等自动化系统的输入。

策略相应的调度如表9所示,在现实执行过程中严格执行调度图与调度表的调度安排,以保证基于eVTOL的城市空中交通调度运行。由于调度表任务数量较多,此处仅展示调度表中的5个任务结果。

4 结论

针对管制低空场景下eVTOL调度问题,构建了包含多维现实约束的优化模型,并提出了一种融合任务串预处理、强化学习参数自适应和禁忌局部搜索的改进多目标遗传算法。得到如下主要研究结论。

(1)构建了包含任务时空、资源分配、序列关系和冲突避免等多维度约束的低空eVTOL调度优化模型,为低空调度问题的求解提供了具体的数学框架。

(2)提出了一种任务串预处理策略,显著缩小了问题的解空间,并设计了一种融合强化学习与禁忌搜索的改进多目标遗传算法,通过引入基于Q-learning的参数自适应策略解决了传统遗传算法参数固定的局限性,同时,设计了基于关键任务串的局部禁忌搜索策略,有效增强了算法跳出局部最优的能力。

(3)进行了策略有效性验证和对比实验,基于Q-learning参数自适应策略使IGD总体降低18%,HV总体提升12.8%。基于关键任务串的局部禁忌搜索策略使IGD总体降低20.6%,HV总体提升11.8%。对比实验将所提QVNSGA-Ⅱ与其他前沿算法对比, 与传统NSGA-Ⅱ在IGD与HV指标上分别取得了36.2%与25.6%的提升。

参考文献

[1]

Bauranov A, Rakas J. Designing airspace for urban air mobility: a review of concepts and approaches[J]. Progress in Aerospace Sciences, 2021, 125: 100726.

[2]

Zhang M, Zeng Y L, Wang K, et al. Learned unmanned vehicle scheduling for large-scale urban logistics[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(7): 7933-7944.

[3]

Li W, Cheng R G, Huang H H, et al. Energy consumption modeling and optimization of an eVTOL aircraft: integrating weight, motor, and battery dynamics[J]. Energy, 2025, 325: 136229.

[4]

Pang Y T, Zhao P, Hu J M, et al. Machine learning-enhanced aircraft landing scheduling under uncertainties[J]. Transportation Research Part C: Emerging Technologies, 2024, 158: 104444.

[5]

Paul S, Chowdhury S. A graph-based reinforcement learning framework for urban air mobility fleet scheduling[C]//Proceedings of AIAA AVIATION 2022 Forum. Chicago: AIAA, 2022: 3911.

[6]

Murthy S, Gao Z Y, Clarke J, et al. A reinforcement learning approach to quiet and safe UAM traffic management[C]//Proceedings of AIAA SCITECH 2025 Forum. Orlando: AIAA, 2025: 2118.

[7]

Shihab S A M, Wei P, Jurado D, et al. By schedule or on demand? a hybrid operation concept for urban air mobility[C]//Proceedings of AIAA Aviation 2019 Forum. Dallas: AIAA, 2019: 3522.

[8]

Fatule E C, Arif M A, Wang F Y, et al. A mathematical model for scheduling electrical vertical takeoff and landing vehicle flights[C]//Proceedings of the 56th North American Power Symposium. El Paso: IEEE, 2024: 1-6.

[9]

钟罡, 华骏鸣, 杜森, 等. 基于复杂网络的城市低空飞行计划优化调度研究[J]. 航空学报, 2025, 46(11): 531479.

[10]

Zhong Gang, Hua Junming, Du Sen, et al. Research on optimization scheduling of urban low-altitude flight plan based on complex network[J]. Acta Aeronautica et Astronautica Sinica, 2025, 46(11): 531479.

[11]

Pradeep P, Wei P. Heuristic approach for arrival sequencing and scheduling for eVTOL aircraft in on-demand urban air mobility[C]//Proceedings of 2018 IEEE/AIAA 37th Digital Avionics Systems Conference. London: IEEE, 2018: 1-7.

[12]

Ge G Y. Research and design of eVTOL garage scheduling and management systems for urban air mobility[C]//Proceedings of 2024 4th International Signal Processing, Communications and Engineering Management Conference. Montreal: IEEE, 2024: 270-275.

[13]

王飞, 徐浩凡, 王京硕. 面向多配送中心的空地协同配送路线优化[J]. 华南理工大学学报(自然科学版), 2026, 54(6): 42-53.

[14]

Wang Fei, Xu Haofan, Wang Jingshuo. Vehicle-drone collaborative distribution route optimization based on the NSGA-Ⅱ algorithm[J]. Journal of South China University of Technology (Natural Science Edition), 2026, 54(6): 42-53.

[15]

中国民用航空局. 国家空域基础分类方法[R/OL]. (2023-12-21)[2025-08-23]. http://www.aopa.org.cn/usr/1/upload/file/20231227/17036672816906355.pdf.

[16]

Civil Aviation Administration of China. Basic classification method for national airspace[R/OL]. (2023-12-21)[2025-08-23]. http://www.aopa.org.cn/usr/1/upload/file/20231227/17036672816906355.pdf.

[17]

李耀华, 谭娜. 基于遗传算法的飞机一体化排班优化方法[J]. 控制工程, 2017, 24(2): 435-440.

[18]

Li Yaohua, Tan Na. Optimization method of aircraft integrated planning based on genetic algorithm[J]. Control Engineering of China, 2017, 24(2): 435-440.

[19]

陈祉烨, 胡毅, 刘俊, 等. 利用强化学习的改进遗传算法求解柔性作业车间调度问题[J]. 科学技术与工程, 2024, 24(25): 10848-10856.

[20]

Chen Zhiye, Hu Yi, Liu Jun, et al. Improved genetic algorithm using reinforcement learning to solve flexible job shop scheduling problem[J]. Science Technology and Engineering, 2024, 24(25): 10848-10856.

[21]

杨泽武, 徐俊洁. 基于延误代价的航班调度优化模型[J]. 科学技术与工程, 2025, 25(35): 15334-15345.

[22]

Yang Zewu, Xu Junjie. Flight scheduling optimization model based on delay cost[J]. Science Technology and Engineering, 2025, 25(35): 15334-15345.

[23]

张国辉, 李志霄, 张利平, 等. 基于强化学习协同进化算法求解柔性作业车间节能调度问题[J]. 计算机应用研究, 2025, 42(7): 2039-2047.

[24]

Zhang Guohui, Li Zhixiao, Zhang Liping, et al. Reinforcement learning based co-evolutionary algorithm for solving flexible job shop energy efficient scheduling problem[J]. Application Research of Computers, 2025, 42(7): 2039-2047.

[25]

Yang Y J, Li K X, Zhan H X, et al. A Q-learning-based improved multi-objective genetic algorithm for solving distributed heterogeneous flexible job shop scheduling problem with dual-resource constraints[J]. Expert Systems with Applications, 2025, 261: 125516.

基金资助

深圳市科技计划(KJZD20240903103806009)

深圳市科技计划(KCXFZ20240903093911016)

重庆市科技创新重大研发项目(CSTB2023TIADSTX0030)

广东省重点领域研发计划(2022B0701180001)

PDF (7021KB)

0

访问

0

被引

详细

导航
相关文章

/

〈 〉