基于博弈論的散貨港口堆場堆位分配算法

*

（1.武漢理工大學計算機科學與技術學院，武漢 430063；2.交通物聯網技術湖北省重點實驗室（武漢理工大學），武漢 430070）

0 引言

港口作為一個從事貨物裝卸、搬運、存儲以及加工的場所，在整個運輸鏈中扮演著關鍵節點的角色，是水陸交通運輸的樞紐［1］。隨著信息技術的迅速發展，我國港口當前正朝著更加綠色、智能的第五代港口發展［2］，并且提出了智慧港口（Smart Port）的概念［3］。例如黃驊港智能堆場系統的投運，使其成為國內散貨碼頭自動化的標桿，專用散貨煤炭碼頭正在實驗鐵路線智能排產［4］等。散貨港口（特別是內河沿線港口）堆場由于面積小，件散貨貨類眾多、形狀不規則，導致作業繁雜，因此急需堆場智能分配方法來提高堆存效率和作業效率，但是和智能排產、智能調度相比，對散貨碼頭的智能分配方面的研究目前仍處于信息搜集和處理的初步階段［5］。因此，港口的散貨堆場如何在先進技術的支持下，對堆場的貨物進行智能分配，規范堆場管理，提高散貨堆場的利用率成為了港口散貨碼頭智能化研究的重點。

隨著港口智能化的不斷推進，堆位分配的研究不斷增多，但主要還是集中在集裝箱方面，針對散貨港口堆場堆位分配方法的研究較少。近年來，相關學者研究堆場堆位分配問題的方法主要有系統仿真、模型和算法兩類。在系統仿真方法上，Wang 等［6］研究了基于規則的煤炭堆場堆位分配問題，通過搜索可用堆場、堆位和裝備三種資源來確定合適的堆存區域，建立的仿真模型能有效提高堆場的利用率，缺點是僅適用于煤炭港口。Bruglieri 等［7］基于貨物體積構建混合整數規劃數學模型，通過系統仿真構建3-D 堆場模型進行優化求解，并通過維多利亞港實際數據模型測試證實該模型的有效性和高效性，但它僅適用于吞吐量大、貨類單一的海港。孫勇［8］建立了散貨碼頭堆場物流系統的動態Petri 網模型，但簡化了堆場物流的流程，且研究成果局限于理論。在模型和算法方面，智能算法運用廣泛，Savelsbergh 等［9］通過在散貨時空圖上搜索空閑堆存區域、可用機械等來確定煤堆最早可以開始裝卸的區域，并提出樹搜索算法，能有效減少船舶等待時間，但方法適用范圍有限。徐克輝［10］在建立堆場分配模型基礎上，使用知識工程相關技術得到最優的堆存區域，但可用空間逐層篩選的效率還十分有限。宋昕［11］采用定性推理和定量計算相結合的方式，設計了基于本體和進化算法的散雜貨港口堆場多目標優化調度算法，但在堆位匹配度計算中簡化了其影響因素，需要進一步在實踐中檢驗和完善。

博弈論主要研究多個參與者之間的理性決策問題，被廣泛運用于無線網絡中頻譜［12］和功率分配［13］，以及云計算中“云資源”調度［14］等問題中，但針對港口的資源調度討論較少。現有研究多針對多個競爭港口之間的定價問題。Dong 等［15］研究表明采用博弈理論的價格匹配策略能有效促進集裝箱碼頭之間的合作。Ishii 等［16］通過實例分析得到納什均衡解，得出多港口之間滿足均衡的收費策略方案。

散貨堆場是散貨港口的核心資源，堆位分配是堆場資源調度中極為重要的部分。散貨堆場堆位分配是一個復雜的綜合性問題，不僅需要考慮堆場的占用情況，還需考慮裝卸船的作業效率。港口（特別是散貨港口）貨物進港有一定的不確定性。由于卸船作業在船舶剩余貨物量多時機械作業效率較高，因此在貨源充足的情況下，為提高效率，港口會將一船貨物分批卸入，在作業繁忙時優先作業剩余貨物較多的船舶，較空閑時再作業剩余貨物量少的效率低的部分。由于所有作業的貨物都需要進入堆場，因此堆位分配時既要統籌全局，也要局部關注貨物和堆位的匹配度。如何協調多票貨物的分配以達到某種均衡狀態，是堆位分配需要解決的問題。

