基于智能算法的船舶分段堆場調(diào)度計劃與優(yōu)化

曾建智，張志英

(同濟大學(xué)機械與能源工程學(xué)院，上海201804)

?

基于智能算法的船舶分段堆場調(diào)度計劃與優(yōu)化

曾建智，張志英

(同濟大學(xué)機械與能源工程學(xué)院，上海201804)

摘要:分段的移動是船舶分段堆場調(diào)度中最主要的作業(yè)過程，而移動路徑的優(yōu)劣決定著分段堆場調(diào)度的效率和成本。論文通過綜合考慮臨時阻擋分段數(shù)量、平板車轉(zhuǎn)向次數(shù)和移動距離對調(diào)度成本的影響，提出分段綜合移動難度的評價標準，以此建立數(shù)學(xué)模型，并以分段綜合移動難度為優(yōu)化目標，利用遺傳算法選擇分段在堆場中停放位置的較優(yōu)方案，運用禁忌搜索優(yōu)化柔性出場時間分段的出場順序，構(gòu)建啟發(fā)式規(guī)則來確定分段最優(yōu)的進、出場路徑。最后，利用某船廠的實際數(shù)據(jù)對模型進行實例驗證和數(shù)值分析，結(jié)果表明，本文方法可以得到較優(yōu)的堆場作業(yè)計劃，實現(xiàn)堆場資源的高效利用。

關(guān)鍵詞:分段堆場;遺傳算法;禁忌搜索;啟發(fā)式規(guī)則

船舶分段堆場是為了協(xié)調(diào)船舶生產(chǎn)過程中由于生產(chǎn)和管理的原因造成分段在不同加工工序之間無法即時周轉(zhuǎn)的問題用于臨時存放分段的場所。分段通過舾裝、噴漆等工藝處理后運輸至堆場進行預(yù)處理作業(yè)(預(yù)舾裝、檢驗和修補等)或暫存等待后續(xù)的加工作業(yè)。由于分段體積和重量都十分龐大，無法進行垂直方向上的吊運，因此只能通過平板車進行平面方向上的運輸，并且平板車一次只能運輸一個船舶分段。在船舶堆場調(diào)度操作過程中，根據(jù)作業(yè)流程可分成3種分段:進場分段、出場分段和臨時阻擋分段。對于進場分段需要安排一個空的存儲單元和一條可行的路徑，對于出場分段則需要規(guī)劃一條可行的路徑，而在分段進出堆場的路徑上會遇到擋道的分段，需要先將擋道的分段臨時移至空地，待平板車運輸完目標分段后，擋道分段可重回原位、重新選位或移至臨時暫存場所。這些操作對于堆場調(diào)度來說都是非增值操作，因此在分段移動中臨時阻擋分段的數(shù)量是影響移動路徑優(yōu)劣的重要因素。此外，還有其他很多因素也會對移動路徑的優(yōu)劣產(chǎn)生影響，如分段的幾何屬性，因此如何設(shè)定一個較為合理、綜合的移動路徑評價指標尤為重要。

