確定任務(wù)視角下集裝箱堆場箱位分配研究

鄭云峰,劉瑞麟,饒本順,周校彬,張國慶

(大連海事大學(xué) 航海學(xué)院,遼寧 大連 116026)

0 引 言

目前的國際貿(mào)易運(yùn)輸中,集裝箱運(yùn)輸雜貨已經(jīng)變得越來越主流。碼頭是運(yùn)輸過程中集裝箱交接的直接場所,其空間以及機(jī)械設(shè)備資源都非常有限,而集裝箱的運(yùn)量卻有增無減。因此,高效分配碼頭資源,提高碼頭前方堆場資源利用效率顯得尤為重要,也引起了業(yè)界的重視。已有關(guān)于集裝箱碼頭資源調(diào)度的研究,主要有堆場空間的分配和設(shè)備的調(diào)度2個方向,其中箱位分配和場橋調(diào)度是近年來學(xué)術(shù)界關(guān)注的熱點(diǎn)。基于此,筆者從堆場空間和設(shè)備調(diào)度2個角度出發(fā),研究箱位分配的問題。

關(guān)于集裝箱碼頭堆場箱位分配問題的研究,可以根據(jù)是否考慮堆場不確定因素分為2類。一些學(xué)者假設(shè)存取箱任務(wù)已知,將不確定問題確定化,對問題進(jìn)行簡化,比如:R.DEKKER等[1]對不同箱位堆存策略分別進(jìn)行了仿真試驗(yàn)分析,結(jié)果表明分類堆存方法明顯要優(yōu)于隨機(jī)堆存方法;范厚明等[2]采取分區(qū)域堆存原則,考慮多場橋之間相互影響及所需的安全距離,建立了整數(shù)規(guī)劃數(shù)學(xué)模型,得出給定批量任務(wù)的貝位方案;范厚明等[3]考慮多場橋作業(yè)的安全距離以及任務(wù)量均衡,構(gòu)建數(shù)學(xué)模型,求解貝位分配問題;倪敏敏等[4]提出一種動態(tài)的多場橋分區(qū)域堆存方案,彌補(bǔ)了上述文獻(xiàn)中為確保各場橋間的安全距離而帶來的不足和缺陷;張燦榮等[5]提出累加重量的思想,將一個堆垛的總重量描述為所有集裝箱重量的累加和,以最小翻箱量為目標(biāo),研究集裝箱的貝內(nèi)排箱問題;張煜等[6]在堆場堆存方案已知的基礎(chǔ)上,研究船上箱位分配問題,分析不同派送方案對配載結(jié)果造成的影響。

一些學(xué)者考慮了堆場的不確定因素,采用滾動周期的方法把不確定問題轉(zhuǎn)化一段時間內(nèi)的確定問題進(jìn)行建模求解,比如:K.H.KIM等[7]考慮集裝箱在場時間,采取滾動策略構(gòu)建混合整數(shù)規(guī)劃(MIP)模型,利用啟發(fā)式算法優(yōu)化求解模型;周鵬飛等[8]考慮離港箱交箱時間的隨機(jī)性,提出兩級調(diào)度策略,建立數(shù)學(xué)模型求解;周鵬飛等[9]針對集裝箱進(jìn)出港時刻不確定,構(gòu)建離港箱位隨機(jī)雙層規(guī)劃模型,優(yōu)化碼頭翻箱量以及場橋移動的行車成本;邵乾虔等[10]運(yùn)用馬爾科夫鏈預(yù)測處理隨機(jī)的交箱序列,解決交箱時間不確定問題,并在實(shí)際進(jìn)場順序和預(yù)測順序出現(xiàn)偏差時,對預(yù)測交箱順序進(jìn)行修正;劉嬋娟等[11]考慮出口箱進(jìn)場時間的不確定,將堆場的箱位分配問題分為兩階段,以集卡運(yùn)輸距離最小和貝內(nèi)翻箱量最少為目標(biāo),構(gòu)建多目標(biāo)規(guī)劃數(shù)學(xué)模型,使用Yalmip軟件求解;郝振勇等[12]基于集裝箱的重量等級建立數(shù)學(xué)模型,將隨機(jī)到達(dá)堆場的出口箱按重量等級在貝位內(nèi)分配具體箱位;武慧榮等[13]均衡碼頭各區(qū)域任務(wù)量,以滾動計(jì)劃為基礎(chǔ)構(gòu)建混合堆場箱區(qū)分配數(shù)學(xué)模型,提出一種模擬退火算法對問題進(jìn)行優(yōu)化求解。

