基于混合遺傳算法的多揀貨小車路徑規(guī)劃研究

胡小建, 楊 智

(1.合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥 230009; 2.合肥工業(yè)大學(xué) 過程優(yōu)化與智能決策教育部重點實驗室,安徽 合肥 230009)

0 引 言

在互聯(lián)網(wǎng)和電子商務(wù)快速發(fā)展的背景下,各大電商企業(yè)都在建立立體倉庫用來提升相對落后的物流系統(tǒng)。“人到貨”的分揀指的是人配合揀貨小車用RFID掃描進(jìn)行揀貨。分揀倉庫中貨物的分揀大多數(shù)還是“人到貨”的分揀,如典型的京東亞洲一號倉庫的分揀,本文主要研究“人到貨”的分揀。分揀倉庫中的揀貨小車調(diào)度問題是分揀系統(tǒng)中一個重要研究問題,也是目前國內(nèi)外學(xué)者研究的熱點問題。合理的車輛調(diào)度方案可以為企業(yè)節(jié)省運輸成本和時間,提高物流服務(wù)的效率,為企業(yè)提升競爭力,因此對該問題的研究很有價值。

揀貨小車調(diào)度問題包括單車調(diào)度問題和多車調(diào)度問題。對于單車調(diào)度問題,文獻(xiàn)[1]基于基因表達(dá)式編程挖掘出高效實時調(diào)度規(guī)則;文獻(xiàn)[2]在柔性制造系統(tǒng)中研究了一輛自動導(dǎo)引車的調(diào)度問題,建立了混合整數(shù)線性規(guī)劃模型,提出了最佳解決方案,并研究了一些管理規(guī)則以及經(jīng)典假設(shè)的影響。對于多車調(diào)度問題,文獻(xiàn)[3]研究了一個新的自動導(dǎo)引車輛調(diào)度問題,該問題涉及在具有多品種和小批量生產(chǎn)的矩陣制造車間中從貨物處理中取貨和交貨,建立了一個多目標(biāo)混合整數(shù)規(guī)劃模型,并設(shè)計了一種有效的多目標(biāo)進(jìn)化算法來解決該問題;文獻(xiàn)[4]解決了一個矩陣制造車間物料搬運過程中的多自動導(dǎo)引車調(diào)度問題,該問題旨在確定一種解決方案以使運輸成本最小化,為此建立了混合整數(shù)線性規(guī)劃模型,提出了一種離散的人工蜂群算法以及一些新的技術(shù)來解決該問題;文獻(xiàn)[5]提出了基于軟時間窗的自動導(dǎo)引車調(diào)度規(guī)則;文獻(xiàn)[6-10]分別提出了改進(jìn)的差分進(jìn)化算法、混合禁忌蝙蝠算法、優(yōu)化的模糊決策算法、改進(jìn)的花授粉算法以及改進(jìn)的混合遺傳算法與粒子群算法;文獻(xiàn)[11]研究了動態(tài)作業(yè)選擇調(diào)度規(guī)則在2種不同規(guī)模柔性制造系統(tǒng)中同時調(diào)度多載自動導(dǎo)引車的性能。

在分揀倉庫中,不僅要考慮揀貨小車的調(diào)度還要考慮多輛揀貨小車的路徑規(guī)劃以及防碰撞問題。針對揀貨小車路徑規(guī)劃,文獻(xiàn)[12]提出了一種混沌模擬退火粒子群優(yōu)化算法解決魚骨型倉庫布局揀選路徑優(yōu)化問題;文獻(xiàn)[13]提出了一種混合粒子群優(yōu)化算法求解多車協(xié)同揀選調(diào)度優(yōu)化模型。對于防碰撞問題,文獻(xiàn)[14]提出了一種環(huán)路死鎖搜索方法;文獻(xiàn)[15]提出了一種動態(tài)加權(quán)地圖的交通規(guī)則和基于預(yù)約表的改進(jìn)A*算法。

分析以上文獻(xiàn)可知,多車調(diào)度一般假定揀貨小車不會發(fā)生沖突且搬運路徑固定。本文綜合考慮了揀貨小車的調(diào)度、路徑規(guī)劃以及多車之間防碰撞,建立多車路徑規(guī)劃模型以最小化最大搬運完成時間為優(yōu)化目標(biāo),并采用遺傳算法和A*算法混合的混合遺傳算法求解。通過比較優(yōu)化后的路徑與優(yōu)化前的路徑,計算出節(jié)約的時間比例。為驗證算法的性能,進(jìn)行了仿真實驗,在數(shù)據(jù)實驗中用HGA進(jìn)行了12組實驗并觀察了關(guān)鍵問題參數(shù)的影響。

