胡小建，周 瓊+，宋旭東，闞 濤

(1.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009；2.過(guò)程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009；3.安徽維德工業(yè)自動(dòng)化有限公司，安徽 合肥 230000)

0 引言

倉(cāng)儲(chǔ)作業(yè)中最復(fù)雜、最繁瑣的環(huán)節(jié)是揀選作業(yè)，揀貨時(shí)間約占整個(gè)倉(cāng)儲(chǔ)中心物流作業(yè)過(guò)程的40%左右[1]，但隨著電子商務(wù)的快速發(fā)展，倉(cāng)庫(kù)規(guī)模逐步擴(kuò)大，客戶的個(gè)性化需求導(dǎo)致用戶訂單趨于小批量、多樣性與碎片化，使得倉(cāng)儲(chǔ)貨物的揀選變得更為復(fù)雜、勞動(dòng)強(qiáng)度大、揀貨成本高。隨著新一代信息技術(shù)的發(fā)展，智能化的自動(dòng)化立體倉(cāng)庫(kù)(Automatic Storage/Retrieval System，AS/RS)和自動(dòng)導(dǎo)引車(Automated Guided Vehicle,AGV)等自動(dòng)化設(shè)備在倉(cāng)庫(kù)中有了一定的應(yīng)用，但通過(guò)對(duì)安徽BY以及眾多企業(yè)的深入調(diào)研發(fā)現(xiàn)，從AS/RS的成本和實(shí)際應(yīng)用情況來(lái)看，由于投資成本太高、實(shí)際運(yùn)作中系統(tǒng)不穩(wěn)定及缺乏自主性規(guī)避障礙等問(wèn)題，目前有75%的企業(yè)依然是平面?zhèn)}庫(kù)。

本文以工信部“高端液壓元件制造數(shù)字化車間”項(xiàng)目為依托，該項(xiàng)目為完善整個(gè)生產(chǎn)車間智能化，不僅對(duì)數(shù)字化生產(chǎn)車間進(jìn)行規(guī)劃研究，還針對(duì)安徽BY數(shù)字化車間外的生產(chǎn)物流過(guò)程進(jìn)行優(yōu)化研究，實(shí)現(xiàn)整個(gè)生產(chǎn)車間的智能制造和互聯(lián)互通。通過(guò)調(diào)研，安徽BY其余庫(kù)區(qū)仍采用的是傳統(tǒng)的人揀貨的揀選模式，由揀貨員手持揀貨單并依據(jù)自身經(jīng)驗(yàn)，在貨架中來(lái)回穿梭，按照揀貨單要求進(jìn)行揀貨，費(fèi)時(shí)費(fèi)力，效率低下。同時(shí)，實(shí)際倉(cāng)庫(kù)中一種貨物可能由多個(gè)貨位存放，揀選作業(yè)時(shí)通常會(huì)有多個(gè)揀選人員進(jìn)行揀貨，在揀選中往往會(huì)產(chǎn)生路徑規(guī)劃不合理及路徑?jīng)_突等情況，導(dǎo)致揀選時(shí)間增加，揀選效率更低，揀選的復(fù)雜性更大。因此，如何合理規(guī)劃多人多儲(chǔ)位揀選路徑、預(yù)測(cè)和消除路徑?jīng)_突、規(guī)避障礙和提高揀選作業(yè)的效率至關(guān)重要，是亟需研究解決的重要問(wèn)題之一。

訂單的揀選一直是影響倉(cāng)儲(chǔ)作業(yè)效率的關(guān)鍵環(huán)節(jié)，因此訂單揀選過(guò)程是比較熱門的研究領(lǐng)域。近年來(lái)揀貨路徑優(yōu)化的研究越來(lái)越多，致力于合理規(guī)劃揀貨任務(wù)與建立揀貨路徑最短的揀選路線，縮短揀貨時(shí)間。揀選路徑問(wèn)題實(shí)質(zhì)上是一類典型的旅行商問(wèn)題(Travelling Saleman Problem,TSP),屬于NP難問(wèn)題[2],目前揀選路徑優(yōu)化研究主要集中在AS/RS和AGV中，可以看出，在自動(dòng)化環(huán)境下，對(duì)于揀選路徑的優(yōu)化十分重要[3]。文獻(xiàn)[4]針對(duì)多品種、少批量以及有揀貨容量限制的情況，采用粒子群算法與蟻群算法混合算法求解最佳的揀貨路徑；ZHOU 等[4]提出一種改進(jìn)的單親遺傳算法(Improved Partheno Genetic Algorithm，IPGA)，研究具有多個(gè)倉(cāng)庫(kù)封閉路徑的多旅行商問(wèn)題(Multi-Traveling Salesman Problem，MTSP)，并進(jìn)行了一系列的對(duì)比實(shí)驗(yàn)，對(duì)所提算法的性能進(jìn)行評(píng)估，證明了 IPGA 在解決 MTSP 時(shí)更優(yōu)；SHETTY等[5]通過(guò)距離矩陣提出一種基于車輛路線的方法，以獲得訂單揀選的最佳路徑，并通過(guò)仿真實(shí)現(xiàn)。