總的來說,國內(nèi)外學(xué)者對箱位分配問題從多方面進(jìn)行研究,已經(jīng)取得了諸多成果,但仍存在一些不足。大多數(shù)學(xué)者將進(jìn)場箱的貝位選擇和貝內(nèi)排箱看作2個問題,只解決其中一個問題,而不考慮另一個;或者使用二階段求解的方法,依次解決2個問題,并未考慮2個環(huán)節(jié)之間的關(guān)系和影響。一旦確定貝位,箱位的位置就只能固定在很小的范圍內(nèi),導(dǎo)致結(jié)果容易過早收斂并陷入局部最優(yōu)。然而,箱位分配是一個連續(xù)的過程,各環(huán)節(jié)是互相耦合的。因此,筆者將考慮這個連續(xù)的過程,將2個階段看作一個整體。

又因?yàn)椴淮_定問題更加復(fù)雜,要考慮的因素更多,而筆者的研究側(cè)重于一種解決箱位分配問題的方法,是否考慮不確定性對結(jié)果影響不大。因此筆者假設(shè)存取箱任務(wù)已知,簡化求解模型。在此基礎(chǔ)上,采取分區(qū)域平衡策劃,考慮場橋移動成本和翻箱成本,構(gòu)建以場橋移動和翻箱總成本最小化為目標(biāo)的多目標(biāo)混合規(guī)劃數(shù)學(xué)模型,提出一種在整個區(qū)域內(nèi)搜索排箱位置的遺傳算法對模型進(jìn)行求解。最后通過仿真實(shí)驗(yàn),并與Yalmip求解工具箱進(jìn)行對比,驗(yàn)證算法的可行性和優(yōu)勢。

在理論上,提出了一種新的箱位分配思路,豐富了集裝箱堆場箱位分配的研究內(nèi)容,使研究成果更符合實(shí)際情況,具備實(shí)用性;實(shí)踐上,為碼頭實(shí)際工作提供一種可行參考對策。

1 問題描述

集裝箱堆場箱區(qū)的箱位一般用貝(bay)、列(row/slot)、層(tier)表示,進(jìn)場的每一個集裝箱都對應(yīng)唯一的位置表示,記作P(i,j,k)。每個集裝箱目的港、離港時間、重量等都不相同,按照這些屬性將集裝箱分組。筆者采用分區(qū)域堆放的方法,將堆場箱區(qū)劃分為不同區(qū)域,不同組的集裝箱儲存在相應(yīng)的區(qū)域內(nèi)。每個集裝箱進(jìn)場時,根據(jù)箱子的信息,將箱子分配在合適的位置。這樣做使得搜索貝的范圍擴(kuò)大了,不同于以往一旦確定了貝位,箱位分配只能在單個貝位中選擇,選擇范圍小,解的搜索限制在小范圍內(nèi)容易局部收斂,造成集裝箱堆積。分區(qū)域策劃下,箱位選擇的求解過程可以有更大的搜索范圍,更有利解的多樣性和接近最優(yōu)解。

堆場在完成堆存作業(yè)時,每個集裝箱所分配的箱位不同,如果相鄰的2個集裝箱在不同貝內(nèi),場橋就必須要移動貝位才能完成裝卸工作;如果某個集裝箱上已經(jīng)堆存了其他箱子,要先將其上面的箱子轉(zhuǎn)移到別的位置,再開始進(jìn)行作業(yè),這就出現(xiàn)了翻箱。所以如果集裝箱在堆存前沒有合理規(guī)劃,分配合適位置,就會導(dǎo)致很多不必要的場橋移動和翻箱,進(jìn)而影響碼頭的工作效率。而場橋移動和翻箱都有一定的成本,所以箱位分配問題就可以轉(zhuǎn)化為求解最小場橋移動和翻箱量總成本問題。