1 問題描述

本文采用的分揀倉庫柵格地圖如圖1所示。

圖1 分揀倉庫柵格地圖

分揀倉庫柵格地圖由以下6個部分構(gòu)成:

(1)分揀臺。位于柵格地圖的最左側(cè)即柵格地圖中的第1列,用于存放已經(jīng)打包完成的包裹。

(2)停靠區(qū)。用于空閑揀貨小車和已經(jīng)完成搬運任務(wù)揀貨小車的?？?所有揀貨小車均從?？繀^(qū)出發(fā)。圖1中箭頭所指停靠區(qū)為坐標(biāo)起點(1,1)。

(3)道路。柵格地圖中白色的部分,用于揀貨小車的行駛。

(4)揀貨小車。用于揀貨作業(yè)中裝載貨物的車輛,在倉庫道路上以勻速v行駛。

(5)貨架。將柵格地圖均勻分割出多個存貨區(qū),每個存貨區(qū)有4個貨架用于存放貨物。圖1中所指貨架坐標(biāo)為(3,15)且各個貨架均用坐標(biāo)標(biāo)出。

(6)分揀目的地。分揀目的地與貨架相對應(yīng),若貨架坐標(biāo)(3,15),則揀貨小車需行駛至柵格(3,16)進(jìn)行分揀。

本文考慮多個訂單、多個目標(biāo)貨架、多輛揀貨小車,根據(jù)訂單進(jìn)行目標(biāo)貨架的選擇以及多車揀選的路徑規(guī)劃問題。一方面,在平倉里進(jìn)行揀選時通常是多輛揀貨小車同時進(jìn)行揀選且由不同的貨架存放不同的貨物,此時需要提前根據(jù)訂單規(guī)劃好最優(yōu)的路徑,避免降低揀貨效率;另一方面,多車同時進(jìn)行揀選容易出現(xiàn)路徑?jīng)_突現(xiàn)象即在相同時間出現(xiàn)在相同位置,此時會造成道路擁堵,降低揀貨效率。從圖1可以看出,第1輛揀貨小車和第m輛揀貨小車在相同時間、相同位置相遇就會產(chǎn)生路徑?jīng)_突,在該分揀倉庫進(jìn)行揀貨作業(yè)的揀貨小車越多,揀貨的復(fù)雜性就越大,產(chǎn)生路徑?jīng)_突就越容易,揀貨效率會降低,因此在路徑規(guī)劃時需要根據(jù)避碰規(guī)則里小車的優(yōu)先級讓優(yōu)先級低的揀貨小車停車等待,優(yōu)先級高的揀貨小車優(yōu)先通過,以此來達(dá)到消除路徑?jīng)_突的目的,最后根據(jù)實際的揀貨狀況動態(tài)調(diào)整揀貨路徑。下面介紹問題參數(shù)與假設(shè)條件。

問題參數(shù)如下:設(shè)G=(V,E)為分揀倉庫賦權(quán)圖,V={i|1,2,…,n}為貨架集合,E為邊集;各貨架之間的距離為dij,已知(dij>0且i,j∈V),距離用曼哈頓距離dij=|xi-xj|+|yi-yj|;v為揀貨小車的行駛速度;xijk為決策變量(0-1變量)表示揀貨小車k從貨架i到貨架j為1,否則為0;k為揀貨小車的編號;K為揀貨小車編號集合,k∈K={1,2,…,m};Tk為揀貨小車k搬運一次貨物所需要的時間;tw為揀貨小車一次停車等待的時間;Tmax為最大搬運完成時間;nkw為揀貨小車k搬運貨物停車等待次數(shù)。

問題假設(shè)如下:

(1)揀貨小車在行駛的過程中保持勻速。

(2)揀貨小車可以沿上下或左右在柵格上行駛,但不允許沿對角線穿越柵格。

(3)不考慮揀貨小車的裝貨與卸貨時間,即揀貨小車的裝貨和卸貨時間為0。

(4)不考慮包裹到達(dá)?？繀^(qū)后的出庫過程。

