基于遺傳算法的自動化集裝箱碼頭雙軌道吊協(xié)同調(diào)度優(yōu)化研究

黃繼偉 韓曉龍

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

0 引 言

隨著經(jīng)濟全球化進程的加快和世界經(jīng)濟貿(mào)易高速發(fā)展，集裝箱港口得到迅猛發(fā)展，各集裝箱港口吞吐量持續(xù)快速增長。為滿足集裝箱船舶大型化和航運聯(lián)盟化的需求，安全、高效、環(huán)保、節(jié)能的自動化集裝箱碼頭ACTs(Automated Container Terminalss)備受青睞。建設(shè)自動化集裝箱碼頭成為全球各大港口的內(nèi)在需求和發(fā)展趨勢。

碼頭堆場作業(yè)是集裝箱港口運作的重要部分。自動化集裝箱碼頭的堆場各箱區(qū)一般配置兩臺相同的兩端式自動化軌道吊ASCs(Automatic Stacking Cranes)。兩臺軌道吊共用相同的軌道且不可互相穿越通過。軌道吊是集裝箱港口作業(yè)的瓶頸，雙ASC的協(xié)同調(diào)度直接影響到港口整體運行效率。在自動化集裝箱碼頭文獻研究方面，文獻[1]對堆場作業(yè)相關(guān)研究如裝卸運輸設(shè)備等進行了深入的概述，重點介紹了當(dāng)前的行業(yè)趨勢和發(fā)展?fàn)顩r，提出了堆場作業(yè)分類方法，并對2004年—2012年間發(fā)表的科研期刊論文進行了分類。文中還探討了現(xiàn)有的堆場作業(yè)模式，最后根據(jù)集裝箱碼頭行業(yè)的發(fā)展趨勢指出新的研究點。碼頭堆場作業(yè)是集裝箱港口運作的重要部分。在自動化集裝箱碼頭中，自動化軌道吊ASCs的采用大幅提升了港口整體運行效率，軌道吊的調(diào)度策略直接影響到碼頭生產(chǎn)運營。文獻[2]對集裝箱碼頭的主要物流流程和運營情況的現(xiàn)有研究情況進行了詳盡描述和分類，并對相關(guān)優(yōu)化方法進行了全面調(diào)研。Vis等[3]將自動化集裝箱碼頭堆場內(nèi)集裝箱的存取問題視為農(nóng)村郵路問題的一個特例，并將該問題重新定義為一個不對稱的Steiner旅行商問題，以重構(gòu)方式在部分問題二分網(wǎng)絡(luò)中的最優(yōu)分配以及這些部分之間連接的動態(tài)規(guī)劃組合來有效解決ASC調(diào)度問題以實現(xiàn)優(yōu)化。文獻[4]全面研究了自動化集裝箱碼頭堆場不同領(lǐng)域的路線規(guī)劃中的各種問題。提出了基于集裝箱裝卸問題的數(shù)學(xué)分析模型，并考慮箱區(qū)長度、作業(yè)流暢度及安全距離等因素，開發(fā)了一種基于遺傳算法的最優(yōu)路徑規(guī)劃方法。最后通過實驗算例驗證了該算法的有效性，為提高集裝箱裝卸效率探索出了一條新途徑。文獻[5]針對自動化碼頭并行式雙ASC調(diào)度問題首次對雙ASC優(yōu)先級進行對比分析，并量化了所選優(yōu)先級的影響，提出了14條雙ASC優(yōu)先規(guī)則，并通過仿真對完工時間進行了評估。最后將優(yōu)先級規(guī)則與使用分支定界法求得的最優(yōu)優(yōu)先級進行比較，得到最優(yōu)的單調(diào)度規(guī)則和調(diào)度規(guī)則組合。文獻[6]就集裝箱碼頭并行式雙ASC在海側(cè)完成進口集裝箱存箱作業(yè)的調(diào)度問題進行了探索，考慮雙ASC之間的作業(yè)干擾和ASC優(yōu)先權(quán)問題，以總完工時間最小化為目標(biāo)，提出了基礎(chǔ)問題的復(fù)雜性證明，并引入和測試了高效的啟發(fā)式算法。文獻[7]探討了由雙ASC合作完成裝卸任務(wù)對任務(wù)執(zhí)行效果的影響，開發(fā)啟發(fā)式算法求解并通過算例對算法性能進行評估。文獻[8]也針對作業(yè)任務(wù)已分配完成的情況探討了兩端式和穿越式兩種軌道吊配置的優(yōu)先作業(yè)順序問題，建立相應(yīng)的圖形模型并開發(fā)強多項式算法進行求解。

