初良勇， 阮志毅， 李淑娟

(1.集美大學 現代物流研究中心，福建 廈門 361021；2.廈門雅迅網絡股份有限公司 研發(fā)部，福建 廈門 361008； 3.仰恩大學 管理學院，福建 泉州 362000)

基于遺傳算法的港口集裝箱堆場場橋智能調度優(yōu)化

初良勇1， 阮志毅2， 李淑娟3

(1.集美大學 現代物流研究中心，福建 廈門 361021；2.廈門雅迅網絡股份有限公司 研發(fā)部，福建 廈門 361008； 3.仰恩大學 管理學院，福建 泉州 362000)

以港口集裝箱場橋調度為研究對象，建立集裝箱場橋的智能調度優(yōu)化數學模型，設計基于遺傳算法的模型求解策略，并根據一個典型港口的實際數據進行驗證。運算結果表明，與實際操作及以前的優(yōu)化算法相比，該方法可較大幅度地縮短作業(yè)時間、降低運作成本。

水路運輸；港口物流；集裝箱堆場；場橋調度；遺傳算法

集裝箱碼頭的場橋作為港口物流系統(tǒng)的重要組成部分，其運作效率的高低直接影響堆場(乃至整個港口集裝箱物流系統(tǒng))的運作水平，進而影響港口的綜合運營成本及其競爭力。國內外相關學者已對堆場和場橋的合理配置問題進行積極探索。LEE等[1]對堆場空間分配問題和堆場車輛調度問題進行研究，以最小化加權總延誤和車輛總運輸時間為目標，設計混合插入算法對問題進行求解；SAFAEI等[2]以各箱區(qū)作業(yè)量的平衡為目標解決進口箱的箱位分配問題，并運用遺傳算法進行求解；毛鈞等[3]針對集裝箱碼頭堆場作業(yè)效率較低的問題，構建以平衡各箱區(qū)貝位間的作業(yè)量和最小化泊位到堆場的運輸距離為目標的兩階段優(yōu)化模型，并運用Lingo進行求解；鄭紅星等[4]建立混堆模式下的多箱區(qū)場橋聯合調度的非線性數學規(guī)劃模型，并采用遺傳算法進行求解；初良勇等[5]建立多箱區(qū)多場橋的智能調度優(yōu)化模型,并采用模擬退火算法進行優(yōu)化求解；康海貴等[6]以解決堆場箱區(qū)間作業(yè)量的平衡和集卡行駛距離等問題為切入點，構建兩階段智能算法，并利用具體算例驗證模型和算法的有效性?？v觀國內外相關學者對港口集裝箱場橋調度問題的研究，大部分以場橋的移動距離或移動時間最短為優(yōu)化目標，還有一部分以堆場場橋的無效率作業(yè)時間最短為目標函數構建優(yōu)化模型。當前，隨著信息技術的不斷發(fā)展和智慧港口建設的不斷推進，先進的集裝箱碼頭已可通過信息化手段提前確定集卡進場的時間。因此，這里在構建模型時，綜合考慮面向集卡服務的時間窗，對場橋等待集卡的時間和集卡等待場橋的時間進行聯合優(yōu)化，并綜合考慮多場橋移動產生的時間成本和均衡性，以使所構建的模型更能符合港口信息化、智能化的發(fā)展趨勢。

（4）打破出版商尤其是大型出版巨頭的壟斷。如今，全球學術機構每年付給出版社80億訂購費用，而且有進一步上漲的趨勢。為此，德國有150多個圖書館、大學和研究機構聯合起來要求出版社改變商業(yè)模式，一些學者已經拒絕為一些商業(yè)期刊提供同行評議或投稿［9］。

1 調度優(yōu)化模型

文獻[5]結合集裝箱場橋調度的特點建立多箱區(qū)多場橋調度的優(yōu)化模型，先期采用模擬退火算法進行求解，實例驗證結果顯示該算法可收斂到最優(yōu)解，并可有效縮短作業(yè)時間和降低運作成本。為尋求更高效的求解算法，在文獻[5]的基礎上對優(yōu)化算法進行改進和提升，限于篇幅，這里只列出調度優(yōu)化模型的目標函數和約束條件。

