基于單雙親混合GA的復(fù)雜揀選作業(yè)優(yōu)化

李 曉，項(xiàng) 前＋，呂志軍，管樹林（.東華大學(xué) 機(jī)械工程學(xué)院，上海060；.上海精星倉(cāng)儲(chǔ)設(shè)備工程有限公司，上海06）

0 引 言

對(duì)于揀貨作業(yè)優(yōu)化問(wèn)題的研究，曾經(jīng)有學(xué)者利用啟發(fā)式算法［1］研究訂單分批策略，在此基礎(chǔ)上對(duì)揀選路徑進(jìn)行優(yōu)化；也有學(xué)者把揀選作業(yè)優(yōu)化問(wèn)題抽象成旅行商 （TSP）問(wèn) 題，分 別 利 用 遺 傳 算 法［2，3］、蟻 群 算 法［4，5］、多 種 群 果 蠅算法［6］、啟發(fā)式TSP算法［7］、MMAS算法［8］等對(duì)此問(wèn)題進(jìn)行過(guò)研究，且取得了不錯(cuò)的效果。然而以上研究方法簡(jiǎn)化了問(wèn)題的復(fù)雜性，忽略了裝箱約束條件，王占磊［9］、周超［10］等在考慮了裝箱約束條件的前提下，對(duì)單一作業(yè)揀選優(yōu)化問(wèn)題進(jìn)行了研究；由于配送中心很多時(shí)候同時(shí)進(jìn)行多個(gè)出入庫(kù)作業(yè)，周軍等［11］在兼顧最小路徑原則和先進(jìn)先出原則的基礎(chǔ)上，對(duì)復(fù)合作業(yè)揀選路徑優(yōu)化進(jìn)行了研究。以上都取得了可喜的研究成果，但忽略了多品項(xiàng)揀選時(shí)復(fù)雜約束條件。據(jù)此，本文在考慮多品項(xiàng)約束的前提下，建立儲(chǔ)存區(qū)復(fù)雜揀選作業(yè)優(yōu)化模型，基于一種單雙親混合GA對(duì)作業(yè)順序和儲(chǔ)位分配同時(shí)進(jìn)行優(yōu)化求解，以達(dá)到縮短揀選路徑、提高揀選效率的目標(biāo)。

1 復(fù)雜揀選作業(yè)優(yōu)化模型

1.1 模型描述與假設(shè)

（1）儲(chǔ)存區(qū)布局：如圖1所示，出入庫(kù)臺(tái)位于貨架的同側(cè)，每條揀貨巷道都設(shè)有一臺(tái)堆垛機(jī)。一個(gè)儲(chǔ)物單元包括：兩排貨架、一條揀貨通道、一臺(tái)堆垛機(jī)；本文僅對(duì)單個(gè)倉(cāng)儲(chǔ)單元的揀選作業(yè)進(jìn)行優(yōu)化求解；

圖1 儲(chǔ)存區(qū)布局

（2）揀選作業(yè)工作流程：堆垛機(jī)接收到倉(cāng)儲(chǔ)控制系統(tǒng)（WCS）發(fā)送的出入庫(kù)任務(wù)序列后，從出入庫(kù)臺(tái)出發(fā)，首先運(yùn)行至第一作業(yè)任務(wù)的目標(biāo)儲(chǔ)位，對(duì)其進(jìn)行存取操作；然后執(zhí)行下一個(gè)作業(yè)任務(wù)，直至所有的作業(yè)任務(wù)完成，若改變?nèi)蝿?wù)序列的順序，將有不同的揀選路徑與之對(duì)應(yīng)；

（3）每個(gè)儲(chǔ)位只能存放一個(gè)貨物單元 （托盤或集裝箱）［12］，且貨架上的品項(xiàng)儲(chǔ)存類型和存放狀態(tài) （有物料／無(wú)物料）已知，因此求解過(guò)程中可及時(shí)查詢獲得各品項(xiàng)的出入庫(kù)約束域；

