張艷偉 周 萬 郭 放

（武漢理工大學物流工程學院1） 武漢 430063）（武漢新港發(fā)展研究院2） 武漢 430063）

0 引 言

集裝箱港口日常經營決策主要包括以下幾個問題［1］：Q1，為到達船舶分配泊位；Q2，為到達船舶分配岸橋；Q3，確定岸橋在不同艙位的作業(yè)順序；Q4，確定外部集裝箱卡車的到達時間；Q5，內集卡的分配、調度及租用計劃；Q6，內、外集卡的路徑選擇問題；Q7，內、外集卡在大門和岸邊的派工策略；Q8，集裝箱的箱位分配問題；Q9，場橋的分配與調度問題.

在以上9個問題中：Q1，Q2，Q3主要解決集裝箱港口的岸邊作業(yè)問題；Q4，Q5，Q6，Q7主要解決集卡調度問題（包括內集卡和外集卡），Q8，Q9主要解決堆場作業(yè)問題.在實際生產活動中，集裝箱港口通常將岸邊作業(yè)計劃作為堆場作業(yè)問題及集卡調度問題的輸入，因此在制定岸邊作業(yè)計劃時往往只需要考慮到港船舶的相關特性即可，而不用考慮集卡調度問題以及堆場作業(yè)問題對其可能產生的影響.

在集裝箱港口的岸邊作業(yè)問題中，Q1確定集裝箱船在哪一段時間內停泊在碼頭的什么位置［2］，Q2確定各集裝箱船在靠泊時間內的岸橋分配情況，Q3在Q1和Q2問題的基礎上確定岸橋在各集裝箱船不同艙位間的作業(yè)順序.由于岸橋的分配情況（Q2）將直接影響到不同集裝箱船所需的作業(yè)時間，而不同集裝箱船所需的作業(yè)時間又對泊位分配計劃（Q1）的結果產生很大影響，因而Q1和Q2通常需要一起考慮，被稱為泊位與岸橋的聯(lián)合分配問題（Q1+Q2）［3］.由于Q1+Q2的結果是岸橋調度問題（Q3）的輸入，因此Q3不需要與Q1和Q2問題同時考慮，可以單獨研究.

在岸橋調度問題的相關研究中，靳志紅，李娜［4］研究了基于泊位計劃的岸橋調度問題，并利用遺傳算法對模型進行了求解.張亞輝，梁承姬［5］研究了離散艙位的岸橋調度問題.秦進，倪玲霖，王承娜等［6］研究了多船舶的岸橋調度問題，并利用模擬退火算法對建立的數學模型進行了求解.

1 建立三維空間

結合岸橋的實際工作情況，對岸橋調度問題做出如下假設.

1）每條船舶的靠泊時間以及該時間段內分配的岸橋數量已知（由Q1+Q2確定），每臺岸橋都受到最早可利用時間的制約，并且所有岸橋的裝卸效率相同.

2）集裝箱船的每個艙位可以沒有裝卸任務，也可以包含多個裝卸任務，每個裝卸任務的工作量已知，同艙位的裝卸任務之間存在作業(yè)順序的制約，因為同貝位的裝卸任務通常先進行卸船作業(yè)，再進行裝船作業(yè).每個裝卸任務必須連續(xù)作業(yè)，同艙位的多個裝卸任務之間可以連續(xù)作業(yè)，也可以不連續(xù)作業(yè).

3）由于岸橋之間必須保持一定的安全距離，因而2個相鄰的岸橋之間必須間隔至少一個艙位.

4）岸橋在固定軌道上運行，因而無論岸橋是否處于作業(yè)狀態(tài)，岸橋之間都不能相互跨越.

將岸橋調度問題抽象成三維空間中長方體的位置決定問題，這種做法使得建立的模型更加簡單.岸橋調度的三維空間模型見圖1.

圖1 岸橋調度的三維空間模型

