復(fù)雜時空網(wǎng)絡(luò)沖突消解群組角色指派研究

劉冬寧，向佳敏，曾思敏，葉自青

(廣東工業(yè)大學(xué) 計算機學(xué)院，廣東 廣州 510006)

信息化進程的持續(xù)推進和跨行業(yè)的融合發(fā)展進一步擴張了對公共資源的緊缺程度，例如在生產(chǎn)管理、交通運輸、航空運營管理等調(diào)度背景[1]下，由于任務(wù)集時間約束和空間約束的緊密耦合[2-4]，形成復(fù)雜的時空網(wǎng)絡(luò)[5-6]，難以合理將任務(wù)分拆、解耦與優(yōu)化，從而影響了各工作任務(wù)的高效協(xié)同與執(zhí)行。因此，急需進行時空沖突消解以優(yōu)化組合，緩解資源的壓力，降低運營成本。

傳統(tǒng)時空網(wǎng)絡(luò)背景[7]下的任務(wù)分配主要考慮特定場景下的約束規(guī)則和目標(biāo)求解，缺乏對時空沖突的系統(tǒng)化方法。雖然目前有許多優(yōu)化方法求解任務(wù)分配問題的逼近最優(yōu)解[8]，但是對求解響應(yīng)時間一般要求較高，故很難快速得到無假設(shè)前提情況下的最優(yōu)解[9]?；诖?，本文擬以時空網(wǎng)絡(luò)的經(jīng)典場景機場登機口調(diào)度為例，采用集中式建模、分布式執(zhí)行方式，對時空網(wǎng)絡(luò)下的任務(wù)沖突消解予以解決。在追求協(xié)作效益最大化的同時，采用整數(shù)規(guī)劃方法加速時空網(wǎng)絡(luò)復(fù)雜求解，同時兼顧用戶客體偏好(乘客滿意度)與任務(wù)執(zhí)行主體的效能(登機口空間利用率)，以求多目標(biāo)平衡。

本文所采取的方法為角色協(xié)同理論(role-based collaboration，RBC)及其E-CARGO模型。該方法與模型可通過群組角色指派(group role assignment，GRA)子模型[10-12]準(zhǔn)確描述多約束和多關(guān)聯(lián)關(guān)系的協(xié)調(diào)問題[13-14]。本文針對復(fù)雜時空網(wǎng)絡(luò)的沖突耦合問題，以沖突和協(xié)作的關(guān)聯(lián)關(guān)系[15]為出發(fā)點，對時空約束進行沖突消解，通過GRA，提出可量化和評估的具有一般化和系統(tǒng)化的方法，力求對時空網(wǎng)絡(luò)的任務(wù)指派進行快速響應(yīng)并提供多樣的合理調(diào)度方案。

1 場景案例

針對復(fù)雜時空網(wǎng)絡(luò)的沖突消解問題，本文選取機場登機口調(diào)度這一經(jīng)典場景進行分析。

某小型機場讓機場調(diào)度人員負責(zé)對有限的登機口資源進行合理調(diào)度，要求進一步提高資源利用率以及中轉(zhuǎn)乘客對航空公司服務(wù)質(zhì)量和水平的滿意度。機場現(xiàn)設(shè)有70個不同區(qū)域位置和功能類型的登機口，假設(shè)調(diào)度人員需要對未來兩天的10架中轉(zhuǎn)飛機進行分配。

首先考慮飛機和登機口的分配問題，計算不同登機口和飛機在機型(寬窄)和功能類型(國內(nèi)外)上的匹配程度(見表1)，然后根據(jù)機場運營規(guī)則，同一登機口的兩架飛機的間隔時間至少大于45 min，飛機從到達到離開機場的期間只能?？恳粋€登機口。接著計算出不同飛機之間的時間沖突(見表2)。對于飛機之間的協(xié)作情況見表3，停靠時間短的飛機盡量被分配到同一個登機口，以減少登機口的使用數(shù)量。

表1 飛機?登機口匹配度評分示例1）Table 1 Aircraft-gate matching score

