基于改進(jìn)遺傳算法的托盤揀選延誤時間優(yōu)化

李敬花，曹 旺，趙定剛，蔣 巖，周青驊

(1.哈爾濱工程大學(xué) 船舶工程學(xué)院，黑龍江 哈爾濱 150001；2.上海外高橋造船有限公司 生產(chǎn)管理部，上海 200137；3.哈爾濱工程大學(xué) 經(jīng)濟(jì)管理學(xué)院，黑龍江 哈爾濱 150001)

0 引言

船舶建造過程中的舾裝件數(shù)量大、品種多，而且船舶舾裝工程量占全船工程量相當(dāng)大的比重，因此準(zhǔn)時配送船舶舾裝物資成為更復(fù)雜的管理需求[1]，有必要引入“智能制造”概念[2-3]，利用各類智能優(yōu)化方法節(jié)約船舶建造項目中的企業(yè)管理資源。作為舾裝物資離開集配中心的最后一道工序，舾裝物資揀選具有重要的意義，其中舾裝件托盤為舾裝物資的基礎(chǔ)單元，對其揀選延誤時間進(jìn)行優(yōu)化可以顯著降低經(jīng)濟(jì)損失，提高船東滿意度。在實(shí)際中，舾裝件托盤揀選時間占總作業(yè)時間80%左右，降低揀選延誤時間最有效的辦法是對托盤揀選方法進(jìn)行優(yōu)化。針對船企集配中心多揀選人員揀貨作業(yè)的情形，能否最大限度地降低舾裝件托盤揀選延誤時間主要取決于以下3點(diǎn)：①托盤的分批問題，即如何將舾裝件托盤進(jìn)行分批[4]；②分批指派問題，即如何將分完批次的托盤指派給不同的揀選人員[5]；③分批排序問題，即如何將揀選人員手中的托盤批次進(jìn)行重新排序[5]。舾裝件托盤的分批、指派和排序問題是一類典型的NP-hard組合優(yōu)化問題[6]，其問題復(fù)雜度隨托盤數(shù)量的增加呈幾何數(shù)級增長，難以在合理的時間內(nèi)求解。

目前，行業(yè)逐漸使用智能化算法對上述問題進(jìn)行求解，現(xiàn)有研究中，文獻(xiàn)[7-8]采用遺傳算法對單區(qū)型倉庫揀選路徑進(jìn)行優(yōu)化，文獻(xiàn)[9-10]采用改進(jìn)蟻群算法對雙區(qū)倉庫揀貨路徑進(jìn)行優(yōu)化，文獻(xiàn)[11]以總揀選距離為優(yōu)化目標(biāo)，采用禁忌搜索算法對訂單分批進(jìn)行優(yōu)化。上述研究只單一地使用某一種方法求解倉儲揀選路徑問題，并未將交貨期考慮在內(nèi)。經(jīng)典的倉庫路徑優(yōu)化問題無法滿足船舶建造過程中不同安裝區(qū)域同時需要大批量舾裝件的需求，導(dǎo)致各個安裝區(qū)域無法在規(guī)定時間內(nèi)收到需要的舾裝件。Henn等[12]雖然考慮到交貨期，并以總延誤時間為優(yōu)化目標(biāo)進(jìn)行研究，但是只針對單揀選人員揀選貨物，并沒有分析多揀選人員同時揀選貨物的情況；Scholz等[13]雖然考慮了多揀選人員揀貨，并以總延誤時間為優(yōu)化目標(biāo)進(jìn)行研究，但是只適用于小規(guī)模問題，不適用于大批量托盤揀選問題。

本文針對上述研究的不足，結(jié)合船企集配中心托盤揀選的實(shí)際需求，充分考慮了托盤的交貨期，對雙揀選人員在集配中心同時揀選中、大規(guī)模舾裝件托盤的情況進(jìn)行深入研究，建立了以總延誤時間為優(yōu)化目標(biāo)，以完成時間、交貨期和揀貨設(shè)備容積為約束條件的數(shù)學(xué)模型。最后，根據(jù)某船廠的實(shí)際托盤揀選數(shù)據(jù)，通過比較改進(jìn)遺傳算法(Improved Genetic Algorithm，IGA)和標(biāo)準(zhǔn)遺傳算法(Genetic Algorithm，GA)，驗證了本文提出的基于IGA的托盤揀選方法解決舾裝件托盤揀選問題的有效性。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述

