基于動(dòng)態(tài)學(xué)習(xí)的泊位調(diào)度方案優(yōu)化

王 軍，郭力銘，杜 劍，王美蓉

(大連海事大學(xué)交通運(yùn)輸工程學(xué)院，遼寧大連116026)

0 引言

為充分利用碼頭資源，保證船舶能夠順利靠泊，碼頭通常需要依據(jù)計(jì)劃期內(nèi)預(yù)計(jì)到港船舶的船型尺寸、到港時(shí)間、裝卸貨量，制定包括船舶靠泊位置、靠泊時(shí)間、分配岸橋數(shù)量的泊位調(diào)度方案.泊位調(diào)度方案的合理與否，對碼頭與船方均會產(chǎn)生影響.對碼頭而言，由于泊位與岸橋資源是有限的，泊位調(diào)度方案的不合理會造成嚴(yán)重的資源浪費(fèi)；對船方而言，泊位調(diào)度方案不合理會導(dǎo)致船舶裝卸時(shí)間的延長，甚至嚴(yán)重?cái)_亂后續(xù)船期計(jì)劃.對此，本文將對泊位調(diào)度方案優(yōu)化問題展開研究.

在優(yōu)化泊位調(diào)度方案時(shí)，碼頭需要根據(jù)在泊船舶的占用泊位情況及預(yù)計(jì)在泊時(shí)間，確定其他待泊船舶的靠泊位置與靠泊時(shí)間.在計(jì)算預(yù)計(jì)在泊時(shí)間時(shí)，曾慶成等[1]用船舶裝卸箱量與岸橋裝卸效率相除；Zhen等[2]考慮了航道中船舶流量的影響；常祎妹等[3]認(rèn)識到岸橋作業(yè)時(shí)存在相互干擾；Golias[4]和Han[5]假設(shè)在泊時(shí)間分布的概率密度已知.為減少在泊時(shí)間的計(jì)算偏差，Xu等[6]為靠泊船舶設(shè)置了緩沖時(shí)間，并提出了處理隨機(jī)干擾的響應(yīng)恢復(fù)策略；Karafa等[7]從歷史數(shù)據(jù)中挖掘船舶延誤概率，再基于此概率函數(shù)進(jìn)行在泊時(shí)間計(jì)算；Zhen[8]當(dāng)在泊時(shí)間分布已知時(shí)構(gòu)建了泊位分配的隨機(jī)優(yōu)化模型，未知時(shí)則構(gòu)建了魯棒優(yōu)化模型.然而，上述文獻(xiàn)中的在泊時(shí)間分布都是固定不變的，而實(shí)際中各種因素對在泊時(shí)間的影響程度卻是動(dòng)態(tài)變化的.如風(fēng)力通過影響岸橋吊具的搖擺幅度，海浪通過影響船舶的搖擺幅度，導(dǎo)致岸橋裝卸效率的降低.而不同季節(jié)的平均風(fēng)級與平級浪高存在明顯差異，所以對裝卸效率的影響程度并不相同.

本文設(shè)計(jì)了在泊時(shí)間計(jì)算函數(shù)的動(dòng)態(tài)學(xué)習(xí)方法，再基于所學(xué)習(xí)函數(shù)進(jìn)行泊位調(diào)度方案優(yōu)化.即利用泊位調(diào)度方案的實(shí)際執(zhí)行結(jié)果，借助神經(jīng)網(wǎng)絡(luò)方法對在泊時(shí)間計(jì)算函數(shù)進(jìn)行逐天修正，以實(shí)現(xiàn)計(jì)算函數(shù)隨環(huán)境的動(dòng)態(tài)更新.另外，本文設(shè)計(jì)了包含在泊時(shí)間動(dòng)態(tài)學(xué)習(xí)及泊位調(diào)度方案優(yōu)化的并行算法，前者為后者提供更新的在泊時(shí)間計(jì)算函數(shù)，后者的實(shí)際執(zhí)行結(jié)果為前者提供學(xué)習(xí)樣本.

1 問題描述

泊位調(diào)度方案優(yōu)化問題是個(gè)二維背包問題，泊位調(diào)度方案可以用二維圖表示，如圖1所示.圖1的橫軸為時(shí)間軸，縱軸為岸線軸；用矩形框表示到港船舶，矩形內(nèi)陰影正方形的個(gè)數(shù)為分配岸橋數(shù)量；矩形左下角的橫縱坐標(biāo)分別為船舶的靠泊時(shí)間、靠泊位置，矩形的長寬分別為船舶在泊時(shí)間、所占岸線長度.

