增強(qiáng)學(xué)習(xí)算法在集裝箱船舶配載問(wèn)題上的應(yīng)用

嚴(yán)翀宇 王男男 沈一帆

集裝箱船舶配載是集裝箱碼頭生產(chǎn)作業(yè)的重要環(huán)節(jié)之一，其直接影響碼頭整體裝卸作業(yè)效率。目前，我國(guó)集裝箱碼頭主要采用傳統(tǒng)在線搜索算法解決集裝箱船舶配載問(wèn)題，但此類方法在求解大規(guī)模算例時(shí)效率較低。為此，本文采用增強(qiáng)學(xué)習(xí)算法，將大量耗時(shí)計(jì)算前置到線下訓(xùn)練階段，實(shí)際配載時(shí)則利用訓(xùn)練好的網(wǎng)絡(luò)直接求解，從而提高求解效率。具體思路如下：首先，分析集裝箱船舶配載問(wèn)題的關(guān)鍵決策因素，并從中提煉相關(guān)的配載特征向量；然后，根據(jù)集裝箱船舶配載問(wèn)題的特點(diǎn)和約束條件，設(shè)計(jì)相應(yīng)的狀態(tài)、動(dòng)作和回報(bào)函數(shù)，以計(jì)算每組集裝箱-船箱位配對(duì)的Q值，并以配載特征向量作為網(wǎng)絡(luò)輸入，以每組集裝箱-船箱位配對(duì)的Q值作為網(wǎng)絡(luò)輸出，以均方誤差作為評(píng)估函數(shù)，構(gòu)建增強(qiáng)學(xué)習(xí)網(wǎng)絡(luò)，并結(jié)合Q學(xué)習(xí)算法實(shí)現(xiàn)集裝箱船舶配載問(wèn)題的增強(qiáng)學(xué)習(xí)算法；最后，分析該算法與傳統(tǒng)智能優(yōu)化算法的區(qū)別，說(shuō)明增強(qiáng)學(xué)習(xí)算法能夠高效求解集裝箱船舶配載問(wèn)題。

1 研究現(xiàn)狀

目前，我國(guó)集裝箱碼頭主要依靠人工加計(jì)算機(jī)輔助的方式制訂集裝箱船舶配載計(jì)劃，而人工配載的一大弊端是配載結(jié)果容易受到配載員個(gè)人經(jīng)驗(yàn)和狀態(tài)的影響；因此，如何將配載員的個(gè)人經(jīng)驗(yàn)與計(jì)算機(jī)算法相結(jié)合，快速、有效地制訂合理的配載計(jì)劃有重要的研究意義。國(guó)內(nèi)外學(xué)者對(duì)集裝箱船舶配載問(wèn)題的研究主要集中在配載模型和配載算法方面。

1.1 配載模型的研究現(xiàn)狀

（1）主貝計(jì)劃配載模型 TODD等針對(duì)單港口的主貝計(jì)劃配載問(wèn)題，以縱傾力矩、橫傾力矩、船舶穩(wěn)性和距離位置等為約束條件，以翻箱量最小為目標(biāo)函數(shù)，采用遺傳算法求解。ZHAO等針對(duì)集裝箱船舶主貝計(jì)劃配載問(wèn)題，考慮船舶穩(wěn)性、翻箱量和場(chǎng)橋作業(yè)效率等因素，建立多目標(biāo)整數(shù)規(guī)劃模型；但該模型過(guò)于復(fù)雜，很難進(jìn)行規(guī)劃求解，缺乏實(shí)用性。MOURA等在同時(shí)考慮主貝計(jì)劃和航線因素的情況下，以運(yùn)輸成本最小化為目標(biāo)函數(shù)，建立混合整數(shù)規(guī)劃模型。

（2）貝內(nèi)計(jì)劃配載模型 AVRIEL等以翻箱量最小為優(yōu)化目標(biāo)構(gòu)建簡(jiǎn)單的整數(shù)規(guī)劃模型，并設(shè)計(jì)相應(yīng)算法，通過(guò)算例驗(yàn)證該算法在較小規(guī)模的情況下可以得到較好的求解效果；但該模型過(guò)于簡(jiǎn)單，實(shí)用性不強(qiáng)。SHIELDS建立數(shù)學(xué)模型，并將模型求解結(jié)果與實(shí)際裝船結(jié)果進(jìn)行對(duì)比，證明模型的有效性；但由于當(dāng)時(shí)的船舶大多為中小型船舶，該模型已無(wú)法適應(yīng)當(dāng)前船舶大型化趨勢(shì)下的約束條件和優(yōu)化目標(biāo)。IMAI等構(gòu)建0-1整數(shù)多目標(biāo)配載模型，計(jì)算得到堆場(chǎng)翻箱量；但在配載問(wèn)題中，如果存在大量0-1整數(shù)二元變量和約束條件，求解難度將加大，很難得到最優(yōu)解。