當前，港口向著智能化方向不斷發展，但對于散貨港口堆場堆位分配的研究仍非常有限，因此，為綜合考慮堆場資源的合理化利用和裝卸作業進度的匹配程度，本文采用博弈論的思想，通過設定博弈策略，進行多次迭代博弈，采用“滿足均衡”［17］分析博弈，以尋求使得堆位分配達到均衡的分配方案，從而提高貨物與堆位之間的匹配度，提高堆場使用效率，降低不必要的作業成本。

1 港口散貨堆場堆位分配模型

散貨堆場堆位分配模型用來描述多票貨物博弈的堆位分配情況，通過設計博弈策略和相應的博弈算法，使得復雜的散貨堆場的堆位分配結果達到一種均衡狀態。

1.1 模型要素

堆位分配模型包括港口堆場相關資源的描述，以及博弈論中三大基本元素，即參與者、策略空間和效用函數。

1.1.1 堆場資源描述

建立一個堆場形式化模型是進行堆位分配的基礎，模型對相應的資源及條件進行符號化描述，本文采用如下一種四元組的形式來描述堆場模型Y=其中：S={si|i=1，2，…，k1}，si表示第i個堆位，每一個堆位包含其基本信息如容量、所在位置和支持存儲貨類等；H表示堆場目前堆存的貨物，H={hi|i=1，2，…，k2}，hi表示第i票貨物，其中包含貨主、貨類、重量等基本信息；J表示堆場作業機械（堆取料機）集合，J={ji|i=1，2，…，k3}，ji表示第i個機械，每個機械包含所處位置等信息；R代表堆場的作業線集合，R={ri|i=1，2，…，k4}，ri表示第i條作業線，每條作業線包括配置人員數量、每個環節工作量系數（作業單價）等信息。

1.1.2 參與者

在堆場堆位分配的博弈模型中，參與者為當前時刻確定的即將卸貨入堆場的多票貨物，用集合N={Ni|i=1，2，…，n}表示，?Ni∈N都包含以下相關屬性：貨主、貨類、重量、進出港運輸方式等。

1.1.3 策略空間

針對當前的堆場Y，需要搜索出所有可用的堆位，集合S={s1，s2，…，sM}表示有M個可用堆位，將參與者做出決策（選擇某一堆位）這一動作稱為行動（action），定義ai表示參與者i的行動，所有的行動集合稱為行動空間（action space），即策略空間。用Ai表示參與者i的行動空間，Ai={s1，s2，…，sK}，K≤M，即有Ai?S。參與者i根據博弈的混合策略原則從Ai中選擇行動，即遵循特定的概率分布πi=其中表示參與者選擇行動sk的概率，即第i票貨物選擇可用堆位k的概率。

1.1.4 效用函數

堆位具有諸多屬性，比如支持存放的貨類、堆位的容量、是否靠近鐵路線或碼頭等，每個屬性都可以量化為相應的屬性值，同時，貨物對堆位的各個屬性具有一定程度的偏好，比如采用船舶運輸的貨物對靠近碼頭的堆位有著較重的偏好。同樣可以量化為偏好值。將上述屬性和偏好處理為向量，稱為屬性向量和偏好向量。假設抽取出T個因素，有pi=[pi1，pi2，…，piT]表示第i個堆位的屬性向量，pij，j∈(1，2，…，T)表示堆位i在屬性j上的屬性值。同樣有ri=[ri1，ri2…，riT]表示貨物i的偏好向量，rij，j∈(1，2，…，T)表示貨物i對堆位屬性j的偏好度。設rmax=pmax為貨物偏好值和堆位屬性值的上限，規定0 ≤pij≤rmax=pmax。

在屬性向量和偏好向量的基礎上，為每個參與者定義函數gi：pi→[0，1]來度量分配的匹配度，如式（1）所示：

1.2 散貨堆場堆位分配中動態博弈的表現

本文建立的堆位分配模型中博弈的動態性具體表現在參與者的博弈次序和策略空間上。

1.2.1 博弈次序