在制定泊位調(diào)度方案時(shí)，同一時(shí)刻同一位置只能安排一艘船舶，同一時(shí)刻所有船舶所占岸線長度之和不能超過碼頭的岸線總長度.任意船舶的分配岸橋數(shù)量不能超過該船舶允許的岸橋數(shù)量區(qū)間，且所有船舶的分配岸橋數(shù)量不超過碼頭的岸橋總數(shù)量.為吸引船舶掛靠，當(dāng)碼頭的計(jì)劃離泊時(shí)間超過船舶的要求離泊時(shí)間，碼頭需向船舶支付延誤賠償.對此，雖然通過增加岸橋數(shù)量可以縮短在泊時(shí)間，但岸橋使用成本是隨之增加的.為了降低泊位調(diào)度方案的總成本，需要對上述兩種成本進(jìn)行權(quán)衡.

本文采用神經(jīng)網(wǎng)絡(luò)方法來擬合在泊時(shí)間計(jì)算函數(shù)，將船舶的靠泊時(shí)間、裝卸箱量、分配岸橋數(shù)量、岸橋裝卸效率、泊位水深、平均風(fēng)級及平均浪級作為輸入?yún)?shù)，實(shí)際在泊時(shí)間作為目標(biāo)參數(shù).通過不斷減小在泊時(shí)間的計(jì)算結(jié)果與目標(biāo)參數(shù)間偏差，幫助擬合高質(zhì)量的在泊時(shí)間計(jì)算函數(shù).進(jìn)一步地，借助泊位調(diào)度方案及其實(shí)際執(zhí)行結(jié)果對計(jì)算函數(shù)進(jìn)行逐天修正，可以實(shí)現(xiàn)計(jì)算函數(shù)隨環(huán)境的動(dòng)態(tài)更新.

圖1 泊位調(diào)度方案二維圖Fig.1 Two-dimensional chart of berth scheduling scheme

2 基于動(dòng)態(tài)學(xué)習(xí)的泊位調(diào)度方案優(yōu)化模型

2.1 研究假設(shè)

(1)以集裝箱碼頭的連續(xù)型泊位為研究對象.

(2)碼頭的岸線長度已知，前沿水深能滿足所有船舶的吃水要求.

(3)碼頭的岸橋總數(shù)量已知，每臺岸橋的裝卸效率已知，不考慮岸橋的移動(dòng)時(shí)間.

(4)船舶到港計(jì)劃已知，每艘到港船舶都必須被服務(wù)，且只服務(wù)1次.

(5)船舶到港后才被安排靠泊，每艘船舶靠泊后就不能移泊.

(6)任意兩艘靠泊船舶間要留有固定的安全距離.

(7)船舶裝卸箱量均以標(biāo)準(zhǔn)箱計(jì)數(shù)，不考慮因配積載問題產(chǎn)生的倒箱時(shí)間.

2.2 模型參數(shù)

S={1,…,i,…,I}——計(jì)劃期內(nèi)的到港船舶集合，I為到港船舶總數(shù)量，i為第i艘到港船舶；

Q={1,…,j,…,J}——碼頭的岸橋集合，J為岸橋總數(shù)量，j為第j臺岸橋；

T={1,…,t,…,N}——計(jì)劃期的時(shí)間段集合，N為時(shí)間段總數(shù)量，t為第t時(shí)間段；

li——船舶i的長度；

Wi——船舶i的裝卸箱量；

Ai——船舶i的預(yù)計(jì)到港時(shí)間；

di——船舶i的要求離泊時(shí)間；

q1i——船舶i允許的最小岸橋數(shù)量；

q2i——船舶i允許的最大岸橋數(shù)量；

L——碼頭的岸線總長度；

r——船舶間安全距離；

η——每臺岸橋的裝卸效率；

c2——每臺岸橋的單位時(shí)間使用成本；

c1i——船舶i未滿足要求離泊時(shí)間時(shí)，碼頭向船舶支付的單位時(shí)間賠償成本；

P——泊位調(diào)度方案的總成本；

f1i——神經(jīng)網(wǎng)絡(luò)訓(xùn)練前船舶i的計(jì)算在泊時(shí)間；

F()——神經(jīng)網(wǎng)絡(luò)訓(xùn)練后的在泊時(shí)間計(jì)算函數(shù)，括號內(nèi)是輸入?yún)?shù)；

f2i——神經(jīng)網(wǎng)絡(luò)訓(xùn)練后船舶i的計(jì)算在泊時(shí)間；