同時為簡化數(shù)學(xué)模型,筆者作出以下假設(shè):

1)進(jìn)場集裝箱規(guī)格一致,且采取先到先服務(wù)原則。

2)集裝箱按照目的港、離港時間、重量等屬性分組,同種集裝箱在同一區(qū)域。

3)集裝箱預(yù)約進(jìn)出場的時間、重量、目的港,堆場的剩余容量等信息已知。

4)按同尺寸、同目的港的出口箱堆存,貝內(nèi)不同重量級按重壓輕堆存。

2 模型建立

2.1 符號說明

I為堆場的貝數(shù);J為堆場的列數(shù);K為堆場的層數(shù);N為進(jìn)場箱的總數(shù);M為一個充分大的正數(shù)。

Cn為第n個進(jìn)場箱的屬性值,其值越大的集裝箱,越早離開碼頭、重量越大。Cn可根據(jù)目的港編號,交箱時間,重量計(jì)算得到,計(jì)算公式為:

Cn=k1×p+k2×t+k3×w+k4×n

(1)

式中:p為目的港編號。為便于裝船,同目的港的集裝箱需集中堆存,將作業(yè)區(qū)域按貝位劃分為不同子區(qū)域存放不同目的港的集裝箱。目的港編號越大,說明對應(yīng)子區(qū)域的集裝箱越早裝船。t為離港時間等級。將離港時間劃分為不同時段,每個時段對應(yīng)不同的時間等級。時間等級越大說明離港時間越早。w為集裝箱重量等級。將重量劃分為不同重量段,每個重量段對應(yīng)不同重量等級。重量等級越大說明集裝箱的重量越大。n為集裝箱進(jìn)場序列。k1,k2,k3,k4分別為根據(jù)堆場規(guī)模和實(shí)際需要確定的系數(shù),分別決定不同因素對屬性值的影響。

Ti為第i貝的初始箱量;Pnijk為箱位(i,j,k)是否堆存出口箱n,分別用0或1表示,即:

(2)

式中:i=1,2,…,I;j=1,2,…,J;k=1,2,…,K。

Rnijk為出口箱n堆存在箱位(i,j,k),對下方箱位(i,j,k-z)的出口箱m是否存在翻箱,分別用0或1表示,即:

(3)

式中:i=1,2,…,I;j=1,2,…,J;k=1,2,…,K;z=1,2,…,K-1。

圖1為一個貝內(nèi)的翻箱現(xiàn)象,方框內(nèi)的數(shù)字表示該位置所放置集裝箱的屬性值Cn,空值表示該位置空箱。按照堆存規(guī)則,屬性值越大越早離開碼頭,位置越靠上。若某箱下面存在屬性值更大的集裝箱,即Cn

圖1 翻箱現(xiàn)象 Fig. 1 Container turning phenomenon

2.2 堆場箱位分配模型

箱位分配的目標(biāo)有2個,分別是場橋移動的行車成本最小和作業(yè)的翻箱成本最小。其中場橋貝內(nèi)移動距離最短的目標(biāo)函數(shù)為:

(4)

翻箱量最小的目標(biāo)函數(shù)為:

(5)

綜合以上2個目標(biāo)函數(shù),構(gòu)建總成本目標(biāo)函數(shù):

Z=min(α×Z1+β×Z2)

(6)

式中:α為場橋跨越一個貝位的行車成本;β為一次翻箱的成本。

約束條件為:

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

模型中式(7)為一個集裝箱只能存放在一個箱位內(nèi);式(8)為一個箱位最多只能堆存一個集裝箱;式(9)為場橋的初始位置在貝位1;式(10)為分配在貝位i的集裝箱數(shù)量要小于堆場容量;式(11)為不能出現(xiàn)懸空堆放的情況;式(12)為上層晚于下層放箱, 其中M是一個足夠大的正數(shù)。