目前很多研究主要通過(guò)聚類、動(dòng)態(tài)規(guī)劃和遺傳算法、粒子群等智能算法對(duì)雙區(qū)型、魚(yú)骨型等不同的倉(cāng)庫(kù)類型中的路徑規(guī)劃問(wèn)題進(jìn)行優(yōu)化研究[6-9]。與此同時(shí)，目前大多數(shù)對(duì)揀選路徑的研究針對(duì)的是對(duì)單個(gè)揀貨人員或是揀貨設(shè)備以及針對(duì)貨物存放的是單個(gè)存儲(chǔ)貨位，而實(shí)際中，往往是多個(gè)揀貨員同時(shí)進(jìn)行揀選與貨物存儲(chǔ)在多個(gè)庫(kù)位上。文獻(xiàn)[10]研究了倉(cāng)庫(kù)揀貨中存在多個(gè)揀貨人員同時(shí)作業(yè)的問(wèn)題，利用多種群遺傳算法對(duì)揀貨路徑進(jìn)行規(guī)劃，同時(shí)通過(guò)時(shí)間窗的預(yù)測(cè)避障法，提出一種基于時(shí)間窗約束多種群遺傳揀選路徑優(yōu)化算法，在一種靜態(tài)狀態(tài)下進(jìn)行路徑的規(guī)劃與路徑?jīng)_突預(yù)測(cè)，該方法在靜態(tài)規(guī)劃時(shí)有效地進(jìn)行路徑優(yōu)化，但在動(dòng)態(tài)變化的環(huán)境下將會(huì)受到制約；文獻(xiàn)[11]則研究了在窄通道摘果式揀選倉(cāng)庫(kù)系統(tǒng)中存在兩個(gè)揀貨人員揀選時(shí)的擁塞問(wèn)題，以行走時(shí)間與等待時(shí)間最小為目標(biāo)函數(shù)，提出粒子群算法與蟻群算法解決揀選路徑擁堵問(wèn)題，為解決多揀貨員同時(shí)作業(yè)時(shí)產(chǎn)生的路徑擁堵提供了一種解決方法，但未進(jìn)行路徑優(yōu)化的深入研究，同時(shí)僅考慮一種貨物僅存放一個(gè)貨位上的情況；文獻(xiàn)[12-13]研究了在自動(dòng)化存儲(chǔ)系統(tǒng)中一種貨物有多個(gè)儲(chǔ)存庫(kù)位時(shí)的揀貨路徑問(wèn)題，并通過(guò)對(duì)比分析實(shí)驗(yàn)，證明了遺傳算法的效率更高，但研究對(duì)象是單個(gè)揀貨人員或揀選設(shè)備，因此在研究過(guò)程中就缺乏對(duì)實(shí)際存在的多揀貨員以及路徑?jīng)_突的綜合研究。針對(duì)現(xiàn)有研究中的不足和現(xiàn)實(shí)BY倉(cāng)儲(chǔ)建設(shè)需求，本文將根據(jù)實(shí)際揀選現(xiàn)狀，研究多儲(chǔ)位環(huán)境下的多人同時(shí)揀選，進(jìn)行揀選路徑優(yōu)化并考慮路徑?jīng)_突問(wèn)題，利用時(shí)間窗和兩階段策略實(shí)現(xiàn)揀選路徑的動(dòng)態(tài)局部規(guī)劃，提高企業(yè)倉(cāng)儲(chǔ)揀選效率。

綜上所述，目前雖然關(guān)于倉(cāng)庫(kù)揀選路徑的研究較多，但很少有研究綜合考慮多揀貨員同時(shí)作業(yè)和多貨位兩個(gè)方面，考慮較多的僅是其中一個(gè)方面，其中考慮多人同時(shí)揀選大多也是為解決擁堵問(wèn)題提供算法思想，對(duì)路徑的規(guī)劃研究還是較少。另外目前關(guān)于揀選路徑較多的是AGV的研究[14-15]，經(jīng)過(guò)實(shí)際調(diào)研大部分企業(yè)還沒(méi)有實(shí)現(xiàn)自動(dòng)化，不適于當(dāng)前人工揀選的現(xiàn)狀，因此本文將為解決當(dāng)前人工揀選效率低下問(wèn)題進(jìn)行研究。本文將同時(shí)考慮多人揀選及多儲(chǔ)位這兩個(gè)問(wèn)題，并考慮多人同時(shí)揀選路徑?jīng)_突的發(fā)生，提出解決策略，合理規(guī)劃揀選路徑并動(dòng)態(tài)調(diào)整，使研究更貼合實(shí)際，提高揀選作業(yè)的效率與揀選精確性。本研究將采用具有時(shí)間窗約束的遺傳算法和貪心算法相結(jié)合的基于時(shí)間窗約束的改進(jìn)遺傳算(Improved Gentic Algorithm Time Window Constraint, TWC-IGA)TWC-IGA算法對(duì)優(yōu)化模型進(jìn)行求解，首先通過(guò)IGA得到優(yōu)化路徑的集合，再通過(guò)時(shí)間窗約束與兩階段策略對(duì)路徑?jīng)_突進(jìn)行預(yù)測(cè)、消除以及規(guī)避障礙，動(dòng)態(tài)調(diào)整局部路徑，并進(jìn)行仿真對(duì)比實(shí)驗(yàn)，驗(yàn)證所提算法的穩(wěn)定性及收斂速度優(yōu)越性，為提高企業(yè)倉(cāng)庫(kù)內(nèi)部揀貨作業(yè)效率提供了有效的解決方法。