本文研究的舾裝件托盤揀選問題采用經(jīng)典的船企集配中心單區(qū)型倉庫布局模型，后續(xù)研究均在單區(qū)型倉庫布局模型的基礎(chǔ)上進(jìn)行。單區(qū)型倉庫由一定數(shù)量的等長揀選通道和上下兩端過道組成，揀選通道兩側(cè)貨架上存放著需要揀取的舾裝件；出入口位于下方過道的最左側(cè)，它是每次揀選舾裝件的起點(diǎn)和終點(diǎn)。圖1所示為本文應(yīng)用的倉庫布局模型，該模型有10個等長揀選通道和上下兩端過道，每一條揀選通道兩側(cè)都有30個儲物點(diǎn)。

下面以一個實(shí)例來闡述雙揀選人員舾裝件托盤的分批、指派及排序(Outfitting Pallets Batching, Assigning and Sequencing，OPBAS)問題。實(shí)例包括8個托盤，各托盤均有確定的交貨期和舾裝件組成清單，首先將8個托盤分成4批，每個揀選人員負(fù)責(zé)揀選2批托盤。圖2所示為初始揀選方案。

圖中的圓內(nèi)有3部分?jǐn)?shù)字，其中左上角數(shù)字表示托盤編號，右上角時間表示交貨期，下方數(shù)字表示托盤的舾裝件組成[13]。下面改變托盤的指派方案，將第3批次的托盤交由揀選人員2進(jìn)行揀選，將第4批次托盤交由揀選人員1進(jìn)行揀選，得到的揀選方案如圖3所示。

改變托盤分批的排序方式，調(diào)換第2批次和第4批次托盤的揀選順序，得到的揀選方案如圖4所示。

通過圖3和圖4可以看出，改變指派和改變排序后的方案明顯與原來方案的完成時間有很大不同，與單揀選人員揀選舾裝件相比，雙揀選人員揀選舾裝件時還應(yīng)考慮托盤指派問題。揀選人員揀選舾裝件時，不同的揀選路徑也會對完成時間產(chǎn)生影響。實(shí)際中的揀選人員經(jīng)常使用S型路徑策略揀選舾裝件，該策略描述如下：如果一個揀選通道上至少包括一個需要揀選的舾裝件，則揀選人員必須進(jìn)入該揀選通道并完全穿過該通道前往下一個包括舾裝件的揀選通道，然后返回出入口。一種特殊情況是，如果包括舾裝件的揀選通道的數(shù)目是奇數(shù)，則揀選人員將到達(dá)最后一個揀選通道上最遠(yuǎn)端存放舾裝件的位置，然后原路返回到過道，最后返回出入口。S型路徑策略示意圖如圖5所示。

本文在后續(xù)的模型建立和算法設(shè)計中，設(shè)定揀選人員揀選舾裝件時均采用S型路徑策略。在集配中心，舾裝件托盤分批分為靜態(tài)分批和動態(tài)分批[14]，其中靜態(tài)分批中所有托盤的交貨期和舾裝件組成均提前確定，動態(tài)分批則是托盤可以在任意時間點(diǎn)到達(dá)集配中心。本文主要考慮靜態(tài)分批的情況，下述工作均在靜態(tài)分批基礎(chǔ)上提出并完成。

由引言部分及上述內(nèi)容可知，雙揀選人員OPBAS問題可以描述為托盤分批問題、分批指派問題和分批排序問題，而且這3個問題聯(lián)系緊密，改變其中任何一個都會影響最終結(jié)果，相比于單揀選人員的托盤分批揀選問題，雙揀選人員OPBAS問題的主要特點(diǎn)是為雙揀選人員同時找出最佳托盤分批和分批排序方案。在揀貨設(shè)備容積確定的前提下，隨著托盤數(shù)量的增加，托盤分批方案的數(shù)量呈指數(shù)級增長，分批指派方案的數(shù)量隨托盤分批方案數(shù)量的增加而增加，分批排序方案的數(shù)量隨分批指派方案數(shù)量的增加呈指數(shù)級增長，因此該問題的求解難點(diǎn)是可行解的數(shù)量隨托盤數(shù)量的增加呈幾何數(shù)級增長，運(yùn)用啟發(fā)式算法難以在合理的時間內(nèi)求出該問題的滿意解。