（4）堆垛機(jī)的每次存取操作對(duì)象為單個(gè)品項(xiàng)的一個(gè)貨物單元，堆垛機(jī)對(duì)每個(gè)操作品項(xiàng)的存、取動(dòng)作所用時(shí)間相等；

（5）堆垛機(jī)勻速運(yùn)行，故可用堆垛機(jī)運(yùn)行路徑來(lái)衡量堆垛機(jī)的存取效率；當(dāng)堆垛機(jī)執(zhí)行完最后一個(gè)任務(wù)后返回到出入庫(kù)臺(tái)。

1.2 復(fù)雜揀選作業(yè)數(shù)學(xué)模型

1.2.1 模型相關(guān)符號(hào)描述

（1）MRxC：?jiǎn)闻咆浖軆?chǔ)存矩陣，R 表示貨架層數(shù)，C表示貨架列數(shù)。MRxC第i 層第j 列的元素Mij∈Z（整數(shù)集），表示品項(xiàng)編碼號(hào)，Mij＞0時(shí)表示該儲(chǔ)位有物料存儲(chǔ)，Mij＜0時(shí)表示該儲(chǔ)位無(wú)物料；

（2）T：初始任務(wù)矩陣，T＝ （T1，T2，…，Tn），n∈Z＊（正整數(shù)集），代表任務(wù)的個(gè)數(shù)。其中Ti＝（typei，toi）T，typei表示任務(wù)類型，typei∈Z（整數(shù)集），表示品項(xiàng)編碼號(hào)，typei＞0時(shí)表示入庫(kù)任務(wù)，typei＜0時(shí)表示出庫(kù)任務(wù)，typei＝0時(shí)表示堆垛機(jī)在出入庫(kù)臺(tái)等待任務(wù)指令；toi表示目標(biāo)儲(chǔ)位編碼，toi∈Z＊（正整數(shù)集）；

（3）Loci：Loci表示第i個(gè)任務(wù)的目標(biāo)儲(chǔ)位，其由所處的排列層號(hào)k，r，c唯一表示，Loci＝ （ki，ri，ci），出入庫(kù)臺(tái)坐標(biāo)表示為：Loco＝ （0，0，0）。

1.2.2 目標(biāo)函數(shù)的確立

據(jù)1.1假設(shè)，取堆垛機(jī)完成一系列任務(wù)的總行程S作為優(yōu)化目標(biāo)

式中：Di——完成第i 個(gè)任務(wù)的作業(yè)行程，如表1 所示，歸納了其路徑組成。Di與前一個(gè)任務(wù)結(jié)束儲(chǔ)位Loci－1（當(dāng)前一個(gè)任務(wù)為首個(gè)任務(wù)或出庫(kù)任務(wù)時(shí)Loci－1＝Loco）、當(dāng)前任務(wù)的目標(biāo)儲(chǔ)位Loci、前一個(gè)任務(wù)類型typei－1、當(dāng)前任務(wù)類型typei、當(dāng)前任務(wù)是否為最后一個(gè)任務(wù) （用ξ表示，當(dāng)前任務(wù)為最后任務(wù)時(shí)ξ＝1，否則ξ＝0）有關(guān)，故Di可以表示為

綜合上述分析，Di的計(jì)算如下

其中，dist（Locm，Locn）表示同一倉(cāng)儲(chǔ)單元內(nèi)相鄰兩排貨架中目標(biāo)儲(chǔ)位Locm與Locn之間的距離，計(jì)算如下

1.2.3 約束域的確立

貨物的存儲(chǔ)遵循了一定的存儲(chǔ)策略，不同的品項(xiàng)存放在儲(chǔ)存區(qū)的不同區(qū)域，首先獲得品項(xiàng)出入庫(kù)約束域（MPN）：?jiǎn)蝹€(gè)品項(xiàng)出庫(kù)約束域即品項(xiàng)入庫(kù)可行域，單個(gè)品項(xiàng)入庫(kù)約束域即品項(xiàng)出庫(kù)可行域。

2 單雙親混合遺傳算法設(shè)計(jì)

2.1 模型編碼

（1）染色體編碼