1 問(wèn)題描述

本文主要考慮解決基于多人同時(shí)進(jìn)行揀選作業(yè)，且揀選目標(biāo)存在多個(gè)存放位置時(shí)，進(jìn)行目標(biāo)貨位的選擇以及多人揀選的路徑規(guī)劃問(wèn)題。實(shí)際在進(jìn)行倉(cāng)庫(kù)作業(yè)揀選時(shí)，往往是多個(gè)揀貨員同時(shí)進(jìn)行揀選且揀選對(duì)象會(huì)存放在多個(gè)貨位上，這就需要提前確定符合條件與最優(yōu)的揀選貨位，避免產(chǎn)生無(wú)意義的路徑，另一方面，多人同時(shí)進(jìn)行揀選經(jīng)常會(huì)出現(xiàn)路徑?jīng)_突現(xiàn)象，造成揀選路徑擁堵，降低揀選效率。如圖1所示，圖中所示的倉(cāng)庫(kù)布局中，相同物料在如下倉(cāng)庫(kù)布局中，存在于多個(gè)貨位上(如圖中陰影相同的貨位)，因揀選通道某一時(shí)刻僅允許一名揀選員進(jìn)入，當(dāng)存在兩名及以上揀選人員同時(shí)進(jìn)入，會(huì)產(chǎn)生路徑?jīng)_突現(xiàn)象，出現(xiàn)延時(shí)等待現(xiàn)象，因此當(dāng)有更多揀選人員參與揀選作業(yè)時(shí)，揀選復(fù)雜性更大，產(chǎn)生路徑?jīng)_突更加不可避免，使得揀選效率低下，因此在路徑規(guī)劃的時(shí)候需要進(jìn)行路徑?jīng)_突預(yù)測(cè)，進(jìn)行一定的消除，再根據(jù)實(shí)際揀選動(dòng)態(tài)調(diào)整揀選路徑。

1.1 布局分析

本文將選取如圖1所示的倉(cāng)庫(kù)布局平面圖進(jìn)行研究，左右兩側(cè)為單排貨架，中間為背靠式。圖1中每一個(gè)格子代表獨(dú)立的貨位，每一排或列都是由貨位組成的貨架，貨架之間為揀貨通道，貨位編號(hào)從下往上，從左至右由1開(kāi)始遞增，通道編號(hào)從左至右依次遞增，上下為可行走的主通道。倉(cāng)庫(kù)中任意貨位點(diǎn)位置可用編碼(a,b,c)來(lái)表示，其中：a表示通道編號(hào)；b表示通道左右，取值為0或1,0表示位于通道左邊，1表示位于通道右邊；c表示位于該貨架的第幾個(gè)貨位。例如(3,0,15)表示位于第3通道的左邊貨架的第15個(gè)貨位。

本文通過(guò)對(duì)實(shí)際倉(cāng)庫(kù)進(jìn)行模擬，將現(xiàn)實(shí)問(wèn)題進(jìn)行抽象化處理，構(gòu)建相關(guān)數(shù)學(xué)模型進(jìn)行仿真與實(shí)驗(yàn)，并提出一種TWC-IGA的求解方法。首先通過(guò)IGA算法確定揀選人數(shù)、揀貨順序及揀選貨位，并求得揀選路徑集合；然后通過(guò)TWC算法中的時(shí)間窗約束及兩階段策略實(shí)現(xiàn)路徑?jīng)_突的預(yù)測(cè)、消除以及障礙規(guī)避，動(dòng)態(tài)局部地調(diào)整揀貨路徑；最終得到?jīng)]有或路徑?jīng)_突較少的最佳揀選路徑，使得總揀選路徑最短，縮短揀選時(shí)間并提高揀選效率，對(duì)實(shí)際倉(cāng)庫(kù)揀選作業(yè)具有一定的現(xiàn)實(shí)指導(dǎo)意義，能一定程度提高倉(cāng)儲(chǔ)運(yùn)作效率。

1.2 距離矩陣計(jì)算

(1)當(dāng)ai=aj時(shí)，即需揀貨位位于同一通道：

1)bi=bj，即貨位位于同一排貨架上，則dij=|ci-cj|×d。

2)bi≠bj，即貨位分布在同一巷道兩側(cè)，則dij=|ci-cj|×d+e。

(2)當(dāng)bi=bj時(shí)，即需揀貨位位于不同的通道：

1)bi=bj，即兩貨位位于同側(cè)，均位于其所在通道的左側(cè)或右側(cè)，則

dij=min{(ci+cj)×d,[2H-(ci+cj)×

d]}+|ai-aj|×(s+e)。

2)bi≠bj，即兩貨位一個(gè)位于其通道左側(cè)，一個(gè)位于其通道右側(cè),則：

當(dāng)bi

當(dāng)bi>bj時(shí)，有dij=min{(ci+cj)×d,[2H-(ci+cj)×d]}+|ai-aj|×(s+e)-e。

