基于非完全覆盖的机场任务指派问题优化研究

Optimization of Airport Task Assignment Problem Based on Incomplete Coverage

摘要

随着淡旺季不同以及临时突发状态的发生，机场会出现在某一时间段内任务量剧增而人员严重不足的情况。研究基于非完全覆盖的机场任务指派问题，以任务产生的效益最大化为第一目标函数，资格技能水平差总和最小化为第二目标函数，构建了多目标整数规划模型，设计了改进的多目标文化基因算法。在求解过程中，采用实际数据进行测试，测试结果表明：1） 通过与CPLEX优化软件对比，验证了所建模型和改进算法的准确性；2） 针对大规模算例，改进的算法在保证第一目标函数值近似最优解时，第二目标函数值都优于CPLEX求得的解，平均优化5.89%；3） 对覆盖率、班次工作时长等参数进行灵敏度分析，结果表明不同参数的设置对目标函数的影响显著。该研究不仅能够有效解决机场任务指派问题，而且可为企业实际运营决策提供科学依据。

Abstract

With the difference between the off-peak season and the occurrence of temporary emergencies, the airport will have a situation of severe shortage of personnel in a certain period when the task volume increases sharply. The studies in this paper do not entirely cover the problem of airport task assignment. The first objective function is to maximize the benefits generated by the task, and the second objective function is to minimize the sum of the differences in the level of qualifications and skills. A multi-objective integer programming model was constructed, and an improved multi-objective memetic algorithm was designed. In the process of solving the problem, the actual data were tested, and the numerical results showed that the accuracy of the built model and improved algorithm was verified compared with CPLEX optimization software. For large-scale examples, when the first objective function value is approximately optimal, the second objective function value is better than the CPLEX solution, with an average optimization of 5.89%. The sensitivity analysis of the coverage rate, shift working hours, and other parameters showed that the setting of different parameters significantly impacted the objective function. This study can not only effectively solve the problem of airport task assignment, but also provide a scientific basis for the actual operational decisions of enterprises.

Graphical abstract

关键词

非完全覆盖 / 整数规划模型 / 改进的多目标文化基因算法

Key words

incomplete coverage / integer programming model / improved multi-objective memetic algorithm

0　 引 言

机场作为人类在地面上操作的最复杂系统之一，是航空运输过程的重要组成部分^[1]，而机场任务包含了很多类型，比如咨询服务、检票进站、飞机清洁、机器维修（售卖机或者取票机等）等。每个任务都具有任务类型、开始时间、结束时间、优先权、执行该任务的资格要求、最低资格熟练程度要求等多种属性。为了使飞机安全起飞并按时着陆，地勤人员要轮班执行任务。班次由机场工作人员组成，具有开始时间、结束时间、拥有的资格以及每种资格对应的熟练程度等多种属性，一旦确定了班次，下一步就是按照机场的规章制度将任务分配给班次。当任务指派给班次时要满足时间约束、资格约束、资格熟练程度约束，每个任务的完成会产生相应的效益，如何使总效益最大化是机场任务指派问题的一个目标。

虽然关于机场的研究已引起许多学者的关注^[2-7]，但当前关于机场任务指派问题的研究较少^[8]。其中，Chen等^[9]研究了地面保障设备车辆分配任务问题。Frey等^[10]对机场行李提取的规划调度问题进行了研究。Yang等^[11]研究了机场行李处理任务，基于实时行李跟踪信息建立线性规划模型，采用动态规划算法进行求解。Gupta等^[12]对机场设备维护任务计划进行研究，提出了一种从数据集中去除空闲数据和噪声数据的算法。Zeng等^[13]研究了机场地面人员的队伍规划问题，其中允许具有较高技能的人员满足较低级别的需求，并采用分支定价算法求解该模型。Guimarans和Padrón^[14]针对地面资源支援任务工作计划进行研究。Wang等^[15]针对员工排班和任务分配问题进行综合研究，要求一旦任务被指派，任务时间就要被完全覆盖，并采用混合启发式算法求得大规模问题的解。

综上所述，现有文献中关于任务指派问题的研究要么任务类型比较单一，要么要求任务的执行时间被完全覆盖。在实际情况中，机场的任务是允许在规定时间内较早或较晚开始的，只要工作时长满足覆盖率的要求，即，在原规定的时间内，任务被连续完成的时长不低于提前设置的值（覆盖率\times初始时长），那么任务允许在班次加急的情况下被完全执行。另外，为了避免资源浪费，尽量安排与任务资格技能水平要求相近的班次去执行相应的任务，这也是现在越来越多机场在解决任务指派问题时注重的方面。因此，本文研究基于非完全覆盖的机场任务指派问题，以最大化任务产生的总效益和最小化资格技能水平差总和为目标函数，建立多目标整数规划模型，采用改进多目标文化基因算法（Improved Multi-Objective Memetic Algorithm, IMOMA）对实际数据进行求解，与CPLEX优化软件进行对比分析，同时对不同参数进行灵敏度分析。通过对比实验，验证了本文模型的正确性及IMOMA算法的有效性。

1　 问题描述与数学模型

1.1　问题描述

