基于时空间维度分解的机场停机位分配方法及系统

摘要

本发明提供一种基于时空间维度分解的机场停机位分配方法及系统，该方法包括：根据预设的各时间段和各航班的机场运行时间，对各航班进行划分，获得各时间段对应的航班集合；根据预设的各停机位属性，对各停机位进行划分，获得各停机位属性对应的停机位集合；根据所述航班集合和所述停机位集合，建立约束条件和0‑1整数规划模型；利用分支定界法，对所述0‑1整数规划模型进行求解，获得停机位分配方案。本发明提高了机场停机位分配的效率，且优化了分配结果，有利于机场高效安全的运行。

说明书

技术领域

本发明涉及机场运行优化领域，尤其涉及一种基于时空间维度分解的机场停机位分配方法及系统。

背景技术

随着民航运输业的快速发展，航班数量逐年增加，机场运行日益繁忙，停机位资源已逐步成为制约机场运行能力的瓶颈。停机位是旅客上下飞机和机场进行地面保障作业的场所，停机位资源紧缺则会造成机场运行效率下降甚至运行混乱，进而导致航班延误等不利后果，因而停机位资源优化已成为机场运行研究的热点和急需解决的问题。

目前有两种方法可以解决机场停机位资源紧缺的问题：一、扩建机场或新建机场，从硬件方面增加机场停机位资源。但是这种方法一方面需要大量人力物力财力的投入，会对机场周围环境产生重大影响；另一方面在时间上具有滞后性，并不能立刻见效。二、通过合理高效的方法来对现有机位资源进行优化分配，以提高停机位使用效率和旅客满意度。这种方法不存在第一种方法的经济和环境问题，而且简单易行，投入少，见效快，适用面广。

针对停机位分配问题，国内外已采用的研究方法有数学规划、启发式算法、专家系统、网络流、图着色模型等，但是机场停机位分配问题本质上是一个NP(non-deterministicpolynomial,非确定性多项式)难问题，由于求解该组合优化问题时遇到的“组合爆炸”，求解复杂度大且耗时长，现有研究多数存在难以应用于大规模计算的难题；同时，由于该问题约束条件与优化目标的复杂性，目前的研究只考虑到部分必须执行的硬规则，忽略了机场调控中需要权衡优先级处理的软规则。

发明内容

本发明提供一种基于时空间维度分解的机场停机位分配方法及系统，用于解决现有的机场停机位分配方法求解复杂度大且耗时长，难以应用于大规模计算的问题。

本发明的第一个方面是提供一种基于时空间维度分解的机场停机位分配方法，包括：

根据预设的各时间段和各航班f_i的机场运行时间，对各航班进行划分，获得各时间段对应的航班集合；

根据预设的各停机位属性，对各停机位g_j进行划分，获得各停机位属性对应的停机位集合；

根据所述航班集合和所述停机位集合，建立约束条件和0-1整数规划模型；

利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。

本发明的第二个方面是提供一种基于时空间维度分解的机场停机位分配系统，包括：

第一划分模块，用于根据预设的各时间段和各航班f_i的机场运行时间，对各航班进行划分，获得各时间段对应的航班集合；

第二划分模块，用于根据预设的各停机位属性，对各停机位g_j进行划分，获得各停机位属性对应的停机位集合；

处理模块，用于根据所述航班集合和所述停机位集合，建立约束条件和0-1整数规划模型；

求解模块，用于利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。

本发明提供的基于时空间维度分解的机场停机位分配方法及系统，通过根据在时间维度上对各航班进行划分获得的各航班集合；在空间维度上对各停机位进行划分获得的各停机位集合，建立约束条件和0-1整数规划模型，并利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。上述方案将复杂的机场停机位分配的组合优化问题在基于时间与空间的维度上分解，缩小了解空间，降低了求解复杂度，可在有限的时间内求解规模较大的停机位分配问题，提高了机场停机位分配的效率。

附图说明

图1A为本发明实施例一提供的一种基于时空间维度分解的机场停机位分配方法的流程示意图；

图1B为本发明实施例一提供的另一种基于时空间维度分解的机场停机位分配方法的流程示意图；

图1C为本发明实施例一提供的又一种基于时空间维度分解的机场停机位分配方法的流程示意图；