2 MLP的多人揀選路徑優(yōu)化模型

2.1 模型假設(shè)

為便于模型的建立，作如下假設(shè)：

(1)忽略揀貨過(guò)程中垂直方向上的揀貨位移，僅考慮揀貨人員在地面上的行走距離；

(2)每張揀貨單至少包含一種及以上的物料；

(3)任意一個(gè)貨位點(diǎn)需揀選物料重量不超過(guò)揀選作業(yè)小推車及人員的最大作業(yè)能力；

(4)所揀物料在倉(cāng)庫(kù)內(nèi)的位置(貨位已知)且不會(huì)產(chǎn)生缺貨現(xiàn)象；

(5)所有需揀訂單的物料的總量不超過(guò)所有揀貨小車的最大揀選能力；

(6)揀貨員及小推車開(kāi)始進(jìn)行作業(yè)揀選時(shí)統(tǒng)一在出入口處，揀選完畢后回到出入口；

(7)一個(gè)貨位只由一個(gè)揀貨人員進(jìn)行揀選，不重復(fù)揀選；

(8)一種貨物至少有一個(gè)貨位可滿足揀貨需求。

2.2 符號(hào)說(shuō)明及參數(shù)

本文建模設(shè)計(jì)參數(shù)如下：

D為揀選的總路徑；

i,j為貨位，i,j∈N；

m表示參與倉(cāng)庫(kù)揀貨作業(yè)揀貨人數(shù)，m=1,2,3,…,M

h為總分布貨位數(shù)；

Q為揀選小車最大承載能力；

l為揀選路徑的數(shù)量，l=1,2,3,…,L；

t為表示揀選貨物的種類，t=1,2,3,…,T；

qt為物料t的揀貨量；

nm表示第m個(gè)揀貨員揀選的貨位數(shù)量；

dlij為揀選路徑l上貨位i與貨位j之間的距離；

d0l為揀選路徑l上第一個(gè)揀選貨位與揀選中心之間的距離；

dnl為揀選路徑l上最后一個(gè)揀選貨位與揀選中心之間的距離；

uli為揀選路徑l上貨位i需要揀選的量；

xlij為路徑上l上揀選完貨位i是否去揀選貨位j；

2.3 模型構(gòu)建

(1)目標(biāo)函數(shù)及約束條件

在構(gòu)建多人揀選路徑優(yōu)化的模型中，主要是在揀選任務(wù)合理的分配情況下實(shí)現(xiàn)揀選總路徑最短，具體構(gòu)建步驟如下：

步驟1首先確定該批次揀選任務(wù)中進(jìn)行揀選任務(wù)的揀貨人員數(shù)量。在自動(dòng)化程度不高的企業(yè)，揀貨過(guò)程依然采取的是人工揀選的作業(yè)方式，因此多個(gè)揀貨人員同時(shí)進(jìn)行揀選是一種普遍現(xiàn)象。確定揀選作業(yè)所需的人數(shù)，是進(jìn)行揀選路徑規(guī)劃的前提。根據(jù)式(1)可以確定進(jìn)行此次揀選作業(yè)的最少人數(shù)。

(1)

步驟2建立考慮多存儲(chǔ)貨位及多揀選人員情況下的揀貨路徑優(yōu)化模型。目標(biāo)是實(shí)現(xiàn)該批次揀選過(guò)程中所有揀選作業(yè)人員行走距離最短，建立目標(biāo)函數(shù)如式(2)所示：

(2)

(2)目標(biāo)函數(shù)與約束條件說(shuō)明

s.t.

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

L≤M;

(11)

(12)

(13)

(14)

(15)

(16)

式(2)為目標(biāo)函數(shù)，表示所有揀選作業(yè)人員同時(shí)進(jìn)行揀選作業(yè)的行走距離最短，行走路徑為最優(yōu)路徑；式(3)表示任意一條路徑上所有貨位的揀選量不能超過(guò)揀選小車的最大承重；式(4)滿足所有貨物 的揀貨量；式(5)表示一種貨物只能從一個(gè)貨位上進(jìn)行揀選；式(6)指的是貨位滿足貨物的需求量的前提是貨位上有貨物;式(7)表示揀選的貨位滿足揀選需求；式(8)表示所有揀選人員的總的揀貨貨位數(shù)不能超過(guò)貨物分布的貨位數(shù)；式(9)與式(10)表示任意一個(gè)貨位只存在一條揀貨路徑上且只被揀選一次；式(11)表示揀選路徑不能超過(guò)揀貨人員數(shù)量；式(12)表示貨位在揀選路徑只能揀選一次或不被揀選；式(13)～式(16)為決策變量。

3 TWC-IGA算法設(shè)計(jì)

本文提出TWC-IGA來(lái)求解建立的多廠儲(chǔ)位問(wèn)題(Multi Location Problerm,MLP)的多人揀選路徑優(yōu)化模型，算法首先利用改進(jìn)的遺傳算法，即遺傳貪心混合算法來(lái)求解在有多個(gè)存儲(chǔ)貨位時(shí)的多人同時(shí)作業(yè)的揀貨路徑規(guī)劃模型，獲得揀選路徑的集合；然后利用時(shí)間窗算法對(duì)路徑進(jìn)行時(shí)間預(yù)測(cè)，消除可能出現(xiàn)路徑擁塞的情況，并結(jié)合兩階段的規(guī)劃方法實(shí)時(shí)動(dòng)態(tài)地規(guī)劃揀選路徑；最后輸出揀選路徑。