本文考虑非完全覆盖的机场任务指派问题，该问题的数学描述如下：设G=\left(V,E\right)为一个有向图，其中，V=\left\{\mathrm{0,1},\mathrm{2},\cdots ,N\right\}为节点集，其中，0为虚拟任务；E=\{(i,j),i,j\in V,i\ne j\}为边集。T=\{\mathrm{1,2},\cdots ,N\}代表任务集合；S=\{\mathrm{1,2},\cdots ,M\}代表班次集合。机场每天都有大量的任务等待着指派给有限数量的班次，其中，一个任务代表一种服务，必须由一个或多个具有一定资格的地勤人员在规定的时间内完成。假设一个任务可以指派给一个班次，那么它们之间要满足以下约束：

1） 当考虑任务的非完全覆盖率时，班次的开始时间要早于任务的实际开始时间，班次的结束时间要晚于任务的实际结束时间；

2） 任务的资格集合要求属于班次资格集合的子集，相应资格的技能水平也要满足要求；

3） 不同任务类型分布在机场不同位置，任务之间的距离用时间表示。

1.2　数学模型

模型中使用的符号及变量如下：\mathrm{T}{\mathrm{S}}_i为任务i的预设开始时间，i\in T；\mathrm{T}{\mathrm{E}}_i为任务i的预设结束时间，i\in T；\mathrm{T}{\mathrm{S}}_i^{\mathrm{1}}为考虑非完全覆盖率时任务i的实际开始时间，i\in T；\mathrm{T}{\mathrm{E}}_i^{\mathrm{1}}为考虑非完全覆盖率时任务i的实际结束时间，i\in T；\mathrm{T}{\mathrm{T}}_i为任务i的类型，i\in T；\mathrm{T}{\mathrm{P}}_i为任务i的优先级，i\in T；\mathrm{T}{\mathrm{Q}}_i为执行任务i的资格要求，i\in T；\mathrm{T}\mathrm{p}\mathrm{r}{\mathrm{o}}_i为执行任务i所需最低的资格技能水平，i\in T；\mathrm{S}{\mathrm{S}}_s为班次s的开始时间，s\in S；\mathrm{S}{\mathrm{E}}_s为班次s的结束时间，s\in S；\mathrm{S}\mathrm{S}{\mathrm{Q}}_{s,n}为班次s拥有的第n个资格，其中，s\in S,n\in \{\mathrm{1,2},\cdots ,\mathrm{9}\}；\mathrm{S}\mathrm{S}\mathrm{p}\mathrm{r}{\mathrm{o}}_{s,m}为班次s所拥有第m个资格的技能水平，其中，s\in S,m\in \{\mathrm{1,2},\cdots ,\mathrm{9}\}；d_{ij}为任务i和任务j之间的距离,其中，i,j\in T；c_{ijs}为任务i,j被班次s连续执行所产生的效益，即c_{ijs}=(\mathrm{T}{\mathrm{E}}_i^{\mathrm{1}}-\mathrm{T}{\mathrm{S}}_i^{\mathrm{1}})\times \mathrm{T}{\mathrm{P}}_i+(\mathrm{T}{\mathrm{E}}_j^{\mathrm{1}}-\mathrm{T}{\mathrm{S}}_j^{\mathrm{1}})\times \mathrm{T}{\mathrm{P}}_j,i,j\in T\bigcup \{\mathrm{0}\},s\in S；\beta \in [\mathrm{0,1}]；\overline{M}为一个较大的非负常数；D为一个常数，根据机场数据的实际情况进行设定。

决策变量x_{ijs}：班次s先执行了任务i紧接着执行了任务j时,x_{ijs}为1；否则为0，s\in S,i,j\in T\bigcup \{\mathrm{0}\}。

根据以上变量，建立整数规划模型如下：

f_{\mathrm{1}}=\mathrm{m}\mathrm{a}\mathrm{x}\hspace{1em}\frac{\mathrm{1}}{\mathrm{2}}\times \left(\sum _{s\in S}\sum _{i\in T\bigcup \left\{\mathrm{0}\right\}}\sum _{j\in T\bigcup \left\{\mathrm{0}\right\}}{c}_{ijs}{x}_{ijs}\right)(1)

f_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{i\in T}\sum _{j\ne i,j\in T}\sum _{s\in S,m\in \{\mathrm{1,2},\cdots ,\mathrm{9}\}}(\mathrm{S}\mathrm{S}\mathrm{p}\mathrm{r}{\mathrm{o}}_{s,m}-\mathrm{T}\mathrm{p}\mathrm{r}{\mathrm{o}}_{\mathrm{i}})x_{ijs}(2)

s.t. \sum _{j\in T}{x}_{\mathrm{0}js}=\mathrm{1},s\in S(3)

\sum _{i\in T}{x}_{i\mathrm{0}s}=\mathrm{1},s\in S(4)

\sum _{j\in T\bigcup \{\mathrm{0}\}}\sum _{s\in S}{x}_{ijs}\le \mathrm{1},i\in T(5)

\sum _{i\in T,i\ne h}{x}_{ihs}-\sum _{j\in \mathrm{T},j\ne h}{x}_{hjs}=\mathrm{0},h\in T,h\ne \mathrm{0},s\in S(6)

\sum _{i\in T,i\ne \mathrm{0}}{x}_{iis}=\mathrm{0},s\in S(7)

(\mathrm{S}\mathrm{S}{\mathrm{Q}}_{s,n}-\mathrm{T}{\mathrm{Q}}_i)\sum _{j\in T,j\ne i}{x}_{ijs}=\mathrm{0},

