*

（1.武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430063；2.交通物聯(lián)網(wǎng)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室（武漢理工大學(xué)），武漢 430070）

0 引言

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

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

博弈論主要研究多個(gè)參與者之間的理性決策問(wèn)題，被廣泛運(yùn)用于無(wú)線網(wǎng)絡(luò)中頻譜［12］和功率分配［13］，以及云計(jì)算中“云資源”調(diào)度［14］等問(wèn)題中，但針對(duì)港口的資源調(diào)度討論較少?，F(xiàn)有研究多針對(duì)多個(gè)競(jìng)爭(zhēng)港口之間的定價(jià)問(wèn)題。Dong 等［15］研究表明采用博弈理論的價(jià)格匹配策略能有效促進(jìn)集裝箱碼頭之間的合作。Ishii 等［16］通過(guò)實(shí)例分析得到納什均衡解，得出多港口之間滿足均衡的收費(fèi)策略方案。

散貨堆場(chǎng)是散貨港口的核心資源，堆位分配是堆場(chǎng)資源調(diào)度中極為重要的部分。散貨堆場(chǎng)堆位分配是一個(gè)復(fù)雜的綜合性問(wèn)題，不僅需要考慮堆場(chǎng)的占用情況，還需考慮裝卸船的作業(yè)效率。港口（特別是散貨港口）貨物進(jìn)港有一定的不確定性。由于卸船作業(yè)在船舶剩余貨物量多時(shí)機(jī)械作業(yè)效率較高，因此在貨源充足的情況下，為提高效率，港口會(huì)將一船貨物分批卸入，在作業(yè)繁忙時(shí)優(yōu)先作業(yè)剩余貨物較多的船舶，較空閑時(shí)再作業(yè)剩余貨物量少的效率低的部分。由于所有作業(yè)的貨物都需要進(jìn)入堆場(chǎng)，因此堆位分配時(shí)既要統(tǒng)籌全局，也要局部關(guān)注貨物和堆位的匹配度。如何協(xié)調(diào)多票貨物的分配以達(dá)到某種均衡狀態(tài)，是堆位分配需要解決的問(wèn)題。

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

1 港口散貨堆場(chǎng)堆位分配模型

散貨堆場(chǎng)堆位分配模型用來(lái)描述多票貨物博弈的堆位分配情況，通過(guò)設(shè)計(jì)博弈策略和相應(yīng)的博弈算法，使得復(fù)雜的散貨堆場(chǎng)的堆位分配結(jié)果達(dá)到一種均衡狀態(tài)。

1.1 模型要素

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

1.1.1 堆場(chǎng)資源描述

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

1.1.2 參與者

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

1.1.3 策略空間

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

1.1.4 效用函數(shù)

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

在屬性向量和偏好向量的基礎(chǔ)上，為每個(gè)參與者定義函數(shù)gi：pi→[0，1]來(lái)度量分配的匹配度，如式（1）所示：

1.2 散貨堆場(chǎng)堆位分配中動(dòng)態(tài)博弈的表現(xiàn)

本文建立的堆位分配模型中博弈的動(dòng)態(tài)性具體表現(xiàn)在參與者的博弈次序和策略空間上。

1.2.1 博弈次序

根據(jù)參與者做出決策的順序?qū)⒉┺姆譃殪o態(tài)博弈和動(dòng)態(tài)博弈。本文博弈模型的參與者為待分配的貨物，港口通過(guò)相應(yīng)的卸貨計(jì)劃獲得需要的卸貨信息，由于港口作業(yè)具有較大的不確定性，卸貨計(jì)劃在一定時(shí)間段內(nèi)并不確定，因此參與者的信息具有動(dòng)態(tài)的特性。同時(shí)，由于各參與者對(duì)堆位資源是獨(dú)占的、不可共享的，因此在博弈分配的過(guò)程中需要維持一定的順序以推進(jìn)博弈的進(jìn)行。初始的博弈順序可采取卸貨計(jì)劃到達(dá)的先后順序。

1.2.2 策略空間的動(dòng)態(tài)變化

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

策略空間動(dòng)態(tài)變化只發(fā)生在一次博弈過(guò)程中，在下一次博弈時(shí)，策略空間需要恢復(fù)到初始狀態(tài)。

1.3 散貨堆場(chǎng)堆位分配的滿足博弈

