一种航班调度方法和装置的制造方法

一种航班调度方法和装置的制造方法
【技术领域】
[0001] 本发明实施例设及信息技术，尤其设及一种航班调度方法和装置。
【背景技术】
[0002] 随着我国空中交通运输事业取得的发展，飞行流量快速增加，枢纽机场W及主干 航路的容量日渐饱和，空中交通拥堵现象逐步加剧，导致大面积航班延误，不但造成巨大的 经济损失，而且严重影响飞行运行安全，已成为影响我国航空运输业发展的焦点问题。解 决空中交通拥堵问题最有效、最经济的手段是空中交通流量管理，即通过先期的航班计划 优化和实时的飞行流量控制等措施，减少不同航班对有限的航路资源和时刻资源的使用冲 突，进而保障空中交通系统的安全、有序、顺畅地运行。
[0003] 智能优化算法（Intelligent Optimization Algorithm)，又称智能计算 (Intelligent Computation)，是通过模拟或揭示某些自然现象或过程发展而来的优化算 法，其中的粒子群算法（Particle Swarm化timization，简称PS0)是一种模仿鸟类群体行 为的智能优化算法，基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。
[0004] 基本PS0算法由于采用全联通网络结构，其获取结果的收敛速度较慢。

【发明内容】

[0005] 本发明实施例提供一种航班调度方法和装置，W克服现有技术中获取结果的速度 较慢的问题。
[0006] 本发明实施例的第一方面提供一种航班调度方法，包括：
[0007] 获取时间段T内在第一机场待降落的D架飞机的计划到达时间段和的空中等待成 本；其中，第d架飞机的计划到达时间段为A(d)，第d架飞机的空中等待成本为Ca化At)， At为空中等待时长，时间段T包括m个安全着陆时间段Ti、T2、…、Tm，A(d)为Ti、T2、…、 Tm中的一个时间段，dG[1，D];
[000引随机生成X个粒子，并根据无标度网络的产生机制建立初始状态各个粒子的网络 拓扑；其中，X大于D，每个粒子包括D维位置矢量和D维速度矢量，所述D维位置矢量中的 第d个元素为第d架飞机的着陆时间段L(d)，且L(d)大于等于A(d)，所述D维速度矢量中 的第d个元素为第d架飞机的着陆时间段的迭代改变量；所述各个粒子中的第i个粒子的 网络拓扑包括第i个粒子与所述X个粒子中除该粒子之外的其他粒子之间的相邻关系；根 据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒子当前的位置矢 量对应的航班总延误成本，确定各个粒子当前的位置矢量对应的航班总延误成本为各个粒 子的初始的自身历史最好位置；根据各个粒子的当前的位置矢量对应的航班总延误成本和 所述初始状态各个粒子的网络拓扑，确定各个粒子的邻居最好位置和所述X个粒子的全局 最好位置；其中，第i个粒子的邻居最好位置为当前与第i个粒子直接相邻的粒子的自身历 史最好位置中对应的航班总延误成本最小的粒子的自身历史最好位置；所述X个粒子的全 局历史最好位置为所述X个粒子的当前自身历史最好位置中对应的航班总延误成本最小 的自身历史最好位置；
[0009] 开始迭代过程，所述迭代过程包括（1)至（3);
[0010] (1)分别根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒子的速 度矢量；分别根据各个粒子的更新后的速度矢量，更新各个粒子的位置矢量；
[0011] (2)根据更新后的各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒 子当前的位置矢量对应的航班总延误成本，并根据由更新后的各个粒子的位置矢量计算的 各个粒子的航班总延误成本，确定各个粒子的自身历史最好位置、邻居最好位置和所述X 个粒子的全局历史最好位置；其中，第i个粒子的自身历史最好位置为在迭代过程中第i个 粒子的所有位置矢量中对应的航班总延误成本最小的位置矢量；
[0012] (3)判断本次迭代是否达到迭代终止条件，若达到所述迭代终止条件，则确定当前 全局历史最好位置中的D个元素为所述待着陆飞机中各架飞机的着陆时间段，停止迭代过 程；若未达到所述迭代终止条件，则进一步判断本次迭代是否达到拓扑自适应调整口限，若 本次迭代达到所述拓扑自适应调整口限，则对各个粒子的网络拓扑进行调整；所述调整包 括；选择当前所述X个粒子中自身历史最好位置对应的航班总延误成本最小的P个第一粒 子和所述X个粒子中自身历史最好位置对应的航班总延误成本最大的Q个第二粒子，对每 个所述第一粒子，随机选择第一边调整个数个第=粒子，增加第一粒子与每个第=粒子之 间的相邻关系，对每个所述第二粒子，在与所述第二粒子直接相邻的粒子中，随机选择第二 边调整个数个第四粒子，删除第二粒子与每个第四粒子之间的相邻关系，执行（1);
[0013] 分别将所述待着陆飞机中的各架飞机的着陆时间段发送给对应的飞机。
[0014] 进一步地，所述根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本， 计算各个粒子的当前的位置矢量对应的航班总延误成本，包括：
[0015] 根捐
I计算第i个粒子的当前的位置矢量对应的航班总延 误成本；
[0016] 其中，L,(d)为初始状态第i个粒子的位置矢量中的第d架飞机的着陆时间段， A(d)为第d架飞机的计划到达时间段，Ca化At)为第d架飞机空中等待时长为At时的 成本；
[0017] 所述根据更新后的各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒 子当前的位置矢量对应的航班总延误成本，并根据由更新后的各个粒子的位置矢量计算的 各个粒子的航班总延误成本，包括：
[0018] 根据
计算第i个粒子的当前位置矢量对应的航班总延误 成本；
[0019] 其中，Li(d)为更新后的第i个粒子的位置矢量中的第d架飞机的着陆时间段， A(d)为第d架飞机的计划到达时间段，Ca化At)为第d架飞机空中等待时长为At时的 成本。
[0020] 进一步地，所述分别根据各个粒子的自身历史最好位置和邻居最好位置，更新各 个粒子的速度矢量，分别根据各个粒子的更新后的速度矢量更新各个粒子的位置矢量，具 体包括：
[0021] 对于每一个粒子，依次根据
[00巧V"二乂小'/'+('iX/;x0V' -x/) + ￡']xr]X(八/ -A'/'：)]更新第i个粒子的速度矢量 中的第d个元素，dG[1，D];其中，vf，胃为第i个粒子的第d个元素更新后的速度矢量， vf为第i个粒子的第d个元素更新前的速度矢量，Pid为第i个粒子的历史最好位置Pi的 第d个元素，Pgd为第i个粒子的历史邻居最好位置的第d个元素，C1为预设的自我学习因 子，C2为预设的社会学习因子，ri和r2为[Oa]间的随机数；X为预设的收缩因子；
[0023] 对于每一个粒子，依次根据xf胃=x/+v/更新第i个粒子的位置矢量中的第d个 元素，dG[1，D];其中，第i个粒子的第d个元素更新后的位置矢量，x/第i个粒子 的第d个元素更新前的位置矢量。
[0024] 进一步地，所述第一机场在Ti、T2、…、Tm时间段的可用跑道容量分别为C1、C2、…、 Cm，则
[0025] 对于初始状态随机生成的任一粒子中的位置矢量中的D个元素对应的D架飞机的 着陆时间W及在迭代过程中的任一粒子更新后的位置矢量中的D个元素对应的D架飞机的 着陆时间满足第一约束条件，所述第一约束条件具体包括：
[0026] 在Ti、T2、…、Tm各个时间段着陆的飞机的数量小于各个时间段的可用跑道容量； 其中，所述第一机场在时间段T内的可用跑道次大于X。
[0027] 进一步地，所述随机选择第一边调整个数个第=粒子，增加第一粒子与每个第= 粒子之间的相邻关系，具体包括：
[002引在与所述第一粒子不直接相邻的粒子中，随机选择第一边调整个数个第=粒子， 增加第一粒子与每个第=粒子之间的相邻关系；
[0029] 所述在与所述第二粒子直接相邻的粒子中，随机选择第二边调整个数个第四粒 子，删除第二粒子与每个第四粒子之间的相邻关系，还具体包括：
[0030] 若与所述第二粒子直接相邻的粒子的个数小于或等于所述第二边调整个数，则在 与所述第二粒子相邻的粒子中，随机删除第=边调整个数个第四粒子与所述第二粒子之间 的相邻关系，所述第=边调整个数为与所述第二粒子直接相邻的粒子的个数减一。
[0031] 进一步地，所述选择所述X个粒子中自身历史最好位置对应的航班总延误成本最 小的P个第一粒子和所述X个粒子中自身历史最好位置对应的航班总延误成本最大的Q个 第二粒子，包括：
[0032] 根据预设的第一调整概率，选择所述X个粒子中自身历史最好位置对应的航班总 延误成本最小的P个第一粒子；根据预设的第二调整概率选择所述X个粒子中自身历史最 好位置对应的航班总延误成本最大的Q个第二粒子；
[0033] 进一步地，P等于X与所述第一调整概率的乘积；Q等于X与所述第二调整概率的 乘积。
[0034] 进一步地，所述第一预设调整概率等于所述第二预设调整概率。
[0035]本发明实施例的第二方面提供一种航班调度装置，包括：
[0036] 获取模块，用于获取时间段T内在第一机场待降落的D架飞机的计划到达时间段 和空中等待成本；其中，第d架飞机的计划到达时间段为A(d) ，第d架飞机的空中等待成本 为Ca(d，At)，At为空中等待时长，时间段T包括m个安全着陆时间段Ti、T2、…、Tm，A(d) 为VT2、…、Tm中的一个时间段，dG[1，D];
[0037] 处理模块，用于随机生成X个粒子，并根据无标度网络的产生机制建立初始状态 各个粒子的网络拓扑；其中，X大于D，每个粒子包括D维位置矢量和D维速度矢量，所述D 维位置矢量中的第d个元素为第d架飞机的着陆时间段L(d)，且L(d)大于等于A(d)，所述 D维速度矢量中的第d个元素为第d架飞机的着陆时间段的迭代改变量；所述各个粒子中 的第i个粒子的网络拓扑包括第i个粒子与所述X个粒子中除该粒子之外的其他粒子之间 的相邻关系；根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒 子当前的位置矢量对应的航班总延误成本，确定各个粒子当前的位置矢量对应的航班总延 误成本为各个粒子的初始的自身历史最好位置；根据各个粒子的当前的位置矢量对应的航 班总延误成本和所述初始状态各个粒子的网络拓扑，确定各个粒子的邻居最好位置和所述 X个粒子的全局最好位置；其中，第i个粒子的邻居最好位置为当前与第i个粒子直接相邻 的粒子的自身历史最好位置中对应的航班总延误成本最小的粒子的自身历史最好位置；所 述X个粒子的全局历史最好位置为所述X个粒子的当前自身历史最好位置中对应的航班总 延误成本最小的自身历史最好位置；开始迭代过程，所述迭代过程包括（1)至（3) ;(1)分 别根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒子的速度矢量；分别根 据各个粒子的更新后的速度矢量，更新各个粒子的位置矢量；（2)根据更新后的各个粒子 的位置矢量和各个飞机的空中等待成本，计算各个粒子当前的位置矢量对应的航班总延误 成本，并根据由更新后的各个粒子的位置矢量计算的各个粒子的航班总延误成本，确定各 个粒子的自身历史最好位置、邻居最好位置和所述X个粒子的全局历史最好位置；其中，第 i个粒子的自身历史最好位置为在迭代过程中第i个粒子的所有位置矢量中对应的航班总 延误成本最小的位置矢量；（3)判断本次迭代是否达到迭代终止条件，若达到所述迭代终 止条件，则确定当前全局历史最好位置中的D个元素为所述待着陆飞机中各架飞机的着陆 时间段，停止迭代过程；若未达到所述迭代终止条件，则进一步判断本次迭代是否达到拓扑 自适应调整口限，若本次迭代达到所述拓扑自适应调整口限，则对各个粒子的网络拓扑进 行调整；所述调整包括；选择当前所述X个粒子中自身历史最好位置对应的航班总延误成 本最小的P个第一粒子和所述X个粒子中自身历史最好位置对应的航班总延误成本最大的 Q个第二粒子，对每个所述第一粒子，随机选择第一边调整个数个第=粒子，增加第一粒子 与每个第=粒子之间的相邻关系，对每个所述第二粒子，在与所述第二粒子直接相邻的粒 子中，随机选择第二边调整个数个第四粒子，删除第二粒子与每个第四粒子之间的相邻关 系，执行（1);
[003引发送模块，用于分别将所述待着陆飞机中的各架飞机的着陆时间段发送给对应的 飞机。
[0039] 本发明实施例提供的一种航班调度方法，通过本发明实施例提供的一种航班调度 方法，通过在根据航班计划到达时间和各飞机的空中等待成本确定各航班的着陆时间时， 采用无标度网络的产生机制生成各航班着陆时间的粒子群网络拓扑，由于无标度网络的异 质性特点，保证了粒子种群网络拓扑的多样性，并在迭代的过程中，增加航班等待成本最小 的P个粒子与网络拓扑中其他粒子的连接，同时减少航班等待成本最大的Q个粒子与网络 拓扑中其他粒子的连接，由于增加了距离最优航班调度时间结果最近的粒子的连接权重， 降低了距离最优航班调度时间结果最远的粒子的连接权重，使得最终获得的航班着陆时间 的结果的收敛时间缩短，提升了确定各航班的着陆时间的效率。
【附图说明】
[0040] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现 有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发 明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可W 根据该些附图获得其他的附图。
[0041] 图1为本发明提供的一种航班调度方法实施例一的流程图；
[0042] 图2为本发明提供的一种航班调度装置的结构示意图。
【具体实施方式】
[0043] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例 中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是 本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员 在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0044] 航班调度的应用场景通常是有若干架飞机在一段时间内W-定的顺序到达某一 机场上空后，需要按照一定的顺序着陆，如何安排飞机的着陆时序同时使得总的航班总等 待成本最小成本航班调度需要解决的问题。本发明实施例提供了一种航班调度方法和装 置。本发明提供的航班调度方法和装置的各个实施例的应用场景包括第一机场和D架飞 机，下面对本发明提供的航班调度方法和装置的实施方式进行具体说明。
[0045] 图1为本发明提供的一种航班调度方法实施例一的流程示意图。
[0046] 如图1所示，本实施例的步骤可W包括：
[0047] S101、获取时间段T内在第一机场待降落的D架飞机的计划到达时间段和空中等 待成本。
[0048] 其中，第d架飞机的计划到达时间段为A(d)，第d架飞机的空中等待成本为 Ca(d，At)，At为空中等待时长，时间段T包括m个安全着陆时间段Ti、T2、…、Tm，A(d)为 了1、了2、…、Tm中的一个时间段，dG[1，D]。
[0049] 可选的，每个时间段Ti、T2、…、Tm可W等于飞机着陆时间，或者，考虑异常状态时 需要的安全处理时间，每个时间段可W等于飞机着陆时间与安全处理时间的和。
[0化0] 还需要说明的是，本发明提供的航班调度方法也可W应用其他交通工具的调度场 景，例如火车进站的场景，相应的，本发明实施例中的各个飞机的空中等待成本可W转换为 考虑火车的进站等待成本，又如，轮船进入港口或者通过渡口的场景，相应的，飞机的空中 等待成本可W转换为考虑轮船的水上等待成本。
[0化1] S102、随机生成X个粒子，并根据无标度网络的产生机制建立初始状态各个粒子 的网络拓扑。
[0052] 其中，X大于D，每个粒子包括D维位置矢量和D维速度矢量，所述D维位置矢量中 的第d个元素为第d架飞机的着陆时间段L(d)，且L(d)大于等于A(d)，所述D维速度矢量 中的第d个元素为第d架飞机的着陆时间段的迭代改变量；所述各个粒子中的第i个粒子 的网络拓扑包括第i个粒子与所述X个粒子中除该粒子之外的其他粒子之间的相邻关系。 举例来说，所述X个粒子的网络拓扑中，任两个粒子之间的相邻关系可W包括直接相邻和 不直接相邻两种。
[0化3] 需要说明的是，采用所述无标度网络的产生机制生成网络拓扑通常可W包括"增 长节点"和"优先连接"两个步骤，即从一个具有3。(3。〉1)个节点的连通网络开始，每次引入 一个新的节点，并且连接到S个已存在的节点上，该里S小于或等于S。;一个新节点与一个 已经存在的节点j相连接的概率Pj与节点j的度Kj.满足如下关系：
[0054] Pj.=K/SfKf，其中，Kj为节点j的度。节点的度是指与节点直接相邻的其他节点 的个数。
[0055] 对于本发明实施例来说，可W具体采用如下方式建立初始状态所述X个粒子的网 络拓扑：
[0化6] 在所述X个粒子随机选择3。= 2个粒子作为初始连通网络的2个节点，每次从X个粒子中剩余的粒子中选择一个新的粒子作为一个新的节点，并将其连接到已存在的S个 节点上，S小于或等于S。，该新节点与已经存在的节点j直接相邻的概率Pj与节点j的度KJ 满足如下关系：
[0057] Pj=K/XfKf，其中，Kj为节点j的度。
[005引按照无标度网络的产生机制的特性是网络中各节点的度的分布服从幕率分布，即 少量的节点（相当于中屯、节点）具有大量的连边，类似于全连通网络中的节点，而大量的节 点（相当于非中屯、节点）的连边较少，类似于环形网络中的节点。因此，无标度网络具有较 强的异质性。该样的网络拓扑结构能加强粒子种群的多样性，使得采用本发明提供的航班 调度方法获得的结果不易陷入局部最优。
[0059] 可选的，所述第一机场在Ti、T2、…、Tm时间段的可用跑道容量可W分别为Cl、 〔2、…、Cm，则
[0060] 对于初始状态随机生成的任一粒子中的位置矢量中的D个元素对应的D架飞机的 着陆时间可W满足第一约束条件，所述第一约束条件具体包括：
[0061] 在Ti、T2、…、Tm各个时间段着陆的飞机的数量小于各个时间段的可用跑道容量； 其中，所述第一机场在时间段T内的可用跑道次大于X。
[0062] 可选的，考虑各个飞机能够容忍的延后时长是有限的，初始状态随机生成的各个 粒子中的位置矢量应满足第二约束条件，所述第二约束条件包括：
[0063] 初始状态中各个粒子的位置矢量对应的各个飞机的着陆时间与到达时间的差值 小于航班降落顺序延后理性容忍度。
[0064] 举例来说， 即Z,(d)-A(d) <T(d)，其中，Z,(d)为初始状态的第i个粒子中第d架飞 机的着陆时间，A(d)为第d架飞机的计划到达时间，T(d)为第d架飞机的航班降落顺序延 后理性容忍度。
[00化]S103、根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算各个 粒子当前的位置矢量对应的航班总延误成本，确定各个粒子当前的位置矢量对应的航班总 延误成本为各个粒子的初始的自身历史最好位置。
[0066] 其中，所述根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算 各个粒子的当前的位置矢量对应的航班总延误成本，可W包括：
[0067] 根捉i兵,(d，L,(d)-A(d))计算第i个粒子的当前的位置矢量对应的航班总延 d=\ 误成本；其中，为初始状态第i个粒子的位置矢量中的第d架飞机的着陆时间段， A(d)为第d架飞机的计划到达时间段，Ca化At)为第d架飞机空中等待时长为At时的 成本。
[0068] S104、根据各个粒子的当前的位置矢量对应的航班总延误成本和所述初始状态各 个粒子的网络拓扑，确定各个粒子的邻居最好位置和所述X个粒子的全局最好位置。
[0069] 其中，第i个粒子的邻居最好位置为当前与第i个粒子直接相邻的粒子的自身历 史最好位置中对应的航班总延误成本最小的粒子的自身历史最好位置；所述X个粒子的全 局历史最好位置为所述X个粒子的当前自身历史最好位置中对应的航班总延误成本最小 的自身历史最好位置。
[0070] S105至S107为迭代过程的具体步骤，所述迭代过程包括：
[0071] S105、分别根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒子的 速度矢量；分别根据各个粒子的更新后的速度矢量，更新各个粒子的位置矢量。
[0072] 其中，所述分别根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒 子的速度矢量，分别根据各个粒子的更新后的速度矢量更新各个粒子的位置矢量，可W具 体包括：
[0073] 对于每一个粒子，依次根据
[0074] vfnew= 乂小'严+qX/;X(^ -.Y,/') +C'2 X(代'/ 更新第i个粒子的速度矢量 中的第d个元素，dG[1，D];其中，为第i个粒子的第d个元素更新后的速度矢量， vf为第i个粒子的第d个元素更新前的速度矢量，Pid为第i个粒子的历史最好位置Pi的 第d个元素，Pgd为第i个粒子的历史邻居最好位置的第d个元素，C1为预设的自我学习因 子，C2为预设的社会学习因子，ri和r2为[oa]间的随机数；X为预设的收缩因子。
[007引对于每一个粒子，依次根据自。。" = +v/更新第i个粒子的位置矢量中的第d 个元素，dG[1，D];其中，xf第i个粒子的第d个元素更新后的位置矢量，X:'第i个粒 子的第d个元素更新前的位置矢量。
[0076] 需要说明的是，所述预设的收敛因子可W用于控制获取结果的收敛速度。
[0077] 可选的，Ci=C2= 2. 05，X= 0. 7298。
[007引可选的，当所述第一机场在VT2、…、Tm时间段的可用跑道容量分别为C1、C2、…、Cm时，在迭代过程中的任一粒子更新后的位置矢量中的D个元素对应的D架飞机的着陆时 间应满足上述的第一约束条件。
[0079] 可选的，考虑各个飞机能够容忍的延后时长是有限的，在迭代过程中各个粒子更 新后的位置矢量应满足类似上述第二约束条件的第=约束条件，所述第=约束条件可W包 括：
[0080] 更新后的各个粒子的位置矢量对应的各个飞机的着陆时间与到达时间的差值小 于航班降落顺序延后理性容忍度。
[OOW] 举例来说，即Li(d)-A(d) <T(d)，其中，Li(d)为更新后的第i个粒子中第d架飞 机的着陆时间，A(d)为第d架飞机的计划到达时间，T(d)为第d架飞机的航班降落顺序延 后理性容忍度。
[0082]S106、根据更新后的各个粒子的位置矢量和各个飞机的空中等待成本，计算各个 粒子当前的位置矢量对应的航班总延误成本，并根据由更新后的各个粒子的位置矢量计算 的各个粒子的航班总延误成本，确定各个粒子的自身历史最好位置、邻居最好位置和所述X 个粒子的全局历史最好位置。
[0083] 其中，第i个粒子的自身历史最好位置为在迭代过程中第i个粒子的所有位置矢 量中对应的航班总延误成本最小的位置矢量；所述X个粒子的全局历史最好位置为当前所 述X个粒子的自身历史最好位置中对应的航班总延误成本最小的自身历史最好位置。
[0084] 可选的，所述根据更新后的各个粒子的位置矢量和各个飞机的空中等待成本，计 算各个粒子当前的位置矢量对应的航班总延误成本，并根据由更新后的各个粒子的位置矢 量计算的各个粒子的航班总延误成本，可W包括：
[0085] 根据^
计算第i个粒子的当前位置矢量对应的航班总延误 成本；其中，Li(d)为更新后的第i个粒子的位置矢量中的第d架飞机的着陆时间段，A(d) 为第d架飞机的计划到达时间段，Ca化At)为第d架飞机空中等待时长为At时的成本。
[0086]S107、判断本次迭代是否达到迭代终止条件，若达到所述迭代终止条件，执行 S108,若未到达所述迭代终止条件，执行S109。
[0087] 可选的，所述迭代终止条件可W为最大迭代次数，如1000次，当达到最大迭代次 数时，结束迭代。
[008引 S108、确定当前全局历史最好位置中的D个元素为所述待着陆飞机中各个飞机的 着陆时间段，停止迭代过程，执行S110。
[0089]S109、判断本次迭代是否达到拓扑自适应调整口限，若本次迭代达到所述拓扑自 适应调整口限，则对各个粒子的网络拓扑进行调整；所述调整包括；选择当前所述X个粒子 中自身历史最好位置对应的航班总延误成本最小的P个第一粒子和所述X个粒子中自身历 史最好位置对应的航班总延误成本最大的Q个第二粒子，对每个所述第一粒子，随机选择 第一边调整个数个第=粒子，增加第一粒子与每个第=粒子之间的相邻关系，对每个所述 第二粒子，在与所述第二粒子直接相邻的粒子中，随机选择第二边调整个数个第四粒子，删 除第二粒子与每个第四粒子之间的相邻关系，执行S105。
[0090] 其中，为了防止在直接相邻的粒子间增加的相邻关系，所述随机选择第一边调整 个数个第=粒子，增加第一粒子与每个第=粒子之间的相邻关系，可W具体包括：
[0091] 在与所述第一粒子不直接相邻的粒子中，随机选择第一边调整个数个第=粒子， 增加第一粒子与每个第=粒子之间的相邻关系。
[0092] 相应地，为了防止第二粒子在删除相邻关系后成为孤立的节点，即该第二粒子与 其他粒子均不直接相邻，所述在与所述第二粒子直接相邻的粒子中，随机选择第二边调整 个数个第四粒子，删除第二粒子与每个第四粒子之间的相邻关系，还具体包括：
[0093] 若与所述第二粒子直接相邻的粒子的个数小于或等于所述第二边调整个数，则在 与所述第二粒子相邻的粒子中，随机删除第=边调整个数个第四粒子与所述第二粒子之间 的相邻关系，所述第=边调整个数为与所述第二粒子直接相邻的粒子的个数减一。
[0094] 可选的，若与所述第一粒子不直接相邻的粒子的个数小于所述第一边调整个数， 则所述随机选择第一边调整个数个第=粒子，增加第一粒子与每个第=粒子之间的相邻关 系，还可W具体包括：
[0095] 增加所有与第一粒子不直接相邻的粒子与所述第一粒子之间的相邻关系。
[0096] 需要说明的是，可选的，所述拓扑自适应调整口限可W为一预设的迭代次数，且所 述预设的迭代次数应小于所述迭代终止条件设置的迭代次数，例如，迭代终止条件为迭代 次数等于1000次时，拓扑自适应调整口限的迭代次数可W设置为迭代次数等于100次。
[0097] S110、分别将所述待着陆飞机中的各架飞机的着陆时间段发送给对应的飞机。
[0098] 其中，将第d架飞机的着陆时间段L(d)发送给第d架飞机，dG[1，D]。
[0099] 本发明实施例提供的一种航班调度方法，通过在根据航班计划到达时间和各飞机 的空中等待成本确定各航班的着陆时间时，采用无标度网络的产生机制生成各航班着陆时 间的粒子群网络拓扑，由于无标度网络的异质性特点，保证了粒子种群网络拓扑的多样性， 并在迭代的过程中，增加航班等待成本最小的P个粒子与网络拓扑中其他粒子的连接，同 时减少航班等待成本最大的Q个粒子与网络拓扑中其他粒子的连接，由于增加了距离最优 航班调度时间结果最近的粒子的连接权重，降低了距离最优航班调度时间结果最远的粒子 的连接权重，使得最终获得的航班着陆时间的结果的收敛时间缩短，提升了确定各航班的 着陆时间的效率。同时，还避免了采用规则网络的粒子群网络拓扑而导致的获取的航班着 陆时间结果陷入局部最优的问题。
[0100] 本发明实施例提供的航班调度方法还提供另一种可选的实施方式。
[0101] 与图1所示方法不同的是，本实施例的方法可W包括：
[0102] S103中所述根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算 各个粒子当前的位置矢量对应的航班总延误成本，可W具体包括：
[0103] 根据初始状态各个粒子的位置矢量、各个飞机的空中等待成本和公平 性惩罚因 子，计算各个粒子当前的位置矢量对应的航班总延误成本。
[0104] 可选的，可W根据
计算第i个粒 子的当前的位置矢量对应的航班总延误成本。
[01化]其中，L,.(d)为初始状态第i个粒子的位置矢量中的第d架飞机的着陆时间段， A(d)为第d架飞机的计划到达时间段，Ca化At)为第d架飞机空中等待时长为At时的 成本，Cp"为公平性惩罚因子。
[0106] 可选的，公平性惩罚因子可W根据D种类型飞机的航班平均运行成本、各个飞机 的到达时间、着落时间、飞机的航班降落顺序延后理性容忍度确定。
[0107] 举例来说，可W根据C计算 公平性惩罚因子。
[010引其中，Ca化At)为第d架飞机空中等待时长为At时的成本，k可W为航班公平 性惩罚成本增长指数，X可W为所有飞机的航班降落顺序延后理想容忍度，L,(d)可W为初 始状态第i个粒子的位置矢量中的第d架飞机的着陆时间段，A(d)可W为第d架飞机的计 划到达时间段，符号"「1 "表示符号内的数值大于等于1时有效，否则为0。
[0109] 相应地，S106中的所述根据更新后的各个粒子的位置矢量和各个飞机的空中等待 成本，计算各个粒子当前的位置矢量对应的航班总延误成本，可W具体包括：
[0110] 根据更新后的各个粒子的位置矢量、各个飞机的空中等待成本和公平性惩罚因 子，计算各个粒子当前的位置矢量对应的航班总延误成本。
[0111] 可选的，可W根据-
计算第i个 粒子的当前的位置矢量对应的航班总延误成本。
[0112] 其中，Li(d)为更新后的第i个粒子的位置矢量中的第d架飞机的着陆时间段， A(d)为第d架飞机的计划到达时间段，Ca化At)为第d架飞机空中等待时长为At时的 成本，Cp"为公平性惩罚因子。
[0113] 类似地，可W根据
计算公 平性惩罚因子。
[0114] 其中，Ca化At)为第d架飞机空中等待时长为At时的成本，k可W为航班公平 性惩罚成本增长指数，X可W为所有飞机的航班降落顺序延后理想容忍度，Li(d)可W为更 新后的第i个粒子的位置矢量中的第d架飞机的着陆时间段，A(d)可W为第d架飞机的计 划到达时间段，符号"「1 "表示符号内的数值大于等于1时有效，否则为0。
[0115] 本实施例的航班调度方法通过引入公平性惩罚因子确定各个粒子的位置矢量对 应的航班总等待成本，由于公平性惩罚因子的确定原则是飞机的空中等待时间越长，公平 性惩罚因子越大，使得在确定各个飞机的着陆时间时，若航班地面等待时间段增大时显著 增加总运行成本，从而有效的避免运输成本较小的航班无限制的被延迟起飞，保证航班获 得公平对待。
[0116] 图2为本发明实施例提供的一种航班调度装置的结构示意图。
[0117] 如图2所示，本实施例的航班调度装置1可W包括；获取模块10、处理模块11和 发送模块12。
[0118] 获取模块10,可W用于获取时间段T内在第一机场待降落的D架飞机的计划到达 时间段和空中等待成本；其中，第d架飞机的计划到达时间段为A(d)，第d架飞机的空中等 待成本为Cg化At)，At为空中等待时长，时间段T包括m个安全着陆时间段Ti、T2、…、Tm，A(d)为Ti、T2、…、Tm中的一个时间段，dG[1，D];
[0119] 处理模块11，用于随机生成X个粒子，并根据无标度网络的产生机制建立初始状 态各个粒子的网络拓扑；其中，X大于D，每个粒子包括D维位置矢量和D维速度矢量，所述 D维位置矢量中的第d个元素为第d架飞机的着陆时间段L(d)，且L(d)大于等于A(d)，所 述D维速度矢量中的第d个元素为第d架飞机的着陆时间段的迭代改变量；所述各个粒子 中的第i个粒子的网络拓扑包括第i个粒子与所述X个粒子中除该粒子之外的其他粒子之 间的相邻关系；根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算各个 粒子当前的位置矢量对应的航班总延误成本，确定各个粒子当前的位置矢量对应的航班总 延误成本为各个粒子的初始的自身历史最好位置；根据各个粒子的当前的位置矢量对应的 航班总延误成本和所述初始状态各个粒子的网络拓扑，确定各个粒子的邻居最好位置和所 述X个粒子的全局最好位置；其中，第i个粒子的邻居最好位置为当前与第i个粒子直接相 邻的粒子的自身历史最好位置中对应的航班总延误成本最小的粒子的自身历史最好位置； 所述X个粒子的全局历史最好位置为所述X个粒子的当前自身历史最好位置中对应的航班 总延误成本最小的自身历史最好位置；开始迭代过程，所述迭代过程包括（1)至（3) ;(1) 分别根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒子的速度矢量；分别 根据各个粒子的更新后的速度矢量，更新各个粒子的位置矢量；（2)根据更新后的各个粒 子的位置矢量和各个飞机的空中等待成本，计算各个粒子当前的位置矢量对应的航班总延 误成本，并根据由更新后的各个粒子的位置矢量计算的各个粒子的航班总延误成本，确定 各个粒子的自身历史最好位置、邻居最好位置和所述X个粒子的全局历史最好位置；其中， 第i个粒子的自身历史最好位置为在迭代过程中第i个粒子的所有位置矢量中对应的航班 总延误成本最小的位置矢量；(3)判断本次迭代是否达到迭代终止条件，若达到所述迭代 终止条件，则确定当前全局历史最好位置中的D个元素为所述待着陆飞机中各架飞机的着 陆时间段，停止迭代过程；若未达到所述迭代终止条件，则进一步判断本次迭代是否达到拓 扑自适应调整口限，若本次迭代达到所述拓扑自适应调整口限，则对各个粒子的网络拓扑 进行调整；所述调整包括；选择当前所述X个粒子中自身历史最好位置对应的航班总延误 成本最小的P个第一粒子和所述X个粒子中自身历史最好位置对应的航班总延误成本最大 的Q个第二粒子，对每个所述第一粒子，随机选择第一边调整个数个第=粒子，增加第一粒 子与每个第=粒子之间的相邻关系，对每个所述第二粒子，在与所述第二粒子直接相邻的 粒子中，随机选择第二边调整个数个第四粒子，删除第二粒子与每个第四粒子之间的相邻 关系，执行（1);
[0120] 发送模块12,可W用于分别将所述处理模块11确定的待着陆飞机中的各架飞机 的着陆时间段发送给对应的飞机。
[0121] 可选的，本发明实施例提供的航班调度装置可W用于执行上述各个实施例所示的 各种航班调度方法，其技术方案与技术效果与上述各个实施例类似，此处不再寶述。
[0122] 本领域普通技术人员可W理解；实现上述各方法实施例的全部或部分步骤可W通 过程序指令相关的硬件来完成。前述的程序可W存储于一计算机可读取存储介质中。该程 序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括；ROM、RAM、磁碟 或者光盘等各种可W存储程序代码的介质。
[0123] 最后应说明的是；W上各实施例仅用W说明本发明的技术方案，而非对其限制； 尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其 依然可W对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征 进行等同替换；而该些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技 术方案的范围。
【主权项】
1. 一种航班调度方法，其特征在于，包括： 获取时间段T内在第一机场待降落的D架飞机的计划到达时间段和空中等待成本；其 中，第d架飞机的计划到达时间段为A (d)，第d架飞机的空中等待成本为Ca (d，Λ t)，Λ t为 空中等待时长，时间段T包括m个安全着陆时间段I\、T2、…、Tm，A(d) Sl\、T2、…、^中 的一个时间段，d G [1，D]; 随机生成X个粒子，并根据无标度网络的产生机制建立初始状态各个粒子的网络拓 扑；其中，X大于D，每个粒子包括D维位置矢量和D维速度矢量，所述D维位置矢量中的第 d个元素为第d架飞机的着陆时间段L (d)，且L (d)大于等于A (d)，所述D维速度矢量中的 第d个元素为第d架飞机的着陆时间段的迭代改变量；所述各个粒子中的第i个粒子的网 络拓扑包括第i个粒子与所述X个粒子中除该粒子之外的其他粒子之间的相邻关系；根据 初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒子当前的位置矢量 对应的航班总延误成本，确定各个粒子当前的位置矢量对应的航班总延误成本为各个粒子 的初始的自身历史最好位置；根据各个粒子的当前的位置矢量对应的航班总延误成本和所 述初始状态各个粒子的网络拓扑，确定各个粒子的邻居最好位置和所述X个粒子的全局最 好位置；其中，第i个粒子的邻居最好位置为当前与第i个粒子直接相邻的粒子的自身历史 最好位置中对应的航班总延误成本最小的粒子的自身历史最好位置；所述X个粒子的全局 历史最好位置为所述X个粒子的当前自身历史最好位置中对应的航班总延误成本最小的 自身历史最好位置； 开始迭代过程，所述迭代过程包括（1)至（3): (1) 分别根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒子的速度矢 量；分别根据各个粒子的更新后的速度矢量，更新各个粒子的位置矢量； (2) 根据更新后的各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒子当 前的位置矢量对应的航班总延误成本，并根据由更新后的各个粒子的位置矢量计算的各个 粒子的航班总延误成本，确定各个粒子的自身历史最好位置、邻居最好位置和所述X个粒 子的全局历史最好位置；其中，第i 个粒子的自身历史最好位置为在迭代过程中第i个粒子 的所有位置矢量中对应的航班总延误成本最小的位置矢量； (3) 判断本次迭代是否达到迭代终止条件，若达到所述迭代终止条件，则确定当前全局 历史最好位置中的D个元素为所述待着陆飞机中各架飞机的着陆时间段，停止迭代过程； 若未达到所述迭代终止条件，则进一步判断本次迭代是否达到拓扑自适应调整门限，若本 次迭代达到所述拓扑自适应调整门限，则对各个粒子的网络拓扑进行调整；所述调整包括： 选择当前所述X个粒子中自身历史最好位置对应的航班总延误成本最小的P个第一粒子和 所述X个粒子中自身历史最好位置对应的航班总延误成本最大的Q个第二粒子，对每个所 述第一粒子，随机选择第一边调整个数个第三粒子，增加第一粒子与每个第三粒子之间的 相邻关系，对每个所述第二粒子，在与所述第二粒子直接相邻的粒子中，随机选择第二边调 整个数个第四粒子，删除第二粒子与每个第四粒子之间的相邻关系，执行（1); 分别将所述待着陆飞机中的各架飞机的着陆时间段发送给对应的飞机。2. 根据权利要求1所述的方法，其特征在于，所述根据初始状态各个粒子的位置矢量 和各个飞机的空中等待成本，计算各个粒子的当前的位置矢量对应的航班总延误成本，包 括： ^f算第i个粒子的当前的位置矢量对应的航班总延误成 本； 其中，i, (6(1)为初始状态第i个粒子的位置矢量中的第d架飞机的着陆时间段，A(d)为 第d架飞机的计划到达时间段，Ca (d，At)为第d架飞机空中等待时长为At时的成本； 所述根据更新后的各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒子当 前的位置矢量对应的航班总延误成本，并根据由更新后的各个粒子的位置矢量计算的各个 粒子的航班总延误成本，包括：}计算第i个粒子的当前位置矢量对应的航班总延误成 本； 其中山(d)为更新后的第i个粒子的位置矢量中的第d架飞机的着陆时间段，A(d)为 第d架飞机的计划到达时间段，Ca (d，At)为第d架飞机空中等待时长为At时的成本。3. 根据权利要求1所述的方法，其特征在于，所述分别根据各个粒子的自身历史最好 位置和邻居最好位置，更新各个粒子的速度矢量，分别根据各个粒子的更新后的速度矢量 更新各个粒子的位置矢量，具体包括： 对于每一个粒子，依次根据vf = Zx[vf +C1 x/〖-xf) +? x( p/ -彳)]更新 第i个粒子的速度矢量中的第d个元素，d e [1，D];其中，vf 为第i个粒子的第d个元 素更新后的速度矢量，< 为第i个粒子的第d个元素更新前的速度矢量，Pid为第i个粒子 的历史最好位置Pi的第d个元素，p gd为第i个粒子的历史邻居最好位置的第d个元素，c i 为预设的自我学习因子，C2为预设的社会学习因子，r JPr2S [0，1]间的随机数；X为预 设的收缩因子； 对于每一个粒子，依次根据_ = xf + v/更新第i个粒子的位置矢量中的第d个元 素，de [1，D];其中，xf 第i个粒子的第d个元素更新后的位置矢量，xf第i个粒子的 第d个元素更新前的位置矢量。4. 根据权利要求1所述的方法，其特征在于，所述第一机场在T i、T2、…、T#间段的 可用跑道容量分别为Q、C2、…、Cm，则 对于初始状态随机生成的任一粒子中的位置矢量中的D个元素对应的D架飞机的着陆 时间以及在迭代过程中的任一粒子更新后的位置矢量中的D个元素对应的D架飞机的着陆 时间满足第一约束条件，所述第一约束条件具体包括： 在T\、T2、…、Tm#个时间段着陆的飞机的数量小于各个时间段的可用跑道容量；其中， 所述第一机场在时间段T内的可用跑道次大于X。5. 根据权利要求1所述的方法，其特征在于， 所述随机选择第一边调整个数个第三粒子，增加第一粒子与每个第三粒子之间的相邻 关系，具体包括： 在与所述第一粒子不直接相邻的粒子中，随机选择第一边调整个数个第三粒子，增加 第一粒子与每个第三粒子之间的相邻关系； 所述在与所述第二粒子直接相邻的粒子中，随机选择第二边调整个数个第四粒子，删 除第二粒子与每个第四粒子之间的相邻关系，还具体包括： 若与所述第二粒子直接相邻的粒子的个数小于或等于所述第二边调整个数，则在与所 述第二粒子相邻的粒子中，随机删除第三边调整个数个第四粒子与所述第二粒子之间的相 邻关系，所述第三边调整个数为与所述第二粒子直接相邻的粒子的个数减一。6. 根据权利要求1-5任一所述的方法，其特征在于，所述选择所述X个粒子中自身历史 最好位置对应的航班总延误成本最小的P个第一粒子和所述X个粒子中自身历史最好位置 对应的航班总延误成本最大的Q个第二粒子，包括： 根据预设的第一调整概率，选择所述X个粒子中自身历史最好位置对应的航班总延误 成本最小的P个第一粒子；根据预设的第二调整概率选择所述X个粒子中自身历史最好位 置对应的航班总延误成本最大的Q个第二粒子。7. 根据权利要求6所述的方法，其特征在于，P等于X与所述第一调整概率的乘积；Q 等于X与所述第二调整概率的乘积。8. 根据权利要求6所述的方法，其特征在于，所述第一预设调整概率等于所述第二预 设调整概率。9. 一种航班调度装置，其特征在于，包括： 获取模块，用于获取时间段T内在第一机场待降落的D架飞机的计划到达时间段和空 中等待成本；其中，第d架飞机的计划到达时间段为A(d)，第d架飞机的空中等待成本为 Ca (d，At)，At为空中等待时长，时间段T包括m个安全着陆时间段InT2、…、Tm，A (d)为 1'1、1'2、一、1'"1中的一个时间段，(1￡[1，〇]; 处理模块，用于随机生成X个粒子，并根据无标度网络的产生机制建立初始状态各个 粒子的网络拓扑；其中，X大于D，每个粒子包括D维位置矢量和D维速度矢量，所述D维位 置矢量中的第d个元素为第d架飞机的着陆时间段L (d)，且L (d)大于等于A (d)，所述D维 速度矢量中的第d个元素为第d架飞机的着陆时间段的迭代改变量；所述各个粒子中的第 i个粒子的网络拓扑包括第i个粒子与所述X个粒子中除该粒子之外的其他粒子之间的相 邻关系；根据初始状态各个粒子的位置矢量和各个飞机的空中等待成本，计算各个粒子当 前的位置矢量对应的航班总延误成本，确定各个粒子当前的位置矢量对应的航班总延误成 本为各个粒子的初始的自身历史最好位置；根据各个粒子的当前的位置矢量对应的航班总 延误成本和所述初始状态各个粒子的网络拓扑，确定各个粒子的邻居最好位置和所述X个 粒子的全局最好位置；其中，第i个粒子的邻居最好位置为当前与第i个粒子直接相邻的 粒子的自身历史最好位置中对应的航班总延误成本最小的粒子的自身历史最好位置；所述 X个粒子的全局历史最好位置为所述X个粒子的当前自身历史最好位置中对应的航班总延 误成本最小的自身历史最好位置；开始迭代过程，所述迭代过程包括（1)至（3) :(1)分别 根据各个粒子的自身历史最好位置和邻居最好位置，更新各个粒子的速度矢量；分别根据 各个粒子的更新后的速度矢量，更新各个粒子的位置矢量；（2)根据更新后的各个粒子的 位置矢量和各个飞机的空中等待成本，计算各个粒子当前的位置矢量对应的航班总延误成 本，并根据由更新后的各个粒子的位置矢量计算的各个粒子的航班总延误成本，确定各个 粒子的自身历史最好位置、邻居最好位置和所述X个粒子的全局历史最好位置；其中，第i 个粒子的自身历史最好位置为在迭代过程中第i个粒子的所有位置矢量中对应的航班总 延误成本最小的位置矢量；（3)判断本次迭代是否达到迭代终止条件，若达到所述迭代终 止条件，则确定当前全局历史最好位置中的D个元素为所述待着陆飞机中各架飞机的着陆 时间段，停止迭代过程；若未达到所述迭代终止条件，则进一步判断本次迭代是否达到拓扑 自适应调整门限，若本次迭代达到所述拓扑自适应调整门限，则对各个粒子的网络拓扑进 行调整；所述调整包括：选择当前所述X个粒子中自身历史最好位置对应的航班总延误成 本最小的P个第一粒子和所述X个粒子中自身历史最好位置对应的航班总延误成本最大的 Q个第二粒子，对每个所述第一粒子，随机选择第一边调整个数个第三粒子，增加第一粒子 与每个第三粒子之间的相邻关系，对每个所述第二粒子，在与所述第二粒子直接相邻的粒 子中，随机选择第二边调整个数个第四粒子，删除第二粒子与每个第四粒子之间的相邻关 系，执tx (1); 发送模块，用于分别将所述处理模块确定的所述待着陆飞机中的各架飞机的着陆时间 段发送给对应的飞机。
【专利摘要】本发明提供一种航班调度方法和装置。本发明航班调度方法通过在根据航班计划到达时间和各飞机的空中等待成本确定各航班的着陆时间时，采用无标度网络的产生机制生成各航班着陆时间的粒子群网络拓扑，增加航班等待成本最小的P个粒子与网络拓扑中其他粒子的连接，同时减少航班等待成本最大的Q个粒子与网络拓扑中其他粒子的连接,由于增加了距离最优航班调度时间结果最近的粒子的连接权重，降低了距离最优航班调度时间结果最远的粒子的连接权重，使得最终获得的航班着陆时间的结果的收敛时间缩短，提升了确定各航班着陆时间的效率,由于无标度网络的异质性特点，保证了粒子种群网络拓扑多样性，避免了采用规则网络获取的结果陷入局部最优。
【IPC分类】G06N3/00, G06Q10/04
【公开号】CN104881720
【申请号】CN201510303004
【发明人】杜文博, 周兴莲, 陈震, 高阳
【申请人】北京航空航天大学
【公开日】2015年9月2日
【申请日】2015年6月4日