白治江，黃 卿

BAI Zhijiang,HUANG Qing

上海海事大學 信息工程學院，上海 201306

Information Engineering College,Shanghai Maritime University,Shanghai 201306,China

1 引言

集裝箱碼頭的生產(chǎn)效率是由相互影響的若干處理過程決定的，對于岸邊的處理包括泊位分配、岸橋分配以及岸橋調(diào)度問題，其他重要的處理過程包括堆場規(guī)劃，積載規(guī)劃和人力規(guī)劃等。Stahlbock和Vop綜述了集裝箱碼頭的所有操作過程[1]，Bierwirth和Meisel專門論述了泊位分配和岸橋調(diào)度問題[2]。Lai和Shih按照先到先服務的原則提出了一個泊位分配的啟發(fā)式算法[3]。若兩艘貨輪競爭同一泊位時，就必須在平衡成本的前提下考慮它們的優(yōu)先權。影響優(yōu)先權的因素有很多方面，如操作的便利性，盈利效益，負載量大小，緊急情況，海浪情況，集裝箱的轉(zhuǎn)運情況等。Legato和Mazza指出了貨輪接受服務的優(yōu)先權問題[4]，其解決方案是為重要貨輪預留專用泊位，但這種方法不僅增加了調(diào)度的復雜性，也無法有效提高碼頭的總體服務水平。合理的方案應該是讓優(yōu)先權高的貨輪盡可能地靠近其首選泊位即可。Imai提出通過附加權重實現(xiàn)優(yōu)先權的方案[5]，比如某貨輪因緊急情況需要盡快處理，則只須在模型求解時增大其權重值，則規(guī)劃方案就能實現(xiàn)高優(yōu)先權。Lokuge和Alahakoon的方案是讓高優(yōu)先權的貨輪等待時間為0，確保它們能夠隨到隨服務[6]。除了優(yōu)先權對貨輪處理時間的重要影響外，貨輪的泊位和配置的岸橋數(shù)也是影響處理時間的重要因素。Moorthy和Teo提出了處理首選泊位問題的框架結(jié)構(gòu)[7]，并闡述了首選泊位對堆場存儲規(guī)劃，人員和設備調(diào)度等的重要影響。Park和Kim的整數(shù)規(guī)劃模型同時考慮了貨輪優(yōu)先權和首選泊位問題[8]，優(yōu)先權通過在目標函數(shù)中施加延誤懲罰值的辦法實現(xiàn)。模型用兩階段法求解，第一階段確定每個時段內(nèi)貨輪的泊位以及配置給每個貨輪的岸橋數(shù)，第二階段實現(xiàn)每個岸橋的任務規(guī)劃（該階段實際上是操作層面的決策問題，所以本文只考慮第一階段的問題）。Liu等在先行優(yōu)化BA方案的基礎上再求解QCA問題[9]。QCA確定了配置于貨輪的岸橋數(shù)量，因而也決定著貨輪的處理時間以及總的泊位占用時間，而處理時間和泊位占用時間又是BA問題的關鍵輸入，所以將BA和QCA集成優(yōu)化能夠體現(xiàn)總體優(yōu)化效果。

本文對碼頭作業(yè)的基本假設如下：

（1）岸邊看作一個連續(xù)的線段，采用連續(xù)泊位建模規(guī)則。

（2）岸橋可以在泊位之間自由移動。

（3）每一個岸橋一旦準備就緒立即開始作業(yè)。

（4）貨輪負載量是其裝卸集裝箱的總量。

（5）處理時間是裝卸的總時間（包括延誤在內(nèi)）。

（6）貨輪一旦錨定，則服務期間不再移動，但岸橋可以移動。

2 BA和QCA的集成模型

本章建立了一個BA和QCA的集成模型，目標是使所有集裝箱貨輪的調(diào)度費用最小，模型中同時考慮了優(yōu)先權，首選泊位，岸橋移動等生產(chǎn)中的實際特征。貨輪最好的停泊位置（即首選位置）就是距離裝卸集裝箱的存放位置最近的泊位，如果停泊位置距離首選泊位太遠將增大集卡運送距離，所以實際泊位與首選泊位距離應最小化。

