抵港和裝卸時間不確定情況下的離散泊位分配問題

謝 鑫，胡志華，2＊

（1.上海海事大學(xué) 物流研究中心，上海 201306；2.同濟大學(xué) 經(jīng)濟與管理學(xué)院，上海 200092）

近年來，吞吐量的快速增長和集裝箱船舶的大型化、高速化給集裝箱碼頭的生產(chǎn)作業(yè)帶來了巨大的壓力.集裝箱船舶在港裝卸作業(yè)量增加，而港口為了提供高質(zhì)量的服務(wù)，必須在承諾的時間內(nèi)完成船舶的裝卸作業(yè)任務(wù)，但是受泊位資源和裝卸資源的限制，時常會出現(xiàn)船舶滯港現(xiàn)象.為了避免這種情況發(fā)生，港口最合理的做法就是充分利用現(xiàn)有的資源，提高港口的泊位分配效率和裝卸效率.

眾多學(xué)者已經(jīng)利用數(shù)學(xué)規(guī)劃方法對港口資源的調(diào)度進行了研究分析［1－2］.采用先來先服務(wù)（FCFS）的分配策略，Lai和Shih［3］提出了一種針對泊位分配問題的啟發(fā)式算法，并利用其對不同分配標(biāo)準(zhǔn)下的分配方案進行了評估.Imai等［4］證明了在多用戶集裝箱碼頭系統(tǒng)中，不考慮FCFS原則可以獲得較短船舶停泊時間的分配方案以及更高的港口生產(chǎn)力，但是同時也會導(dǎo)致某些船舶等待時間過長，所以他們改進模型追求獲得更大的作業(yè)效率，同時最小化船舶等待時間.值得注意的是Imai等的研究建立在調(diào)度前所有船舶都已抵港的假設(shè)基礎(chǔ)上，但在實際情況中，船舶都是在調(diào)度開始后陸續(xù)到港，因此Imai等［5］隨后將原有的靜態(tài)模型發(fā)展到動態(tài)模型.Nishimura等［6］進一步擴展了動態(tài)模型，考慮了不同泊位水深的情形，并設(shè)計遺傳算法求解模型.Imai等［7］在原有模型的基礎(chǔ)上對不同服務(wù)優(yōu)先級船舶的泊位分配問題進行了研究，隨后又研究了嵌入式泊位的裝卸作業(yè)情形.

上述模型和方法大都是面向確定性環(huán)境，在這些文獻(xiàn)中認(rèn)為船舶抵港時間和裝卸時間是固定不變的并且根據(jù)這些確定參數(shù)制定泊位分配計劃.但是在港口的作業(yè)調(diào)度中由于存在多種不確定性，如船舶航速變化、天氣因素、岸橋機械故障、岸橋效率變化、人員安排變動等原因都會造成船舶抵港時間和裝卸時間在原定計劃時間上產(chǎn)生波動，如船舶一旦延遲抵港，則按原計劃分配的泊位就會產(chǎn)生閑置時間甚至被臨時分配給其他船只；而船舶的裝卸時間發(fā)生波動時，則會影響船舶的離港時間，繼而擾亂下一艘船舶的作業(yè)計劃，因此這使得確定性模型不能正確反映實際系統(tǒng)，甚至?xí)绊懽罱K的分配方案，所以通過確定性模型得出的分配決策過于理想化，不僅達(dá)不到優(yōu)化港口作業(yè)的目標(biāo)，甚至?xí)斐筛嗟乩速M，所以有必要加強面向隨機環(huán)境的泊位調(diào)度研究.Zhou等［8］利用模糊理論對泊位調(diào)度中的不確定因素進行了初步探索性研究.Moorthy等［9］基于序列對編碼的方法，采用項目評審技術(shù)對連續(xù)岸線的隨機泊位分配問題進行了求解.在國內(nèi)，周鵬飛等人［10］針對抵港時間和裝卸時間的隨機性，建立了隨機環(huán)境下的集裝箱碼頭泊位－岸橋分配模型，并設(shè)計了一種改進的遺傳算法.而杜玉泉以船舶達(dá)到時間具有隨機延誤和有計劃外船舶到港兩種不確定性，制定了原始的魯棒泊位分配方案.