由于標(biāo)準(zhǔn)的遺傳算法的初始種群是隨機(jī)產(chǎn)生的，如果采用單純的輪盤(pán)賭進(jìn)行選擇操作，將很容易陷入局部最優(yōu)解當(dāng)中，使得算法搜索效率低，收斂速度慢。為提高搜索速度和效率，本研究將對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)。因貪心算法求解速度快、局部搜索以及遺傳算法全局尋優(yōu)的能力強(qiáng)，所以本文采用貪心遺傳混合算法求解多人多貨位揀選路徑問(wèn)題。

3.1 IGA算法設(shè)計(jì)

3.1.1 編碼

(1)首先采用實(shí)數(shù)編碼對(duì)倉(cāng)庫(kù)內(nèi)進(jìn)行實(shí)驗(yàn)的某區(qū)內(nèi)的所有貨位進(jìn)行編碼，為了滿足多人揀貨的條件，將在編碼中引入0作為分隔符，用來(lái)區(qū)分不同揀貨人員及其路徑，同時(shí)0作為揀選中心的編碼，1,2,3，…,h表示所有貨位，因此染色體為(0,10,45,42,22,0,88,106,120,0，…)，其中(0,10,45,42,22,0)表示第一個(gè)揀貨人員的路徑從揀選中心出發(fā)依次對(duì)貨位10、貨位45、貨位42、貨位22進(jìn)行揀選，揀選完成后回到揀選中心，依此類推，另外染色體中0的數(shù)量為M+1個(gè)。

(2)采用雙層編碼的方式，對(duì)揀選貨物的順序和貨位的指派位置進(jìn)行編碼。如果有n種待揀選貨物，其中第一層編碼長(zhǎng)度為n，基因?yàn)?～n的整數(shù)的一個(gè)不重復(fù)排序，其中節(jié)點(diǎn)表示貨物揀選順序，第二層編碼長(zhǎng)度為n的整數(shù)編碼，表示某種貨物可選的貨位。

例1一個(gè)合法的染色體可表示為[5,4,2,1,3;1,2,3,3,1]，如圖2所示，第一層編碼是揀選貨物的揀選順序，5,4,2,1,3表示先揀選貨物5，再揀選貨物4，再到2，依次類推，其中路徑的劃分也是按照該順序，依據(jù)揀選小車的載重進(jìn)行子路徑的劃分，完成路徑的規(guī)劃；第二層編碼是揀選貨物所在的貨位順位編號(hào)，1,2,3,3,1表示貨物5由存放該貨物的第1個(gè)貨位提供貨物，貨物4由存放該貨物的第2個(gè)貨位提供，依次類推。

3.1.2 貪心算法產(chǎn)生初始種群

多人揀選路徑問(wèn)題實(shí)質(zhì)上是一個(gè)多旅行商問(wèn)題，屬于NP難問(wèn)題。本文將利用貪心的思想，每個(gè)揀貨員在初始揀貨中心處作為出發(fā)點(diǎn)，始終選擇距離自己最近的貨位作為下一個(gè)揀選貨位(貨位不重復(fù)揀選)，直到達(dá)到揀選小車的載重，最后回到揀選中心。由貪心算法產(chǎn)生一定規(guī)模的初始種群，使算法更快達(dá)到最優(yōu)解。

3.1.3 適應(yīng)度函數(shù)計(jì)算

由MLP多人揀選數(shù)學(xué)模型可知，目標(biāo)函數(shù)是求揀貨路徑最短的問(wèn)題，在遺傳算法中一般選取適應(yīng)度最大的個(gè)體作為最優(yōu)個(gè)體，因此采用倒數(shù)的方法來(lái)獲得函數(shù)的適應(yīng)度值，同時(shí)為了防止數(shù)據(jù)溢出，在目標(biāo)函數(shù)加1，最終得到的適應(yīng)度函數(shù)為如下所示：

(17)

3.1.4 選擇操作

采用輪盤(pán)賭的方式進(jìn)行選擇操作，其思想是個(gè)體被選中的概率與其適應(yīng)度函數(shù)值成正比比例選擇算子，步驟如下：

步驟1計(jì)算每個(gè)個(gè)體的適應(yīng)度值，記為Fi。

步驟2根據(jù)適應(yīng)度的值計(jì)算每個(gè)個(gè)體被選中的概率，計(jì)算公式如下：

(18)

其中：Pi表示個(gè)體i被選擇的概率，F(xiàn)i為個(gè)體i的適應(yīng)度值，Pi越大，則個(gè)體被選中進(jìn)入下一代的概率越大，根據(jù)概率隨機(jī)選擇進(jìn)入下一代的個(gè)體。

3.1.5 遺傳算子設(shè)計(jì)

(1)第一層遺傳算子設(shè)計(jì)

