李 俊， 張 煜， 計三有， 馬 杰

（1.武漢科技大學(xué) 汽車與交通工程學(xué)院，湖北 武漢430081；2.武漢理工大學(xué) 物流工程學(xué)院，湖北 武漢430063；3.武漢理工大學(xué) 航運(yùn)學(xué)院，湖北 武漢430063）

0 引言

內(nèi)河集裝箱班輪由于體型較小、容量有限，船舶穩(wěn)性對配載計劃十分敏感，且與班期相比船方往往更強(qiáng)調(diào)艙容利用率。同時，內(nèi)河集裝箱班輪運(yùn)輸中，海關(guān)抽檢可能導(dǎo)致外貿(mào)箱發(fā)生箱量變化，班輪航線配載決策需要不斷考慮箱量變化影響，是一個動態(tài)決策問題。

已有的集裝箱班輪航線配載決策理論大多研究海運(yùn)船舶，往往假設(shè)船舶在航線上各港口節(jié)點的作業(yè)集裝箱信息已知來制定航線配載方案，仍屬于靜態(tài)決策的范疇。這些學(xué)者的研究方法主要包括啟發(fā)式算法［1～3］、遺傳算 法［4～6］、多階段方法［7，8］、整數(shù)規(guī)劃［9］等。內(nèi)河集裝箱班輪與海運(yùn)船舶相比，一方面由于貨流不均衡性且船舶體型更小，船方往往更強(qiáng)調(diào)艙容利用率；另一方面班輪航線配載會受到集港過程中外貿(mào)箱箱量變化影響，已有的靜態(tài)決策方法配載效率退化明顯，難以滿足內(nèi)河集裝箱班輪航線動態(tài)配載決策需求。

為此，本文考慮內(nèi)河集裝箱班輪運(yùn)輸中外貿(mào)箱不確定箱量影響，研究不確定箱量下班輪航線動態(tài)配載決策方法。考慮海關(guān)抽檢導(dǎo)致外貿(mào)箱箱量變化這一隨機(jī)事件，基于隨機(jī)事件驅(qū)動的滾動調(diào)度策略，構(gòu)建班輪航線多港口多階段滾動調(diào)度的動態(tài)配載決策模型。同時引入大鄰域搜索思想，設(shè)計一種包含混合整數(shù)規(guī)劃模型、破壞器與修復(fù)器的精確啟發(fā)式算法，實現(xiàn)港口多階段配載決策。最后基于真實場景的算例研究驗證模型與算法的有效性。

1 問題描述與建模分析

內(nèi)河集裝箱班輪航線運(yùn)輸中順序遍歷多個港口節(jié)點，航線上任意兩個港口節(jié)點（始發(fā)港o和目的港d）之間的集裝箱流向可用一個二元副a＝（o，d）唯一標(biāo)識，記為O-D副a流向。班輪航線配載決策中，上一港口節(jié)點輸出的配載計劃作為輸入來制定下一港口節(jié)點配載計劃。對于外貿(mào)箱而言，由于存在海關(guān)抽檢這一隨機(jī)事件，其集港過程中普遍存在集港后臨時抽檢、放關(guān)情況不理想、臨時加箱等不確定性因素干擾，使配載計劃隱含極強(qiáng)的脆性，如圖1所示。

圖1 內(nèi)河集裝箱班輪航線動態(tài)配載決策

具體來說，集裝箱集港后海關(guān)進(jìn)行臨時抽檢以及抽檢后放關(guān)情況不理想會使得原計劃中包含的集裝箱無法進(jìn)行裝船作業(yè)，從而導(dǎo)致裝船集裝箱箱量的減少；同時由于海關(guān)抽檢而錯過原航次的集裝箱進(jìn)行臨時裝船使得原計劃中未包含的集裝箱需要進(jìn)行裝船作業(yè)，從而導(dǎo)致裝船集裝箱箱量的增加。由于內(nèi)河集裝箱班輪船體結(jié)構(gòu)的特殊性，實際箱信息的微小誤差都會使得當(dāng)前港口的預(yù)配與實配計劃發(fā)生失效，從而需要對原計劃進(jìn)行動態(tài)調(diào)整。不僅會增加港口的額外作業(yè)成本，也會對班輪運(yùn)輸?shù)慕?jīng)濟(jì)性和時效性產(chǎn)生不良影響。