針對堆場存箱或取箱的單一類型作業(yè)問題，文獻[9]探討了單箱區(qū)內(nèi)海陸側(cè)集裝箱存取作業(yè)的雙ASC調(diào)度問題，以雙ASC完工時間最小化為目標(biāo)，建立整數(shù)規(guī)劃模型并提出了兩種算法對該問題進行求解。文獻[10]就洋山四期自動化集裝箱碼頭的雙ASC協(xié)同調(diào)度問題進行了研究。通過分析任意兩個任務(wù)之間的最小時間間隔來量化ASC之間的干擾，建立了三個數(shù)學(xué)模型，以最小化總完工時間對集裝箱作業(yè)任務(wù)進行排程。設(shè)計精確算法和遺傳算法來解決該問題，同時就所提出的模型和算法對實際自動化集裝箱碼頭的管理理念和技術(shù)方面的應(yīng)用進行了探討。文獻[11]針對堆場同一箱區(qū)內(nèi)存箱或取箱的單一作業(yè)，考慮雙起重機時空同步約束條件，以最小化作業(yè)總完成時間為目標(biāo)建立雙起重機調(diào)度混合整數(shù)規(guī)劃模型，并設(shè)計遺傳算法對大規(guī)模任務(wù)數(shù)量問題進行求解。算例分析結(jié)果表明，在大規(guī)模問題上遺傳算法在解的質(zhì)量上逐漸優(yōu)于CPLEX算法且運算時間遠小于CPLEX，證明了該雙起重機調(diào)度模型與算法的有效性及合理性。

針對接力區(qū)或緩沖區(qū)的設(shè)計問題，文獻[12]探索了自動化集裝箱碼頭海陸側(cè)接力區(qū)的設(shè)計對雙自動化軌道吊作業(yè)性能的影響。以任務(wù)總完工時間或因作業(yè)干擾造成的ASC等待時間最小化為目標(biāo)，通過變換堆場設(shè)計條件如ASC作業(yè)方式、接力區(qū)中集裝箱對方位置以及接力區(qū)的有無、大小、數(shù)量等，并針對不同條件開發(fā)多種啟發(fā)式方法進行求解。文獻[13]通過對成對自動堆垛起重機在堆場實時調(diào)度問題的研究。建立了以最小化外集卡和船舶延時為目標(biāo)的不對稱的多旅行商模型，引入了接力、緩沖、干擾等關(guān)鍵約束，并利用并行實時調(diào)度策略對多組情景進行案例研究分析。結(jié)果表明設(shè)置主緩沖區(qū)以及接力區(qū)可以減少作業(yè)延時且海側(cè)作業(yè)量較多時，增加緩沖區(qū)的容量可以更有效地增加作業(yè)效率。

現(xiàn)有研究多只針對堆場存箱或取箱操作的單一作業(yè)類型進行探討，而對于單箱區(qū)內(nèi)考慮存箱和取箱作業(yè)同時進行以及接力區(qū)的設(shè)計的研究相對較少。本文同時考慮進、出口箱的存取操作，以任務(wù)完成總時間最小化為目標(biāo)，建立雙軌道吊協(xié)同調(diào)度混合整數(shù)規(guī)劃模型，有效避免ASC之間作業(yè)干擾，并用CPLEX和遺傳算法對不同規(guī)模算例進行求解。

1 問題描述

目前，國際上自動化集裝箱港口堆場多采用垂岸式布局，雙ASC協(xié)同作業(yè)完成對進出于堆場的各種集疏港和裝卸船的集裝箱的裝卸操作。堆場箱區(qū)布局如圖1所示。當(dāng)碼頭裝卸任務(wù)下達后，分配到各箱區(qū)的集裝箱需要在最短的時間內(nèi)處理完畢，這對各箱區(qū)內(nèi)設(shè)備的集裝箱處理能力提出了更高的要求。兩臺相同的軌道吊在完成各自的裝卸任務(wù)時往往發(fā)生作業(yè)干擾。若在箱區(qū)中設(shè)置接力區(qū)，使雙ASC通過接力完成集裝箱存取操作，即可大幅減少雙ASC的作業(yè)干擾頻率。因此，確定合適的接力區(qū)位置、有效避免雙ASC作業(yè)干擾成為優(yōu)化堆場作業(yè)、提高堆場作業(yè)效率的關(guān)鍵。

