基于改進(jìn)麻雀算法的集裝箱裝卸設(shè)備調(diào)度優(yōu)化

王 旭 董春芳

（東北林業(yè)大學(xué)機(jī)電工程學(xué)院，黑龍江 哈爾濱 150000）

港站作業(yè)區(qū)是集裝箱海鐵聯(lián)運(yùn)的重要組成部分，當(dāng)2 個區(qū)域距離較遠(yuǎn)時，需要借助自動導(dǎo)引運(yùn)輸車（AGV）完成集裝箱在兩者之間的往返運(yùn)輸。船到達(dá)港口靠岸后，船上集裝箱通過岸橋吊裝到AGV 上，然后由AGV 運(yùn)至堆場中，由軌道門吊進(jìn)行吊裝擺放。但目前一些作業(yè)區(qū)的裝卸設(shè)備配置不合理、設(shè)備調(diào)度不科學(xué)等，導(dǎo)致集裝箱裝卸作業(yè)效率低下。因此根據(jù)港口作業(yè)模式對裝卸設(shè)備合理配置和作業(yè)調(diào)度優(yōu)化、提高裝卸作業(yè)效率、縮短船舶在港時間以及提高整體運(yùn)輸網(wǎng)絡(luò)服務(wù)水平具有重要作用。

目前許多學(xué)者對這類問題進(jìn)行了研究。Liu[1]等提出了一種適用于直接轉(zhuǎn)運(yùn)和間接轉(zhuǎn)運(yùn)2 種模式的雙目標(biāo)整數(shù)規(guī)劃模型，應(yīng)用NSGA II 進(jìn)行求解，驗證模型有效性。Lu[2]等研究了一個新的約束模型。以優(yōu)化起重機(jī)的綜合調(diào)度問題和卡車行駛路徑，旨在最小化裝卸作業(yè)的最大完工時間。

該文針對裝載作業(yè)過程中集裝箱的存儲位置和各類裝卸設(shè)備的調(diào)度問題，研究“岸橋-AGV-軌道門吊”3 種設(shè)備的協(xié)同作業(yè)調(diào)度，在考慮設(shè)備數(shù)量約束的前提下，以岸橋完成卸載任務(wù)的時間最短為目標(biāo)建立模型，以期更精準(zhǔn)地提升港站作業(yè)效率，避免設(shè)備浪費(fèi)。

1 模型建立

1.1 模型假設(shè)和符號說明

針對港口作業(yè)區(qū)裝卸設(shè)備協(xié)同調(diào)度和配置方案，該文提出如下假設(shè)：1）所建立模型中的集裝箱型號一致。2）各裝卸設(shè)備能夠連續(xù)完成裝卸作業(yè)，并且作業(yè)過程中無故障。3）已知裝卸任務(wù)在船舶和堆場的位置信息和AGV 的初始位置[3]。4）軌道門吊堆放集裝箱時遵循先下后上的原則。

1.2 模型建立

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

建立以最小化作業(yè)完工時間和設(shè)備配置數(shù)量最少為目標(biāo)的混合整數(shù)規(guī)劃模型，如公式（1）所示。

式中：a為作業(yè)完工時間的權(quán)重系數(shù)；b為設(shè)備配置數(shù)量的權(quán)重系數(shù)；為裝卸作業(yè)結(jié)束時間（nk為設(shè)備，i為裝卸集裝箱），k∈{1，2，3}；N為所有裝卸設(shè)備集合。

1.2.2 約束條件

有且只有一個裝卸設(shè)備對每個裝卸任務(wù)進(jìn)行作業(yè)的表達(dá)，如公式（2）所示。

岸橋、軌道門吊和AGV 最多有一個前續(xù)集裝箱作業(yè)的表達(dá)如公式（3）所示。

岸橋、軌道門吊和AGV 最多有一個后續(xù)集裝箱作業(yè)的表達(dá)如公式（4）所示。

當(dāng)岸橋連續(xù)作業(yè)2 個裝卸任務(wù)時，后一個裝卸任務(wù)的開始時間應(yīng)晚于前一個裝卸任務(wù)的結(jié)束時間和該設(shè)備在兩裝卸任務(wù)之間的空駛時間之和，如公式（5）所示。

卸車過程中岸橋等待AGV 的時間如公式（6）所示。

裝車作業(yè)過程中岸橋等待AGV 的時間如公式（7）所示。

卸載作業(yè)中，岸橋的開始作業(yè)時間應(yīng)晚于AGV 完成前一作業(yè)后并返回岸橋處的時間，如公式（8）所示。

式中：αi為集裝箱需要進(jìn)行的作業(yè)類別，當(dāng)集裝箱i∈Ku時，αi=1。

裝車過程中，岸橋的作業(yè)開始時間應(yīng)晚于AGV 的到達(dá)時間，如公式（9）所示。

岸橋作業(yè)的開始時間與結(jié)束時間的關(guān)系如公式（10）所示。

