張艷偉，蔡夢(mèng)蝶

（武漢理工大學(xué)交通與物流工程學(xué)院，湖北武漢 430063）

集裝箱碼頭堆場(chǎng)裝船發(fā)箱和翻箱效率直接影響岸邊裝船作業(yè)和船舶靠泊時(shí)間，是提升集裝箱港口競(jìng)爭(zhēng)力的重要突破口之一。受船舶配載等不確定信息的影響，堆場(chǎng)裝船前預(yù)翻箱整理往往不能完全滿足發(fā)箱要求，裝船時(shí)翻箱作業(yè)不可避免。由于裝船時(shí)翻箱不產(chǎn)生價(jià)值［1］，單次發(fā)箱的翻箱次數(shù)過(guò)多會(huì)影響裝船作業(yè)連貫性，優(yōu)化裝船時(shí)堆場(chǎng)翻箱方案，實(shí)現(xiàn)智能高效決策，是提高堆場(chǎng)裝船發(fā)箱和翻箱效率、保障岸邊裝船作業(yè)的有效手段。集裝箱碼頭堆場(chǎng)通常劃分為不同箱區(qū)，每個(gè)箱區(qū)由多個(gè)貝位組成。一個(gè)貝位的長(zhǎng)度為一個(gè)標(biāo)準(zhǔn)集裝箱長(zhǎng)，貝位內(nèi)通常可堆垛6列4層及以上，即包含24個(gè)集裝箱箱位及以上。由于多層直接堆垛、貝位內(nèi)集裝箱多且每個(gè)集裝箱具有唯一屬性、一個(gè)集裝箱可能存在多次翻箱等，堆場(chǎng)翻箱問(wèn)題解空間大，當(dāng)堆存狀態(tài)不佳時(shí)，甚至無(wú)法在有效時(shí)間內(nèi)得到可行方案，具有NP難屬性［2］。因此，裝船時(shí)翻箱問(wèn)題（container relocation problem，CRP）一直是研究熱點(diǎn)之一。關(guān)于CRP的研究，主要包括數(shù)學(xué)模型研究、精確求解方法研究和智能算法等方面。

Caserta等［3］提出二元線性規(guī)劃模型CRP-Ⅱ，Expósito-Izquierdo等［4］指出CRP-Ⅱ會(huì)產(chǎn)生不可行解，難以保證解最優(yōu)，將其改進(jìn)為CRP-Ⅱ*。Zehendner等［5］也對(duì)CRP-Ⅱ進(jìn)行了修正。Petering等［6］提出混合整數(shù)線性規(guī)劃模型CRP-Ⅲ，整數(shù)決策變量比CRP-Ⅱ少。Galle等［7］改進(jìn)二進(jìn)制整數(shù)編碼方式，提出二元整數(shù)規(guī)劃模型CRP-Ⅰ。Jin［8］指出CRP-Ⅰ中后進(jìn)先出約束存在缺陷，設(shè)計(jì)整數(shù)變量將其變?yōu)榫€性約束。常見(jiàn)的CRP求解分為精確求解［9-12］和智能算法求解［13-15］。Tanaka等［9］提出嚴(yán)格的下界用于分枝定界算法。Tricoire等［10］設(shè)計(jì)基于啟發(fā)式規(guī)則的分枝定界算法。Forster等［11］設(shè)計(jì)啟發(fā)式樹(shù)搜索算法，得到基于翻箱移動(dòng)序列的分枝方案。Tanaka等［12］提出消除樹(shù)搜索不必要節(jié)點(diǎn)的方法。Ting等［13］設(shè)計(jì)波束搜索算法，并用啟發(fā)式評(píng)估搜索節(jié)點(diǎn)。Bacci等［14］設(shè)計(jì)有界波束搜索算法，關(guān)注最有希望的節(jié)點(diǎn)以縮小搜索空間。Feillet等［15］基于局部搜索設(shè)計(jì)啟發(fā)式算法，優(yōu)化局部翻箱操作序列。