綜上，內(nèi)河集裝箱班輪航線配載決策中，對于外貿(mào)箱而言，需考慮海關(guān)抽檢導(dǎo)致箱量變化對其影響。在滿足船舶航行安全性前提下，制定出滿足航線各港口節(jié)點之間運(yùn)輸需求的配載計劃。同時考慮到內(nèi)河班輪運(yùn)輸?shù)莫?dú)特性和經(jīng)濟(jì)性，以最小化航線班輪堆棧占用數(shù)量為目標(biāo)，實現(xiàn)被占用堆棧的高效利用，保證船舶的艙容利用率。

2 模型構(gòu)建

2.1 假設(shè)條件

針對內(nèi)河集裝箱班輪航線運(yùn)輸中外貿(mào)箱集港特點，考慮現(xiàn)實約束，做出以下假設(shè)：

（1）考慮同一尺寸的普通箱；

（2）集裝箱集港后存在臨時抽檢以及抽檢后放關(guān)情況不理想；

（3）由于臨時抽檢而錯過原航次的集裝箱需要進(jìn)行臨時裝船。

2.2 模型建立

為了方便建模，將內(nèi)河集裝箱班輪貝位內(nèi)堆棧按前半部、后半部、左半部、右半部分成不同的堆棧集合，如圖2所示。

圖2 內(nèi)河集裝箱班輪結(jié)構(gòu)

（1）集合

P：航線港口集合；Q（p）：當(dāng)前港口p的O-D副集合，Q（p）＝Qb∪Qs（p），?p∈P；Qb（p）：途徑當(dāng)前港口p的O-D副集合，Qb（p）＝｛a｜o，p，d∈P，o?p?d，a＝（o，d）｝；Qs（P）：當(dāng)前港口p始發(fā)的O-D副集合，Qs（p）＝｛a｜o，p，d∈P，o＝p?d，a＝（o，d）｝；G：集裝箱重量等級集合，分為輕、中、重三個等級，即G＝｛1，2，3｝；J：班輪所有堆棧集合，從船頭到船尾、從左到右依次對堆棧進(jìn)行編號得到堆棧集合，J＝JF∪JA＝JL∪JR；JF：班輪前半部堆棧集合；JA：班輪后半部堆棧集合；JL：班輪左半部堆棧集合；JR：班輪右半部堆棧集合；NTp：當(dāng)前港口p的階段數(shù)集合，NTp＝｛t｜0≤t≤Tp｝。

（2）參數(shù)

Tp：當(dāng)前港口p截港時的最后階段；Ntg（a）：t階段，從當(dāng)前港口p流向后續(xù)港口d的重量等級為g的待裝船集裝箱箱量（TEU），?t∈NTp，a＝（o，d）∈Qs（p），g∈G；（a）：t階段，由于海關(guān)抽檢導(dǎo)致的從當(dāng)前港口p流向后續(xù)港口d的重量等級為g的增加箱量（TEU），?t∈NTp-｛0｝，a＝（o，d）∈Qs（p），g∈G；（a）：t階段，由于海關(guān)抽檢導(dǎo)致的從當(dāng)前港口p流向后續(xù)港口d的重量等級為g的減少箱量（TEU），?t∈NTp-｛0｝，a＝（o，d）∈Qs（p），g∈G；wg：重量等級為g的集裝箱平均重量（ton），g∈G；ΔLG：班輪允許的最大縱向重量差（ton）；ΔCG：班輪允許的最大橫向重量差（ton）；STj：堆棧j的最大箱位容量（TEU），?j∈J；SWj：堆棧j的最大載重量（ton），?j∈J；L：一個大數(shù)。

（3）變量

xtjg（a）：t階段，堆棧j內(nèi)a流向下重量等級為g的集裝箱箱量（TEU），?t∈NTp，g∈G，j∈J，a∈Q（p），p∈P；ytj（a）：0-1變量。t階段，若班輪堆棧j被a流向下的集裝箱占用則為1；否則為0，?t∈NTp，j∈J，a∈Q（p），p∈P。

（4）模型