1)變異操作。采用兩點(diǎn)互異進(jìn)行變異操作如圖3所示，其中變異概率pm選擇范圍為[0.01～0.2]，變異是為了產(chǎn)生新的揀貨路徑，對(duì)路徑中的路段進(jìn)行變異操作可以提高算法的效率，保持種群多樣性，步驟如下：

步驟1產(chǎn)生兩個(gè)隨機(jī)自然數(shù)a,b。

步驟2交換第a位和b位的基因，得到新的揀貨順序。

示例說(shuō)明若有染色體為[1,3,2,5,4]表示依次揀選貨物1、3、2、5、4，產(chǎn)生的兩個(gè)隨機(jī)自然數(shù)為a=2,b=4，交換以后，得到新的揀貨順序?yàn)橐来螔x貨物1、5、2、3、4，新的染色體為[1,5,2,3,4]。如圖3所示。

2)交叉操作。采用兩點(diǎn)交叉算子，在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，交換兩個(gè)交叉點(diǎn)中間的元素，產(chǎn)生新的個(gè)體，即產(chǎn)生新的個(gè)體，提高種群的多樣性，如圖4所示。步驟如下：

步驟1隨機(jī)選擇兩個(gè)染色體作為父本。

步驟2產(chǎn)生2個(gè)隨機(jī)自然數(shù)a和b。

步驟3將兩個(gè)父本染色體a～b之間的基因片段進(jìn)行交換, 得到兩個(gè)子代染色體,并對(duì)得到的兩個(gè)染色體進(jìn)行修復(fù)處理,使得不發(fā)生沖突。修復(fù)方法為交叉后, 取交叉片段的補(bǔ)集重新隨機(jī)排列到非交叉片段。

示例說(shuō)明兩個(gè)染色體為[4,3,2,1,5]與[2,3,5,1,4]分別表示兩個(gè)揀選人員的揀選貨物順序，產(chǎn)生隨機(jī)自然數(shù)a=2,b=3進(jìn)行交叉修復(fù)操作，以得到最新的兩條染色體，選擇最優(yōu)的染色體組合，實(shí)現(xiàn)揀選路徑最優(yōu)。如圖4所示。

(2)第二層遺傳算子設(shè)計(jì)

1)變異操作。采用單點(diǎn)變異進(jìn)行變異操作如圖5所示，其中變異概率pm選擇范圍為[0.01～0.2]，變異是為了產(chǎn)生新的揀貨路徑，對(duì)路徑中的路段進(jìn)行變異操作可以提高算法的效率，保持種群多樣性，步驟如下：

步驟1產(chǎn)生一個(gè)隨機(jī)自然數(shù)a,a表示第a位的基因發(fā)生變異。

步驟2采用隨機(jī)變異的方式將第a位的基因進(jìn)行變異。

示例說(shuō)明染色體[1,3,3,2,1,2]表示揀選人員依次揀選貨物對(duì)應(yīng)的其所在第1個(gè)貨位，第3個(gè)貨位，以此類推，現(xiàn)第3位基因發(fā)生變異，則a=3，新的染色體為[1,3,1,2,1,2]，得到不同的揀選路徑。如圖5所示。

2)交叉操作。采用兩點(diǎn)交叉算子，在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，交換兩個(gè)交叉點(diǎn)中間的元素，得到兩個(gè)子代染色體，即產(chǎn)生新的個(gè)體，提高種群的多樣性。步驟如下：

步驟1隨機(jī)選擇兩個(gè)染色體作為父本。

步驟2產(chǎn)生2個(gè)隨機(jī)自然數(shù)a和b。

步驟3將兩個(gè)父本染色體a～b之間的基因片段進(jìn)行交換, 得到兩個(gè)子代染色體。

示例說(shuō)明隨機(jī)選擇表示兩個(gè)揀貨員揀選貨位染色體[1,3,3,2,1,2]與[2,3,1,1,2,3]，若產(chǎn)生的隨機(jī)自然數(shù)a=2,b=4，則進(jìn)行交叉之后得到兩條新的染色體，以獲得最優(yōu)路徑，如圖6所示。

重復(fù)3.1.3節(jié)～3.1.5節(jié)中的操作，直到適應(yīng)度達(dá)到預(yù)期或是達(dá)到最大迭代次數(shù)，結(jié)束并輸出最優(yōu)的種群集合，即最優(yōu)的路徑規(guī)劃。算法流程圖如圖7所示。

3.2 時(shí)間窗路徑擁塞預(yù)測(cè)與兩階段避障策略