染色體包括作業(yè)順序段染色體 （seq）和目標(biāo)儲(chǔ)位段染色體 （loc），seq 和loc 采用分開獨(dú)立編碼方式。如圖2 所示，其中seq的基因碼為T 的列索引，loc的基因碼對(duì)應(yīng)與目標(biāo)儲(chǔ)位編碼toi。

表1 Di 路徑組成

圖2 染色體結(jié)構(gòu)

（2）儲(chǔ)位編碼與解碼

每個(gè)儲(chǔ)位都有其唯一的地址：第k排r 層c 列，即 （k，r，c），儲(chǔ)位編碼codekrc的計(jì)算如下

式 （2）、式 （3）中codekrc表示儲(chǔ)位編碼后的編碼，MAX ＿CODE 表 示 儲(chǔ) 位 最 大 編 碼；其 中codekrc∈［0，MAX ＿CODE］，k＝0或1，r∈［0，R］，c∈［0，C］。

儲(chǔ)位的解碼過(guò)程為儲(chǔ)位編碼計(jì)算過(guò)程的逆運(yùn)算，已知codekrc、R、C 可求解儲(chǔ)位的排k、列r、層c。

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度是用來(lái)度量種群中個(gè)體優(yōu)劣的指標(biāo)。本文適應(yīng)度計(jì)算如下

式 （4）為計(jì)算單條染色體的適應(yīng)度值 （score）公式，式（5）為種群適應(yīng)度值 （scores）的表達(dá)式，其中m 為種群規(guī)模，scorei表示單條染色體的適應(yīng)度值。

2.3 創(chuàng)建初始種群

初始種群的創(chuàng)建過(guò)程如下：

步驟1 隨機(jī)排列1到n個(gè)任務(wù)來(lái)創(chuàng)建seq；

步驟2 獲取各品項(xiàng)出入庫(kù)約束域MPN，按照任務(wù)矩陣T 從MPN 中隨機(jī)抽取符合條件的儲(chǔ)位，參照seq段排列儲(chǔ)位順序創(chuàng)建loc段；

步驟3 組合創(chuàng)建好的seq和loc 為一條完整的染色體；

步驟4 重復(fù)步驟1～步驟3，直到創(chuàng)建完成PopulationSize （種群規(guī)模）條染色體。

2.4 交叉算子設(shè)計(jì)

交叉算子的設(shè)計(jì)思想是，seq 采用基因重組方式；loc基因重組后再采用雙親交叉方式；圖3為此過(guò)程圖解，其中P11、P21為seq，P12、P22為loc。

圖3 交叉算子設(shè)計(jì)圖解

步驟1 基因重組：選擇一個(gè)父體P1，把它分段為：P11和P12，再產(chǎn)生兩個(gè)隨機(jī)位置a1、a2，分別顛倒P11和P12上a1到a2間的基因碼的排列位置；

步驟2 loc雙親交叉：選擇另外一個(gè)父體P2，把它分段為：P21和P22，將P22和P12上同品項(xiàng)作業(yè)類型的儲(chǔ)位碼toi先合并為X，再?gòu)腦 中為該品項(xiàng)隨機(jī)抽取一個(gè)目標(biāo)儲(chǔ)位，按照l(shuí)oc段索引生成新的P12。

步驟3 組合P11和P12為一條新的完整的染色體P1；

步驟4 重復(fù)步驟1～步驟3，直到完成所選全部父體的交叉操作。

2.5 變異算子設(shè)計(jì)

變異算子的設(shè)計(jì)思想：seq采用基因重組方式；loc采用基因重組后再單點(diǎn)變異方式；變異算子設(shè)計(jì)過(guò)程如下，圖4為此過(guò)程圖解，其中P11為seq，P12為loc。

步驟1 基因重組：選擇一個(gè)父體P1，把它分段為：P21和P22，再產(chǎn)生兩個(gè)隨機(jī)位置m1、m2，交換P21和P22上m1和m2處的基因碼；

