复杂时空网络冲突消解群组角色指派研究

刘冬宁，向佳敏，曾思敏，叶自青

(广东工业大学 计算机学院，广东 广州 510006)

信息化进程的持续推进和跨行业的融合发展进一步扩张了对公共资源的紧缺程度，例如在生产管理、交通运输、航空运营管理等调度背景[1]下，由于任务集时间约束和空间约束的紧密耦合[2-4]，形成复杂的时空网络[5-6]，难以合理将任务分拆、解耦与优化，从而影响了各工作任务的高效协同与执行。因此，急需进行时空冲突消解以优化组合，缓解资源的压力，降低运营成本。

传统时空网络背景[7]下的任务分配主要考虑特定场景下的约束规则和目标求解，缺乏对时空冲突的系统化方法。虽然目前有许多优化方法求解任务分配问题的逼近最优解[8]，但是对求解响应时间一般要求较高，故很难快速得到无假设前提情况下的最优解[9]。基于此，本文拟以时空网络的经典场景机场登机口调度为例，采用集中式建模、分布式执行方式，对时空网络下的任务冲突消解予以解决。在追求协作效益最大化的同时，采用整数规划方法加速时空网络复杂求解，同时兼顾用户客体偏好(乘客满意度)与任务执行主体的效能(登机口空间利用率)，以求多目标平衡。

本文所采取的方法为角色协同理论(role-based collaboration，RBC)及其E-CARGO模型。该方法与模型可通过群组角色指派(group role assignment，GRA)子模型[10-12]准确描述多约束和多关联关系的协调问题[13-14]。本文针对复杂时空网络的冲突耦合问题，以冲突和协作的关联关系[15]为出发点，对时空约束进行冲突消解，通过GRA，提出可量化和评估的具有一般化和系统化的方法，力求对时空网络的任务指派进行快速响应并提供多样的合理调度方案。

1 场景案例

针对复杂时空网络的冲突消解问题，本文选取机场登机口调度这一经典场景进行分析。

某小型机场让机场调度人员负责对有限的登机口资源进行合理调度，要求进一步提高资源利用率以及中转乘客对航空公司服务质量和水平的满意度。机场现设有70个不同区域位置和功能类型的登机口，假设调度人员需要对未来两天的10架中转飞机进行分配。

首先考虑飞机和登机口的分配问题，计算不同登机口和飞机在机型(宽窄)和功能类型(国内外)上的匹配程度(见表1)，然后根据机场运营规则，同一登机口的两架飞机的间隔时间至少大于45 min，飞机从到达到离开机场的期间只能停靠一个登机口。接着计算出不同飞机之间的时间冲突(见表2)。对于飞机之间的协作情况见表3，停靠时间短的飞机尽量被分配到同一个登机口，以减少登机口的使用数量。

表1 飞机−登机口匹配度评分示例1）Table 1 Aircraft-gate matching score

表2 飞机间的时间冲突情况示例Table 2 Time conflicts between aircraft

表3 飞机间的协作情况示例Table 3 Time cooperation between aircraft

为了提高中转乘客的满意度，调度人员针对中转乘客的换乘流程(如图1)，统计所有中转乘客的基本换乘时间和其到达—出发航班的连接时间。在保证乘客换乘成功的前提下，计算出每个中转乘客在等待登机过程中的中转满意度(见表4)。

图1 中转流程的时空网络结构Figure 1 Spatio-temporal network structure of the transfer process

表4 中转乘客满意度情况部分示例Table 4 Satisfaction of transit passengers

本文研究的是一个考虑协作和冲突的任务指派问题，即一个登机口可以在不同时段停泊多架不同的飞机，但同一个时段只能停泊一架飞机，且应尽量便利乘客换乘。因此，需要解决复杂时空网络下的多目标指派问题，获得能平衡优化中转乘客时间满意度和空间资源利用率的解决方案，降低运营成本的同时提升服务质量。

