利索能及
我要发布
收藏
专利号: 2025105039078
申请人: 中国民航大学
专利类型:发明专利
专利状态:已下证
更新日期:2025-12-08
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种航班串节点序列确定方法,其特征在于,所述方法基于经训练后的节点序列确定模型实现,所述经训练后的节点序列确定模型包括起始节点选择模块、节点嵌入特征提取模块和目标节点获取模块;所述方法包括如下步骤:S100,基于当前待处理事件集,构建全连通图;当前待处理事件集中的一个待处理事件表征一个航班,全连通图为含有自连接的无向图,全连通图中的节点表示待处理事件,任意两个节点之间通过无向边连接;

S200,将所述全连通图输入至起始节点选择模块中,以从全连通图中的所有节点中随机选择k个节点作为起始节点,并输入给所述目标节点获取模块;k>1;

S300,将所述全连通图输入至节点嵌入特征提取模块中,以对全连通图中的所有节点的节点嵌入特征进行提取,并将提取的节点嵌入特征输入给所述目标节点获取模块;

S400,对于每个起始节点,利用所述目标节点获取模块获取每个起点节点对应的节点序列集,作为候选节点序列集,得到k个候选节点序列集;其中,候选节点序列集中的每个候选节点序列由同一个执行对象执行;

S500,获取每个候选节点序列集对应的总资源需求值,得到k个总资源需求值,并将k个总资源需求值中的最小者对应的候选节点序列集作为当前待处理事件的目标节点序列集;

所述目标节点获取模块包括候选节点选择单元、多头注意力层、单头注意力层和目标节点选择单元;

S400具体包括:

S401,设置起始节点计数器r=1;

S402,如果r≤k,设置执行对象计数器g=1,执行S403,如果r>k,得到k个候选节点序列集,执行S500;

S403,如果当前的节点集不为空,执行S404,否则,得到第r个起始节点对应的候选节点序列集,设置r=r+1,执行S402;当前的节点集的初始值为全连通图中的所有节点形成的节点集;

S404,利用所述候选节点选择单元从当前的节点集中选择与第g个执行对象对应的当前已选择节点之间满足预设约束条件的节点,如果获取到与第g个执行对象对应的当前已选择节点之间满足预设约束条件的节点,将获取的与第g个执行对象对应的当前已选择节点之间满足预设约束条件的节点作为第g个执行对象的当前候选节点,执行S405;如果获取不到与第g个执行对象对应的当前已选择节点之间满足预设约束条件的节点,执行S409;其中,g的初始值为1,第1个执行对象对应的当前已选择节点的初始值为第r个起始节点;

S405,基于全连通图中的所有节点的节点嵌入特征的平均值、第g个执行对象对应的当前已选择节点的节点嵌入特征和当前已使用的执行对象的数量,利用所述多头注意力层获取全连通图对应的上下文注意力特征,作为第g个执行对象对应的当前上下文注意力特征;

S406,基于第g个执行对象对应的当前上下文注意力特征,利用所述单头注意力层获取全连通图中的每个节点的节点权重,作为第g个执行对象对应的当前节点权重;

S407,基于第g个执行对象对应的当前节点权重,利用目标节点选择单元从第g个执行对象的当前候选节点中获取目标节点,作为第g个执行对象对应的当前的目标节点;其中,第g个执行对象对应的当前的目标节点为第g个执行对象的当前节点权重中的最大节点权重对应的节点;

S408,将第g个执行对象对应的当前的目标节点作为第g个执行对象对应的当前已选择节点,并加入到第g个执行对象对应的当前已选择节点集中,以及将第g个执行对象对应的当前的目标节点从当前的节点集中删除,执行S403;第g个执行对象对应的当前已选择节点集的初始值为空;

S409,基于第g个执行对象对应的当前已选择节点集得到第g个执行对象对应的候选节点序列,设置g=g+1,并从当前的节点集中随机选择一个节点作为第g+1个执行对象对应的当前已选择节点的初始值,执行S403;