國內(nèi)外針對船舶分段堆場調(diào)度問題的研究較少。Changkyu等以臨時分段移動數(shù)量最少為目標建立優(yōu)化模型，并運用遺傳算法和改進動態(tài)啟發(fā)式算法對模型進行求解［1－2］。然而該優(yōu)化模型是在假定堆場場地固化的生產(chǎn)環(huán)境中建立，限定分段在堆場中的移動路徑和移動方向，導(dǎo)致分段只能按直線進出堆場，大大增加了臨時分段的移動量。Tao等［3］在此基礎(chǔ)上考慮了分段進出堆場的任務(wù)順序?qū)φ{(diào)度方案的影響，并運用啟發(fā)式算法和禁忌搜索對結(jié)果進行優(yōu)化。申鋼等［4］以最小化臨時分段移動量和平板車在堆場中的行駛距離為優(yōu)化目標建立優(yōu)化模型，并運用分支定界法和啟發(fā)式規(guī)則來確定分段的移動路徑和停放位置。徐建祥等［5］提出臨時場地用于暫時存放臨時移動分段，采用改進遺傳算法選擇分段在堆場中停放位置的最優(yōu)方案，并構(gòu)建啟發(fā)式規(guī)則來確定分段在堆場中的最優(yōu)進、出場路徑。但上述研究對分段堆場調(diào)度方案的評價因素單一，并且假設(shè)分段堆場的場外道路確定且唯一，脫離了船舶生產(chǎn)的實際情況。

除了臨時阻擋分段數(shù)量這一影響因素，本文還考慮了平板車轉(zhuǎn)向次數(shù)和移動距離對移動路徑選擇的影響，并確定了較為全面的評價指標，以綜合移動難度為優(yōu)化目標，利用智能算法和啟發(fā)式規(guī)則建立分段堆場調(diào)度優(yōu)化模型。確定分段在堆場中最佳的停放位置，規(guī)劃進、出場平板車最優(yōu)的移動路徑，合理的安排出場任務(wù)的順序，從而提高堆場的運作效率。論文還對堆場的尺寸規(guī)格、道路開放程度和初始負載率進行對比優(yōu)化，提高了對堆場資源的利用率，并用某船廠的實際數(shù)據(jù)對模型進行驗證。

1　問題描述與解決方法

1.1問題描述

平板車是船廠中最主要的運輸工具，作為中間產(chǎn)品的分段在各個生產(chǎn)車間和分段堆場間的運輸都依賴于它。常用的平板車是一種具有液壓提升裝置，有65個輪子的特殊車輛［6］。它通過液壓裝置將分段提升，通過堆場中的可行路徑，將分段移動至目標存儲單元并放置支撐桿上。除了提升、移動和放置，轉(zhuǎn)向也是平板車在堆場中的重要操作，通過轉(zhuǎn)向可以避開擋道分段較多的路徑，從而有效降低臨時阻擋分段的數(shù)量，但轉(zhuǎn)向?qū)τ隗w型龐大的平板車在空間有限的堆場道路上是十分不易的，因此，有必要將平板車的轉(zhuǎn)向次數(shù)這一指標加入平板車移動路徑優(yōu)劣的評價標準之中。

船舶分段存在緊前、緊后的搭載順序，因此這些分段的出場順序需要滿足一定的先后順序，而有些分段出場時間是柔性的，因此對于具有柔性出場時間的分段，可以根據(jù)其所在的堆場位置選擇適當?shù)某鰣鰰r間，從而對分段的調(diào)度方案進行優(yōu)化。

考慮到堆場運作的實際情況和研究問題的方便，本文作了以下的假設(shè):1)船舶分段堆場由若干個面積相等的正方形場地組成，每個正方形場地為一個存儲單元;2)分段用最小包絡(luò)矩形近似;3)一個存儲單元只能存放一個分段;4)存儲單元能容下各種不同形狀的分段;5)每天分段的出場任務(wù)優(yōu)先于進場任務(wù);每日出場分段除具有緊前、緊后關(guān)系的分段，其他的分段出場順序可隨意調(diào)整。

要解決的問題有:1)為進場分段分配一個合適的存儲單元;2)為進出場分段確定一條最優(yōu)的移動路徑;3)確定同一天出場各個分段之間的調(diào)度順序。

1.2解決方法

本文針對以上問題，首先制定一個同時考慮臨時阻擋分段數(shù)量、平板車轉(zhuǎn)向次數(shù)和移動距離的分段綜合移動難度的評價標準。然后以使其最小化為目標函數(shù)，利用遺傳算法［7］(genetic algorithm，GA)為進場分段選擇一個合適的存儲單元位置，并用啟發(fā)式規(guī)則根據(jù)評價指標，為進、出場分段選擇一條最優(yōu)的移動路徑。對于同一天出場的具有柔性出場時間的分段，需要運用禁忌搜索(tabu search，TS)優(yōu)化其出場順序。最后綜合考慮調(diào)度周期內(nèi)所有的分段，制定一個整體最優(yōu)的分段調(diào)度計劃。

