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

摘要:

权利要求书:

1.一种结合过站松弛时间与航班延误的航班环编排方法,其特征在于,所述方法包括如下步骤:S100,基于待处理的航班任务信息表,获取初始的任务节点集;其中,初始的任务节点集中的一个节点对应一个航班任务;

S200,基于贪心算法,从初始的任务节点集中获取满足预设约束条件的初始任务节点序列集合,并将初始任务节点序列集合中的任务节点从初始的任务节点集中删除,得到初始的待处理任务节点列表;设置迭代次数计数器c=1;

S300,如果c≤c0或者当前的节点序列集合记录集对应的目标函数值满足收敛条件,执行S600,否则,执行S400;当前的节点序列集合记录集的初始值为初始任务节点序列集合;

c0为预设次数阈值;其中,每个任务节点序列的目标函数值用于表征该任务节点序列所需求的资源需求值,每个任务节点序列的资源需求值基于对应的任务节点对应的停留松弛时间和延误时间确定;

S400,基于序列破坏方法和序列重构方法,对当前的任务节点序列集合进行更新,得到更新后的任务节点序列集合,并加入当前的节点序列集合记录集中;当前的任务节点序列集合的初始值为初始任务节点序列集合,执行S500;

S500,基于预设更新结果接收规则,从当前的任务节点序列集合和更新后的任务节点序列集合中选择一个作为新的当前的任务节点序列集合;设置c=c+1,执行S300;

S600,将当前的节点序列集合记录集中具有最小资源需求值的任务节点序列集合作为目标任务节点序列集合,并退出当前控制程序。

2.根据权利要求1所述的方法,其特征在于,S400具体包括:

S401,获取当前的任务节点序列集合中的每个任务节点序列对应的目标函数值,并将具有最大目标函数值的任务节点序列从当前的任务节点序列集合中删除,并加入当前的待处理任务节点列表中;

S402,基于每种序列破坏方法和每种序列重构方法的当前优先级,获取当前需要选择的序列破坏方法和序列重构方法,分别作为当前序列破坏方法和当前序列重构方法;

S403,对于当前的任务节点序列集合中的任一个任务节点序列,利用当前序列破坏方法和当前序列重构方法对该任务节点序列进行更新;得到当前的任务节点序列集合对应的更新后的任务节点序列集合,并存入当前的节点序列集合记录集中;

其中,S403具体包括:利用当前序列破坏方法对该任务节点序列进行破坏操作,得到破坏后的任务节点序列,作为当前待重构任务节点序列,以及利用当前序列重构方法对当前待重构任务节点序列进行重构操作,得到重构后的任务节点序列;

其中,破坏操作用于将需要破坏的任务节点序列中的至少一个任务节点从对应任务节点序列中删除并加入当前的待处理任务节点列表中,重构操作用于利用当前的待处理任务节点列表中的任务节点对执行了破坏操作后的任务节点序列进行重构。

3.根据权利要求2所述的方法,其特征在于,每种序列破坏方法的当前优先级满足如下条件:m

P(d)i=WDi/∑j=1WDj;

P(d)i为第i种序列破坏方法的当前优先级,WDi为第i种序列破坏方法的当前权重,i的取值为1到m,m为序列破坏方法的数量,WDj为第j种序列破坏方法的当前权重,j的取值为1到m;

每种序列重构方法的当前优先级满足如下条件:

n

P(r)u=WRu/∑v=1WRv;

P(r)u为第u种序列重构方法的当前优先级,WRu为第u种序列重构方法的当前权重,u的取值为1到n,n为序列重构方法的数量,WRv为第v种序列重构方法的当前权重,v的取值为1到n。

4.根据权利要求3所述的方法,其特征在于,WDi满足如下条件:

last

WDi=(1‑φ)WDi +φ(g1i/t)i ;

last

其中,φ为更新系数,WDi 为第i种序列破坏方法在上一次迭代中的权重,g1i为第i种序列破坏方法的累计分值,ti为第i种序列破坏方法被选中的次数;

WRu满足如下条件:

last

WRu=(1‑φ)WRu +φ(g2u/t)u ;

last

其中,WRu 为第u种序列重构方法在上一次迭代中的权重,g2u为第u种序列重构方法的累计分值,tu为第u种序列重构方法被选中的次数。

5.根据权利要求4所述的方法,其特征在于,任一序列破坏方法或任一序列重构方法的累计分值满足如下条件:如果在某次迭代过程中,基于该序列破坏方法或该序列重构方法得到的更新后的任务节点序列集合对应的目标函数值等于当前最优目标函数值,设置该序列破坏方法或该序列重构方法的当前累计分值增加第一分值;当前最优目标函数值为当前的节点序列集合记录集中对应的所有任务节点序列集合对应的目标函数值中的最小者;

如果基于该序列破坏方法或该序列重构方法得到的更新后的任务节点序列集合对应的目标函数值大于当前最优目标函数值,设置该序列破坏方法或序列重构方法的当前累计分值增加第二分值;

如果基于某个序列破坏方法或序列重构方法得到的更新后的任务节点序列集合对应的目标函数值小于当前最优目标函数值,但该更新后的任务节点序列集合被选择作为新的当前的任务节点序列集合,设置该序列破坏方法或该序列重构方法的当前累计分值增加第三分值。

6.根据权利要求1所述的方法,其特征在于,S500具体包括:

如果更新后的任务节点序列集合对应的目标函数值小于当前最优目标函数值,选择该更新后的任务节点序列集合作为新的当前的任务节点序列集合;当前最优目标函数值为当前的节点序列集合记录集中对应的所有任务节点序列集合对应的目标函数值中的最小者;

如果更新后的任务节点序列集合对应的目标函数值大于等于当前的任务节点序列集合对应的目标函数值,基于当前的任务节点序列集合对应的目标函数值和该更新后的任务节点序列集合对应的目标函数值确定新的当前的任务节点序列集合。

7.根据权利要求6所述的方法,其特征在于,所述基于当前的任务节点序列集合对应的目标函数值和该更新后的任务节点序列集合对应的目标函数值确定新的当前的任务节点序列集合,具体包括:基于当前的任务节点序列集合对应的目标函数值和该更新后的任务节点序列集合对应的目标函数值,获取该更新后的任务节点序列集合的当前选择值P;

如果P≥P0,选择该更新后的任务节点序列集合作为新的当前的任务节点序列集合,否则,选择当前的任务节点序列集合作为新的当前的任务节点序列集合,P0为设定选择值阈值。

8.根据权利要求7所述的方法,其特征在于,P满足如下条件:

‑(F(new)‑F(cur))/T(cur)

P=e ;

其中,F(new)为更新后的任务节点序列集合对应的目标函数值,F(cur)为当前的任务节点序列集合对应的目标函数值,T(cur)为当前的调节系数。

9.根据权利要求2所述的方法,其特征在于,包括第一序列破坏方法和第二序列破坏方法,其中,第一序列破坏方法用于从当前任务节点序列中随机选择一个任务节点作为目标破坏任务节点,并将该目标破坏任务节点及其后续任务节点加入到当前的待处理任务节点列表中,第二序列破坏方法用于将当前任务节点序列中具有最大停留时间的任务节点及其后续任务节点加入到当前的待处理任务节点列表中。

10.根据权利要求2所述的方法,其特征在于,包括第一序列重构方法和第二序列重构方法,第一序列重构方法用于基于贪心算法从当前的待处理任务节点列表中选择任务节点对被破坏的任务节点序列进行重构,第二序列重构方法用于基于动态规划算法从当前的待处理任务节点列表中选择任务节点对被破坏的任务节点序列进行重构。