上述有關(guān)不確定性環(huán)境下的泊位分配研究主要致力于構(gòu)建具有較強魯棒性的分配計劃，另外有一部分的文獻(xiàn)又從干擾管理的角度研究了不確定性環(huán)境的泊位調(diào)度問題［11－13］，但是少有文獻(xiàn)研究當(dāng)船舶抵港和裝卸時間發(fā)生不同程度波動時，對港口作業(yè)目標(biāo)的影響規(guī)律，所以本文針對抵港和裝卸時間波動這兩種不確定情況，研究它們在不同的波動幅度下對船舶總在港時間產(chǎn)生的影響規(guī)律.

1 問題描述

泊位調(diào)度分為離散泊位調(diào)度和連續(xù)泊位調(diào)度.連續(xù)泊位調(diào)度將整個碼頭岸線看作是連續(xù)的，只要有滿足到港船舶物理條件（水深和長度）限制的位置就可以進行停泊.而離散泊位調(diào)度是將碼頭岸線劃分為若干獨立的泊位來進行分配.本文的研究是基于離散泊位調(diào)度環(huán)境.

離散泊位調(diào)度指的是，在一條被分為I個泊位的岸線上，為每一條到港的船舶分配一個合適的停靠泊位和停靠時間［14］.一般制約泊位分配的因素主要有：1）船舶有關(guān)信息，如船期計劃、船長、噸位、裝卸量等.2）岸邊資源情況，如岸橋、集卡調(diào)度等.3）其他物理條件，如泊位長度、水深等.

可是港口運作中有許多不確定因素，按照其來源可以分為來自系統(tǒng)外的不確定性和正常生產(chǎn)中的不確定性兩類.

來自系統(tǒng)外的不確定性是指，碼頭生產(chǎn)受到來自整個運輸鏈上下環(huán)節(jié)的制約和影響，這些因素難以確定是動態(tài)變化的，另外船舶的航行速度也會動態(tài)變化，這些發(fā)生在港口系統(tǒng)外部的不確定因素直接導(dǎo)致了船舶抵港時間的波動.而正常生產(chǎn)中的不確定性表現(xiàn)在生產(chǎn)過程中由于人為操作或設(shè)備間等待、干擾而產(chǎn)生的作業(yè)效率和處理能力的不確定性.如：岸橋干擾、機械故障、人員安排變動.這些因素直接導(dǎo)致了船舶裝卸時間的波動.

圖1 抵港時間和裝卸時間偏差示意圖Fig.1 Schematic diagram of arrival and handling time deviation

船舶航速變化、天氣因素、岸橋機械故障、岸橋效率變化、人員安排變動等不確定因素，根據(jù)其不確定性的強度，使船舶的抵港和裝卸時間產(chǎn)生不同程度的波動，如圖1所示.根據(jù)波動程度的不同，必然會對原計劃產(chǎn)生不同的影響.在不同的波動幅度下到底會對港口的作業(yè)目標(biāo)（本文考慮最小化船舶總在港時間）產(chǎn)生怎樣的影響，接下來本文就分別用靜態(tài)數(shù)據(jù)和產(chǎn)生波動的數(shù)據(jù)計算船舶的總在港時間并進行比較.

2 動態(tài)泊位分配模型

在本文中泊位分配模型將基于以下前提：1）船舶到港時間作為隨機變量來考慮；2）船舶裝卸時間將根據(jù)泊位、岸橋等因素確定，屬于隨機變量；3）不考慮移泊情況，每個船舶只有一次靠泊機會；4）考慮船舶物理特性與水深對分配計劃的約束.5）船靠泊后立刻進行裝卸作業(yè)，不考慮等待岸橋時間.