i\in T,s\in S,n\in \{\mathrm{1,2},\cdots ,\mathrm{9}\}(8)

\mathrm{T}\mathrm{p}\mathrm{r}{\mathrm{o}}_i)\times \sum _{j\in T,j\ne i}{x}_{ijs}\le \theta ,

i\in T,s\in S,m\in \{\mathrm{1,2},\cdots ,\mathrm{9}\},m=n(9)

\mathrm{S}{\mathrm{S}}_s-\mathrm{T}{\mathrm{S}}_i^{\mathrm{1}}\le \left(\mathrm{1}-x_{ijs}\right)\overline{M},

i\in T,i\ne \mathrm{0},j\in T,j\ne i,s\in S(10)

\mathrm{T}{\mathrm{E}}_i^{\mathrm{1}}-\mathrm{S}{\mathrm{E}}_s\le \left(\mathrm{1}-x_{ijs}\right)\overline{M},

i\in T,i\ne \mathrm{0},j\in T,j\ne i,s\in S(11)

\mathrm{T}{\mathrm{E}}_i-\mathrm{T}{\mathrm{S}}_i\ge \mathrm{T}{\mathrm{E}}_i^{\mathrm{1}}-\mathrm{T}{\mathrm{S}}_i^{\mathrm{1}}\ge \beta (\mathrm{T}{\mathrm{E}}_i-\mathrm{T}{\mathrm{S}}_i),

i\in T,i\ne \mathrm{0},j\in T,j\ne i,s\in S(12)

\mathrm{T}{\mathrm{S}}_i^{\mathrm{1}}\ge \mathrm{T}{\mathrm{S}}_i,i\in T,i\ne \mathrm{0}(13)

\mathrm{T}{\mathrm{E}}_i^{\mathrm{1}}\le \mathrm{T}{\mathrm{E}}_i,i\in T,i\ne \mathrm{0}(14)

\mathrm{T}{\mathrm{E}}_i^{\mathrm{1}}+d_{ij}-\mathrm{T}{\mathrm{S}}_j^{\mathrm{1}}\le \left(\mathrm{1}-x_{ijs}\right)\overline{M},

i\in T,i\ne \mathrm{0},j\in T,j\ne \mathrm{0},j\ne i,s\in S(15)

x_{ijs}\in \left\{\mathrm{0,1}\right\},i,j\in T\bigcup \left\{\mathrm{0}\right\},s\in S(16)

d_{ij}\le D,i,j\in T且i\ne j(17)

（1）式表示效益最大化，为第一目标函数，由于每一个被完成的任务在\sum _{s\in S}\sum _{i\in T\bigcup \left\{\mathrm{0}\right\}}\sum _{j\in T\bigcup \left\{\mathrm{0}\right\}}{c}_{ijs}{x}_{ijs}这里都被计算了两次，所以系数要乘以1/2；（2）式表示资格技能水平差总和最小化，为第二目标函数。（3）~（17）式为模型的约束条件，其中，（3）式表示每一个班次都从任务0开始（这里任务0表示空任务）；（4）式表示每一个班次最后都回到任务0；（5）式表示每一个任务最多被完成一次，这里使用关联矩阵\mathit{A}解释说明，设矩阵\mathit{A}是N\times M维，那么任务T和班次S的关联矩阵如下所示：

\mathit{A}={\left[\begin{array}{ccccc}\mathrm{0}& \mathrm{0}& \mathrm{1}& \cdots & \mathrm{1}\\ \mathrm{1}& \mathrm{1}& \mathrm{0}& \cdots & \mathrm{1}\\ \mathrm{1}& \mathrm{0}& \mathrm{0}& \cdots & \mathrm{1}\\ ⋮& ⋮& ⋮& \cdots & ⋮\\ \mathrm{0}& \mathrm{0}& \mathrm{1}& \cdots & \mathrm{0}\end{array}\right]}_{N\times M}

关联矩阵\mathit{A}中的行代表任务T（N个），列代表班次S（M个），矩阵中的元素“1”表示矩阵所在行的任务与所在列的班次之间由于满足各种约束条件可以进行指派，元素“0”表示矩阵所在行的任务与所在列的班次之间由于不满足约束条件而不能进行指派；（6）式表示流量守恒约束；（7）式表示任何一个任务不允许被同一个班次连续执行；（8）~（9）式表示一个任务如果被一个班次执行，那么就要满足任务对班次的资格要求以及相应资格技能水平相匹配的要求，即m=n，\theta表示资格的匹配度，其数值根据机场人员班次与任务之间的特征需求设置；（10）~（14）式表示考虑“非完全覆盖率”的情况，比如当\beta \ne \mathrm{1}时，允许任务被执行的时长不低于提前设置的值（\beta\times初始时长），同时不高于初始时长；（15）式表示当两个任务被同一个班次去完成时，要满足距离上的要求；（16）式表示决策变量x_{ijs}属于0-1变量；（17）式表示对指派给同一个班次的两个任务之间的距离的约束。

2　 改进的多目标文化基因算法

本文的研究问题属于复杂的多目标组合优化问题，为了在短时间内获得问题的解决方案，提出一种改进的多目标文化基因算法。该算法流程如图1所示。

2.1　初始种群的生成

2.1.1　染色体的编码与解码