三維空間中的每一個長方體都代表了一個裝卸任務.X軸為時間序列；Y軸為船舶艙位號；Z軸為岸橋序號.長方體在X軸方向上的長度為裝卸任務的作業(yè)量，在Y軸上的坐標為裝卸任務所在的艙位，在Z軸上的坐標為裝卸任務由哪一個岸橋完成.XOZ平面內的投影表示岸橋作業(yè)計劃，即哪一個岸橋在哪一個時間段內為哪一個裝卸任務服務；XOY平面內的投影表示不同艙位上的作業(yè)狀態(tài)，即哪一個艙位上的哪一個裝卸任務在哪一段時間內正在被服務.通過對XOZ平面，以及XOY平面內的投影設置相關約束就能夠使岸橋調度滿足實際生產中的限制條件.

2 變量定義和數學模型

為了方便建立數學模型，定義變量如下：I為裝卸任務集合，i，j∈I；K為岸橋集合，k∈K；wi為任務i的裝卸作業(yè)量，任務量單位為自然箱；xi為任務i開始裝卸作業(yè)的時間，文中所涉及的時間單位均設定為處理一個自然箱所需要的平均時間；yi，任務i所在的船舶艙位號；zi，為任務i提供裝卸服務的岸橋序號；bi，任務i完成裝卸作業(yè)的時間；vij，當任務i的完成作業(yè)時間早于在任務j的開始作業(yè)時間，vij=1，否則vij=0.當同艙位的裝卸任務之間存在先后順序時，可以利用vij=1對裝卸時間進行控制，這部分vij可以認為是已知量，其他的vij則為變量；uij，當uij=1時，任務i所在的船舶艙位號小于任務j所在船舶艙位號，并且為任務i提供裝卸服務的岸橋序號小于為任務j提供裝卸服務的岸橋序號.當uij=0時，艙位序號之間以及岸橋序號之間不需要滿足大小關系的約束；Sik，當任務i由岸橋k提供裝卸作業(yè)服務時，Sik=1，否則Sik=0；M為一個較大的實數，本文中取1000.

利用以上數學符號以及岸橋調度問題在三維空間中的幾何意義，建立岸橋調度的整數線性規(guī)劃模型如下.

目標函數：

約束條件：

目標函數（1）表示最小化各裝卸任務完成時間的最大值，因此該模型是一個最大、最小化問題.目標函數（2）表示最小化所有任務完成作業(yè)時間之和，為次目標函數.當目標函數（1）存在多個最優(yōu)解時，可以利用目標函數（2）對岸橋調度問題進一步優(yōu)化，得到更加合理的解.約束條件（3）～（6）用來實現(xiàn)岸橋調度問題中假設3）和假設4）的約束；約束（7）保證所有的任務有且僅有一個岸橋為其提供裝卸服務；約束（8）表示岸橋作業(yè)狀態(tài)與岸橋序號之間的關系；約束條件（9）表示所有的裝卸任務都必須在對應岸橋的最早可利用時間后才能進行裝卸作業(yè).

3 算例分析

由于建立的模型是一個整數線性規(guī)劃模型，因而該模型的求解比較容易，利用LINGO 軟件可以方便地求解這一類問題.表1和表2給出了一個岸橋調度問題的算例，表示為一艘具有10個40in艙位，12個裝卸任務的集裝箱船分配了3臺岸橋，需要確定岸橋在不同艙位間的作業(yè)順序.假設岸橋裝卸一個集裝箱的作業(yè)時間為一個時間單位.

對于本文建立的多目標最大最小化數學模型，可以先不考慮目標函數（2）的最優(yōu)化，并將目標函數（1）轉化為約束條件，使優(yōu)化模型轉化為一個只有約束條件的混合組模型.增加的約束條件為

通過設定不同的L值來尋找目標函數（1）的最小值.利用Lingo軟件的分支定界求解器，可以在1s之內求出混合組的可行解.當L=162時，混合組具有可行解，而當L=161時，混合組不存在可行解，因此目標函數（1）在最優(yōu)解條件下的函數值為162.由于L=161條件下的可行解存在多個，因此目標函數（1）達到最小值時的最優(yōu)解也有多個.將L值固定為162，把目標函數（2）作為惟一的目標函數，利用分支定界算法可以在6s內求出模型的最優(yōu)解，目標函數（2）在最優(yōu)解條件下的函數值為1198.在絕大多數情況下，模型的最優(yōu)解惟一.利用LINGO 求得算例的最優(yōu)調度方案見表3.