圖1 自動化集裝箱港口箱區(qū)布局示意圖

為有效解決雙ASC存取箱操作同時進行的協(xié)同調(diào)度干擾問題，采用以下任務(wù)拆分規(guī)則：箱區(qū)中設(shè)接力區(qū)(Handshake area)，接力區(qū)大小為1貝。凡需要跨越接力區(qū)才能完成的任務(wù)均以接力區(qū)為界限進行拆分，即每個符合要求的初始任務(wù)均拆分為兩個子任務(wù)，并分別由海陸兩側(cè)SAC協(xié)作完成存取操作。同一箱區(qū)內(nèi)海、陸側(cè)兩端各設(shè)有一個集裝箱交接區(qū)，又稱為I/O點(I/O point)，集港或疏港的外集卡與陸側(cè)ASC在陸側(cè)I/O點進行交接，對應(yīng)的載有集裝箱的自動導(dǎo)引車AGVs(Automated Guided Vehicles)與海側(cè)ASC在海側(cè)I/O點進行交接。各ASC只能在各自半箱區(qū)內(nèi)作業(yè)，跨越半箱區(qū)的作業(yè)任務(wù)均需雙ASC利用接力區(qū)合作完成，雙ASC之間的作業(yè)干擾只發(fā)生在接力區(qū)。假設(shè)箱區(qū)長度為L貝位，貝位數(shù)為0的箱位為海側(cè)ASC與AGV的交接點，貝位數(shù)為L+1的箱位為陸側(cè)ASC與外集卡的交接點。海陸兩側(cè)ASC作業(yè)范圍分別跨越半箱區(qū)，雙ASC分別負(fù)責(zé)本側(cè)集裝箱的裝卸作業(yè)。堆場作業(yè)任務(wù)主要分為存箱操作S型(Storage requests)和取箱操作R型(Retrieval requests)兩種。將海側(cè)ASC與AGV交接點和陸側(cè)ASC與外集卡交接點均稱為交接點，將存箱操作中集裝箱的存放位置及取箱操作中集裝箱的提取位置均稱為目標(biāo)點。故堆場ASC存箱和提箱作業(yè)過程均可簡化為4個步驟，如表1所示。

表1 存箱和提箱操作步驟

引入時間-貝位坐標(biāo)系，其中橫軸為各任務(wù)的執(zhí)行時刻，縱坐標(biāo)為對應(yīng)集裝箱的位置，各操作步驟與圖中各曲線段一一對應(yīng)，如ASC無需移動即可完成存取操作則無對應(yīng)線段。通過找到坐標(biāo)中對應(yīng)線段的分段函數(shù)圖像交點可簡明直觀地描述出雙ASC之間作業(yè)干擾是否發(fā)生或發(fā)生在何處。雙ASC作業(yè)干擾問題轉(zhuǎn)化為所有子任務(wù)的時間-貝位曲線不相交問題。

符合拆分規(guī)則的初始任務(wù)經(jīng)拆分后，子任務(wù)之間的干擾只發(fā)生在接力區(qū)位置，這樣可以有效避免雙ASC在執(zhí)行任務(wù)時的相互干擾。任意兩個緊前緊后關(guān)系的子任務(wù)i、j在接力區(qū)位置的干擾狀態(tài)均滿足圖2中4種模式的一種。任務(wù)i、j分別由不同的ASC執(zhí)行，各子任務(wù)一經(jīng)確定，除ASC完成上一任務(wù)后移動至下一任務(wù)的銜接作業(yè)狀態(tài)不確定外，其余三個連續(xù)步驟均隨之確定。線段斜率為非負(fù)時表示該步驟中ASC處于運動狀態(tài)，且移動速率為恒值v；線段斜率為0時表示ASC正在執(zhí)行存取操作，且各操作需固定作業(yè)時間τ。

(a) “TT”模式 (b) “ST”模式