當(dāng)AGV 連續(xù)作業(yè)2 個集裝箱時，后一個裝卸任務(wù)的開始時間應(yīng)晚于前一個裝卸任務(wù)的結(jié)束時間和設(shè)備在2 個作業(yè)之間的空駛時間之和[4]，如公式（11）所示。

卸車過程中AGV 等待軌道門吊的時間如公式（12）所示。

在卸載作業(yè)中，AGV 的作業(yè)開始時間應(yīng)晚于岸橋的作業(yè)結(jié)束時間，如公式（13）所示。

軌道門吊的運(yùn)行速度對AGV 作業(yè)結(jié)束時間的影響如公式（14）所示。

當(dāng)軌道門吊連續(xù)作業(yè)2 個集裝箱時，后一個裝卸作業(yè)的開始時間應(yīng)晚于前一個裝卸作業(yè)的結(jié)束時間和設(shè)備在2 個作業(yè)之間的空駛時間之和，如公式（15）所示。

卸車過程中軌道門吊等待AGV 的時間如公式（16）所示。

在卸載作業(yè)中，軌道門吊的開始時間應(yīng)晚于AGV 完成前一作業(yè)后并返回岸橋處的時間，如公式（17）所示。

軌道門吊作業(yè)開始時間與作業(yè)結(jié)束時間的關(guān)系如公式（18）所示。

2 改進(jìn)麻雀搜索算法

2.1 算法設(shè)計思想

與其他優(yōu)化算法相比，麻雀搜索算法（SSA 算法）控制參數(shù)較少，局部搜索能力較強(qiáng)，可用于車間調(diào)度[5]、路徑規(guī)劃[6]等問題的優(yōu)化。但傳統(tǒng)的SSA 算法在搜索初期易陷入局部最優(yōu)點，因此一些學(xué)者對該算法進(jìn)行了改進(jìn)。劉麗娜[7]等利用量子計算、正余弦搜索和警戒者數(shù)量遞減策略對SSA 進(jìn)行改進(jìn)，避免算法在求解后期陷入局部最優(yōu)。王海瑞[8]等引入Tent 混沌提高初始解質(zhì)量，同時優(yōu)化了麻雀位置更新公式，以提高SSA 的工程實用性。該文在種群初始化階段引入Levy 飛行搜索機(jī)制以增大搜索空間，提高群體搜索多樣性，最大限度地提高裝卸作業(yè)效率。

2.2 傳統(tǒng)麻雀搜索算法

在麻雀覓食的過程中，根據(jù)麻雀的任務(wù)不同，將其分為發(fā)現(xiàn)者和加入者。發(fā)現(xiàn)者通過搜尋發(fā)現(xiàn)食物位置，加入者則依賴于發(fā)現(xiàn)者獲取食物。此外，當(dāng)麻雀種群受到捕食者的攻擊時會做出反捕食行為。

首先，發(fā)現(xiàn)者通過搜尋發(fā)現(xiàn)食物，同時為加入者提供尋找方向，因此發(fā)現(xiàn)者能夠獲得比加入者更大的覓食搜索范圍，如公式（19）所示。

式中：t為當(dāng)前迭代次數(shù)；Xij為第i個麻雀種群在第j 維中的位置信息；α為的0～1 的隨機(jī)數(shù)；itermax為最大迭代次數(shù)；Q為一個服從正態(tài)分布的隨機(jī)數(shù)；L為一個1×d 并且元素全為1 的矩陣；R2屬于0～1，表示麻雀種群位置的預(yù)警值；ST屬于0.5～1，表示麻雀種群位置的安全值。

當(dāng)R2ST時，表示種群中部分警戒者已發(fā)現(xiàn)天敵，全體種群應(yīng)先轉(zhuǎn)移至安全區(qū)，再進(jìn)行食物搜尋。

其次，在搜尋食物的過程中，一些加入者會緊跟發(fā)現(xiàn)者。當(dāng)發(fā)現(xiàn)者尋覓到食物后，加入者會同發(fā)現(xiàn)者進(jìn)行爭奪或者圍繞在發(fā)現(xiàn)者周圍進(jìn)行覓食，如公式（20）所示。

式中：Xpt+1為目前發(fā)現(xiàn)者所發(fā)現(xiàn)的最佳位置；Xworst為當(dāng)前全局最差的位置；A+=AT（AAT）-1，A為一個與麻雀個體同維度的列向量，其元素隨機(jī)賦值為1 或-1 的1×d的矩陣。

當(dāng)i≤n/2 時，加入者會積極追隨發(fā)現(xiàn)者的覓食路徑；當(dāng)i>n/2 時，表明第i個加入者沒有搜尋到食物，因此需要飛往其他地方進(jìn)行覓食。

最后，在種群中，有一部分麻雀在搜尋食物的同時還肩負(fù)偵察敵人的任務(wù)，由于處在種群外圍的麻雀很容易受到天敵的攻擊，因此它們需要不斷調(diào)整位置，該文稱其為警戒者，如公式（21）所示。