在SPOC翻轉課堂中，學生的角色發(fā)生了轉變。學生在課堂上通過小組活動、協(xié)作學習、課堂成果展示的形式來完成對所學知識的理解、吸收、內化和應用，由之前知識的消費者轉變成了知識的生產者[3]13。一些學習效率高、接受能力較強的學生還可以擔任學習效率相對較低的同伴的“小老師”。同伴互助和教師在線答疑解惑使學生在整體上達到了學習要求。與此同時，教師的角色也發(fā)生了變化，由知識的傳授者轉變成學生學習的支持者，協(xié)助他們在語言學習的道路上不斷前進。

1) 目標函數為

首先按自然序列{1,2,…,K}對場橋進行編號，按自然序列{1,2,…,N}對進場外集卡操作的任務進行編號；隨后以一定次序將任務編碼分配給場橋,根據所分配任務編碼的次序對場橋進行調度。針對多場橋的調度,采用雙染色體的編碼方式[7-8],其中一條用于編碼任務，另一條用于編碼場橋，并分別記為α染色體和β染色體，圖1為2組不同編碼的雙染色體。雙染色體的解碼方式為：α染色體中編碼的任務根據β染色體對應位置的編號分配給相應的場橋。例如，圖1a)表示場橋1和場橋2的調度次序分別為[4-2-3-6]及[1-7-5]；圖1b)表示場橋1和場橋2的調度次序分別為[5-4-1]及[7-6-2-3]。

(1)

對于互換編碼方式,交叉算子一般可分為單點交叉和多點交叉,此外又有匹配交叉、順序交叉和循環(huán)交叉等區(qū)別。[10]這里將單點交叉和兩點交叉分別與順序交叉相組合形成4種交叉形式,并在交叉過程中等概率選擇使用。在算法中,交叉算子僅對α染色體的編碼進行互換,保留任務與場橋間的對應關系,即交叉后還需對β染色體編碼進行調整。例如,以圖1中的2組雙染色體為父代,對第3個交叉點采用單點交叉和順序交叉的形式進行交叉，其大致過程見圖2。

由上可知，“農業(yè)為主”論在教育界乃至政界均有一定的共識，他們認為中國“以農立國”，而且現實國情也要求中國應當重點發(fā)展農業(yè)，因此發(fā)展生產教育應當以農業(yè)為主。其中又有“農業(yè)為主，工業(yè)為輔”與單純強調“農業(yè)為主”兩種觀點的區(qū)別。

(2)

(3)

(4)

(5)

在約束條件中：式(2)表示完成場橋操作的總任務；式(3)表示場橋k操作的任務數；式(4)表示每項任務只由1個場橋完成；式(5)表示每個場橋的任務多于1項；式(7)表示對于任意由場橋k完成的任務i，至多存在某個任務p使得操作次序為i-p; 式(8)表示對于任意由場橋k完成的任務I，至多存在某個任務q使得操作次序為q-i; 式(9)表對于示任意由場橋k完成的任務i,至少存在某個任務p使得操作次序為i-p; 式(10)表示相關變量的定義;式(11)表示任意時刻不同場橋之間必須保持一定的安全距離。

(6)

(7)

(8)

(9)

(10)

|Bk1(s)-Bk2(s)|>Bsafe，k1≠k2

(11)

式(1)由3部分組成，其中：第1部分表示場橋的移動成本；第2部分表示場橋等待集卡和集卡等待場橋的總罰金；第3部分用以約束在場工作的場橋的工作時間，實現對均衡性的控制。

2）數值計算。數值計算包括數值類型轉換、CRC校驗等。CRC校驗選擇A001多項式碼的CRC16校驗。

Nk>1，k=1,2,…，K

2 遺傳算法求解設計

2.1 編碼與解碼

?? ? Breidenbach ，Mediation:Struktur，Chancen und Risiken von Vermittlung im Konflikt，1995，S．72．

a)b)

圖1 雙染色體的編碼示意

2.2 適應度函數

在本文的遺傳算法中,直接以式(1)為個體的適應度函數。合理地限定初始代與代際間種群中個體的產生方式,可使所有解滿足式(2)～式(10)，而安全距離條件的約束并不容易被體現和滿足。因此,再在算法中針對每個個體分別設置一個安全距離標記變量，用f表示，用以標記對應個體是否滿足式(11)。