根據參與者做出決策的順序將博弈分為靜態博弈和動態博弈。本文博弈模型的參與者為待分配的貨物，港口通過相應的卸貨計劃獲得需要的卸貨信息，由于港口作業具有較大的不確定性，卸貨計劃在一定時間段內并不確定，因此參與者的信息具有動態的特性。同時，由于各參與者對堆位資源是獨占的、不可共享的，因此在博弈分配的過程中需要維持一定的順序以推進博弈的進行。初始的博弈順序可采取卸貨計劃到達的先后順序。

1.2.2 策略空間的動態變化

為了避免為每一個參與者都維系一個策略空間所帶來的瑣繁，規定所有的參與者共享同一個策略空間，即所有貨物都可以分配到可用的堆位，可以通過概率分布πi進行控制，例如前面的貨物i選擇堆位j后，那么后面的參與者概率分布中=0。同時，若貨物i在做出選擇后，后面存在參與者k的貨類不能與貨物i相鄰，因此對于參與者k而言，所有貨物i相鄰的可用堆位的選擇概率均為0。

策略空間動態變化只發生在一次博弈過程中，在下一次博弈時，策略空間需要恢復到初始狀態。

1.3 散貨堆場堆位分配的滿足博弈

在動態博弈中，由于參與者之間存在著競爭對抗的關系，從而導致收益無法達到最大化。本文將滿足均衡［17］的概念運用在堆位分配中，解決納什均衡［17］難以分析的問題。

1.3.1 滿足式表述

假設參與者對收益有一個低于最優值Γmax的預期，設為Γ，若存在行動組合s=(si，s-i)使得ui(s) ≥Γi，其中si，s-i分別表示參與者i的策略組合和除i之外其他參與者的策略組合。則稱參與者i達到滿足狀態。定義映射如下：

將其表示為式（2）所示的形式：

因此可用式（3）所示的三元組表示博弈模型，稱為博弈的滿足式表達：

其中：N為參與者，Si為策略空間。

1.3.2 滿足均衡

滿足均衡（Satisfaction Equilibrium）指的是與上述1.3.1節中滿足式（3）表述所對應的均衡，如定義1。

定義1若給定行動s*=針對式（3）所示的滿足式表述，有?i∈N→則稱s*為博弈的滿足均衡［17］。

1.3.3 滿足博弈

若不考慮貨物之間對堆位的競爭關系，則貨物i在其策略空間的最大效用為其理想效用，定義貨物i理想效用如式（4）所示：

其中：Ui=gi，根據滿足均衡的定義，若給定一個行動ai，即分配堆位j，其屬性向量pj，若有ui(ai，a-i)=gi(pj)≥Γi，則稱貨物i得到滿足。本文建立的基于博弈論的散貨堆場堆位分配模型可用式（5）所示的三元組表示。

效用函數量化了堆位分配的質量，但各票貨物對分配的質量要求不同，通過期望效用表示這種要求，為了體現每一次的分配在這種要求下的效果，本文定義滿足度來表示。

定義2貨物在某一堆位處的效用與期望效用之比稱為滿足度，記作：

其中，σi表示貨物i的滿足度，用σ-i表示其他貨物的滿足度，即：

引入σi和σ-i之后，可以將ui(ai，a-i) 改寫為ui(σi，σ-i；ri)，函數ui(·；ri)以ri作為參數，以σi和σ-i作為輸入變量。

1.4 裝卸成本函數

不同的堆存區域對貨物的裝卸成本有著直接的影響，且各貨物有著其成本上限，因此在堆位的分配過程中，需要考慮其裝卸成本。定義Cji表示第i票貨物分配堆位j所產生的裝卸成本，如式（6）所示：

為了直觀地體現裝卸成本，僅考慮港方在裝卸過程中的金錢成本，同時作業線每個環節的工作量系數（作業單價）已經事先設置好，因此成本計算包括兩個方面：機械成本和人員成本。假設所有作業線包含S個環節，M種機械，每個環節的人力成本單價為ps(s=1，2，…，S)（元/噸）。機械成本僅考慮其機械本身在作業過程中的油耗和損耗成本兩部分，并通過實際生產中機械的維護數據可以計算出相應機械的油耗oilm和損耗系數losm（元/噸）。以卸貨成本為例，計算如式（7）所示：

1.5 模型求解目標

1）堆位分配目標。

2）散貨堆場堆位分配系統誘導目標。

散貨堆場堆位分配系統的誘導目標主要有：①使得所有貨物的效益和最大，如式（9）所示；②使得所有貨物的裝卸成本和最小，如式（10）所示：