倉(cāng)庫(kù)內(nèi)多人同時(shí)進(jìn)行揀選作業(yè)時(shí)出現(xiàn)路徑?jīng)_突或是遇到障礙等問(wèn)題時(shí)有發(fā)生，因此國(guó)內(nèi)外很多學(xué)者對(duì)避免沖突和避障進(jìn)行了研究，但是對(duì)象大多是自動(dòng)引導(dǎo)車與機(jī)器人系統(tǒng)，因此本文將研究“人到貨”模式下的避障問(wèn)題。本文采用時(shí)間窗的預(yù)測(cè)避障方法，從離線與在線兩階段實(shí)現(xiàn)揀貨路徑的規(guī)劃。離線規(guī)劃是指對(duì)多名揀貨作業(yè)人員進(jìn)行全局的靜態(tài)規(guī)劃，在接收到揀貨任務(wù)后，利用改進(jìn)的遺傳算法搜索揀貨人員的最優(yōu)路徑集合；然后利用時(shí)間窗約束預(yù)測(cè)路徑?jīng)_突，選擇最佳的揀貨路徑；在線規(guī)劃是指揀貨人員在揀貨過(guò)程中遇到障礙或更改路徑后，將對(duì)其進(jìn)行路徑賦值，使路徑代價(jià)最大，再利用IGA對(duì)其進(jìn)行局部的路徑調(diào)整，實(shí)現(xiàn)路徑動(dòng)態(tài)規(guī)劃。

算法流程圖8所示,步驟如下：

步驟1對(duì)IGA在離線階段得到的每條路徑，對(duì)第一個(gè)揀貨員所在路徑計(jì)算其在經(jīng)過(guò)單位路徑段的時(shí)間窗ei,初始化第一個(gè)揀貨員各路段的時(shí)間窗集合E1。

步驟2依次計(jì)算剩余揀貨人員經(jīng)過(guò)其揀貨路徑的各個(gè)路徑段的時(shí)間窗集合E2、E3，…,Em。

步驟3對(duì)照揀貨員的路徑，對(duì)揀貨員重疊路徑進(jìn)行時(shí)間窗的對(duì)比，若存在空閑時(shí)間窗，則不存在沖突，按照離線階段規(guī)劃的揀貨路線進(jìn)行揀貨作業(yè)的操作；否則，執(zhí)行步驟4。

步驟4當(dāng)存在路徑?jīng)_突即路段時(shí)間窗重合ei=ej或是遇到客觀障礙時(shí)，在揀貨中將出現(xiàn)路徑“死鎖”現(xiàn)象，這時(shí)需要進(jìn)入在線階段，根據(jù)實(shí)際揀選中優(yōu)先申請(qǐng)疊加路徑為優(yōu)先級(jí)，利用IGA重新規(guī)劃局部揀貨路線，對(duì)規(guī)劃的局部揀貨路線執(zhí)行步驟1與步驟2。

步驟5重復(fù)步驟3～步驟4,直至所有揀貨人員在揀貨過(guò)程中不發(fā)生路徑?jīng)_突的情況下揀選路徑最短。

4 算例分析

根據(jù)研究分析可知，目前較多文獻(xiàn)的研究還是集中在單個(gè)揀選人員或設(shè)備進(jìn)行揀選時(shí)的路徑規(guī)劃，或是一種貨物存放在一個(gè)儲(chǔ)位上，但通過(guò)實(shí)際調(diào)研可知，這種假設(shè)不適于實(shí)際倉(cāng)儲(chǔ)作業(yè)中。安徽BY倉(cāng)庫(kù)中往往是一種貨物根據(jù)生產(chǎn)工藝或需求有多個(gè)存放儲(chǔ)位和多揀貨員同時(shí)工作，路徑選擇也依據(jù)個(gè)人經(jīng)驗(yàn)，缺乏合理規(guī)劃，當(dāng)參與人數(shù)較多時(shí)，在較為狹小的巷道中會(huì)出現(xiàn)排隊(duì)現(xiàn)象，即產(chǎn)生了路徑?jīng)_突，降低揀選效率。因此，研究多儲(chǔ)位下的多人揀選路徑優(yōu)化研究，并動(dòng)態(tài)解決路徑?jīng)_突問(wèn)題，得到最優(yōu)的揀選路徑，將有利于提高安徽BY實(shí)際揀選效率，達(dá)到倉(cāng)儲(chǔ)運(yùn)作最大化。

本章將通過(guò)實(shí)驗(yàn)對(duì)模型和算法進(jìn)行仿真測(cè)試，該實(shí)驗(yàn)基于AMD A6-6310 APU with AMD Radeon R4 Graphics 處理器、8 G內(nèi)存、64位Windows 10環(huán)境運(yùn)行，使用的仿真軟件為MATLAB R2016a，進(jìn)行本文所提的TWC-IGA與遺傳算法、貪心算法的對(duì)比，驗(yàn)證本文所提的TWC-IGA更有利于解決MLP下的多人揀選路徑的規(guī)劃，路徑?jīng)_突與動(dòng)態(tài)規(guī)劃問(wèn)題。設(shè)單個(gè)貨位的長(zhǎng)度與寬度均為1 m，巷道寬度為1.5 m，左右兩側(cè)單排貨架，中間為背靠式貨架，巷道最大編號(hào)為10，每列貨架共有40個(gè)貨位；揀選小車的最大承重為25 kg，本文通過(guò)安徽BY零件庫(kù)為背景，取如下部分實(shí)驗(yàn)數(shù)據(jù)[13]進(jìn)行仿真，如表1所示。

表1 揀選貨物坐標(biāo)及倉(cāng)庫(kù)存儲(chǔ)情況(部分)

4.1 參數(shù)設(shè)置和仿真實(shí)驗(yàn)

