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

曾建智，張志英

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

?

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

曾建智，張志英

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

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

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

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

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

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

1　問題描述與解決方法

1.1問題描述

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

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

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

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

1.2解決方法

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

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

2.1堆場(chǎng)狀態(tài)二進(jìn)制矩陣

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

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

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

2.3分段移動(dòng)路徑優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)

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

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

表1　移動(dòng)路徑評(píng)價(jià)因素Table 1 Moving path evaluation factor

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

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

定義決策變量如下:

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

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

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

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

3　模型求解

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

1)初始化。以調(diào)度開始時(shí)的堆場(chǎng)狀態(tài)作為初始狀態(tài)建立堆場(chǎng)初始狀態(tài)二進(jìn)制矩陣。

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

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

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

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

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

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

③將已標(biāo)有p的位置放入集合S中，同時(shí)記錄到達(dá)該位置的前一個(gè)位置的節(jié)點(diǎn)r(父節(jié)點(diǎn))，如圖2(a)所示。

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

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

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

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

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

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

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

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

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

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

1)用遺傳算法求得的最優(yōu)調(diào)度序列作為一個(gè)初始可行解xnow。并計(jì)算當(dāng)前序列下總的綜合移動(dòng)難度p，將具有緊前、緊后出場(chǎng)順序的分段放入禁忌表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)并計(jì)算該鄰域序列總的綜合移動(dòng)難度p’，若p’＜p，那么Ino=Ino+1，NIno=0，否則Ino=Ino+1，NIno=Nino+1。將當(dāng)期得到的調(diào)度序列作為當(dāng)前最優(yōu)的解，并更新禁忌表H。

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

圖5　鄰域搜索Fig.5 Neighborhood search

4　實(shí)例驗(yàn)證與結(jié)果分析

4.1實(shí)驗(yàn)驗(yàn)證與結(jié)果

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

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

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

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

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

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

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

4.2數(shù)值分析

4.2.1堆場(chǎng)尺寸、初始負(fù)載率、道路開放程度比較

為了驗(yàn)證堆場(chǎng)尺寸、初始負(fù)載率、道路開放程度對(duì)綜合移動(dòng)難度的影響，本文進(jìn)行以下試驗(yàn):

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

2)堆場(chǎng)尺寸:4×15、5×12、6×10

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

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

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

通過圖8對(duì)比分析可得

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

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

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

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

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

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

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

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

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

4.2.2算法比較分析

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

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

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

5　結(jié)論

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

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

2)通過確定的評(píng)價(jià)指標(biāo)運(yùn)用智能算法對(duì)堆場(chǎng)的分段調(diào)度計(jì)劃進(jìn)行優(yōu)化;

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

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

參考文獻(xiàn):

［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］張志英，申鋼，劉祥瑞，等.基于最短路算法的船舶分段堆場(chǎng)調(diào)度［J］.計(jì)算機(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］張志英，徐建祥，計(jì)峰.基于遺傳算法的船舶分段堆場(chǎng)調(diào)度研究［J］.上海交通大學(xué)學(xué)報(bào)，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)工程理論與實(shí)踐，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é)報(bào)，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@ #edu.cn.

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

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

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

中圖分類號(hào):O224;U673

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):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