1.2 配載算法的研究現(xiàn)狀

大多數(shù)學(xué)者采用智能優(yōu)化算法求解集裝箱船舶配載問(wèn)題。ALVAREZ在考慮正面吊移動(dòng)距離、翻箱量和船舶質(zhì)量分布的情況下，提出基于多個(gè)初始解的禁忌搜索算法，并將該算法運(yùn)用到實(shí)際算例中與混合整數(shù)規(guī)劃算法進(jìn)行對(duì)比。研究結(jié)果表明，其設(shè)計(jì)的算法能夠在較短時(shí)間內(nèi)求解上百個(gè)箱量的算例，而混合整數(shù)規(guī)劃算法只能求解40個(gè)以內(nèi)集裝箱的算例。KIM等提出運(yùn)用束搜索算法求解集裝箱船舶配載問(wèn)題，并在考慮場(chǎng)橋和翻箱量等因素的基礎(chǔ)上構(gòu)建模型，制訂合理、有效的配載和收箱策略。LEE等利用層級(jí)理論解決集裝箱船舶配載問(wèn)題，將發(fā)箱順序問(wèn)題分解為小規(guī)模子問(wèn)題，并設(shè)計(jì)一種將蟻群算法與禁忌搜索算法相結(jié)合的混合啟發(fā)式算法。算例驗(yàn)證結(jié)果表明，該混合啟發(fā)式算法的求解效率高于單純的蟻群算法和禁忌搜索算法。衛(wèi)家駿[14]設(shè)計(jì)禁忌搜索-蟻群混合算法求解集裝箱船舶配載問(wèn)題，并通過(guò)仿真模擬試驗(yàn)進(jìn)行驗(yàn)證。

1.3 小結(jié)

綜上所述，針對(duì)集裝箱船舶配載問(wèn)題，現(xiàn)有的研究主要聚焦于構(gòu)建混合整數(shù)規(guī)劃模型，并利用特殊設(shè)計(jì)的啟發(fā)式算法求解。該類算法雖然能夠在一定程度上較好地求解小規(guī)模算例，但仍然存在很大局限性，例如：只能求解特殊情況下的配載問(wèn)題；大規(guī)模算例的求解效率不高；等等。為此，本文采用增強(qiáng)學(xué)習(xí)算法，通過(guò)訓(xùn)練得到配載智能體，從而能夠在各種情況下高效求解配載問(wèn)題。

2 集裝箱船舶配載問(wèn)題描述

2.1 決策因素

（1）集裝箱不懸空原則 在制訂裝船作業(yè)的貝內(nèi)計(jì)劃時(shí)，需要考慮集裝箱的裝船順序。如果同一列的上層船箱位的裝船順序先于下層船箱位的裝船順序，就會(huì)造成集裝箱懸空現(xiàn)象，致使裝船作業(yè)無(wú)法順利進(jìn)行，進(jìn)而導(dǎo)致裝船作業(yè)效率下降。

（2）海側(cè)至陸側(cè)裝船原則 在陸側(cè)已裝船集裝箱層高高于海側(cè)已裝船集裝箱層高的情況下，如果需要繼續(xù)為海側(cè)船箱位發(fā)箱，岸橋的起升高度必須超過(guò)陸側(cè)已裝船集裝箱層高，否則會(huì)造成集裝箱碰撞。為避免產(chǎn)生上述跨高作業(yè)，對(duì)于同一層的船箱位，配載時(shí)應(yīng)當(dāng)考慮從海側(cè)往陸側(cè)實(shí)施裝船作業(yè)，從而確保裝船作業(yè)的安全性和高效性。

（3）船箱位質(zhì)量范圍原則 在制訂貝內(nèi)計(jì)劃時(shí)，應(yīng)當(dāng)考慮主貝計(jì)劃確定的船舶貝位預(yù)分層質(zhì)量，即每個(gè)貝位每層集裝箱的質(zhì)量范圍，確保每個(gè)船箱位的集裝箱質(zhì)量在此范圍內(nèi)，以滿足船舶穩(wěn)性和集裝箱綁扎要求。