采用自然数的编码方式构造染色体，其中0表示空任务，其他自然数表示要执行的任务（由于并不是所有任务都能被执行，所以染色体长度可能不一致）。图2(a)展示了染色体编码示意图，每条染色体编码顺序表示任务的执行顺序（任务按顺序5、8、3、9、1、2、6执行），图2(b)为图2(a)对应的解码后的个体，其中中间加0表示当不满足约束条件时该班次执行任务结束。每个个体表示班次执行的任务顺序，表示班次1先执行任务0，依次执行任务5、8、3、9然后回到任务0，班次2从任务0开始，执行任务1、2、6后回到任务0。

2.1.2　生成初始种群的三种方法

初始解的质量对算法的求解效果和效率有着至关重要的影响。因此，本文采用三种方法生成初始种群，种群规模为P_Size。其中，采用贪婪修复算子和后悔修复算子，可以生成一条染色体；采用基于随机生成的序惯最优插入，可以生成P_Size-2条染色体。

1） 贪婪修复算子

\mathrm{\Delta }{f}_{\mathrm{1}}(i,s)表示将任务i插入到班次s中第一目标函数值最大的位置时第一目标函数值的变化，当任务i不满足班次与任务的资格匹配、时间窗等约束时，将\mathrm{\Delta }{f}_{\mathrm{1}}(i,s)设置为一个负数。\mathrm{\Delta }{f}_{\mathrm{2}}(i,s)表示将任务i插入到班次s中第二目标函数值最小的位置时第二目标函数值的变化，当任务i不满足班次与任务的资格匹配、时间窗约束等限制时，将\mathrm{\Delta }{f}_{\mathrm{2}}(i,s)设置为一个很大的数。基于贪婪原则，选择使\mathrm{\Delta }{f}_{\mathrm{1}}(i,s)最大、\mathrm{\Delta }{f}_{\mathrm{2}}(i,s)最小的(i,s)进行插入匹配，若无法同时满足，则优先选择\mathrm{\Delta }{f}_{\mathrm{1}}(i,s)最大进行插入，直到无可行插入存在。

2） 后悔修复算子

\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{1}}^{(i,g)}表示将任务i插入到使第一目标函数值第g大的路径中最好的位置（一个任务可以插入一个解的多条路径，一条路径有多个位置可供插入，能使目标函数值最大化的那条路径的某个位置就是最好的位置）时第一目标函数值的变化，\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{2}}^{(i,g)}表示把任务i插入到使第二目标函数值第g小的路径中最好的位置时第二目标函数值的变化。在每一次迭代中，要插入的任务i需满足i=\mathrm{a}\mathrm{r}\mathrm{g}\underset{{}_{i\in N_{Task}}}{\mathrm{m}\mathrm{a}\mathrm{x}}\{\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{1}}^{(i,\mathrm{1})}-\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{1}}^{(i,\mathrm{2})}\}且i=\mathrm{a}\mathrm{r}\mathrm{g}\underset{{}_{i\in N_{Task}}}{\mathrm{m}\mathrm{a}\mathrm{x}}\{\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{2}}^{(i,\mathrm{2})}-\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{2}}^{(i,\mathrm{1})}\}，然后将任务i插入到对应班次的最好位置，若无法同时满足，则优先选择使i=\mathrm{a}\mathrm{r}\mathrm{g}\underset{{}_{i\in N_{Task}}}{\mathrm{m}\mathrm{a}\mathrm{x}}\{\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{1}}^{(i,\mathrm{1})}-\mathrm{\Delta }\mathrm{R}{\mathrm{f}}_{\mathrm{1}}^{(i,\mathrm{2})}\}最大的任务i进行插入，直到无可行插入存在。其中，该算子中设置g=\mathrm{2}。

3） 基于随机生成的序惯最优插入

随机生成P_Size-2个所有任务被安排的顺序，然后依次将任务安排给与班次之间相应资格技能水平差最小的班次，直到没有可行的指派存在，从而生成P_Size-2条染色体。

2.2　局部搜索和全局搜索

局部搜索算法，具备深度搜索优势，可以提升获得高质量可行解的概率。遗传算法具有良好的全局寻优能力，可用于全局搜索过程。因此，本文结合改进的遗传算法和用于局部搜索的大邻域搜索算法对初始种群的解进行优化，从而获得高质量的解。

2.2.1　局部搜索——大邻域搜索算法

两个优化目标均受班次任务分配决策影响，设计邻域结构时应着重考虑扰动这一因素。因此，本文基于“班次与任务的匹配”提出基于三种移除算子和两种修复算子的大领域搜索算法来提高解的质量。该过程的核心思想是：首先随机选择一种移除算子从当前解中移除q个任务；然后随机选择一种修复算子将所有未被执行的任务集合中的任务重新插入，直到无可行任务插入。

1） 移除算子

① 随机移除算子

随机选择q个任务从当前解中删除，并放入未被执行的任务集合中。该算子以较大的随机性扩大了邻域解的搜索空间，避免陷入局部最优。

② 最坏移除算子