第r个起始节点对应的总资源需求值Dr满足如下条件:

f(r) z(r) z(r)

Dr=∑ i=1∑ u=1RCiu×xiu+∑ u=1Pu×Tu×Iu;其中,RCiu为第i个执行对象执行第u个节点对应的待处理事件所需要的资源,i的取值为1到f(r),f(r)为第r个起始节点对应的执行对象的数量,u的取值为1到z(r),z(r)为第r个起始节点对应的候选节点序列集中的节点数量;xiu为变量,如果第i个执行对象执行第u个节点对应的待处理事件,xiu=1,否则,xiu=0;

Pu第u个节点对应的延误系数,如果xiu=1,Pu=Qu‑front+(1‑Qu‑front)×Pu‑front,Qu‑front为基于第j个节点的前序节点和第j个节点之间的松弛时间确定的延迟系数,Pu‑front为第j个节点的前序节点的延迟系数,Tu为第u个节点对应的历史平均延误时间,Iu为第u个节点的延误所需要的资源值,其中,两个航班之间的松弛时间为两个航班的计划过站时间差与最小过站时间的差值。

2.根据权利要求1所述的方法,其特征在于,所述预设约束条件满足如下条件:如果Mj=1,表示当前的节点集中的第j个节点为当前已选择节点的候选节点,如果Mj=0,表示当前的节点集中的第j个节点不是当前已选择节点的候选节点,其中,Mj为第j个节点E L E对应的总约束值,Mj=Cj⊙Cj ⊙Cj ,Cj为第j个节点对应的中转时间约束值,Cj 为第j个节点E对应的机型约束值,Cj为第j个节点对应的机场衔接约束值,Cj满足如下条件:如果当前已E选择节点和第j个节点之间的松弛时间大于等于0,Cj=1,否则,Cj=0;Cj满足如下条件:如果E E L当前已选择节点对应的飞机机型适用于第j个节点,Cj=1,否则,Cj=0;Cj满足如下条件:如L L果第j个节点对应的出发机场为当前已选择节点对应的机场,Cj=1,否则,Cj=0;⊙表示同或运算,j的取值为1到Q,Q为当前的节点集中的节点数量。

3.根据权利要求2所述的方法,其特征在于,在S405中,利用所述多头注意力层获取全连通图对应的上下文注意力特征具体包括:

S4051,获取当前的拼接特征FP;其中,FP满足如下条件:如果时间步t=1,FP=[Favg,z,Pt],如果t>1,FP=[Favg,Ft,Pt],Favg为所有节点的节点嵌入特征的平均值,z为设定输入占位符,Pt为当前已使用的执行对象的数量,Ft为当前已选择节点的节点嵌入特征;

S4052,分别利用多头注意力层的每个注意头获取当前上下文嵌入特征和全连通图中的所有节点的节点嵌入特征之间的注意力分数向量;

S4053,基于每个注意力头获取的当前上下文嵌入特征和全连通图中的所有节点之间N S(c,a) N S(c,b1)

的注意力分数向量,获取当前上下文嵌入特征的注意力值Av=∑a=1(e /∑b1=1e )×va,S(c,b1)为当前上下文嵌入特征和全连通图中的第b1个节点的节点嵌入特征之间的注意力分数,b1的取值为1到N,e为自然数;

S4054,基于所有注意力头得到的当前上下文嵌入特征的注意力值,得到多头注意力的输出结果,作为所述上下文注意力特征。

4.根据权利要求3所述的方法,其特征在于,当前上下文嵌入特征对应的查询向量qc满Q Q