針對內(nèi)河集裝箱班輪運(yùn)輸中外貿(mào)箱箱量變化特點，采用基于隨機(jī)事件驅(qū)動的滾動調(diào)度策略來實現(xiàn)班輪航線動態(tài)配載決策?？紤]船舶的艙容利用率，以最小化班輪堆棧占用數(shù)量為目標(biāo)，實現(xiàn)被占用堆?？臻g的高效利用，保證班輪航線運(yùn)輸?shù)慕?jīng)濟(jì)性。對于航線上任意港口的配載決策而言，利用多階段決策的無后效性，針對海關(guān)抽檢導(dǎo)致外貿(mào)箱箱量變化這一隨機(jī)事件，基于隨機(jī)事件將當(dāng)前港口的配載決策劃分為多個階段，每個隨機(jī)事件驅(qū)動一個階段，保證各階段最優(yōu)來實現(xiàn)整體最優(yōu)。基于隨機(jī)事件驅(qū)動的班輪航線多港口多階段滾動調(diào)度策略如圖3所示。圖中，初始狀態(tài)下階段數(shù)t＝0，當(dāng)海關(guān)抽檢導(dǎo)致箱量發(fā)生變化時，更新階段數(shù)t＝t+1，依次類推，當(dāng)前港口p截港時記錄下最后階段Tp。構(gòu)建當(dāng)前港口p任意階段t的配載決策模型（Stowage Planning Model），記為SPM（t），?t∈NTp-｛0｝，p∈P-｛1｝：

圖3 內(nèi)河集裝箱班輪航線多港口多階段滾動調(diào)度策略

式（1）～式（2）為目標(biāo)函數(shù)，其中式（1）表示最小化當(dāng)前港口任意階段的班輪堆棧占用數(shù)量，實現(xiàn)航線班輪堆棧占用數(shù)量最小，保證被占用堆棧的高效利用；式（2）表示最小化當(dāng)前港口相鄰階段之間配載計劃偏差，保證配載計劃的魯棒性。式（3）～式（14）為約束條件。其中式（3）表示當(dāng)前港口任意階段集裝箱裝船約束；式（4）表示當(dāng)前港口任意階段的集裝箱流平衡約束；式（5）表示到達(dá)當(dāng)前港口時已裝船集裝箱箱位固定約束；式（6）保證當(dāng)前港口任意O-D階段班輪航線上任意副流向下的集裝箱至少占用一個堆棧；式（7）保證當(dāng)前港口任意階段班輪任意堆棧至多被一種O-D副流向下的集裝箱占用，避免出現(xiàn)為了卸載下方集裝箱，而需要暫時卸下再重新裝船的阻塞箱；式（8）定義決策變量xtjg（a）與ytj（a）之間的關(guān)系：若xtjg（a）＞0，則說明當(dāng)前港口t階段堆棧j內(nèi)堆放有a流向下的集裝箱，此時ytj（a）＝1；若xtjg（a）＝0，則說明當(dāng)前港口t階段堆棧j內(nèi)沒有堆放a流向下的集裝箱，此時ytj＝0；式（9）保證當(dāng)前港口任意階段班輪任意堆棧的載箱量滿足容量約束；式（10）保證當(dāng)前港口任意階段班輪任意堆棧的載重量滿足約束；式（11）保證當(dāng)前港口任意階段班輪滿足縱向重量差約束；式（12）保證當(dāng)前港口任意階段班輪滿足橫向重量差約束；式（13）和（14）定義決策變量的取值范圍。

由于不存在上一階段，去除上述子目標(biāo)（2）和約束（4）可得到當(dāng)前港口p初始階段t＝0的配載決策模型SPM（0）如下：（SPM（0））｛f1（0）＝y(tǒng)oj（a）：（3），（5）～（14）｝。

2.3 下界值模型

對于優(yōu)化目標(biāo)f1（t）而言，直接基于當(dāng)前港口截港時最后階段t＝Tp的集裝箱信息進(jìn)行配載決策，不考慮當(dāng)前港口各階段配載計劃之間的差異性，即不考慮配載計劃的魯棒性，可得到原問題中優(yōu)化目標(biāo)f1（t）的下界值模型（Low Bound Model 1，LBM1）。當(dāng)前港口p截港后所有待裝船集裝箱的箱量等信息均變?yōu)橐阎?，即NTpg（a）已知。此時，將約束式（4）修改為：