图1的横轴表示位置，分布着登机口，纵轴表示时间(单位为min，1 440表示1 d)。例如，飞机F1于某一时刻停靠在登机口T1，随后中转乘客P1转乘下一趟航班，前往登机口T3。飞机F1按照航班时刻表离开登机口T1。

2 基于E-CARGO的形式化建模

从上述场景来看，生成平衡多目标解决方案这一过程遵循E-CARGO模型和RBC的初始步骤[16]，并且这类问题的核心等同于群组角色指派问题，故基于E-CARGO模型对问题形式化建模如下。

角色协同理论是由Zhu[17]提出的，其通用模型E-CARGO模型以9元组∑::=＜C,O,A,M,R,E,G,S0,H＞抽象并描述协作系统的组成部分。其中，C表示类；O是对象集合；A是代理集合；M是消息集合，R表示岗位角色集合；E表示环境；G表示群组的协作全部团队；S0为系统最初状态；H为所有成员。在这个模型构建的环境中，由群组的代理执行角色。通过E-CARGO模型，可进一步分配问题抽象为其子模型群组角色指派(GRA)，其中角色、代理对角色的匹配度、指派方案都可以用向量和矩阵形式化表示。

定义1角色R。角色被定义为r:: = ＜id, Ⓡ＞。其中，id是r的标识；Ⓡ是代理扮演r的要求。

在上述场景中，将登机口作为角色，Ⓡ={“到达航班类型”, “出发航班类型”, “ 机型”}。

定义2代理A。代理定义为a::= ＜id,Ⓠ＞。id是a的标识；Ⓠ是与组中所需属性相对应的a值集合。

在上述场景中，代理是指飞机；Ⓠ={“飞机号”,“到达类型”, “机型”, “出发类型”, “停靠时间”}。

定义3属性集Ⓢ：属性集Ⓢ是一组定义为对象的属性。例如，p0，p1，···，pn-1，其中，n= |Ⓢ|。

在上述场景中，Ⓢ= {“到达航班类型”, “出发航班类型”, “机型”, “停靠时间”}，如代理a的“到达航班类型”、“出发航班类型”、“机型”和“停靠时间”分别命名为a.r、a.d、a.m和a.t。

定义4角色需求向量L表示群组中的每个角色至少需要的代理数量，

在上述场景中，登机口作为角色，对停靠的飞机数量无限制条件。

定义5资格评估矩阵Q是一个m×n矩阵。其中，表示代理i对于角色j的评估值。资格评估矩阵Q的具体数值如图2所示。其中，0表示执行力评分最低；表示执行力评分最高。

在上述场景中，需要同时考虑到达航班类型、出发航班类型和宽窄机型的匹配度，a.r和a.d的取值范围为{ 0,1}。对于a.m，当窄型飞机停靠在宽型机位时，a.m=0.5，故定义a.m取值范围为 {0,0.5,1}。飞机对登机口的评估值{0,0.5,1},0≤i＜m,0≤j＜n。

根据飞机对登机口的匹配情况(见表1)，生成资格评估矩阵Q，其示例数值如图2所示。

图2 资格评估矩阵Q 示例Figure 2 Example of qualification matrix Q

在群组角色任务分配过程中，代理之间存在冲突关联，会影响协同和合作。为了考虑避免冲突，引入代理冲突矩阵。

定义6代理冲突矩阵AC是一个m×m对称矩阵。其中，表 示代理i1和 代理i2在执行同一个角色时存在冲突，若为0值则反之。

在上述场景中，飞机作为代理，根据飞机之间存在的冲突情况(见表2)可以生成代理冲突矩阵，其示例数值如图3(a)所示。

定义7分配矩阵T是一个m×n矩 阵。其中，表示代理i被指派执行角色j。

根据上述场景描述，飞机分配给登机口的方案即任务指派的分配矩阵T，其示例数值如图3(b)所示。

图3 代理冲突矩阵AC 和分配矩阵T 示例Figure 3 Example of agent conflict matrix AC and assignment matrix T

