梁承姬，王丹丹

(上海海事大學(xué) 物流研究中心，上海 201306)

集裝箱港口岸橋動態(tài)分配與貝位調(diào)度研究

梁承姬，王丹丹

(上海海事大學(xué) 物流研究中心，上海 201306)

為提高集裝箱港口岸橋的利用率和對船舶的服務(wù)水平，針對多船各貝位的任務(wù)量，考慮船舶優(yōu)先度、可作業(yè)岸橋數(shù)量、岸橋沖突和安全距離等因素，以船舶的在港時間最短為目標(biāo)，建立了多船岸橋動態(tài)分配與貝位調(diào)度混合整數(shù)規(guī)劃模型，通過不同規(guī)模的算例，分別用C#調(diào)用Cplex和C#對遺傳算法編程求解。結(jié)果表明：該模型能有效地解決多船的岸橋分配與調(diào)度問題，且遺傳算法求解時間更短、求解質(zhì)量更高，進而驗證了該模型和算法的有效性。

交通運輸工程；岸橋動態(tài)分配；岸橋貝位調(diào)度；岸橋沖突；安全距離；遺傳算法

0 引 言

集裝箱港口作為現(xiàn)代物流的重要組成部分，在全球物流系統(tǒng)中起著重要的作用。隨著競爭的加劇，各個港口都面臨著提高服務(wù)質(zhì)量、降低服務(wù)成本、增加吞吐量的壓力。要想緩解這些壓力，必須有效利用港口的各種資源，如泊位、岸橋、場橋、堆存、集卡等。岸橋是港口的昂貴資源，也是稀缺資源，它的有效利用對于港口的運作效率至關(guān)重要。岸橋資源計劃分為岸橋分配計劃(Quay Crane Allocation Problem, QCAP)和岸橋調(diào)度計劃(Quay Crane Scheduling Problem, QCSP)，兩者緊密聯(lián)系，同時考慮岸橋分配和調(diào)度問題可以更加有效的利用岸橋資源。集裝箱港口的岸橋分配與調(diào)度問題(Quay Crane Allocation and Scheduling Problem, QCASP)研究如何為集裝箱船舶分配岸橋以及安排每臺岸橋的任務(wù)操作順序，使得在滿足實際約束的情況下盡早完成每艘船舶的裝卸操作。

對于單船的QCSP，K.H.Kim等[1]提出了分支定界算法和貪婪隨機自適應(yīng)搜索算法。L.Moccia等[2]在K.H.Kim[1]的基礎(chǔ)上，設(shè)計了分支切割算法，改進了解的質(zhì)量。M.Sammarra等[3]把單船的QCSP分解為兩個子問題，在此基礎(chǔ)上設(shè)計了一種禁忌搜索算法。C.Bierirth等[4]設(shè)計了一個基于分支定界的單向調(diào)度啟發(fā)式算法，算例結(jié)果表明該算法能夠在更短時間內(nèi)產(chǎn)生比以往文獻質(zhì)量更好的解。楊明珠[5]也對該問題進行了研究，給出了一種改進的啟發(fā)式算法。F.Meisel等[6]對目前已有的單船岸橋調(diào)度優(yōu)化模型和算法進行了分析和評價。

對于多船的QCASP，很多學(xué)者都是聯(lián)合泊位資源一起考慮的。R.Tavakkoli-Moghaddam[7]擴展了K.H.Kim[1]提出的單船岸橋調(diào)度模型，構(gòu)建了同時考慮一組船舶的混合整數(shù)規(guī)劃(Mixed Integer Programming ,MIP)模型，并設(shè)計了遺傳算法求解該問題。Liang Chengji等[8]和Zhang Canrong等[9]研究了船舶的靠泊位置、作業(yè)時間以及分配給每艘船的岸橋數(shù)量，前者建立了作業(yè)時間、等待時間及延遲時間之和最小的優(yōu)化模型，后者建立了成本最小的優(yōu)化模型，考慮產(chǎn)生成本的因素是船舶靠泊位置、停泊時間和完成時間。Lee Der-horng等[10]建立了求船舶在港時間最小的MIP模型，并證明了該模型是完全NP問題。梁承姬等[11]研究了考慮泊位的多船QCAP，建立了泊位分配MIP模型和岸橋調(diào)度MIP模型，并用Gurobi軟件進行求解。A.Imai等[12]研究了泊位和岸橋的協(xié)調(diào)分配問題，并運用遺傳算法進行求解。