對于所有種群中的個體,由初始時刻起取一定的時間步長，逐一時刻定位場橋的位置，并計算各場橋之間的距離，判斷對應的解是否滿足式(11)。顯然，所取的時間步長必須

2.3 初始代種群

先產生一組{1,2,…,N}的隨機亂序數列以形成α染色體;將前K個任務分配給K個場橋作為其初始操作任務,并在β染色體中進行相應賦值;以初始操作任務為對照,依據就近原則將剩下的任務逐一分配給相應的場橋,從而形成β染色體。這樣即產生初始代種群中的一個個體。通過模擬M個個體生成初始代種群,其中M為算法中代際間種群的規(guī)模。這樣的個體既可最大程度地使解滿足安全距離條件的約束,又能得到比較優(yōu)的解,使算法以較快的速度收斂到最優(yōu)解。

2.4 遺傳算子

代際間種群遺傳過程包括個體間的選擇、交叉和變異。[9]對于每個優(yōu)化問題,所使用的選擇算子、交叉算子和變異算子及遺傳策略都有可能直接影響到求解算法的收斂效果。

2.4.1選擇算子

為模擬生物種群“優(yōu)勝劣汰”和“適者生存”的演化方式,在各代種群中執(zhí)行所選用的個體選擇機制,以保證整體朝著較優(yōu)的方向進化，常用的方法有最優(yōu)化選擇、輪盤賭選擇和錦標賽選擇等。在經典的遺傳算法中,會先從父代種群中選擇出中間代種群,再經過交叉和變異生成子代種群。在這種情況下,最優(yōu)化選擇會直接淘汰適應度較差但帶有優(yōu)秀基因的個體;輪盤賭選擇雖然能彌補上述最優(yōu)化選擇的缺陷，但對于大規(guī)模問題,當種群中存在極優(yōu)的局部最優(yōu)個體時,反而容易引發(fā)算法的“早熟”現象。

2.4.2交叉算子

本試驗的各項數據表明，不同煉苗方法對煙株生長發(fā)育和產值產量或多或少都有一些影響。本試驗處理3的煙株總體表現相對較好，可能是處理3煉苗方法能夠使煙苗長壯，更好、更快地適應大田環(huán)境。其他2個處理則隨著煉苗強度的減小，農藝性狀相應變差，但主要表現在產量上有明顯減少。所以，合理煉苗可以提高煙葉的產量。因此，煉苗對于培育優(yōu)質煙是必不可少的一個關鍵工序。今后應根據品種的特點和當地生態(tài)條件采用不同的煉苗方法，以保證煙葉的質量、產量滿足工業(yè)需求。

2) 約束條件為

2.4.3變異算子

在場橋作業(yè)時間的均衡化方面,為使算法更高效地收斂于最優(yōu)解,采用“人工誘導變異”的方式進行定向變異。變異的大致過程為：通過計算每個場橋操作最后一項任務的結束時刻,得到所有場橋的作業(yè)時間,若作業(yè)時間最長的場橋的任務數多于1項,則將最后一項任務調配給作業(yè)時間最短的場橋作為其最后一項任務,否則將最后一項任務與作業(yè)時間最短的場橋的最后一項任務互換,從而形成變異的新個體。

a)

b)

上述構建的集裝箱堆場場橋智能調度優(yōu)化模型屬于不帶裝載能力約束的完全開放式車輛路徑問題。模型自身的特點決定著其很難獲得精確的解法。為此，設計基于遺傳算法的模型求解程序，實現對第2部分構建的調度優(yōu)化模型的最優(yōu)化求解。

在算法中,變異算子僅需變更或互換β染色體的編碼。例如：若圖1a)中場橋1的作業(yè)時間長于場橋2,則將β染色體上場橋1對應的最后一個編碼變更為2;若圖1b)中場橋2的作業(yè)時間長于場橋1,則將β染色體上場橋2對應的最后一個編碼變更為1。上述變異結果分別見圖3a)及圖3b)。

a)b)

圖3 雙染色體的變異示意

2.4.4遺傳策略