定义8群组执行力δ 指派成功后，所有代理的执行力评分总和为

定义9根据上述定义Q和AC，建立群组角色指派模型来找到分配矩阵T。该模型考虑代理之间的冲突，其中，目标函数及其约束如下。

约束条件(1)表示角色分配矩阵T的值只能取0或1，分别表示分配和不分配；约束条件(2)表示分配矩阵T的每一行1的个数总和等于1，即一个代理只能分配到一个角色，保证所有代理都能分配到角色；约束条件(3)表示代理i1和 代理i2存在冲突时，不能同时分配给某一个角色j。

上述模型提供了一个追求群组执行力最大化的方案。为了考虑复杂时空网络的多维目标，对时间成本和空间成本作如下定义。

定义10空间利用率U为一正小数，表示所有资源的平均占用率。其归一化处理为

其中，max{|U|}和 min{|U|}分 别表示U的绝对值的最大值和最小值。

在上述场景中，登机口是有限的空间资源，不考虑维修、清洁等其他情况时，登机口一般处于使用或者空闲状态。定义登机口的利用率为单位调度时间内的总使用时间。

定义11时间满意度S为一正小数，表示指派过程中客体对其时间属性的满意度评估。其归一化处理为

其中，np表 示中转乘客的总数量； max{|S|}和min{|S|}分 别表示S的绝对值的最大值和最小值。

在上述场景中，考虑中转乘客的换乘满意度，对时间满意度的函数表达式为

其中，t表示中转乘客的等待时间；t0表示最小等待时间；[ts,ts+∆t]是最佳等待时间的区间，即对应的时间满意度S(t) = 1，表示达到最大时间满意度；tm表示最大等待时间。时间满意度S(t)的分段函数分布情况如图4所示。

图4 时间满意度函数图Figure 4 Graph of Time satisfaction function

图4说明，在最佳等待时间范围内，中转乘客的满意度最高；当超过最佳等待时间段后，乘客对中转航班的满意度会逐渐降低。

为了解决时空约束耦合、冲突消解的问题，本文提出冲突量化和评估策略，生成新的协作矩阵。

定义12不同角色下的不同代理协作影响矩阵AD代表被分配到不同角色下的不同代理合作产生的影响的评估，是一个由 (m×n)×(m×n)矩阵即(A×R)×(A×R)组 合的nd×d矩阵，nd为 矩阵AD的行数，d=5为 矩阵AD的 列数。表示代理i1分 配给角色j1，且代理i2分 配给角色j2时的影响值( 0≤i1,i2＜m, 0≤j1,j2＜n,i1≠i2,j1≠j2)。

在上述场景中，针对时间满意度这一目标，根据场景要求，选取t0=45，ts=120，∆t=60，tm=360，单位为min，构造时间满意度函数S(t)，生成中转乘客时间满意度(如表4)，作为不同飞机分配给各个登机口的协作值，构成协作矩阵AD，其示例如图5(a)。同时也考虑另一个目标，引入不同的代理承担同个角色情况下的协作影响，以提高团队执行力。

图5 不同角色下和相同角色下的代理协作矩阵Figure 5 Agents collaboration matrix of different roles and role

定义13相同角色下的不同代理协作影响矩阵AS代表被分配到同个角色的不同代理合作产生的影响的评估，是一个由 (m×n)×(m×n)矩 阵即(A×R)×(A×R) 组 合 的ns×d矩 阵，ns为 矩 阵AS的 行 数，d=5为 矩阵AS的 列数。表示代理i1分 配给角色j，且代理i2分 配给角色j时的影响值，其中，0 ≤i1,i2＜m, 0≤j＜n,i1≠i2。

在上述场景中，针对空间利用率这一目标，根据第1节中提到的飞机间的协作情况，计算不同飞机对登机口的占用时长，然后对数据进行规范化处理，构成协作矩阵AS，其示例如图5(b)。

在定义12和定义13中进行了多目标的约束量化。为了考虑主体的多目标偏好，引入多目标的权重系数。