2　建立船舶分段堆場調(diào)度模型

2.1堆場狀態(tài)二進制矩陣

為了表示分段在堆場中的停放位置及分段堆場存儲單元的狀態(tài)，建立堆場狀態(tài)二進制矩陣Ht。Ht的每個元素bVxy表示此時調(diào)度t時刻堆場中存儲單元位置為Vxy(位于堆場的第x行第y列)的狀態(tài)，bVxy=1表示存儲單元內(nèi)已有分段停放，bVxy=0表示該時刻存儲單元狀態(tài)為空，進場分段可以分配至該位置。

2.2堆場狀態(tài)的更新

隨著船舶分段調(diào)度任務(wù)的進行，堆場中存儲單元的狀態(tài)也會隨之改變。若位于Vxy位置的分段在t時刻有調(diào)度任務(wù)，那么堆場狀態(tài)矩陣對應(yīng)位置的元素要滿足，即原來存儲單元停放有分段的，出場后狀態(tài)由1變?yōu)?;原來空存儲單元，分段進出停放至該位置后，狀態(tài)由0變?yōu)?。

2.3分段移動路徑優(yōu)劣的評價標準

評價分段移動路徑優(yōu)劣的因素主要有:1)路徑中的臨時分段的數(shù)量;2)存取分段時，為了到達目標位置平板車在該路徑中的轉(zhuǎn)向次數(shù);3)平板車在該路徑中移動的距離。

表1將上述評價因素按其對分段調(diào)度作業(yè)的影響程度排序。因此，建立分段綜合移動難度p的評價標準:p=αx+βy+γz，根據(jù)評價分段移動路徑優(yōu)劣因素的重要程度，為了區(qū)分設(shè)定α=1，β=0.1，γ=0.01，在路徑搜索時，移動路徑中每一個擋道分段便累加α，平板車每進行一次轉(zhuǎn)向便累加β，每移動經(jīng)過一個存儲單元便累加γ。最后得到每條路徑的移動難度p。若p=2.36，則表示該分段進(出)堆場臨時阻擋分段的數(shù)量為2個，平板車的轉(zhuǎn)向次數(shù)為2次，平板車需要移動6個存儲單元的距離。

表1　移動路徑評價因素Table 1 Moving path evaluation factor

2.4船舶分段堆場調(diào)度模型

堆場分段調(diào)度計劃以分段綜合移動難度最小為優(yōu)化目標建立堆場調(diào)度模型，并采用改進的啟發(fā)式算法進行優(yōu)化。

定義決策變量如下:

以最小化分段綜合移動難度為目標，建立以下目標函數(shù):

式中:M、N分別表示堆場在寬度和長度上被劃分的存儲單元數(shù)量，堆場中存儲單元的總數(shù)為M×N;(Lg，Wg)為分段g的幾何投影參數(shù)，g∈Si，Ri;S0為堆場中每個存儲單元的面積;Vxy為分段在堆場中的位置，分段處于堆場的第x行第y列。x=1，2…M;y=1，2…N;Si=(S1，S2…Sm)為待調(diào)度的進場分段集合，i=1，2…m;Rj=(R1，R2…Rn)為待調(diào)度的出場分段集合，j=1，2…n;T為堆場的調(diào)度周期;ts為調(diào)度周期T的開始時間;te為調(diào)度周期T的結(jié)束時間;tSi為分段Si的進場時間;tRj為分段Rj的出場時間;為進場分段i從道路移動到堆場Vxy儲位位置的過程中，選擇第k條可選路徑時的分段綜合移動難度，k=1，2…h(huán)，h為啟發(fā)式算法搜索產(chǎn)生的可選路徑的數(shù)量;plxyjk為出場分段j從堆場Vxy儲位位置移動到道路的過程中，選擇第k條可選路徑時的分段綜合移動難度，k=1，2…h(huán)，h為啟發(fā)式算法搜索產(chǎn)生的可選路徑的數(shù)量。