(c) “TS”模式 (d) “SS”模式圖2 有接力區(qū)設(shè)計下任務(wù)的4種干擾模式

每種干擾模式下子任務(wù)關(guān)系均可能存在兩種情形，分別如圖2 中虛、實線圖形所示。子任務(wù)的開始和結(jié)束狀態(tài)分別用“S”和“T”表示，根據(jù)ASC在接力區(qū)位置執(zhí)行前后任務(wù)的操作步驟。將(a)兩種情形定義為“TT”干擾模式，表示雙ASC發(fā)生干擾時其在接力區(qū)位置分別執(zhí)行的任務(wù)i、j均處于結(jié)束狀態(tài)；同理，將(b)兩種情形定義為“ST”干擾模式，表示雙ASC發(fā)生干擾時其在接力區(qū)位置分別執(zhí)行的任務(wù)i處于開始狀態(tài)，任務(wù)j處于結(jié)束狀態(tài)；將(c)兩種情形定義為“TS”干擾模式，表示雙ASC發(fā)生干擾時其在接力區(qū)位置分別執(zhí)行的任務(wù)i處于結(jié)束狀態(tài)，任務(wù)j處于開始狀態(tài)；將(d)兩種情形定義為“SS”干擾模式，表示雙ASC發(fā)生干擾時其在接力區(qū)位置分別執(zhí)行的任務(wù)i、j均處于開始狀態(tài)。

2 模型建立

為簡化流程同時不失一般性，根據(jù)問題作以下假設(shè)：(1) ASC在箱區(qū)兩端裝卸作業(yè)時無需等待；(2) 接力區(qū)存儲空間足夠大；(3) 雙ASC勻速移動且速率相同；(4) 雙ASC取箱和放箱的固定作業(yè)時間相同且為固定值；(5) 忽略ASC加速與減速及小車移動的影響。ASC裝卸作業(yè)滿足以下要求：(1) 雙ASC之間需保持一定的安全距離，通常為一個貝位；(2) 雙ASC不能同時對同一集裝箱執(zhí)行裝卸任務(wù)，且拆分后的子任務(wù)有明顯的先后順序，即一臺ASC將集裝箱移動至接力點并安全退出后，另一ASC方能對該集裝箱執(zhí)行下一階段的操作。

相關(guān)符號說明：

Jk：第k臺ASC的任務(wù)集，k=1, 2；

A={(i,j)|i∈Jk,j∈Jl,k≠l}，同一任務(wù)拆分后的子任務(wù)對{i,j}的集合；

J：所有ASC的任務(wù)集，J=Jk∪Jk；

B={0,…,L+1}：貝位集，其中L為箱區(qū)長度，0表示海側(cè)I/O點的貝位，L+1表示陸側(cè)I/O點的貝位；

exB：雙ASC作業(yè)接力區(qū)的貝位；

v：ASC水平移動速率；

τ：ASC提箱或存箱作業(yè)的固定作業(yè)時間；

Tij：ASC從任務(wù)i的結(jié)束位置到任務(wù)j的開始位置的移動時間，特別地，當(dāng)i=j時，Tij表示ASC從任務(wù)i的開始位置到其結(jié)束位置的移動時間；

T：任務(wù)總完工時間。

決策變量定義如下：

si：任務(wù)i的開始時刻，i∈J；

ti：任務(wù)i的結(jié)束時刻，i∈J；

ui∈{0,1}，當(dāng)ASC從任務(wù)i開始作業(yè)時ui=1；

vi∈{0,1}，當(dāng)ASC在任務(wù)i結(jié)束作業(yè)時vi=1；

xij∈{0,1}，任務(wù)i,j為緊前緊后關(guān)系且被同一ASC執(zhí)行時xij=1；

yij∈{0,1}，i∈Jk,j∈Jl,k≠l，任務(wù)i早于任務(wù)j被執(zhí)行且i和j被不同ASC執(zhí)行時yij=1；

σ：兩ASC作業(yè)的安全距離；

M為一足夠大的正數(shù)。

根據(jù)上述信息建立混合整數(shù)規(guī)劃模型：

MinT=max{ti}

(1)

ti≥si+2τ+Tii?i∈J

(2)

sj≥ti+Tij+M(1-xij) ?i,j∈Jk,k=1,2

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

si≥T0i-M(1-ui) ?i∈Jk,k=1,2