定义14权重系数 α 是一个正小数，其取值范围为[0,1]，代表影响矩阵AD基数的系数。同样，权重系数 β也是一个正小数，表示影响矩阵AS基数的系数，且α +β=1。

定义15影响执行效果矩阵E表示代理分配给角色后，对所执行效果产生的影响，是一个ne×d矩阵。其中，ne为 矩阵E的 行数；d=5为 矩阵E的列数，且E[k,4]∈[0,1],(0≤k＜ne)，表示代理i1分配给角色j1，且代理i2分 配给角色j2时 的影响值。E[k,4]的公式为

通过改变 α，可以生成具有不同数量的二维协作矩阵，并在下文指派模型中将矩阵转为向量，以解耦冲突，构成新的约束。

定义16分配向量Tne是 一个ne维的向量。其中，Tne[k]∈{0,1},0≤k＜ne。Tne[k]=1表 示代理i1被指派执行角色j1的 同时，代理i2被指派执行角色j2(0≤i1,i2＜m, 0≤j1,j2＜n)。

定义17根据上述定义，考虑到影响执行效果E的群组执行力 δE以及约束函数目标函数如下。

除了式(1)、(2)和(3)，还需要满足以下约束。

约束条件(4)表示分配向量Tne的值只能取0或1，分别表示分配和不分配；约束条件(5)和(6)分别表示当代理E[k,0]分 配给角色E[k,1], 且代理E[k,2]分配给角色E[k,3]时，分配向量才为1，若二者有一个分配失败，则分配向量值为0。

通过上述形式化，如果将Q和T矩阵转换为向量，则可以通过IBM ILOG CPLEX优化包处理该线性整数规划问题。

3 CPLEX 解决方案及实验分析

3.1 解决方案及流程图

基于上述模型和定义，为了获得多目标平衡指派方案，需要找出最优解的权重系数α。

设定 α从0.00递增至1.00，步长为0.01，每次改变α，通过CPLEX求解器生成新的分配矩阵T，计算出归一化后的空间利用率和时间满意度，具体算法流程图如图6所示。

图6表明，本文提出的解决方案，其关键在于最优解的选取。通过对权重系数 α进行多次迭代，生成多目标解空间后，采用擂台赛法则构造多目标Pareto最优解集[18]，根据客体偏好确定最优解，获得该解决方案的权重系数α。

图6 算法流程Figure 6 The flow chart of the proposed algorithm

对于寻找帕累托解，例如，假设多目标最大值问题的解空间在坐标轴上的集合为{X1=(0.6,1)，X2=(0.7,0.93)，X3=(0.3,0.93)}。由于X2在横坐标值上大于X3，故排除X3，再考虑X1。由于X1的纵坐标值大于X2，但是X2的横坐标值大于X1，故X1和X2均为帕累托最优解。

3.2 实验设置及结果分析

为了验证上述方法的可行性，采用型号为Inter(R)Core(TM) i5-8400和2.81GHz频率的CPU，以及运行内存为16GB的计算机，运行在Windows 10 Education版本的操作系统，使用IBM公司2019年发布的软件Eclipse作为集成开发环境(IDE)，并选用1.8.0版本的Java语言开发工具包(JDK)，进行相关实验和数据分析。

在上述场景中，登机口作为角色，飞机作为代理，m=10，权重系数 α从0.00递增至1.00，步长为0.01。进行100次求解，计算得到空间利用率和时间满意度随着α 的变化趋势如图7所示。

图7 时间满意度和空间利用率随权重的变化趋势Figure 7 Graph of change trend of time satisfaction and space utilization with weight coefficient

图7表明，时间满意度和空间利用率随权重系数 α的增大成不规律的增减变化，这说明本次实验存在不唯一的最优解。

为了在多目标解空间中找到最优解，对上述100个解的空间利用率和时间满意度分别进行归一化，以时间满意度作为横轴，以空间利用率作为纵轴，生成多目标的散点分布如图8所示。