(5)本文所用倉庫為傳統(tǒng)的分揀倉庫。

(6)所有貨架上都有貨物,所有揀貨小車均可使用。

(7)揀貨小車不考慮容積約束和載重約束。

2 多車路徑規(guī)劃模型

Tk、Tmax計算方法如下:

|yi-yj|)xijk]/v+twnkw

(1)

(2)

基于(1)式、(2)式可得最小化最大搬運完成時間目標(biāo)函數(shù)為:

(3)

約束條件為:

(4)

(5)

?S?V；k=1,…,m

(6)

xijk∈{0,1}，i=0,…,n;k=1,…,m

(7)

x01=1,xn0=1

(8)

tw>0

(9)

其中:目標(biāo)函數(shù)(3)式表示最小化最大揀貨小車搬運完成時間;(4)式、(5)式表示所有待取貨點所在貨架都被選取且僅一次;(6)式則保證沒有任何子回路解產(chǎn)生;(7)式表示決策變量是0-1變量即揀貨小車從貨架i到貨架j為1,否則為0;(8)式表示揀貨小車進(jìn)行揀選作業(yè)時從?？繀^(qū)出發(fā),揀選作業(yè)完成后返回停靠區(qū);(9)式表示揀貨小車單次停車等待的時間要大于0。

3 模型求解

3.1 混合遺傳算法

本文研究的多揀貨小車調(diào)度與路徑規(guī)劃問題類似于多旅行商問題(multiple traveling salesman problems,M-TSP),因此遺傳算法是求解該問題有效的智能算法,而A*算法是搜索最短路徑的啟發(fā)式算法并且可以用來得出揀貨小車相鄰揀貨任務(wù)之間的最短路徑的路徑坐標(biāo),本文將遺傳算法和A*算法混合得到混合遺傳算法(hybrid genetic algarithm,HGA)用于求解多車路徑規(guī)劃模型。

A*算法主要用求得出多輛揀貨小車的最短路徑的路徑坐標(biāo),然后在遺傳算法中根據(jù)多輛揀貨小車的路徑坐標(biāo)計算停車等待次數(shù)nkw,再根據(jù)nkw計算各個個體的適應(yīng)度值。

HGA求解多車路徑規(guī)劃模型基本步驟如下。

(1)染色體編碼。個體編碼方法采用實數(shù)編碼，如圖2所示。

圖2 編碼示意圖

首先對分揀倉庫內(nèi)所有貨架進(jìn)行編碼,在實數(shù)編碼中引入0作為分隔符,用來區(qū)分不同揀貨小車及其路徑,同時用0作為?？繀^(qū)的編碼。1,2,3,…,s表示所有貨架。因此，染色體為(0,64,25,6,33,18,0,12,8,27,55,34,0，…),其中(0,1,2,3,4,5,0)表示第1輛揀貨小車從停靠區(qū)出發(fā)依次對貨位64、貨位25、貨位6、貨位33、貨位18進(jìn)行揀貨,揀選完成后返回?？繀^(qū),以此類推,另外染色體中0的數(shù)量為m+1個。

(2)產(chǎn)生初始種群。初始化種群大小p、揀貨點個數(shù)n(即染色體基因數(shù))、算法迭代的次數(shù)I、交叉概率pc和變異概率pm等參數(shù)。

(3)根據(jù)路徑坐標(biāo)計算停車等待次數(shù)。首先根據(jù)A*算法得出揀貨小車揀貨的路徑坐標(biāo);然后根據(jù)路徑坐標(biāo)計算停車等待次數(shù)nkw。

(4)適應(yīng)度函數(shù)。在多車路徑規(guī)劃模型中,已知距離矩陣d,根據(jù)n個揀選點的隨機排列(每個染色體)和揀貨小車的行駛速度v可計算出總運輸時間,比較多輛小車的總運輸時間,將最大的總運輸時間作為適應(yīng)度函數(shù),即最大的運輸時間越短,適應(yīng)度函數(shù)越好。

(5)選擇運算。采用基于適應(yīng)度比例的選擇策略,即適應(yīng)度越好的個體被選擇的概率越大。

(6)交叉運算。采用2點交叉算子,在相互配對的2個染色體編碼串中隨機設(shè)置2個交叉點,交換2個交叉點中間的元素,產(chǎn)生新的個體,提高種群的多樣性,如圖3所示。