逆向強(qiáng)化學(xué)習(xí)（inverse reinforcement learning，IRL）是機(jī)器學(xué)習(xí)的重要分支，可挖掘示例數(shù)據(jù)中隱含信息，克服已有智能算法難以挖掘?qū)＜医?jīng)驗(yàn)的局限，為實(shí)現(xiàn)裝船時(shí)堆場(chǎng)翻箱智能決策奠定基礎(chǔ)。Bengio等［16］對(duì)機(jī)器學(xué)習(xí)求解組合優(yōu)化問(wèn)題進(jìn)行綜述，主張結(jié)合機(jī)器學(xué)習(xí)與已有的組合優(yōu)化算法，實(shí)現(xiàn)算法的改進(jìn)與創(chuàng)新。強(qiáng)化學(xué)習(xí)（reinforcement learning，RL）在人為設(shè)計(jì)回報(bào)函數(shù)后，基于獎(jiǎng)懲機(jī)制使收益最大化，可實(shí)現(xiàn)組合優(yōu)化問(wèn)題的序列決策［17］。為克服RL人為確定回報(bào)函數(shù)的局限，IRL將示例軌跡作為訓(xùn)練數(shù)據(jù)，實(shí)現(xiàn)回報(bào)函數(shù)的自動(dòng)構(gòu)建［18］。陳希亮等［19］綜述深度IRL時(shí)，回顧了學(xué)徒學(xué)習(xí)、最大邊際規(guī)劃、結(jié)構(gòu)化分類等經(jīng)典IRL算法，指出IRL可實(shí)現(xiàn)專家示例數(shù)據(jù)高效利用。Lin等［20］將回報(bào)函數(shù)視為以特征期望為參數(shù)的函數(shù)，從專家示例中學(xué)習(xí)策略。Abbeel等［21］研究馬爾科夫決策過(guò)程（Markov decision processes，MDP）時(shí)，假設(shè)回報(bào)函數(shù)是已知特征的線性組合，并根據(jù)專家正在優(yōu)化該回報(bào)函數(shù)這一假設(shè)，設(shè)計(jì)學(xué)徒學(xué)習(xí)算法。楊放青等［22］運(yùn)用學(xué)徒學(xué)習(xí)解決調(diào)度優(yōu)化問(wèn)題，基于MDP構(gòu)建仿真模型并學(xué)習(xí)專家示范調(diào)度。

現(xiàn)有研究的CRP模型通常以最小化堆場(chǎng)總翻箱次數(shù)為優(yōu)化目標(biāo)，較少限制單次發(fā)箱對(duì)應(yīng)的翻箱次數(shù)；算法難以有效挖掘隱含專家決策經(jīng)驗(yàn)，堆存狀態(tài)不佳時(shí)，優(yōu)化效果有限。為此，論文從模型及算法兩個(gè)方面進(jìn)行研究，實(shí)現(xiàn)以下創(chuàng)新：

（1）以最小化總翻箱次數(shù)為目標(biāo)，同時(shí)限制單次發(fā)箱對(duì)應(yīng)的翻箱次數(shù)，將堆場(chǎng)翻箱過(guò)程描述為MDP，構(gòu)建裝船時(shí)堆場(chǎng)翻箱動(dòng)態(tài)決策模型。

（2）設(shè)計(jì)基于IRL的裝船時(shí)堆場(chǎng)翻箱智能決策算法，挖掘并應(yīng)用翻箱方案中隱含的專家決策信息。

論文設(shè)計(jì)的模型和算法可以實(shí)現(xiàn)裝船時(shí)堆場(chǎng)翻箱智能決策，能有效解決各種堆存狀態(tài)下的裝船時(shí)堆場(chǎng)翻箱決策問(wèn)題。

1 裝船時(shí)堆場(chǎng)翻箱問(wèn)題描述

以常見(jiàn)的順岸式集裝箱碼頭為對(duì)象，研究裝船時(shí)堆場(chǎng)翻箱問(wèn)題。貝位內(nèi)空箱位編號(hào)為0，集裝箱發(fā)箱順序用非0不重復(fù)編號(hào)表示，編號(hào)越小發(fā)箱越早，編號(hào)最小的集裝箱為目標(biāo)箱。各列最早發(fā)箱的集裝箱不在最上層時(shí)，位于其上的集裝箱為阻塞箱。如圖1所示，以6列4層21個(gè)集裝箱的貝位為例，空箱位為第4、5、6列的第4層，第3列第3層編號(hào)為1的集裝箱為目標(biāo)箱，1號(hào)集裝箱的阻塞箱為3號(hào)集裝箱。

裝船時(shí)堆場(chǎng)發(fā)箱作業(yè)包括取箱操作和翻箱操作。取箱操作將位于列最上層的目標(biāo)箱移至水平搬運(yùn)設(shè)備，搬運(yùn)至岸邊裝船；翻箱操作將目標(biāo)箱上方的阻塞箱依次移至貝位內(nèi)空箱位，直至目標(biāo)箱位于最上層。裝船時(shí)堆場(chǎng)翻箱落箱位在翻箱前為空箱位，需滿足集裝箱翻箱后不懸空。翻箱決策需避免后續(xù)不必要翻箱，減少總翻箱次數(shù)，同時(shí)保障單次發(fā)箱對(duì)應(yīng)的翻箱次數(shù)均衡。圖1中，對(duì)1號(hào)集裝箱發(fā)箱時(shí)，阻塞箱3選擇第4列第4層作為翻箱落箱位，可避免后續(xù)翻箱。完成1號(hào)集裝箱發(fā)箱后，貝位堆存狀態(tài)如圖2所示，對(duì)2號(hào)集裝箱發(fā)箱時(shí)，阻塞箱8的翻箱落箱位不選擇第6列，可避免第6列中6號(hào)集裝箱發(fā)箱時(shí)連續(xù)翻箱3次。