2.1 模型

B，V，U為模型中考慮的泊位集、到港船舶集和船舶服務(wù)順序集，i＝（1，2，…，I）∈B，j＝（1，2，…，T）∈V，k＝（1，2，…，T）∈U.

當(dāng)船舶j在Aj時刻到達(dá)港口時，港口工作人員根據(jù)船舶的長度Lj和設(shè)計吃水深Dj選擇合適靠泊泊位i，即泊位i、長度Li和水深Di均大于Lj和Dj，如果沒有合適的泊位則船舶j在錨地等待.一旦有合適的泊位i分配給船舶j，則船舶靠泊，此時在船舶j前有k－1艘船進行了裝卸作業(yè)，船舶j在bijk時刻開始在泊位i第k個進行裝卸任務(wù)，經(jīng)過裝卸時間Cij后在時刻fijk結(jié)束作業(yè)，然后離港.以下為相關(guān)符號的定義：

M：大型常數(shù)；Aj：船j到港時間；Cij：船j在泊位i的裝卸作業(yè)時間；bijk：船j在泊位i第k個服務(wù)的開始裝卸作業(yè)時間；fijk：船j在泊位i第k個服務(wù)的結(jié)束作業(yè)時間；Di：泊位i的水深；Li：泊位i的長度；Dj：船j的設(shè)計吃水深；Lj：船j的長度.Xijk＝1，表示船j在泊位i第k個被服務(wù)；否則，Xijk＝0.Xvijk：當(dāng)船j在i泊位第k個被服務(wù)時的總在港時間；Xijk，bijk，Xvijk，fijk為決策變量.

數(shù)學(xué)模型：

該數(shù)學(xué)模型的優(yōu)化目標(biāo)是所有船舶總在港時間最小化.式（2）定義了Xvijk與bijk、Aj、Cij、Xijk之間的關(guān)系，表示船舶總在港時間等于船舶抵港到開始裝卸作業(yè)的時間與裝卸時間之和.約束（3）表示所有船舶有且只有一次靠泊機會.約束（4）保證泊位上同時停泊的船舶不超過1艘.約束（5）和（6）給出了泊位對于船舶長度和水深的約束條件.約束（7）保證當(dāng)Xijk＝0時，bijk＝0，否則bijk≥0.式（8）給出了船舶開始作業(yè)時間、裝卸時間和作業(yè)結(jié)束時間之間的關(guān)系.約束（9）保證船舶到港后才能被服務(wù).約束（10）保證在某一泊位被服務(wù)的船舶作業(yè)開始時間大于該泊位前一艘船的結(jié)束作業(yè)時間.式（11）聲明決策變量Xijk是0～1變量.

“互聯(lián)網(wǎng)+”教育深入融合的當(dāng)今時代，微課等形式作為新的教學(xué)模式在教學(xué)課堂中如火如荼進行著。為解決成人繼續(xù)教育學(xué)員的工學(xué)時間矛盾的突出問題，提高教學(xué)效果和學(xué)員的學(xué)習(xí)質(zhì)量為教學(xué)目標(biāo)，我們將微課理念融入繼續(xù)教育課程建設(shè)中，我們嘗試在“C語言程序設(shè)計”這門課的繼續(xù)教育中引入微課為基礎(chǔ)的翻轉(zhuǎn)課堂教學(xué)，探究其在“C語言程序設(shè)計”中的應(yīng)用效果。

由于式（2）是非線性的，為了方便該數(shù)學(xué)模型采用Cplex工具求解，這里將式（2）轉(zhuǎn)換為線性約束（12）：

2.2 抵港和裝卸時間的不確定性處理