步驟2 loc 單點(diǎn)變異：首先產(chǎn)生一個(gè)隨機(jī)變異位置m，獲得m 位置處品項(xiàng)的typei及出／入庫(kù)可行域，取該品項(xiàng)的出／入庫(kù)可行域與m 位置toi的差集Y，從Y 中重新為該變異位置隨機(jī)抓取一個(gè)儲(chǔ)位完成變異基因位的變異操作；

步驟3 組合P11和P12為一條新的完整的染色體P1；

步驟4 重復(fù)步驟1～步驟3，直到完成所選全部父體的變異操作。

圖4 變異算子圖解

3 實(shí)驗(yàn)與分析

為了驗(yàn)證單雙親混合GA 對(duì)求解復(fù)雜揀選作業(yè)優(yōu)化問(wèn)題的有效性，基于基本GA 和單雙親混合GA，以MATLAB遺傳算法工具箱為實(shí)驗(yàn)環(huán)境，分別進(jìn)行單品項(xiàng)單一揀選作業(yè)、單品項(xiàng)復(fù)合揀選作業(yè)、多品項(xiàng)單一揀選作業(yè)、多品項(xiàng)復(fù)合揀選作業(yè)、缺貨報(bào)警作業(yè)實(shí)驗(yàn)，最后對(duì)兩種算法的優(yōu)化結(jié)果及優(yōu)化前后性能做了比較。實(shí)驗(yàn)設(shè)置如下：實(shí)驗(yàn)對(duì)象為一個(gè)倉(cāng)儲(chǔ)單元，由兩排5層10列的貨架和一條揀貨通道組成。此外，本文還做了算法參數(shù)優(yōu)化實(shí)驗(yàn)，分別測(cè)試了交叉概率 （CrossoverFraction）和種群規(guī)模 （PopulationSize）對(duì)適應(yīng)度影響及種群規(guī)模 （PopulationSize）和精英個(gè)體（EliteCount）對(duì)適應(yīng)度影響，其它算法參數(shù)設(shè)置見(jiàn)表2，算法主要參數(shù)對(duì)適應(yīng)度影響實(shí)驗(yàn)結(jié)果如圖5、圖6所示。

表2 實(shí)驗(yàn)案例算法參數(shù)設(shè)置

實(shí)驗(yàn)結(jié)果分析：當(dāng)PopulationSize＜20，Crossover－Fraction＜0.2或CrossoverFraction＞0.95時(shí)算法不易找到最優(yōu)解；當(dāng)EliteCount＞6時(shí)，算法很不穩(wěn)定。通過(guò)實(shí)驗(yàn)結(jié)果分析比較，優(yōu)選的實(shí)驗(yàn)算法參數(shù)設(shè)置見(jiàn)表2第3列。

圖5 PopulationSize－CrossoverFraction 測(cè)試結(jié)果

圖6 PopulationSize－EliteCount測(cè)試結(jié)果

3.1 單品項(xiàng)單一揀選與單品項(xiàng)復(fù)合揀選作業(yè)實(shí)驗(yàn)

單品項(xiàng)單一揀選與單品項(xiàng)復(fù)合揀選作業(yè)實(shí)驗(yàn)，作業(yè)任務(wù)分別為：品項(xiàng)3的10次出庫(kù)作業(yè)、品項(xiàng)3的5次出庫(kù)和入庫(kù)作業(yè)。根據(jù)下達(dá)的任務(wù)，首先搜索品項(xiàng)3的存儲(chǔ)區(qū)域并尋找目標(biāo)貨位，然后進(jìn)行組合優(yōu)化，分別利用基本GA 和本文算法進(jìn)行求解，優(yōu)化前后性能及兩種算法優(yōu)化結(jié)果比較見(jiàn)表3。

3.2 多品項(xiàng)單一揀選與多品項(xiàng)復(fù)合揀選作業(yè)實(shí)驗(yàn)