图2A为本发明实施例三提供的一种基于时空间维度分解的机场停机位分配系统的结构示意图；

图2B为本发明实施例三提供的另一种基于时空间维度分解的机场停机位分配系统的结构示意图；

图2C为本发明实施例三提供的又一种基于时空间维度分解的机场停机位分配系统的结构示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下获得的所有其他实施例，都属于本发明保护的范围。

图1A为本发明实施例一提供的一种基于时空间维度分解的机场停机位分配方法的流程示意图，如图1A所示，所述方法包括如下步骤：

11、根据预设的各时间段和各航班f_i的机场运行时间，对各航班进行划分，获得各时间段对应的航班集合。

进一步的，针对其机场运行时间与多个时间段存在重合的航班，判定所述航班属于所述多个时间段对应的航班集合。

12、根据预设的各停机位属性，对各停机位g_j进行划分，获得各停机位属性对应的停机位集合。

13、根据所述航班集合和所述停机位集合，建立约束条件和0-1整数规划模型。

具体的，根据航班集合和停机位集合，可以建立多种约束条件，举例来说，约束条件可以包括硬规则和软规则，硬规则可以包括停机位容量与航班机型之间的关系约束、与时间相关的约束、以及预设的与停机位调度相关的约束，软规则可以包括预设的与机场布局和运行相关的约束。

进一步的，根据航班集合和停机位集合，建立0-1整数规划模型可以有多种，举例来说，建立0-1整数规划模型，需要为划分好的航班集合和停机位集合建立考虑多规则约束条件和多优化目标的0-1整数规划模型。具体如图1B所示，图1B为本发明实施例一提供的另一种基于时空间维度分解的机场停机位分配方法的流程示意图，在图1A所示实施方式的基础上，13具体可以包括：

131、根据所述航班集合和所述停机位集合，建立约束条件；

132、设定航班f_i和停机位g_j对应的决策变量X_ij，X_ij的取值表征所述航班f_i是否停放在停机位g_j；

133、根据所述航班集合和所述停机位集合，建立各优化目标，所述各优化目标包括停机位优先级权重、停机位变更率、航班靠桥率和旅客步行距离；

134、根据各优化目标对应的权重值，对所述各优化目标进行加权求和，获得目标函数；

135、根据所述约束条件和所述目标函数，建立所述0-1整数规划模型。

具体的，根据航班集合和停机位集合，建立停机位优先级权重优化目标的方法可以有多种，例如，可以根据航班集合和停机位集合，利用软规则建立相应的停机位优先级权重优化目标。相应的，如图1C所示，图1C为本发明实施例一提供的又一种基于时空间维度分解的机场停机位分配方法的流程示意图，在图1B所示实施方式的基础上，133具体可以包括：

1331、根据所述航班集合和所述停机位集合，建立停机位变更率、航班靠桥率和旅客步行距离；

1332、根据所述决策变量X_ij，建立决策矩阵X；

1333、根据所述软规则，建立相应的权重矩阵；

具体的，所述软规则可以包括：过站航班优先于纯出港航班安排在近机位，所述纯出港航班优先于纯进港航班安排在所述近机位；同一机型时，过站时间短的航班优先于过站时间长的航班安排在所述近机位，相同过站时间时，大机型优先于小机型安排在所述近机位；客座率高的航班优先安排在所述近机位。

1334、对所述权重矩阵进行归一化处理及线性加和，获得所述软规则的总体权重矩阵；

1335、对所述总体权重矩阵与所述决策矩阵进行点积，获得所述停机位优先级权重。

14、利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。

本实施例提供的基于时空间维度分解的机场停机位分配方法，通过根据在时间维度上对各航班进行划分获得的各航班集合；在空间维度上对各停机位进行划分获得的各停机位集合，建立约束条件和0-1整数规划模型，并利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。上述方案将复杂的机场停机位分配的组合优化问题在基于时间与空间的维度上分解，缩小了解空间，降低了求解复杂度，可在有限的时间内求解规模较大的停机位分配问题，提高了机场停机位分配的效率。同时通过考虑包含优先级的软规则对停机位分配的影响，进一步优化了机位分配结果，增加了机场停机位分配优化方案的合理性，实现对停机位容量灵活高效的使用。

本发明实施例二提供一种基于时空间维度分解的机场停机位分配方法，具有如下步骤：

