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

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

0 引言

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

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

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

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

1.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

(1)

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

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

(2)

約束條件如下：

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

(8)

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

(9)

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

(10)

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

(11)

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

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

2.1 算法策略

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

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

在求解OPBAS這類NP-hard難題時(shí)通常采用智能優(yōu)化算法，其中采用GA求解OPBAS問(wèn)題較為常見(jiàn)，然而GA在求解過(guò)程中容易陷入局部最優(yōu)，鑒于此，本文對(duì)GA進(jìn)行改進(jìn)，采用最早交貨期(Earliest Due Date，EDD)啟發(fā)式方法進(jìn)行種群初始化；在遺傳算子設(shè)計(jì)過(guò)程中的選擇、交叉、變異操作后引入進(jìn)化逆轉(zhuǎn)和插入操作，從而在種群陷入局部最優(yōu)解時(shí)，通過(guò)進(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)操作和插入操作帶來(lái)的種群多樣性，防止種群陷入局部最優(yōu)解，從而快速生成全局最優(yōu)的托盤分批和分批排序序列[15]。IGA求解OPBAS問(wèn)題的具體步驟如圖6所示。

2.2 編碼生成

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

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

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

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

2.3 求解過(guò)程

2.3.1 初始種群

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

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

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

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

(12)

2.3.3 選擇操作

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

2.3.4 交叉操作

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

(1)產(chǎn)生一個(gè)[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個(gè)[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個(gè)位置，對(duì)兩個(gè)位置之間的托盤進(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)交叉后，同一個(gè)個(gè)體會(huì)有重復(fù)的托盤，保留不重復(fù)的托盤，有沖突的托盤(帶*位置)按照中間段的對(duì)應(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問(wèn)題變異主要是前后順序的變異。對(duì)于OPBAS這個(gè)特定的問(wèn)題來(lái)說(shuō)，每個(gè)托盤的排序還受揀貨設(shè)備容積和揀選人員工作狀態(tài)的影響，則此處變異過(guò)程的操作步驟如下(假定托盤數(shù)量為10)：產(chǎn)生一個(gè)[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個(gè)[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個(gè)位置，然后將其對(duì)換，如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)過(guò)逆轉(zhuǎn)后，只有適應(yīng)度值提高的染色體才可以繼續(xù)存活，否則逆轉(zhuǎn)無(wú)效。進(jìn)化逆轉(zhuǎn)操作如下：產(chǎn)生一個(gè)[1,5]范圍內(nèi)的隨機(jī)整數(shù)a1和一個(gè)[6,10]范圍內(nèi)的隨機(jī)整數(shù)a2，確定兩個(gè)位置，然后將兩個(gè)位置之間的托盤序列進(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年《中華人民共和國(guó)教育部義務(wù)教育數(shù)學(xué)教學(xué)課程(實(shí)驗(yàn)版)》發(fā)表之前的小學(xué)數(shù)學(xué)內(nèi)容勾勒，B圖根據(jù)美國(guó)2000 NCTM《中小學(xué)數(shù)學(xué)教育的原則與課程標(biāo)準(zhǔn)》勾勒[8].

2.3.7 插入操作

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

3 實(shí)例驗(yàn)證與算法性能評(píng)估

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

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

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

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

續(xù)表4

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

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

續(xù)表5

續(xù)表5

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

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

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

續(xù)表7

續(xù)表7

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

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

續(xù)表8

續(xù)表8

續(xù)表8

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

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

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

0≤MTCR≤1。

(13)

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

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

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

4 結(jié)束語(yǔ)

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