基于0-1整数规划的签派员任务分配优化

Dispatcher Task Assignment Optimization Based on 0-1 Integer Programming

摘要: 航班签派是航空公司运行控制的核心环节，签派员的工作负荷与任务分配的合理性直接关系到航班运行的安全与效率。针对传统人工分配模式中存在的负荷不均、技能错配、应急响应迟滞等问题，本文提出了一种面向航班签派任务的数学优化模型。本文以签派员是否放行航班为决策变量，以航空公司成本最低为目标构建目标函数，建立0-1规划模型。并且使用二阶模拟退火算法对该数学模型进行求解，数值算例证明了模型的有效性。通过将二阶模拟退火算法与遗传算法和蚂蚁算法进行对比，说明了二阶模拟退火算法在求解该问题中的优越性。

Abstract: Flight dispatch is a core aspect of airline operations control, and the workload and task allocation of dispatchers are directly related to the safety and efficiency of flight operations. Addressing issues in traditional manual allocation models, such as uneven workload, skill mismatches, and delayed emergency responses, this paper proposes a mathematical optimization model for flight dispatch tasks. The decision variable in this model is whether the dispatcher releases a flight, and the objective function is constructed to minimize airline costs, forming a 0-1 programming model. A second-order simulated annealing algorithm is used to solve this mathematical model, and numerical examples demonstrate the model’s effectiveness. By comparing the second-order simulated annealing algorithm with genetic algorithms and ant colony optimization, the superiority of the second-order simulated annealing algorithm in solving this problem is illustrated.

1. 引言

民航业的快速发展和航班量的持续增长，对航空公司运行控制中心的签派放行工作效率与安全性提出了更高要求。签派员作为航班运行控制的核心决策者，其任务分配的合理性直接关系到航班运行的安全与正常[1]。当前，签派员的任务分配主要依赖人工经验，面临着工作负荷不均、资质与任务匹配度不高、在复杂运行条件下难以动态优化等问题[2]。因此，构建科学、高效、自动化的签派员任务分配模型与优化方法，对于提升运行控制精细化水平、保障民航可持续安全发展具有重要意义[1]。

签派员任务分配问题可被抽象为一个典型的组合优化问题。0-1整数规划是描述此类“是否分配”决策问题的有效数学工具，它能够清晰地将任务与人员的匹配关系、各类业务约束(如资质匹配[3] [4]、负荷均衡[2]、连续性要求等)形式化为数学表达式[5]。已有研究利用0-1规划模型成功解决了编组计划等类似资源分配问题[6]。然而，签派员任务分配问题约束复杂、解空间庞大且非线性特征明显，属于NP难问题，传统的精确求解算法往往难以在可接受时间内获得满意解[5]。

为高效求解这类复杂的0-1整数规划问题，元启发式算法因其强大的全局搜索能力和对问题结构的低依赖性而备受青睐[7]。模拟退火算法作为一种经典的元启发式算法，通过模拟物理退火过程，以一定的概率接受劣解，从而有效避免陷入局部最优，已被成功应用于轧制批量计划、编组计划等工业优化问题中[6] [8]。近年来，教与学优化算法等新型元启发式算法也被提出并用于连续和非线性优化[9] [10]，甚至有研究尝试将其与模拟退火算法融合，以提升寻优性能[11]。这为改进传统模拟退火算法、增强其在离散组合问题中的求解效率提供了思路借鉴。本文以签派员是否放行航班为决策变量，以航空公司成本最低为目标构建目标函数，建立0-1规划模型，并用二阶模拟退火算法对该数学模型进行求解。

本文的第二节将通过某航空公司的问题描述以及根据描述提出的模型假设来明确研究对象、分类标准及建模前提条件。第三节通过将签派员是否放行某一航班为决策变量和最小化航空公司总运营成本为目标函数来构建数学优化模型。第四节将设计两阶段模拟退火算法，通过分阶段优化来解决多目标权衡问题。第五节则是通过具体数据验证模型在实际场景中的可行性与优化效果。第六节则是将设计的两阶段模拟退火算法与遗传算法和蚂蚁算法进行对比，验证算法的优越性。

2. 问题描述与模型假设

在民航局及航空公司运行政策中，航班可分为不同类别，如国际航班、特殊机场航班、普通航班，不同航班类型对飞行员、放行签派员的训练、考核要求不同，航班任务性质决定了飞行签派员任务分配策略，如表1。

Table 1. Classification of flight types and requirements for flight dispatchers

表1. 航班性质划分以及对飞行签派员的要求

