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

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

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

傳統(tǒng)時(shí)空網(wǎng)絡(luò)背景[7]下的任務(wù)分配主要考慮特定場(chǎng)景下的約束規(guī)則和目標(biāo)求解，缺乏對(duì)時(shí)空沖突的系統(tǒng)化方法。雖然目前有許多優(yōu)化方法求解任務(wù)分配問題的逼近最優(yōu)解[8]，但是對(duì)求解響應(yīng)時(shí)間一般要求較高，故很難快速得到無假設(shè)前提情況下的最優(yōu)解[9]?；诖?，本文擬以時(shí)空網(wǎng)絡(luò)的經(jīng)典場(chǎng)景機(jī)場(chǎng)登機(jī)口調(diào)度為例，采用集中式建模、分布式執(zhí)行方式，對(duì)時(shí)空網(wǎng)絡(luò)下的任務(wù)沖突消解予以解決。在追求協(xié)作效益最大化的同時(shí)，采用整數(shù)規(guī)劃方法加速時(shí)空網(wǎng)絡(luò)復(fù)雜求解，同時(shí)兼顧用戶客體偏好(乘客滿意度)與任務(wù)執(zhí)行主體的效能(登機(jī)口空間利用率)，以求多目標(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]。本文針對(duì)復(fù)雜時(shí)空網(wǎng)絡(luò)的沖突耦合問題，以沖突和協(xié)作的關(guān)聯(lián)關(guān)系[15]為出發(fā)點(diǎn)，對(duì)時(shí)空約束進(jìn)行沖突消解，通過GRA，提出可量化和評(píng)估的具有一般化和系統(tǒng)化的方法，力求對(duì)時(shí)空網(wǎng)絡(luò)的任務(wù)指派進(jìn)行快速響應(yīng)并提供多樣的合理調(diào)度方案。

1 場(chǎng)景案例

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

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

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

表1 飛機(jī)?登機(jī)口匹配度評(píng)分示例1）Table 1 Aircraft-gate matching score

表2 飛機(jī)間的時(shí)間沖突情況示例Table 2 Time conflicts between aircraft

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

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

圖1 中轉(zhuǎn)流程的時(shí)空網(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

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

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

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

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

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

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

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

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

在上述場(chǎng)景中，代理是指飛機(jī)；?={“飛機(jī)號(hào)”,“到達(dá)類型”, “機(jī)型”, “出發(fā)類型”, “?？繒r(shí)間”}。

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

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

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

在上述場(chǎng)景中，登機(jī)口作為角色，對(duì)?？康娘w機(jī)數(shù)量無限制條件。

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

在上述場(chǎng)景中，需要同時(shí)考慮到達(dá)航班類型、出發(fā)航班類型和寬窄機(jī)型的匹配度，a.r和a.d的取值范圍為{ 0,1}。對(duì)于a.m，當(dāng)窄型飛機(jī)停靠在寬型機(jī)位時(shí)，a.m=0.5，故定義a.m取值范圍為 {0,0.5,1}。飛機(jī)對(duì)登機(jī)口的評(píng)估值{0,0.5,1},0≤i＜m,0≤j＜n。

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

圖2 資格評(píng)估矩陣Q 示例Figure 2 Example of qualification matrix Q

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

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

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

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

根據(jù)上述場(chǎng)景描述，飛機(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í)行力評(píng)分總和為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義16分配向量Tne是 一個(gè)ne維的向量。其中，Tne[k]∈{0,1},0≤k＜ne。Tne[k]=1表 示代理i1被指派執(zhí)行角色j1的 同時(shí)，代理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]時(shí)，分配向量才為1，若二者有一個(gè)分配失敗，則分配向量值為0。

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

3 CPLEX 解決方案及實(shí)驗(yàn)分析

3.1 解決方案及流程圖

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

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

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

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

對(duì)于尋找帕累托解，例如，假設(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í)驗(yàn)設(shè)置及結(jié)果分析

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

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

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

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

為了在多目標(biāo)解空間中找到最優(yōu)解，對(duì)上述100個(gè)解的空間利用率和時(shí)間滿意度分別進(jìn)行歸一化，以時(shí)間滿意度作為橫軸，以空間利用率作為縱軸，生成多目標(biāo)的散點(diǎn)分布如圖8所示。

圖8 步長(zhǎng)為0.01的時(shí)間滿意度和空間滿意度散點(diǎn)分布Figure 8 The scattered distribution of time satisfaction and space satisfaction with a step size of 0.01

圖8表明，此次解空間不存在理想點(diǎn)(1,1)，故構(gòu)造帕累托最優(yōu)解，得到解空間集合為{(0.721,1),(1,0.375)}，根據(jù)用戶對(duì)多維目標(biāo)的偏好，選取權(quán)重系數(shù)α =0.42，完成此次沖突消解和多目標(biāo)平衡指派。

本文在GRA模型(簡(jiǎn)稱模型1)基礎(chǔ)上引入沖突消解的概念，提出的多目標(biāo)指派模型(簡(jiǎn)稱模型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é)果對(duì)比Table 5 Comparison of multi-target results

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

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

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

圖10 步長(zhǎng)為0.001的時(shí)間滿意度和空間滿意度散點(diǎn)分布Figure 10 The scattered distribution of time satisfaction and space satisfaction with a step size of 0.001

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

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

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

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

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

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

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

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

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

4 結(jié)論

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