本文采用的混合算法與對(duì)比算法終止方式是設(shè)定一定的迭代次數(shù)，達(dá)到最大迭代次數(shù)將停止算法的運(yùn)行，算法中涉及的主要仿真參數(shù)的取值如表2和表3所示，其中表2為模型參數(shù)，表3為算法參數(shù)。

表2 模型參數(shù)

表3 算法參數(shù)

通過(guò)多次實(shí)驗(yàn)，設(shè)置種群規(guī)模為100，交叉概率為0.9，變異概率為0.1，最大迭代次數(shù)2 000進(jìn)行仿真，得到的結(jié)果更優(yōu)。如圖9所示為某次運(yùn)行的最優(yōu)解與種群均值的跟蹤圖，由圖9可以看出TWC-IGA對(duì)于目標(biāo)函數(shù)具有較好的優(yōu)化效果，在迭代次數(shù)在1 000左右最優(yōu)值和種群均值開(kāi)始趨于收斂，逐漸穩(wěn)定，得到的總路徑長(zhǎng)度為900.5 m。路徑規(guī)劃如表4所示，通過(guò)TWC-IGA解決了揀選過(guò)程中可能會(huì)產(chǎn)生的路徑?jīng)_突，并規(guī)劃出總揀選路徑最短的揀選路線，優(yōu)化得到的路線圖如圖10所示。

表4 揀貨路線及對(duì)應(yīng)坐標(biāo)

4.2 性能分析

為驗(yàn)證TWC-IGA的性能，本文將利用遺傳算法與貪心算法分別對(duì)優(yōu)化模型進(jìn)行求解，得到最優(yōu)解與種群均值的跟蹤圖分別如圖11和圖12所示。根據(jù)算法跟蹤圖可知，貪心算法在經(jīng)過(guò)大約800次迭代左右逐漸趨于收斂，總路徑為1 191 m；遺傳算法經(jīng)過(guò)大約1 200次迭代后開(kāi)始趨于收斂逐漸平穩(wěn)，雖然較貪心算法迭代次數(shù)多，但得到的路徑更優(yōu)，為992 m。

通過(guò)仿真實(shí)驗(yàn)，得出如表5所示數(shù)據(jù)，相對(duì)于貪心算法，遺傳算法路徑節(jié)約比例為16.71%，TWC-IGA路徑節(jié)約比例為24.39%，可知本文提出的TWC-IGA結(jié)果更優(yōu)，同時(shí)根據(jù)三者的迭代曲線圖如圖13所示，可知本文提出的TWC-IGA，不但解決了路徑?jīng)_突問(wèn)題，且運(yùn)行速度快，效果更好，大大提高了揀選效率。

表5 仿真優(yōu)化對(duì)比

為避免實(shí)驗(yàn)結(jié)果的偶然性，本文將按照上述參數(shù)設(shè)定，再進(jìn)行另外兩組實(shí)驗(yàn)，分別為20種貨物分布在37個(gè)貨位上以及15種貨物分布在31個(gè)貨位上，實(shí)驗(yàn)數(shù)據(jù)如表6所示。

依據(jù)圖14與圖15所示，本文所改進(jìn)的TWC-IGA得到的結(jié)果相較貪心算法和遺傳算法均要好，且依據(jù)表6數(shù)據(jù)可知，本文所提算法相比與遺傳算法和貪心算法而言，隨著實(shí)驗(yàn)數(shù)據(jù)規(guī)模的增大，節(jié)約比例增大，驗(yàn)證了本文所提算法對(duì)于路徑的優(yōu)化效果依然更好，而且優(yōu)化效果更顯著，因此本文提出的算法在一定程度上能夠解決實(shí)際倉(cāng)儲(chǔ)揀選作業(yè)中的路徑規(guī)劃問(wèn)題，對(duì)安徽BY零件庫(kù)揀選作業(yè)具有一定的實(shí)際意義與有效性，實(shí)現(xiàn)了整個(gè)生產(chǎn)車間的智能化。

表6 揀貨路徑對(duì)比實(shí)驗(yàn)

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

通過(guò)TWC-IGA為多個(gè)揀貨員同時(shí)作業(yè)時(shí)進(jìn)行路徑規(guī)劃，同時(shí)時(shí)間窗約束和兩階段規(guī)劃策略能夠有效地預(yù)測(cè)路徑?jīng)_突與規(guī)避障礙，能快速獲取不產(chǎn)生路徑?jīng)_突的新路徑，避免了路徑?jīng)_突造成揀貨時(shí)間的增加和縮短揀選路徑。在電子商務(wù)大環(huán)境下，有利于降低大規(guī)模倉(cāng)庫(kù)人工揀選的復(fù)雜性，大大提高了揀選效率和倉(cāng)儲(chǔ)運(yùn)作效率，對(duì)安徽BY倉(cāng)儲(chǔ)揀選作業(yè)具有實(shí)際的指導(dǎo)意義。本文在建模過(guò)程中，還是將實(shí)際運(yùn)作中有關(guān)影響因素理想化，在以后的研究中將這些影響因素加入模型，使得研究成果與現(xiàn)實(shí)倉(cāng)庫(kù)作業(yè)更加吻合，解決眾多企業(yè)倉(cāng)庫(kù)揀選難的作業(yè)問(wèn)題，提高揀選效率。