2 基于MDP的裝船時(shí)堆場(chǎng)翻箱模型構(gòu)建

2.1 模型假設(shè)

根據(jù)順岸式集裝箱碼頭生產(chǎn)實(shí)際做如下假設(shè)：

（1）貝位內(nèi)僅堆存同一尺寸類型集裝箱，各擬裝船集裝箱發(fā)箱順序已知且唯一。

（2）裝船過(guò)程中，不允許其他集裝箱進(jìn)入擬裝船集裝箱所在貝位。

（3）翻箱操作發(fā)生在單一堆場(chǎng)貝位內(nèi)，翻箱僅針對(duì)目標(biāo)箱上方的阻塞箱。

2.2 符號(hào)說(shuō)明

2.2.1 狀態(tài)變量

I：貝位列標(biāo)號(hào)集合。

H：貝位層標(biāo)號(hào)集合。

K：貝位內(nèi)擬裝船集裝箱集合。

k：當(dāng)前目標(biāo)箱發(fā)箱順序，k∈K。

i：貝位列標(biāo)號(hào)，i∈I。

j：貝位層標(biāo)號(hào)，j∈H。

ij：作為下標(biāo)時(shí)，表示第i列第j層的集裝箱箱位。

n、n′：當(dāng)前目標(biāo)箱的阻塞箱數(shù)量，n=0時(shí)無(wú)阻塞箱，n≠n′。

s：貝位堆存狀態(tài)，貝位同型矩陣，元素值為對(duì)應(yīng)箱位集裝箱發(fā)箱順序，對(duì)應(yīng)箱位為空時(shí)取0。

skn：目標(biāo)箱k有n個(gè)阻塞箱的貝位狀態(tài)。

s′：狀態(tài)s的下一個(gè)堆存狀態(tài)，其中，狀態(tài)s不是最終狀態(tài)。

S：貝位所有可能的堆存狀態(tài)構(gòu)成的有限集合，

t：發(fā)生狀態(tài)轉(zhuǎn)移的時(shí)刻。初始堆存狀態(tài)下，t=0，狀態(tài)s不是最終狀態(tài)時(shí)，轉(zhuǎn)移到s時(shí)刻為t，轉(zhuǎn)移到s′的時(shí)刻為t+1，定義狀態(tài)與時(shí)刻的對(duì)應(yīng)關(guān)系后，作為下標(biāo)可與狀態(tài)s通用。

T：狀態(tài)轉(zhuǎn)移時(shí)刻集合，t∈T。

Nt k：時(shí)刻t目標(biāo)箱k前一個(gè)集裝箱完成發(fā)箱，目標(biāo)箱k上方阻塞箱總數(shù)。

：目標(biāo)箱k上方n個(gè)阻塞箱中最上層的阻塞箱，無(wú)阻塞箱時(shí)，=0。

a、a′：堆場(chǎng)貝位內(nèi)發(fā)箱作業(yè)動(dòng)作，分為取箱和翻箱，目標(biāo)箱有阻塞箱時(shí)為翻箱動(dòng)作，目標(biāo)箱無(wú)阻塞箱時(shí)為取箱動(dòng)作，翻箱落箱位不同，作業(yè)動(dòng)作不同，a≠a′。

A：作業(yè)動(dòng)作集合，翻箱時(shí)，元素為落箱位不同的翻箱動(dòng)作，取箱時(shí)，元素為一個(gè)取箱動(dòng)作，a，a′∈A。

：堆存狀態(tài)轉(zhuǎn)移概率，為狀態(tài)s下采取動(dòng)作a后，轉(zhuǎn)移到s′的概率。

P：堆存狀態(tài)轉(zhuǎn)移概率集合γ：折扣因子，平衡當(dāng)前獎(jiǎng)勵(lì)與未來(lái)獎(jiǎng)勵(lì)，γ∈[0，1]。

Gt：從時(shí)刻t到最終狀態(tài)，獲得的累積獎(jiǎng)勵(lì)。

π：發(fā)箱動(dòng)作選擇策略，為既定狀態(tài)下執(zhí)行所有可能動(dòng)作的概率分布。

qπ(s，a)：狀態(tài)動(dòng)作值函數(shù)，表示從狀態(tài)s出發(fā)，采取動(dòng)作a后，再使用策略π的累積獎(jiǎng)勵(lì)。

R(s)：回報(bào)函數(shù)，計(jì)算狀態(tài)轉(zhuǎn)移時(shí)環(huán)境給出的獎(jiǎng)勵(lì)值，Rt=R(s)時(shí)，Rt+1=R(s′)。