给定一个任务i和当前解Y，f_{\mathrm{1}}(Y)和f_{\mathrm{2}}(Y)分别表示当前解Y的第一目标函数值和第二目标函数值。f_{\mathrm{1}}^{-i}(Y)表示从解Y中移除任务i后的效益，\mathrm{\Delta }{f}_{\mathrm{1}}^{-i}(Y)=f_{\mathrm{1}}(Y)-f_{\mathrm{1}}^{-i}(Y)；f_{\mathrm{2}}^{-i}(Y)表示从解Y中移除任务i后的第二目标函数值，\mathrm{\Delta }{f}_{\mathrm{2}}^{-i}(Y)=f_{\mathrm{2}}(Y)-f_{\mathrm{2}}^{-i}(Y)。由于文中两个目标具有冲突性，无法找到一个解能使得两个目标同时达到最优，故本文在每次迭代过程中，通过随机选择任意一个目标作为最坏移除算子，产生多样化的邻域解，从而提高解的求解质量。其中最坏移除算子是不断移除使得\mathrm{\Delta }{f}_{\mathrm{1}}^{-i}(Y)或\mathrm{\Delta }{f}_{\mathrm{1}}^{-i}(Y)变化最大的任务i。

③ 聚类移除算子

在当前解中随机选择一个任务，然后以与该任务的资格要求一致为聚类移除原则，移除q-\mathrm{1}个任务。该算子的目的是便于交换班次执行的任务，以期获得更好的Pareto非支配解。

定义1 如果一个解x占优于一个解y（x<y），当且仅当对\forall i\in \{\mathrm{1,2},\cdots ,k\},f_i(x)\le f_i(y)成立，并且\exists i\in \{\mathrm{1,2},\cdots ,k\}，使成立。

如果一个解未被任何其他解占优，则该解被称为Pareto最优。Pareto最优解的集合被称为Pareto前沿。因此，本文设计的改进的多目标文化基因算法就是寻找Pareto前沿，或者接近Pareto前沿。

2） 修复算子

该过程是利用修复算子，把移除过程中被移除的任务和未被执行的任务集合中的任务重新插入到移除后剩余的部分解中。其中，移除的任务和未被执行的任务均放在待执行任务集合N_{\mathrm{T}\mathrm{a}\mathrm{s}\mathrm{k}}中，N_{\mathrm{S}\mathrm{h}\mathrm{i}\mathrm{f}\mathrm{t}}表示所有班次集合。本文采用贪婪修复算子和后悔修复算子进行修复。

2.2.2　全局搜索——改进的遗传算法

1） 交叉算子

不同染色体中被执行的任务及其数目存在差异，因此本文改进了传统交叉算子，形成了如下的基于路径交叉算子。如图3所示，具体交叉方式如下：

Step1: 以一定的概率随机选择两个染色体P_{\mathrm{1}}和P_{\mathrm{2}}作为父代，然后随机选择它们各自解码所对应的一条路径\mathrm{R}{\mathrm{P}}_{\mathrm{1}}和\mathrm{R}{\mathrm{P}}_{\mathrm{2}}，即某一班次所执行的任务路径；

Step2： 删除染色体P_{\mathrm{1}}中与路径\mathrm{R}{\mathrm{P}}_{\mathrm{2}}中相同的任务，然后基于序惯插入法，在满足任务指派约束的条件下将\mathrm{R}{\mathrm{P}}_{\mathrm{2}}中的任务指派到当前P_{\mathrm{1}}中，从而生成新的子代\mathrm{P}{\mathrm{C}}_{\mathrm{1}}。同理，基于染色体P_{\mathrm{2}}和路径\mathrm{R}{\mathrm{P}}_{\mathrm{1}}，产生了另一个子代\mathrm{P}{\mathrm{C}}_{\mathrm{2}}；

Step3： 将2.2.1节中的局部搜索算法作用于步骤2产生的子代\mathrm{P}{\mathrm{C}}_{\mathrm{1}}和\mathrm{P}{\mathrm{C}}_{\mathrm{2}}，生成更高质量新子代\mathrm{N}{\mathrm{C}}_{\mathrm{1}}和\mathrm{N}{\mathrm{C}}_{\mathrm{2}}。

2） 变异算子

由于研究问题中对任务与班次之间的资格匹配和熟练程度的匹配要求较高，因此，存在任务可能不被执行的情形。为了增加种群的多样性及生成高质量的个体，采用已执行任务与未被执行任务在满足班次执行任务的约束条件下进行互换变异，如图4所示，具体步骤如下：

Step1: 以一定的概率随机选择一条未执行完所有任务的染色体作为父代P_{\mathrm{1}}；

Step2: 随机选择该染色体中的一个变异点和不在该染色体中的待执行任务，将变异点的任务与该待执行的任务互换，产生新的子代；

Step3: 将2.2.1中的局部搜索算法作用于步骤2产生的子代\mathrm{P}{\mathrm{C}}_{\mathrm{1}}，生成更高质量的新子代\mathrm{N}{\mathrm{C}}_{\mathrm{1}}。

2.3　种群筛选

最大化任务指派所产生的效益、最小化任务与班次之间相应资格技能水平差的总和是本文的两个优化目标，由于两个目标之间存在矛盾，通常不能找到一个解使这两个目标同时达到最优，故需要找到Pareto非支配解，使两个目标值达到决策者的可接受范围。但是随着迭代次数的增加，Pareto非支配解的数目随之增加，降低了算法的收敛速度。因此，当非支配解的数目超过一定阈值时，需要对已得到的种群进行筛选，通过评价每个个体的优劣来淘汰相应的个体，获得满足Pareto非支配解的新种群。本文选用带精英策略的种群选择机制进行种群筛选。