以上研究大多是將岸橋分配和岸橋調(diào)度分開考慮的，即使考慮岸橋分配與調(diào)度的協(xié)同，也只是考慮單船的貝位調(diào)度問題。為此，筆者將岸橋分配和調(diào)度問題結(jié)合起來，針對多船各個貝位的任務(wù)量動態(tài)地考慮岸橋分配和調(diào)度問題，提出了相應(yīng)的優(yōu)化模型和求解算法，以尋求港口岸邊操作效率最高的岸橋分配和調(diào)度方案。

1 問題描述

船舶靠泊之后由岸橋進行集裝箱的裝卸操作，完成裝卸操作之后離港，如圖1。在該過程中，對于某一個確定的計劃時段，如船舶的進港時間、最晚離港時間、最大裝卸時間、船舶上每個貝位的裝卸任務(wù)量都是已知的，且假定船舶按照進港時間在岸邊依次從左到右靠泊。在為船舶分配岸橋以及安排每臺岸橋的任務(wù)操作順序時，不僅要考慮船舶的進港時間、最晚離港時間和船舶優(yōu)先度，還要考慮可作業(yè)岸橋數(shù)量、岸橋沖突以及岸橋安全距離等因素。筆者研究的是對某一個計劃期內(nèi)(通常一個計劃期為12 h)，對進港的所有船舶進行動態(tài)的岸橋分配和調(diào)度，在保證船舶按時離港的前提下最小化每艘船舶的在港時間。

圖1 集裝箱港口岸邊示意Fig.1 The illustration of quay side at container terminal

2 模型的建立

2.1 模型假設(shè)

岸橋在其服務(wù)的船舶沒有全部完成任務(wù)之前可以移動到另外一艘船舶；每臺岸橋擁有相同的工作能力，且可以雙向移動；所有的岸橋都位于一條水平軌道上，并且將其從左到右依次編號；考慮岸橋之間的安全距離，不考慮岸橋的移動時間；按進港先后順序為船舶依次編號，并將所有船舶的所有貝位依次編號；根據(jù)船舶進港時間生成船舶優(yōu)先度序列，即先進港的船舶優(yōu)先度高，其中同時進港的船舶根據(jù)其離港時間產(chǎn)生優(yōu)先度，即先離港的船舶優(yōu)先度高；根據(jù)所有船舶的總?cè)蝿?wù)量安排可作業(yè)的岸橋數(shù)量；每個貝位的任務(wù)量由整數(shù)時間表示，單位為h；每個貝位的任務(wù)可以由多臺岸橋在不同時段完成。

2.2 集合、參數(shù)及決策變量的定義

集合：K為船舶集合，由k表示，k代表船舶序號；Jk為船舶k的貝位集合，由j表示；Q為岸橋集合，由q表示，q代表岸橋序號；T為時間集合，由t表示。

參數(shù)：lkj為船舶k的貝位j的位置序號；m為相鄰岸橋所在貝位序號的最小差值，這里定義為最小安全距離；pkj為船舶k的貝位j的任務(wù)量;Dk為船舶k的最大裝卸時間；wk為船舶k的優(yōu)先度。

Lk為船舶k的進港時間與第一個進港船舶的進港時間之差，這里定義為相距時間。

決策變量：Xkjqt為若岸橋q在第t時段分配給了船舶k的第j貝位則為1，否則為0；fkjt為若船舶k的第j貝位在第t時段已全部完成任務(wù)則為1，否則為0；rkt為若船舶k在第t時段已全部完成任務(wù)則為1，否則為0。

2.3 目標(biāo)函數(shù)和約束條件

(1)

(2)

(3)

(4)

?q∈Q,?t∈T

(5)

(6)

?k∈K,?j∈Jk,?t∈T

(7)

fkjt≥rkt, ?k∈K,?j∈Jk,?t∈T

(8)

(9)

?k∈K,?j∈Jk

(10)

Xkjqt,fkjt,rkt∈{0,1},

?k∈K,?j∈Jk,?q∈Q,?t∈T

(11)