為了更好地衡量堆位分配的效果，本文定義堆場分配效益，堆場分配效益為以上兩者的線性組合，如定義3所示。

定義3設ωU，ωC分別表示貨物分配效用、裝卸成本的權值系數，兩者之和為1，所有貨物分配的效用值以及裝卸成本的帶權和稱為堆場分配效益，如式（11）所示：

其中：ξU、ξC分別表示將貨物分配效用值和裝卸成本轉化為堆場效益的正參數，是在具體港口的實際情況下，根據貨物效用和裝卸成本計算結果的動態變化范圍以及數量級關系來設置相應部分轉為堆場使用效益的正參數，其值可通過實驗和實際生產數據統計分析得到。相應的權值系數取值范圍均為［0，1］。如果忽略裝卸成本，所得效益稱為理想堆場分配效益。

定義4堆場所有貨物的理想效用的累加和稱為理想堆場分配效益，如式（12）所示：

顯然，任何階段的堆場分配效益都小于理想堆場分配效益，Qt表示博弈階段的堆場分配效益，則有Qt＜Q*。

散貨堆場堆位分配系統的誘導目標為最大化堆場分配效益，如式（13）所示：

本文旨在找到某一分配組合a+，使其成為式（8）、（13）最優解，稱a+為系統均衡解，即本文建立的分配模型求解目標為：在提高貨物與堆位匹配度的同時最大化堆場分配效益。

2 港口散貨堆場堆位分配模型求解

2.1 博弈次序調整策略

博弈次序決定參與者做出決策的順序，為了體現堆位分配中的公平性和加速堆位分配算法的收斂，本文采取如下規則調整博弈次序。

1）初始博弈次序采用系統卸貨計劃順序，即先來先服務。

2）假設貨物i在第t-1 次迭代中獲得效用與期望效用的距離記作＜0 時，效用未達到預期≥0時，效用已達預期。

2.2 堆位分配策略

堆位分配采取迭代的思想，每一次迭代開始的輸入和輸出形式如下：

輸入為所有的參與者信息N（所有待分配的貨物），初始的策略空間S（可用的堆位集合），前一次的迭代分配結果at-1，前一次的效用向量Ut-1，前一次的總裝卸成本Ct-1，前一次的堆場分配效益Qt-1，同樣輸出為本次迭代的相應結果。根據文獻［17］，本文規定迭代過程按如下規則進行：

1）初始分配。

初始的博弈次序采用卸貨計劃的順序，即先來先服務。

初始時刻（t=0），貨物i對策略空間進行搜索，過濾掉已被占用的堆位，得到可用策略空間并計算其在行動空間上的概率分布，然后選擇ai(0)，貨物選擇行動ai(0)的概率計算如式（16）所示：

其中：ci(ak)表示選擇該行動的裝卸成本，α(α＞1)表示貨物對裝卸成本的重視程度，α取值越大，貨物在分配堆位過程中越重視裝卸成本；β(β＞1)表示貨物對效用的重視程度，β取值越大，表示越重視貨物分配所取得的效用。表示在當前局面中其他貨物的分配結果向量，χi(0)為歸一化因子，按式（17）計算：

初始時刻，由于沒有歷史選擇策略可供參考，理性的參與者以效用最大且成本最小的方式選擇堆位。

2）迭代分配過程。

在第t次迭代開始時(t=1，2…)，貨物i首先判斷目前的分配ai(t-1)是否滿足了預期，即效用和裝卸成本是否滿足要求。定義指示變量νi(t-1)，計算如式（18）所示。

在第t次迭代過程中，貨物根據νi(t-1)的取值更新概率分布，然后選擇行動ai(t)。需要說明的是，受動態博弈的博弈次序影響，在新的迭代中，前一次分配的堆位可能不可用。因此，在指示變量為0或者1時都需要考慮ai(t-1)是否可用問題。當然這是很容易判斷的，根據前面參與者的決策和策略空間的動態變化得到當前策略空間新一輪迭代按照如下規則進行。

如果當前貨物i還未達到預期，即νi(t-1)=0，此時，貨物i可能改變策略，或其他貨物改變策略。但是其他貨物的行動策略不確定，作為理性的參與者，希望此時的選擇在將來看來是不后悔的，此時的行動選擇概率如式（19）所示：