表2 飛機間的時間沖突情況示例Table 2 Time conflicts between aircraft

表3 飛機間的協(xié)作情況示例Table 3 Time cooperation between aircraft

為了提高中轉(zhuǎn)乘客的滿意度，調(diào)度人員針對中轉(zhuǎn)乘客的換乘流程(如圖1)，統(tǒng)計所有中轉(zhuǎn)乘客的基本換乘時間和其到達—出發(fā)航班的連接時間。在保證乘客換乘成功的前提下，計算出每個中轉(zhuǎn)乘客在等待登機過程中的中轉(zhuǎn)滿意度(見表4)。

圖1 中轉(zhuǎn)流程的時空網(wǎng)絡(luò)結(jié)構(gòu)Figure 1 Spatio-temporal network structure of the transfer process

表4 中轉(zhuǎn)乘客滿意度情況部分示例Table 4 Satisfaction of transit passengers

本文研究的是一個考慮協(xié)作和沖突的任務(wù)指派問題，即一個登機口可以在不同時段停泊多架不同的飛機，但同一個時段只能停泊一架飛機，且應(yīng)盡量便利乘客換乘。因此，需要解決復(fù)雜時空網(wǎng)絡(luò)下的多目標(biāo)指派問題，獲得能平衡優(yōu)化中轉(zhuǎn)乘客時間滿意度和空間資源利用率的解決方案，降低運營成本的同時提升服務(wù)質(zhì)量。

圖1的橫軸表示位置，分布著登機口，縱軸表示時間(單位為min，1 440表示1 d)。例如，飛機F1于某一時刻?？吭诘菣C口T1，隨后中轉(zhuǎn)乘客P1轉(zhuǎn)乘下一趟航班，前往登機口T3。飛機F1按照航班時刻表離開登機口T1。

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

從上述場景來看，生成平衡多目標(biāo)解決方案這一過程遵循E-CARGO模型和RBC的初始步驟[16]，并且這類問題的核心等同于群組角色指派問題，故基于E-CARGO模型對問題形式化建模如下。

角色協(xié)同理論是由Zhu[17]提出的，其通用模型E-CARGO模型以9元組∑::=＜C,O,A,M,R,E,G,S0,H＞抽象并描述協(xié)作系統(tǒng)的組成部分。其中，C表示類；O是對象集合；A是代理集合；M是消息集合，R表示崗位角色集合；E表示環(huán)境；G表示群組的協(xié)作全部團隊；S0為系統(tǒng)最初狀態(tài)；H為所有成員。在這個模型構(gòu)建的環(huán)境中，由群組的代理執(zhí)行角色。通過E-CARGO模型，可進一步分配問題抽象為其子模型群組角色指派(GRA)，其中角色、代理對角色的匹配度、指派方案都可以用向量和矩陣形式化表示。

定義1角色R。角色被定義為r:: = ＜id, ?＞。其中，id是r的標(biāo)識；?是代理扮演r的要求。

在上述場景中，將登機口作為角色，?={“到達航班類型”, “出發(fā)航班類型”, “ 機型”}。

定義2代理A。代理定義為a::= ＜id,?＞。id是a的標(biāo)識；?是與組中所需屬性相對應(yīng)的a值集合。

在上述場景中，代理是指飛機；?={“飛機號”,“到達類型”, “機型”, “出發(fā)類型”, “?？繒r間”}。

定義3屬性集?：屬性集?是一組定義為對象的屬性。例如，p0，p1，···，pn-1，其中，n= |?|。

在上述場景中，?= {“到達航班類型”, “出發(fā)航班類型”, “機型”, “停靠時間”}，如代理a的“到達航班類型”、“出發(fā)航班類型”、“機型”和“?？繒r間”分別命名為a.r、a.d、a.m和a.t。

定義4角色需求向量L表示群組中的每個角色至少需要的代理數(shù)量，

在上述場景中，登機口作為角色，對停靠的飛機數(shù)量無限制條件。

