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

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

0 引言

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

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

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

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

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

1 問題描述

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

1.1 布局分析

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

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

1.2 距離矩陣計算

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

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

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

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

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

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

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

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

當(dāng)bi

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

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

2.1 模型假設(shè)

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

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

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

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

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

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

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

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

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

2.2 符號說明及參數(shù)

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

D為揀選的總路徑；

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

m表示參與倉庫揀貨作業(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個揀貨員揀選的貨位數(shù)量；

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

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

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

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

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

2.3 模型構(gòu)建

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

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

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

(1)

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

(2)

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

s.t.

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

L≤M;

(11)

(12)

(13)

(14)

(15)

(16)

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

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

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

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

3.1 IGA算法設(shè)計

3.1.1 編碼

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

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

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

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

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

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

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

(17)

3.1.4 選擇操作

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

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

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

(18)

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

3.1.5 遺傳算子設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

示例說明隨機(jī)選擇表示兩個揀貨員揀選貨位染色體[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 時間窗路徑擁塞預(yù)測與兩階段避障策略

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

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

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

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

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

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

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

4 算例分析

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

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

表1 揀選貨物坐標(biāo)及倉庫存儲情況(部分)

4.1 參數(shù)設(shè)置和仿真實驗

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

表2 模型參數(shù)

表3 算法參數(shù)

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

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

4.2 性能分析

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

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

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

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

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

表6 揀貨路徑對比實驗

5 結(jié)束語

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