（4）重壓輕極限原則 理論上，集裝箱船舶配載應(yīng)遵循下重上輕原則；但在實(shí)際配載過(guò)程中，為方便碼頭作業(yè)，在不影響船舶穩(wěn)性的前提下，允許存在少量的重壓輕。在重壓輕的情況下，上下相鄰集裝箱的質(zhì)量差通常應(yīng)控制在0.5～1.0t，具體可根據(jù)船型作相應(yīng)調(diào)整。

2.2 優(yōu)化目標(biāo)

（1）艙面梯形配載 梯形配載是艙面配載的獨(dú)特工藝，指配載時(shí)應(yīng)考慮按船箱位順序從海側(cè)往陸側(cè)以樓梯形式依次發(fā)箱，從而確保相鄰格柵已裝船集裝箱的層高不至于相差過(guò)大，同時(shí)降低岸橋司機(jī)的作業(yè)難度。

（2）減少翻箱頻次 翻箱作業(yè)是無(wú)用作業(yè)，是導(dǎo)致裝船作業(yè)效率下降的主要因素之一。對(duì)于堆場(chǎng)內(nèi)同一箱區(qū)、同一貝位、同一列的集裝箱，配載時(shí)應(yīng)盡量使上層集裝箱先發(fā)，否則會(huì)導(dǎo)致翻箱作業(yè)。為避免場(chǎng)橋頻繁翻箱，配載時(shí)應(yīng)當(dāng)考慮同一箱區(qū)、同一貝位、同一列的集裝箱從上往下依次發(fā)箱，從而使場(chǎng)橋翻箱頻次最小。

（3）減少移機(jī)頻次 此處的移機(jī)指場(chǎng)橋在不同箱區(qū)之間或同一箱區(qū)內(nèi)的不同貝位之間移動(dòng)。裝船作業(yè)時(shí)，如果相鄰發(fā)箱順序號(hào)所對(duì)應(yīng)的集裝箱位于不同箱區(qū)或同一箱區(qū)內(nèi)的不同貝位，就會(huì)造成移機(jī)。不合理的發(fā)箱順序會(huì)導(dǎo)致場(chǎng)橋在不同箱區(qū)之間或同一箱區(qū)內(nèi)的不同貝位之間頻繁移動(dòng)，使得裝船作業(yè)效率下降；因此，配載時(shí)應(yīng)當(dāng)考慮同一箱區(qū)內(nèi)的同一貝位連續(xù)發(fā)箱，從而使場(chǎng)橋移機(jī)頻次最小。

3 集裝箱船舶配載問(wèn)題增強(qiáng)學(xué)習(xí)算法設(shè)計(jì)

3.1 增強(qiáng)學(xué)習(xí)算法概述

設(shè)計(jì)函數(shù)Q（s，a），用于計(jì)算配載狀態(tài)s下執(zhí)行

式中t為時(shí)刻；st為系統(tǒng)在時(shí)刻t的狀態(tài)；at為決策者在系統(tǒng)處于狀態(tài)st的情況下所采取的動(dòng)作；rt為系統(tǒng)在狀態(tài)st下通過(guò)動(dòng)作at獲得的回報(bào)值。

式中：t為時(shí)刻；st為系統(tǒng)在時(shí)刻t的狀態(tài)；at為決策者在系統(tǒng)處于狀態(tài)st的情況下所采取的動(dòng)作。

3.2.2 配載狀態(tài)設(shè)計(jì)

在配載問(wèn)題中，t為配載順序，t=0表示未配載集裝箱，t=1表示配載第1個(gè)集裝箱，t=2表示配載第2個(gè)集裝箱，以此類推。假設(shè)船箱位序號(hào)為L(zhǎng)1～L6（見(jiàn)圖1），則集裝箱船舶配載問(wèn)題的馬爾可夫決策過(guò)程如圖2所示。

配載動(dòng)作a所得到的總回報(bào)值。在初始階段，配載智能體就像一位對(duì)集裝箱船舶配載問(wèn)題一竅不通的配載員。針對(duì)配載智能體為解決配載問(wèn)題所采取的每個(gè)配載動(dòng)作，即集裝箱-船箱位的配對(duì)，回報(bào)函數(shù)均會(huì)反饋相應(yīng)的回報(bào)值。配載智能體通過(guò)這一反饋來(lái)更新函數(shù)Q（s，a），并根據(jù)更新后的函數(shù)Q（s，a）決策下一個(gè)配載動(dòng)作，這就是增強(qiáng)學(xué)習(xí)的迭代過(guò)程。配載智能體通過(guò)不斷地試錯(cuò)，從中吸取經(jīng)驗(yàn)，逐漸學(xué)會(huì)在特定狀態(tài)下如何配載才能獲得最大回報(bào)值，最終使配載問(wèn)題的評(píng)價(jià)迭代收斂到最優(yōu)。