2.2.1 集裝箱碼頭船舶到港規(guī)律 在集裝箱運輸出現(xiàn)之前的海上貨物運輸，主要是以散裝貨運輸為主，這種運輸模式下的船舶到港時間間隔分布規(guī)律基本是隨機的.國內(nèi)外學(xué)者通過大量到港船舶時間的數(shù)理統(tǒng)計的研究，通常認(rèn)為單位時間內(nèi)到港船舶數(shù)服從泊松分布，而到港時間間隔服從負(fù)指數(shù)分布.但是集裝箱運輸自出現(xiàn)開始得到快速發(fā)展，且主要是班輪化運輸，有固定的航線、船期、掛靠港口.這種運輸模式顯然與散裝貨運輸?shù)碾S機性是不同的，因此再用原來的計算方法就不是很合理.

根據(jù)張魯寧，王諾等［15］對集裝箱班輪到港規(guī)律的實證研究，認(rèn)為船舶的到港規(guī)律更符合愛爾朗分布.愛爾朗分布函數(shù)如式（12）所示.

其中，當(dāng)m＝1時，其分布就是負(fù)指數(shù)分布，不定期的雜貨船到港規(guī)律就服從該分布；當(dāng)m→＋∞，即集裝箱船舶到港規(guī)律在理想狀態(tài)下服從的分布.在本文中取m＝2，即到港時間間隔服從二階愛爾朗分布，得到式（13），其中1／λ為到港時間間隔的期望值.

2.2.2 船舶計劃抵港時間和計劃裝卸時間 本文設(shè)定第一艘船的到港時間為0∶00點，則后面的船舶到港時間可以根據(jù)到港時間間隔規(guī)律的分布，通過式Aj＋1＝Aj＋Tj＋1，j（其中Tj＋1，j為船舶到港時間間隔）隨機生成12艘船的計劃到港時間.船舶的計劃裝卸作業(yè)時間由U（1，3）＊ （船舶長度）Lj／40隨機生成.

2.2.3 抵港和裝卸時間的不確定性處理 由于船舶航速變化、天氣因素、岸橋機械故障、岸橋作業(yè)效率變化、人事安排變動等外部因素都會造成船舶抵港時間和裝卸時間在原有計劃時間上產(chǎn)生波動，因此要考慮這一部分對模型數(shù)據(jù)造成的影響.根據(jù)統(tǒng)計分析，船舶的實際抵港時間和裝卸時間與計劃時間之間的偏差可以認(rèn)為是服從正態(tài)分布的，偏差量為期望值為零的正態(tài)分布隨機變量，我們可以為偏差量設(shè)定不同的均方差來表示外界環(huán)境對于計劃時間產(chǎn)生的波動程度.所以本文偏差量服從正態(tài)分布N（0，σ2），根據(jù)波動程度的大小，在輕度波動下σ2在區(qū)間［1，2］上隨機生成，中度波動下在區(qū)間［2，3］上隨機生成，高度波動下在區(qū)間［3，4］上隨機生成（都服從均勻分布）.

3 算例

本文中選取了4個泊位和12艘船設(shè)計算例，以評價和測試建立的模型.泊位長度、水深以及船舶的長度、設(shè)計水深都是在一定的范圍內(nèi)服從均勻分布.泊位信息列于表1，船舶信息列于表2.

表1 泊位信息Tab.1 The information of berths

表2 船舶信息Tab.2 The information of vessels

首先隨機生成某一到港時間間隔下的船舶計劃抵港時間和計劃裝卸時間，得出計劃目標(biāo)值（船舶總在港時間）；然后在裝卸時間不變的情況下，對計劃抵港時間進行不同波動模式下的處理，即（實際抵港時間）＾Aj＝（計劃抵港時間）Aj＋（偏差量）α，為了使得到的數(shù)據(jù)更加穩(wěn)定，對目標(biāo)值生成多組數(shù)據(jù)，然后相加求平均值.圖2為不同時間間隔下，計劃目標(biāo)值和3種抵港時間波動模式下的目標(biāo)值.圖3為3種波動模式產(chǎn)生的目標(biāo)值與計劃值的偏差幅度.

圖2 不同抵港時間波動下船舶總在港時間Fig.2 The planned and actual target value under different degrees of arrival fluctuation