為了將本規(guī)劃問題建成混合整數(shù)模型，把時間軸離散化為等距離的時段，岸橋的配置和變動均以時段為單位進行。正如本文實驗中將要說明的一樣，時段的具體長度由用戶根據(jù)實際情況確定。

2.1 滾動規(guī)劃結(jié)構(gòu)

滾動規(guī)劃結(jié)構(gòu)是實現(xiàn)規(guī)劃的策略。當某特定時刻（例如早上6點）求解模型時，須限定規(guī)劃的時間跨度（如24 h或48 h），該時間跨度簡稱規(guī)劃期，規(guī)劃期被離散化為相等的若干時段（如2 h為一個時段）。求解模型獲取當前規(guī)劃期中第一個時段（如6點至8點）的執(zhí)行方案。在第一時段末（8點），利用已經(jīng)更新的數(shù)據(jù)（如參數(shù)arr(i)，mst(i)，epd(i)，ddl(i)的值會相應遞減）將同一模型又重新求解一次，從而在時段數(shù)相同的新規(guī)劃期內(nèi)生成第一時段（此時的第一時段是8點至10點）的執(zhí)行方案，即每運行一次模型相當于規(guī)劃期向前滾動一個時段。

滾動規(guī)劃結(jié)構(gòu)會增加模型實現(xiàn)的復雜度。首先，在做新規(guī)劃時，有些貨輪的服務已經(jīng)開始，所以它們的停泊位置不允許改變，但這些貨輪在下一時段的岸橋數(shù)仍可改變。從模型的角度而言，這些貨輪的相關參數(shù)busyi1，pli，dli，dri已經(jīng)固定不變，但負載wl(i)卻必須更新。其次，對那些最后離港期限或最早離港時間超出規(guī)劃期范圍的貨輪，要在模型的約束條件中做特別的規(guī)定。上述這些情況在下文解釋模型時將做具體說明。

2.2 模型建立

模型中所使用參數(shù)記號如表1所示（凡涉及時間的，均以時段為度量單位）。

決策變量如表2所示。

基于滾動規(guī)劃結(jié)構(gòu)的混合整數(shù)線性規(guī)劃模型如下所示。目標函數(shù)一共由4項組成，其中前三項分別對應著處理時間延誤代價，泊位偏差代價和移動岸橋的代價；第4項是與滾動規(guī)劃有關的修正值。下面分別進行詳細說明：目標函數(shù)第一項是貨輪處理時間延誤的懲罰項。當貨輪靠泊并立即以最大岸橋數(shù)開始服務，則各個連續(xù)時段起始點的負載余量稱為理想負載余量irw(i，t)，最小服務時間mst(i)就是當irw(i，t)降為0時所需的時段數(shù)。顯然，各個后續(xù)時段的實際負載余量大于或等于irw(i，t)。在時段 epd(i)=arr(i)+mst(i)上，理想負載余量已經(jīng)降為0，但由于泊位和岸橋條件的限制，實際負載余量一般并不為0，這表示貨輪服務已經(jīng)延誤。目標是要使延誤最小化，也就是使從時段epd(i)開始往后各個時段的負載余量總和最小化，并且與理想負載余量偏差越大，接受的懲罰也越大，因此再給延誤總量乘以優(yōu)先處理系數(shù)α(i)，于是當兩個貨輪同一時刻競爭岸橋時，優(yōu)先權能保證更重要（或延誤更多）的貨輪獲得相對多數(shù)的岸橋以便盡早完成處理。目標函數(shù)第二項是貨輪停泊位置偏離首選位置的懲罰項，dli和dri分別表示與首選泊位的左偏差和右偏差，該偏差先與貨輪相應負載量wl(i)相乘，以表示內(nèi)卡裝卸每個集裝箱時都要運行這段額外的偏差距離。此項再進一步乘以位置優(yōu)先系數(shù)β(i)，用以反映貨輪的首選泊位相對于處理時間（目標函數(shù)的第一項）的重要性。

表1 模型中所使用參數(shù)記號

表2 決策變量