定義5資格評估矩陣Q是一個m×n矩陣。其中，表示代理i對于角色j的評估值。資格評估矩陣Q的具體數(shù)值如圖2所示。其中，0表示執(zhí)行力評分最低；表示執(zhí)行力評分最高。

在上述場景中，需要同時考慮到達航班類型、出發(fā)航班類型和寬窄機型的匹配度，a.r和a.d的取值范圍為{ 0,1}。對于a.m，當(dāng)窄型飛機?？吭趯捫蜋C位時，a.m=0.5，故定義a.m取值范圍為 {0,0.5,1}。飛機對登機口的評估值{0,0.5,1},0≤i＜m,0≤j＜n。

根據(jù)飛機對登機口的匹配情況(見表1)，生成資格評估矩陣Q，其示例數(shù)值如圖2所示。

圖2 資格評估矩陣Q 示例Figure 2 Example of qualification matrix Q

在群組角色任務(wù)分配過程中，代理之間存在沖突關(guān)聯(lián)，會影響協(xié)同和合作。為了考慮避免沖突，引入代理沖突矩陣。

定義6代理沖突矩陣AC是一個m×m對稱矩陣。其中，表 示代理i1和 代理i2在執(zhí)行同一個角色時存在沖突，若為0值則反之。

在上述場景中，飛機作為代理，根據(jù)飛機之間存在的沖突情況(見表2)可以生成代理沖突矩陣，其示例數(shù)值如圖3(a)所示。

定義7分配矩陣T是一個m×n矩 陣。其中，表示代理i被指派執(zhí)行角色j。

根據(jù)上述場景描述，飛機分配給登機口的方案即任務(wù)指派的分配矩陣T，其示例數(shù)值如圖3(b)所示。

圖3 代理沖突矩陣AC 和分配矩陣T 示例Figure 3 Example of agent conflict matrix AC and assignment matrix T

定義8群組執(zhí)行力δ 指派成功后，所有代理的執(zhí)行力評分總和為

定義9根據(jù)上述定義Q和AC，建立群組角色指派模型來找到分配矩陣T。該模型考慮代理之間的沖突，其中，目標(biāo)函數(shù)及其約束如下。

約束條件(1)表示角色分配矩陣T的值只能取0或1，分別表示分配和不分配；約束條件(2)表示分配矩陣T的每一行1的個數(shù)總和等于1，即一個代理只能分配到一個角色，保證所有代理都能分配到角色；約束條件(3)表示代理i1和 代理i2存在沖突時，不能同時分配給某一個角色j。

上述模型提供了一個追求群組執(zhí)行力最大化的方案。為了考慮復(fù)雜時空網(wǎng)絡(luò)的多維目標(biāo)，對時間成本和空間成本作如下定義。

定義10空間利用率U為一正小數(shù)，表示所有資源的平均占用率。其歸一化處理為

其中，max{|U|}和 min{|U|}分 別表示U的絕對值的最大值和最小值。

在上述場景中，登機口是有限的空間資源，不考慮維修、清潔等其他情況時，登機口一般處于使用或者空閑狀態(tài)。定義登機口的利用率為單位調(diào)度時間內(nèi)的總使用時間。

定義11時間滿意度S為一正小數(shù)，表示指派過程中客體對其時間屬性的滿意度評估。其歸一化處理為

其中，np表 示中轉(zhuǎn)乘客的總數(shù)量； max{|S|}和min{|S|}分 別表示S的絕對值的最大值和最小值。

在上述場景中，考慮中轉(zhuǎn)乘客的換乘滿意度，對時間滿意度的函數(shù)表達式為

其中，t表示中轉(zhuǎn)乘客的等待時間；t0表示最小等待時間；[ts,ts+?t]是最佳等待時間的區(qū)間，即對應(yīng)的時間滿意度S(t) = 1，表示達到最大時間滿意度；tm表示最大等待時間。時間滿意度S(t)的分段函數(shù)分布情況如圖4所示。

圖4 時間滿意度函數(shù)圖Figure 4 Graph of Time satisfaction function