21、在时间维度上对各航班进行划分。

对次日所有的运行航班f_i,i＝1,2,…,N_f，其中，N_f为次日航班总量，通过固定的时间间隔，或者夜间和白天两种时间间隔将航班划分为若干个航班集合。具体的，以白天(6点-24点)1小时，夜间(0点-6点)3小时，根据航班的计划运行时间将全部航班分为M_f＝20个集合，记为F_x,x＝1,2,…,M_f。

针对其机场运行时间跨越两个或更多个时间段的航班，规定只要航班运行时间与该时间段重合，就判定这架航班位于该时间段对应的航班集合中。

针对每个航班集合F_x，分别依次采用整数规划模型进行优化分配，需要考虑的是，前一集合中已经分配的航班，在后一次的整数规划模型中，需要提前锁定航班对应的停机位。

22、在空间维度上对各停机位进行划分。

对机场所有的停机位g_j,j＝1,2,…,N_g，其中，N_g为停机位总量，根据停机位的属性特征将所有机位分为多个停机位集合；结合机场的布局和机位特征，分别从东区、西区两个分区、停机位的距离属性(同一停机坪或连续几个停机位)、停机位的型号及停机位的区域特征角度进行考虑，将所有机位分为M_g个机位集合，记为G_x,x＝1,2,…,M_g。

针对每一架航班，通过该航班与停机位集合属性间的关系，可以确定该航班对应的停机位属于某一个或某几个停机位集合，从而，缩小了解的空间，降低了模型求解的复杂度，最终可以保障在有限的时间内等到较优的可行解。

23、针对划分好的航班集合和停机位集合，建立约束条件，并建立0-1整数规划模型，具体包括：

231、设定航班f_i和停机位g_j对应的决策变量X_ij，X_ij的取值表征所述航班f_i是否停放在停机位g_j。

其中，

232、根据划分好的航班集合和停机位集合，建立约束条件，约束条件包括：硬规则和软规则。

硬规则是强制性的运行规则，即停机位分配过程中必须遵守的硬性规则。本发明实施例二从空间约束条件、时间约束条件、人为约束条件三个角度建立硬规则，包括：

a)空间约束条件：空间约束指停机位容量与航班机型之间的约束关系，包括：

1)任何停机位只能停放其允许的最大机型及其以下机型的航班：

X_ij≤T_ij

其中，

b)时间约束条件：时间约束指与时间相关的约束，包括独占制约规则、停机位占用时间规则、邻接飞机停泊的间隔时间规则、相邻停机位需要满足的时间规则。具体包括：

2)每架航班f_i只能分配一个停机位g_j：

3)同一停机位g_j上安排的不同架次的航班f_i、f_k在占用时间上不能重叠：

X_ijX_kj(d_i-a_k)(d_k-a_i)≤0

其中，a_i、d_i分别表示航班f_i的进港时间和出港时间，a_k、d_k分别表示航班f_k的进港时间和出港时间。

4)同一停机位上g_j相邻两架航班f_i、f_k满足最小缓冲时间：

X_ijX_kj(d_i-a_k+b_j)(d_k*a_i+b_j)≤0

其中，b_j表示停机位g_j要求的相邻两架航班f_i、f_k需满足的最小缓冲时间；

5)相邻停机位上同时只能有一个任务作业：

其中，G_adj为相邻停机位集合，G_adj∈{G_x|x＝1,2,…,M_g}。

6)相邻停机位上不能同时推入或推出飞机：

and

其中，为航班f_i停放停机位时推入、推出时间，G’_adj为相邻停机位不能同时推入或推出飞机的停机位集合，G’_adj∈{G_x|x＝1,2,…,M_g}。

c)人为约束条件：人为约束指在实际停机位分配过程中，机场调度人员人为定义的约束条件，可包括国际国内航班与停机位对应的规则约束、混合航班与停机位对应的规则约束、强制分配停机位的规则约束。根据航班的飞行路线对各航班进行划分，获得国际航班集合F_I、国内航班集合F_D和混合航班集合F_M。人为约束条件具体可以包括：

7)国际航班停在近机位的国际停机位，国内航班停在近机位的国内停机位：

X_ij≤0，f_i∈F_D,g_j∈G_Nandg_j∈G_I

