基于電子商務競標結構的分布式作戰資源調度

顏 驥, 劉丙杰, 陳建華

(海軍潛艇學院戰略導彈與水中兵器系, 山東 青島 266199)

0 引 言

技術的進步使得現代作戰資源具備對敵攻擊、監視與偵察、搜索、救援以及災難應對等多領域作戰能力,如何充分發揮資源的能力是指揮員面臨的巨大挑戰。指揮員需要在有限的時間內,在任務時間、距離、優先級及資源能力等因素的約束下,將作戰資源分配給不同的作戰任務,并確定基于連續時間的資源調度計劃,以最大化資源整體效用。任務分配與調度問題可視為約束優化問題[1],視約束條件和優化目標不同,問題存在多種變體,一般都將任務集映射為非循環圖上的節點集,通過尋找資源的最優路徑/調度求解問題。

本文主要研究上述問題的變體之一:帶時間窗約束的團隊合作定向問題[2](cooperative team orienteering problem with time windows, CTOPTW)。

定向問題(orienteering problem, OP)描述為:給定n個節點,每個節點i有一個非零分數s,節點i和j之間的弧有一關聯成本cij,用節點間的旅行時間表示,每個節點最多被訪問一次。OP的目標是在不違反最大成本約束T(旅行時間)的情況下,最大化路徑得分,該路徑由從節點1開始到節點n結束的節點子集組成。

團隊OP(team orienteering problem, TOP)通過為多個定向選手創建網絡的多個回路來擴展OP,以最大化團隊得分。

帶時間窗約束的[3-4]TOP(TOP with time windows, TOPTW),要求各選手在時間窗內訪問節點,在時間窗之前或之后到達都不算節點被訪問。

在TOPTW中,各選手遍歷的節點并無交集,CTOPTW則要求多個選手在時間窗內同步訪問節點,因而又稱帶時間窗與同步訪問約束的路徑規劃問題[5](vehicle routing problem with time windows and synchronized visits, VRPTWSyn)。

CTOPTW模型目前廣泛應用于家庭健康護理[6-7]、無人機任務分配與調度[1,8]以及應急物流管理[9-11]。現代戰爭中,大部分作戰任務需要多個資源合作完成,如對潛艇搜索、攻擊任務中,需要艦載直升機、水面艦船、潛艇甚至太空偵察衛星在指定時間窗內進行合作[12-13]。現代戰爭作戰任務地理空間分布廣,作戰資源分屬不同作戰集群,前述問題求解方法并不適應現代作戰任務分配與調度的需要。

針對作戰任務CTOPTW特點,本文提出一種基于市場機制的分布式資源分配架構,將任務規劃者視為消費者,將資源管理者視為供應商,供應商通過對消費者任務的去中心化競標來協調跨多域的資源,使資源服務于需求最迫切、成本最低的客戶。基于市場機制資源分配架構,提出規劃時間可接受的資源聯合調度(resource united scheduling, RUS)算法。

1 電子商務競標結構

1.1 相關概念與假設

基于電信網絡,消費者通過虛擬地指定商品名和條件,就可以從一系列供應商中選擇最便宜的商品,這就是電子商務。資源獲取渠道的豐富程度和速度,是電子商務的主要特征。

電子商務通過3個主要組成部分定義:通信系統、數據管理系統和安全機制[14]。假設通信及數據管理系統都是可靠的,本文重點介紹供應商與消費者之間的分布式資源分配架構,定義消費者和供應商之間的交互協議,以及基于用戶安全考量,限定網絡中的通信內容。

不同于經典市場特征,本文基于如下假設:① 消費者和供應商不用金錢交換服務,消費者通過賦予價值來表達其對某項任務的重視程度。② 消費者是誠實的行為人,不會為騙取供應商的資源而賦予低優先級的任務高價值。③ 供應商在其調度計劃可行的情況下總是愿意為任務請求提供服務。當部分供應商忙于其他供應商時,會通過其提供的資源成本來表示這一狀態。

1.2 消費者-供應商關系

本文關注供應商如何更有效地將有限的資源分配給消費者。兩者間的互動由消費者開始,處于不同位置,需要特定資源的任務由多個消費者創建,位于不同地點的多個供應商負責提供并調度資源。任務由以下參數定義:

價值:指定的數值,位于區間[1,100]內,以量化任務的重要性。

位置:任務的二維地理坐標。

最小持續時間:完成任務所需的最少時間。

時間窗:必須為任務提供服務的開始和結束時間。如果資源在時間窗開始前到達,必須等待至時間窗開始才能服務任務。如果資源在任務窗口結束前未提供最小持續時間的服務,任務視為未完成。

資源:完成一項任務可能需要一種或多種資源。這些資源由類型定義,只有同類型的資源才能滿足任務對該類資源的請求。

元素:每種類型的單個資源。

由上述定義可知,要完成一項任務,其請求的所有資源在該任務的時間窗內都必須處于相同的服務位置,且為任務提供服務的重疊時間不小于任務的最小持續時間。

消費者與供應商的關系決定了資源的調度方式,兩者間的關系可概括為如下3種。

1.2.1 一個消費者對應一個供應商

一個消費者分配給一個供應商,這種煙囪式的關系今天仍然很普遍,因為其能簡化調度,并且對計劃細節保密。消費者的資源來源只有一個,所以任務的可行性很容易通過詢問供應商是否擁有所需的資源,或是否正服務于另一任務來確定。由于資源只服務于一個客戶,因此只有該消費者知道供應商的計劃。

這種關系的最大缺點是消費者完全依賴于供應商。當任務需要的資源供應商無法提供,且沒有其他選擇時,任務便無法完成。并且,這種關系也會被對手觀察到而變得易受攻擊。即便通信鏈路上沒有發布任何信息,對手也可以通過消費者-供應商的歷史關系或觀察供應商資源的活動來預測作戰行動,甚至可以移除供應商來徹底削弱消費者。

1.2.2 一個消費者對應多個供應商

眾多供應商能有力改進任務規劃的效率。更多的供應商帶來更多的資源可用性,增加了消費者獲得所需資源的概率,該關系的另一優勢是不可預測性。由于資源的豐富性,消費者可以改變對供應商的選擇,來掩蓋針對對手的行動意圖,并通過冗余消除單供應商的不足。

但網絡中節點越多,系統信息泄露的潛在風險就越高,對作戰安全威脅也越大。因此,本文中,供應商不與彼此或消費者共享調度計劃。供應商只通過帶有以下信息的“投標”來回應消費者:

成本:資源到達任務位置的花費,以旅行時間度量。

時間窗:資源到達和離開任務位置的時間。

資源:分配給任務的資源類型和數量。

1.2.3 多個消費者對多個供應商

理論上,多個供應商共同服務一個消費者是理想的狀態,但在現實世界中,從網絡上獲得眾多供應商的靈活性需要多個消費者相互競爭供應商的資源來實現。

本文中,消費者并不與其他消費者合作以實現全局最大任務完成率。消費者只關心自己任務的完成情況,在任務完成或競標停止前,消費者將持續向所有供應商發送資源請求。

1.3 電子商務競標結構

本文中,消費者負責陳述一項任務需要的資源類型、數量以及任務的時間窗,對資源的調度則由供應商負責。消費者就所需資源通過多輪競標與供應商交互。每一輪競標包括3次握手:① 資源請求由消費者連同任務的關鍵信息發送給供應商;② 供應商向消費者發送元素投標,表示資源可用性;③ 消費者向供應商發送投標確認,以接受或拒絕元素投標。資源競標輪中的信息流如圖1所示。

圖1 一輪競標中的信息流Fig.1 Information flow in one bidding round

發送資源請求后,消費者將收到來自供應商的資源元素投標,每項任務有3種投標結果。

(1) 不完全實現

任務請求的至少一個資源,沒有收到投標。

(2) 完整的實現

從一個或多個供應商那里,獲得完成一項任務所需的所有資源,且資源重疊服務時間不小于最小持續時間。

(3) 非同步的實現

一項任務從多個供應商收到所有資源請求的投標,但收到的投標有不一致的服務時間。

這3種不同的投標結果需要一個協議來處理,使所有任務在多輪投標結束前達到完整實現的結果。對此,根據不同的投標結果,設計消費者決策過程如圖2所示。

