倉庫揀貨員多任務(wù)路徑優(yōu)化

楊東起,駱心怡,毛 鵬?

(1. 南京林業(yè)大學(xué)輕工與食品學(xué)院, 江蘇 南京 210037;2. 南京林業(yè)大學(xué)土木工程學(xué)院, 江蘇 南京 210037)

1 引言

隨著大數(shù)據(jù)、智慧供應(yīng)鏈的興起和科學(xué)技術(shù)的快速發(fā)展,眾多企業(yè)的商務(wù)模式與供應(yīng)鏈運(yùn)營相互作用,產(chǎn)生了新業(yè)態(tài)[1]。為了提升企業(yè)核心競爭力,以期能更好地調(diào)控供應(yīng)鏈運(yùn)營中的費(fèi)用,倉庫的成本管理十分非常重要[2]。越來越多的企業(yè)為了使倉庫施行更有效的庫存信息化管理和提高貨物的搬運(yùn)效率,紛紛建立智能倉庫進(jìn)行倉儲管理[3]。倉庫的取貨最優(yōu)路徑是使倉庫管理高效運(yùn)行的核心[4],因此,為了使倉庫的管理更加智能化,提高揀貨員的工作效率,眾多學(xué)者進(jìn)行了倉庫取貨的路徑規(guī)劃研究。

路徑規(guī)劃的算法主要有傳統(tǒng)算法、智能優(yōu)化算法[5]?，F(xiàn)大多數(shù)學(xué)者在原先的算法上進(jìn)行改進(jìn),引入模型得出路徑調(diào)度的進(jìn)一步優(yōu)化。如Xing等人[6]對禁忌搜索(NTS)算法進(jìn)行改進(jìn),在鄰域搜索過程中設(shè)計了重定位和交換操作,優(yōu)化了取貨點(diǎn)的順序,從而提高了揀貨的工作效率。傳統(tǒng)的A星算法存在計算量大的缺點(diǎn)[7],為此,Zhang等人[8]先基于A星算法得到初始路徑,采用關(guān)鍵點(diǎn)選擇策略進(jìn)行二次規(guī)劃,以去除路徑中冗余的拐點(diǎn)和節(jié)點(diǎn),提供更有效的倉庫路徑規(guī)劃。上述的兩種算法均屬于傳統(tǒng)的路徑規(guī)劃算法,智能優(yōu)化算法中,由于遺傳算法具有較好的魯棒性和并行性,能夠獲得滿足特定要求的最優(yōu)解,被廣泛應(yīng)用于倉庫的路徑規(guī)劃中[9],改進(jìn)遺傳算法以解決倉庫的路徑規(guī)劃問題受到了大量學(xué)者的關(guān)注。如Zhu等人[10]提出了一種平均分布遺傳算法,預(yù)先調(diào)整隨機(jī)輸入的染色體,以生成更合理的染色體,使迭代過程可以更高效地進(jìn)行,同時避免早熟收斂,有效地處理了揀貨調(diào)度問題。Paraskevi等人[11]將遺傳算法與倉庫揀貨的距離和容量的模糊模型相結(jié)合,給出了不同情況下的路徑調(diào)度最優(yōu)解。Liu等人[12]將兩種自適應(yīng)遺傳算法和一種多自適應(yīng)遺傳算法相結(jié)合,優(yōu)化揀貨的任務(wù)調(diào)度,具有較強(qiáng)的全局搜索能力和較快的優(yōu)化速度。

然而上述文獻(xiàn)均只考慮了揀貨員執(zhí)行一個任務(wù)時的路徑優(yōu)化,在實(shí)際生活中,由于揀貨員數(shù)量有限,他們常常需要連續(xù)執(zhí)行多個任務(wù)。此外,上述文獻(xiàn)中提及的倉庫規(guī)模較小,當(dāng)倉庫規(guī)模較大時,現(xiàn)有的方法難以滿足需求。

針對上述問題,本文將揀貨員的多任務(wù)拆分為若干個單任務(wù),依次利用改進(jìn)的遺傳算法求解其最短路徑。為了解決因大量計算兩點(diǎn)間的距離而導(dǎo)致求解過程耗時的問題,本文創(chuàng)新性的總結(jié)了揀貨員從當(dāng)前位置運(yùn)動到下一位置的路程計算公式,并引入了距離查找表。

2 問題描述

本文的倉庫模型由貨架和復(fù)核臺組成,其規(guī)模較大。貨架共4排,每排25組,每組2列,每列貨架包含15個貨格。貨格共3000個。復(fù)核臺共13個,位于貨架外圍,成直角分布于倉庫左下角,縱5橫8。任意兩組水平方向相鄰的貨架之間的距離為1500mm,任意兩組豎直方向相鄰的貨架之間的距離為2000mm。貨格長寬均為800mm,復(fù)核臺長寬均為1000mm。除貨架和復(fù)核臺,倉庫其它地方皆可通行。圖1為倉庫的局部(倉庫的左下角),包含1排7組,其每組2列,每列貨架包含15個貨格。

