基于案例檢索的集裝箱碼頭箱區(qū)優(yōu)化研究

大連東軟信息學(xué)院商務(wù)管理系 李浩淵 孫冬石

基于案例檢索的集裝箱碼頭箱區(qū)優(yōu)化研究

大連東軟信息學(xué)院商務(wù)管理系 李浩淵 孫冬石

摘 要：本文面對集裝箱碼頭的進(jìn)出口箱區(qū)規(guī)劃問題，采用仿真模型與智能優(yōu)化算法相結(jié)合的仿真優(yōu)化方法進(jìn)行分析求解。底層仿真模型覆蓋集裝箱碼頭全作業(yè)過程，并充分考慮了作業(yè)中的隨機(jī)因素；頂層優(yōu)化采用了遺傳算法與案例檢索相結(jié)合的一種創(chuàng)新方法，有效解決了仿真優(yōu)化運(yùn)算時間過長的問題。

關(guān)鍵詞：仿真優(yōu)化 箱區(qū)規(guī)劃 遺傳算法 案例檢索

近年來伴隨著集裝箱碼頭吞吐量的不斷增長，堆場資源變得越來越緊張。如何在有限的空間約束前提下，通過合理的規(guī)劃和管理來提升作業(yè)效率，已經(jīng)成為碼頭管理者關(guān)注的重點問題。

由于碼頭生產(chǎn)作業(yè)中包含諸多隨機(jī)因素，數(shù)學(xué)模型往往很難描述[1]，而仿真與優(yōu)化相結(jié)合成為解決該問題的一種有效手段。因此，本文采用仿真優(yōu)化方法對進(jìn)出口箱區(qū)規(guī)劃問題進(jìn)行求解。

針對仿真優(yōu)化方法中存在的運(yùn)算時間過長問題，在Lee[2]和Bachelet[3]研究基礎(chǔ)上，提出了一種改進(jìn)的案例檢索方法，較好地解決了運(yùn)算代價過大的問題。

1　 仿真模型

1.1 仿真對象

以國內(nèi)某集裝箱碼頭實際布局為背景，開展仿真模型構(gòu)建仿真對象中，包含4個泊位，36個堆區(qū)，6排碼頭進(jìn)出閘口通道，每個泊位分配若干岸橋，每臺岸橋配備10臺內(nèi)部集卡，每個堆區(qū)配備一臺龍門吊，碼頭內(nèi)會隨機(jī)產(chǎn)生若干外部集卡開展作業(yè)。

1.2 模型特點

(1)仿真模型能夠?qū)崿F(xiàn)多船作業(yè)模擬，對過程的描述能夠細(xì)化到每臺機(jī)械的運(yùn)行過程。

(2)仿真過程以秒為單位，實現(xiàn)細(xì)粒度仿真推進(jìn)。

(3)為節(jié)省仿真運(yùn)行時間，本模型采用數(shù)學(xué)仿真方式。

2　 仿真優(yōu)化算法設(shè)計

2.1 算法原理

仿真優(yōu)化是一種將仿真模型與優(yōu)化算法結(jié)合使用的一種組合算法，其與傳統(tǒng)優(yōu)化的主要區(qū)別在于，仿真程序取代數(shù)學(xué)公式成為目標(biāo)評價的方式，主要優(yōu)點在于仿真程序相對數(shù)學(xué)模型能夠更為充分地考慮到系統(tǒng)中隨機(jī)因素的干擾，從而更為準(zhǔn)確地對不同方案的表現(xiàn)進(jìn)行評估。優(yōu)化算法負(fù)責(zé)將性能參數(shù)輸入仿真模型，仿真模型負(fù)責(zé)輸出評價指標(biāo)給優(yōu)化算法，優(yōu)化算法再根據(jù)評價結(jié)果開展進(jìn)化搜索，并將更優(yōu)參數(shù)再次回饋仿真模型，不斷重復(fù)評價—優(yōu)化過程，直至滿足終止條件。

2.2 遺傳算法設(shè)計

(1)編碼方案

決策向量采用0～1編碼方式：

其中，

(2)適值計算

綜合考慮作業(yè)效率和岸橋利用率兩個因素，分別進(jìn)行歸一化處理，形成評價適值

(3)遺傳算子

選擇策略：正比選擇。

交叉策略：單切點方式，交叉概率0.9。

變異策略：位值方式，變異概率0.05。

(4)停止準(zhǔn)則

最大進(jìn)化代數(shù)100，運(yùn)算停止。

3　 基于案例檢索的改進(jìn)方法

3.1 案例檢索原理

針對仿真優(yōu)化方法運(yùn)算時間過長的問題，可以從兩個方面進(jìn)行努力，一是避免重復(fù)仿真，二是通過預(yù)測減少表現(xiàn)不好的解的仿真次數(shù)。因此，本文設(shè)計了一種考慮近似匹配程度的案例檢索方法。

3.2 幾個基礎(chǔ)定義

定義2：完全匹配案例

定義3：近似匹配案例

3.3 案例檢索流程

步驟1：在案例庫中，是否存在該解的完全匹配案例，如存在，跳轉(zhuǎn)至步驟8。如不存在，跳轉(zhuǎn)至步驟2。