分析圖2，船舶的總在港時間隨著抵港時間間隔的擴大而下降，這是符合實際情況的，因為當(dāng)?shù)指蹠r間間隔擴大時，單位時間內(nèi)到港船舶減少，使現(xiàn)有的泊位資源和裝卸資源變得相對充裕，需要處理的信息也減少，加快了船舶的過關(guān)效率.結(jié)合圖3分析船舶總在港時間的波動范圍，可以看到當(dāng)平均間隔為2h 時目標(biāo)值分布在區(qū)間［208，225］之間，偏差幅度分別為2%、5%和2%，4h時目標(biāo)值分布在區(qū)間［152，167］之間，偏差幅度分別為1%、3%和8%，偏差比較小，但是當(dāng)平均間隔為3h時，目標(biāo)值分布在區(qū)間［156，194］之間，偏差幅度分別為20%、15%和8%，偏差表現(xiàn)得就比較明顯.

圖3 不同抵港時間波動下船舶總在港時間與計劃值的偏差幅度Fig.3 Deviation amplitude between the planned and actual target value under different degrees of arrival fluctuation

然后在船舶抵港時間不變的情況下，對裝卸時間進行波動的處理并計算目標(biāo)值，圖4為計劃目標(biāo)值和3種裝卸時間波動模式下的目標(biāo)值，圖5為3種波動模式下產(chǎn)生的目標(biāo)值與計劃值的偏差幅度.

圖4 不同裝卸時間波動下船舶總在港時間Fig.4 The planned and actual target value under different degrees of handling fluctuation

分析圖4和圖5，圖中呈現(xiàn)的規(guī)律與圖2和圖3相似，都表現(xiàn)為平均間隔為2h和4h時的偏差要小于平均間隔為3h時的偏差.但是對比圖3、圖5可以發(fā)現(xiàn)發(fā)生在岸橋上的波動產(chǎn)生的目標(biāo)值相較于計劃值的偏差要大于由于抵港時間波動所產(chǎn)生的偏差.如當(dāng)平均時間間隔為2h時，波動產(chǎn)生的目標(biāo)值與計劃值分布在區(qū)間［198，220］，偏差幅度分別為4%、7%和10%，要大于同一情況下由于抵港時間波動而產(chǎn)生的偏差幅度2%、5%和2%.另外觀察這兩張圖，可以發(fā)現(xiàn)一個有趣的地方，就是用考慮波動后的數(shù)據(jù)運用模型計算出來的目標(biāo)值相較于計劃值都有一定的改善，這說明采用靜態(tài)數(shù)據(jù)生成的泊位分配計劃就船舶總在港時間上來說在實際港口作業(yè)中往往不是最優(yōu)的，一旦發(fā)生波動，新的泊位分配方案可以獲得更優(yōu)的目標(biāo)值.因此如果決策者要為某段時間制定一個考核目標(biāo)，比如說總在港時間，如果根據(jù)靜態(tài)數(shù)據(jù)來制定的話是不合理的，而應(yīng)該在計劃值的基礎(chǔ)上提高考核要求.

圖5 不同裝卸時間波動下船舶總在港時間與計劃值的偏差幅度Fig.5 Deviation amplitude between the planned and ctual target value under different degrees of handling fluctuation

4 結(jié)論

在集裝箱碼頭的泊位分配中，由于船舶航速變化、天氣因素、岸橋機械故障、岸橋效率變化、人員安排變動等原因，船舶抵港和裝卸時間具有明顯的動態(tài)性，會產(chǎn)生不同程度的波動.本文針對離散泊位建立動態(tài)泊位分配模型，采用Cples求解，對靜態(tài)數(shù)據(jù)進行了波動處理來研究抵港時間和裝卸時間的波動對船舶總在港時間的影響.結(jié)論表明在船舶抵港時間間隔為3h時，抵港和裝卸時間波動造成的總在港時間與原目標(biāo)的偏差幅度大于間隔為2h和4h的情況，并且隨著波動程度的升高這種差距減小；由于裝卸時間的波動產(chǎn)生的總在港時間偏差比抵港時間波動產(chǎn)生的偏差更為明顯.