目標(biāo)函數(shù)(1)將最小化每艘船舶的在港時間之和,轉(zhuǎn)換為最大化一個計劃期內(nèi)船舶離港之后的時間之和；約束條件(2)保證在任意一個時段一臺岸橋最多只能停放在一個貝位上；約束條件(3)保證在任意一個時段任意一個貝位上最多只能停放一臺岸橋；約束條件(4)保證在任意一個時段正在工作的岸橋總數(shù)量不能超過可用的岸橋數(shù)量；約束條件(5)保證在岸橋從左到右依次排序的情況下，相鄰岸橋之間保持至少m貝位的安全距離；約束條件(6)保證所有的集裝箱任務(wù)在計劃時段內(nèi)都必須完成；約束條件(7)定義了每一個貝位上的工作完成標(biāo)志，當(dāng)t時段船舶k的第j貝位上的任務(wù)全部完成時fkjt的值為1，此時在某一貝位上的所有岸橋的時間段總和要大于該貝位的任務(wù)量；約束條件(8)保證某一船舶的所有貝位上的任務(wù)全部完成時才表示該船舶操作完成；約束條件(9)確保所有船舶不超過其最晚離港時間離港；約束條件(10)確保任意船舶的任意貝位是在船舶進港之后開始操作的；約束條件(11)確保所有的決策變量都是0～1變量。

3 遺傳算法的實現(xiàn)

遺傳算法(Genetic Algorithm,GA)是一種高度并行、隨機和自適應(yīng)的優(yōu)化算法，其編碼技術(shù)與遺傳操作較簡單，優(yōu)化不受限制性條件的約束，其已經(jīng)在各個領(lǐng)域有了廣泛的應(yīng)用。由于問題的復(fù)雜性，考慮使用遺傳算法來求解。

3.1 染色體編碼

圖2 染色體編碼示意Fig.2 The illustration of chromosome coding

3.2 生成初始種群

生成初始種群有兩種方法。一種是隨機生成法，該方法有利于保持初始種群的多樣性；另一種是啟發(fā)式方法，它雖然可以生成質(zhì)量較高的初始個體，但可能會導(dǎo)致局部最優(yōu)解。筆者采用隨機生成法生成初始種群，并且只允許可行解成為初始種群的一部分，具體規(guī)則如下：

2)每行中的整數(shù)順序隨機排列，但要保證每艘船舶的各個貝位要在進港之后開始作業(yè)以及在最晚離港時間之前結(jié)束作業(yè)；

3)每列中的整數(shù)按降序排列，即保證岸橋不跨越交叉，且每列中相鄰整數(shù)的差值不能小于安全距離。

3.3 適應(yīng)度計算和父代選擇

根據(jù)目標(biāo)函數(shù)，目標(biāo)函數(shù)值大的給予高適應(yīng)度值。采用輪盤賭方式產(chǎn)生與種群相同數(shù)量的染色體為父代。

3.4 遺傳操作

3.4.1 交叉操作

采用修補交叉，它基于均勻交叉。即首先生成一個二進制字符串矩陣，其中1和0的個數(shù)相等。如果在該二進制字符串矩陣中的值為1則子代相應(yīng)位置的基因值取父代1相應(yīng)位置的基因值，然后根據(jù)子代已有的基因值劃去父代2的一部分基因值，再用父代2剩余的基因值依次填滿子代剩余的基因位置。如圖3為交叉操作的過程。

圖3 交叉操作示意Fig.3 The illustration of crossover operation

3.4.2 變異操作

采用交換變異，其變異操作過程如圖4。

圖4 變異操作示意Fig.4 The illustration of mutation operation

3.5 結(jié)束規(guī)則

通過以上規(guī)則產(chǎn)生的新的子代將會替代舊種群中適應(yīng)度值最小的染色體，該過程中將保持種群規(guī)模，且迭代到最大迭代次數(shù)時終止迭代。

4 算例與結(jié)果分析

為了更好地理解和驗證筆者所提出的模型和算法的有效性，編制了不同規(guī)模的算例。設(shè)定遺傳算法的交叉概率是0.9，變異概率是0.2，最大迭代次數(shù)是500次，種群規(guī)模是150。運行環(huán)境為Intel(R) Core(TM) i5處理器、內(nèi)存4G、硬盤500G的個人計算機，使用C#_2010對遺傳算法編程并計算。

4.1 兩艘船舶的輸入數(shù)據(jù)與結(jié)果分析

船舶數(shù)量為2，可用的岸橋數(shù)量為3，安全距離為1，其它輸入數(shù)據(jù)見表1和表2。計算結(jié)果如圖5，可以看出該結(jié)果既滿足模型中船舶的約束也滿足岸橋的約束，且能夠使每艘船舶在最晚離港時間之前盡早離港。圖6所示是將結(jié)果用岸橋和時間的坐標(biāo)顯示，坐標(biāo)里的數(shù)字代表貝位編號。