式中：Xbest為當(dāng)前全局最優(yōu)位置；β為一個屬于-1～1 的隨機(jī)數(shù)，fi為當(dāng)前麻雀個體的適應(yīng)度值；fg為全局最佳適應(yīng)度值；fw為全局最差適應(yīng)度值；ε為一個避免分母為0 的常數(shù)。

當(dāng)fi>fg時，表示麻雀在種群外圍，極易受到天敵攻擊；當(dāng)fi=fg時，表示處于種群中間的麻雀也感受到天敵的危險，此時需要靠近其他麻雀以減少被攻擊的風(fēng)險。

2.3 改進(jìn)麻雀搜索算法

針對傳統(tǒng)麻雀搜索算法的缺點，該文在種群初始化階段引入Levy 飛行搜索機(jī)制以增大搜索空間，提高群體搜索多樣性，避免搜索算法陷入局部最優(yōu)。另外，麻雀搜索算法需要仔細(xì)的參數(shù)調(diào)優(yōu)才能獲得最佳性能，因此增加Levy 飛行組件可以提供額外的探索機(jī)制并提高算法的魯棒性，以減少對參數(shù)調(diào)優(yōu)的依賴。

Levy 飛行擾動步長Tp的計算如公式（22）～公式（24）所示。

式中：i∈{1，2，…，n}；j∈{1，2，…，D}；u和v屬于正態(tài)分布；β=1.5。

麻雀搜索位置步長擾動如公式（25）所示。

3 算例分析

隨著海鐵聯(lián)運(yùn)的快速發(fā)展，港口的貨物吞吐量日益增多，為滿足日益多樣化的運(yùn)輸市場對高質(zhì)量運(yùn)輸?shù)男枨?，港站作業(yè)區(qū)需要對裝卸設(shè)備進(jìn)行合理配置、優(yōu)化裝卸設(shè)備調(diào)度，以適應(yīng)更高的運(yùn)輸壓力。該文以某港裝卸作業(yè)設(shè)備協(xié)同調(diào)度為例進(jìn)行分析。

該港某碼頭共有4 臺岸橋供裝卸船，在集裝箱堆場設(shè)置3 臺軌道門吊進(jìn)行作業(yè)，往返港口與堆場的運(yùn)輸AGV 數(shù)量為9 輛。裝卸設(shè)備的基本參數(shù)信息見表1。

運(yùn)行結(jié)果見表2。針對該問題，與遺傳算法（GA）相比，改進(jìn)后的麻雀搜索算法所得設(shè)備配置更合理且目標(biāo)函數(shù)值更優(yōu)。

表2 LISSA 與GA 運(yùn)行結(jié)果對比

根據(jù)算例分析可得：1）改進(jìn)后的麻雀搜索算法性能較穩(wěn)定，能夠較快計算出目標(biāo)函數(shù)最優(yōu)解。不同參數(shù)設(shè)置下的性能比較如圖1 所示。在箱量較小的情況下，該算法能較快達(dá)到收斂。2）目標(biāo)函數(shù)值隨集裝箱吞吐量增加而增大，并且岸橋及軌道門吊的數(shù)量變化比AGV 的數(shù)量變化對目標(biāo)函數(shù)的影響更大。3）以集裝箱量40TEU 為分析對象，箱量規(guī)模較小，將其存儲至一個箱區(qū)，根據(jù)模型求得的最優(yōu)設(shè)備使用量為2/3/3，即有2 臺岸橋投入使用，每輛岸橋到達(dá)集卡所需時間為97s。岸橋?qū)⒖堪洞把b載的集裝箱卸下并裝至AGV 上。在碼頭與堆場之間有3 輛AGV 正在行駛，AGV 將集裝箱由港口運(yùn)至堆場，然后軌道門吊將集裝箱放置到指定位置。裝卸作業(yè)完成時間和3 種設(shè)備的作業(yè)時間見表3，3種設(shè)備的詳細(xì)使用方案見表4。

圖1 不同箱量設(shè)置下的算法性能比較

表3 裝卸作業(yè)完成時間（單位：s）

表4 設(shè)備詳細(xì)使用方案

4 結(jié)論

該文主要研究了港口作業(yè)區(qū)裝卸設(shè)備配置，在“岸橋-AGV-軌道門吊”的港口協(xié)同裝卸方案下，首先分析了3種設(shè)備之間的時間銜接。其次建立以裝卸任務(wù)完成時間最少和設(shè)備使用數(shù)量最少為目標(biāo)的設(shè)備調(diào)度模型。最后，將某港碼頭運(yùn)箱量代入模型進(jìn)行求解。通過算法對比，發(fā)現(xiàn)改進(jìn)后的麻雀搜索算法性能更穩(wěn)定，可求解出較適當(dāng)?shù)脑O(shè)備使用數(shù)量和最短的作業(yè)完工時間，能夠在一定程度上提升整個堆場的作業(yè)效率。由于該文沒有考慮船舶的泊位利用率和港口裝卸線數(shù)量對作業(yè)效率的影響，因此今后的研究中有待改進(jìn)，以豐富海鐵聯(lián)運(yùn)集裝箱轉(zhuǎn)運(yùn)的研究內(nèi)容。