圖3 交叉示意圖

步驟如下:① 隨機選擇2個染色體作為父本;② 產(chǎn)生2個隨機自然數(shù)r1、r2;③ 將2個父本染色體r1至r2之間的基因片段進(jìn)行交換,得到2個子代染色體,并對得到的2個染色體進(jìn)行修復(fù)處理,使得不發(fā)生沖突。修復(fù)方法為交叉后取交叉片段的補集重新隨機排列到非交叉片段。

示例說明:2個父代染色體為(9,5,1,3,7,4,2,10,8,6)與(10,5,4,6,3,8,7,2,1,9)分別表示2輛揀貨小車的揀貨順序,產(chǎn)生隨機自然數(shù)r1=4、r2=7進(jìn)行交叉修復(fù)操作,以得到新的2條染色體,選擇最優(yōu)的染色體組合,實現(xiàn)揀貨路徑最優(yōu)。

(7)變異運算。采用2點互異進(jìn)行變異操作，如圖4所示,其中變異概率pm選擇范圍為[0.01～0.2],變異是為了產(chǎn)生新的揀貨路徑,對路徑中的路段進(jìn)行變異操作，可以提高算法的效率,保持種群的多樣性。步驟如下:① 產(chǎn)生2個隨機自然數(shù)r1、r2;② 交換第r1位和第r2位的基因,得到新的揀貨順序。

圖4 變異示意圖

示例說明:有染色體為(9,5,1,6,3,8,7,10,4,2)表示依次揀選貨架9、5、1、6、3、8、7、10、4、2,產(chǎn)生隨機自然數(shù)r1=4、r2=7進(jìn)行變異運算即交換第4位和第7位的基因,得到新的揀貨順序為9、5、1、7、3、8、6、10、4、2,新的染色體為(9,5,1,7,3,8,6,10,4,2)。

3.2 避碰規(guī)則

根據(jù)揀貨小車載貨情況的不同,將揀貨小車的屬性分為揀選過程中的載貨、返回過程中的載貨和空車3種屬性。本文根據(jù)揀貨小車的不同屬性給予不同的優(yōu)先級,根據(jù)揀貨小車優(yōu)先級確定避碰規(guī)則。不同揀貨小車屬性優(yōu)先級的比較見表1所列。

表1 不同揀貨小車屬性優(yōu)先級的比較

當(dāng)產(chǎn)生沖突的2輛揀貨小車的屬性不同時,判斷2輛揀貨小車的優(yōu)先級,載貨(揀選)的揀貨小車優(yōu)先級最高,載貨(返回)的優(yōu)先級其次,空車的優(yōu)先級最低。

當(dāng)產(chǎn)生沖突的2個揀貨小車的屬性相同時,根據(jù)載貨的情況判斷貨物優(yōu)先級,貨物優(yōu)先級高的揀貨小車的優(yōu)先級高;空車的,優(yōu)先級相同。

HGA的算法流程如圖5所示。

圖5 混合遺傳算法流程

4 數(shù)據(jù)實驗

4.1 實驗設(shè)計

仿真對象為分揀倉庫,其各項參數(shù)取值參見1.1節(jié)問題參數(shù)與假設(shè)條件。本文中實驗為多車路徑規(guī)劃實驗。實驗運行環(huán)境為Intel(R)Core(TM)i5-5200U CPU @2.20 GHz,仿真軟件為Matlab R2016a。

為驗證HGA的有效性和先進(jìn)性,以分揀倉庫模型為仿真實例進(jìn)行實驗。HGA中揀貨小車行駛速度v=1 m/s,種群大小p=100,迭代次數(shù)I=100。

問題規(guī)模設(shè)置為:揀選點數(shù)n為10、20、30、40;揀貨小車數(shù)m為2、5、10。實驗共分為12組,每組隨機生成10個算例。

4.2 實驗結(jié)果分析

12組實驗算法的求解結(jié)果即最小化最大搬運完成時間(minTmax)和算法運行時間(algorithm running time,TAR)見表2、表3所列。表2、表3中加粗的數(shù)值是每組實驗中的最小值。

表2 12次實驗的min Tmax和TAR(算例1～算例5)

表3 12次實驗的min Tmax和TAR(算例6～算例10)

由表2、表3可知:

(1)minTmax越小,不代表TAR越小。