X_ij≤0，f_i∈F_I,g_j∈G_Nandg_j∈G_D

其中，G_N为近机位集合，G_N∈{G_x|x＝1,2,…,M_g}，G_I为国内机位集合，G_I∈{G_x|x＝1,2,…,M_g}，G_D为国际机位集合，G_D∈{G_x|x＝1,2,…,M_g}。

8)混合航班停在远机位：

X_ij≤0，f_i∈F_M,g_j∈G_f

其中，G_f为远机位集合，G_f∈{G_x|x＝1,2,…,M_g}。

9)强制分配停机位，即锁定航班f_i位于停机位g_j：

X_ij＝1

10)超过三小时过站时间的航班不靠桥，即不停放在近机位：

软规则包括预设的与机场布局和运行相关的约束，引入权重值来表示每条软规则体现的优先级关系，即权重值越大，航班越优先停在近机位上，并使用权重矩阵定义满足所述软规则的航班与停机位对应的优先级关系。在实际应用中，针对每条软规则，可以根据需求调整权重值。

根据航班的起讫点对各航班进行分解，获得过站航班集合F_turn、纯出港航班集合F_dep、纯进港航班集合F_arr；根据航班的机型对各航班进行分解，获得大机型集合F_L-type和小机型集合F_s-type。

本发明实施例二的软规则包括：

11)过站航班优先于纯出港航班安排在近机位，纯出港航班优先于纯进港航班安排在近机位：

其中，为a、b、c分别为预设的权重值。

12)同一机型时，过站时间短的航班优先于过站时间长的航班安排在近机位，相同过站时间时，大机型优先于小机型安排在近机位：

其中，u、v分别为预设的权重值。

13)客座率高的航班优先安排在近机位：

其中SR_i为航班f_i的客座率，是反映航空客运公司运营效率的指标，SR_i(客座率)＝实际承运人数÷可供座位数×100％。

233、根据划分好的航班集合和停机位集合，设置各优化目标，根据各优化目标对应的权重值，对所述各优化目标进行加权求和，获得目标函数；所述各优化目标包括：停机位优先级权重、停机位变更率、航班靠桥率和旅客步行距离。

具体的，上述获得目标函数，包括：

设置停机位变更率优化目标：

其中，为航班f_i对应的航班集合中的航班数量，Y_ij为航班f_i与停机位g_j在停机位变更前的分配结果.

其中，

设置航班的靠桥率优化目标(即近机位使用率优化目标)：

设置旅客的步行距离优化目标：

其中，D_j为停机位g_j对应的旅客的步行距离。

设置停机位优先级权重优化目标，具体包括：

根据所述决策变量X_ij，建立决策矩阵X；

根据上述三个软规则，设定任意航班f_i对应的远机位的权重均为0，即：

由此获得分别与三个软规则对应的三个权重矩阵，分别为：

对三个权重矩阵的权重值分别进行归一化处理，使用离差标准化处理方法，对权重矩阵进行线性变换，使结果映射到[0,1]之间，转换函数如下：

其中max为权重矩阵的元素的最大值，min为权重矩阵的元素的最小值。

对三个权重矩阵进行线性加和，获得总体软规则的权重矩阵：

将总体软规则的权重矩阵与决策矩阵进行点积，获得停机位优先级权重优化目标：

根据各优化目标对应的权重值，对所述各优化目标进行加权求和，获得目标函数：

Max z＝αz₁+βz₂+γz₃+εz₄

其中，α、β、γ、ε为预设的权重系数。

234、根据所述约束条件和所述目标函数，建立所述0-1整数规划模型。

24、利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案，包括：

241、求解上述0-1整数规划模型的松弛问题最优解；

242、判断上述松弛问题的最优解是否满足整数要求，若满足，则结束求解过程，将上述松弛问题的最优解和目标值作为上述0-1整数规划模型的最优解和目标值；否则，

243、针对各非整数解的变量x_i，在松弛问题中加上约束x_i≤[x_i]及x_i≥[x_i]+1组成两个新的松弛问题，称为分支A_i、A_i+1；

244、选择目标值最大的分支A_i，判断该分支的解是否是整数，若是，则结束求解过程，将该分支的解和目标值作为上述0-1整数规划模型的最优解和目标值，否则，返回执行243。