其中，σi(t-1)表示貨物i對前一次分配的不后悔程度。對前一次迭代的選擇越不后悔，那么繼續選擇該堆位的概率就越大；即在新的一次迭代中繼續保持上一次的分配結果。不后悔程度可直接用滿足度表示，具體表現形式如式（20）所示：

從式（20）中可以看出，若上一次分配獲得的效用越接近于預期效用，σi(t-1)取值越大，則貨物保持前一次選擇的概率越大。因此隨著迭代的進行，貨物的效用逐漸接近預期效用，則不再改變策略，達到均衡狀態。歸一化因子χi(t)定義如式（21）所示：

如果前一次的分配已經達到預期，即σi(t-1)=1，則貨物i很有可能不改變策略，此時，概率的計算方式如式（22）所示：

其中：參數μ表示貨物維持前一次選擇的概率，文獻［17］證明0.5 ≤μ≤1，此時歸一化因子χi(t)計算如式（23）所示：

當所有貨物都分配了堆位之后，按照式（17）輸出結果，之后進入下一次迭代。

3）算法結束。

若經過ts(ts＞0)次迭代之后，所有的貨物都得到了滿足，或者算法迭代達到最大可接受次數tmax，算法終止并按式（15）輸出最佳分配組合。

2.3 基于博弈論的散貨堆場堆位分配算法

本文根據上述堆位分配策略提出基于博弈論的散貨堆場堆位分配算法，主要由兩部分組成：1）算法初始階段為每票貨物根據貪心策略分配堆位；2）隨后按照上述博弈策略進行多次的迭代分配直到算法滿足終止條件。該算法的流程如圖1所示。

圖1 基于博弈論的散貨堆場堆位分配算法Fig.1 Bulk storage assignment algorithm in bulk port based on game theory

2.4 算法收斂性證明

這里采用數學歸納法證明基于博弈論的散貨堆場堆位分配算法（Bulk Storage Assignment Algorithm in Bulk port based on Game theory，BSAABG）可使堆場分配效益隨著算法迭代次數的增加而增大，最后達到收斂。

初始分配階段，各貨物根據貪心策略分配，此時堆場分配效益有Q0＜Q*，對應的分配結果為a0。在迭代階段有如下幾種情況：

1）第1次迭代。

根據初始的分配結果Q0和博弈次序調整策略對所有貨物N進行重新排序，對?i∈N按照分配策略進行分配。

①對于第1 票貨物（通常將船上裝載的某一規格貨物稱為1票貨，一般每艘船載貨數少于5票）：

分配初始階段，使用a0中第1票貨物的分配結果a0，1作為初始的分配結果，此時堆場的最優分配效益為Q0。記Q1，1，0=Q0。Q1，1，0表示第一次迭代，第一票貨物做出決策后堆場分配效率。

更新第1 票貨物對應策略空間的概率分布，選出所有使得效用得到滿足的行動，設有K1，1個行動使得效用達到滿足。貨物試探性地選取K1，1中每一個行動j，并計算其堆場分配效率Q1，1，j。從中選取最大的堆場分配效益Q1，1=max{Q1，1，0，Q1，1，1，…，Q1，1，j，…，Q1，1，K1，1}，對應的行動為a1，1。此時有Q0=Q1，1，0≤Q1，1≤Q*。

②對于第i+1票貨物（2 ≤i+1 ≤|N|）：

設第i票貨物做出決策后，所得堆場分配效益為Q1，i。

分配初始階段，使用a0中第i+1 票貨物的分配結果a0，i+1作為初始的分配結果。由于前i票貨物已經確定行動，當前局面的最優堆場分配效益為Q1，i。記Q1，i+1，0=Q1，i。

更新第i+1票貨物對應策略空間的概率分布，選出所有使得效用得到滿足的行動，設有K1，i+1個行動使得效用達到滿足。貨物試探性地選取K1，i+1中的每一個行動j，并計算出堆場分配效率為Q1，i+1，j，然后，從中選取出其最大的堆場分配效益為Q1，i+1=max{Q1，i+1，0，Q1，i+1，1，…，Q1，i+1，j，…，Q1，i+1，K1，1}，對應的行動為a1，i+1。此時有Q1，i=Q1，i+1，0≤Q1，i+1≤Q*。