足如下条件:qc=W×FP,W为注意力头的查询权重矩阵,全连通图中的第a个节点对应的键K V K向量ka=W ×ha,第a个节点对应的值向量va=W×ha,W为注意力头的键权重矩阵,ha为第a个V节点的节点嵌入特征,W为注意力头的值权重矩阵,其中,如果第a个节点不是候选节点,设置当前上下文嵌入特征和第a个节点的节点嵌入特征之间的注意力分数为负无穷,如果第a个节点不是候选节点,设置当前上下文嵌入特征和第a个节点的节点嵌入特征之间的注意T 1/2力分数S(c,a)=qcka /(dk) ,dk为键向量的维度,a的取值为1到N,N为全连通图中的节点的数量。

5.根据权利要求3所述的方法,其特征在于,在S406中,全连通图中的第a个节点的节点权重Wa满足如下条件:

C(a) N C(b1)

Wa=(e )/∑b1=1e ;C(a)为单头注意力层对应的当前上下文嵌入特征和第a个节点的节点嵌入特征之间的注意力分数,其中,C(a)满足如下条件:如果第a个节点为候选节点,T 1/2C(a)=G•tanh(qsksa /(d)k );其中,•表示点乘,G为预设值,tanh()为双曲正切函数,qs为单q q头注意力层对应的当前上下文嵌入特征,qs=WsAc,Ws 为单头注意力层的查询权重矩阵,Ack k为上下文注意力特征,ksa为单头注意力层得到的第a个节点对应的键向量,ksa=Ws ha,Ws 为单头注意力层的键权重矩阵,如果第a个节点不为候选节点,C(a)等于负无穷;C(b1)为单头注意力层对应的当前上下文嵌入特征和第b1个节点的节点嵌入特征之间的注意力分数。

6.根据权利要求1所述的方法,其特征在于,所述节点嵌入特征提取模块包括:节点嵌入模块、依次连接的M个编码模块,其中,每个编码模块包括依次连接的多头自注意力层、第一拼接处理模块、前馈神经网络层和第二拼接处理模块,其中,节点嵌入模块分别与第1个编码模块的多头自注意力层和第一拼接处理连接,每个编码模块的第一拼接处理模块还与对应的第二拼接处理模块连接,相邻的两个编码模块中的前一个编码模块的第二拼接处理模块分别与后一个编码模块的多头自注意力层和第一拼接处理模块连接,第M个编码模块的第二拼接处理模块与所述目标节点获取模块连接,第一拼接处理模块和第二拼接处理模块均用于:对接收到的输入特征进行拼接,得到对应的拼接结果,以及对拼接结果进行仿射变换批量归一化处理,M>1。

7.根据权利要求5所述的方法,其特征在于,所述经训练后的节点序列确定模型通过如下步骤获取:

S10,构建初始的节点序列确定模型;

S20,将样本数据集划分为B个批次的训练数据集,其中,样本数据集由设定时间段内的多个待处理事件构成;

S30,基于当前批次的训练数据集,构建对应的全连通图,并输入给当前的节点序列确定模型,得到当前批次的训练数据集对应的目标节点序列集;当前的节点序列确定模型的初始值为初始的节点序列确定模型;

S40,获取当前批次的训练数据集对应的候选节点序列集对应的总资源需求值的梯度,作为当前梯度,并基于当前梯度更新当前的节点序列确定模型的参数;

S50,判断当前的节点序列确定模型是否满足预设模型结束条件,如果满足,将当前的节点序列确定作为所述经训练的节点序列确定模型,否则,将下一批次的训练数据集作为当前批次的训练数据集,执行S40。

8.根据权利要求7所述的方法,其特征在于,其中,当前梯度▽J满足如下条件:▽J≈k

(1/k)∑v=1(Dv‑Davg)▽log(Wv1×……×Wvb2×……×Wvz(v)),▽表示梯度,Dv为当前批次的训练数据集对应的第v个起始节点对应的总资源需求值,Davg为当前批次的训练数据集对应的k个起始节点对应的总资源需求值的平均值,v的取值为1到k,Wvb2为第v个起始节点对应的候选节点序列集中的第b2个节点的节点权重,b2的取值为1到z(v),z(v)为第v个起始节点对应的候选节点序列集中的节点数量。