圖4說明，在最佳等待時間范圍內(nèi)，中轉(zhuǎn)乘客的滿意度最高；當(dāng)超過最佳等待時間段后，乘客對中轉(zhuǎn)航班的滿意度會逐漸降低。

為了解決時空約束耦合、沖突消解的問題，本文提出沖突量化和評估策略，生成新的協(xié)作矩陣。

定義12不同角色下的不同代理協(xié)作影響矩陣AD代表被分配到不同角色下的不同代理合作產(chǎn)生的影響的評估，是一個由 (m×n)×(m×n)矩陣即(A×R)×(A×R)組 合的nd×d矩陣，nd為 矩陣AD的行數(shù)，d=5為 矩陣AD的 列數(shù)。表示代理i1分 配給角色j1，且代理i2分 配給角色j2時的影響值( 0≤i1,i2＜m, 0≤j1,j2＜n,i1≠i2,j1≠j2)。

在上述場景中，針對時間滿意度這一目標(biāo)，根據(jù)場景要求，選取t0=45，ts=120，?t=60，tm=360，單位為min，構(gòu)造時間滿意度函數(shù)S(t)，生成中轉(zhuǎn)乘客時間滿意度(如表4)，作為不同飛機分配給各個登機口的協(xié)作值，構(gòu)成協(xié)作矩陣AD，其示例如圖5(a)。同時也考慮另一個目標(biāo)，引入不同的代理承擔(dān)同個角色情況下的協(xié)作影響，以提高團隊執(zhí)行力。

圖5 不同角色下和相同角色下的代理協(xié)作矩陣Figure 5 Agents collaboration matrix of different roles and role

定義13相同角色下的不同代理協(xié)作影響矩陣AS代表被分配到同個角色的不同代理合作產(chǎn)生的影響的評估，是一個由 (m×n)×(m×n)矩 陣即(A×R)×(A×R) 組 合 的ns×d矩 陣，ns為 矩 陣AS的 行 數(shù)，d=5為 矩陣AS的 列數(shù)。表示代理i1分 配給角色j，且代理i2分 配給角色j時的影響值，其中，0 ≤i1,i2＜m, 0≤j＜n,i1≠i2。

在上述場景中，針對空間利用率這一目標(biāo)，根據(jù)第1節(jié)中提到的飛機間的協(xié)作情況，計算不同飛機對登機口的占用時長，然后對數(shù)據(jù)進行規(guī)范化處理，構(gòu)成協(xié)作矩陣AS，其示例如圖5(b)。

在定義12和定義13中進行了多目標(biāo)的約束量化。為了考慮主體的多目標(biāo)偏好，引入多目標(biāo)的權(quán)重系數(shù)。

定義14權(quán)重系數(shù) α 是一個正小數(shù)，其取值范圍為[0,1]，代表影響矩陣AD基數(shù)的系數(shù)。同樣，權(quán)重系數(shù) β也是一個正小數(shù)，表示影響矩陣AS基數(shù)的系數(shù)，且α +β=1。

定義15影響執(zhí)行效果矩陣E表示代理分配給角色后，對所執(zhí)行效果產(chǎn)生的影響，是一個ne×d矩陣。其中，ne為 矩陣E的 行數(shù)；d=5為 矩陣E的列數(shù)，且E[k,4]∈[0,1],(0≤k＜ne)，表示代理i1分配給角色j1，且代理i2分 配給角色j2時 的影響值。E[k,4]的公式為

通過改變 α，可以生成具有不同數(shù)量的二維協(xié)作矩陣，并在下文指派模型中將矩陣轉(zhuǎn)為向量，以解耦沖突，構(gòu)成新的約束。

定義16分配向量Tne是 一個ne維的向量。其中，Tne[k]∈{0,1},0≤k＜ne。Tne[k]=1表 示代理i1被指派執(zhí)行角色j1的 同時，代理i2被指派執(zhí)行角色j2(0≤i1,i2＜m, 0≤j1,j2＜n)。

定義17根據(jù)上述定義，考慮到影響執(zhí)行效果E的群組執(zhí)行力 δE以及約束函數(shù)目標(biāo)函數(shù)如下。