綜上，第1次迭代中各票貨物通過試探性分配所得堆場分配效益間關系為Q0≤Q1，1≤…≤Q1，i+1≤…≤Q1，|N|≤Q*。第1次迭代所得的分配結果為a1，堆場分配效益為Q1，滿足Q0≤Q1≤Q*。

2）第t+1次迭代。

設第t次迭代后得到的堆場分配效益為Qt，對應的分配結果為at。

①對于第1票貨物：

分配初始階段，使用at中第1 票貨物的分配結果at，1作為初始的分配結果，此時堆場的最優分配效益為Qt。記Qt+1，1，0=Qt。

更新第1票貨物對應策略空間的概率分布，選出所有使得效用得到滿足的行動，設有Kt+1，1個行動使得效用達到滿足。貨物試探性地選取Kt+1，1中的每一個行動j，并計算其堆場分配效率Qt+1，1，j。然后，從中選取出其最大的堆場分配效益為Qt+1，1=max{Qt+1，1，0，Qt+1，1，1，…，Qt+1，1，j，…，Qt+1，1，K1，1}，對應的行動為at+1，1。此時有Qt=Qt+1，1，0≤Qt+1，1≤Q*。

②對于第i+1票貨物（2 ≤i+1 ≤|N|）：

設第i票貨物做出決策后，所得堆場分配效益為Qt+1，i。

分配初始階段，使用at中第i+1 票貨物的分配結果at+1，i+1作為初始的分配結果。由于前i票貨物已經確定行動，當前局面的最優堆場分配效益為Qt，i。記Qt+1，i+1，0=Qt，i。

更新第i+1 票貨物對應策略空間的概率分布，選出所有使得效用得到滿足的行動，設有Kt+1，i+1個行動使得效用達到滿足。貨物試探性地選取Kt+1，i+1中每一個行動j，并計算堆場分配效率Qt+1，i+1，j。然后，從中選取出最大堆場分配效益Qt+1，i+1=max{Qt+1，i+1，0，Qt+1，i+1，1，…，Qt+1，i+1，j，…，Qt+1，i+1，K1，1}，對應的行動為at+1，i+1。此時有Qt，i=Qt+1，i+1，0≤Qt+1，i+1≤Q*。

綜上，第t+1 次迭代中，各票貨物通過試探性分配所得到的堆場分配效益的關系為Qt≤Qt+1，1≤…≤Qt+1，i+1≤…≤Qt+1，|N|≤Q*。第t+1 次迭代所得的分配結果為at+1，堆場分配效益為Qt+1，滿足Qt≤Qt+1≤Q*。

由上述分析可得Q0≤Q1≤…≤Qt≤…≤Q*，即隨著迭代次數的增大堆場分配效益也逐漸增大，最后達到收斂。

2.5 時間復雜度分析

根據算法的時間復雜度分析方法，對本文算法的時間復雜度進行分析。本文的散貨堆場堆位分配方法分為初始分配和迭代分配：1）初始分配階段，各票貨物按照先來先服務的原則，根據貪心策略選擇堆位，設有待分配的貨物為N，可用堆位數為M，計算選擇堆位的概率分布，因此初始分配階段的時間復雜度為O(NM)。2）迭代分配階段，首先需要調整博弈次序，進行從小到大排序，時間復雜度為O(NlogN)，然后對每票貨物進行策略調整，首先計算隨機概率分布，然后試探性地選擇滿足效用的堆位，故時間復雜度為O(NM2)，綜上，本文所提的堆位分配算法時間復雜度為O(NlogN+NM2)。

3 實驗結果與分析

3.1 實驗平臺

本文實驗所依托的軟硬件環境如下：處理器為Intel（R）Core i5-6360U CPU 2.0 GHz；內存為8 GB 1867 MHz LPDDR3；操作系統為Windows 10 專業版；開發語言為Java 1.8.0_111；開發工具為IntelliJ IDEA 2018.2.6；服務器為Tomcat 8.8.50；工具包為SpringMVC5.2.1.RELEASE、Hibernate 5.1.0.Final；數據庫為Oracle 12。

3.2 實驗數據

本文實驗所使用的數據均來自某內河散貨港口，主要包括堆場基礎數據和生產業務數據。

3.2.1 堆場基礎數據