(11)

sj≥ti+σ?{i,j}∈A

(12)

式(1)表示模型目標(biāo)為最小化作業(yè)總完工時間。約束條件式(2)表示同一任務(wù)的起始時間關(guān)系；約束條件式(3)表示任意兩個任務(wù)之間的起止時間關(guān)系；約束條件式(4)、式(5)保證了同一ASC每次只能執(zhí)行一個任務(wù)；約束條件式(6)表示任務(wù)執(zhí)行時間與執(zhí)行該任務(wù)的ASC的位置關(guān)系；約束條件式(7)-式(10)分別表示在“TT”、“ST”、“TS”和“SS”4種干擾模式下雙ASC執(zhí)行任意一組緊前緊后任務(wù)對{i,j}時均須保持一定的安全距離；約束條件式(11)是對作業(yè)初始化進行定義；約束條件式(12)表示對于由同一任務(wù)拆分來的緊前緊后子任務(wù)對{i,j}之間的作業(yè)先后關(guān)系。

對于大規(guī)模問題，很難直接求解。下面給出遺傳算法。

3 遺傳算法

3.1 參數(shù)設(shè)置

某自動化集裝箱港口垂岸式堆場采用兩端式雙ASC布置，兩臺同型號的軌道吊C1(即海側(cè)ASC)和C2(即陸側(cè)ASC)協(xié)同完成作業(yè)任務(wù)。箱區(qū)長度為39貝位，接力區(qū)初始位置為第20貝位，第0貝位表示海側(cè)ASC與AGV的交接點，第40貝位為表示陸側(cè)ASC與外集卡的交接點；雙ASC勻速移動且速度相同，單位時間(設(shè)為1 s)內(nèi)移動距離為1貝；ASC取箱和放箱的固定作業(yè)時間為3 s；兩臺軌道吊作業(yè)干擾只發(fā)生在接力區(qū)，雙ASC間須保持安全距離1貝，顯然在數(shù)值上有δ=1/v。

3.2 算法設(shè)計

遺傳算法具有良好的全局搜索能力，它通過模仿自然界的選擇與遺傳的機理，利用迭代尋求全局最優(yōu)，并利用其內(nèi)在并行性，方便地進行分布式計算以加快求解速度，對作業(yè)調(diào)度類問題具有良好的適應(yīng)性[14]。

3.2.1 選 擇

適應(yīng)度函數(shù)由最小化 ASC 作業(yè)完工時間的目標(biāo)函數(shù)轉(zhuǎn)化而來，并采用比較經(jīng)典的錦標(biāo)賽選擇方法選擇個體。

3.2.2 編碼與解碼

在對任務(wù)序列進行編號時，初始任務(wù)規(guī)模為n，則任務(wù)i與n+i表示由同一初始任務(wù)i拆分而來的子任務(wù)，且i為緊前任務(wù)。例如當(dāng)n=4(初始序列為0,1,2,3)時，若任務(wù)0,2,3需要被拆分，則子任務(wù)序列為(0,1,2,3,4,6,7)，如表2所示。當(dāng)解碼染色體時，由同一初始任務(wù)拆分得到的先出現(xiàn)的子任務(wù)實際被優(yōu)先執(zhí)行或在接力區(qū)享有優(yōu)先權(quán)。

表2 任務(wù)編號示例

現(xiàn)有10個初始任務(wù)，根據(jù)任務(wù)拆分規(guī)則得到18個子任務(wù)，由兩臺ASC協(xié)作完成。染色體由兩條組成，分別為任務(wù)段和ASC段，任務(wù)段中的基因分別對應(yīng)各子任務(wù)，ASC編號由各子任務(wù)被執(zhí)行的情況而定，C1需完成[0,2,3,6,9,11,14,17,18]，C2需完成[1,4,5,7,8,10,12,13,16]。染色體編碼解碼情況如圖3所示。

圖3 染色體編碼解碼示意圖

3.2.3 交 叉

交叉運算是產(chǎn)生新個體的主要方法，它決定了遺傳算法的全局搜索能力，在遺傳算法中起關(guān)鍵作用。本文采用PMX交叉方法，首先隨機選擇一對父代染色體中幾個基因的起止位置，然后交換這兩組基因的位置，最后做沖突檢測，根據(jù)交換的兩組基因建立一個映射關(guān)系。所有沖突的基因經(jīng)過映射，形成新一對沒有沖突的子代基因。PMX交叉如圖4所示。