除了式(1)、(2)和(3)，還需要滿足以下約束。

約束條件(4)表示分配向量Tne的值只能取0或1，分別表示分配和不分配；約束條件(5)和(6)分別表示當(dāng)代理E[k,0]分 配給角色E[k,1], 且代理E[k,2]分配給角色E[k,3]時，分配向量才為1，若二者有一個分配失敗，則分配向量值為0。

通過上述形式化，如果將Q和T矩陣轉(zhuǎn)換為向量，則可以通過IBM ILOG CPLEX優(yōu)化包處理該線性整數(shù)規(guī)劃問題。

3 CPLEX 解決方案及實驗分析

3.1 解決方案及流程圖

基于上述模型和定義，為了獲得多目標(biāo)平衡指派方案，需要找出最優(yōu)解的權(quán)重系數(shù)α。

設(shè)定 α從0.00遞增至1.00，步長為0.01，每次改變α，通過CPLEX求解器生成新的分配矩陣T，計算出歸一化后的空間利用率和時間滿意度，具體算法流程圖如圖6所示。

圖6表明，本文提出的解決方案，其關(guān)鍵在于最優(yōu)解的選取。通過對權(quán)重系數(shù) α進行多次迭代，生成多目標(biāo)解空間后，采用擂臺賽法則構(gòu)造多目標(biāo)Pareto最優(yōu)解集[18]，根據(jù)客體偏好確定最優(yōu)解，獲得該解決方案的權(quán)重系數(shù)α。

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

對于尋找帕累托解，例如，假設(shè)多目標(biāo)最大值問題的解空間在坐標(biāo)軸上的集合為{X1=(0.6,1)，X2=(0.7,0.93)，X3=(0.3,0.93)}。由于X2在橫坐標(biāo)值上大于X3，故排除X3，再考慮X1。由于X1的縱坐標(biāo)值大于X2，但是X2的橫坐標(biāo)值大于X1，故X1和X2均為帕累托最優(yōu)解。

3.2 實驗設(shè)置及結(jié)果分析

為了驗證上述方法的可行性，采用型號為Inter(R)Core(TM) i5-8400和2.81GHz頻率的CPU，以及運行內(nèi)存為16GB的計算機，運行在Windows 10 Education版本的操作系統(tǒng)，使用IBM公司2019年發(fā)布的軟件Eclipse作為集成開發(fā)環(huán)境(IDE)，并選用1.8.0版本的Java語言開發(fā)工具包(JDK)，進行相關(guān)實驗和數(shù)據(jù)分析。

在上述場景中，登機口作為角色，飛機作為代理，m=10，權(quán)重系數(shù) α從0.00遞增至1.00，步長為0.01。進行100次求解，計算得到空間利用率和時間滿意度隨著α 的變化趨勢如圖7所示。

圖7 時間滿意度和空間利用率隨權(quán)重的變化趨勢Figure 7 Graph of change trend of time satisfaction and space utilization with weight coefficient

圖7表明，時間滿意度和空間利用率隨權(quán)重系數(shù) α的增大成不規(guī)律的增減變化，這說明本次實驗存在不唯一的最優(yōu)解。

為了在多目標(biāo)解空間中找到最優(yōu)解，對上述100個解的空間利用率和時間滿意度分別進行歸一化，以時間滿意度作為橫軸，以空間利用率作為縱軸，生成多目標(biāo)的散點分布如圖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)，故構(gòu)造帕累托最優(yōu)解，得到解空間集合為{(0.721,1),(1,0.375)}，根據(jù)用戶對多維目標(biāo)的偏好，選取權(quán)重系數(shù)α =0.42，完成此次沖突消解和多目標(biāo)平衡指派。

本文在GRA模型(簡稱模型1)基礎(chǔ)上引入沖突消解的概念，提出的多目標(biāo)指派模型(簡稱模型2)的指派結(jié)果如圖9，數(shù)據(jù)分析如表5所示。

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

表5 多目標(biāo)結(jié)果對比Table 5 Comparison of multi-target results