下列是獲得的體外數據，但其臨床意義尚不清楚。下列細菌至少90%顯示低于或等于阿奇霉素對相似屬或菌群的分離菌株敏感折點的體外最小抑菌濃度（MIC）。然而，阿奇霉素治療由這些細菌引起的臨床感染的有效性，尚未在充分的良好對照的臨床試驗中確定。

在一定的交義率Pc和變異率Pm下,算法先對父代種群進行充分交叉及變異,即任取種群中2個個體執(zhí)行上述交叉算子和變異算子,得到中間代種群。同時,在中間代種群中實行“精英保留策略”,即將父代種群以精英的形式保留到中間代種群中,則中間代種群的規(guī)模約為M(M-1)Pc+M。對于中間代種群,在選擇算子上采用最優(yōu)化選擇的方法,并將適應度函數作為種群“優(yōu)勝劣汰”的唯一準則。隨后結合安全距離的標記變量(即f取值的標示),從滿足安全距離約束的所有個體中選擇出足夠多的優(yōu)秀個體,形成子代種群。若滿足安全距離約束的個體總數少于M,則用不滿足安全距離約束的優(yōu)秀個體進行補充,以維持子代種群的規(guī)模。

3 算法驗證及對比分析

基于廈門港海天碼頭的實際運營數據，應用提出的優(yōu)化模型和算法進行計算，通過與實際作業(yè)及其他優(yōu)化算法相對比,驗證所構建的優(yōu)化模型的有效性及用于求解的算法的顯著性。

5.由于國家對無形資產研發(fā)支出資本化和費用化的規(guī)定不夠清晰明確，企業(yè)通過將研發(fā)支出資本化來平滑企業(yè)利潤是一種更為隱蔽的手段，既能夠保障賬面價值的穩(wěn)定增長，贏得投資者滿意，又能夠帶來一定的利潤增長。因此可得出結論，盈余比前一年下降的企業(yè)更愿意將研發(fā)支出資本化。

該港口各箱區(qū)左右兩側均有30個貝位,中間過道和兩側均有場橋的轉場板。對于場橋等待時間的罰金和集卡等待時間的罰金，可根據港口管理者的具體偏好設定,若更注重港口的效率和運營成本,則可提高場橋等待時間的罰金。在該實例中,港口管理者更傾向于維護用戶的利益,因此將場橋與集卡的相關參數設置為表1所示的數值。

表1 場橋與集卡的參數設定

在模型中,假定集卡期望在其到達的30 min內被服務,即LTi=ETi+30。這里選取該港口出口箱區(qū)中4個箱區(qū)75 min內集卡到達的40項任務,具體數據見表2。針對本文的優(yōu)化模型，在算法的參數中：取父代和子代等代際間種群的規(guī)模M=75；取算法遺傳的終止代數G=20；將交叉率和變異率分別設置為Pc=0.95及Pm=0.05。對文獻[5]中的模擬退火算法相關參數進行以下設置：初始溫度為50 000 ℃，終止溫度為10 ℃，降溫系數為0.999 75，對每個溫度增設10次內循環(huán)。同時，根據所得的結果,由式(1)計算相應的函數值，將其與本文涉及的遺傳算法的優(yōu)化結果相比較。

表2 實例數據

設計遺傳算法的計算機求解程序,并通過使用MATLAB軟件編程實現；在Inter(R) Core(TM) i5-6500 CPU @3.2GHz 8GB內存及Windows 7 64位操作系統(tǒng)中模擬運行，得到遺傳算法的運行結果,并將其與實際人工操作及文獻[5]所設計的模擬退火算法相對比，結果見表3。

從表3中可看出，與實際人工操作相比，本文的算法可有效縮短作業(yè)時間，降低運作成本。此外，從作業(yè)時間、目標函數值和算法運行時間等3個方面與文獻[5]中采用的模擬退火算法相比，本文采用的遺傳算法更優(yōu)，更具適應性，收斂性更強。對于本文算法3個解的結果，除了場橋操作任務的次序略有區(qū)別之外，所分配到的操作任務是完全相同的。這充分說明在操作任務的分配上，本文采用的遺傳算法已“收斂”到接近最優(yōu)解。雖然以種群的方式啟發(fā)式地對優(yōu)化問題進行求解，但往往也容易引發(fā)“早熟”現象。上述對比結果恰恰說明本文算法所采用的遺傳策略能有效規(guī)避“早熟”現象。