圖4 染色體PMX交叉示意圖

3.2.4 變 異

染色體包含任務(wù)段和ASC段，選擇兩組等位基因進行變換。變異運算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力。變異運算示意圖如圖5所示。

圖5 染色體變異示意圖

3.3 結(jié)果分析

3.3.1 算法性能分析

設(shè)置6組不同規(guī)模的算例對兩種算法的性能進行評估，假設(shè)接力區(qū)處于箱區(qū)中間位置(第20貝位)。遺傳算法求解時參數(shù)設(shè)置為種群規(guī)模N=200，交叉概率cxpb=0.5，變異概率mutpb=0.1，迭代次數(shù)ngen=300，使用相同的參數(shù)運算10次取平均值。兩種方法求解結(jié)果如表3所示。

表3 CPLEX與遺傳算法求解不同規(guī)模算例性能結(jié)果對比

求解過程中，當(dāng)算例規(guī)模較大時，CPLEX運行內(nèi)存溢出，但仍可以找到可行解。由表3易知，兩種算法性能對比發(fā)現(xiàn)，即使CPLEX的內(nèi)存管理非常有效，但是求解較大規(guī)模的線性規(guī)劃問題，內(nèi)存不足仍然是需要考慮的問題之一，而遺傳算法求解大規(guī)模算例具有獨特優(yōu)勢。

3.3.2 雙ASC作業(yè)干擾優(yōu)化分析

當(dāng)自動化集裝箱碼頭的裝卸任務(wù)下達后，分配到各箱區(qū)的集裝箱需要在最短的時間內(nèi)處理完畢，這對各箱區(qū)內(nèi)設(shè)備的集裝箱處理能力提出了更高的要求。兩臺相同的軌道吊在完成各自的裝卸任務(wù)時往往發(fā)生作業(yè)干擾。若在箱區(qū)中設(shè)置接力區(qū)，使雙ASC通過接力完成集裝箱存取操作，即可大幅降低雙ASC的作業(yè)干擾頻率。因此，確定合適的接力區(qū)位置、有效避免雙ASC作業(yè)干擾成為優(yōu)化堆場作業(yè)、提高堆場作業(yè)效率的關(guān)鍵。針對第2組實例運用CPLEX和遺傳算法對該問題進行求解，并評估兩種方法對堆場設(shè)備協(xié)同調(diào)度的優(yōu)化效果。當(dāng)變換接力區(qū)位置時，求得的不同接力區(qū)位置對應(yīng)的最小總完工時間結(jié)果如圖6所示。

圖6 CPLEX與GA求解結(jié)果對比

由圖6可知，兩種方法所求接力區(qū)最優(yōu)位置均為第18貝位。CPLEX求得的最小總完工時間為218 s，雙ASC在作業(yè)過程中未發(fā)生干擾，求解歷時637.53 s；采用遺傳算法，每組重復(fù)10次運算后取最優(yōu)值，求得的最小總完工時間為225 s，雙ASC在第151 s發(fā)生一次干擾，平均求解歷時86.033 s。兩種算法求得的雙ASC作業(yè)軌跡分別如圖7和圖8所示。

圖7 exB=18時CPLEX求解雙ASC作業(yè)軌跡

圖8 exB=18時GA求解雙ASC作業(yè)軌跡

兩種方法均找到了相同的最優(yōu)接力區(qū)位置，生成的ASC作業(yè)計劃不同，且CPLEX求得的解更優(yōu)，避免了雙ASC干擾問題。但遺傳算法也有效降低了干擾的發(fā)生，并展示出了更高效的求解能力。如果統(tǒng)一采用表2所示的任務(wù)編號方式，則CPLEX求得的雙ASC作業(yè)計劃為：

C1：6—9—0—14—2—11—3—17—18

C2：4—5—1—10—7—12—8—13—16

遺傳算法求得的雙ASC作業(yè)計劃為：

C1：6—0—9—3—17—11—2—14—18

C2：7—16—1—5—4—13—12—8—10