表1 船舶任務(wù)量數(shù)據(jù)Table 1 The task data of every vessel

表2 船舶時間數(shù)據(jù)Table 2 The time data of every vessel

圖5 兩艘船舶的貝位-時間甘特圖Fig.5 Bay & time Gantt chart of double vessels

圖6 兩艘船舶的岸橋-時間甘特圖Fig.6 Quay crane & time Gantt chart of double vessels

4.2 5艘船舶的輸入數(shù)據(jù)與結(jié)果分析

船舶數(shù)量為5，可用的岸橋數(shù)量為7，安全距離為1，其它輸入數(shù)據(jù)見表3和表4。計算結(jié)果如圖7所示，可以看出該結(jié)果既滿足模型中船舶的約束也滿足岸橋的約束，且能夠使每艘船舶在最晚離港時間之前盡早離港。圖8是將結(jié)果用岸橋和時間的坐標(biāo)顯示，坐標(biāo)里的數(shù)字代表貝位編號。

表3 船舶任務(wù)量數(shù)據(jù)Table 3 The task data of every vessel

表4 船舶時間數(shù)據(jù)Table 4 The time data of every vessel

圖7 5艘船舶的貝位-時間甘特圖Fig.7 Bay & time Gantt chart of five vessels

圖8 5艘船舶的岸橋-時間甘特圖Fig.8 Quay crane & time Gantt chart of five vessels

4.3 不同規(guī)模的算例結(jié)果比較

為了驗證筆者設(shè)計的遺傳算法求解該模型的有效性，使用C#_2010編程并調(diào)用Cplex求解作為對比。問題規(guī)模從小規(guī)模擴展到實際問題的規(guī)模，其中每艘船舶的貝位數(shù)以及每個貝位上的任務(wù)量是隨機生成的。船舶的時間信息和可用的岸橋數(shù)量是根據(jù)問題的規(guī)模已知的。表5是不同算例規(guī)模的情形下兩種方法的計算結(jié)果。對比可以看出：從能否求解來講，在所有算例中遺傳算法均求得了最優(yōu)解，而當(dāng)問題規(guī)模擴大到一定程度時Cplex無法求解；在計算時間方面，盡管在較小規(guī)模時遺傳算法求解的時間稍長，但隨著問題規(guī)模的擴大，其計算時間遠遠小于Cplex的求解時間，如圖9；在求解質(zhì)量方面，小規(guī)模問題時兩者的求解結(jié)果一致，但隨著問題規(guī)模的擴大，遺傳算法的目標(biāo)函數(shù)值(OFV)越來越優(yōu)于Cplex?？傊?，遺傳算法能夠在合理的時間內(nèi)求得最優(yōu)解，相比Cplex求解時間較短，求解質(zhì)量較高，體現(xiàn)了其有效性，且對于該問題的大規(guī)模問題，遺傳算法更加有效。

圖9 兩種方法求解時間對比Fig.9 Comparison of computing time by two methods

表5 Cplex和GA求解不同規(guī)模的算例結(jié)果Table 5 The results of Cplex and GA by solving examples of different scales

5 結(jié) 語

對集裝箱港口的岸橋分配與調(diào)度問題進行了研究?？紤]了船舶和岸橋的實際因素，以船舶在港時間最短為目標(biāo)建立了多船岸橋動態(tài)分配與貝位調(diào)度混合整數(shù)規(guī)劃模型。設(shè)計了遺傳算法進行求解，結(jié)果表明該模型可以有效解決岸橋的分配與調(diào)度問題。最后，通過不同規(guī)模的算例，分別用Cplex與遺傳算法進行求解。結(jié)果表明遺傳算法的求解時間更短，求解質(zhì)量更高，隨著問題規(guī)模的擴大其優(yōu)越性更加明顯。因此筆者提出的優(yōu)化方法，可為解決大規(guī)模的多船情形下岸橋的統(tǒng)一優(yōu)化問題提供科學(xué)合理的解決方案和決策依據(jù)。需提出的是，由于泊位計劃影響岸橋的分配和調(diào)度，所以未來也可以考慮把泊位計劃加入QCASP中，進而更加有效的優(yōu)化集裝箱港口的岸邊操作。