vπ(s)：價(jià)值函數(shù)，用于計(jì)算狀態(tài)s下，采取策略π轉(zhuǎn)移到最終狀態(tài)的累積獎(jiǎng)勵(lì)期望。

M：一個(gè)正整數(shù)，用于限制單次發(fā)箱的翻箱次數(shù)，堆存狀態(tài)良好時(shí)可取值為2，否則取值為初始貝位堆存狀態(tài)下各列中最大阻塞箱數(shù)。

2.2.2 中間變量

d ij：表示第i列第j層的集裝箱箱位是否被占用，被占用時(shí)為1，否則為0。

x ij：表示第i列第j層的集裝箱箱位是否懸空，懸空時(shí)為1，否則為0。

l k：表示是否對(duì)目標(biāo)箱k最上層阻塞箱bkn以外的集裝箱翻箱，是則為1，否則為0。

zi：表示第i列的阻塞箱數(shù)量是否超過(guò)M-1，超過(guò)時(shí)為1，否則為0。

2.2.3 決策變量

aij(skn)：0-1變量，在狀態(tài)skn下翻箱且選擇第i列第j層的集裝箱箱位時(shí)為1，否則為0（取箱時(shí)取值為0）。

2.3 約束與目標(biāo)函數(shù)

初始貝位已知時(shí)，取箱次數(shù)等于擬裝船集裝箱數(shù)量，翻箱次數(shù)越少，發(fā)箱-翻箱移動(dòng)作業(yè)序列越短。每次作業(yè)動(dòng)作后，貝位狀態(tài)發(fā)生轉(zhuǎn)移，記非最終狀態(tài)s為skn，最上層阻塞箱為bkn，轉(zhuǎn)移情況為：若n=0，目標(biāo)箱k阻塞箱為0，發(fā)箱動(dòng)作后轉(zhuǎn)移到s′，目標(biāo)箱更新為k+1，目標(biāo)箱的阻塞箱數(shù)量更新為n′，最上層阻塞箱更新為，s′為；若n≠0，對(duì)阻塞箱翻箱，目標(biāo)箱的阻塞箱數(shù)量減一，最上層阻塞箱序號(hào)更新，s′為。初始貝位狀態(tài)經(jīng)過(guò)取箱、翻箱及落箱位決策，逐步更新到最終狀態(tài)，翻箱方案記錄每次翻箱操作動(dòng)作。裝船時(shí)堆場(chǎng)發(fā)箱過(guò)程時(shí)序性明顯，描述為MDP，記為{S，A，P，R，}γ。以最小化總翻箱次數(shù)為優(yōu)化目標(biāo)，同時(shí)控制單次發(fā)箱對(duì)應(yīng)的翻箱次數(shù)，構(gòu)建基于MDP的翻箱模型，目標(biāo)函數(shù)如式（1）所示。

式（2）表示每次翻箱時(shí)，落箱位決策僅針對(duì)當(dāng)前狀態(tài)中的空箱位；式（3）表示每次翻箱后，集裝箱不懸空；式（4）表示每次翻箱僅針對(duì)當(dāng)前目標(biāo)箱最上層的阻塞箱；式（5）表示狀態(tài)s經(jīng)過(guò)翻箱轉(zhuǎn)移到s′時(shí)，選擇阻塞箱數(shù)量小于M-1的列，限制單次發(fā)箱的翻箱次數(shù)。

MDP具有動(dòng)態(tài)性，狀態(tài)轉(zhuǎn)移與時(shí)刻t有關(guān)，可用時(shí)刻t表示狀態(tài)。式（6）到式（10）為MDP相關(guān)理論。式（6）為狀態(tài)s下采取動(dòng)作a，轉(zhuǎn)移到狀態(tài)s′的概率，取值與策略有關(guān)，隨機(jī)選擇翻箱落箱位時(shí)，取值為|A|的倒數(shù)。每次狀態(tài)轉(zhuǎn)移環(huán)境均會(huì)給出獎(jiǎng)勵(lì)值，若時(shí)刻t對(duì)應(yīng)狀態(tài)為s，式（7）表示從狀態(tài)s轉(zhuǎn)移到最終狀態(tài)，得到的累積獎(jiǎng)勵(lì)值，距離s越遠(yuǎn)的狀態(tài)受s影響越小，引入折扣因子平衡當(dāng)前獎(jiǎng)勵(lì)與未來(lái)獎(jiǎng)勵(lì)。式（8）中，將狀態(tài)s下動(dòng)作a的概率分布記為π(a|s)。由價(jià)值函數(shù)和狀態(tài)動(dòng)作值函數(shù)的定義，可以得到式（9）。根據(jù)式（8）和式（9），推出價(jià)值函數(shù)與狀態(tài)動(dòng)作值函數(shù)關(guān)系如式（10）。