圖1 倉庫局部示意圖

在揀貨過程中,揀貨員執(zhí)行單任務(wù)的路徑是由起始復(fù)核臺、若干貨格和終止復(fù)核臺構(gòu)成,可表示為

T={Sstart,L1,…,Li,…,Ln,Send}

(1)

其中,Sstart表示起始復(fù)核臺,Send表示終止復(fù)核臺,Li表示第i個貨格。

實(shí)際生活中,一個揀貨員會接到多個任務(wù),揀貨員每完成一個任務(wù)時,必須到復(fù)核臺核對。此時,揀貨員接到的多任務(wù)表示為

P={T1,…,Tj,Tj+1,…,Tm}

(2)

其中,Tj為揀貨員的第j個單任務(wù)。Tj+1的起始復(fù)核臺為Tj的終止復(fù)核臺。

3 貨格/復(fù)核臺間距離計算

揀貨員從當(dāng)前位置(xi,yi)運(yùn)動到下一位置(xi+1,yi+1)時,如果其中的某段路程同時滿足:(1)連續(xù)兩次轉(zhuǎn)向,且方向相同(同為順時針或者逆時針轉(zhuǎn)向);(2)包含當(dāng)前位置(xi,yi)或者下一位置(xi+1,yi+1),那么稱它為“N”型路程,如圖2中的路線ABCD。揀貨員運(yùn)動時通過偏移量才能繞過貨架或復(fù)核臺。圖2中,線段AB、CD、EF和GH為橫向偏移量,CI和FJ為縱向偏移量。所有的偏移量均記為bias=750mm。

圖2 兩貨格間的路徑示意圖

當(dāng)計算揀貨員從當(dāng)前位置(xi,yi)運(yùn)動到下一位置(xi+1,yi+1)的路程時,如果揀貨員無需繞過貨架,如圖3所示,那么當(dāng)前位置和下一位置滿足以下條件之一:

圖3 揀貨員從當(dāng)前位置運(yùn)動到下一位置的路徑示意圖

1)當(dāng)前位置和下一位置分布在同一過道的一側(cè)或兩側(cè)

2)當(dāng)前位置和下一位置不在同一排貨架。

此時,揀貨員的路程可表示為:

D(i,i+1)=|xi-xi+1|+|yi-yi+1|+2n×bias

(3)

其中,n為“N”型路程的個數(shù)。

當(dāng)計算揀貨員從當(dāng)前位置(xi,yi)運(yùn)動到下一位置(xi+1,yi+1)的路程時,如果揀貨員需要繞過貨架,如圖4所示,那么當(dāng)前位置和下一位置同時滿足以下條件:①當(dāng)前位置和下一位置在同一排;②當(dāng)前位置和下一位置不在同一豎直過道的一側(cè)或兩側(cè)。

圖4 揀貨員從當(dāng)前位置運(yùn)動到下一位置的路徑示意圖

由于揀貨員在繞過貨架時,可從貨架上方繞過,也可從貨架下方繞過,所以選擇它們中最短的路程。此時,揀貨員的路程可表示為:

D(i,i+1)=|xi-xi+1|+min{ytop,ybottom}+(2n+2)×bias

(4)

其中,n為“N”型路線的個數(shù);ytop和ybottom分別為從貨架上方繞過和從貨架下方繞過的總縱向距離,且滿足以下關(guān)系:

(5)

其中,ymax和ymin分別表示貨格所在貨架的最大和最小縱坐標(biāo)。

4 揀貨員路徑優(yōu)化

4.1 改進(jìn)的遺傳算法

由于本文的倉庫規(guī)模較大,直接從全部貨格和復(fù)核臺中查找揀貨員當(dāng)前位置和下一位置并計算二者之間的距離,這將導(dǎo)致求解過程中消耗大量時間。為此,本文在計算適應(yīng)度時,引入了距離查找表來縮短程序運(yùn)行時間。具體的過程如下:

1)編碼

對于單任務(wù)而言,隨機(jī)起始復(fù)核臺和終止復(fù)核臺,分別置于染色體的首部和尾部,任務(wù)涉及到的貨格隨機(jī)置于染色體的中間,以此作為該任務(wù)的潛在路徑,如圖5所示。對于多任務(wù)而言,將多個任務(wù)的染色體依次拼接作為一個染色體即可,如圖6所示。

復(fù)核臺貨格1…貨格n復(fù)核臺

圖6 多任務(wù)的編碼

2)查找表

本文提及的倉庫模型共包含3000個貨格和13個復(fù)核臺,倉庫規(guī)模較大。計算揀貨員從當(dāng)前位置到下一位置的路程時,如果采用先從整個倉庫模型中查取當(dāng)前位置和下一位置的坐標(biāo),再計算二者之間的距離這一策略,那么這將消耗大量的時間。為了避免上述問題,本文先將揀貨員任務(wù)中所涉及的貨格和復(fù)核臺選出,然后計算任意貨格與貨格、貨格與復(fù)核臺之間的距離,最后以此建立相應(yīng)的距離查找表。