本文根據(jù)目標函數(shù)(1)依次計算調(diào)度計劃中分段移動的可選路徑，選擇每個分段最優(yōu)的移動路徑，從而使整體綜合移動難度最小，然后利用遺傳算法，得到一個基于位置選擇的整體最優(yōu)的分段調(diào)度方案。最后運用禁忌搜索，優(yōu)化每天具有柔性出場時間的分段出場順序。

約束(2)說明堆場中一個存儲單元只能存放一個分段;約束(3)確保一個分段只能分配到一個確定的儲位;約束(4)～(6)限制堆場每次只能執(zhí)行一個調(diào)度任務(wù);約束(7)規(guī)定計劃進場的分段其進場時間在調(diào)度周期內(nèi);約束(8)限定計劃出場的分段其出場時間在調(diào)度周期內(nèi);約束(9)保證分段的幾何投影尺寸能夠在一個存儲單元內(nèi)放下。

3　模型求解

船舶分段堆場調(diào)度模型的遺傳算法設(shè)計如下:

1)初始化。以調(diào)度開始時的堆場狀態(tài)作為初始狀態(tài)建立堆場初始狀態(tài)二進制矩陣。

2)產(chǎn)生初始種群。將進場分段在堆場中可能放置的存儲單元的位置(出場分段則為出場前分段所在位置)按照調(diào)度計劃組合形成一種調(diào)度方案(染色體)。

3)編碼。根據(jù)堆場的大小，若堆場大小M×N，遺傳算法的染色體可以采取如圖1的編碼方式。

染色體的基因位數(shù)為調(diào)度周期內(nèi)所有需調(diào)度的分段數(shù)量，基因中的整數(shù)部分用來表示分段在堆場中的位置，而小數(shù)部分則用于表示調(diào)度周期內(nèi)分段的時間屬性(最小單位以天計)。沒有整數(shù)部分的基因位置表示進場分段，整數(shù)部分根據(jù)分段可能存放的存儲單元位置隨機生成，為堆場狀態(tài)二進制矩陣中0的存儲單元的序號(按從左到右，從上到下依次為的存儲單元編號，隨機生成為第a個零的位置，整數(shù)部分則為a)。負數(shù)則表示原先進入堆場的分段此時要出堆場，例如－8.03則表示位于染色體第8個位置的進場分段，需要出堆場，它的出場時間為調(diào)度周期的第3天。通過這樣的編碼，可以更好的反應(yīng)調(diào)度任務(wù)的時間屬性，使算法最后呈現(xiàn)的調(diào)度計劃更加直觀，也便于后續(xù)的禁忌搜索。

4)解碼。利用改進的路徑搜索啟發(fā)式算法搜索得到調(diào)度周期內(nèi)每個分段的最優(yōu)移動路徑，通過計算每個分段的堆場調(diào)度計劃產(chǎn)生的綜合移動難度，并進行累加。具體過程如下:

①將目標位置(出場分段為出場前分段所在存儲單元的位置)放入已搜索集合S ;

②搜索與S集合中各個位置直接相鄰并且bVxy=0的位置，計算移動到該位置所需的綜合移動難度p并記錄;

③將已標有p的位置放入集合S中，同時記錄到達該位置的前一個位置的節(jié)點r(父節(jié)點)，如圖2(a)所示。

圖2　路徑搜索Fig.2 Moving path searching

⑥重復(fù)②～⑤，當計算各個新搜索位置的p時，檢查p的值是否有更新，若有更小的p值，則對其進行修正，并更新該位置的父節(jié)點r，直到已搜索集合S中的位置臨近道路，算法便停止搜索。