基于MDP的裝船時(shí)堆場(chǎng)翻箱問(wèn)題，旨在找到一種策略π(s)，在狀態(tài)s下采取對(duì)應(yīng)的動(dòng)作a，使總翻箱操作回報(bào)累計(jì)值最大，即每次根據(jù)當(dāng)前狀態(tài)s選擇翻箱動(dòng)作時(shí)，選擇價(jià)值函數(shù)最大的狀態(tài)作為s′，最大狀態(tài)價(jià)值函數(shù)由最優(yōu)狀態(tài)動(dòng)作值函數(shù)得到。用*表示最優(yōu)，裝船時(shí)堆場(chǎng)翻箱動(dòng)態(tài)決策的目標(biāo)函數(shù)可改寫成如式（11）和式（12）所示。

3 基于IRL的求解算法設(shè)計(jì)

裝船時(shí)堆場(chǎng)翻箱問(wèn)題具有MDP特性，可用RL方法求解。為克服RL回報(bào)函數(shù)依賴人為確定的局限，設(shè)計(jì)基于IRL的裝船時(shí)堆場(chǎng)翻箱智能決策算法，挖掘?qū)＜曳浞桨钢须[含的決策經(jīng)驗(yàn)，應(yīng)用于裝船時(shí)堆場(chǎng)翻箱落箱位選擇，實(shí)現(xiàn)裝船時(shí)堆場(chǎng)翻箱智能決策。

3.1 專家示例表示方法

RL中狀態(tài)轉(zhuǎn)移后，環(huán)境會(huì)給出獎(jiǎng)勵(lì)，訓(xùn)練數(shù)據(jù)是狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)值構(gòu)成的系列。不同于RL，IRL的輸入是專家示例，不需環(huán)境給出獎(jiǎng)勵(lì)，訓(xùn)練數(shù)據(jù)是狀態(tài)-動(dòng)作序列。裝船時(shí)翻箱問(wèn)題中，發(fā)箱動(dòng)作矩陣可由相鄰狀態(tài)矩陣相減求出。以圖1貝位狀態(tài)為例，初始狀態(tài)為矩陣s0，將3號(hào)集裝箱翻箱至第4列第4層得到矩陣s1，完成1號(hào)集裝箱取箱后得到矩陣s2。翻箱動(dòng)作矩陣a1和取箱動(dòng)作矩陣a2如下：

在翻箱、取箱動(dòng)作矩陣中，非0元素絕對(duì)值為被操作集裝箱發(fā)箱順序編號(hào)，元素位置對(duì)應(yīng)于堆場(chǎng)貝位中位置。翻箱動(dòng)作矩陣中，負(fù)值元素位置對(duì)應(yīng)堆場(chǎng)貝位中翻箱動(dòng)作起始位置，正值元素位置對(duì)應(yīng)翻箱落箱位。取箱動(dòng)作矩陣中無(wú)正值元素，負(fù)值元素位置對(duì)應(yīng)當(dāng)前目標(biāo)箱所在集裝箱箱位。發(fā)箱動(dòng)作矩陣可由相鄰狀態(tài)矩陣計(jì)算得到，此時(shí)，專家示例可只用貝位狀態(tài)序列表示。

3.2 基于IRL的回報(bào)函數(shù)確定

基于IRL構(gòu)建回報(bào)函數(shù)，需先將狀態(tài)映射為狀態(tài)特征向量，并根據(jù)專家示例進(jìn)行求解，相關(guān)理論如下：

其中，φ(s)：s→Rn是基函數(shù)，將狀態(tài)s映射到狀態(tài)特征向量中。ω∈Rn為參數(shù)向量，是根據(jù)專家示例構(gòu)建回報(bào)函數(shù)的關(guān)鍵。π*表示專家方案，πˉ表示所求方案，δ為極小的正數(shù)。

IRL假設(shè)待求回報(bào)函數(shù)下專家示例最優(yōu)，回報(bào)函數(shù)為狀態(tài)特征向量和參數(shù)向量的內(nèi)積，如式（13）所示，基于假設(shè)求解參數(shù)向量ω，即可構(gòu)建回報(bào)函數(shù)。定義μπ(s)為特征期望，如式（14）所示。由式（13）和式（14）可將價(jià)值函數(shù)改寫為式（15）。式（16）表示得到的方案πˉ在特征期望上接近專家方案π*。

特征向量需簡(jiǎn)潔全面地刻畫堆場(chǎng)貝位堆存狀態(tài)，特征向量元素選取當(dāng)前目標(biāo)箱發(fā)箱順序、目標(biāo)箱的阻塞箱數(shù)量、有空箱位的列的數(shù)量、空列的數(shù)量。進(jìn)行翻箱落箱位選擇，需分析有空位的列的性質(zhì)，為此，判斷當(dāng)前目標(biāo)箱最上層阻塞箱發(fā)箱順序是否晚于其他列的最早發(fā)箱順序，并關(guān)注當(dāng)前堆存狀態(tài)下阻塞箱數(shù)量達(dá)到M的列數(shù)。每次進(jìn)行翻箱動(dòng)作選取之前，采取較為常見(jiàn)的蒙特卡洛模擬方法，計(jì)算下一個(gè)狀態(tài)所有可能的特征期望。