在動(dòng)態(tài)博弈中，由于參與者之間存在著競(jìng)爭(zhēng)對(duì)抗的關(guān)系，從而導(dǎo)致收益無(wú)法達(dá)到最大化。本文將滿足均衡［17］的概念運(yùn)用在堆位分配中，解決納什均衡［17］難以分析的問(wèn)題。

1.3.1 滿足式表述

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

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

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

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

1.3.2 滿足均衡

滿足均衡（Satisfaction Equilibrium）指的是與上述1.3.1節(jié)中滿足式（3）表述所對(duì)應(yīng)的均衡，如定義1。

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

1.3.3 滿足博弈

若不考慮貨物之間對(duì)堆位的競(jìng)爭(zhēng)關(guān)系，則貨物i在其策略空間的最大效用為其理想效用，定義貨物i理想效用如式（4）所示：

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

效用函數(shù)量化了堆位分配的質(zhì)量，但各票貨物對(duì)分配的質(zhì)量要求不同，通過(guò)期望效用表示這種要求，為了體現(xiàn)每一次的分配在這種要求下的效果，本文定義滿足度來(lái)表示。

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

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

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

1.4 裝卸成本函數(shù)

不同的堆存區(qū)域?qū)ω浳锏难b卸成本有著直接的影響，且各貨物有著其成本上限，因此在堆位的分配過(guò)程中，需要考慮其裝卸成本。定義Cji表示第i票貨物分配堆位j所產(chǎn)生的裝卸成本，如式（6）所示：

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

1.5 模型求解目標(biāo)

1）堆位分配目標(biāo)。

2）散貨堆場(chǎng)堆位分配系統(tǒng)誘導(dǎo)目標(biāo)。

散貨堆場(chǎng)堆位分配系統(tǒng)的誘導(dǎo)目標(biāo)主要有：①使得所有貨物的效益和最大，如式（9）所示；②使得所有貨物的裝卸成本和最小，如式（10）所示：

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

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

其中：ξU、ξC分別表示將貨物分配效用值和裝卸成本轉(zhuǎn)化為堆場(chǎng)效益的正參數(shù)，是在具體港口的實(shí)際情況下，根據(jù)貨物效用和裝卸成本計(jì)算結(jié)果的動(dòng)態(tài)變化范圍以及數(shù)量級(jí)關(guān)系來(lái)設(shè)置相應(yīng)部分轉(zhuǎn)為堆場(chǎng)使用效益的正參數(shù)，其值可通過(guò)實(shí)驗(yàn)和實(shí)際生產(chǎn)數(shù)據(jù)統(tǒng)計(jì)分析得到。相應(yīng)的權(quán)值系數(shù)取值范圍均為［0，1］。如果忽略裝卸成本，所得效益稱為理想堆場(chǎng)分配效益。

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

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

散貨堆場(chǎng)堆位分配系統(tǒng)的誘導(dǎo)目標(biāo)為最大化堆場(chǎng)分配效益，如式（13）所示：

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

2 港口散貨堆場(chǎng)堆位分配模型求解

2.1 博弈次序調(diào)整策略

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

1）初始博弈次序采用系統(tǒng)卸貨計(jì)劃順序，即先來(lái)先服務(wù)。

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

2.2 堆位分配策略

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

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

1）初始分配。

初始的博弈次序采用卸貨計(jì)劃的順序，即先來(lái)先服務(wù)。

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

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

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

2）迭代分配過(guò)程。

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

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

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

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

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

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

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

當(dāng)所有貨物都分配了堆位之后，按照式（17）輸出結(jié)果，之后進(jìn)入下一次迭代。

3）算法結(jié)束。

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

2.3 基于博弈論的散貨堆場(chǎng)堆位分配算法

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

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

2.4 算法收斂性證明

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

初始分配階段，各貨物根據(jù)貪心策略分配，此時(shí)堆場(chǎng)分配效益有Q0＜Q*，對(duì)應(yīng)的分配結(jié)果為a0。在迭代階段有如下幾種情況：

1）第1次迭代。

根據(jù)初始的分配結(jié)果Q0和博弈次序調(diào)整策略對(duì)所有貨物N進(jìn)行重新排序，對(duì)?i∈N按照分配策略進(jìn)行分配。

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

分配初始階段，使用a0中第1票貨物的分配結(jié)果a0，1作為初始的分配結(jié)果，此時(shí)堆場(chǎng)的最優(yōu)分配效益為Q0。記Q1，1，0=Q0。Q1，1，0表示第一次迭代，第一票貨物做出決策后堆場(chǎng)分配效率。

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

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