同樣地，對于優(yōu)化目標(biāo)f2（t）而言，不考慮優(yōu)化目標(biāo)f1（t）影響，直接對其進(jìn)行單獨(dú)優(yōu)化，可得到其下界值模型（Low Bound Model 2，LBM2）：

上述模型LBM1與LBM2分別用來確定模型SPM中兩個優(yōu)化目標(biāo)f1（t）和f2（t）的下界值，進(jìn)行后續(xù)模型及算法求解性能分析。

3 算法設(shè)計

精確啟發(fā)式算法（Matheuristic Algorithm，MA）是將數(shù)學(xué)規(guī)劃融入到啟發(fā)式架構(gòu)中的一種算法。已有船舶航線配載相關(guān)研究中，僅文獻(xiàn)［10］針對海運(yùn)集裝箱船舶的全航線主貝計劃設(shè)計了名為兩階段漸進(jìn)隨機(jī)修復(fù)進(jìn)程（Two-level progressive Random Fixing Procedure）的混合整數(shù)規(guī)劃啟發(fā)式（Mixed Integer Programming Heuristic）方法，通過對模型中變量的松弛與修復(fù)來分階段實現(xiàn)求解。本文引入大鄰域搜索思想，設(shè)計一種包含混合整數(shù)規(guī)劃模型、破壞器與修復(fù)器的精確啟發(fā)式算法，來實現(xiàn)內(nèi)河集裝箱班輪航線運(yùn)輸中當(dāng)前港口多階段配載決策。算法主要思路如下：

Step 1初始解生成。當(dāng)前港口初始階段t＝0時，求解模型SPM（0）得到當(dāng)前港口的初始配載方案；

Step 2階段數(shù)更新。當(dāng)海關(guān)抽檢導(dǎo)致外貿(mào)箱箱量發(fā)生變化時，更新當(dāng)前港口階段數(shù)t＝t+1；

Step 3破壞器設(shè)計。當(dāng)前階段t（t＞0）下，將當(dāng)前港口始發(fā)的所有O-D副流向按集裝箱箱量是否發(fā)生變化，分為兩部分。其中未發(fā)生箱量變化的O-D副流向集合記為A0（t），發(fā)生箱量變化的記為A1（t）。設(shè)計兩種不同的破壞策略，對上一階段的配載計劃進(jìn)行破壞，將部分集裝箱取出后重新配載，實現(xiàn)對初始解鄰域結(jié)構(gòu)的搜索：

（1）隨機(jī)破壞（Random Destruction）。從集合A0（t）和A1（t）內(nèi)隨機(jī)選擇集裝箱進(jìn)行破壞，其中對于集合A0（t）內(nèi)任意O-D副流向a′而言，假設(shè)其對應(yīng)集裝箱占用堆棧數(shù)量為O（a′），則隨機(jī)生成［0，O（a′）］范圍內(nèi)整數(shù)，實現(xiàn)對應(yīng)數(shù)量堆棧內(nèi)集裝箱破壞，取出的集裝箱需重新配載。對于集合A1（t）內(nèi)任意O-D副流向a″而言，假設(shè)其對應(yīng)集裝箱占用堆棧數(shù)量為O（a″），若箱量變化為正數(shù)（即箱量增加），則隨機(jī)生成［0，O（a″）］范圍內(nèi)整數(shù)，實現(xiàn)對應(yīng)數(shù)量堆棧內(nèi)集裝箱破壞，取出的集裝箱與增加的集裝箱需重新配載；若箱量變化為負(fù)數(shù)（即箱量減少），則隨機(jī)生成［1，O（a″）］范圍內(nèi)整數(shù)k，若k個堆棧內(nèi)任意重量等級g下的集裝箱箱量之和ng（k）滿足gn（k）≥（a″），則對該k個堆棧內(nèi)集裝箱進(jìn)行破壞，若ng（k）不滿足ng（k）≥（a″），則重新生成k至滿足條件，取出的集裝箱減去減少箱量后需重新配載；

（2）固定破壞（Fixed Destruction）。集合A0（t）內(nèi)集裝箱保留上一階段的配載結(jié)果，對集合A1（t）內(nèi)所有O-D副流向集裝箱進(jìn)行破壞，取出的集裝箱需重新配載；