圖2 消費者決策過程Fig.2 Consumer decision process

1.3.1 不完全實現

對不完全實現情況,消費者重新廣播原始任務請求,希望上輪繁忙的供應商在下一輪競標中,其調度表中能產生新的空閑時間。因任務投標可能在上輪競標中被拒絕,供應商在競標輪中可以不斷調整調度計劃,如圖3所示。

圖3 供應商計劃決策周期Fig.3 Supplier schedule decision cycle

1.3.2 完整的實現

在完整實現的情況下,消費者將以最低的成本選擇需要的競標組合。消費者應通知未被選擇的元素投標供應商,將任務從該元素的調度表中刪除。如果分配的資源突然不可用,消費者可以在下一輪招標中重新提交資源請求。

在消費者決策過程中需注意的是,圖2中,“選擇的投標來自同一供應商”,當單個供應商為一項任務提供所有資源時,在任務時間窗范圍內,供應商可以調整任務的開始和結束時間,即使消費者接受了一個(或多個)對特定開始時間的投標,供應商也可以根據其認為合適的情況更改開始時間。如果先前商定的開始時間過于嚴格,供應商可能會放棄承諾,以支持新的更有價值的任務請求。

當消費者從多個供應商中選擇資源時,有必要進行“保護時間窗”設置。因原始資源請求指定了任務時間窗,為供應商提供的資源給出了一個可能到達和離開時間的范圍。一旦找到一組完全完成任務的投標,消費者就不希望這些資源的時隙被供應商改動,從而導致任務不同步。為防止出現此類情況,消費者將任務的時間窗口確認為所有元素競標重疊的開始和結束時間。供應商通過消費者發送的招標確認信息,對更改了的任務時間窗做出相應更新。

1.3.3 非同步的實現

非同步的實現給消費者帶來的挑戰最大。由于供應商之間不進行溝通,需利用消費者重新廣播的資源請求信息來協調供應商之間的調度計劃。

消費者在決策過程中試圖保持任務的可行性與資源同步的平衡。任務的時間窗口范圍越寬,供應商將任務納入調度計劃中的可選項就越多,任務資源請求得到響應的可能性就越大。對供應商而言,擁有眾多選擇的缺點是,元素投標與其他調度計劃未知的供應商保持同步的概率降低了。

為推動不同供應商的同步,消費者可采取“更新時間窗”策略。具體方法為:將任務原時間窗開始時間推遲至所有元素投標的第二最早到達時間。由于后續供應商數學模型將所有任務推進至盡可能早的時間進行服務,這意味著當收到一個投標時,消費者知道在不改變計劃的情況下,資源的開始服務時間不能再向前移動,但可以向后移動。并且,在資源路徑的后續部分仍有空閑時間的情況下,整個調度計劃仍是可行的。

將開始窗口更新到投標的第二最早到達時間,對于同步供應商而不使調度計劃成為次優解至關重要。從圖4可以看出,即便在新時間窗內,所有4個元素標價的到達時間都不是同步的。供應商可能會將標價e1和e2的到達時間后推至與e3的到達時間相同,但e4的到達時間可能不會提前。在這種情況下,任務將再次進入“非同步的實現”狀態,時間窗將縮短到e4的到達時間,然后任務預計將在所有元素投標中達到同步。

圖4 更新時間窗口Fig.4 Update time window

任務的開始時間不會立即更新為投標最遲的到達時間,即e4的到達時間,因為這可能會將任務的時間窗口收緊到一個不可行的時間范圍。假設一個供應商提供投標e1和e2,其有一項非常有價值的任務,在任務i之后服務,但不能移動該任務。如果時間窗口大幅收緊,那么任務i將失去兩個元素的投標。通過多輪投標逐步更新時間窗口,接下來的幾輪可以讓e4的供應商將其到達時間提前,或者新的供應商能夠代替e4的供應商為任務i提供服務。

如果“更新時間窗”的過程導致一個供應商放棄對該任務的元素投標,而沒有其他供應商填補,那么該任務將成為一個不完全實現的任務,消費者可沿用任務的原始時間窗重新提交資源請求。

2 供應商、消費者調度問題模型

