岸橋調(diào)度的三維空間建模方法研究＊

張艷偉 周 萬 郭 放

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

0 引 言

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

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

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

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

1 建立三維空間

結(jié)合岸橋的實(shí)際工作情況，對(duì)岸橋調(diào)度問題做出如下假設(shè).

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

2）集裝箱船的每個(gè)艙位可以沒有裝卸任務(wù)，也可以包含多個(gè)裝卸任務(wù)，每個(gè)裝卸任務(wù)的工作量已知，同艙位的裝卸任務(wù)之間存在作業(yè)順序的制約，因?yàn)橥愇坏难b卸任務(wù)通常先進(jìn)行卸船作業(yè)，再進(jìn)行裝船作業(yè).每個(gè)裝卸任務(wù)必須連續(xù)作業(yè)，同艙位的多個(gè)裝卸任務(wù)之間可以連續(xù)作業(yè)，也可以不連續(xù)作業(yè).

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

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

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

圖1 岸橋調(diào)度的三維空間模型

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

2 變量定義和數(shù)學(xué)模型

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

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

目標(biāo)函數(shù)：

約束條件：

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

3 算例分析

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

對(duì)于本文建立的多目標(biāo)最大最小化數(shù)學(xué)模型，可以先不考慮目標(biāo)函數(shù)（2）的最優(yōu)化，并將目標(biāo)函數(shù)（1）轉(zhuǎn)化為約束條件，使優(yōu)化模型轉(zhuǎn)化為一個(gè)只有約束條件的混合組模型.增加的約束條件為

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

利用Excel軟件將表3中最優(yōu)化的結(jié)果繪制成岸橋調(diào)度的計(jì)劃圖（見圖2）.為了進(jìn)一步檢驗(yàn)?zāi)Ｐ偷挠行裕⒎治鋈蝿?wù)數(shù)、艙位數(shù)以及岸橋數(shù)對(duì)模型求解時(shí)間的影響，需要編制多個(gè)不同算例實(shí)驗(yàn)并進(jìn)行求解.假設(shè)船舶貝位數(shù)的取值分別為10（3），14（4），18（5），22（5），括號(hào)中的數(shù)字表示允許同時(shí)作業(yè)的最大岸橋數(shù)量，岸橋數(shù)取值為3，4，5，任務(wù)數(shù)取值為10～30之間，當(dāng)任務(wù)數(shù)較多時(shí)，分配的岸橋數(shù)量往往也較多.總共設(shè)計(jì)了54個(gè)算例.

表1 裝卸任務(wù)數(shù)據(jù)表

表2 岸橋工作數(shù)據(jù)表

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

圖2 岸橋調(diào)度求解結(jié)果

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

表4 算例實(shí)驗(yàn)的求解時(shí)間岸橋數(shù)＝3 s

表5 算例實(shí)驗(yàn)的求解時(shí)間岸橋數(shù)＝4 s

表6 算例實(shí)驗(yàn)的求解時(shí)間岸橋數(shù)＝5 s

4 結(jié)束語

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

［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］靳志紅，李 娜.基于泊位計(jì)劃的集裝箱碼頭岸橋動(dòng)態(tài)調(diào)度優(yōu)化［J］.交通運(yùn)輸工程與信息，2011，11（3）：58-64.

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

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