多品項(xiàng)單一揀選與多品項(xiàng)復(fù)合揀選作業(yè)實(shí)驗(yàn)，作業(yè)任務(wù)分別為：10 種品項(xiàng)分別對(duì)應(yīng)的一次出庫(kù)作業(yè)、品項(xiàng)1、4、5、8分別對(duì)應(yīng)的一次入庫(kù)作業(yè)和品項(xiàng)2、3、6、7、9、10分別對(duì)應(yīng)的一次出庫(kù)作業(yè)。對(duì)于多品項(xiàng)揀選問(wèn)題的優(yōu)化，普通GA 不再適用。基于本文算法對(duì)多品項(xiàng)揀選作業(yè)問(wèn)題進(jìn)行優(yōu)化求解，優(yōu)化前后性能比較見(jiàn)表3，優(yōu)化結(jié)果顯示見(jiàn)表4。其中G 為優(yōu)化結(jié)果輸出單元數(shù)組，用于直觀顯示優(yōu)化后作業(yè)順序及目標(biāo)儲(chǔ)位，G1、G2分別對(duì)應(yīng)于兩排貨架中品項(xiàng)及任務(wù)布局，其中，“0”代表該儲(chǔ)位無(wú)作業(yè)任務(wù)，正整數(shù)表示入庫(kù)品項(xiàng)，負(fù)整數(shù)表示出庫(kù)品項(xiàng)，帶圈的整數(shù)表示作業(yè)執(zhí)行順序。

表3 揀選作業(yè)優(yōu)化前后性能及優(yōu)化方法比較

以上實(shí)驗(yàn)結(jié)果表明，構(gòu)建的復(fù)雜揀選作業(yè)優(yōu)化模型更貼近于實(shí)際倉(cāng)儲(chǔ)作業(yè)情況，單雙親混合GA 算法優(yōu)化效果顯著。此外，所研究算法已經(jīng)在企業(yè)倉(cāng)儲(chǔ)管理與監(jiān)控軟件中得到了應(yīng)用，且取得了良好的應(yīng)用效果。

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

本文在多品項(xiàng)約束條件下，建立了復(fù)雜揀選作業(yè)數(shù)學(xué)模型，在獲得多品項(xiàng)不同出入庫(kù)約束域的基礎(chǔ)上，兼顧作業(yè)順序及儲(chǔ)位優(yōu)化，提出了一種單雙親混合GA 倉(cāng)儲(chǔ)作業(yè)優(yōu)化算法，并用實(shí)驗(yàn)驗(yàn)證了該算法的有效性。本文僅對(duì)配送中心單個(gè)儲(chǔ)物單元的復(fù)雜揀貨作業(yè)優(yōu)化問(wèn)題進(jìn)行了研究，對(duì)于多巷道聯(lián)合作業(yè)間的作業(yè)量平衡問(wèn)題，在此基礎(chǔ)上，遵循 “出庫(kù)頻率高和關(guān)聯(lián)度高的品項(xiàng)儲(chǔ)存在不同揀貨巷道”的原則，對(duì)多個(gè)倉(cāng)儲(chǔ)單元的作業(yè)優(yōu)化進(jìn)一步研究。

［1］LI Shizhen.Study on optimal design and control of order pic－king in distribution center［D］.Chengdu：Southwest Jiaotong University，2008 （in Chinese）.［李詩(shī)珍.配送中心揀貨作業(yè)優(yōu)化設(shè)計(jì)與控制研究 ［D］.成都：西南交通大學(xué)，2008.］

［2］LIU Wanjun，HUANG Yangbo，DING Peng.Optimized research on order picking based on partheno－genetic algorithm［J］.Journal of Computer Applications，2010，30 （11）：2891－2893 （in Chinese）.［劉萬(wàn)軍，黃楊波，丁鵬.基于單親遺傳算法的揀選作業(yè)優(yōu)化研究 ［J］.計(jì)算機(jī)應(yīng)用，2010，30（11）：2891－2893.］

［3］JIN Meng，MU Xihui，DU Fengpo，et al.Dynamic programming and immune genetic algorithm－based multi－cross aisles order picking path planning studies［J］.Computer Measurement＆Control，2013，21 （11）：3120－3123 （in Chinese）.［靳萌，穆希輝，杜峰坡，等.基于動(dòng)態(tài)規(guī)劃與免疫遺傳算法的多穿越巷道揀貨路徑規(guī)劃研究 ［J］.計(jì)算機(jī)測(cè)量與控制，2013，21（11）：3120－3123.］