依次比較路徑搜索啟發(fā)式算法搜索產(chǎn)生各條路徑的綜合移動難度，選取具有最小綜合移動難度的路徑，并記錄下該路徑。

根據(jù)堆場的調(diào)度計劃來依次安排分段，每調(diào)度一個分段更新相應(yīng)的堆場二進制矩陣Ht。

5)選擇。本文采用精英保留戰(zhàn)略，把適應(yīng)度好的個體保留下來，并利用其好的性質(zhì)繁殖后代。同時采用比例選擇算子，使個體按照與適應(yīng)度倒數(shù)成正比的概率向下一代群體繁殖。

6)交叉。隨機產(chǎn)生一個以二進制編碼的染色體E，將其基因位置與雙親的位置一一對應(yīng)，將染色體E上基因值為1所對應(yīng)的雙親染色體基因互換，若1所對應(yīng)的位置為出場分段，則不作交叉。如圖3所示。

圖3　染色體交叉Fig.3 Crossover of chromosome

7)變異。隨機產(chǎn)生一個以二進制編碼的染色體E，將染色體E上基因值為1所對應(yīng)基因用重新隨機生成的a來代替，a的上限為當前堆場狀態(tài)下堆場中空閑的存儲單元的個數(shù)。若染色體E基因1所對應(yīng)的位置為出場分段，則不變。如圖4所示。

圖4　染色體變異Fig.4 Mutation of chromosome

由于具有緊前、緊后搭載順序的分段出場順序是固定的，而禁忌搜索的禁忌表就可以避免這些分段順序的調(diào)換，因此本文采用禁忌搜索［8－9］對柔性出場時間的分段進行調(diào)度順序的優(yōu)化。算法設(shè)計如下:

1)用遺傳算法求得的最優(yōu)調(diào)度序列作為一個初始可行解xnow。并計算當前序列下總的綜合移動難度p，將具有緊前、緊后出場順序的分段放入禁忌表H中。令I(lǐng)no=0，NIno=0，其中Ino為總的交換次數(shù)，NIno為交換后結(jié)果沒有優(yōu)化的次數(shù)。

2)若滿足Ino≥MaxIno或者NIno≥MaxNIno，轉(zhuǎn)至3);否則，搜索xnow的鄰域(鄰域產(chǎn)生方法由圖5所示)N(xnow)并計算該鄰域序列總的綜合移動難度p’，若p’＜p，那么Ino=Ino+1，NIno=0，否則Ino=Ino+1，NIno=Nino+1。將當期得到的調(diào)度序列作為當前最優(yōu)的解，并更新禁忌表H。

3)輸出分段調(diào)度的最優(yōu)序列，算法結(jié)束。

圖5　鄰域搜索Fig.5 Neighborhood search

4　實例驗證與結(jié)果分析

4.1實驗驗證與結(jié)果

為了驗證本文所建模型以及算法的可行性與正確性，以上海某大型船廠一周內(nèi)的分段調(diào)度為例，利用Microsoft Visual Studio 2010軟件，在處理器為2.40 GHz，內(nèi)存為4 GB的計算機上進行求解。實驗包括以下輸入?yún)?shù):1)堆場初始狀態(tài)的二進制矩陣;2)調(diào)度周期T內(nèi)計劃進出場分段的數(shù)量和進出場的日期;3)每日出場時間固定的分段以及出場時間較為柔性的出場分段;4)遺傳算法的參數(shù)設(shè)置:種群規(guī)模為100，染色體個體長度為50，交叉概率為0.9，變異概率為0.1，算法終止代數(shù)為100;5)禁忌搜索的參數(shù)設(shè)置:算法終止條件MaxIno=100，Nino=15，禁忌表長度為10，某分段堆場初始狀態(tài)如圖6所示，該堆場有6×10個存儲單元構(gòu)成，其中42個存儲單元已有分段存放，A x為暫存在堆場不同存儲單元上的分段編號。