步驟2：在不存在該解的完全匹配案例的情況下，再次檢測是否存在該解的近似匹配案例，如存在，跳轉(zhuǎn)至步驟3。如不存在，轉(zhuǎn)步驟9。

步驟3：如果發(fā)現(xiàn)該解的近似匹配案例的表現(xiàn)較好時，即它的評價值與最好評價值非常接近，差值小于一個常數(shù)的話，則跳轉(zhuǎn)至步驟5。否則，跳轉(zhuǎn)至步驟4。

步驟4：如果發(fā)現(xiàn)該解的近似匹配案例的表現(xiàn)值不好時，即它的評價值與最好評價值相距較遠(yuǎn)，差值大于一個常數(shù)，則認(rèn)為當(dāng)前解仿真價值不大，但為了保證算法的探索能力，利用隨機(jī)數(shù)則跳轉(zhuǎn)至驟5。否則，跳轉(zhuǎn)至步驟8。來決定是否繼續(xù)仿真，若

步驟5：運(yùn)行仿真程序，獲得解的評價值。跳轉(zhuǎn)至步驟6。

步驟6：對比該解在案例庫中存儲的評價值，若更優(yōu)，更跳轉(zhuǎn)至步驟7。否則，跳轉(zhuǎn)至步驟10。

步驟7：更新評價值，跳轉(zhuǎn)至步驟10。

步驟8：將案例庫中存儲的評價值直接賦予當(dāng)前解，跳轉(zhuǎn)至步驟10。

步驟9：通過運(yùn)行仿真程序，獲得解的評價值，并將其加入案例庫。轉(zhuǎn)步驟10。

步驟10：完成評價值獲取后，繼續(xù)優(yōu)化算法運(yùn)算。

3.4 案例檢索特點

(1)實現(xiàn)了對已完成仿真結(jié)果的有效利用，避免重復(fù)仿真。

(2)只將局部最優(yōu)案例加入案例庫，并不是所有的新解均加入案例庫，有效縮小了案例庫的規(guī)模。

(3)通過評估預(yù)測，實現(xiàn)對好評價的獲得可能性進(jìn)行評估，從而大大減少了仿真次數(shù)。

(4)通過當(dāng)前解與近似案例的對比，節(jié)省了大量仿真運(yùn)算代價。

(5)通過當(dāng)前解與最優(yōu)解的對比，保證了算法的全局探索能力，確保了解的多樣性。

4　 實驗與分析

4.1 仿真參數(shù)設(shè)計

在仿真運(yùn)行的過程中，充分考慮碼頭作業(yè)的各項隨機(jī)因素，采取數(shù)據(jù)統(tǒng)計和概率分布來進(jìn)行隨機(jī)描述，其中，岸橋、龍門吊的作業(yè)效率以及外部集卡在閘口處的作業(yè)時間，均服從正態(tài)分布，對應(yīng)具體分布參數(shù)為和外部集卡的到達(dá)時間服從泊松分布，其具體分布參數(shù)設(shè)定為

4.2 案例檢索效果分析

案例檢索之所以能夠?qū)崿F(xiàn)運(yùn)算代價的降低，主要源于兩點：一是能找到完全匹配案例的解，不需要進(jìn)行仿真；二是能找到近似匹配案例的解，通過進(jìn)一步與最優(yōu)案例的對比，也存在很大可能不通過仿真運(yùn)算而直接完成賦值。

因此，在實驗中，本文記錄了算法運(yùn)算各代中，檢索到完全匹配案例的解的個數(shù)，檢索到近似匹配案例的解的個數(shù)以及案例庫的規(guī)模等數(shù)值，如表1所示。

表1 案例檢索統(tǒng)計結(jié)果

從表1中可以看出，本文所設(shè)計的案例檢索方法，有效減少了調(diào)用仿真程序的次數(shù)，從而大大降低了運(yùn)算時長，而且很好地控制了案例庫的整體規(guī)模，在問題得到求解的同時，運(yùn)行時間的問題也得到了有效解決。

5　 結(jié)語

本文面向集裝箱碼頭箱區(qū)規(guī)劃問題，運(yùn)用仿真模型與優(yōu)化算法相結(jié)合的仿真優(yōu)化方法進(jìn)行求解，并引入了考慮案例匹配的案例檢索方法，有效地解決了運(yùn)算代價的問題，獲得了較好的解決方案。

參考文獻(xiàn)

［1］于越，金淳，霍琳.基于仿真的集裝堆場大門系統(tǒng)規(guī)劃研究［J］.系統(tǒng)仿真學(xué)報，2007（13）.

［2］Lee L H，Chew E P Manikam P.A general framework on the simulation-based optimization under fixed computing budget［J］.European Journal of Operational Research，2006（3）.

［3］Bachelet B，Yon L.Model enhancement：improving theoretical optimization with simulation［J］.Simulation Modelling Practice and Theory，2007（6）.

中圖分類號：F069

文獻(xiàn)標(biāo)識碼：A

文章編號：2096-0298（2016）06（b）-162-02