表4 實(shí)驗(yàn)結(jié)果

［4］PANG Long，LU Jingui.Order picking optimization of automated warehouses based on the ant colony genetic algorithm［J］.Computer Engineering ＆Science，2012，34 （3）：148－151 （in Chinese）.［龐龍，陸金桂.基于蟻群遺傳算法的自動(dòng)化立體倉(cāng)庫(kù)揀選路徑優(yōu)化 ［J］.計(jì)算機(jī)工程與科學(xué)，2012，34（3）：148－151.］

［5］LIU Chenqi，LI Meijuan，CHEN Xuebo.Order picking prob－lem based on ant colony algorithm ［J］.Systems Engineering－Theory ＆ Practice，2009，29 （3）：179－185 （in Chinese）.［劉臣奇，李梅娟，陳雪波.基于蟻群算法的揀選作業(yè)優(yōu)化問(wèn)題 ［J］.系統(tǒng)工程理論與實(shí)踐，2009，29 （3）：179－185.］

［6］LIU Zhixiong，WANG Yafen，ZHANG Yu.Multiple population fruit fly optimization algorithm for automatic warehouse order picking operation scheduling problem ［J］.Journal of Wuhan University of Technology，2014，36 （3）：71－77 （in Chinese）.［劉志雄，王雅芬，張煜.多種群果蠅優(yōu)化算法求解自動(dòng)化倉(cāng)庫(kù)揀選作業(yè)調(diào)度問(wèn)題 ［J］.武漢理工大學(xué)學(xué)報(bào)，2014，36 （3）：71－77.］

［7］Christophe Theys，Olli Braysy，Wout Dullaert，et al.Using a TSP heuristic for routing order in warehouse ［J］.European Journal of Operational Research，2010，200 （3）：755－763.

［8］FANG Yanjun，XIE Yijing.Optimization for order picking of metrological verification warehouse based on MMAS ［J］.Engineering Journal of Wuhan University，2013，46 （5）：645－658 （in Chinese）.［方彥軍，謝宜凈.基于MMAS算法的計(jì)量檢定中心倉(cāng)儲(chǔ)堆垛機(jī)揀選路徑優(yōu)化 ［J］.武漢大學(xué)學(xué)報(bào) （工學(xué)版），2013，46 （5）：645－658.］

［9］WANG Zhanlei.Research on order batching and picking path optimization problem in distribution center ［D］.Changchun：Jilin University，2013 （in Chinese）.［王占磊.配送中心訂單分批及揀貨路徑優(yōu)化問(wèn)題研究 ［D］.長(zhǎng)春：吉林大學(xué)，2013.］

［10］ZHOU Chao.Stduying on the three－dimensional warehouse storage spaces and picking routin ［D］.Ma’anshan：Anhui University of Technology，2013 （in Chinese）.［周超.企業(yè)立體倉(cāng)庫(kù)儲(chǔ)位及揀貨路徑優(yōu)化研究 ［D］.馬鞍山：安徽工業(yè)大學(xué)，2013.］

［11］ZHOU Jun，ZHAO Changyou，LIU Zhanqiang，et al.Operation optimization of storage and retrieval for stacks in AS／RS of raw tabacco material［J］.Computer Integrated Manufacturing Systems，2009，15 （4）：772－776（in Chinese）.［周軍，趙長(zhǎng)友，劉戰(zhàn)強(qiáng)，等.煙絲原料立體倉(cāng)庫(kù)堆垛機(jī)出入庫(kù)作業(yè)優(yōu)化研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15 （4）：772－776.］

［12］ZHANG Xiaochuan.Modern logistics technology and equipment［M］.Beijing：Chemical Industry Press，2013：37－38（in Chinese）.［張小川.現(xiàn)代倉(cāng)儲(chǔ)物流技術(shù)與裝備 ［M］.北京：化學(xué)工業(yè)出版社，2013：37－38.］