Step 4修復(fù)器設(shè)計。當(dāng)前階段t（t＞0）下，對破壞器取出的集裝箱進(jìn)行重新配載，實現(xiàn)配載計劃的修復(fù)。針對破壞后取出的集裝箱，基于下界模型LBM2求解實現(xiàn)重新配載。由于初始階段下已對原問題中優(yōu)化目標(biāo)f1（t）即當(dāng)前港口的班輪堆棧占用數(shù)量進(jìn)行優(yōu)化，在下一階段中僅考慮對優(yōu)化目標(biāo)f2（t）進(jìn)行優(yōu)化，保證與上一階段配載計劃中堆棧占用結(jié)果的偏差最小，亦可保證對當(dāng)前階段下班輪堆棧占用數(shù)量的優(yōu)化。以此類推，可以滾動實現(xiàn)當(dāng)前港口后續(xù)所有階段配載計劃的求解；

Step 5完成模型LBM2求解，輸出當(dāng)前港口t（t＞0）階段下的配載方案；

Step 6重復(fù)上述Step 2～5，完成當(dāng)前港口多階段滾動配載決策。

圖4 精確啟發(fā)式算法設(shè)計

4 算例研究

4.1 算例設(shè)計

根據(jù)國家標(biāo)準(zhǔn)GB/T 19283-2010，以長江集裝箱班輪運(yùn)輸為例，選取三艘不同尺寸類型（小、中、大型）的集裝箱班輪進(jìn)行算例研究，班輪相關(guān)信息如表1所示。

表1 長江集裝箱班輪信息

為驗證不同模型的求解效果，基于長江集裝箱班輪實際運(yùn)輸場景設(shè)計一系列算例進(jìn)行研究。考慮4條包含不同港口數(shù)目的航線，見表2。每條航線中，考慮3種不同的班輪裝載率，見表3。其中，班輪裝載率是指班輪離港時所有裝船集裝箱總箱量與其總?cè)萘恐g的比率值，值越大表示班輪裝載集裝箱越多。采用諸如S1L1C45的方式來表示不同的算例，其中第一部分S1表示班輪船型，第二部分L1表示班輪航線，第三部分C45表示班輪裝載率。

表2 班輪航線設(shè)計

表3 班輪裝載率

4.2 算例求解

所有的數(shù)學(xué)模型SPM、LBM1以及LBM2均采用Gurobi 7.5.1求解。采用隨機(jī)破壞和固定破壞策略的精確啟發(fā)式算法（MA）分別記為MA_Random和MA_Fixed，基于Python 3.6編程實現(xiàn)。所有的算例均在4GB內(nèi)存筆記本電腦（Intel Core I7-5500U，2.40GHz）上運(yùn)行求解。每個算例中，航線各港口均考慮5個階段的箱量變化，各階段下不同副流向下集裝箱箱量可增可減且箱量變化隨機(jī)生成。為了保證模型的求解效率，將其單次求解時間限制設(shè)置為60秒。

4.2.1 多目標(biāo)優(yōu)化權(quán)重分析

由于模型SPM中含有兩個子目標(biāo)，引入權(quán)重系數(shù)λ1、λ2將其目標(biāo)函數(shù)轉(zhuǎn)化為：

為了確定合適的權(quán)重系數(shù)，選擇體型最大的班輪S3對應(yīng)算例設(shè)計多組對比試驗，結(jié)果如下表4所示。表中，f1表示航線班輪堆棧占用數(shù)量，對所有港口最后階段班輪堆棧占用數(shù)量求和得到，即（單位：個）；f2表示班輪航線配載計劃偏差之和，即f2＝｜（單位：個）；T表示每個算例的求解時間（單位：秒）。

表4 不同權(quán)重比率下求解結(jié)果

從表4中可以看出，不同權(quán)重系數(shù)λ1、λ2比率下，模型SPM對兩個子目標(biāo)的優(yōu)化程度差異不大，僅在求解時間方面存在一定差異性。綜合來看設(shè)置λ1：λ2＝1：10時，模型SPM優(yōu)化兩個子目標(biāo)時平均值均最小，且平均求解時間與最短平均時間的差異也較小。為此，后續(xù)模型SPM求解時，選擇設(shè)置λ1：λ2＝1：10。

4.2.2 模型與算法結(jié)果