3.2 集裝箱船舶配載問(wèn)題的馬爾可夫決策過(guò)程

3.2.1 馬爾可夫決策過(guò)程概述

馬爾可夫決策過(guò)程可表述為：在系統(tǒng)處于某個(gè)狀態(tài)的情況下，決策者的決策決定其所采取的動(dòng)作，該動(dòng)作決定系統(tǒng)獲得的回報(bào)值和下一時(shí)刻系統(tǒng)將達(dá)到的狀態(tài)。馬爾可夫決策過(guò)程的數(shù)學(xué)表達(dá)式為

馬爾可夫決策過(guò)程具有無(wú)后效性，即系統(tǒng)獲得的回報(bào)值以及系統(tǒng)從當(dāng)前狀態(tài)向下一狀態(tài)轉(zhuǎn)移的概率只取決于當(dāng)前狀態(tài)和動(dòng)作，而與歷史狀態(tài)和動(dòng)作無(wú)關(guān)。狀態(tài)轉(zhuǎn)移函數(shù)

注：s0一未配載集裝箱，船箱位為空，此時(shí)有多個(gè)動(dòng)作可以選擇，即將某個(gè)集裝箱配載到某個(gè)船箱位；s1（C1，L4）—當(dāng)前狀態(tài)為已配載1個(gè)集裝箱，即將集裝箱C1配載到船箱位L4；s2（C3，Ll∣s1（C1，L4））—當(dāng)前狀態(tài)為已配載2個(gè)集裝箱，即在給定狀態(tài)s1（C1，L4）下，將集裝箱C3配載到船箱位L1

3.2.3 配載動(dòng)作設(shè)計(jì)

在配載問(wèn)題中，動(dòng)作定義為集裝箱與船箱位的配對(duì)，即將某個(gè)集裝箱配載到某個(gè)船箱位。以圖2為例，若不考慮配載約束條件，配載狀態(tài)s0下可執(zhí)行的配載動(dòng)作有36種，即集裝箱與船箱位的配對(duì)方式有36種。

3.2.4 配載回報(bào)設(shè)計(jì)

集裝箱船舶配載問(wèn)題中的回報(bào)函數(shù)設(shè)計(jì)與各個(gè)目標(biāo)函數(shù)的權(quán)重以及約束條件有關(guān)。配載效果的評(píng)價(jià)指標(biāo)主要包括配載完成情況、翻箱情況、移機(jī)情況、重壓輕情況等。鑒于上述指標(biāo)在配載過(guò)程中的重要程度不同，設(shè)計(jì)回報(bào)函數(shù)時(shí)有不同的側(cè)重。

式（3）～（5）分別表示配載完成情況回報(bào)值、翻箱情況回報(bào)值和移機(jī)情況回報(bào)值。

3.2.5 配載值函數(shù)和動(dòng)作價(jià)值函數(shù)設(shè)計(jì)

設(shè)計(jì)配載值函數(shù)和動(dòng)作價(jià)值函數(shù)，即

式（10）表示所選取的在場(chǎng)箱的質(zhì)量；式（11）表示所選取的在場(chǎng)箱所在船箱位的層高；式（12）表示所采取的配載動(dòng)作中的集裝箱與其所在船箱位下方集裝箱的質(zhì)量差；式（13）表示所采取的配載動(dòng)作的潛力值，即在將該配載動(dòng)作作為本次配載策略的情況下，比該配載動(dòng)作中的集裝箱質(zhì)量輕的集裝箱數(shù)量與該集裝箱所在船箱位上方空余船箱位數(shù)量之差，也就是當(dāng)前配載動(dòng)作對(duì)該配載動(dòng)作中的船箱位上方集裝箱配載的影響情況；式（14）表示所采取的配載動(dòng)作產(chǎn)生的堆場(chǎng)翻箱量；式（15）表示所采取的配載動(dòng)作中的集裝箱的發(fā)箱順序與其左側(cè)集裝箱所

式（6）～（9）中： π為所選擇的配載策略；λ為下次配載對(duì)于當(dāng)前配載的影響因子；T（s∣s，a）為從配載狀態(tài)s采取配載動(dòng)作a最終到達(dá)配載狀態(tài)s的概率；R（s∣s，a）為從配載狀態(tài)s采取配載動(dòng)作a最終到達(dá)配載狀態(tài)，所獲得的回報(bào)值；v（s）為在配載狀態(tài)s下采取配載動(dòng)作a所獲得的期望回報(bào)值，即在該船箱位配載該集裝箱將給之后配載其他集裝箱帶來(lái)的回報(bào)值；Q（s，a）為在配載狀態(tài)s下采取配載動(dòng)作a所獲得的總回報(bào)值；V*（s）為在配載狀態(tài)s下可獲得的最大回報(bào)值；V*（s，a）為在配載狀態(tài)s下采取配載動(dòng)作a所獲得的最大回報(bào)值。