當(dāng)(i,j,k)存在集裝箱時:

(15)

此時上層箱進(jìn)場序列n,大于下層箱進(jìn)場序列n。即上層晚于下層放箱。

當(dāng)(i,j,k)沒有集裝箱時:

(16)

此時式(12)仍然成立,并符合實(shí)際情況。

式(13)表示(i,j,k)的集裝箱晚于(i,j,k-z)離港時,記一次翻箱, 其中M是一個足夠大的正數(shù)。

當(dāng)(i,j,k)存在集裝箱時:

(17)

此時,若上層箱屬性值小于下層箱屬性值,為使公式成立,必須使Rnijk=1,即發(fā)生翻箱;若上層箱屬性值大于下層箱屬性值,Rnijk=0也可使公式成立,即不翻箱。

當(dāng)(i,j,k)沒有集裝箱時:

(18)

此時式(13)仍然成立,并符合實(shí)際情況。

式(14)表示進(jìn)場箱需要堆存在所分配的箱區(qū),其中min和max分別為該箱區(qū)所容納集裝箱屬性的最小和最大值。

3 求解算法

在分區(qū)域平衡策劃下,根據(jù)已知的集裝箱到港信息表和堆場剩余容量信息,將不同屬性的集裝箱分配在堆場的不同區(qū)域,確定箱位分配方案。筆者設(shè)計(jì)一種遺傳算法優(yōu)化求解數(shù)學(xué)模型。

3.1 染色體編碼方式

筆者選用實(shí)數(shù)編碼,每條染色體為3行n列的矩陣,每行分別表示集裝箱分配的貝、列、層。染色體長度對應(yīng)進(jìn)場箱的數(shù)量,每一列的3個數(shù)即表示一個集裝箱在堆場中的坐標(biāo)。不同染色體對應(yīng)不同的堆存方案,如圖2。圖2中:10個集裝箱分配在4個貝位的箱區(qū)內(nèi),第1列表示第1個集裝箱分配的位置為(3,1,1)。

圖2 染色體示意Fig. 2 Chromosome diagram

3.2 種群初始化

在約束條件下,根據(jù)已知的集裝箱和堆場信息,得到每個集裝箱的屬性值,以及堆場的堆存情況,確定集裝箱的堆存區(qū)域,隨機(jī)生成初始種群。檢查生成的種群,對不滿足約束的染色體進(jìn)行修正,使其滿足約束。

3.3 適應(yīng)度函數(shù)與選擇操作

計(jì)算種群中每條染色體所對應(yīng)的適應(yīng)度函數(shù),得到相應(yīng)的目標(biāo)函數(shù)值。采用輪盤賭的選擇方法,由于目標(biāo)函數(shù)要求最小值,將目標(biāo)函數(shù)取倒數(shù),使種群中函數(shù)值較小的基因更具優(yōu)勢,更容易遺傳到下一代,從而實(shí)現(xiàn)種群的優(yōu)化。

3.4 交叉操作

交叉采取兩點(diǎn)交叉的方法。如圖3,首先在2個父代個體確定交叉位置,之后將2個父代的前半段和后半段進(jìn)行交叉遺傳給2個子代,得到新的子代個體。最后檢查子代個體的染色體,修正不滿足約束的子代染色體。

圖3 交叉操作Fig. 3 Cross operation

3.5 變異操作

變異操作采用單點(diǎn)變異的方式。如圖4,首先在父代個體上確定變異點(diǎn),根據(jù)約束條件以及該變異位置所在貝的堆存情況確定變異范圍,進(jìn)行基因變異,使得該位置的集裝箱的坐標(biāo)發(fā)生變化。最后檢驗(yàn)子代個體的染色體,修正不滿足約束的子代染色體,使染色體滿足約束并遺傳到下一代。

圖4 變異操作Fig. 4 Mutation operation