3.3 IRL算法設(shè)計(jì)

回報(bào)函數(shù)影響RL的求解質(zhì)量，人為確定具有很強(qiáng)的主觀性，復(fù)雜問(wèn)題甚至難以給出直觀的回報(bào)函數(shù)。為此，以專家翻箱方案為訓(xùn)練數(shù)據(jù)，基于IRL還原回報(bào)函數(shù)，同時(shí)結(jié)合RL方法，設(shè)計(jì)基于IRL的裝船時(shí)堆場(chǎng)翻箱智能決策算法，挖掘并應(yīng)用專家翻箱方案中隱含決策經(jīng)驗(yàn)，實(shí)現(xiàn)裝船時(shí)堆場(chǎng)翻箱智能決策。

IRL分為最大邊際和最大熵兩大類，前者包括學(xué)徒學(xué)習(xí)、最大邊際規(guī)劃、結(jié)構(gòu)化分類等，后者包括最大熵、相對(duì)熵和深度IRL等。學(xué)徒學(xué)習(xí)算法所需數(shù)據(jù)少，決策空間離散時(shí)可定量比較各策略，為此，設(shè)計(jì)學(xué)徒學(xué)習(xí)算法從專家翻箱方案中學(xué)習(xí)回報(bào)函數(shù)，結(jié)合RL實(shí)現(xiàn)問(wèn)題求解：先基于學(xué)徒學(xué)習(xí)還原專家示例中的回報(bào)函數(shù)，用于RL進(jìn)行策略迭代；對(duì)比當(dāng)前策略與專家策略，基于最大邊際求參數(shù)向量ω。循環(huán)以上兩步，改進(jìn)回報(bào)函數(shù)至能反應(yīng)專家意圖為止。裝船時(shí)堆場(chǎng)翻箱智能決策算法流程如圖3所示。

圖3 基于IRL的裝船時(shí)堆場(chǎng)翻箱智能決策算法流程Fig.3 Flow chart of intelligent decision algorithm based on IRL for yard relocation during loading

4 算例分析

4.1 對(duì)比策略設(shè)計(jì)

裝船時(shí)堆場(chǎng)貝位按照既定發(fā)箱順序發(fā)箱，若當(dāng)前目標(biāo)箱位于貝位內(nèi)列的最上層，直接提箱裝船；若當(dāng)前目標(biāo)箱不位于貝位內(nèi)列的最上層，依次對(duì)其上方各集裝箱進(jìn)行翻箱操作，直至當(dāng)前目標(biāo)箱位于列的最上層，提箱裝船。翻箱決策的本質(zhì)是對(duì)當(dāng)前擬翻箱的集裝箱進(jìn)行落箱箱位選取，最基礎(chǔ)的翻箱決策不考慮總翻箱次數(shù)及單次發(fā)箱對(duì)應(yīng)的翻箱次數(shù)，隨機(jī)選擇不懸空的空箱位作為翻出集裝箱的落箱位。

由于隨機(jī)決策無(wú)任何優(yōu)化，在碼頭生產(chǎn)實(shí)際中，通?？紤]翻出集裝箱對(duì)后續(xù)裝船的影響，依照一定的經(jīng)驗(yàn)規(guī)則選取落箱箱位，盡量避免翻出集裝箱再次阻塞貝位內(nèi)其他集裝箱，減少總翻箱次數(shù)。

基于規(guī)則的決策在集裝箱碼頭生產(chǎn)實(shí)際中被廣泛使用，但貝位堆存狀態(tài)不佳時(shí)，其優(yōu)化效果有限，甚至存在劣于隨機(jī)決策的可能。

為驗(yàn)證本文算法與模型的有效性，將設(shè)計(jì)的IRL算法與碼頭常見(jiàn)規(guī)則決策、隨機(jī)決策對(duì)比。

策略一：隨機(jī)決策。隨機(jī)選擇不懸空的空箱位，作為翻出集裝箱的落箱位。

策略二：規(guī)則決策。在有不懸空空箱位的列中，優(yōu)先選取列內(nèi)最早發(fā)箱順序晚于被翻集裝箱的列，作為翻出集裝箱的落箱位；沒(méi)有這樣的列時(shí)，隨機(jī)選擇空列；沒(méi)有空列時(shí)，隨機(jī)選擇不懸空的空箱位，作為翻出集裝箱的落箱位。