利用Excel軟件將表3中最優(yōu)化的結果繪制成岸橋調度的計劃圖（見圖2）.為了進一步檢驗模型的有效性，并分析任務數、艙位數以及岸橋數對模型求解時間的影響，需要編制多個不同算例實驗并進行求解.假設船舶貝位數的取值分別為10（3），14（4），18（5），22（5），括號中的數字表示允許同時作業(yè)的最大岸橋數量，岸橋數取值為3，4，5，任務數取值為10～30之間，當任務數較多時，分配的岸橋數量往往也較多.總共設計了54個算例.

表1 裝卸任務數據表

表2 岸橋工作數據表

表3 算例最優(yōu)解結果

圖2 岸橋調度求解結果

當算例的規(guī)模比較大時，往往很難通過LINGO 快速得出最優(yōu)解，因而考慮通過設置合適的L值，得到可以接受的較優(yōu)解，并比較分析在不同艙位數，任務數以及岸橋數等條件下，LINGO 求得較優(yōu)解所需要的時間.假設某集裝箱船的裝卸任務量為450，分配3臺岸橋為其服務.若所有岸橋在初始時刻就可以進行作業(yè)，則最優(yōu)解不會小于150m（即L可以取得的最小值）.顯然150 m為最優(yōu)解可能達到的最小值（通常情況下最優(yōu)解會大于這個值），令L分別取該值的105%和110%，即L=158m 或者165m.若L=158m 時存在可行解，則該可行解可以視為較優(yōu)解，較優(yōu)解與最優(yōu)解（最優(yōu)解大于或等于150m）的差值最大為5%；若L=158m 時不存在可行解，而L=165m時存在可行解，則較優(yōu)解與最優(yōu)解（最優(yōu)解大于或等于158m）的最大差值仍為5%.比較不同條件下，LINGO 求得滿足該L 限制的較優(yōu)解的時間，見表4～表6.從表中的實驗結果可以看出，在大多數算例實驗中，可以在60s以內得到模型的較優(yōu)解.在極少數情況下，模型較優(yōu)解的求解時間會超過2min，即便如此，求解時間依然在可以接受的時間范圍內.綜上所述，該整數線性規(guī)劃模型能夠有效解決岸橋調度問題.

表4 算例實驗的求解時間岸橋數＝3 s

表5 算例實驗的求解時間岸橋數＝4 s

表6 算例實驗的求解時間岸橋數＝5 s

4 結束語

本文針對集裝箱港口實際生產中岸橋調度問題的特點，建立了以時間序列、船舶艙位號，以及岸橋序號為坐標軸的三維空間，并基于該三維空間建立了岸橋調度的整數線性規(guī)劃模型.利用LINGO 軟件可以求解出數學模型的最優(yōu)解，當問題規(guī)模較小時，利用LINGO 軟件求得模型最優(yōu)解比較方便，當問題規(guī)模較大時，可以利用LINGO 軟件在可以接受的時間內求得模型的較優(yōu)解，通常情況下可以在1min左右求得與最優(yōu)解差值在5%的較優(yōu)解.算例實驗結果表明，該三維空間建模方法能夠有效解決岸橋調度問題.

［1］MURTY K G，LIU JIYIN，WAN Yatwah，et al.A decision support system for operations in a container terminal［J］.Decision Support System，2005，39：309-332.

［2］MOON K.Berth scheduling by simulated annealing［J］.Transportation Research，2003，37：541-560.

［3］KIM P.A scheduling method for berth and quay cranes［J］.OR Spectrum，2003，25：1-23.

［4］靳志紅，李 娜.基于泊位計劃的集裝箱碼頭岸橋動態(tài)調度優(yōu)化［J］.交通運輸工程與信息，2011，11（3）：58-64.

［5］張亞輝，梁承姬.基于離散艙位的集裝箱港口岸橋作業(yè)調度研究［J］.武漢理工大學學報，2012，34（5）：64-69.

［6］秦 進，倪玲霖，王承娜，等.集裝箱碼頭岸橋調度優(yōu)化模型及算法［J］.西南交通大學學報，2013，48（1）：184-192.