基于NSGA-II快遞智能倉(cāng)庫(kù)多目標(biāo)優(yōu)化問題研究

，

(廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006)

0 引言

隨著電子商務(wù)的興起，智能倉(cāng)儲(chǔ)已經(jīng)發(fā)展成為一個(gè)極具市場(chǎng)價(jià)值和發(fā)展前景的行業(yè)，智能倉(cāng)庫(kù)調(diào)度方案的好壞直接關(guān)系到整個(gè)倉(cāng)儲(chǔ)系統(tǒng)出入庫(kù)和整個(gè)物流過程的效率。對(duì)于現(xiàn)在的大型智能倉(cāng)庫(kù)，一個(gè)訂單往往對(duì)應(yīng)多個(gè)物品，同時(shí)下單的多個(gè)物品往往通過同一快遞物流分發(fā)到客戶手中。本文就這一現(xiàn)象進(jìn)行生產(chǎn)調(diào)度研究。

本文要研究的內(nèi)容可以歸結(jié)于混合流水車間調(diào)度問題。混合流水車間是一種復(fù)雜的組合問題。國(guó)內(nèi)外的主要研究有兩級(jí)作業(yè)混合流水車間。在這類問題中Ruiz[1]，Gupta[2]和Li[3]研究了兩級(jí)作業(yè)混合流水車間，最大完工時(shí)間最優(yōu)化的問題。Lin[4]研究了兩級(jí)混合流水車間，且各個(gè)階段引入了時(shí)間驅(qū)動(dòng)的概念，對(duì)目標(biāo)函數(shù)重新設(shè)置，最大限度地在原有的順序上進(jìn)行優(yōu)化。Haouari[5]使用新的優(yōu)化算法區(qū)去解決混合流水車間的問題，同時(shí)他給出了較為詳細(xì)的解決步驟和方案。Allaoui[6]從機(jī)器故障等中斷點(diǎn)的角度去優(yōu)化混合流水車間，研究中引入了中斷的解決方案。Logendran[9]引入群混合流水車間，優(yōu)化最大完工時(shí)間。Botta-Genoulaz[10]研究了混合流水車間的步驟限制和時(shí)間滯后。Voss[11]介紹了從批處理的角度去解決混合流水車間問題，引入了重中的處理的目標(biāo)機(jī)制。國(guó)內(nèi)外的研究中，引入了眾多新的解決方法。其中Engin[7]采用了人工免疫算法。Uiusoy[8]用基因算法來優(yōu)化多級(jí)混合流水車間的多重處理任務(wù)調(diào)度問題。Zitzler[12]使用進(jìn)化的Pareto對(duì)目標(biāo)進(jìn)行優(yōu)化。Deb[13]使用NSGA的改進(jìn)方法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化。

在這些研究中很少提到帶有集中打包的混合流水車間，本文從準(zhǔn)時(shí)度和同時(shí)度兩個(gè)層面，考慮到集中打包策略的混合流水車間多目標(biāo)調(diào)度，并且通過對(duì)智能算法進(jìn)行優(yōu)化最后實(shí)現(xiàn)優(yōu)化調(diào)度方案。

1 調(diào)度模型的建立

1.1 研究問題描述

本文研究的是一個(gè)考慮到集中打包的生產(chǎn)調(diào)度問題，在大型網(wǎng)站購(gòu)物中客戶的一個(gè)訂單可能對(duì)應(yīng)多個(gè)物品，每個(gè)物品都需要經(jīng)過幾道工序才能打包。每個(gè)物品到達(dá)打包區(qū)域的時(shí)間都不一樣，例如：一個(gè)訂單有3個(gè)物品，其中2個(gè)物品已經(jīng)完成出庫(kù)階段，這2個(gè)物品就需要在緩沖區(qū)等待最后的一個(gè)物品才能進(jìn)入打包環(huán)節(jié)，如果調(diào)度不合理，那么就有大量的物品在緩沖區(qū)等待打包，緩沖區(qū)庫(kù)存過大將不利于倉(cāng)庫(kù)的管理。結(jié)合這一問題，本文提出了同時(shí)度和準(zhǔn)時(shí)度兩個(gè)目標(biāo)優(yōu)化指標(biāo)。

如圖1所示，是智能倉(cāng)庫(kù)一個(gè)訂單對(duì)應(yīng)多個(gè)快遞物品從出庫(kù)到打包的流程圖。在本文中我們把智能倉(cāng)庫(kù)的工作生命周期分為兩個(gè)過程：1)出庫(kù)過程，這一過程就是物品的揀貨、增加填充、運(yùn)輸?shù)入A段的集合；2)打包過程，這一過程就是物品封裝打包的過程，打包結(jié)束后就完成一個(gè)訂單的在智能倉(cāng)庫(kù)中的生命周期，從而進(jìn)入下一個(gè)物流環(huán)節(jié)。