目標函數(shù)的第三項是貨輪服務期間岸橋配置數(shù)量變化的懲罰項，反映了岸橋移動的機會成本。規(guī)定只有當貨輪的岸橋數(shù)增加時才計算此懲罰項，因為當岸橋減少時，要么是貨輪服務結(jié)束（當然不能罰），要么岸橋移到另一個貨輪（懲罰值在接受岸橋的貨輪上計算）。目標函數(shù)第四項是與滾動規(guī)劃有關的修正項。對于那些最早離港時間超出T的貨輪其延誤懲罰并未包含在目標函數(shù)的第一項中，這意味著模型可以把此類貨輪的服務延遲到T之后而無須承擔任何代價，其好處是能為優(yōu)化其他貨輪的調(diào)度提供更大余地。但如果在當前規(guī)劃期內(nèi)完全不考慮epd(i)超出T的貨輪，則可能在后繼的規(guī)劃中付出更大的代價。所以在目標函數(shù)中增加修正項rwiT作為對這些貨輪延誤的懲罰，從而使它們也參與到當前規(guī)劃期的調(diào)度當中。

約束條件式（1）表示貨輪i正在接受服務；式（2）將二值變量busyit與rwit聯(lián)系起來，一旦開始，只要負載余量不為0，處理就一直繼續(xù)；式（3）定義貨輪的初始負載；式（4）貨輪i在下一個時段的負載余量等于前一時段之負載余量減去該貨輪岸橋數(shù)乘以岸橋生產(chǎn)率，不等式確保rwit非負；式（5）規(guī)定貨輪處理的最后期限（ddl(i)＞T的貨輪除外）；式（6）任何時刻實際配置于貨輪的岸橋數(shù)不能超過所允許的最大值；式（7）任何時段，岸邊布局的岸橋數(shù)小于等于岸橋總數(shù)，式（8）定義變量chgit為貨輪i從某時段到下一個時段岸橋的增加數(shù)。若岸橋數(shù)不變或減少時，chgit=0；式（9）貨輪實際泊位由相對于首選泊位的左右偏差確定；式（10）處于服務中的貨輪泊位固定不變；式（11）所有貨輪泊位須在可用岸線長度范圍內(nèi)；式（12）保證不能在相同位置同時服務兩個貨輪；式（13）規(guī)定決策變量非負屬性；式（14）定義整型變量；式（15）和式（16）定義二值變量。

2.3 示范例子

本示范例子用以說明模型的工作原理，所使用的相應數(shù)據(jù)如表3所示。設有5個貨輪，岸線長1 200 m，15個岸橋，生產(chǎn)率為30箱/h，時段長為1 h，γ設為150。

本示范例的解決方案如圖1所示，其中三類懲罰值均有發(fā)生（如表4），貨輪2和3在第7和第8時段未分配到最大岸橋數(shù)因而產(chǎn)生延誤罰值，服務結(jié)束時間延誤一個時段，例如對貨輪2，本來在第10時段理想負載余量為150，在第11時段（即最早離港時段）為0，由于在第7和第8時段只配置了3個岸橋，則貨輪2的服務遲滯了120個集裝箱，使得在第10和第11時段的實際負載余量分別為270箱和120箱，引起的延誤罰值為9×120=1 080，貨輪5的延誤懲罰值是因為開始服務時間延遲（必須等貨輪4離開）。

第二類懲罰值是偏離首選泊位引起的，只有貨輪1和4在首選泊位，剩余的貨輪只有等別的貨輪離開后才有可能得到首選泊位，但這將導致非常高的延誤罰值。模型在不同代價之間尋找最優(yōu)平衡的結(jié)果是：雖然達不到首選泊位，但盡快靠泊是代價較小的選擇。

表3 示例中的船數(shù)據(jù)

圖1 示例的解

表4 示例中的懲罰值

為了限制服務期間貨輪的岸橋數(shù)量變化，增加岸橋?qū)е聭土P值，所以貨輪2和3在第9時段有岸橋增加的罰值。

3 實驗結(jié)果

為了驗證模型及滾動規(guī)劃結(jié)構(gòu)的有效性，采集到上海港某碼頭一個季度的運行數(shù)據(jù)集，如表5所示。碼頭的岸線長度近似為2 000 m，岸橋數(shù)為18臺。負載即為所有待裝/卸集裝箱總量，貨輪數(shù)量為782，總負載量為669 503。

表5 實驗數(shù)據(jù)