航班性质	定义	对飞行签派员的要求
国际航班	起飞或着陆机场为中国境外的航班	接受国际运行相关培训并获取资质
特殊航班	起飞或着陆机场为特殊、复杂机场的航班	接受特殊、复杂机场相关培训并获取资质
普通航班	除国际航班及特殊机场航班以外的航班	取得普通放行资质

本文假设某航空公司共有$I$ 个航班，索引为$i=1,2,\cdots ,I$ 。航班集合可以划分为三个互斥的子集，国际航班集合$I_1$ ，特殊航班集合$I_2$ ，普通航班集合$I_3$ 。$I_1\cup I_2\cup I_3=\left\{1,2,\cdots ,I\right\}$ .并且$I_1\cap I_2=\varnothing$ ，$I_2\cap I_3=\varnothing$ ，$I_1\cap I_3=\varnothing$ 。

设该航空公司共有$J$ 名签派员，索引为$j=1,2,\cdots ,J$ 。签派员集合可以划分为三个互斥的子集，国际资质签派员集合$J_1$ ，特殊资质签派员集合$J_2$ ，普通资质签派员集合$J_3$ 。$J_1\cup J_2\cup J_3=\left\{1,2,\cdots ,J\right\}$ ,并且$J_1\cap J_2=\varnothing$ ，$J_2\cap J_3=\varnothing$ ，$J_1\cap J_3=\varnothing$ 。

根据该航空公司的实际运营情况和表1，我们做如下假设：

假设1：$\forall i\in I_1$ ，则只能分配给$j\in J_1$ ；若$\forall i\in I_2$ ，则只能分配给$j\in J_2$ ；若$\forall i\in I_3$ ，则可以分配给$j\in J_1\cup J_2\cup J_3$ 。

假设2：每个航班只能由一名签派员负责，一名签派员可以负责多个航班。

假设3：不同签派员的薪资比例不同，设普通资质签派员单位薪资为$c$ ，则国际资质和特殊资质签派员的单位薪资分别为$k_{1}c$ 和$k_{2}c$ ($k_1\ge 1$ , $k_2\ge 1$ )。

假设4：设处理一个普通航班的工作量为1个标准单位，国际航班和特殊航班的工作量复杂度高，国际航班的工作量相当于$r_1$ 个标准单位，特殊航班的工作量当于$r_2$ 个标准单位($r_1\ge 1$ , $r_2\ge 1$ )。

假设5：不考虑签派员的疲劳度，个人偏好，休息时间等因素，视为计划期内的静态分配。

假设6：所有签派员在其资质范围内的工作能力相同。

假设7：每个航班的工作量已知。

假设8：每个航班$j$ 有固定的执行时间段$\left[t_j^{\text{strat}},t_j^{\text{end}}\right]$ ，且在该时间段内持续占用签派员的处理能力。

假设9：每个签派员$i$ 在任意时间段$t$ 的处理能力峰值为$p_i$ (可处理的最大工作量)。

3. 优化模型

对于$\forall i\in I,\forall j\in J$ ，我们令