圖1 智能倉(cāng)庫(kù)從出庫(kù)到打包過程圖

1.2 量化模型建立

通過對(duì)問題的研究，將現(xiàn)實(shí)的問題量化，將現(xiàn)實(shí)問題轉(zhuǎn)換為數(shù)學(xué)問題，將整個(gè)過程量化為出庫(kù)和打包兩個(gè)過程。

1.2.1 同時(shí)度的定義和設(shè)定

對(duì)于智能倉(cāng)庫(kù)來說，一般情況下智能倉(cāng)庫(kù)的出庫(kù)量巨大，對(duì)于一個(gè)訂單中包含多個(gè)物品的情況，往往多個(gè)物品不是同時(shí)到達(dá)打包區(qū)。這里就存在一個(gè)問題，如果，多個(gè)物品等待一個(gè)物品才能打包，那么這多個(gè)物品將在Buffer區(qū)中等待，直至所有的物品都到達(dá)。如果這種情況過多，buffer區(qū)的庫(kù)存物品就會(huì)很多，不利于整個(gè)智能倉(cāng)庫(kù)的管理，也不利于存放。所以基于這個(gè)考慮，我們的第一個(gè)目標(biāo)函數(shù)就是同一個(gè)訂單的多個(gè)物品到達(dá)打包區(qū)的同時(shí)度。目標(biāo)函數(shù)式(1)是盡量讓同一個(gè)訂單內(nèi)的多個(gè)物品能同時(shí)到達(dá)打包區(qū)域，從而盡量的減少buffer區(qū)域的庫(kù)存物品。

f1(x)=minCT

=1，…，P；

(1)

1.2.2 準(zhǔn)時(shí)度的定義和設(shè)定

對(duì)于每一個(gè)訂單而言，都會(huì)有一個(gè)規(guī)定的發(fā)貨日期，智能倉(cāng)庫(kù)必須保證，在預(yù)定的發(fā)貨期到來前所有的來自于同一個(gè)訂單的物品能夠到達(dá)打包區(qū)域。目標(biāo)函數(shù)式(2)就是要讓所有的物品都盡量的在預(yù)定的發(fā)貨前能夠到達(dá)指定的打包區(qū)域，而不存在推遲發(fā)貨等情況。

=1，…，P；

(2)

上面的(1)和(2)式就構(gòu)成了本模型的目標(biāo)函數(shù)，(1)表達(dá)的是同一個(gè)訂單的多個(gè)物品同時(shí)到達(dá)打包區(qū)域的時(shí)間間隔最小，(2)則表示的是每個(gè)訂單的打包完成后的發(fā)貨時(shí)間與預(yù)計(jì)的發(fā)貨時(shí)間間隔最小。

2 基于優(yōu)化的NSGA-II模型的建立

NSGA-Ⅱ算法是 Srinivas和Deb 于 2000 年在 NSGA 的基礎(chǔ)上提出的，它比 NSGA算法更加優(yōu)越：它采用了快速非支配排序算法，計(jì)算復(fù)雜度比 NSGA低很多；采用了擁擠度和擁擠度比較算子，代替了需要指定的共享半徑 shareQ，并在快速排序后的同級(jí)比較中作為勝出標(biāo)準(zhǔn)，使準(zhǔn) Pareto 域中的個(gè)體能擴(kuò)展到整個(gè) Pareto 域，并均勻分布，保持了種群的多樣性；引入了精英策略，擴(kuò)大了采樣空間，防止最佳個(gè)體的丟失，提高了算法的運(yùn)算速度和魯棒性。

本文采用改進(jìn)的NSGA-Ⅱ算法。改進(jìn)的NSGA-II具體采用的流程如圖2 所示，本文較之前的NSGA-II算法，對(duì)父代生成新個(gè)體，增加精英選擇機(jī)制，在以往的流程中往往存在一些交叉的信息，在改進(jìn)的流程中將增加優(yōu)化策略，將重復(fù)的迭代個(gè)體進(jìn)行精英刷選。經(jīng)過優(yōu)化的NSGA-II模型的種群類型更加合理，不存在大量重復(fù)的冗余個(gè)體。

圖2 改進(jìn)的NSGA-II流程圖

算法改進(jìn)的具體過程為：種群個(gè)數(shù)為N，帶精英策略的NSGA-Ⅱ算法將父代與子代個(gè)體合并，合并后的種群個(gè)數(shù)大于N，比較個(gè)體中的目標(biāo)函數(shù)值，相同個(gè)體只保留一個(gè)，由于是帶精英策略，保證了改進(jìn)之后得到的新種群中的個(gè)體數(shù)大于等于N，再?gòu)睦锩姘匆?guī)則選取優(yōu)良的N個(gè)個(gè)體成為下一代父種群。