1.2 數(shù)學(xué)模型

在實(shí)際求解過程中，單揀選人員揀選問題已經(jīng)被證明是NP-hard難題，雙揀選人員OPBAS問題不僅需要考慮單揀選人員揀選時的托盤分批和分批排序問題，還需考慮分批指派問題，因此雙揀選人員揀選托盤問題也被證明是NP-hard難題。本文研究的雙揀選人員OPBAS問題中，集配中心采用如圖1所示的單區(qū)型倉庫布局模型，而且集配中心有足夠數(shù)量的揀貨容積均為C的揀貨設(shè)備；揀選人員揀選每一批次托盤前的準(zhǔn)備時間均為ts，單位長度行走時間均為th，確認(rèn)和揀取每一個舾裝件的時間均為tp;揀選任務(wù)中托盤的數(shù)目為n，托盤集合為J，第j個托盤所包含的舾裝件總體積為cj，同時該托盤的交貨期為dj；在實(shí)際揀選過程中，n個托盤分成I個批次進(jìn)行揀選，第i批次的托盤處理時間為pti，揀選第i批次托盤中所有舾裝件所要行走的距離為hi，第j個托盤的揀選完成時間為ctj，該時間為該托盤所處批次托盤的處理時間，同時第j個托盤的揀選延誤時間為tarj；問題目標(biāo)是為雙揀選人員同時找出最佳托盤分批和分批排序方案，以滿足托盤揀選的實(shí)際需求，使托盤揀選總延誤時間最短。

目標(biāo)函數(shù)如下：

在船舶的實(shí)際建造過程中，托盤揀選環(huán)節(jié)的舾裝進(jìn)度拖延對船舶建造整體造成影響的范圍較大，帶來的經(jīng)濟(jì)損失比較嚴(yán)重；另外，由于舾裝過程中舾裝件數(shù)量巨大，只有保證舾裝件在揀選過程不產(chǎn)生延誤或產(chǎn)生的延誤較小，后續(xù)的配送和安裝環(huán)節(jié)才能及時進(jìn)行。因此為了使托盤揀選滿足實(shí)際需求，將托盤揀選總延誤時間作為優(yōu)化目標(biāo)，確保大部分托盤在揀選過程中不產(chǎn)生延誤，目標(biāo)函數(shù)數(shù)學(xué)表達(dá)式為

(1)

式中tarj為托盤j的揀選延誤時間，其等于托盤j的揀選完成時間ctj及其交貨期dj的差值，如果ctj

tarj=max{ctj-dj,0},?j∈J。

(2)

約束條件如下：

(1)確定某個托盤處于某一批次的托盤分批中。

(3)

(2)確定某一批次托盤分批由某一個揀選人員進(jìn)行揀選。

(4)

(3)每一批次的托盤分批中至少包含一個托盤。

(5)

(4)一個托盤能且只能分到某一批次托盤分批中，即一個托盤不能分成兩批進(jìn)行揀選。

(6)

(5)每一個揀選人員至少揀選一個批次的托盤。

(7)

(6)一個托盤分批能且只能由某個揀選人員揀選，即一個托盤分批不能由兩個揀選人員揀選。

(8)

(7)每一批次托盤所包括的舾裝件總體積小于揀貨設(shè)備的揀貨容積。

(9)

(8)某一個托盤的完成時間等于該托盤所處批次的處理時間。

(10)

(9)某一批次托盤的處理時間為

(11)

輸入條件為在集配中心同時收到n個有交貨期的托盤，而且每個托盤的舾裝件組成清單均已明確；輸出條件為雙揀選人員在揀選過程中只有同時滿足全部約束條件，才會各自得到合理的托盤分批和分批排序方案。

2 托盤揀選優(yōu)化的改進(jìn)遺傳算法設(shè)計

2.1 算法策略