圖6　堆場初始狀態(tài)Fig.6 Stockyard initial state

按調(diào)度日期順序排列的一周內(nèi)堆場調(diào)度計劃如表2所示。表中共有25個進場分段(從B1至B25依次編號)，25個出場分段(A x出場分段的編號，C1 至C6為調(diào)度周期T內(nèi)進入堆場暫存一段時間后又從堆場中取出的分段)。分段停放位置Vxy則表示分段停放的位置，x表示行，y表示列，例如V48則表示該分段位于堆場的第4行第8列的存儲單元上。由于C1至C5的分段出場位置是由先前分段進入堆場的位置所決定的，因此Vz中的z則表示進入堆場中的序號所對應(yīng)的停放位置，例如V6表示序號為6的B1分段進入堆場所停放的存儲單元的位置。標有*號的出場分段表示這些分段由于生產(chǎn)的緊前、緊后關(guān)系出場先后順序是固定的，不可進行隨意的調(diào)整。

表2　一周內(nèi)堆場調(diào)度計劃Table 2 Stockyard scheduling for one week

表3　堆場調(diào)度方案Table 3 Stockyard scheduling scheme

通過算法程序確定進場分段在堆場中的停放位置、出場分段的出場順序以及進出場分段進出堆場的路徑，得到一種較優(yōu)的堆場調(diào)度方案如表3所示。隨著程序的運行，個體的多樣性在55代后逐漸消失，解開始收斂，收斂時間為291.95 s，收斂曲線如圖7所示。

圖7　算法收斂曲線Fig.7 Algorithm convergence curves

4.2數(shù)值分析

4.2.1堆場尺寸、初始負載率、道路開放程度比較

為了驗證堆場尺寸、初始負載率、道路開放程度對綜合移動難度的影響，本文進行以下試驗:

1)調(diào)度分段數(shù)量:50個

2)堆場尺寸:4×15、5×12、6×10

3)初始負載率:60％、70％、80％、90％

4)道路開放程度:一條、兩條、四條

針對以上不同參數(shù)一共試驗了36種組合試驗，對于每種情況，為了保證更好的試驗效果，對每種情況進行5次試驗，并取平均值。

通過圖8對比分析可得

1)相同堆場規(guī)格的情況下，提高堆場的初始負載率，分段總的綜合移動難度會相應(yīng)的增加。

2)堆場初始負載率相同的情況下，隨著場外道路開放程度的增加，分段總的綜合移動難度會相應(yīng)的減少。

3)堆場場外道路開放程度的增加，在較高初始負載率的堆場狀態(tài)下，總的綜合移動難度的下降更為明顯。說明在較高初始負載率的堆場狀況下，適當?shù)脑黾娱_放道路的數(shù)量，能有效的提高堆場的運作效率。

4)堆場的道路由兩條增加至四條，對提升堆場的運作效率作用并不明顯，尤其是堆場在較低初始負載率的情況下運作。

5)對于場外道路數(shù)為一條，不同規(guī)格的堆場，分段總的綜合移動難度與初始負載率由以下關(guān)系:

①對于堆場規(guī)格為6×10(圖8(a))當堆場的初始負載率由70％提高至80％時，分段的綜合移動難度提高164.83％，因此在該堆場規(guī)格下，將堆場的初始負載率定為70％左右較為合理;

②對于堆場規(guī)格為5×12(圖8(b))當堆場的初始負載率由80％提高至90％時，分段的綜合移動難度提高109.98％，因此在該堆場規(guī)格下，將堆場的初始負載率定為80％左右較為合理;

③對于高負荷(堆場初始負載率90％)的分段堆場，堆場的布局規(guī)格設(shè)計為4×15較為合理。

圖8　不同規(guī)格堆場調(diào)度實驗分析Fig.8 Analysis of stockyard scheduling experiments with different specification

4.2.2算法比較分析