$x_{ij}=\{\begin{array}{l}1,航班i分配给签派员j\\ 0,航班i不分配给签派员j\end{array}$

代价系数$C_{ij}$ 表示将航班$i$ 分配给签派员$j$ 所产生的成本。它由签派员$j$ 的单位成本系数$s_j$ 和航班$i$ 的工作量系数$w_i$ 共同决定。根据假设3和假设4可知：

$w_i=\{\begin{array}{l}{r}_1,如果i\in I_1\\ r_2,如果i\in I_2\\ 1,如果i\in I_3\end{array}{s}_j=\{\begin{array}{l}{k}_{1}c,如果j\in J_1\\ k_{2}c,如果j\in J_2\\ c,如果j\in J_3\end{array}$

则我们可以得到代价系数$C_{ij}$ ，即

$C_{ij}=w_i\ast s_j$

$C_{ij}$ 的含义为：成本为$s_j$ 的签派员去完成一个工作量为$w_i$ 的航班，所消耗的成本为两者乘积。

我们以该航空公司运营成本最小化为目标，构建目标函数如下：

$\min z={\displaystyle \sum _{i=1}^I{\displaystyle \sum _{j=1}^J{C}_{ij}\times x_{ij}}}$

下面我们描述约束条件。根据假设1可知：对于国际航班有：

${\displaystyle \sum _{j\notin J_1}{x}_{ij}}=0,\forall i\in I_1$

对于特殊航班有：

${\displaystyle \sum _{j\notin J_2}{x}_{ij}}=0,\forall i\in I_2$

根据假设2可知

${\displaystyle \sum _{j=1}^J{x}_{ij}=1,\forall i=1,\cdots ,I}$

除此之外，为了尽量使每个签派员的工作总量相差最小，而工作量的差异可以通过最小化所有签派员工作量的方差来实现，所以引入辅助变量$W_{\text{mean}}$ ：

$W_{\text{mean}}=\left[\frac{r_1\left|I_1\right|+r_2\left|I_2\right|+\left|I_3\right|}{J}\right]$ ,

其中，符号$\left[a\right]$ 表示对实数$a$ 向上取整，符号$\left|I_i\right|$ 表示集合$I_i$ 的元素个数$\left(i=1,2,3\right)$ 。继而我们对每个签派员的工作量上界进行约束，即：

${\displaystyle \sum _{i=1}^I{w}_i\times x_{ij}\le W_{\text{mean}},\forall j\in 1,2,\cdots ,J}$

对于每个签派员i，在任意时刻t，其同时处理的航班数量不能超过最大并行处理能力$p_i$ 这可以通过以下约束表示：对于任意两个不同的航班j和k，如果它们的时间区间重叠，则不能分配给同一个签派员，除非该签派员的并行处理能力允许。

时间冲突指示变量：

${\xi }_{jk}=\{\begin{array}{l}1,\text{if}\max \left(t_j,t_k\right)<\min \left(t_j,t_k\right)\\ 0,\text{else}\end{array}$

对任意签派员$i$ 在任意时间段$t$ 内的总工作量不超过其能力峰值$p_i$ ：

${\displaystyle \sum j}\in J:t\in \left[t_j^{\text{start}},t_j^{\text{end}}\right]w_i\times x_{ij}\le p_i,\forall i\in I,\forall t\in T$

综上，我们建立的数学模型如下：

$\min z={\displaystyle \sum _{i=1}^I{\displaystyle \sum _{j=1}^J{C}_{ij}\times x_{ij}}}$

s.t. $x_{ij}\in \left\{0,1\right\}$

${\displaystyle \sum _{j\notin J_1}{x}_{ij}=0},\forall i\in I_1$

${\displaystyle \sum _{j\notin J_2}{x}_{ij}=0},\forall i\in I_2$

${\displaystyle \sum _{j=1}^J{x}_{ij}=1,\forall i=1,\cdots ,I}$

${\displaystyle \sum _{i=1}^I{w}_i\times x_{ij}\le W_{\text{mean}},\forall j\in 1,2,\cdots ,J}$

${\xi }_{jk}=\{\begin{array}{l}1,\text{if}\max \left(t_j,t_k\right)<\min \left(t_j,t_k\right)\\ 0,\text{else}\end{array}$

${\displaystyle \sum j}\in J:t\in \left[t_j^{\text{start}},t_j^{\text{end}}\right]w_i\times x_{ij}\le p_i,\forall i\in I,\forall t\in T$

4. 算法设计

本文使用两阶段模拟退火算法来解决航班签派员分配问题。这是一种元启发式优化算法，结合了局部搜索和随机搜索的特点，专门用于解决组合优化问题。图1为算法流程图。

Figure 1. Algorithm flowchart

图1. 算法流程图

算法第一阶段的目标是找到工作量分配最平均的方案，确保所有签派员的工作量尽可能接近平均值。其核心思想是通过模拟退火算法优化工作量的公平性，暂时不考虑成本因素。算法第一阶段的执行过程有三个步骤，步骤1是初始化解，其特点为国际航班分配给国际签派员(随机选择)、特殊航班分配给特殊签派员(随机选择)、普通航班轮询分配给所有签派员(确保初步平衡)。步骤2是温度控制即主循环，采用邻居解生成策略，即在保持资格约束的前提下，随机选择航班分配给有资格的签派员。步骤3则为温度下降，通过不断迭代完成从广泛搜索到精细搜索的转变，完成工作量的均分。图2是算法第一阶段流程图。

Figure 2. Flowchart of the first phase of the algorithm

图2. 算法第一阶段流程图

算法第二阶段的目标是在第一阶段找到的平衡方案基础上，进一步降低总成本，同时保持工作量基本平衡。其核心思想是引入平衡容忍度，允许工作量有轻微不平衡，以换取成本的大幅降低。算法的设计原理是惩戒机制，即允许第二阶段方案比第一阶段差10%，在110分以内，可以自由优化成本，而超过110分，施加严厉惩罚。算法第二阶段的执行过程也分有三个步骤，步骤1是从第一阶段最佳解开始，这既避免了从头搜索，又能进行更精细的搜索。步骤2是成本导向的邻居生成策略优化，其目标导向是主动引导搜索向低成本方向移动，步骤3则是带约束的退火搜索，其搜索特点为在平衡容忍度范围内自由优化成本，一旦超出容忍度，惩罚机制会自动拒绝该解，温度较低，接受较差解的概率小，收敛更稳定。图3是算法第二阶段流程图。

Figure 3. Flowchart of the second phase of the algorithm

图3. 算法第二阶段流程图

两阶段设计既保证了算法的全局搜索能力，又通过分阶段优化提高了求解效率，解决了多目标优化中的权衡问题，实现了经济效益的最大化。

5. 数值算例

本文令$r_1=r_2=2$ ，即国际航班的工作量为2个标准单位，特殊航班的工作量为2个标准单位；成本系数$c=50$ ；令$k_1=1.5$ ，$k_2=1.5$ ，即国际资质的签派员的工作薪资为$1.5c$ ，特殊资质的签派员的工作薪资为$1.5c$ 。假设国际资质签派员的数量$\left|J_1\right|=5$ ，特殊资质签派员的数量$\left|J_2\right|=3$ ，普通资质签派员的数量$\left|J_3\right|=11$ ；国际航班的数量$\left|I_1\right|=22$ ，特殊航班的数量$\left|I_2\right|=10$ ，普通航班的数量$\left|I_3\right|=268$ 。求解结果为：平均工作量为17.47，工作量标准差为0.5，在平衡工作量差异约束下最小成本为20,000，签派员最大并行处理能力为4，即签派员同时处理的航班数为4，国际航班：开始时间约08:00左右，特殊航班：开始时间约08:00左右，普通航班：开始时间约07:30左右，国际航班和特殊航班所需的时间为5分钟，普通航班所需的时间为3分钟。结果为国际航班在08:30左右结束；特殊航班在08:30左右结束，普通航班在08:30左右结束。表2是签派员分配的航班数和工作量以及分配的航班编号。

Table 2. Summary of flights managed by each dispatcher

表2. 各签派员负责签派的航班情况汇总表

编号	资质	签派国际航班数	签派特殊航班数	签派普通航班数	签派航班总数	总工作量
01	国际	5	0	7	12	17
02	国际	5	0	7	12	17
03	国际	5	0	7	12	17
04	国际	4	0	9	13	17
05	国际	3	0	11	14	17
06	特殊	0	2	13	15	17
07	特殊	0	4	9	13	17
08	特殊	0	4	9	13	17
09	普通	0	0	18	18	18
10	普通	0	0	18	18	18
11	普通	0	0	18	18	18
12	普通	0	0	18	18	18
13	普通	0	0	17	17	17
14	普通	0	0	18	18	18
15	普通	0	0	17	17	17
16	普通	0	0	18	18	18
17	普通	0	0	18	18	18
18	普通	0	0	18	18	18
19	普通	0	0	18	18	18

6. 算法性能对比

为验证本文所提二阶模拟退火算法的有效性与优越性，将其与遗传算法(GA)、蚁群算法(ACO)在相同算例下进行对比实验。下面我们从五个方面评估这两个算法的性能。

一、是算法的优化能力，包含最终总成本和成本降低率。最终总成本的定义为在满足所有约束条件的前提下，算法求得的最优分配方案所对应的航空公司总运营成本，其数学表达式是

$C_{\text{final}}={\displaystyle {\sum }_{i=1}^I{\displaystyle {\sum }_{j=1}^J{C}_{ij}\times x_{ij}}}$ ，

最终总成本的数值越小，表示算法找到分配方案的成本越低，也就意味着求解结果更优；成本降低率的定义为算法优化后最终成本相对于初始平均成本的下降百分比，成本降低率反映算法的优化效果。其数学表达式是

$\text{Reduction}\text{Rate}=\frac{C_{\text{avg}}-C_{\text{final}}}{C_{\text{avg}}}\times 100\%$ ，

其中，$C_{\text{avg}}$ 为k个随机初始解的平均成本，$C_{\text{avg}}=\frac{1}{k}{\displaystyle {\sum }_{k=1}^k{C}_{\text{initial}}}$ ，其中$C_{\text{initial}}$ 为第k个初始解的成本，${\text{C}}_{\text{fina}}$ 为算法求得的最优解成本。成本降低率越大，表示算法对初始解的改进程度越大。

二、是解的质量稳定性，即成本方差。成本方差的定义为算法在多次运行或单次运行中产生的可行解的成本波动程度，反映了算法的稳定性。成本方差的数学表达式为

$Var\left(C\right)=\frac{1}{N-1}{{\displaystyle {\sum }_{k=1}^N\left(C_k-\overline{C}\right)}}^2$ 。

N为样本解的数量(可以是多次运行的最优解，或单次迭代中的候选解)，$C_k$ 为第k个解的成本，$\overline{C}$ 为样本解的平均成本，其中$\overline{C}=\frac{1}{N}{\displaystyle {\sum }_{k=1}^N{C}_k}$ 。成本方差反映了算法的鲁棒性和收敛一致性。成本方差越小

表示算法每次找到的解质量越稳定，波动越小。

三、是负荷均衡性，即工作量平衡分数(标准差)。工作量平衡分数是衡量各签派员之间工作量分配均衡程度的指标。工作量平衡分数的数学表达式为

$B=\sigma \left(W\right)=\sqrt{\frac{1}{I}{{\displaystyle {\sum }_{i=1}^I\left(W_i-\overline{W}\right)}}^2}$

工作量平衡分数越小表示各签派员之间工作量越均衡。

四、是计算效率即算法运行时间，其定义是算法从开始到结束所消耗的实际时间。运行时间反映了算法的计算效率，数值越小表示算法的求解速度越快。

五、是算法约束满足能力即有效解比例。有效解比例的定义是算法在搜索过程中产生的满足所有约束条件的可行解所占的比例，反映了算法的约束处理能力。有效解比例的数学表达式为

$R_{\text{valid}}=\frac{N_{\text{vaild}}}{N_{\text{total}}}\times 100\%$

其中$N_{\text{vaild}}$ 为满足所有约束条件的解的数量，$N_{\text{total}}$ 为算法生成的解的总数(包括接受和拒绝的解)有效解比例越高，表示算法生成的可行解越多，100%表示所有生成的解都是可行的。详细对比数据如表3。

Table 3. Comparison of performance of different algorithms

表3. 不同算法性能对比表

指标	二阶模拟退火	遗传算法	蚁群算法
最终总成本	20000	20200.00	20400.00
成本降低率	10.3%	7.9%	5.3%
成本方差	196.42	30.69	2422.25
工作量平衡分数	0.5 (标准差)	1.5984	5.7069
运行时间(秒)	14.58	18.02	78.76
有效解比例	100%	98%	100%

根据表3数据可知，在算法的成本优化能力方面，本文提出的二阶模拟退火算法取得了最优值20000，分别比遗传算法低1.0%、比蚁群算法低2.0%。从成本降低率来看，二阶模拟退火达到10.3%，显著高于遗传算法的7.9%和蚁群算法的5.3%。这一优势主要得益于算法的两阶段设计：第一阶段确保工作量均衡，第二阶段在容忍度范围内进一步优化成本，有效避免了过早陷入局部最优。在解的质量稳定性方面：遗传算法在成本方差指标上表现最优(30.69)，表明其解的分布最为集中。二阶模拟退火算法方差为196.42，处于可接受范围。蚁群算法方差高达2422.25，说明其解的质量波动较大，稳定性较差。遗传算法的选择操作保留了优良基因，而蚁群算法的信息素更新机制在本问题中易导致收敛不稳定。在工作量均衡性分析方面：工作量均衡是签派员任务分配的核心约束之一。二阶模拟退火算法的工作量标准差仅为0.5，远优于遗传算法的1.5984和蚁群算法的5.7069。这一显著优势源于算法第一阶段的专门优化：通过轮询初始化策略和均衡导向的邻域搜索，确保了各签派员负荷高度均衡。在计算效率方面：二阶模拟退火算法仅需12.36秒，比遗传算法快19.1%，比蚁群算法快81.5%。二阶模拟退火的高效性体现在：第一阶段快速获得均衡解；第二阶段在优质解基础上局部搜索，避免全局重复探索。对于算法的收敛性分析，两阶模拟退火算法与蚂蚁算法和遗传算法相比，收敛曲线平滑可控，避免局部最优能力强，收敛稳定性最好。解接受率在理想范围内(20%~40%)，表明算法参数设置合理。图4是解接受率图。

Figure 4. Acceptance rate diagram

图4. 解接受率图

7. 结论与展望

本文针对航空公司签派员任务分配问题建立了优化模型。模型综合考虑了资质匹配、成本控制和工作量均衡等问题，构建了以公司运营成本最小，资质匹配和工作量均衡为主要约束条件的0-1整数规划模型。使用两阶段模拟退火算法求解，数值算例和算法的性能对比说明了模型和算法的有效性和优越性。

NOTES

^*通讯作者。