針對雙揀選人員OPBAS問題的主要特點(diǎn)，即為雙揀選人員同時找出最佳托盤分批以和分批排序方案，常規(guī)求解順序是先將托盤指派給雙揀選人員，然后將雙揀選人員分到的托盤進(jìn)行分批處理，最后再將各自托盤分批進(jìn)行排序處理。然而這種求解順序耗時過長，因為在進(jìn)行托盤指派時會隨機(jī)指派一部分托盤給某一揀選人員，然后將剩余托盤指派給另一揀選人員，所以在托盤指派過程會產(chǎn)生大量隨機(jī)指派方案，其數(shù)量會隨托盤數(shù)量的增加呈指數(shù)級增長，同時托盤分批方案數(shù)量和分批排序方案數(shù)量也會隨指派方案數(shù)量的增加而增加，導(dǎo)致求解耗時過長。

針對上述問題，本文采用逆向求解方式對數(shù)學(xué)模型進(jìn)行求解。首先打亂所有托盤的排列順序，目的是為后續(xù)的指派操作和分批操作在更短的時間內(nèi)提供更多的解決方案；然后將排序后的托盤前半部分指派給第1位揀選人員，后半部分指派給第2位揀選人員，以降低指派方案的復(fù)雜度，縮短求解時間，同時盡量保證雙揀選人員的工作量相當(dāng)；最后將每一位揀選人員分得的托盤按照既定順序進(jìn)行分批處理，目的同樣是降低分批方案的復(fù)雜度，縮短求解時間。采用逆向求解方式對數(shù)學(xué)模型進(jìn)行求解，實(shí)際上是將雙揀選人員OPBAS問題轉(zhuǎn)化為尋找最優(yōu)托盤排序序列的問題，這種求解方法可以在合理的時間內(nèi)尋找到滿意解。

在求解OPBAS這類NP-hard難題時通常采用智能優(yōu)化算法，其中采用GA求解OPBAS問題較為常見，然而GA在求解過程中容易陷入局部最優(yōu)，鑒于此，本文對GA進(jìn)行改進(jìn)，采用最早交貨期(Earliest Due Date，EDD)啟發(fā)式方法進(jìn)行種群初始化；在遺傳算子設(shè)計過程中的選擇、交叉、變異操作后引入進(jìn)化逆轉(zhuǎn)和插入操作，從而在種群陷入局部最優(yōu)解時，通過進(jìn)化逆轉(zhuǎn)操作和插入操作增加種群的多樣性，使種群跳出局部最優(yōu)解，能夠繼續(xù)搜索全局最優(yōu)解。

本文提出一種基于IGA的舾裝件托盤揀選優(yōu)化方法，其基本思路是結(jié)合數(shù)學(xué)模型中可行解的性質(zhì)，采用逆向求解方法進(jìn)行求解。算法初始階段采用EDD啟發(fā)式方法進(jìn)行種群初始化，然后充分利用選擇操作、交叉操作和變異操作的快速性、隨機(jī)性和全局收斂性，以及進(jìn)化逆轉(zhuǎn)操作和插入操作帶來的種群多樣性，防止種群陷入局部最優(yōu)解，從而快速生成全局最優(yōu)的托盤分批和分批排序序列[15]。IGA求解OPBAS問題的具體步驟如圖6所示。

2.2 編碼生成

對于雙揀選人員OPBAS問題，按照2.1節(jié)描述的常規(guī)求解順序求解問題時，通常采用基于托盤的雙層編碼方式，雙層編碼染色體為{1,10,2,4,5,6,8,7,9,3|1,2,1,2,1,2,1,2,1,2}，第一層染色體表示托盤的揀選順序，第二層染色體表示托盤揀選人員?？梢钥闯?，雙層編碼染色體長度過長會導(dǎo)致進(jìn)化過程中的尋優(yōu)時間過長。針對尋優(yōu)時間過長的問題，本文采用2.1節(jié)提出的的逆向求解順序?qū)﹄p揀選人員OPBAS問題進(jìn)行求解，將該問題轉(zhuǎn)化為尋找一個最佳托盤排序序列。因此，對于n個托盤的分批指派排序問題，本文采用基于托盤的單層編碼方式，將染色體分為n段，每一段為對應(yīng)托盤的編號，例如{1,10,2,4,5,6,8,7,9,3}為一個合法的染色體，其中{1,10,2,4,5}表示第1位揀選人員需要揀選的托盤，{6,8,7,9,3}表示第2位揀選人員需要揀選的托盤。假設(shè)每一舾裝件的體積均為單位體積，則每一托盤中舾裝件的總體積如表1所示。