實驗中將岸橋生產(chǎn)率設為35箱/h，雖然實際生產(chǎn)率高于這個值，但考慮到岸橋移動所造成耽誤的事實，特意將其降為35。貨輪的位置優(yōu)先系數(shù)β(i)取為0.000 1，這個微小取值能保證目標函數(shù)中對位置偏差的懲罰相對于延誤懲罰仍然很小。

模型用C++（使用ILOG Concert Technology技術）編碼實現(xiàn)，用Cplex 12求解。

3.1 基本情況分析

首先通過實驗確定適合該數(shù)據(jù)集的時段長度和規(guī)劃期長度，所以在數(shù)據(jù)集上以不同的時段（2，4和8 h）與不同的規(guī)劃期（24，48和72 h）來運行模型。

表6最后兩行列出了不同組合下模型每次迭代的CPU平均值和最大值，正如所料，在小時段且大規(guī)劃期組合的情況下運算復雜度增加。從CPU的值得到的重要結(jié)論是，即使對最復雜的72 h規(guī)劃期與2 h時段組合的平均計算時間也非常有限（說明：在運算期間需要通過逐漸增加MIP的相對允許偏差（relative MIP gap tolerance）來限制單次運行的計算時間，例如，運行1 min后cplex相對偏差由默認的0.01%增至0.05%，2 min和3 min后相對偏差分別增大至0.1%和1%。本實驗中最大的MIP偏差僅為0.4%，最長運行時間僅為3 min）。由于運行時間如此之短，模型可用于信息更新快并且需要進行頻繁重新規(guī)劃的環(huán)境中。

表6剩余部分列出不同組合下的目標函數(shù)代價，對比結(jié)果發(fā)現(xiàn)，在時段長度相同的情況下，24 h規(guī)劃期的懲罰值一般較大，而48和72 h的懲罰值幾乎相同。原因是對當前時段到達的貨輪進行規(guī)劃時，將后續(xù)時段到達的貨輪考慮進來是有意義的，但顯然向前看2天已經(jīng)足夠了，向前看得更遠（如3天）計算復雜度增加但解的質(zhì)量并無提高，所以本文實驗中只考慮48 h的規(guī)劃期。

表6 目標函數(shù)各組成部分的值和模型的時間復雜度

圖2 一個規(guī)劃的解

當時段長度不同時，規(guī)劃總代價差距很大，然而解的實際結(jié)構(gòu)（即泊位分配和岸橋配置）卻幾乎相同。時段長度對總代價影響的原因如下：因為泊位是以時段為基本單位分配的，所以即使完成服務的貨輪在某時段內(nèi)已經(jīng)離開，但該空閑泊位其他貨輪仍不可用。例如假設一個貨輪需要6 h服務，若使用2 h時段的話，則3個時段后該位置即為可用。若使用4 h時段，雖然該貨輪只需1.5個時段即可完成服務，但必須給其分配2個連續(xù)時段，此時在剩余的0.5時段內(nèi)，該泊位雖然已經(jīng)空閑但仍不能被其他貨輪使用，從而迫使這些貨輪或者等待或者?？坎簧趵硐氲牟次唬瑢е聲r間和距離的相關代價上升?；趯嶒灲Y(jié)果的分析，該碼頭生成泊位分配和岸橋配置的最合適組合是2 h時段且48 h規(guī)劃期。

圖2是該組合下一次規(guī)劃的結(jié)果，其中V表示貨輪，相應的數(shù)字表示服務期間每個時段內(nèi)的岸橋數(shù)，水平軸表示當前規(guī)劃期內(nèi)的時段，縱軸表示岸線的長度。

3.2 敏感性分析