表3 運行結果及對比分析

4 結束語

本文針對港口集裝箱場橋的調度問題進行系統(tǒng)化研究，構建多箱區(qū)多場橋的調度優(yōu)化模型，通過優(yōu)化調度過程使場橋調度移動成本與場橋、集卡之間等待罰金之和最小化，并運用遺傳算法對優(yōu)化模型進行求解，同時利用實例港口的數據對模型和算法的有效性進行驗證。由研究結果可知，本文建立的優(yōu)化模型能有效避免場橋與場橋之間的安全距離問題，減少場橋移動過程中產生的不必要的等待時間，并可有效均衡多個場橋之間的工作時間，使場橋司機的工作效率得到有效保障。在實際操作中，場橋的工作效率受眾多因素的影響，因此對堆場布局優(yōu)化、岸橋與場橋聯合調度和多種優(yōu)化算法的聯合求解等問題進行研究將是下一階段的工作重點。

[1] LEE D H， CAO Z， MENG Q. Scheduling of Two-Tanstainer Systems for Loading Outbound Containers in Port Container Terminal with Simulated Annealing Algorithm[J]. International Journal of Production Economics，2007，107(1):115-124.

[2] SAFAEI N，BAZZAZI K.A Genetic Algorithm to Solve the Storage Space Allocation Problem in a Container Terminal [J]. Computers & Industrial Engineering，2008，12:1-10.

[3] 毛鈞，李娜.基于混堆模式的集裝箱碼頭堆場空間資源配置優(yōu)化[J].大連海事大學學報，2014，40(1)：117-122.

[4] 鄭紅星,吳岳,楊文滔,等.混堆模式下多箱區(qū)場橋聯合調度[J].水運工程，2015，4(1)：113-118.

[5] 初良勇,李淑娟,阮志毅.多箱區(qū)多場橋調度優(yōu)化模型及算法實現[J].上海海事大學學報，2017,38(1):48-53.

[6] 康海貴，劉艷.基于混堆的集裝箱堆場動態(tài)箱位分配研究[J].水運工程，2009(8)：73-83.

[7] 張超群,鄭建國,錢潔.遺傳算法編碼方案比較[J].計算機應用研究，2011,28(3): 819-822.

[8] 馮興杰,陳素敏.進近階段飛機著陸調度優(yōu)化[J].計算機工程與設計，2013,34(3): 1023-1028.

[9] 周冬梅,孫俊.遺傳規(guī)劃中遺傳算子對種群多樣性的影響[J].計算機工程與應用，2016,52(20): 39-45.

[10] 李書全,孫雪,孫德輝,等.遺傳算法中的交叉算子的述評[J].計算機工程與應用，2012,48(1): 36-39.

IntelligentSchedulingOptimizationofYardCraneinContainerTerminalBasedonGeneticAlgorithm

CHULiangyong1，RUANZhiyi2,LIShujuan3

(1. Modern Logistics Institute, Jimei University, Xiamen 361021, China; 2. R&D Department, Xiamen Yaxon Network Co., Ltd., Xiamen 361008, China; 3. Management Institution, Yangen University, Quanzhou 362000, China)

An optimizing model for intelligent scheduling of yard cranes is set up. Considered the characteristics of the model, a genetic algorithm is designed to solve the optimizing model. An example is used to illustrate the validity of the optimizing model. Compared with the practical operation and previously used algorithm, the model and solving algorithm can greatly shorten the operation time and reduce the operation cost.

waterway transportation; port logistics; container yard; crane scheduling; genetic algorithm

2017-11-15

福建省自然科學基金(2017J01796;2017J01797);集美大學研究生教育教學改革項目(2016)

初良勇(1973—)，男，黑龍江訥河人，副教授，碩士生導師，博士，研究方向為交通運輸系統(tǒng)規(guī)劃、國際航運與物流管理等。E-mail:chuliangyong@163.com

1000-4653(2018)01-0048-05

U691

A