3.6 終止規(guī)則

當(dāng)算法的遺傳操作達(dá)到設(shè)定的最大迭代次數(shù)時,算法結(jié)束,此時得到的排箱方案即為最佳方案,對應(yīng)的函數(shù)值即為最優(yōu)值。算法流程如圖5。

圖5 算法流程Fig. 5 Algorithm flow

算法具體求解過程為:根據(jù)已有的集裝箱進(jìn)出場信息表和碼頭現(xiàn)有的堆存情況,確定染色體的編碼長度以及數(shù)學(xué)模型各個約束的范圍。設(shè)定所需的初始參數(shù),如迭代次數(shù),種群規(guī)模,交叉概率,變異概率等,隨機(jī)生成滿足約束的初始種群,開始算法的迭代,直到滿足終止規(guī)則,算法結(jié)束。

4 仿真實(shí)驗(yàn)

4.1 算例描述

仿真實(shí)驗(yàn)的堆場規(guī)模為20×4×4(貝×列×層),配備一臺場橋;考慮到堆存作業(yè)時會出現(xiàn)翻箱,每貝位最多堆存12個出口箱,即預(yù)留4個翻箱位。某時刻共有30個裝卸任務(wù),該任務(wù)的集裝箱的到港信息已知,如表1。其中交箱時間等級越大意味著越早交箱,重量等級越大意味著重量越大。各貝位的堆存情況和根據(jù)區(qū)域策略相對應(yīng)的目的港已知,如表2。根據(jù)場橋的技術(shù)參數(shù)和港口規(guī)范,經(jīng)計(jì)算得場橋移動一個貝位成本是0.56元,翻箱一次成本是4.47元。

表1 出口箱的目的港和重量級屬性信息Table 1 Destination port and weight attribute information of export box

表2 各貝位初始箱量和對應(yīng)目的港Table 2 Initial container quantity of each bay and corresponding destination port

根據(jù)堆場規(guī)模,并結(jié)合實(shí)際情況,假設(shè)箱位分配優(yōu)先考慮級分別是:目的港,離港時間,重量,進(jìn)場序列。Cn的計(jì)算系數(shù)k1,k2,k3,k4分別取100 000,10 000,1 000,1。

4.2 結(jié)果分析與比較

為了驗(yàn)證筆者算法的性能,在軟件MATLAB R2016b中完成代碼的編寫,設(shè)定迭代次數(shù)為400,種群規(guī)模為100,交叉概率為0.6,變異概率為0.001。對該算例求解可知,隨著算法不斷地迭代,各代種群的目標(biāo)函數(shù)和相應(yīng)翻箱量變化情況如圖6。

圖6 結(jié)果收斂Fig. 6 Result convergence

在圖6中:算法迭代到140代,目標(biāo)函數(shù)收斂于59.92。此時翻箱量為0,成本只有場橋移動的費(fèi)用,即為59.92元,目標(biāo)函數(shù)值最小,對應(yīng)的排箱方案即為最優(yōu)方案。

具體的集裝箱堆存方案如表3,每一行分別表示一個集裝箱被分配貝列層的位置坐標(biāo)以及其所具有的屬性值。

表3 分配實(shí)驗(yàn)結(jié)果Table 3 Results of distribution experimental

根據(jù)k1,k2,k3,k4的取值情況,屬性值Cn第1位數(shù)字表示目的港,第2位數(shù)字表示離港時間等級,第3位數(shù)字表示重量等級,后3位數(shù)字表示進(jìn)場序列。

從表3可以看出,目的港不同,即Cn第1位數(shù)字不同的集裝箱,被分配在不同的子區(qū)域:目的港為1的集裝箱{2,3,5,8,10,12,13,14,15,16,17,18,19,23,27,28,30}被分配在1～9貝;目的港為2的集裝箱{1,4,6,11,20,24,25,26,29}被分配在10～15貝;目的港為3的集裝箱{7,9,21,22}被分配在16～20貝。符合分區(qū)域平衡策劃的堆存規(guī)則。