首先，采用容量较大的存储池结构存储父代种群和当代新生成未被占优的解。然后，鉴于快速非支配排序方法的优异表现，基于优化目标对存储池中的解进行选择操作以维护每一代Pareto非支配集解的数目，从而生成新的父代种群。存储池中任何一个个体i基于其未被占优的层级i_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}和拥挤度距离i_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}这两个属性，可以得出该个体i和其他个体j的优劣关系。

定义2 如果或i_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}=j_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}\mathrm{且}{i}_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}>j_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}，那么个体i优于个体j。其中，i_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}是个体i在当前存储池中未被占优的层级，层级越低表示该个体越好；i_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}为拥挤度距离，表示处于同一层级的个体i与其相邻两个解的距离，距离越大则该解处于越不拥挤的区域，该个体及其对应的解越好。i_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}和i_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}的计算方法参照文献[16]。

在进行种群选择操作时，对父代种群、子代种群和储存池中的所有解按照第一关键字rank升序、第二关键字distance降序的方式进行排序，然后选择前P_Size个个体进入下一代，作为新的父代种群，过程如图5所示。

3　 实验结果与分析

本文所有测试在一个频率为2.8 Hz，运行内存为4 GB的计算机上进行。本文的IMOMA算法代码在C++中编码，编译环境为Visual Studio 2008，为了验证本文模型和算法的有效性，与CPLEX优化软件求解的数学模型结果进行对比，使用的优化软件为IBM ILOG CPLEX 12.2的版本^[17-18]。

3.1　实验数据

为了验证本文构建的数学模型及IMOMA的效果，结合国内某航空咨询公司提供的实际数据构造算例进行实验。对实际数据算例进行分析得到：每天的任务数量超过400个，而班次超过100个。根据咨询公司提供的机场实际数据情况设置D=\mathrm{14},\theta =\mathrm{2}，再通过公式（17）的限制约束发现每天任务和班次的比例大概为3∶1。每个测试算例中的任务和班次都是从实际数据中随机筛选生成的，用“t\_s”表示算例，其中t代表任务，s代表班次，比如：“\mathrm{6}\_\mathrm{2}”表示算例中包含6个任务和2个班次。基于数据测试，改进的多目标文化基因算法实验参数设定如下：种群规模P_size=10，交叉概率P_{\mathrm{c}}=\mathrm{0.8}，变异概率P_{\mathrm{m}}=\mathrm{0.3}，存储池容量C_size=40，最大迭代次数\mathrm{I}\mathrm{t}\mathrm{e}\mathrm{r}\_\mathrm{M}\mathrm{a}\mathrm{x}=\mathrm{50}。

3.2　非完全覆盖率对目标函数的影响

由于考虑了最大化任务指派所产生的效益和最小化资格技能水平差的总和这两个目标函数，而这两个目标函数之间存在矛盾，算法的最终求解结果是一个存在多个满意解的Pareto解集，综合考虑班次利用率和工作人员的劳动强度，本文将覆盖率\beta设置为0.8。结合航空公司的优化需求，依次按照最大化任务指派所产生的效益、最小化任务与班次之间相应资格技能水平差的总和顺序选择3个非支配解作为算例输出结果。

3.2.1　小规模算例实验结果

为了验证本文模型和算法的有效性，分别对10个小规模的实验算例进行求解，并与CPLEX优化软件和IMOMA_Initial算法进行对比，其中，IMOMA_Initial算法是指IMOMA算法中未包含改进以及基于Pareto排序过程的部分，设置最长运行时间为5 400 s。表1给出了CPLEX、IMOMA和IMOMA_Initial求解小规模算例的结果对比。由CPLEX与IMOMA的求解结果可知，IMOMA算法求得的第一目标函数值的第一个解与Z_{\mathrm{1}}^{\mathrm{C}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}}一致，对应的第二目标函数值的均值不大于Z_{\mathrm{2}}^{\mathrm{C}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}}，说明了模型和算法的有效性。这是因为CPLEX无法求解多目标函数，只能求解第一目标函数，Z_{\mathrm{2}}^{\mathrm{C}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}}的值是在第一目标函数值的基础上计算出来的。由IMOMA与IMOMA_Initial的求解结果可知，这10个算例中有3个双方都得到了唯一解，说明基于Pareto的优化方法在求解最优解时鲁棒性较好。在其余7个算例中，除了算例“36_12”和“18_6”以外，其余5个算例IMOMA求得的Pareto最优解都要优于IMOMA_Initial，比如算例“24_8”中，当(Z_{\mathrm{2}\_\mathrm{2}}=\mathrm{45})=(Z_{\mathrm{3}\_\mathrm{2}}=\mathrm{45})时，(Z_{\mathrm{2}\_\mathrm{1}}=\mathrm{6}\mathrm{873})>(Z_{\mathrm{3}\_\mathrm{1}}=\mathrm{6}\mathrm{161})，说明IMOMA求解多目标问题时具有很大的优势。从计算耗时看，IMOMA的求解时间比IMOMA_Initial的求解时间长，这是因为局部搜索需要在个体的基础上搜索大量的领域结构，从而增加了程序的运行时间，而基于Pareto的排序又增加了IMOMA的运算时间，但是对于小规模算例，IMOMA算法仍然可以在60 s内求得问题的最优解，也能满足实时性要求。

3.2.2　大规模算例实验结果