在表5中，方案1對應(yīng)模型1(GRA模型)的結(jié)果，方案2對應(yīng)模型2(本文提出的模型)的結(jié)果。對比可知，方案2在空間利用率的目標(biāo)上提高了20.01%，在時間滿意度的目標(biāo)上提高了24.41%。

因此本文通過量化時空約束，將時空沖突轉(zhuǎn)換為協(xié)作最大化問題，在GRA模型(模型1)的基礎(chǔ)上實現(xiàn)了多目標(biāo)指派，提升了協(xié)作效果。

為了進一步提升協(xié)作效果，針對 α步長對最優(yōu)解的影響，在上述場景下，以0.001為步長進行了1 000次實驗，求解的多目標(biāo)值分布情況如圖10所示。

圖10 步長為0.001的時間滿意度和空間滿意度散點分布Figure 10 The scattered distribution of time satisfaction and space satisfaction with a step size of 0.001

比較圖8和圖10可知，步長對于構(gòu)造帕累托最優(yōu)解的影響不大，因此可以忽略步長對構(gòu)造最優(yōu)解的影響。

為了驗證上述方法的可行性，選取2019年全國研究生數(shù)學(xué)建模競賽F題的真實數(shù)據(jù)，保留時空數(shù)據(jù)特征，并設(shè)定m從20遞增至200，其中迭代步長為20。對每一次m，隨機產(chǎn)生100次數(shù)據(jù)組。經(jīng)過1 000次隨機實驗，生成的平均空間利用率隨m的變化趨勢如圖11所示,平均時間利用率隨m的變化趨勢如圖12所示。

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

經(jīng)過上述大規(guī)模計算可得，相比于考慮沖突的GRA模型，本文提出的方法在空間利用率指標(biāo)上平均提高了6.21%，同時在時間滿意度指標(biāo)上平均提高了9.72%，具體在不同的m條件下的對比情況如圖11和圖12所示，因此也證明了該方法的有效性。

圖12 GRA模型和本文所提出的模型的時間滿意度對比Figure 12 Comparison of time satisfaction between the GRA model and the model proposed

實際上，在遇到突發(fā)情況發(fā)生時(如天氣惡劣導(dǎo)致航班延誤)，可以在冗余的解決方案中快速選取其他多目標(biāo)偏好的解決方案。這樣也證明了該方法具有一定的魯棒性。

在1 000次大規(guī)模實驗中，不同規(guī)模m的求解時間變化趨勢如圖13所示。

圖13 大規(guī)模隨機實驗求解時間Figure 13 Time cost of Large-scale experiment

圖13表明，本文提出的方法可在秒級時間范圍內(nèi)尋找到多目標(biāo)平衡解，因此通過大規(guī)模隨機實驗證明了該方法的實用性。

4 結(jié)論

本文研究了復(fù)雜時空網(wǎng)絡(luò)下的時空約束和任務(wù)分配問題，結(jié)合經(jīng)典的登機口調(diào)度場景，使用GRA方法對該類問題進行形式化建模和求解。首先分析時空約束耦合問題，對時空沖突進行分拆、解耦與消解，然后建立多目標(biāo)平衡指派模型。該模型的求解是基于整數(shù)線性規(guī)劃模型，借助 CPLEX生成解決方案，在秒級時間范圍內(nèi)，滿足時空網(wǎng)絡(luò)對指派快速響應(yīng)的需求。最后，本文對真實場景的時空數(shù)據(jù)進行大規(guī)模仿真實驗，實驗結(jié)果驗證所提出的模型和方法的一般性、有效性和可靠性。在以下方向可以進行下一步的工作：1) 考慮在多對多指派問題中對復(fù)雜時空沖突進行消解，圍繞多對多群組角色指派進一步研究；2) 在第2節(jié)中可以引入圖的理論對約束進行量化，挖掘更多協(xié)作和沖突關(guān)聯(lián)關(guān)系；3) 對于尋找平衡最優(yōu)解的研究點，可以建立時空網(wǎng)絡(luò)下的高階多目標(biāo)求解，以滿足行業(yè)更多需求。