基于本文模型的假設條件，使用的堆場布局如圖2 所示，取該港口的兩個大型散貨堆場，編號A、B，4 臺堆取料機。堆場共劃分為六個區塊，編號規則見圖2。其中堆場A的長度為420 m，區塊寬度為50 m；堆場B 的長度為200 m，區塊寬度為40 m。

圖2 某內河港口真實堆場實況圖Fig.2 Live map of a real storage yard in an inland port

3.2.2 生產業務數據

生產業務數據主要為卸貨計劃信息，即參與者的信息，從該港口的生產業務管理系統數據庫中獲取，如圖3所示。

圖3 生產業務數據采集示例Fig.3 Production business data collection example

3.2.3 性能指標

為了評估基于博弈論的散貨堆場堆位分配算法的可行性和有效性，根據本文設計思想，選擇貨物的平均滿足度和堆場分配效益作為算法的性能指標，如式（24）、（25）所示：

3.3 實驗驗證及分析

為了將本文提出的基于博弈論的散貨堆場堆位分配算法（BSAABG）與目前普遍采用的人工調度經驗進行比較，在同一組實驗數據上，邀請重慶某散貨港口兩名調度員依據其調度經驗進行模擬分配，將模擬分配結果和貪心算法（Greedy Algorithm，GA）所得結果進行比較發現：當貨物數量較大時，由于堆場作業的復雜性，調度人員此時無法掌握堆場全局，只能考慮到某一局部狀態，此時和貪心算法的求解思想一致，所以兩者分配結果所獲得的堆場使用效益相近。因此用貪心算法模擬人工調度經驗是可行的，將人工分配過程模擬為貪心算法，按照先來先服務的次序，為貨物分配堆位。文獻［6，10］通過制定相應的分配規則，設計基于規則的堆位分配算法（Storage Assignment algorithm Based on Rule，SABR），算法設計堆位分配的狀態空間，通過可用機械、可用堆存區和堆位匹配度進行狀態空間篩選，得到分配結果。本文對以上三者進行實驗對比分析。

3.3.1 博弈次序調整中閾值ξ的確定

博弈次序的調整直接影響著算法的迭代收斂，博弈次序調整的關鍵在于閾值ξ的設定，本文設定參與者數量為5、10、15、20，對每組實驗進行20 次迭代，觀察的變化情況，結果如圖4所示。

ξ的變化情況反映了在迭代過程中堆場分配效益Qt-1向理想堆場分配效益Q*收斂的情況。隨著迭代的進行，堆場分配效益增大，ξ值減小。當貨物數量較少時，算法收斂整體平穩，當貨物數量增加時，算法后期會有波動。結合實驗結果和現場作業特點，本文以10 票貨物為界限，當貨物數量N≤10時，貨物數較少，為了得到更好的效益，ξ可適當減小，取值0.18；當N＞10 時，為了避免算法震蕩，無法收斂，ξ可適當增大，取值0.35。

為了評估同時請求堆位分配的貨物數量對實驗結果的影響，本實驗將貨物數量n設置為4、8、12、16、20，其中每組實驗數據采用10次重復實驗結果的平均值。

圖4 (Q*- Qt -1)Q*隨迭代次數變化情況Fig.4 (Q*- Qt -1)Q*changes with the number of iterations

3.3.2 參數設置

根據該內河港口的實際作業情況，對本文相關參數進行設置和調整，下面給出部分參數的取值分析。統計分析該港口單日堆場裝卸作業數據可知，單日同時卸貨總票數不超過20，所以確定本文貨物數量n的取值范圍為［1，20］，算法最大迭代次數tmax和n的取值相關，若貨物數量增加，可適當增大tmax，本文根據港口實際作業情況設tmax取值20。港方在卸貨時的投入往往比裝貨時大，因此在裝卸成本計算式（6）中，卸貨權重略大于裝貨權重。根據港口實際作業情況的貨物效用和裝卸成本計算結果動態變化范圍以及數量級關系，設置相應部分轉為堆場分配效益正參數。博弈次序調整策略閾值在3.2.1節中已經確定，文獻［17］已證明0.5 ≤μ≤1，具體相關參數設置如表1 所示，參數設置應結合港口具體情況，可根據歷史數據和觀察實驗結果進行動態調整。

表1 實驗參數設置Tab.1 Experimental parameter setting

3.3.3 貨物數量對貨物平均滿足度的影響