2.1 供應商調度問題模型

文獻[15-16]建立了單個供應商調度問題數學模型。首先定義集合、決策變量和輸入變量的符號,然后介紹目標函數和約束條件,最后引入該模型的變體,以提高特定任務的元素競標的同步性。

2.1.1 集合定義

T:所有任務集合。

U:所有資源集合。

U(e):所有元素e集合。

P:路徑中所有位置集合。

集合P是資源執行的所有任務在路徑上的位置集合,位置表示任務在路徑中的順序。如一項任務處于位置3,那么該任務是該資源將執行的第3個任務。

2.1.2 決策變量

accommodatei,u,p:二元決策變量,如果資源u在位置p上容納了任務i,則為1,否則為0。

traveli,j,u:二元決策變量,如果資源u經任務i與任務j間的路徑達到任務j,則為1,否則為0。

arrivei,u:連續決策變量,指定資源u到達任務i的時間。

departi,u:連續決策變量,指定資源u離開i的時間。

決策變量accommodate表示供應商暫時將資源分配給任務,任務是否執行最終由消費者決定。

2.1.3 輸入變量

oi:任務i時間窗開始時間。

ci:任務i時間窗結束時間。

ai:任務i的最小持續時間。

horizon:規劃周期。

ti,j,u:資源u從任務i移動到任務j的時間。

travelToBaseTimei,u:資源u從任務i移動到u的供應商位置的時間。

resourceCounti,e:任務i請求的元素e的個數。

valuei:任務i的價值。

2.1.4 目標函數

目標是使完成的任務總價值最大,每項任務有不同數量的資源請求,一些任務只請求一個資源,而另一些任務請求多個資源。只有獲得了請求的全部資源,任務才能實現價值,因此,需用任務的價值除以其請求的資源數量。

由于供應商試圖將盡可能多的任務打包到調度表中以最大化目標函數,資源的時間窗通常只持續最小持續時間,即便在該任務和下一任務之間有空閑時間,對于需要多個資源協同的任務,不同供應商提供的服務時間可能位于任務時間窗的不同位置,使任務依然得不到同步服務,如圖4所示。為解決該問題,將最大時間窗口(maximum time window, MTW)概念添加到供應商調度模型中,以增加元素服務時間重疊概率。MTW目標函數為

目標函數通過最大化資源服務任務的離開時間和到達時間之差來最大化投標的時間窗口。參數wtimeWindow是拉伸時間窗的權重,用于調整容納任務的數量與最大化任務的時間窗之間的關系。

2.1.5 約束條件

(1) 確保任務i不被其未請求的資源u容納。

accommodatei,u,p=0, ?i∈T;e∈i;u?U(e);p∈P

(1)

(2) 每項任務i,每個資源只能為其分配一個位置。

accommodatei,u,p≤1, ?i∈T;u∈U

(2)

(3) 每個位置p,每個資源只能分配一項任務。

accommodatei,u,p≤1, ?u∈U;p∈P

(3)

(4) 確保每項任務i獲得的元素e的個數不超過其請求數。

(4)

(5) 確保任務在資源路徑上的位置是連續的。

?u∈U;p∈P-1

(5)

(6) 在先后執行的兩項任務之間強制存在一條旅行路徑。

accommodatei,u,p+1+accommodatej,u,p-2traveli,j,u≤1,
?i∈T;j∈T;?u∈U;p∈P-1

(6)

(7) 如果容納任務i,資源必須在任務時間窗開始后到達。

(7)

(8) 如果容納任務i,資源必須在任務時間窗結束前離開。

?i∈T;u∈U

(8)

(9) 資源在服務任務最小持續時間之后才能離開。

(9)

(10) 資源從供應商基地位置處開始調度。

travelToBaseTimei,u≤arrivei,u, ?i∈T;u∈U

(10)

(11) 資源在供應商基地位置處結束調度。

departi,u≤horizon-travelToBaseTimei,u, ?i∈T;u∈U

(11)

(12) 確保任務之間有足夠的旅行時間。

(12)

(13) 將未被容納的任務元素的時間窗強制為零。

?i∈T;u∈U

(13)