求解分段進出場的路徑問題是平面堆場調(diào)度問題中最為關(guān)鍵的問題，對于路徑的求解可以用Dijkstra算法［10－12］進行求解，Dijkstra算法能得出最短路徑的最優(yōu)解，但本文需要綜合考慮臨時阻擋分段數(shù)量、平板車的轉(zhuǎn)向次數(shù)和移動距離，若使用Dijkstra算法需要遍歷所有可能的路徑再篩選出最優(yōu)的進出場路徑，大大增加了算法的時間。因此本文在Dijkstra算法的基礎(chǔ)上，利用堆場的二進制矩陣，以起始點為中心，對狀態(tài)為0、1的存儲單元進行交替的搜索，直至搜索到終點，該算法只對路徑上的相關(guān)存儲單元進行搜索，在能夠求得最短路徑最優(yōu)解的情況下大大減少算法的搜索范圍，有效的降低路徑搜索的時間。如圖9所示，隨著調(diào)度分段數(shù)量的增加，兩種算法的運行時間都相應(yīng)的增加，但本文的算法明顯小于Dijkstra算法，且調(diào)度的規(guī)模越大，本文的算法的優(yōu)越性更加明顯。

對于出場分段，本文考慮對出場時間柔性的分段進行重新安排出場順序，使用禁忌搜索算法，根據(jù)出場分段所停放的位置，安排分段的出場順序。如圖9所示，在考慮分段出場順序的情況下，分段的綜合移動難度相比于原來有明顯的下降，并隨著調(diào)度分段數(shù)的增加，優(yōu)化的效果也明顯增加。

圖9　算法比較分析Fig.9 Comparison and analysis of algorithms

5　結(jié)論

本文通過對船舶分段堆場的調(diào)度過程進行研究，得出以下結(jié)論:

1)綜合考慮臨時阻擋分段數(shù)量、平板車轉(zhuǎn)向次數(shù)和移動距離對堆場調(diào)度成本的影響，確定了分段移動路徑優(yōu)劣的綜合評價指標;

2)通過確定的評價指標運用智能算法對堆場的分段調(diào)度計劃進行優(yōu)化;

3)通過對不同堆場尺寸、初始負載率和道路開放程度的實驗分析比較，得出不同堆場環(huán)境下堆場的較優(yōu)配置，提高了堆場的實際運作效率。

由于研究只考慮了一輛平板車的調(diào)度計劃，多輛平板車的協(xié)同調(diào)度情況將會復(fù)雜很多，需要作進一步的研究。

參考文獻:

［1］PARK C，SEO J.Mathematical modeling and solving procedure of the planar storage location assignment problem［J］.Computers＆Industrial Engineering，2009，57(3):1062－1071.

［2］PARK C，SEO J.Comparing heuristic algorithms of the planar storage location assignment problem［J］.Transportation Research Part E:Logistics and Transportation Review，2010，46(1):171－185.

［3］TAO Ningrong，JIANG Zuhua，QU Shipeng.Assembly block location and sequencing for flat transporters in a planar storage yard of shipyards［J］.International Journal of Production Research，2013，51(14):4289－4301.

［4］張志英，申鋼，劉祥瑞，等.基于最短路算法的船舶分段堆場調(diào)度［J］.計算機集成制造系統(tǒng)，2012，18(9):1982－1990.ZHANG Zhiying，SHEN Gang，LIU Xiangrui，et al.Block storage yard scheduling of shipbuilding based on shortest path algorithm［J］.Computer Integrated Manufacturing Systems，2012，18(9):1982－1990.

［5］張志英，徐建祥，計峰.基于遺傳算法的船舶分段堆場調(diào)度研究［J］.上海交通大學(xué)學(xué)報，2013，47(7):1036－1042.ZHANG Zhiying，XU Jianxiang，JI Feng.Shipbuilding yard scheduling approach based on genetic algorithm［J］.Journal of Shanghai Jiaotong University，2013，47(7):1036－1042.