3.3 配載特征分析

為解決維度災(zāi)難問(wèn)題，本文用配載問(wèn)題的9個(gè)相關(guān)特征近似表示配載狀態(tài)。以下描述的特征均針對(duì)當(dāng)前配載狀態(tài)可能采取的配載動(dòng)作進(jìn)行說(shuō)明。假設(shè)每個(gè)配載動(dòng)作的特征向量為

屬區(qū)位的發(fā)箱順序差；式（16）表示所采取的配載動(dòng)作中的集裝箱的發(fā)箱順序與其下方集裝箱所屬區(qū)位的發(fā)箱順序差；式（17）表示所采取的配載動(dòng)作中的集裝箱是否從同區(qū)位發(fā)出；式（18）表示所采取的配載動(dòng)作中的集裝箱是否與其前一配載動(dòng)作中的集裝箱從同區(qū)位發(fā)出。

4 增強(qiáng)學(xué)習(xí)算法求解集裝箱船舶配載問(wèn)題的優(yōu)勢(shì)

（1）計(jì)算遷移 傳統(tǒng)智能算法聚焦于問(wèn)題的決策階段，需要花費(fèi)大量時(shí)間對(duì)問(wèn)題進(jìn)行求解計(jì)算。對(duì)于超大型集裝箱船舶而言，為獲得較好的配載結(jié)果，采用傳統(tǒng)智能算法通常要比人工配載花費(fèi)更多時(shí)間。與傳統(tǒng)智能算法不同的是，增強(qiáng)學(xué)習(xí)算法聚焦于問(wèn)題的學(xué)習(xí)階段，可以在任何時(shí)間段學(xué)習(xí)配載數(shù)據(jù)，從而將大量的計(jì)算遷移至學(xué)習(xí)階段，在決策階段則直接使用增強(qiáng)學(xué)習(xí)得到的參數(shù)集進(jìn)行求解；因此，增強(qiáng)學(xué)習(xí)算法的求解效率較高，通?？稍?s內(nèi)計(jì)算上千個(gè)集裝箱的配載結(jié)果。

（2）泛化能力強(qiáng) 傳統(tǒng)智能算法通常需要人工提煉各種配載規(guī)則并劃定問(wèn)題邊界，并在對(duì)各種規(guī)則和問(wèn)題模型化的基礎(chǔ)上求解；因此，傳統(tǒng)智能算法對(duì)規(guī)則和邊界以外的配載問(wèn)題往往難以取得較好的結(jié)果。增強(qiáng)學(xué)習(xí)算法則基于歷史數(shù)據(jù)學(xué)習(xí)各種配載情況，使得配載智能體能夠掌握隱藏在數(shù)據(jù)背后的規(guī)律，即使面對(duì)全新的配載樣本也具備較強(qiáng)的適應(yīng)能力。

5 結(jié)束語(yǔ)

本文采用增強(qiáng)學(xué)習(xí)算法求解集裝箱船舶配載問(wèn)題，其主要?jiǎng)?chuàng)新點(diǎn)如下。

（1）運(yùn)用機(jī)器學(xué)習(xí)的相關(guān)理論和方法求解規(guī)劃模型，將大量的計(jì)算遷移到模型訓(xùn)練學(xué)習(xí)階段，從而大幅提高決策階段的計(jì)算效率。

（2）將配載問(wèn)題的目標(biāo)和約束條件轉(zhuǎn)換為特征向量，使配載智能體通過(guò)增強(qiáng)學(xué)習(xí)從特征向量中自動(dòng)提取不同狀態(tài)下的配載策略，從而避免傳統(tǒng)啟發(fā)式算法下因人工設(shè)計(jì)啟發(fā)規(guī)則而造成的有偏估計(jì)。

（3）相關(guān)研究思路和方法對(duì)解決集裝箱碼頭場(chǎng)地計(jì)劃、場(chǎng)橋調(diào)度、智能收箱等問(wèn)題具有一定的借鑒意義。

參考文獻(xiàn)：

[14]衛(wèi)家駿.混合蟻群算法求解集裝箱箱位分配問(wèn)題[J].中國(guó)航海，2011，34（2）：96-100.