本文還存在不足，首先模型中目標(biāo)函數(shù)的評價指標(biāo)單一，只考慮了時間因素，因此在設(shè)定泊位調(diào)度優(yōu)化目標(biāo)時可以考慮最小化船舶離港比計劃離港時間延遲程度以及靠泊泊位與偏好泊位偏離程度等.其次由于本文中沒有考慮先到先服務(wù)原則，導(dǎo)致有些船舶的等待時間過長，可以考慮為每艘船設(shè)定最大等待時間.但在實際過程中可能不能滿足所有船的等待要求，所以可以再設(shè)定船舶滿足等待時間的保證率，這一點可以在模型中增加相應(yīng)的約束條件來實現(xiàn).

從實驗數(shù)據(jù)中可以看出，當(dāng)?shù)指蹠r間和裝卸時間發(fā)生波動時，對泊位分配影響是很大的，所以需要考慮加入一個緩沖時間來減小抵港延誤和裝卸延誤的影響，如何制定緩沖時間的長短使得抵港和裝卸時間波動產(chǎn)生的影響最小，又能保證港口較高的運作能力是本文以后繼續(xù)研究的方向.

［1］Bierwirth C，Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals［J］.European Journal of Operational Research，2010，202（3）：615－627.

［2］韓曉龍，丁以中.集裝箱港口裝卸作業(yè)仿真系統(tǒng)［J］.系統(tǒng)仿真學(xué)報，2006，18（8）：2366－2369.

［3］Lai K K，Shik K.A study of container berth allocation［J］.Journal of Advanced Transportation，1992，26（1）：45－60.

［4］Imai A，Nagaiwa K，Chan W T.Efficient planning of berth allocation for container terminals in Asia［J］.Journal of Advanced Transportation，1997，31（1）：75－94.

［5］Imai A，Nishimura E，Papadimitriou S.The dynamic berth allocation problem for a container port［J］.Transportation Research Part B，2001，35（4）：401－417.

［6］Nishimura E，Imai A.Berth allocation planning in the public berth system by genetic algorithms［J］.European Journal of Operational Research，2001，131（2）：282－292.

［7］Imai A，Nishimura E.Berth allocation at indented berths for mega－containerships［J］.European Journal of Operational Research，2007，179（2）：579－593.

［8］Hao J，Shi L，Zhou J.An ant system algorithm with random perturbation behavior for complex TSP problem［J］.Systems Engineering—Theory ＆Practice，2002，25（9）：88－91.

［9］Moorthy R.Berth management in container terminal：the template design problem［J］.OR Spectrum，2006，28（4）：495－518.

［10］周鵬飛.面向隨機環(huán)境的集裝箱碼頭泊位－岸橋分配方法［J］.系統(tǒng)工程理論與實踐，2008（1）：161－169.

［11］楊春霞，王 諾.集裝箱碼頭泊位分配干擾管理決策方法研究［J］.運籌與管理，2011，20（4）：90－95.

［12］曾慶成，胡祥培.集裝箱碼頭泊位分配－裝卸橋調(diào)度干擾管理模 型［J］.系 統(tǒng) 工 程 理 論 與 實 踐，2010，30（11）：2026－2035.

［13］Zhen L，Lee L H，Chew E P.A decision model for berth allocation under uncertainty［J］.European Journal of Operational Research，2011，212（1）：54－68.

［14］Buhrkal K，Zuglian S，Ropke S.Models for the discrete berth allocation problem：A computational comparison［J］.Transportation Research Part E，2011，47（4）：461－473.

［15］張魯寧，王 諾.集裝箱班輪到港規(guī)律實證研究［J］.大連海事大學(xué)學(xué)報，2012，38（1）：47－48.