圖3 改進(jìn)前后的NSGA-Ⅱ算法結(jié)果比較

對(duì)改進(jìn)后的帶精英策略的NSGA-Ⅱ進(jìn)行上述實(shí)驗(yàn)，算法得到的Pareto解圖如圖3。

如圖3，圖中的“+”點(diǎn)是改進(jìn)后算法得到的終止迭代種群中的Pareto解，“⊕”點(diǎn)是帶精英策略NSGA-Ⅱ算法得到的解。

從圖3可以看出：優(yōu)化后的點(diǎn)組成的解集數(shù)多于優(yōu)化前的解集數(shù)，且對(duì)于目標(biāo)函數(shù)的結(jié)果優(yōu)于之前，所以本優(yōu)化的NSGA-II作用較好。

3 仿真實(shí)驗(yàn)及穩(wěn)定性分析

3.1 仿真實(shí)驗(yàn)

基于上面幾節(jié)研究的方法，在MATLAB上進(jìn)行編碼實(shí)驗(yàn)。如表1，通過MATLAB生成相應(yīng)的數(shù)據(jù)，用于實(shí)驗(yàn)。

表1 參數(shù)生成

在生成實(shí)驗(yàn)數(shù)據(jù)后，我們的實(shí)驗(yàn)將對(duì)NSGA-II算法的重要指標(biāo)進(jìn)行設(shè)置。在算法中主要涉及到的參數(shù)有：種群大小POP，交叉概率Pc，變異概率Pm，進(jìn)化代數(shù)Gen。這四個(gè)因子的取值如表2，仿真結(jié)果、甘特圖集Pareto解集的生成如圖4、圖5。

表2 NSGA-II參數(shù)設(shè)定

圖4 調(diào)度甘特圖

圖4是基于模擬的數(shù)據(jù)，通過NSGA-II求解的一種最優(yōu)的調(diào)度方案。圖5為多目標(biāo)優(yōu)化問題中的兩個(gè)目標(biāo)的Pareto解集。

圖5 多目標(biāo)優(yōu)化的Pareto解集

多目標(biāo)優(yōu)化，通過算法得到了一組較優(yōu)的Pareto解，還需要確定這些優(yōu)化目標(biāo)的權(quán)重，通過公式f(x)=w1*f1(x)+(1-w1)f2(x)在所得Pareto解中選擇最優(yōu)方案，式中：w1表示目標(biāo)函數(shù)f1(x)的權(quán)重值。測(cè)試分析中取w1=0.5所得的f(x)對(duì)算法進(jìn)行測(cè)試分析。收斂時(shí)間72.010212 s，目標(biāo)函數(shù)1等于94，目標(biāo)函數(shù)2等于228，綜合目標(biāo)函數(shù)f(x)等于161。

3.2 穩(wěn)定性分析

接下來我們對(duì)模型的穩(wěn)定性進(jìn)行分析，對(duì)以上隨機(jī)生產(chǎn)的數(shù)據(jù)進(jìn)行一百次重復(fù)的實(shí)驗(yàn)，我們從最終的收斂時(shí)間和收斂的綜合目標(biāo)函數(shù)兩個(gè)指標(biāo)評(píng)價(jià)模型的穩(wěn)定性。通過對(duì)模型進(jìn)行重復(fù)實(shí)驗(yàn)，對(duì)收斂時(shí)間t和f(x)進(jìn)行分布分析。

圖6 t與f的分布和正態(tài)擬合曲線

從收斂速度t、收斂的綜合函數(shù)f的直方圖和正態(tài)分布擬合數(shù)據(jù)來看，模型的整體問題性較好，能較好地收斂到一個(gè)最優(yōu)解的范圍中，且最優(yōu)范圍的范圍較小，整個(gè)模型的穩(wěn)定性較好。

4 結(jié)論

通過對(duì)快遞智能倉(cāng)庫(kù)的出庫(kù)打包過程進(jìn)行研究，并對(duì)存在的問題構(gòu)造多目標(biāo)優(yōu)化方案。本文通過對(duì)遺傳算法中的NSGA-II進(jìn)行改進(jìn)，并對(duì)提出的數(shù)學(xué)模型進(jìn)行仿真實(shí)驗(yàn)，從而得到最優(yōu)的調(diào)度方案。并且最后通過大規(guī)模重復(fù)實(shí)驗(yàn)驗(yàn)證模型的穩(wěn)定性，模型總體收斂情況較好，能正確地收斂在最優(yōu)解區(qū)域，模型整體效果較好。