MTW模型不能保證服務于同一任務的多個資源將同步到同一到達時間。為確保多個資源的同步,引入兩個全局決策變量及3個約束條件,全局決策變量如下。

Arrivei:連續決策變量,指定請求的所有資源到達任務i的時間。

Departi:連續決策變量,指定請求的所有資源離開任務i的時間。

以上全局變量保證所有服務任務i的資源在至少最小持續時間的重疊時間窗內服務任務i。資源可以在同步服務任務之前到達,也可以在同步服務任務之后停留,同步約束如下。

(14) 全局變量Arrivei是服務任務i的資源的最遲到達時間。

?i∈T;u∈U

(14)

(15) 全局變量Departi是服務任務i的資源的最早離開時間。

?i∈T;u∈U

(15)

(16) 資源在服務任務最小持續時間后才能離開。

Arrivei+ai≤Departi, ?i∈T

(16)

有約束式(16),約束式(9)變得冗余,可以從模型中移除。

2.2 消費者調度模型

消費者調度模型用于單個消費者為任務尋找最優的元素投標。

2.2.1 集合定義

T:所有任務集合。

B:所有元素投標集合。

B(i,e):對任務i投標的元素e的投標集。

2.2.2 決策變量

bidSelectb:二元決策變量,消費者選擇元素投標b,則為1,否則為0。

performi:二元決策變量,消費者選擇執行任務i,則為1,否則為0。

Arrivei:連續決策變量,指定投標開始任務i的時間。

Departi:連續決策變量,指定投標結束任務i的時間。

2.2.3 輸入變量

earlyb:投標b開始服務任務的最早時間。

lateb:投標b結束服務任務的最遲時間。

costb:投標b的成本。

horizon:規劃周期。

ai:任務i的最小持續時間。

resourceCounti,e:任務i請求的元素e的個數。

2.2.4 目標函數

目標是以最小的成本使完成的任務數量最多。當任務元素投標有多個出價時,模型選擇使總成本最低的元素投標,成本由供應商定義。目標函數為

2.3.5 約束條件

(1) 確保每項任務i不會獲得超出其請求的元素e的個數。

(17)

(2) 任務i獲得請求的所有資源時才被執行。

(18)

(3) 全局變量Arrivei是為任務i選擇的所有投標b的最遲到達時間。

earlyb·bidSelectb≤Arrivei, ?i∈T;b∈B(i)

(19)

(4) 全局變量Departi是為任務i選擇的所有投標b的最早離開時間。

lateb+horizon·(1-bidSelectb)≥Departi, ?i∈T;b∈B(i)

(20)

(5) 任務在被服務所需的最小持續時間后才執行完畢。

Arrivei+ai·performi≤Departi, ?i∈T

(21)

3 模型求解

以上模型為混合整數線性規劃模型,其求解方法可分為精確求解和啟發式求解方法。

定向問題是非確定性多項式(non-deterministic polynomial, NP)完全問題[4],這意味著,供應商調度問題也是NP完全問題,在問題規模較大時,精確解法在有限時間內無法給出最優解。在已知的組合優化問題中,大鄰域搜索是解決混合整數規劃問題最強大也最昂貴的啟發式方法之一[17-18]。為利用大鄰域搜索算法的優勢,減少運算成本,本文將求解過程分為兩個階段[19-20],階段一采用績效(merit-based, MB)算法[9]構建問題的初始解,階段二基于初始解采用自適應大鄰域搜索(adaptive large neighborhood search, ALNS)算法尋找最優解。

消費者數學模型較簡單,采用混合整數線性規劃來求解。

3.1 ALNS

ALNS算法[21]基于大鄰域搜索算法,通過在算法中引入多個破壞算子與修復算子擴大解的搜索空間,同時根據算子的歷史表現自適應調整算子的權重來提高算法的搜索效率。

算法的終止條件一般為搜索迭代次數,符合終止條件后,算法返回全局最優解。

在迭代過程中若生成非改進解(即新解不優于當前解),ALNS算法采用模擬退火準則接受非改進解,避免算法陷入局部最優。

3.2 插入可行性判斷