如圖5 所示，貪心算法、SABR 和本文算法中貨物的平均滿足度隨著貨物數量增加呈現出下降的趨勢。隨著同時請求堆位分配的貨物數量增加，貨物之間的競爭加劇，無法最大化每一票貨物的效用，導致滿足度無法均衡，整體平均滿足度下降。當貨物數量為8 時，本文算法的平均滿足度比貪心算法提高7.2%，比SABR 算法提高3.4%。當貨物數量為20時，本文算法的平均滿足度比貪心算法提高了62.5%，比SABR 算法提高了18.2%。總體而言，隨著貨物數量的增加，本文算法比貪心算法和SABR 算法更能夠提高貨物的平均滿足度。原因是貪心算法忽視了貨物之間對堆位的競爭關系，SABR算法在搜索過程中沒有考慮裝卸成本等因素，而本文的分配算法在考慮堆位匹配度和裝卸成本的同時，通過迭代進行貨物之間的博弈，使整體效用得到均衡。

圖5 貨物數量對貨物平均滿足度的影響Fig.5 Effect of cargo quantity on the average satisfaction

3.3.4 貨物數量對堆場分配效益的影響

如圖6 所示，貪心算法、SABR 算法和本文算法中堆場分配效益隨著貨物數量的增加呈現出下降趨勢。原因是隨著請求堆位貨物數量的增加，平均滿足度降低且裝卸成本增加，因此堆場分配效益降低。當請求堆位的貨物數量為4 時，本文算法的堆場分配效益是貪心算法的1.1 倍，是SABR 算法的1.05倍。當請求堆位的貨物數量為20時，本文算法中的堆場分配效益是貪心算法的6.83 倍，是SABR 算法的3.22 倍。綜上可知，在貨物數量增大的情況下，本文算法相較于貪心算法和SABR 算法能更好地提高堆場分配效益。原因是貪心算法和SABR 算法分配時只考慮單票貨物本身和堆位的匹配度，缺乏對堆場整體效益的考慮。而本文算法在迭代過程中通過調整分配策略，使得分配效益增大，即增大堆場分配效益。

圖6 貨物數量對堆場分配效益的影響Fig.6 Effect of cargo quantity on distribution benefit

3.3.5 貨物數量對算法執行時間的影響

如圖7 所示，貪心算法、SABR 算法和本文算法的運行時間隨著請求堆位貨物數的增加而呈現上升的趨勢。在算法執行時間上，無論貨物數量的多少，前兩個算法的執行時間均低于本文算法。當貨物數量為4 時，貪心算法的執行時間僅為1.252 s，而本文算法執行時間為3.272 s。當貨物數量為20時，貪心算法的執行時間僅為2.485 s，而本文算法執行時間為8.902 s。原因是貪心算法和SABR算法的實現邏輯相對簡單，是對單票貨物的操作，而本文算法由于進行迭代操作，時間復雜度較大。港口進行堆位分配從需求上而言，對實時性要求并不高，以極少的時間代價換取貨物和堆位匹配度的提升和提高堆場的效益是值得的。

綜上，在散貨堆場中，當同時請求堆位分配的貨物數量較多時，本文算法與貪心算法和SABR 算法相比，能夠提高貨物的平均滿足度和堆場分配效益。雖然本文算法的執行時間較長，但結合實際，尚在可接受范圍內。

圖7 貨物數量對算法執行時間的影響Fig.7 Effect of cargo quantity on algorithm execution time

4 結語

為了提高散貨港口堆場堆位分配的合理性，使各票貨物的堆位匹配度得到滿足，同時提高堆場使用效率，降低港口作業成本，使得堆場分配效益最大化，本文首先建立貨物選擇堆位的博弈模型來分析堆位分配的行為，然后采用基于博弈論的散貨堆場堆位分配算法求解模型。在某內河港口的真實堆場環境上進行測試，本文算法在貨物平均滿足度和堆場分配效益方面與貪心算法和SABR 算法相比均有所提升。但本文研究仍存在不足，堆場分配效益的計算具有一定的局限性。在考慮堆位分配模型的求解目標時，雖然考慮了兩個方面的因素，但最后通過線性組合的方式形成了單目標，并引入了相應的參數。今后將深入研究多目標問題，將多目標求解和博弈思想融入模型求解中，進一步提升堆位分配效率，并提出更加完善的堆場分配效益計算方法。