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

胡小建, 楊 智

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

0 引 言

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

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

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

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

1 問題描述

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

圖1 分揀倉庫柵格地圖

分揀倉庫柵格地圖由以下6個部分構成:

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

(2)停靠區。用于空閑揀貨小車和已經完成搬運任務揀貨小車的停靠,所有揀貨小車均從停靠區出發。圖1中箭頭所指停靠區為坐標起點(1,1)。

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

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

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

(6)分揀目的地。分揀目的地與貨架相對應,若貨架坐標(3,15),則揀貨小車需行駛至柵格(3,16)進行分揀。

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

問題參數如下:設G=(V,E)為分揀倉庫賦權圖,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搬運貨物停車等待次數。

問題假設如下:

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

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

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

(4)不考慮包裹到達停靠區后的出庫過程。

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

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

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

2 多車路徑規劃模型

Tk、Tmax計算方法如下:

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

(1)

(2)

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

(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)

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

3 模型求解

3.1 混合遺傳算法

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

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

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

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

圖2 編碼示意圖

首先對分揀倉庫內所有貨架進行編碼,在實數編碼中引入0作為分隔符,用來區分不同揀貨小車及其路徑,同時用0作為停靠區的編碼。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輛揀貨小車從停靠區出發依次對貨位64、貨位25、貨位6、貨位33、貨位18進行揀貨,揀選完成后返回停靠區,以此類推,另外染色體中0的數量為m+1個。

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

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

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

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

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

圖3 交叉示意圖

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

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

(7)變異運算。采用2點互異進行變異操作，如圖4所示,其中變異概率pm選擇范圍為[0.01～0.2],變異是為了產生新的揀貨路徑,對路徑中的路段進行變異操作，可以提高算法的效率,保持種群的多樣性。步驟如下:① 產生2個隨機自然數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,產生隨機自然數r1=4、r2=7進行變異運算即交換第4位和第7位的基因,得到新的揀貨順序為9、5、1、7、3、8、6、10、4、2,新的染色體為(9,5,1,7,3,8,6,10,4,2)。

3.2 避碰規則

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

表1 不同揀貨小車屬性優先級的比較

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

當產生沖突的2個揀貨小車的屬性相同時,根據載貨的情況判斷貨物優先級,貨物優先級高的揀貨小車的優先級高;空車的,優先級相同。

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

圖5 混合遺傳算法流程

4 數據實驗

4.1 實驗設計

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

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

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

4.2 實驗結果分析

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

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

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

由表2、表3可知:

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

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

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

以10×2規模為例,優化后的揀貨路徑如圖6所示。

圖6 10×2規模問題下揀貨路徑優化示意圖

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

表4 10個揀選點下優化前后路徑和節約時間比例表

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

4.3 問題參數分析

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

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

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

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

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

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

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

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

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

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

5 結 論

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