由于時間窗約束及同步約束,使得資源路徑間高度依賴,任意路徑上節點方向的任何微小變化都可能影響所有路徑的到達時間和服務開始時間。為評估在常數時間內插入任意點的可行性,采取如下策略[5]。

首先,濾除解搜尋過程中任務間不可達的邊,即對于任務i,j,當oi+ai+tij>cj時,將邊arcij從初始解中移除。同樣,由于部分任務需要多個資源服務,也就是說被多條路徑訪問,如果在某一路徑中,任務j要在任務i之后被訪問。而在其他路徑中,任務j已被插入到任務i之前,對于這種情況,也要予以濾除。最終,可用一個由0-1變量組成的“插入可行矩陣”Ω來促進插入過程。

為在有限的計算時間內評估某一路徑中插入操作的可行性,還需定義變量maxshifti。該變量用于計算在訪問任務i之前的可用冗余時間。任務i的訪問時間計算為

arrivei=departi-1+ti-1,i

(22)

對于要求多個資源同步服務的任務i,同步服務開始時間為

(23)

式中:Γ為所有服務任務i的資源路徑。資源服務任務i的等待時間為

waiti=sync_starti-arrivei

(24)

將路徑τ對任務i的訪問定義為τ(i),在滿足解可行前提下,資源訪問任務i容許延遲的時間maxshiftτ(i)為

maxshiftτ(i)=min{cτ(i)-startτ(i),waitτ(i+1)+maxshiftτ(i+1)}

(25)

為計算maxshiftτ(i),需要從每條路徑的最后一個任務開始算起,因資源返回基地的時間與其他任務無關。

(26)

(27)

3.3 初始解生成

本文參考MB算法構建ALNS算法的初始解。MB算法是一種改進節約算法[10],結合了經典節約算法和掃描法的優勢,通過在節約函數中添加收益附加項來最大化全局收益。不同于經典節約算法,改進節約算法先嘗試在路徑終端插入新節點,若插入失敗,則嘗試將新節點插入路徑之內[11]。MB算法的核心是優勢對列表(merit pair list, MPL),MPL由元組〈i,j,Mij〉構成,其中i,j∈v,優勢值Mij計算如下:

(28)

算法 1 MB算法偽代碼輸入 最優收益α, 最優路徑β, 未分配任務集T, 優勢對列表MPL, 任務m價值ψm, 元素e個數Ue, 元素e路徑數e∈U(ne), 任務m的資源需求數mrm, 任務距離矩陣dt×t, 任務q的前序已分配任務q'輸出 β和α1 function MB heuristic2 sort T in descending order of ψmrm, ?m∈T3 generate dt×t4 calculate Ω5 calculate merit list and sort ()6 for (m∈T) do

3.4 供應商投標決策過程

供應商在多輪競標過程中需存儲兩個列表。

(1) 未確認任務列表:供應商在上輪調度中已分配,但未從對應消費者處收到接受或拒絕元素投標信息的任務列表。

(2) 確認的任務列表:供應商已從對應的消費者處收到元素投標接受的任務列表。

為加快算法的運行時間,上述列表還包含何種資源在何時為哪項任務提供服務的信息,這些信息被用于下輪投標時初始解的構建。通過將表內任務插入曾經的最優資源路徑位置,使得本輪投標能利用前幾輪投標的結果。當任務因消費者拒絕招標而移除,或消費者對招標資源采取“更新時間窗”策略時,資源調度將發生變化,但原調度框架仍能極大地改善下輪投標的運行時間。

在首輪招、投標中,上述兩個列表為空,首輪招、投標結束后,供應商更新其資源調度表和上述任務列表。當供應商找到資源調度新的最優解后,將調度表中的任務與兩確認列表進行比較,可能出現以下3種情況,如圖5所示。

圖5 供應商決策過程Fig.5 Suppliers decision process

(1) 任務不在任何一個確認列表中:該任務將被添加到未確認任務列表中,并向消費者發送供應商投標通知。

(2) 任務已經在未確認任務列表中:任務的到達和離開時間將在未確認任務列表中更新,以同步新資源調度表的變化。消費者將再次收到供應商的投標通知。

(3) 任務已經在“確認任務列表”中:將任務保持在該列表中,因消費者已經確認了任務投標,供應商不再向消費者發送任何消息。