使用改进的多目标文化基因算法对大规模算例进行求解，结果如表2所示。由表2可知，当算例规模增大到183_61时，CPLEX无法在规定时间（5 400 s）内进行求解，而本文算法仍能够在规定的时间内对算例进行求解，并可以提供多个满意解。从前6个CPLEX、IMOMA求解的算例可以看出，一方面，虽然IMOMA没有求得最优解，但是从已经求得的算例可知，IMOMA可以提供高质量的近似最优解，Gap1平均值小于0.90%；另一方面，因为本文使用的IMOMA可以求解多目标整数规划模型，而CPLEX只能保证第一目标函数值最优，无法对第二目标函数进行优化，因此，IMOMA在保证第一目标函数值近似最优解时，第二目标函数值都优于Z_{\mathrm{2}}^{\mathrm{C}\mathrm{P}\mathrm{L}\mathrm{E}\mathrm{X}}的值，Gap3的绝对值最大达到7.41%，平均优化5.89%，进一步证明了本文模型和算法能够提供高质量的近似Pareto前沿。

3.3　参数灵敏度分析

3.3.1　覆盖率\beta对目标函数值的影响

为了研究覆盖率\beta对目标函数值的影响，随机生成6个算例进行实验。每个算例结果取IMOMA求得三个满意解的平均值，测试结果如图6所示。分别取覆盖率\beta=1，0.8，0.6，其中，\beta=1表示全覆盖，意味着一旦任务被执行就要求被完全覆盖。从图6(a)可以看出，第一目标函数值随覆盖率降低而显著增加，当\beta=0.8时，第一目标函数值的均值增加了7.60%，当\beta=0.6时，第一目标函数值的均值增加达到9.97%；从图6(b)可以看出，第二目标函数值随覆盖率的降低而增加，当\beta=0.8时，第二目标函数值的均值增加了6.45%，当\beta=0.6时，第二目标函数值的均值增加了9.67%，整体增加率低于图6(a)中测试结果的增加率。

3.3.2　班次工作时长对目标函数的影响

在企业的实际运作中，由于某一时间段内任务量繁重，为了完成任务而延长半个小时或者一个小时的工作时长是很普遍的现象。通过对实际数据的检验发现，有部分任务的任务时长是30 min或者60 min，一些班次虽然能满足资格和技能水平等的要求，但由于没有足够的工作时长，使得这些任务不能被执行。

为了分析班次工作时长对目标函数的影响，对随机生成的6个算例进行实验，表3给出了利用IMOMA求解算例的原始结果，以及分别在算例基础上班次的工作时长增加30 min和增加60 min的求解的结果。由实验结果可以看出，在保持其他约束和属性不变的情况下，随着工作时长的增加，第一目标函数值增加，第二目标函数值也增加，而平均求解时间上变化不大。特别是当班次的工作时长增加60 min时，第一目标函数值的均值从18 923增加到20 065，增加了6.03%，这表明适当增加班次的工作时长，第一目标函数值有显著提高，从而对机场的任务完成率和班次的工作效率都有积极影响。

3.3.3　任务的资格要求对目标函数的影响

为了提高企业的服务质量，增加企业市场竞争力，现在越来越多企业重视员工技能培训以提高员工的工作能力。随着员工技能提高，任务资格要求也就相对降低了。

为了研究任务资格要求对目标函数的影响，对随机生成的6个算例进行实验，表4分别给出了利用IMOMA求解算例的原始结果，以及分别在算例基础上任务资格要求降低25%和50%（其他属性保持不变）的求解结果。由表4可知，在保持其他约束和属性不变的情况下，随着任务要求的降低，第一目标函数值增加，第二目标函数值也增加，而平均求解时间变化仍不大。当任务资格要求降低50%时，Z_{\mathrm{2}\_\mathrm{1}}的均值从18 923增加到22 643，增加了19.66%，而Z_{\mathrm{2}\_\mathrm{2}}的均值从129增加到141，增加了9.30%，平均求解时间的增加更加明显。因此，通过均值的变化发现，降低任务资格要求会对总效益目标产生较大程度的影响，从而对机场任务完成率影响也更直观。

4　 结 语

本文研究了基于非完全覆盖的机场任务指派问题，建立了多目标的整数规划模型，并通过模型分析和研究问题的特征提出有效不等式。对于小规模算例，使用CPLEX求解软件可以求得单目标模型的最优解，但是由于CPLEX优化软件无法求解多目标函数模型，同时求解规模十分有限，不能够满足实际运作需求。为了解决这一问题，本文提出一种改进的多目标文化基因算法，将改进的遗传算法应用于全局搜索，将大邻域搜索算法应用于局部搜索，并引入基于Pareto等级i_{\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}}和拥挤度距离i_{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{n}\mathrm{c}\mathrm{e}}的种群选择操作，解决多目标优化问题中目标间的矛盾。对于小规模算例，与CPLEX求解结果的对比验证了本文模型和算法的有效性；对于大规模算例，IMOMA可以在规定时间内求得高质量的近似最优解，说明IMOMA求解多目标问题时具有很大的优势。对覆盖率、班次工作时长和任务的资格要求等参数进行灵敏度分析，结果表明不同参数的设置对总效益函数值和资格技能水平差总和的影响都很显著。通过这些算例的测试结果对比，得出具有指导意义的结论：当旺季机场任务数量增加时，任务的覆盖率可以设置为80%，而临时突发状态发生时覆盖率的值可以设置为60%左右，同时也可以考虑增加班次工作时长30~120 min不等；当机场对员工技能培训次数比较频繁时，资格的匹配度可以降低25%~50%。通过以上不同参数的设置，不仅可以改善机场的资源利用率，而且还可以提高服务水平，增强市场竞争力。未来可进一步将机场任务指派与航班计划问题相结合，研究航空调度问题；当前算法求解时间和规模上仍有提升空间，未来可研究求解速度更快和求解规模更大的优化算法。