表1 每一托盤中舾裝件的總體積

每一位揀選人員按照指定的托盤揀選順序分批揀選，同時滿足每一批次托盤中舾裝件的總體積不超過揀貨設(shè)備容積，假設(shè)揀貨設(shè)備容積均為30，則雙揀選人員進(jìn)行托盤分批和分批排序的結(jié)果如表2所示。

表2 雙揀選人員進(jìn)行托盤分批和分批排序的結(jié)果

2.3 求解過程

2.3.1 初始種群

在完成染色體編碼以后，需要產(chǎn)生一個初始種群作為初始解，這里需要注意兩個問題，即確定初始化種群的數(shù)目和產(chǎn)生初始種群的方法。初始化種群的數(shù)目一般根據(jù)經(jīng)驗得到，種群數(shù)量通常視托盤數(shù)量而定，其取值在20～200之間浮動，本文選取種群的數(shù)目為200。

產(chǎn)生初始種群的方法有隨機(jī)方法和啟發(fā)式方法兩種，前者隨機(jī)產(chǎn)生所有初始個體，后者按照EDD啟發(fā)式方法產(chǎn)生所有初始個體。采用隨機(jī)方法產(chǎn)生初始種群容易產(chǎn)生大量劣質(zhì)個體，GA采用這種方法產(chǎn)生初始種群不能保證優(yōu)化質(zhì)量； EDD啟發(fā)式方法將所有托盤按照交貨期的先后順序排序，將奇數(shù)序號的托盤排在第一部分，偶數(shù)序號的托盤排在第二部分，由此生成初始種群。本文設(shè)計的IGA則采用EDD啟發(fā)式方法產(chǎn)生所有初始個體。

2.3.2 適應(yīng)度函數(shù)

因為優(yōu)化目標(biāo)是總延誤時間最小，同時要求適應(yīng)度函數(shù)為非負(fù)，且適應(yīng)度值越大越好，所以托盤揀選延誤時間的適應(yīng)度函數(shù)定義為

(12)

2.3.3 選擇操作

在選擇需要保留的最優(yōu)托盤揀選序列個體時，采用輪盤賭選擇策略和精英選擇策略，不但可以防止在進(jìn)化過程中丟失最優(yōu)解，而且能夠加快算法收斂速度。

2.3.4 交叉操作

本文采用雙點(diǎn)交叉法對染色體進(jìn)行交叉操作，具體步驟如下(假定托盤數(shù)量為10)：