供應商大規模鄰域搜索中的破壞算子和修復算子見文獻[9],此處不再贅述。

3.5 算例分析

3.5.1 測試集

為分析本算法,建立4個偽隨機檢驗集,對算法進行4輪測試。任務資源需求集為{1,2,3,4},其中{1}是單資源服務任務,{4}是需要4個資源同步的任務。在每個測試集中,需要各級別同步的任務數量相等。如果一個測試集中有4個單資源任務,也會有4個雙協同任務,依此類推。4輪測試由消費者的任務計數區分,分別為4,8,12,16。

測試集的數據由指定邊界內的隨機數生成器生成。任務區域為100 km×100 km的二維平面,任務位置的經緯度是在范圍[0,100]內隨機生成的數字對,任務值從U[1,100]中隨機選取。完成所有任務的規劃時限為1 000 min,所有任務要求完成服務的最短時間都為25 min,任務時間窗開始時間從[0,900]min的均勻分布中選擇,所有時間窗結束時間都是在所選開始時間之后的50 min。

對于任務請求的每個資源,其類型從集合{A,B,C,D}中隨機選擇。因此,一項請求4個資源的任務可以賦予該集合的任意組合,如{A,A,A,A}或{A,B,C,D}。所有資源移動速度相等,但只有X類型的資源才能滿足X類型的任務請求。

與任務位置相同,供應商基地位置也隨機產生。由供應商控制的所有資源,其規劃都從供應商基地位置處開始,又在該處結束。供應商從資源類型集合{A,B,C,D}中隨機分配4類資源。因此,供應商的資源可能為從{A,A,A,A}到{D,D,D,D}之間的所有排列。

3.5.2 評估測試

測試中消費者-供應商網絡為兩個供應商對應3個消費者。消費者和供應商都從測試數據集生成任務和資源。為確定哪種方法更適合實戰場景下的調度資源,通過分析兩個特征進行比較:① 方法的運行時間;② 最佳調度值。

正如預期的那樣,在表1中,除一個測試集外,RUS在比混合整數線性規劃(mixed integer linear programming, MILP)更短的時間內求解測試集。

表1 算法運行時間比較Table 1 Algorithm run time comparison s

一般情況下,隨著測試集規模的增加,MILP方法將無法在2 h內找到最優解,而RUS方法能在合理的時間范圍內持續地找到解。盡管MILP方法不像RUS方法那樣需要多輪競標,但在每個消費者完成8項任務后,MILP方法就變得難以處理。

最優性比較的目的是確定RUS方法生成的解與最優解的差距。MILP方法需要搜索整個解空間,但能保證找到最優解。最優性差距顯示了MILP方法找到的最優解與RUS方法的解之間的差異。

表2中的數據表明,RUS方法提供的解接近最優解。在MILP方法能在2 h內找到最優解的12種情況中,只有1種情況是RUS方法無法找到的。此外,在該情況下,RUS方法解與最優解之間的差異只有4%。

表2 最優性比較Table 2 Optimality comparison

4 結 論

本文參照市場機制,建立基于電子商務多輪競標的供應商調度架構,消費者向供應商提交資源請求參數,供應商對各資源請求發起投標,其資源調度計劃和成本函數僅消費者請求部分對消費者可見,并允許消費者從相互獨立供應商處同步資源。消費者使用混合整數線性規劃來選擇成本最低的投標,通過這些投標的組合來滿足任務的需求。

本文基于電子商務架構的作戰資源調度,將作戰資源調度和作戰任務創建與規劃分由作戰資源規劃節點和作戰任務規劃節點承擔,作戰資源規劃節點只關心本基地所轄資源的調度,作戰任務規劃節點也只關注本區域要執行的作戰任務及任務資源需求。通過去中心化的資源調度與任務規劃,減輕了集中式作戰規劃的復雜性和易損性。同時,供應商不與彼此或消費者共享調度計劃,而只通過有限的握手信息進行交互,減少作戰網絡上的信息傳輸,防止被敵竊聽而泄露計劃。建立了供應商和消費者調度數學模型,并根據模型特點提出模型求解方法,算例分析驗證了方法的有效性。