在同一堆棧,即貝列相同的集裝箱:{(1,11),(2,8,10,13),(3,28),(5,17),(18,30),(19,23),(21,22),(25,29)},上層屬性值大于下層屬性值,滿足先交箱壓后交箱,重箱壓輕箱策略堆存。

同時每個集裝箱貝列層坐標(biāo)均不同,不存在一個箱位存放多個箱子的情況;所有集裝箱都在第一層,或者下層存在集裝箱,沒有懸空放箱的現(xiàn)象。滿足約束條件。以上說明了筆者算法解決箱位分配問題的有效性,并且適應(yīng)實(shí)際情況。

筆者針對不同規(guī)模的算例進(jìn)行仿真,將仿真優(yōu)化的結(jié)果與Yalmip求解結(jié)果作對比,對比結(jié)果如表4。仿真實(shí)驗(yàn)使用的遺傳算法屬于啟發(fā)式算法,所求解是一個近似值,因此實(shí)驗(yàn)結(jié)果使用5次實(shí)驗(yàn)的平均值。

表4 對比實(shí)驗(yàn)結(jié)果Table 4 Results of comparative experiment

從表4中可以看出,Yalmip軟件求解小、中、大規(guī)模問題都可獲得最優(yōu)解,但大規(guī)模的場景案例求解時間較長,且無法求解超大規(guī)模算例。筆者設(shè)計(jì)的算法在小規(guī)模場景得到的解和Yalmip軟件的結(jié)果一致;中規(guī)模場景得到的解逼近Yalmip所求解,開始出現(xiàn)小的求解誤差,并且實(shí)驗(yàn)規(guī)模越大求解誤差越大;對于大規(guī)模場景求解的時間遠(yuǎn)小于Yalmip,所得解產(chǎn)生的誤差依然在可接受范圍內(nèi);甚至可以解決Yalmip不能解決的超大規(guī)模問題。這是因?yàn)殡S著實(shí)驗(yàn)規(guī)模的擴(kuò)大,所需的求解時間在所難免會變長。筆者提出的算法在整個群體中搜索可行解,可以同時比較多個個體的性能,有很好的并行性,減少了不必要的計(jì)算,節(jié)約了迭代時間。在任何規(guī)模的場景下,能夠在可接受時間內(nèi)求得最優(yōu)解或者近優(yōu)解,說明筆者算法在求解箱位分配問題具有優(yōu)越和顯著的性能。

5 結(jié) 語

針對確定任務(wù)視角下的單場橋堆場的箱位分配問題,使用分區(qū)域堆存的策略,綜合考慮場橋行車成本和翻箱成本,構(gòu)建針對此問題的整數(shù)規(guī)劃數(shù)學(xué)模型,提出一種區(qū)別于二階段法的遺傳算法,不必先確定貝位,再貝內(nèi)排箱,與堆場的實(shí)際作業(yè)的情況更相符。仿真實(shí)驗(yàn)結(jié)果表明:使用的分區(qū)域堆存策略能夠有效地解決箱位分配問題;提出的算法可以有效減少場橋在作業(yè)過程中的移動距離和翻箱量,減少不必要的裝卸成本,從而提升碼頭堆場的工作效率;由于數(shù)學(xué)規(guī)劃的求解效率會隨著規(guī)模增大而快速衰減,對不同規(guī)模案例,將文中算法與傳統(tǒng)求解軟件Yalmip的求解結(jié)果相比較,可知筆者提出的算法對大、中規(guī)模模型的求解效率更具有優(yōu)勢。算法具備一定的理論意義,可以應(yīng)用于堆場作業(yè)時的箱位堆存問題,對實(shí)際操作具備一定的借鑒意義。

因?yàn)楣P者只是考慮任務(wù)量已知的情況下的單場橋調(diào)度,實(shí)際到港信息會出現(xiàn)偏差,也可能是多場橋共同作業(yè)。未來可以考慮不確定問題下的排箱問題,以及考慮多場橋之前的互相影響。