参考文献

[1] IP W H， WANG D W， CHO V. Aircraft ground service scheduling problems and their genetic algorithm with hybrid assignment and sequence encoding scheme［J］. IEEE Systems Journal， 2013， 7（4）： 649-657. DOI： 10.1109/JSYST.2012.2196229 .

[2] KIERMAIER F， FREY M， BARD J F. The flexible break assignment problem for large tour scheduling problems with an application to airport ground handlers［J］. Journal of Scheduling， 2020， 23 （2）： 177-209. DOI： 10.1007/s10951-019-00635-5 .

[3] ZHENG H F， WANG Z M， ZHENG C P， et al. A graph multi-attention network for predicting airport delays［J］. Transportation Research Part E： Logistics and Transportation Review， 2024， 181：103375. DOI： 10.1016/j.tre.2023.103375 .

[4] IKLI S， MANCEL C， MONGEAU M. The aircraft runway scheduling problem： A survey［J］. Computers & Operations Research， 2021， 132： 105336. DOI： 10.1016/j.cor.2021.105336 .

[5] BAREA A， DE CELIS R， CADARSO L. An integrated model for airport runway assignment and aircraft trajectory optimization［J］. Transportation Research Part C： Emerging Technologies， 2024， 160： 104498. DOI： 10.1016/j.trc.2024.104498 .

[6] LI J， LI K P， TIAN Q N， et al. A column generation-based algorithm for gate assignment problem with combinational gates［J］. Expert Systems with Applications， 2024， 238： 121792. DOI： 10.1016/j.eswa.2023.121792 .

[7] ORNEK M A， OZTURK C， SUGUT I. Integer and constraint programming model formulations for flight-gate assignment problem［J］. Operational Research， 2022， 22（1）： 135-163. DOI： 10.1007/s12351-020-00563-9 .

[8] 田倩南， 李昆鹏， 李文莉， 等. 机场任务指派问题的优化方案研究［J］. 运筹与管理， 2019， 28（11）： 1-8. DOI： 10.12005/orms.2019.0241 .

[9] TIAN Q N， LI K P， LI W L， et al. Research on optimization of airport task assignment problem［J］. Operations Research and Management Science， 2019， 28（11）： 1-8. DOI： 10.12005/orms.2019.0241（Ch ）.

[10] CHEN S T， ERMIŞ G， SHARPANSKYKH A. Multi-agent planning and coordination for automated aircraft ground handling［J］. Robotics and Autonomous Systems， 2023， 167： 104480. DOI： 10.1016/j.robot.2023.104480 .

[11] FREY M， KIERMAIER F， KOLISCH R. Optimizing inbound baggage handling at airports［J］. Transportation Science， 2017， 51（4）： 1210-1225. DOI： 10.1287/trsc.2016.0702 .

[12] YANG X Q， FENG R C， XU P C， et al. Internet-of-Things-augmented dynamic route planning approach to the airport baggage handling system［J］. Computers & Industrial Engineering， 2023， 175： 108802. DOI： 10.1016/j.cie.2022.108802 .

[13] GUPTA V， MITRA R， KOENIG F， et al. Predictive maintenance of baggage handling conveyors using IoT［J］. Computers & Industrial Engineering， 2023， 177： 109033. DOI：10.1016/j.cie.2023.109033 .

[14] ZENG L S， ZHAO M Y， LIU Y F. Airport ground workforce planning with hierarchical skills： A new formulation and branch-and-price approach［J］. Annals of Operations Research， 2019， 275（1）： 245-258. DOI： 10.1007/s10479-017-2624-y .

[15] GUIMARANS D， PADRÓN S. A stochastic approach for planning airport ground support resources［J］. International Transactions in Operational Research， 2022， 29（6）： 3316-3345. DOI： 10.1111/itor.13104 .

[16] WANG W S， XIE K X， GUO S Q， et al. A shift-based model to solve the integrated staff rostering and task assignment problem with real-world requirements［J］. European Journal of Operational Research， 2023， 310（1）： 360-378. DOI： 10.1016/j.ejor.2023.02.040 .

[17] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197. DOI： 10.1109/4235.996017 .

[18] XU D Y， LI K P， YANG J H， et al. A multicommodity unpaired pickup and delivery vehicle routing problem with split loads and unloads［J］. Industrial Management & Data Systems， 2020， 120（8）： 1565-1584. DOI： 10.1108/IMDS-01-2020-0050 .

[19] LI J， LI K P， TIAN Q N， et al. An improved column generation algorithm for the disrupted flight recovery problem with discrete flight duration control and aircraft assignment constraints［J］. Computers & Industrial Engineering， 2022， 174： 108772. DOI： 10.1016/j.cie.2022.108772 .

基金资助

国家自然科学基金青年项目(72001072)

湖北省教育厅科学研究计划项目(D20232204)

湖北省高等学校优秀中青年科技创新团队计划项目(T2022024)

湖北省普通高等学校人文社会科学重点研究基地项目(DSS20220603)