由于算法MA_Random具有一定隨機(jī)性，每個算例連續(xù)優(yōu)化10次后取平均值。對于不同班輪而言，模型SPM與不同算法MA的求解結(jié)果如表5～7所示。表中，f1、f2、T含義與表4中一致；gap1和gap2分別表示模型與算法求解不同目標(biāo)與下界值 之 間 偏 差（單 位：%），其 中，gap1＝100×

表5 模型與不同算法求解結(jié)果-班輪S1

表6 模型與不同算法求解結(jié)果-班輪S2

表7 模型與不同算法求解結(jié)果-班輪S3

從表5中可以看出，對于小型班輪S1而言，由于考慮航線配載計劃的魯棒性，模型SPM、算法MA_Random與MA_Fixed求解得到的航線班輪堆棧占用數(shù)量與下界值之間的平均偏差較大。但從表6和表7中可以看出，隨著班輪體型的增大以及堆棧數(shù)量的增多，模型及算法得到的航線班輪堆棧占用數(shù)量與下界值之間的平均偏差逐漸減小至3%左右?？傮w來看，在優(yōu)化航線班輪堆棧占用數(shù)量方面，模型SPM、算法MA_Random與MA_Fixed三者之間差異不大。

從表5至表7中可以看出，由于采用下界模型LBM2作為修復(fù)器，算法MA_Random與MA_Fixed總能求得與下界值相同的航線配載計劃偏差之和，因而它們在魯棒性方面的表現(xiàn)要優(yōu)于模型SPM。同時在求解時間方面，算法MA_Random與MA_Fixed也較模型SPM更優(yōu)。兩種不同破壞策略下，算法MA_Random在求解時間方面表現(xiàn)略優(yōu)。

綜上，由于模型SPM、算法MA_Random與MA_Fixed考慮對班輪航線各港口各階段配載計劃之間偏差進(jìn)行優(yōu)化，其對應(yīng)航線班輪堆棧占用數(shù)量與下界值模型（LBM1）之間存在較大的偏差。但模型LBM1僅基于當(dāng)前港口最后階段的集裝箱信息進(jìn)行配載決策，其結(jié)果勢必會在較大程度上優(yōu)于上述兩者。同時，隨著船舶體型增大，模型SPM、算法MA_Random以及MA_Fixed對應(yīng)平均偏差逐步減少至合理范圍內(nèi)。對于班輪航線配載計劃偏差之和而言，模型SPM對應(yīng)結(jié)果在數(shù)量上與下界值模型（LBM2）之間差異很??；而算法MA_Random與MA_Fixed則表現(xiàn)更優(yōu)，總是可以得到與模型LBM2相同結(jié)果，說明模型SPM、算法MA_Random與MA_Fixed在配載計劃的魯棒性方面均表現(xiàn)較好。算例研究表明，模型SPM與算法MA可用來輔助實現(xiàn)不確定箱量下內(nèi)河集裝箱班輪航線動態(tài)配載決策，且后者表現(xiàn)更優(yōu)。兩種不同破壞策略下，算法MA_Random在求解時間方面略優(yōu)于算法MA_Fixed。

5 結(jié)論

本文針對內(nèi)河集裝箱班輪運(yùn)輸中外貿(mào)箱箱量變化特點研究班輪航線動態(tài)配載決策方法?；陔S機(jī)事件驅(qū)動的滾動調(diào)度策略，以最小化航線班輪堆棧占用數(shù)量為目標(biāo)，構(gòu)建班輪航線多港口多階段滾動調(diào)度的動態(tài)配載決策模型。同時，基于大鄰域搜索思想設(shè)計一種精確啟發(fā)式算法來實現(xiàn)港口的多階段滾動配載決策。算例研究發(fā)現(xiàn)，針對外貿(mào)箱箱量變化特點，模型SPM和算法MA可用來輔助實現(xiàn)內(nèi)河集裝箱班輪航線動態(tài)配載決策。算法MA較模型SPM而言表現(xiàn)更優(yōu)，且隨著船舶體型增大，模型與不同算法求解航線班輪堆棧占用數(shù)量結(jié)果與下界值之間偏差呈逐漸減小趨勢。對于算法MA而言，兩種不同破壞策略在求解質(zhì)量方面無差異，在求解時間方面算法MA_Random表現(xiàn)略優(yōu)。下一步研究中，將針對求解效率更高的動態(tài)配載決策算法進(jìn)行開發(fā)。