本实施例提供的基于时空间维度分解的机场停机位分配方法，通过根据在时间维度上对各航班进行划分获得的各航班集合；在空间维度上对各停机位进行划分获得的各停机位集合，建立约束条件和0-1整数规划模型，并利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。上述方案将复杂的机场停机位分配的组合优化问题在基于时间与空间的维度上分解，缩小了解空间，降低了求解复杂度，可在有限的时间内求解规模较大的停机位分配问题，提高了机场停机位分配的效率。同时通过考虑包含优先级的软规则对停机位分配的影响，进一步优化了机位分配结果，增加了机场停机位分配优化方案的合理性，实现对停机位容量灵活高效的使用。

图2A为本发明实施例三提供的一种基于时空间维度分解的机场停机位分配系统的结构示意图，如图2A所示，所述系统包括：

第一划分模块31，用于根据预设的各时间段和各航班fi_i的机场运行时间，对各航班进行划分，获得各时间段对应的航班集合。

进一步的，所述第一划分模块，还用于针对其机场运行时间与多个时间段存在重合的航班，判定所述航班属于所述多个时间段对应的航班集合。

第二划分模块32，用于根据预设的各停机位属性，对各停机位g_j进行划分，获得各停机位属性对应的停机位集合。

处理模块33，用于根据所述航班集合和所述停机位集合，建立约束条件和0-1整数规划模型；

求解模块34，用于利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。

作为一种可选的实施方式，图2B为本发明实施例三提供的另一种基于时空间维度分解的机场停机位分配系统的结构示意图，如图2B所示，在图2A所示实施方式的基础上，处理模块33包括：

约束单元331，用于建立所述约束条件，所述约束条件包括硬规则和软规则，所述硬规则包括停机位容量与航班机型之间的关系约束、与时间相关的约束、以及预设的与停机位调度相关的约束，所述软规则包括预设的与机场布局和运行相关的约束；

初始单元332，用于设定航班f_i和停机位g_j对应的决策变量X_ij，X_ij的取值表征所述航班f_i是否停放在停机位g_j；

处理单元333，用于根据所述航班集合和所述停机位集合，建立各优化目标，所述各优化目标包括停机位优先级权重、停机位变更率、航班靠桥率和旅客步行距离；

计算单元334，用于根据各优化目标对应的权重值，对所述各优化目标进行加权求和，获得目标函数；

所述处理单元333，还用于根据所述约束条件和所述目标函数，建立所述0-1整数规划模型。

作为一种可选的实施方式，图2C为本发明实施例三提供的又一种基于时空间维度分解的机场停机位分配系统的结构示意图，如图2C所示，在图2B所示实施方式的基础上，所述软规则包括：过站航班优先于纯出港航班安排在近机位，所述纯出港航班优先于纯进港航班安排在所述近机位；同一机型时，过站时间短的航班优先于过站时间长的航班安排在所述近机位，相同过站时间时，大机型优先于小机型安排在所述近机位；客座率高的航班优先安排在所述近机位；所述处理单元333还可以包括：

矩阵子单元3331，用于根据所述决策变量X_ij，建立决策矩阵X，所述决策矩阵X包括各航班和停机位对应的决策变量；

所述矩阵子单元3331，还用于根据所述软规则，建立相应的权重矩阵；

计算子单元3332，用于对所述权重矩阵进行归一化处理及线性加和，获得所述软规则的总体权重矩阵；

处理子单元3333，用于对所述总体权重矩阵与所述决策矩阵进行点积，获得所述停机位优先级权重优化目标。

本实施例提供的基于时空间维度分解的机场停机位分配系统，通过根据在时间维度上对各航班进行划分获得的各航班集合；在空间维度上对各停机位进行划分获得的各停机位集合，建立约束条件和0-1整数规划模型，并利用分支定界法，对所述0-1整数规划模型进行求解，获得停机位分配方案。上述系统将复杂的机场停机位分配的组合优化问题在基于时间与空间的维度上分解，缩小了解空间，降低了求解复杂度，可在有限的时间内求解规模较大的停机位分配问题，提高了机场停机位分配的效率。同时通过考虑包含优先级的软规则对停机位分配的影响，进一步优化了机位分配结果，增加了机场停机位分配优化方案的合理性，实现对停机位容量灵活高效的使用。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。