［6］ROH M I，CHA J H.A block transportation scheduling system considering a minimisation of travel distance without loading of and interference between multiple transporters ［J］.International Journal of Production Research，2011，49(11):3231－3250.

［7］REEVES C R.A genetic algorithm for flowshop sequencing ［J］.Computers＆Operations Research，1995，22(1):5－13.

［8］符卓.帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究［J］.系統(tǒng)工程理論與實踐，2004，24(3):123－128.FU Zhuo.The capacitated open vehicle routing problem and its tabu search algorithm［J］.Systems Engineering－Theory ＆Practice，2004，24(3):123－128.

［9］JIA Shuai，HU Zhihua.Path－relinking Tabu search for the multi－objective flexible job shop scheduling problem［J］.Computers＆Operations Research，2014，47:11－26.

［10］FAN Yuezhen，LU Dunmin，WANG Qingchun，et al.Notice of retraction an improved Dijkstra algorithm used on vehicle optimization route planning［C］//Proceedings of the 2nd International Conference on Computer Engineering and Technology.Chengdu:IEEE，2010，3:V3－693－696.

［11］KAMBAYASHI Y，YAMACHI H，TSUJIMURA Y，et al.Dijkstra beats genetic algorithm:Integrating uncomfortable intersection－turns to subjectively optimal route selection ［C］//Proceeding of International Conference on Computational Cybernetics.Spain:IEEE，2009:45－50.

［12］李擎，謝四江，童新海，等.一種用于車輛最短路徑規(guī)劃的自適應(yīng)遺傳算法及其與Dijkstra和A*算法的比較［J］.北京科技大學(xué)學(xué)報，2006，28(11):1082－1086.LI Qing，XIE Sijiang，TONG Xinhai，et al.A self－adaptive genetic algorithm for the shortest path planning of vehicles and its comparison with Dijkstra and A* algorithms ［J］.Journal of University of Science and Technology Beijing，2006，28(11):1082－1086.

［13］PHANTHONG T，MAKI T，URA T，et al.Application of A* algorithm for real－time path replanning of an unmanned surface vehicle avoiding underwater obstacles［J］.Journal of Marine Science and Application，2014，13(1):105－116.

Block stockyard scheduling and optimizing based on an intelligent algorithm

ZENG Jianzhi，ZHANG Zhiying
(School of Mechanical Engineering，Tongji University，Shanghai 201804，China)

Abstract:Block stockyard is a major operation procedure in dispatching a ship block in a storage yard.The pros and cons of moving path determined the efficiency and the cost of the stockyard scheduling operation.This paper presented a synthetical evaluation criterion that considering obstructive blocks，flat transporter turning times and moving distance which influenced the scheduling cost.A mathematical model was established based on this criterion with the aim of minimizing the synthetical degree of moving the block.A genetic algorithm was formulated to select the optimal storage positions for the inbound blocks.Tabu search was used to optimize the entrance order of the blocks with flexible entering times.A heuristic rule was constructed to confirm the optimum entering and leaving routes of the blocks.Finally，real data from a shipyard were used to test the numerical analysis used in the models.The results showed that the proposed algorithm was effective to solve the scheduling problem in shipbuilding yards.

Keywords:block stockyard;genetic algorithm;tabu search;heuristic rule

通信作者:張志英，E－mail:zyzhang08@ tongji.edu.cn.

作者簡介:張志英(1971－)，男，博士，副教授.

基金項目:國家自然科學(xué)基金資助項目(70872076);上海市科技創(chuàng)新行動計劃基金資助項目(11dz1121803).

收稿日期:2014－11－17.網(wǎng)絡(luò)出版時間:2015－12－21.

中圖分類號:O224;U673

文獻標志碼:A

文章編號:1006－7043(2016)01－0041－07

doi:10.11990/jheu.201411053

網(wǎng)絡(luò)出版地址:http://www.cnki.net/kcms/detail/23.1390.u.20151221.1613.040.html