Di——神經(jīng)網(wǎng)絡(luò)訓(xùn)練后船舶i的計(jì)算離泊時(shí)間；

Qit——第t時(shí)間段內(nèi)船舶i的分配岸橋數(shù)量；

λi——船舶i靠泊位置的水深；

O1——計(jì)劃期內(nèi)平均風(fēng)級；

O2——計(jì)劃期內(nèi)平均浪級；

M——一個(gè)足夠大的數(shù).

決策變量：

Bi——船舶i的靠泊位置；

Hi——船舶i的靠泊時(shí)間；

Zitq——0-1變量，若第t時(shí)間段內(nèi)船舶i被岸橋q服務(wù)則為1，否則為0；

Xij——0-1變量，若船舶i早于船舶j停靠則為1，否則為0；

Yij——0-1變量，若船舶i停靠在船舶j左側(cè)則為1，否則為0.

2.3 模型構(gòu)建

式(1)為目標(biāo)函數(shù)，模型以最小化碼頭的延遲離港賠償與岸橋使用成本之和為目標(biāo).式(2)表示任意時(shí)間段內(nèi)船舶分配岸橋數(shù)量之和不超過碼頭的岸橋總數(shù)量；式(3)用于計(jì)算第t時(shí)間段內(nèi)船舶i的分配岸橋數(shù)量；式(4)要求船舶到港后才能被安排靠泊；式(5)根據(jù)船舶裝卸箱量及岸橋裝卸效率，計(jì)算訓(xùn)練前的船舶在泊時(shí)間；式(6)采用動(dòng)態(tài)學(xué)習(xí)后的計(jì)算函數(shù)，重新計(jì)算船舶在泊時(shí)間；式(7)用于計(jì)算船舶離泊時(shí)間；式(8)保證任意船舶的裝卸箱量都能得到滿足；式(9)約束任意船舶的離泊時(shí)間在計(jì)劃期內(nèi)；式(10)～式(14)用于約束岸線同一位置同一時(shí)間段內(nèi)只靠泊1艘船舶；式(15)保證任意船舶i的靠泊位置在岸線長度范圍內(nèi)；式(16)和式(17)保證船舶i的分配岸橋數(shù)量在其允許的岸橋數(shù)量區(qū)間內(nèi)；式(18)定義了0-1變量；式(19)定義了變量所屬集合.

3 算法設(shè)計(jì)

3.1 算法流程

本文設(shè)計(jì)了包含動(dòng)態(tài)學(xué)習(xí)過程的智能啟發(fā)式算法.算法分為2個(gè)獨(dú)立運(yùn)算部分：第1部分運(yùn)用粒子群算法進(jìn)行泊位調(diào)度方案優(yōu)化，第2部分運(yùn)用神經(jīng)網(wǎng)絡(luò)算法進(jìn)行在泊時(shí)間計(jì)算函數(shù)的動(dòng)態(tài)學(xué)習(xí).其中，第1部分是算法主體.計(jì)劃期開始前，將第2部分?jǐn)M合完畢的在泊時(shí)間計(jì)算函數(shù)提取至第1部分，進(jìn)行泊位調(diào)度方案優(yōu)化模型的求解；計(jì)劃期結(jié)束后，將泊位調(diào)度方案的實(shí)際執(zhí)行結(jié)果反饋至第2部分，作為學(xué)習(xí)樣本繼續(xù)對已有在泊時(shí)間計(jì)算函數(shù)進(jìn)行動(dòng)態(tài)修正.基于此并行運(yùn)算流程，泊位調(diào)度方案優(yōu)化模型的求解時(shí)間不會增加，但在泊時(shí)間的計(jì)算準(zhǔn)確性與調(diào)度方案的優(yōu)化效果卻在持續(xù)提升.具體的算法流程如圖2所示，圖2的左側(cè)為第1部分，右側(cè)為第2部分.

圖2 算法流程圖Fig.2 Algorithm flow chart

3.2 關(guān)鍵步驟

(1)泊位調(diào)度方案優(yōu)化的粒子群算法.

粒子群算法中，解方案采用表1的編碼方式.以船舶1為例做解釋：1號船舶在第10個(gè)時(shí)間段，?？吭诎毒€200單位長度處，被分配2臺岸橋.

表1 編碼方式示例Table 1 Example of encoding method

算法步驟如下：