設(shè)第i票貨物做出決策后，所得堆場(chǎng)分配效益為Q1，i。

分配初始階段，使用a0中第i+1 票貨物的分配結(jié)果a0，i+1作為初始的分配結(jié)果。由于前i票貨物已經(jīng)確定行動(dòng)，當(dāng)前局面的最優(yōu)堆場(chǎng)分配效益為Q1，i。記Q1，i+1，0=Q1，i。

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

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

2）第t+1次迭代。

設(shè)第t次迭代后得到的堆場(chǎng)分配效益為Qt，對(duì)應(yīng)的分配結(jié)果為at。

①對(duì)于第1票貨物：

分配初始階段，使用at中第1 票貨物的分配結(jié)果at，1作為初始的分配結(jié)果，此時(shí)堆場(chǎng)的最優(yōu)分配效益為Qt。記Qt+1，1，0=Qt。

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

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

設(shè)第i票貨物做出決策后，所得堆場(chǎng)分配效益為Qt+1，i。

分配初始階段，使用at中第i+1 票貨物的分配結(jié)果at+1，i+1作為初始的分配結(jié)果。由于前i票貨物已經(jīng)確定行動(dòng)，當(dāng)前局面的最優(yōu)堆場(chǎng)分配效益為Qt，i。記Qt+1，i+1，0=Qt，i。

更新第i+1 票貨物對(duì)應(yīng)策略空間的概率分布，選出所有使得效用得到滿足的行動(dòng)，設(shè)有Kt+1，i+1個(gè)行動(dòng)使得效用達(dá)到滿足。貨物試探性地選取Kt+1，i+1中每一個(gè)行動(dòng)j，并計(jì)算堆場(chǎng)分配效率Qt+1，i+1，j。然后，從中選取出最大堆場(chǎng)分配效益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}，對(duì)應(yīng)的行動(dòng)為at+1，i+1。此時(shí)有Qt，i=Qt+1，i+1，0≤Qt+1，i+1≤Q*。

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

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

2.5 時(shí)間復(fù)雜度分析

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

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)平臺(tái)

本文實(shí)驗(yàn)所依托的軟硬件環(huán)境如下：處理器為Intel（R）Core i5-6360U CPU 2.0 GHz；內(nèi)存為8 GB 1867 MHz LPDDR3；操作系統(tǒng)為Windows 10 專業(yè)版；開(kāi)發(fā)語(yǔ)言為Java 1.8.0_111；開(kāi)發(fā)工具為IntelliJ IDEA 2018.2.6；服務(wù)器為Tomcat 8.8.50；工具包為SpringMVC5.2.1.RELEASE、Hibernate 5.1.0.Final；數(shù)據(jù)庫(kù)為Oracle 12。

3.2 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)所使用的數(shù)據(jù)均來(lái)自某內(nèi)河散貨港口，主要包括堆場(chǎng)基礎(chǔ)數(shù)據(jù)和生產(chǎn)業(yè)務(wù)數(shù)據(jù)。

3.2.1 堆場(chǎng)基礎(chǔ)數(shù)據(jù)

基于本文模型的假設(shè)條件，使用的堆場(chǎng)布局如圖2 所示，取該港口的兩個(gè)大型散貨堆場(chǎng)，編號(hào)A、B，4 臺(tái)堆取料機(jī)。堆場(chǎng)共劃分為六個(gè)區(qū)塊，編號(hào)規(guī)則見(jiàn)圖2。其中堆場(chǎng)A的長(zhǎng)度為420 m，區(qū)塊寬度為50 m；堆場(chǎng)B 的長(zhǎng)度為200 m，區(qū)塊寬度為40 m。

圖2 某內(nèi)河港口真實(shí)堆場(chǎng)實(shí)況圖Fig.2 Live map of a real storage yard in an inland port

3.2.2 生產(chǎn)業(yè)務(wù)數(shù)據(jù)

生產(chǎn)業(yè)務(wù)數(shù)據(jù)主要為卸貨計(jì)劃信息，即參與者的信息，從該港口的生產(chǎn)業(yè)務(wù)管理系統(tǒng)數(shù)據(jù)庫(kù)中獲取，如圖3所示。

圖3 生產(chǎn)業(yè)務(wù)數(shù)據(jù)采集示例Fig.3 Production business data collection example

3.2.3 性能指標(biāo)

為了評(píng)估基于博弈論的散貨堆場(chǎng)堆位分配算法的可行性和有效性，根據(jù)本文設(shè)計(jì)思想，選擇貨物的平均滿足度和堆場(chǎng)分配效益作為算法的性能指標(biāo)，如式（24）、（25）所示：