為了更進一步驗證模型的有效性并展示其決策支持的潛力，對可用岸橋數(shù)的變化，可用岸線長的變化以及位置懲罰參數(shù)β(i)的變化做了敏感性分析，得出如下結(jié)論：（1）當岸橋數(shù)量增加時，能顯著降低總代價，這是因為額外的岸橋能使貨輪更快完成服務（避免了時間延誤懲罰），從而盡快釋放泊位使其他貨輪能更靠近首選泊位（減少了位置罰值），岸橋不再為緊缺資源（避免了岸橋移動的懲罰值），減少岸橋數(shù)將導致更多擁堵并增加總的調(diào)度成本。無論是增加還是減少岸橋數(shù)，模型都會在三類成本之間進行尋求優(yōu)化平衡。（2）當可用岸線長度減少時，會同時增加位置偏差罰值和時間延誤罰值，因為岸線長度減少意味著在繁忙時段沒有足夠空間服務所有的貨輪，首選泊位更加沒有可能。（3）權重系數(shù)β(i)實際上是具有管理意義的參數(shù)，因為它決定了如何平衡時間偏差（影響貨輪方收益）和位置偏差（影響碼頭方收益）之間的關系。若β(i)值上升，則貨輪首選泊位平均偏差減少，但延誤會增加。模型將會在兩種代價之間尋找最優(yōu)平衡。

4 結(jié)論

本文介紹了一個泊位分配和岸橋配置的集成模型，包含了優(yōu)先權，首選泊位和處理時間幾個實際生產(chǎn)的特征。該模型能在信息更新的前提下滾動做出優(yōu)化決策，可用作現(xiàn)代化碼頭的決策支持工具，從而使規(guī)劃管理者有更多時間應對意外情況下的調(diào)度問題。模型成功地在實際數(shù)據(jù)上得到了有效性驗證，計算結(jié)果表明該模型能在合理的時間內(nèi)給出高質(zhì)量的規(guī)劃方案。此外對岸橋數(shù)，岸線長度和管理參數(shù)的敏感性分析結(jié)果表明，模型能有效地對各個代價組成部分進行最優(yōu)的折中平衡，表現(xiàn)了支持管理決策的能力。模型能在短時間內(nèi)求解實際案例的規(guī)劃問題，進一步測試評估將在具有高度擁堵特征的仿真數(shù)據(jù)上進行，以便檢驗在極端情況下模型的魯棒性和靈活性以及是否需要采用啟發(fā)式方法。

[1]Stahlbock R，Vop S.Operations research at container terminals：a literature update[J].OR Spectrum，2008，30：1-52.

[2]Bierwirth C，Meisel F.A survey of berth allocation and quay crane scheduling problems in container terminals[J].European Journal of Operational Research，2009，202：615-627.

[3]Lai K K，Shih K.A study of container berth allocation[J].Journal of Advanced Transportation，1992，26：45-60.

[4]Legato P，Mazza R M.Berth planning and resources optimization at a container terminal via discrete event simulation[J].European Journal of Operational Research，2001，133：537-547.

[5]Imai A，Nishimura E，Papadimitriou S.Berth allocation with service priority[J].Transportation Research Part B，2003，37：437-457.

[6]Lokuge P，Alahakoon D.Improving the adaptability in automated vessel scheduling in container ports using intelligent software agents[J].European Journal of Operational Research，2007，177：1985-2015.

[7]Moorthy R，Teo C.Berth management in container terminal：the template design problem[J].OR Spectrum，2006，28：495-518.

[8]Park Y M，Kim K H.A scheduling method for berth and quay cranes[J].OR Spectrum，2003，25：1-23.

[9]Liu J，Wan Y W，Wang L.Quay crane scheduling at container terminals to minimize the maximum relative tardiness of vessel departures[J].Naval Research Logistics，2006，53：60-74.

[10]de Oliveira R M.Clustering search for the berth allocation problem[J].Expert Systems with Applications，2012，39：5499-5505.

[11]Buhrkal K，Zuglian S，Ropke S，et al.Models for the discrete berth allocation problem：a computational comparison[J].Transportation Research Part E：Logistics and Transportation Review，2011，47：461-473.

[12]Chaves A A，Lorena L A N.Clustering search algorithm for the capacitated centred clustering problem[J].Computers&Operations Research，2010，37：552-558.

[13]Cheong C Y，Tan K C，Liu D K，et al.Multi-objective and prioritized berth allocation in container ports[J].Annals of Operations Research，2010，180：63-103.

[14]Cordeau J F，Laporte G.Models and tabu search heuristics for the berth allocation problem[J].Transportation Science，2005，39：525-538.

[15]Giallombardo G，Moccia L，Salani M，et al.Modeling and solving the tactical berth allocation problem[J].Transportation Research Part B，2010，44：232-245.