Step1 從動(dòng)態(tài)學(xué)習(xí)部分中提取更新的在泊時(shí)間計(jì)算函數(shù)，輸入船舶到港計(jì)劃及碼頭相關(guān)信息.

Step2 設(shè)置并行解個(gè)數(shù)，并對初代解進(jìn)行隨機(jī)初始化.

Step3 計(jì)算每個(gè)解方案的評價(jià)值，如果解方案不滿足模型約束，將評價(jià)值賦值為無限大.

Step4 更新解方案的當(dāng)代最優(yōu)位置與歷史最優(yōu)位置.

Step5 計(jì)算解的改善方向與步長，并更新并行解中每個(gè)解方案的當(dāng)前位置.

Step6 判斷是否滿足算法的迭代終止條件，滿足則輸出最滿意解方案，否則返回Step3.

(2)船舶在泊時(shí)間的神經(jīng)網(wǎng)絡(luò)訓(xùn)練.

神經(jīng)網(wǎng)絡(luò)有8個(gè)輸入?yún)?shù)，需要在輸入層設(shè)置8個(gè)節(jié)點(diǎn).目標(biāo)參數(shù)為實(shí)際在泊時(shí)間，輸出層只設(shè)置1個(gè)節(jié)點(diǎn).為了提升神經(jīng)網(wǎng)絡(luò)擬合能力，增加了隱含層.神經(jīng)網(wǎng)絡(luò)訓(xùn)練步驟如下：

Step1 輸入1組學(xué)習(xí)樣本，從數(shù)據(jù)庫中提取輸入層、隱含層、輸出層的節(jié)點(diǎn)數(shù)、權(quán)值wij與閾值θ.

Step2 根據(jù)公式計(jì)算各神經(jīng)元的輸出.

Step3 計(jì)算輸出層的計(jì)算結(jié)果與目標(biāo)參數(shù)間偏差，判斷偏差是否符合要求，是則執(zhí)行Step5.

Step4 使用梯度下降法對權(quán)值與閾值進(jìn)行更新，再返回Step2.

Step5 將訓(xùn)練完畢的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)存入數(shù)據(jù)庫.

4 算例分析

4.1 在泊時(shí)間動(dòng)態(tài)學(xué)習(xí)有效性的分析

通過動(dòng)態(tài)學(xué)習(xí)過程中在泊時(shí)間計(jì)算偏差的變化情況，驗(yàn)證動(dòng)態(tài)學(xué)習(xí)可以提升在泊時(shí)間的計(jì)算準(zhǔn)確性.將2017年某碼頭的泊位調(diào)度方案與實(shí)際執(zhí)行結(jié)果按周分為52組，每組包括100個(gè)樣本.隨機(jī)抽取連續(xù)的6組樣本，第6組作為測試樣本，第1-3組、2-4組與3-5組依次作為學(xué)習(xí)樣本.假設(shè)訓(xùn)練前在泊時(shí)間服從正態(tài)分布.基于訓(xùn)練前計(jì)算函數(shù)，對第1-3組樣本進(jìn)行第1次動(dòng)態(tài)學(xué)習(xí)；再基于第1次更新的計(jì)算函數(shù)，對第2-4組樣本進(jìn)行第2次動(dòng)態(tài)學(xué)習(xí).依此類推，始終基于最新函數(shù)進(jìn)行動(dòng)態(tài)學(xué)習(xí)，以實(shí)現(xiàn)計(jì)算函數(shù)隨環(huán)境的動(dòng)態(tài)更新.

基于訓(xùn)練前計(jì)算函數(shù)，以及動(dòng)態(tài)學(xué)習(xí)后的3個(gè)計(jì)算函數(shù)，計(jì)算100個(gè)樣本的輸出結(jié)果與目標(biāo)參數(shù)間平均偏差，作為1次實(shí)驗(yàn).連續(xù)進(jìn)行10次實(shí)驗(yàn)，并繪制各次實(shí)驗(yàn)中4組平均偏差的柱形圖，平均偏差越小則計(jì)算越準(zhǔn)確.由圖3可知：各次實(shí)驗(yàn)中，動(dòng)態(tài)學(xué)習(xí)后的平均偏差有所下降，越后期更新的計(jì)算函數(shù)的平均偏差越小.可見，動(dòng)態(tài)學(xué)習(xí)過程是有效的.

4.2 泊位調(diào)度方案優(yōu)化效果的對比分析