(2)最小的minTmax和最小TAR發(fā)生在10×10規(guī)模問題中,數(shù)值分別為16 s和4.19 s。

(3)最大的minTmax和最大TAR發(fā)生在40×2規(guī)模問題中,數(shù)值分別是174 s和146.51 s。

以10×2規(guī)模為例,優(yōu)化后的揀貨路徑如圖6所示。

圖6 10×2規(guī)模問題下揀貨路徑優(yōu)化示意圖

以10個揀選點為例,優(yōu)化前后路徑和節(jié)約時間比例見表4所列。表4中:t1為優(yōu)化前小車行駛的總時間;t2為優(yōu)化后小車行駛的總時間;(t1-t2)/t1為節(jié)約時間的比例。從表4中可以看出，10×2規(guī)模下節(jié)約時間的比例最大,節(jié)約了24.19%。

表4 10個揀選點下優(yōu)化前后路徑和節(jié)約時間比例表

同理可知,在20個揀選點情況下,20×2規(guī)模下節(jié)約時間的比例最大,節(jié)約了31.56%;在30個揀選點情況下,30×10規(guī)模下節(jié)約時間的比例最大,節(jié)約了20.86%;在40個揀選點情況下,40×2規(guī)模下節(jié)約時間的比例最大,節(jié)約了16.75%。

4.3 問題參數(shù)分析

本文重點分析研究問題中參數(shù)揀選點數(shù)n和揀貨小車數(shù)m對HGA性能的影響。

(1)本文采用HGA求得12個實驗組的最小化最大搬運完成時間(minTmax)和算法運行時間,其平均值如圖7、圖8所示。

圖7 不同揀選點數(shù)量下的最小化最大搬運完成時間

圖8 不同揀選點數(shù)量下的算法運行時間

分析可得,當(dāng)m分別為2、5、10時,隨著n的增大,minTmax和算法運行時間基本呈線性增長趨勢,說明HGA具有良好的穩(wěn)定性和擴展性。

(2)通過揀選點數(shù)n為10、20、30、40且m為2、5、10的12組實驗,分析揀貨小車數(shù)m對HGA的影響,如圖9所示,當(dāng)n為10、20、30、40時,隨著m的增大,minTmax呈下降趨勢且下降的斜率逐漸減小。原因分析如下:增加揀貨小車的數(shù)量雖能減少搬運完成時間,但揀貨小車的停車等待次數(shù)增多了即總的時間增加了,降低了小車的利用率。因此,需要根據(jù)倉庫的規(guī)模大小和揀選點數(shù)確定合適的揀貨小車的數(shù)量,提升小車的利用率。

圖9 不同揀貨小車數(shù)量下的最小化最大搬運完成時間

(3)不同揀貨小車數(shù)量下的算法運行時間如圖10所示。從圖10可以看出,n為10、20、30時,隨著揀貨小車數(shù)量的增加,算法運行時間呈下降趨勢且下降斜率逐漸減小;n=40時、m=10的算法運行時間比n=40、m=5的算法運行時間還要長。

圖10 不同揀貨小車數(shù)量下的算法運行時間

原因分析如下:增加揀貨小車的數(shù)量能減少算法運行時間,但隨著任務(wù)規(guī)模的增大,增加揀貨小車的數(shù)量會增加算法的時間復(fù)雜度和空間復(fù)雜度,增加算法的運行時間。

5 結(jié) 論

本文研究“人到貨”分揀情形下的揀貨小車的路徑規(guī)劃問題,提出了分揀倉庫的柵格地圖模型。在此基礎(chǔ)上構(gòu)建了多車路徑規(guī)劃模型,并采用HGA求解。經(jīng)過計算發(fā)現(xiàn)優(yōu)化后的路徑比優(yōu)化前的路徑最大可節(jié)約31.56%的時間。最后進(jìn)行了12組實驗,每組實驗10個算例,大量實驗表明,HGA有良好的穩(wěn)定性和可擴展性。根據(jù)問題參數(shù)的分析表明,當(dāng)揀貨小車數(shù)量超過一定值之后,最小化最大搬運完成時間減小幅度越來越小,表明揀貨小車的利用率在下降，即多輛揀貨小車容易造成資源的浪費,如何在現(xiàn)有的倉庫容量下合理地確定揀貨小車的數(shù)量,實現(xiàn)資源的有效利用是接下來研究的重點。