(1)產(chǎn)生一個[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個位置，對兩個位置之間的托盤進(jìn)行交叉，如a1=4，a2=7。將父代1=2 6 3|4 7 1 9|8 5 10和父代2=3 5 2|6 1 9 10|4 7 8交叉為子代1=2 * 3|6 1 9 10|8 5 *，子代2=3 5 2|4 7 1 9| * * 8。

(2)交叉后，同一個個體會有重復(fù)的托盤，保留不重復(fù)的托盤，有沖突的托盤(帶*位置)按照中間段的對應(yīng)順序進(jìn)行映射。本例中子代1的中間段為(6 1 9 10)，子代2的中間段為(4 7 1 9)，子代1的沖突托盤為6和10，因此需要利用子代2中間段的4和7進(jìn)行補(bǔ)位，補(bǔ)位順序按照(4 7 1 9)中4和7的順序進(jìn)行，子代2也按照上述方法補(bǔ)位，結(jié)果為子代1=2 4 3|6 1 9 10|8 5 7，子代2=3 5 2|4 7 1 9|6 10 8。

2.3.5 變異操作

OPBAS問題變異主要是前后順序的變異。對于OPBAS這個特定的問題來說，每個托盤的排序還受揀貨設(shè)備容積和揀選人員工作狀態(tài)的影響，則此處變異過程的操作步驟如下(假定托盤數(shù)量為10)：產(chǎn)生一個[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個位置，然后將其對換，如a1=3，a2=8。將2 4|3|6 1 9 10|8| 5 7變異后為2 4|8| 6 1 9 10|3| 5 7。

2.3.6 進(jìn)化逆轉(zhuǎn)操作

為改善GA的局部搜索能力，在選擇、交叉、變異后引進(jìn)連續(xù)多次進(jìn)化逆轉(zhuǎn)操作[16]，這里的“進(jìn)化”是指逆轉(zhuǎn)托盤排序的方向，即經(jīng)過逆轉(zhuǎn)后，只有適應(yīng)度值提高的染色體才可以繼續(xù)存活，否則逆轉(zhuǎn)無效。進(jìn)化逆轉(zhuǎn)操作如下：產(chǎn)生一個[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個位置，然后將兩個位置之間的托盤序列進(jìn)行逆序排序，如a1=3，a2=8。將2 4|3 6 1 9 10 8|5 7進(jìn)化逆轉(zhuǎn)后為2 4|8 10 9 1 6 3|5 7。

其中A圖根據(jù)2001年《中華人民共和國教育部義務(wù)教育數(shù)學(xué)教學(xué)課程(實(shí)驗版)》發(fā)表之前的小學(xué)數(shù)學(xué)內(nèi)容勾勒，B圖根據(jù)美國2000 NCTM《中小學(xué)數(shù)學(xué)教育的原則與課程標(biāo)準(zhǔn)》勾勒[8].

2.3.7 插入操作

為了改善GA的局部搜索能力，在進(jìn)化逆轉(zhuǎn)操作后引進(jìn)插入操作，這里的插入操作是指將某一個位置的托盤插入到另一個位置。經(jīng)過插入操作后，只有適應(yīng)度值提高的染色體才可以繼續(xù)存活，否則插入無效。插入操作如下：產(chǎn)生一個[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個位置，然后將第一個位置的托盤插入到第二個位置，如a1=3，a2=8。將2 4|3 6 1 9 10 8|5 7插入后為2 4|6 1 9 10 8 3|5 7。

綜上所述，本文設(shè)計的IGA的思路如圖7所示。

3 實(shí)例驗證與算法性能評估

為驗證本文IGA求解的有效性，選取某船廠建造過程中托盤揀選的相關(guān)數(shù)據(jù)，分別使用GA和IGA進(jìn)行求解。下面給出兩個具體實(shí)例，實(shí)例1中有50個托盤，每個托盤中舾裝件的數(shù)量為5～15個，每個舾裝件的體積為1單位體積，每臺揀貨設(shè)備的最大揀貨容積C=30，即每臺揀貨設(shè)備一次最多裝30單位體積的舾裝件；實(shí)例2中有100個托盤，每個托盤中舾裝件的數(shù)量為5～15個，每個舾裝件的體積為1單位體積，每臺揀貨設(shè)備的最大揀貨容積C=50，即每臺揀貨設(shè)備一次最多裝50單位體積的舾裝件。GA和IGA的參數(shù)如表3所示。

表3 GA和IGA的參數(shù)

每個托盤的交貨期均已提前確定，每個揀選人員所需要的時間參數(shù)也已確定且相同。其中每個揀選人員需要花費(fèi)2 s行走1個單位長度的距離，需要花費(fèi)10 s尋找和揀選一個舾裝件，每次揀選之前的準(zhǔn)備時間為120 s。1.1節(jié)已經(jīng)說明，揀選人員在揀選過程中均采用S型路徑策略。表4所示為實(shí)例1中50個托盤中的舾裝件以及每個托盤的交貨期，其中交貨期為換算出的時間長度，即用交貨期減去集配中心接收到托盤的時間，例如托盤的交貨期是16:00，集配中心接收到托盤的時間是15:30，則換算出的交貨期為30 min。

表4 實(shí)例1中50個托盤的舾裝件組成和交貨期時間

續(xù)表4

分別采用基于EDD、基于GA和基于IGA的托盤揀選方法對上述50個托盤進(jìn)行揀選處理，將3種揀選方法的完成時間、延誤時間、延誤托盤數(shù)量和總延誤時間進(jìn)行對比，如表5和表6所示。

表5 實(shí)例1中50個托盤采用3種不同揀選方法的完成時間和延誤時間對比 min

續(xù)表5

續(xù)表5

表6 實(shí)例1中50個托盤采用3種不同揀選方法的延誤托盤數(shù)量和總延誤時間對比

從表6可以看出，分別采用基于EDD、基于GA和基于IGA的托盤揀選方法時，延誤托盤數(shù)量分別為42，35，28。同時由表6計算可得，分別采用GA和IGA對初始解進(jìn)行優(yōu)化時，總延誤時間分別降低30.84%和49.08%。

表7 實(shí)例2中100個托盤的舾裝件組成和交貨期時間表

續(xù)表7

續(xù)表7

同樣分別采用基于EDD、基于GA和基于IGA的托盤揀選方法對上述100個托盤進(jìn)行揀選處理，將3種揀選方法的完成時間、延誤時間、延誤托盤數(shù)量和總延誤時間進(jìn)行對比，如表8和表9所示。

表8 實(shí)例2中100個托盤采用3種不同揀選方法的完成時間和延誤時間對比 min

續(xù)表8

續(xù)表8

續(xù)表8

表9 實(shí)例2中100個托盤采用3種不同揀選方法的延誤托盤數(shù)量和總延誤時間對比

從表9可以看出，分別采用基于EDD、基于GA和基于IGA的托盤揀選方法時，延誤托盤數(shù)量分別為30，12，1。同時由表9計算可得，分別采用GA和IGA對初始解進(jìn)行優(yōu)化，總延誤時間分別降低77.24%和98.73%。

通過上述兩個測試算例可以看出，本文所提優(yōu)化揀選方法可以大幅縮短揀選延誤時間。因此，為進(jìn)一步驗證該優(yōu)化揀選方法的有效性，需擴(kuò)大數(shù)值實(shí)驗的規(guī)模。新增數(shù)值實(shí)驗中交貨期的生成方法為：計算出所有托盤的完成時間，將其中最大值的1/2和最小值作為交貨期區(qū)間的上界和下界，采用正態(tài)分布的方式隨機(jī)產(chǎn)生各個托盤的交貨期，具體的數(shù)學(xué)表達(dá)式如下：

0≤MTCR≤1。

(13)

式中MTCR為修正運(yùn)輸阻塞率，用于描述交貨期的緊密程度[17]。MTCR越大，交貨期生成的區(qū)間越小，表示托盤的交貨期越緊密，托盤越容易產(chǎn)生延誤；MTCR越小，交貨期生成的區(qū)間越大，表示托盤的交貨期越松弛，托盤越不容易產(chǎn)生延誤。新增實(shí)驗中托盤數(shù)量n分別取值為100，150，200，250，300，揀貨設(shè)備容積C分別取值為30，50，MTCR分別取值為0.5，0.6，0.7，因此數(shù)值實(shí)驗一共分為30(5×2×3)種情況。測試指標(biāo)為總延誤時間tar、延誤托盤數(shù)量no_tar、總延誤時間優(yōu)化百分比imp。測試結(jié)果如表10所示。

表10 3種揀選方法的實(shí)驗數(shù)據(jù)對比

由上述實(shí)驗數(shù)據(jù)可以看出，在參數(shù)n和C取值均相同的條件下，總延誤時間和延誤托盤數(shù)量均隨MTCR的增大而增大，優(yōu)化百分比隨MTCR的增大而減小，這恰好說明MTCR越大，交貨期生成區(qū)間越小，托盤的交貨期越緊密，托盤越容易產(chǎn)生延誤，從而降低優(yōu)化效果；在參數(shù)C和MTCR取值均相同的條件下，總延誤時間和延誤托盤數(shù)量均隨n的增大而增大，優(yōu)化百分比隨n的增大而減小，表明隨著托盤數(shù)量的增加，揀貨設(shè)備容積有限會降低優(yōu)化效果；在參數(shù)n和MTCR取值均相同的條件下，總延誤時間和延誤托盤數(shù)量均隨C的增大而減小，優(yōu)化百分比隨C的增大而增大，表明隨著揀貨設(shè)備容積的增加，優(yōu)化效果有明顯提升。

在參數(shù)n，C，MTCR取值均相同的條件下，tarEDD>tarGA>tarIGA，no_tarEDD>no_tarGA>no_tarIGA，impIGA>impGA，其中：tarEDD，tarBGA，tarIGA分別表示采用3種揀選方法時產(chǎn)生的托盤揀選延誤時間，no_tarEDD，no_tarBGA，no_tarIGA分別表示采用3種揀選方法時的延誤托盤數(shù)量。當(dāng)采用基于GA和IGA的托盤揀選方法時，延誤托盤的數(shù)量為初始種群經(jīng)過算法優(yōu)化后所有個體的延誤托盤數(shù)量之和與個體數(shù)量的比值，impIGA和impGA分別表示采用IGA和GA優(yōu)化初始解時的托盤延誤時間優(yōu)化百分比。上述3個不等式充分說明本文提出的基于IGA的托盤揀選方法對總延誤時間的優(yōu)化效果好于基于GA的托盤揀選方法。上述實(shí)驗數(shù)據(jù)中，采用GA優(yōu)化托盤揀選延誤時間問題時，最小優(yōu)化百分比僅為1.72(n=250,C=50,MTCR=0.5)，最大優(yōu)化百分比為93.84(n=300,C=50,MTCR=0.5)；采用IGA優(yōu)化托盤揀選延誤時間問題時，最小優(yōu)化百分比為21.12(n=300,C=30,MTCR=0.7)，最大優(yōu)化百分比達(dá)到95.51(n=300,C=50,MTCR=0.5)。兩種優(yōu)化方法之所以出現(xiàn)最小優(yōu)化百分比，是因為初始解的質(zhì)量已經(jīng)很高，優(yōu)化空間十分有限；而兩種優(yōu)化方法出現(xiàn)最大優(yōu)化百分比的原因是，n越大托盤數(shù)量越大，C越小揀貨設(shè)備容積越小，MTCR越大交貨期區(qū)間越小，托盤揀選總延誤時間越長，從而使優(yōu)化空間更大，優(yōu)化效果更好。同時根據(jù)上述實(shí)驗數(shù)據(jù)也可計算出，分別采用GA和IGA優(yōu)化托盤揀選延誤時間問題時的平均優(yōu)化百分比為26.46和43.33，原因是GA求解該問題時，在初始階段采用隨機(jī)方法生成初始種群會產(chǎn)生大量劣質(zhì)個體，經(jīng)過交叉操作和變異操作，在后續(xù)尋優(yōu)過程中容易陷入局部最優(yōu)解；IGA求解該問題時采用EDD啟發(fā)式方法生成初始種群，能夠避免產(chǎn)生大量劣質(zhì)個體，提高了后續(xù)操作的優(yōu)化質(zhì)量，同時在交叉操作和變異操作后引入進(jìn)化逆轉(zhuǎn)操作和插入操作，通過提高種群多樣性打破了原來陷入局部最優(yōu)解的局面，從而跳出局部最優(yōu)解繼續(xù)搜索全局最優(yōu)解，使解的質(zhì)量得到提高。上述一系列對比分析充分說明，相對于基于GA的托盤揀選方法，本文所提基于IGA的托盤揀選方法能更高效地降低舾裝件托盤揀選延誤時間。

4 結(jié)束語

為解決船舶建造中的舾裝件托盤揀選延誤時間過長的問題，本文以完成時間、交貨期和揀貨設(shè)備容積為約束條件，建立以總延誤時間為優(yōu)化目標(biāo)的數(shù)學(xué)模型，并提出基于IGA的舾裝件托盤揀選方法。通過實(shí)驗從總延誤時間、延誤托盤數(shù)量和延誤時間優(yōu)化百分比3方面與基于GA的托盤揀選方法進(jìn)行對比，表明本文提出的基于IGA的托盤揀選方法可以大幅縮短托盤揀選的總延誤時間，進(jìn)而減少船舶后續(xù)建造過程中因托盤延期送達(dá)帶來的一系列經(jīng)濟(jì)損失。因此，針對實(shí)際揀選過程中的托盤揀選延誤時間過長的問題，本文方法具有一定的實(shí)用價值和理論研究意義。在后續(xù)研究中，擬在數(shù)學(xué)模型中考慮阻塞問題和動態(tài)分批問題，并為模型設(shè)計相應(yīng)的求解算法，以進(jìn)一步提高研究的實(shí)用性。