策略三：基于IRL的決策。挖掘并應(yīng)用專家翻箱方案中隱含決策經(jīng)驗(yàn)，設(shè)計(jì)基于IRL的裝船時(shí)堆場(chǎng)翻箱智能決策算法，基于獎(jiǎng)懲機(jī)制選擇獎(jiǎng)勵(lì)期望最大的不懸空空箱位，作為翻出集裝箱的落箱位。

4.2 算例設(shè)計(jì)

吞吐量和裝卸效率是集裝箱碼頭的重要統(tǒng)計(jì)指標(biāo)，目前已形成完整的統(tǒng)計(jì)體系。相比之下，集裝箱堆場(chǎng)翻箱率為翻箱次數(shù)與總操作次數(shù)的比值，受采集技術(shù)及堆存狀態(tài)波動(dòng)等影響，目前只有少數(shù)港口對(duì)翻箱率進(jìn)行過(guò)初步統(tǒng)計(jì)，尚未形成統(tǒng)一有效的統(tǒng)計(jì)體系。根據(jù)集裝箱碼頭生產(chǎn)實(shí)際，裝船時(shí)堆場(chǎng)翻箱率通常為15%至30%不等，堆場(chǎng)堆存空間不足、集裝箱堆存狀態(tài)欠佳時(shí)，將有所增加。算例以常見(jiàn)的6列4層貝位為例，考慮翻箱空間需求，貝位內(nèi)最多堆存21個(gè)集裝箱，選取翻箱率20%、30%、40%進(jìn)行算例設(shè)計(jì)較為合理，對(duì)應(yīng)翻箱次數(shù)為4.2、6.3和8.4次?？紤]到算例設(shè)計(jì)時(shí)翻箱方案和翻箱次數(shù)未知且需要設(shè)置初始堆存狀態(tài)，為此，進(jìn)行簡(jiǎn)化將貝位初始狀態(tài)阻塞箱數(shù)量設(shè)置為4個(gè)、6個(gè)和8個(gè)。由于貝位初始狀態(tài)阻塞箱總數(shù)是裝船時(shí)堆場(chǎng)貝位翻箱次數(shù)的下界，該設(shè)置方法對(duì)應(yīng)的翻箱率一定大于或約等于20%、30%和40%，比集裝箱碼頭堆場(chǎng)實(shí)際堆存狀態(tài)復(fù)雜，能夠適應(yīng)堆場(chǎng)翻箱決策需要。

定義貝位初始狀態(tài)阻塞箱總數(shù)與待發(fā)集裝箱總數(shù)比值為阻塞箱占比。如圖4中3種貝位初始狀態(tài)，阻塞箱個(gè)數(shù)分別為4個(gè)、6個(gè)和8個(gè)，阻塞箱占比依次為19.0%、28.5%和38.1%。隨著貝位堆存狀態(tài)變差，一般會(huì)出現(xiàn)連續(xù)多次翻箱的情況。M取值為3，從策略一、策略二中選擇總翻箱次數(shù)少，連續(xù)翻箱3次情形少的方案作為專家示例。電腦處理器為Intel（R）Core（TM）i7-8750H CPU@2.20GHz，運(yùn)行內(nèi)存8 GB，基于Python實(shí)現(xiàn)3種狀態(tài)下隨機(jī)決策、規(guī)則決策和基于IRL的決策各100次。

圖4 3種堆場(chǎng)貝位初始堆存狀態(tài)Fig.4 Initial storage state of bay in three scenarios

4.3 結(jié)果分析

3種狀態(tài)下策略一、策略二和策略三對(duì)應(yīng)的100個(gè)方案的翻箱次數(shù)箱形圖如圖5所示。從圖5可以看出，基于IRL的決策整體上求解質(zhì)量較高。相對(duì)于隨機(jī)決策和規(guī)則決策，基于IRL決策的總翻箱次數(shù)下限和中位數(shù)小，貝位阻塞箱占比較大時(shí)，翻箱次數(shù)集中分布在較小翻箱次數(shù)處。表明基于IRL的翻箱決策優(yōu)勢(shì)明顯，可實(shí)現(xiàn)專家經(jīng)驗(yàn)的有效利用。

圖5 3種策略的翻箱次數(shù)箱形圖Fig.5 Box plot of relocation times of three policies

為避免岸橋等待集裝箱，裝船時(shí)貝位翻箱需限制單次發(fā)箱的翻箱次數(shù)，優(yōu)秀的翻箱策略更易形成總翻箱次數(shù)較少的方案，同時(shí)可限制方案中單次發(fā)箱的翻箱次數(shù)。以最小總翻箱次數(shù)及其出現(xiàn)概率、連續(xù)多次翻箱的概率為重要指標(biāo)，3種策略的翻箱方案結(jié)果如表1所示。

由表1可知：