3.3 實(shí)驗(yàn)驗(yàn)證及分析

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

3.3.1 博弈次序調(diào)整中閾值ξ的確定

博弈次序的調(diào)整直接影響著算法的迭代收斂，博弈次序調(diào)整的關(guān)鍵在于閾值ξ的設(shè)定，本文設(shè)定參與者數(shù)量為5、10、15、20，對(duì)每組實(shí)驗(yàn)進(jìn)行20 次迭代，觀察的變化情況，結(jié)果如圖4所示。

ξ的變化情況反映了在迭代過(guò)程中堆場(chǎng)分配效益Qt-1向理想堆場(chǎng)分配效益Q*收斂的情況。隨著迭代的進(jìn)行，堆場(chǎng)分配效益增大，ξ值減小。當(dāng)貨物數(shù)量較少時(shí)，算法收斂整體平穩(wěn)，當(dāng)貨物數(shù)量增加時(shí)，算法后期會(huì)有波動(dòng)。結(jié)合實(shí)驗(yàn)結(jié)果和現(xiàn)場(chǎng)作業(yè)特點(diǎn)，本文以10 票貨物為界限，當(dāng)貨物數(shù)量N≤10時(shí)，貨物數(shù)較少，為了得到更好的效益，ξ可適當(dāng)減小，取值0.18；當(dāng)N＞10 時(shí)，為了避免算法震蕩，無(wú)法收斂，ξ可適當(dāng)增大，取值0.35。

為了評(píng)估同時(shí)請(qǐng)求堆位分配的貨物數(shù)量對(duì)實(shí)驗(yàn)結(jié)果的影響，本實(shí)驗(yàn)將貨物數(shù)量n設(shè)置為4、8、12、16、20，其中每組實(shí)驗(yàn)數(shù)據(jù)采用10次重復(fù)實(shí)驗(yàn)結(jié)果的平均值。

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

3.3.2 參數(shù)設(shè)置

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置Tab.1 Experimental parameter setting

3.3.3 貨物數(shù)量對(duì)貨物平均滿足度的影響

如圖5 所示，貪心算法、SABR 和本文算法中貨物的平均滿足度隨著貨物數(shù)量增加呈現(xiàn)出下降的趨勢(shì)。隨著同時(shí)請(qǐng)求堆位分配的貨物數(shù)量增加，貨物之間的競(jìng)爭(zhēng)加劇，無(wú)法最大化每一票貨物的效用，導(dǎo)致滿足度無(wú)法均衡，整體平均滿足度下降。當(dāng)貨物數(shù)量為8 時(shí)，本文算法的平均滿足度比貪心算法提高7.2%，比SABR 算法提高3.4%。當(dāng)貨物數(shù)量為20時(shí)，本文算法的平均滿足度比貪心算法提高了62.5%，比SABR 算法提高了18.2%?？傮w而言，隨著貨物數(shù)量的增加，本文算法比貪心算法和SABR 算法更能夠提高貨物的平均滿足度。原因是貪心算法忽視了貨物之間對(duì)堆位的競(jìng)爭(zhēng)關(guān)系，SABR算法在搜索過(guò)程中沒(méi)有考慮裝卸成本等因素，而本文的分配算法在考慮堆位匹配度和裝卸成本的同時(shí)，通過(guò)迭代進(jìn)行貨物之間的博弈，使整體效用得到均衡。

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

3.3.4 貨物數(shù)量對(duì)堆場(chǎng)分配效益的影響

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

圖6 貨物數(shù)量對(duì)堆場(chǎng)分配效益的影響Fig.6 Effect of cargo quantity on distribution benefit

3.3.5 貨物數(shù)量對(duì)算法執(zhí)行時(shí)間的影響

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

綜上，在散貨堆場(chǎng)中，當(dāng)同時(shí)請(qǐng)求堆位分配的貨物數(shù)量較多時(shí)，本文算法與貪心算法和SABR 算法相比，能夠提高貨物的平均滿足度和堆場(chǎng)分配效益。雖然本文算法的執(zhí)行時(shí)間較長(zhǎng)，但結(jié)合實(shí)際，尚在可接受范圍內(nèi)。

圖7 貨物數(shù)量對(duì)算法執(zhí)行時(shí)間的影響Fig.7 Effect of cargo quantity on algorithm execution time

4 結(jié)語(yǔ)

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