图8 步长为0.01的时间满意度和空间满意度散点分布Figure 8 The scattered distribution of time satisfaction and space satisfaction with a step size of 0.01

图8表明，此次解空间不存在理想点(1,1)，故构造帕累托最优解，得到解空间集合为{(0.721,1),(1,0.375)}，根据用户对多维目标的偏好，选取权重系数α =0.42，完成此次冲突消解和多目标平衡指派。

本文在GRA模型(简称模型1)基础上引入冲突消解的概念，提出的多目标指派模型(简称模型2)的指派结果如图9，数据分析如表5所示。

图9 模型1和模型2指派矩阵示例Figure 9 Example of assignment matrix of model 1 and model 2

表5 多目标结果对比Table 5 Comparison of multi-target results

在表5中，方案1对应模型1(GRA模型)的结果，方案2对应模型2(本文提出的模型)的结果。对比可知，方案2在空间利用率的目标上提高了20.01%，在时间满意度的目标上提高了24.41%。

因此本文通过量化时空约束，将时空冲突转换为协作最大化问题，在GRA模型(模型1)的基础上实现了多目标指派，提升了协作效果。

为了进一步提升协作效果，针对 α步长对最优解的影响，在上述场景下，以0.001为步长进行了1 000次实验，求解的多目标值分布情况如图10所示。

图10 步长为0.001的时间满意度和空间满意度散点分布Figure 10 The scattered distribution of time satisfaction and space satisfaction with a step size of 0.001

比较图8和图10可知，步长对于构造帕累托最优解的影响不大，因此可以忽略步长对构造最优解的影响。

为了验证上述方法的可行性，选取2019年全国研究生数学建模竞赛F题的真实数据，保留时空数据特征，并设定m从20递增至200，其中迭代步长为20。对每一次m，随机产生100次数据组。经过1 000次随机实验，生成的平均空间利用率随m的变化趋势如图11所示,平均时间利用率随m的变化趋势如图12所示。

图11 GRA模型和本文所提出的模型的空间利用率对比Figure 11 Comparison of space utilization between the GRA model and the model proposed

经过上述大规模计算可得，相比于考虑冲突的GRA模型，本文提出的方法在空间利用率指标上平均提高了6.21%，同时在时间满意度指标上平均提高了9.72%，具体在不同的m条件下的对比情况如图11和图12所示，因此也证明了该方法的有效性。

图12 GRA模型和本文所提出的模型的时间满意度对比Figure 12 Comparison of time satisfaction between the GRA model and the model proposed

实际上，在遇到突发情况发生时(如天气恶劣导致航班延误)，可以在冗余的解决方案中快速选取其他多目标偏好的解决方案。这样也证明了该方法具有一定的鲁棒性。

在1 000次大规模实验中，不同规模m的求解时间变化趋势如图13所示。

图13 大规模随机实验求解时间Figure 13 Time cost of Large-scale experiment

图13表明，本文提出的方法可在秒级时间范围内寻找到多目标平衡解，因此通过大规模随机实验证明了该方法的实用性。

4 结论

本文研究了复杂时空网络下的时空约束和任务分配问题，结合经典的登机口调度场景，使用GRA方法对该类问题进行形式化建模和求解。首先分析时空约束耦合问题，对时空冲突进行分拆、解耦与消解，然后建立多目标平衡指派模型。该模型的求解是基于整数线性规划模型，借助 CPLEX生成解决方案，在秒级时间范围内，满足时空网络对指派快速响应的需求。最后，本文对真实场景的时空数据进行大规模仿真实验，实验结果验证所提出的模型和方法的一般性、有效性和可靠性。在以下方向可以进行下一步的工作：1) 考虑在多对多指派问题中对复杂时空冲突进行消解，围绕多对多群组角色指派进一步研究；2) 在第2节中可以引入图的理论对约束进行量化，挖掘更多协作和冲突关联关系；3) 对于寻找平衡最优解的研究点，可以建立时空网络下的高阶多目标求解，以满足行业更多需求。