表1 3種策略下翻箱方案結(jié)果Tab.1 Results of three kinds of decision-making schemes

（1）基于IRL的決策可產(chǎn)生總翻箱次數(shù)最少的方案，且該類方案出現(xiàn)的次數(shù)明顯高于其他2種策略。說(shuō)明其他2種策略隨機(jī)性大，基于IRL的決策對(duì)應(yīng)的方案收斂至最小翻箱次數(shù)的概率顯著增大。

（2）阻塞箱占比增加時(shí)，規(guī)則決策適應(yīng)性不強(qiáng)，阻塞箱占比28.5%時(shí)，出現(xiàn)3回及以上連翻3次翻箱的方案數(shù)遠(yuǎn)高于其他2種策略。說(shuō)明規(guī)則設(shè)計(jì)與貝位初始狀態(tài)有關(guān)聯(lián)，提煉規(guī)則用于裝船時(shí)堆場(chǎng)翻箱決策的難度較大。

（3）基于IRL的決策在阻塞箱占比較大時(shí)，連續(xù)翻箱3次為3回及以上的方案數(shù)顯著少于其他2種策略。說(shuō)明貝位堆存狀態(tài)不佳時(shí)，基于IRL的決策在限制單次發(fā)箱的翻箱次數(shù)上優(yōu)勢(shì)更明顯。

（4）堆場(chǎng)貝位堆存較滿且阻塞箱占比約20.0%及以上時(shí)，很難避免多次翻箱，翻箱率遠(yuǎn)高于阻塞箱占比。

Kim等［23］提出預(yù)期翻箱次數(shù)（expected number of additional relocations，ENAR）概念，設(shè)計(jì)啟發(fā)式算法OH。徐亞等［24］賦予有空位的列不同的優(yōu)先級(jí)，基于ENAR提出另一種啟發(fā)式算法IH。游鑫夢(mèng)等［25］在堆場(chǎng)箱區(qū)及貝位分配的基礎(chǔ)上，針對(duì)多種堆存情形提出翻箱落箱位選取規(guī)則，設(shè)計(jì)啟發(fā)式算法與OH算法及IH算法對(duì)比，分析不同貝位規(guī)模下算法的性能。

為驗(yàn)證IRL的有效性，選取常見(jiàn)的6列4層貝位規(guī)模，與OH算法［23］、IH算法［24］和啟發(fā)式算法［25］對(duì)比，算法求解方案的平均翻箱次數(shù)和平均運(yùn)行時(shí)間如表2所示。由表2可知，IRL可以有效地控制總翻箱次數(shù)。由于IRL算法在每次狀態(tài)轉(zhuǎn)移時(shí)均需計(jì)算所有下一個(gè)狀態(tài)的價(jià)值函數(shù)，總循環(huán)迭代次數(shù)多，求解時(shí)間相對(duì)較長(zhǎng)，但耗時(shí)在可接受范圍內(nèi)。

5 結(jié)語(yǔ)

裝船時(shí)集裝箱堆場(chǎng)發(fā)箱作業(yè)時(shí)序性明顯，以最小化總翻箱次數(shù)為目標(biāo)，同時(shí)限制連續(xù)多次翻箱，基于MDP構(gòu)建混合整數(shù)模型。為克服RL回報(bào)函數(shù)難以確定的局限，設(shè)計(jì)IRL算法學(xué)習(xí)專家示例，挖掘?qū)＜医?jīng)驗(yàn)應(yīng)用于翻箱決策中。以隨機(jī)決策為基準(zhǔn)，將基于IRL的決策與碼頭常見(jiàn)規(guī)則決策、隨機(jī)決策對(duì)比?；贗RL決策時(shí)，總翻箱次數(shù)收斂于最小翻箱次數(shù)的概率更大；堆場(chǎng)貝位狀態(tài)較差時(shí)，優(yōu)化方案總翻箱次數(shù)集中分布于較小翻箱次數(shù)處，單次發(fā)箱時(shí)翻箱多次的情況得到有效限制。與已有智能算法進(jìn)行對(duì)比，發(fā)現(xiàn)IRL可以有效控制總翻箱次數(shù)，受算法循環(huán)迭代次數(shù)多的影響，耗時(shí)相對(duì)較長(zhǎng)，但在可接受范圍?；贗RL制定翻箱方案可解決常見(jiàn)智能算法難以提煉并應(yīng)用專家經(jīng)驗(yàn)的局面，實(shí)現(xiàn)專家決策中隱含經(jīng)驗(yàn)在翻箱決策中的智能應(yīng)用。

作者貢獻(xiàn)聲明：

張艷偉：提出研究方向，設(shè)計(jì)論文框架并指導(dǎo)模型構(gòu)建、論文撰寫。

蔡夢(mèng)蝶：構(gòu)建模型，進(jìn)行編程求解及論文撰寫。