根據(jù)上述兩種優(yōu)化方法，只要給定任意的堆場既定作業(yè)任務(wù)，均可確定出最優(yōu)的接力區(qū)位置，有效解決雙ASC作業(yè)干擾問題，并生成各ASC的作業(yè)計劃，使總完工時間最小。

3.3.3 遺傳算法優(yōu)化分析

當(dāng)有集裝箱船舶靠泊或集疏港相對集中時，自動化集裝箱碼頭往往需要應(yīng)對大規(guī)模的裝卸任務(wù)。由3.3.1節(jié)可知遺傳算法是求解該類問題非常有效的方法，因此，對遺傳算法的參數(shù)設(shè)置進行優(yōu)化也是高效準(zhǔn)確求得最優(yōu)解、快速得到堆場設(shè)備調(diào)度計劃的重要內(nèi)容。為更直觀地反映收斂效果，選擇初始任務(wù)規(guī)模為50的第4組實例進行研究。

當(dāng)變換迭代次數(shù)時，設(shè)計50、100、200、300和500五個梯度求解，結(jié)果如圖9所示。易知當(dāng)?shù)螖?shù)取300和500時收斂效果最佳，為提高運算效率，迭代次數(shù)取300為宜。同理，通過變換種群規(guī)模發(fā)現(xiàn)當(dāng)種群規(guī)模為300時收斂效果更佳，結(jié)果如圖10所示。

圖9 不同迭代次數(shù)收斂曲線

圖10 不同種群規(guī)模收斂曲線

對于提高遺傳算法求解效率而言，交叉概率cxpb與變異概率mutpb的選取并不是相互無關(guān)和獨立的，而是存在最優(yōu)組合問題。針對不同類型的優(yōu)化問題，所選取的變異率一般隨交叉率的增大而呈減小趨勢[15]。因此為提高求解效率，設(shè)置幾組交叉率—變異率組合如表4所示。

表4 交叉率—變異率組合

取種群規(guī)模和迭代次數(shù)均為300，根據(jù)表3得出各交叉率—變異率組合的收斂圖像如圖11所示。易知當(dāng)交叉概率為0.4、變異概率為0.1時收斂效果最佳。當(dāng)接力區(qū)位置在箱區(qū)中間貝位(exB=20)時，在種群規(guī)模為300、交叉概率為0.4、變異概率為0.1條件下迭代300次得到完成該50個任務(wù)的最短完工時間為1 046 s，求解過程平均歷時241.52 s。經(jīng)優(yōu)化，所得結(jié)果較表1更優(yōu)，求解時間也大幅縮短，充分論證了該組遺傳算法參數(shù)優(yōu)化結(jié)果的有效性。該參數(shù)配置下收斂曲線如圖12所示，雙ASC作業(yè)軌跡如圖13所示。

圖11 不同交叉率—變異率組合收斂曲線

圖12 最優(yōu)參數(shù)配置下收斂曲線

圖13 最優(yōu)參數(shù)配置下雙ASC作業(yè)軌跡圖

4 結(jié) 語

雙軌道吊作業(yè)干擾是自動化集裝箱碼頭堆場存取箱作業(yè)同時進行的核心問題，雙ASC協(xié)同調(diào)度優(yōu)化結(jié)果直接影響港口整體運營效率。本文考慮集裝箱的堆存和取出兩種作業(yè)同時進行的情況，設(shè)計既定任務(wù)下的任務(wù)拆分規(guī)則，以任務(wù)完成總時間最小化為目標(biāo)，建立雙軌道吊協(xié)同調(diào)度混合整數(shù)規(guī)劃模型，并采用CPLEX和遺傳算法對多組算例進行求解，主要結(jié)論如下：

(1) 通過評估不同規(guī)模任務(wù)下求解雙ASC協(xié)同調(diào)度優(yōu)化問題的算法性能，得出遺傳算法更適合求解大規(guī)模設(shè)備調(diào)度問題。

(2) 變換接力區(qū)位置，用CPLEX和遺傳算法兩種方法求解均能找到最優(yōu)接力區(qū)位置，并得到了兩臺ASC各自的作業(yè)計劃，充分論證了所提出的模型和算法解決自動化集裝箱港口雙ASC作業(yè)干擾問題的有效性。

后續(xù)研究重點為自動化集裝箱碼頭堆場接力區(qū)設(shè)計如時間窗條件下動態(tài)接力區(qū)設(shè)計等方面。