[1] KIM K H,PARK Y M.A crane scheduling method for port container terminals[J].EuropeanJournalofOperationalResearch,2004,156(3):752-768.

[2] MOCCIA L,CORDEAU J F,GAUDIOSO M ,et al.A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal[J].NavalResearchLogistics,2006,53(1):45-59.

[3] SAMMARRA M,CORDEAU J F,LAPORTE G,et al.A tabu search heuristic for the quay crane scheduling problem[J].JournalofScheduling,2007,10(4/5):327-336.

[4] BIERWIRTH C,MEISEL F.A fast heuristic for quay crane scheduling with interference constraints[J].JournalofScheduling,2009,12(4): 345-360.

[5] 楊明珠.單船裝卸作業(yè)的岸橋調(diào)度[J].計算機工程與應(yīng)用,2011,47(10): 224-228. YANG Mingzhu.Quay crane scheduling method for single vessel[J].ComputerEngineeringandApplications,2011,47(10):224-228.

[6] MEISEL F,BIERWIRTH C.A unified approach for the evaluation of quay crane scheduling models and algorithms[J].Computers&OperationsResearch,2011,38(3):683-693.

[7] TAVAKKOLI-MOGHADDAM R,MAKUIA A,SALAHI S ,et al .An efficient algorithm for solving a new mathematical model for a quay crane scheduling problem in container ports[J].Computers&IndustrialEngineering,2009,56(1):241-248.

[8] LIANG Chengji,HUANG Youfang,YANG Yang.A quay crane dynamic scheduling problem by hybrid evolutionary algorithm for berth allocation planning[J].Computers&IndustrialEngineering,2009,56(3):1021-1028.

[9] ZHANG Canrong,ZHENG Li,ZHANG Zhihai,et al.The allocation of berths and quay cranes by using a sub-gradient optimization technique[J].Computers&IndustrialEngineering,2010,58(1):40-50.

[10] LEE Der-horng,WANG Huiqiu.Integrated discrete berth allocation and quay crane scheduling in port container terminals[J].EngineeringOptimization,2010,42(8):747-761.

[11] 趙坤強,韓曉龍,梁承姬.連續(xù)泊位下集裝箱港口泊位與橋吊協(xié)同調(diào)度優(yōu)化研究[J].武漢理工大學(xué)學(xué)報,2011,33(11):60-65. ZHAO Kunqiang,HAN Xiaolong,LIANG Chengji.Berth and quay crane collaborative optimization research at continuous terminals[J].JournalofWuhanUniversityofTechnology,2011,33(11):60-65.

[12] IMAI A,CHEN H C,NISHIMURA E,et al.The simultaneous berth and quay crane allocation problem[J].TransportationResearchPartE:LogisticsandTransportationReview,2008,44(5):900-920.

Quay Crane Dynamic Allocation and Scheduling with Bay Research at Container Terminal

LIANG Chengji，WANG Dandan

(Logistics Research Center, Shanghai Maritime University, Shanghai 201306, P. R. China)

In order to improve the quay crane’s efficiency and service level for vessels at container terminal, aiming at the heavy workload in every bay of multi-vessels, by considering such factors as ship priority, quantity of available quay crane, quay crane collision and safe distance, a mixed integer programming model on dynamic allocation of quay crane for vessels and scheduling and deployment of bay was establizhed in an attempt to minimize vessels’ staying time at container terminal. Through different scales of examples, the results obtained from Cplex and genetic algorithm programmed by C# respectively showed that the proposed model can effectively solve the problems of quay crane allocation and scheduling of multi-vessels and genetic algorithm has shorter computing time and higher quality solution thus verifying the effectiveness of this model and algorithm.

transportation engineering; quay crane dynamic allocation; quay crane scheduling with bay; quay crane collision; safe distance; genetic algorithm

10.3969/j.issn.1674-0696.2016.02.34

2014-10-27；

2014-12-29

國家自然科學(xué)基金項目(71471110，71301101)；中國博士后科學(xué)基金項目(2014M550084)

梁承姬(1970—)，女(朝鮮族)，吉林龍井人，教授，博士，主要從事集裝箱港口物流方面的研究。E-mail：liangcj@shmtu.edu.cn。

王丹丹(1989—)，女，山西長治人，碩士研究生，主要從事集裝箱港口設(shè)備資源優(yōu)化方面的研究。E-mail：783964457@qq.com。

U694

A

1674-0696(2016)02-169-05