碼頭岸線長度800 m，岸橋總數(shù)量6臺，岸橋作業(yè)效率35 TEU/h；岸橋使用成本300 USD/h，船舶延誤賠償20 000 USD/h；計(jì)劃期開始時(shí)間為2018年1月1日0點(diǎn)，共48 h；計(jì)劃期內(nèi)的船舶到港計(jì)劃如表2所示.

表2 船舶到港計(jì)劃Table 2 Vessels arrival plan

圖3 動(dòng)態(tài)學(xué)習(xí)中在泊時(shí)間計(jì)算的平均偏差Fig.3 The mean deviation of handling time calculation in dynamic learning

對上述52組樣本進(jìn)行動(dòng)態(tài)學(xué)習(xí)，得到最新的在泊時(shí)間計(jì)算函數(shù).基于最新計(jì)算函數(shù)制作推薦方案，簡稱為方案1；基于訓(xùn)練前計(jì)算函數(shù)制作對比方案，簡稱為方案2.將方案1繪制于圖4，方案2繪制于圖5.圖中的矩形框表示到港船舶，矩形左下角的橫縱坐標(biāo)分別為船舶靠泊時(shí)間、靠泊位置，矩形內(nèi)陰影正方形的個(gè)數(shù)為分配岸橋數(shù)量.將方案1與方案2的結(jié)果差值列于表3，可知：方案1和2存在較大差異，兩方案中7條船舶的平均在泊時(shí)間相差2.0 h，總成本相差71 511美元.由于訓(xùn)練前在港時(shí)間計(jì)算函數(shù)的準(zhǔn)確性有限，導(dǎo)致計(jì)算離泊時(shí)間、分配岸橋數(shù)量及方案總成本均不準(zhǔn)確.可見，動(dòng)態(tài)學(xué)習(xí)過程是必要的.

圖4 泊位調(diào)度方案1Fig.4 Berth scheduling scheme 1

圖5 泊位調(diào)度方案2Fig.5 Berth scheduling scheme 2

表3 方案1與方案2的結(jié)果差值Table 3 Difference in results between scheme 1 and scheme 2

由于方案2的計(jì)算準(zhǔn)確性有限，與方案1的結(jié)果差值不能真實(shí)地反映優(yōu)化效果.對此，基于最新的在泊時(shí)間計(jì)算函數(shù)，在不改變方案2的靠泊時(shí)間、靠泊位置及岸橋數(shù)量的前提下，對各船的在泊時(shí)間、離泊時(shí)間及方案總成本進(jìn)行重新評估，得到方案3.將方案2與方案3的結(jié)果差值列于表4，由表4可知：方案3中各船的在泊時(shí)間、離泊時(shí)間及方案總成本均在增加，說明訓(xùn)練前函數(shù)的計(jì)算結(jié)果偏小，這主要是因?yàn)槠湮纯紤]冬季風(fēng)高浪大對裝卸效率的影響；在泊時(shí)間的增加導(dǎo)致多條船舶不能按時(shí)離泊，造成了延誤賠償?shù)募眲≡黾?進(jìn)一步地對比方案優(yōu)化效果，將方案1與方案3的結(jié)果差值列于表5，由表5可知：方案1比方案3的平均在泊時(shí)間縮短2.4 h，成本降低11.1%，且兩方案的求解時(shí)間仍均小于1 min.可見，在求解時(shí)間不會增加的前提下，動(dòng)態(tài)學(xué)習(xí)可以提升泊位調(diào)度方案優(yōu)化效果.

表4 方案2與方案3的結(jié)果差值Table 4 Difference in results between scheme 2 and scheme 3

表5 方案1與方案3的結(jié)果差值Table 5 Difference in results between scheme 1 and scheme 3

5 結(jié)論

本文構(gòu)建了基于在泊時(shí)間動(dòng)態(tài)學(xué)習(xí)的泊位調(diào)度方案優(yōu)化模型，在提升在泊時(shí)間計(jì)算準(zhǔn)確性的基礎(chǔ)上，降低了方案總成本.設(shè)計(jì)了包含動(dòng)態(tài)學(xué)習(xí)過程的智能啟發(fā)式算法，在保證泊位調(diào)度方案優(yōu)化模型的求解時(shí)間不會增加的前提下，可以提升泊位調(diào)度方案的優(yōu)化效果.但考慮到動(dòng)態(tài)學(xué)習(xí)過程可能遭遇樣本數(shù)量少及質(zhì)量差的情況，后續(xù)研究會嘗試借助強(qiáng)化學(xué)習(xí)方法，對動(dòng)態(tài)學(xué)習(xí)過程的學(xué)習(xí)能力進(jìn)行增強(qiáng).