3)適應(yīng)度

對染色體的優(yōu)劣進(jìn)行評價時,本文采用的衡量標(biāo)準(zhǔn)如下

(6)

其中,n為染色體的長度,即該路徑中復(fù)核臺和貨架的總數(shù);D(i,i+1) 為第i個復(fù)核臺或者貨格和第i+1個復(fù)核臺或者貨格間的距離,該距離從距離查找表中獲得。

4)選擇

利用選擇操作中傳統(tǒng)的輪盤賭,選擇出適應(yīng)度小的染色體作為子代。

5)交叉

交叉分為兩種情況:(1)針對一個染色體,對一個任務(wù)內(nèi)的隨機(jī)的兩個貨格進(jìn)行換位;(2)針對不同染色體,對應(yīng)位置的復(fù)核臺進(jìn)行交叉。本文通過交叉閾值來決定染色體交叉時,會發(fā)生上述情況中的哪一種。

6)變異

通過變異閾值,決定染色體是否發(fā)生變異。如果染色體發(fā)生變異,那么用重新初始化的染色體替代該染色體。

4.2 倉庫揀貨員多任務(wù)路徑優(yōu)化策略

假設(shè)一個揀貨員執(zhí)行一次任務(wù)需要訪問2個復(fù)核臺和n個貨格。以上述遺傳算法為基礎(chǔ),本文提出以下三種策略來求解一個揀貨員的m個任務(wù)的最短路徑:

方法1:采用m次單目標(biāo)規(guī)劃。采用上述遺傳算法的單任務(wù)編碼,染色體長度為n+2,含有1個適應(yīng)度,共執(zhí)行m次;

方法2:采用單目標(biāo)規(guī)劃。采用上述遺傳算法的多任務(wù)編碼,染色體長度為m(n+1)+1,含有1個適應(yīng)度,共執(zhí)行1次;

方法3:采用多目標(biāo)規(guī)劃。采用NSGA-Ⅱ算法,編碼方式為多任務(wù)編碼,染色體長度為m(n+1)+1,含有m個適應(yīng)度,共執(zhí)行1次。

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

本文選取了3個揀貨員作為實(shí)驗(yàn)對象,并設(shè)定每個揀貨員共執(zhí)行3個任務(wù),每個任務(wù)包含2個復(fù)核臺和20個貨格。為了簡化實(shí)驗(yàn),假設(shè)只有復(fù)核臺FH03和FH11正常工作。實(shí)驗(yàn)所需原數(shù)據(jù)如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

表2為利用遺傳算法求解揀貨員單任務(wù)時是否采用距離查找表迭500次的耗時結(jié)果。從該表可以看出,采用距離查找表后,可將求解耗時縮小100多倍。

表2 是否采用距離查找表的耗時比較

對于上述求解倉庫揀貨員多任務(wù)路徑的三種策略所涉及到的參數(shù)均相同:運(yùn)行一次算法的最大迭代次數(shù)為1500次,變異閾值為0.1,交叉閾值為0.5。此外,三種策略在計算適應(yīng)度時,均采用了距離查找表,且它們的選擇、交叉、變異方式相同。三種策略求得的最短距離和耗時如表3所示。

表3 不同策略下的實(shí)驗(yàn)結(jié)果比較

從表3可以看出,對于3個揀貨員而言,方法1雖然耗時較長,但是它更利于發(fā)現(xiàn)揀貨員多任務(wù)時的最短路徑。為了探究其原因,本文將3個揀貨員在不同策略下的求解過程可視化,如圖7所示。以揀貨員P001為例,方法1收斂速度較快;方法2由于染色體的長度太長,所以收斂的速度較慢;方法3很難同時找到三個任務(wù)的最短路徑,對于任務(wù)T0001迭代了1500次后,仍未收斂,這導(dǎo)致了該方法所得到的結(jié)果最差。其他揀貨員亦是如此。方法1所求的最短路徑如表4所示。

表4 基于方法1的揀貨員的最短路徑

圖7 基于三種方法的3位接貨員最短路徑求解過程

6 結(jié)束語

本文總結(jié)了揀貨員揀貨時從當(dāng)前位置運(yùn)動到下一位置時的路程計算的基本規(guī)律。對于較大的倉庫,為了避免因查找位置坐標(biāo)而導(dǎo)致計算兩點(diǎn)間的距離消耗大量時間,本文先將所涉及的位置坐標(biāo)選出,計算任意兩位置間的距離,然后建立了距離查找表。提出了利用遺傳算法,采用多次單目標(biāo)規(guī)劃、單目標(biāo)規(guī)劃、多目標(biāo)規(guī)劃三種計算揀貨員在多任務(wù)情況下最短路徑的策略。最后,通過實(shí)驗(yàn)驗(yàn)證了多次單目標(biāo)規(guī)劃效果最優(yōu)。本文所提的方案能有效解決實(shí)際中規(guī)模較大的倉庫的路徑優(yōu)化問題。