基于偏離度的揀貨路徑的優(yōu)化

1、基于偏離度的揀貨路徑的優(yōu)化揀貨作業(yè)是倉儲管理中一個必不可少的環(huán)節(jié)，該環(huán)節(jié)的效率如何、差錯率高低直接影響倉儲管理運行效率。傳統(tǒng)的揀貨方法都沒有系統(tǒng)地對每種貨物在倉庫中的位置進行描述，沒有建立倉庫入口與所揀貨物之間的路徑幾何關(guān)系，只是機械地或者主觀地根據(jù)所揀貨物位置以及種類，隨機選擇一條自己認為比較合適的路線，而沒有依據(jù)所揀貨物的種類及其相互間的位置關(guān)系進行揀貨最佳路徑的計算與設(shè)計，使得很多時候倉儲人員都會把時間浪費在揀貨的流程上?；谄x度的揀貨方法是近年來興起的一種比較科學的揀貨方法。本文在S形啟發(fā)方式揀貨的基礎(chǔ)之上，將基于偏離度的揀貨方法結(jié)合在一起，根據(jù)揀貨點與貨物存儲地點之間的偏差來對揀貨

2、的路徑進行規(guī)劃與不斷的修正。1、相關(guān)問題的提出本文研究的是平行揀貨通道倉庫的揀貨路徑問題。以某倉儲系統(tǒng)的倉庫為例（如圖1所示），在該倉庫中，分揀貨物的通道首先可以分為橫向通道與縱向通道，其中橫向通道數(shù)目要少于縱向通道的數(shù)目。橫向通道主要有前橫向通道和后橫向通道，縱向通道與貨物的擺放呈平行的關(guān)系。在揀貨的過程中，同一條路徑到達路徑兩邊貨物的距離在本文中忽略不計。在這個倉庫中只有一個出口，揀貨人員的目的就是從圖1左下方的入口進入倉庫并在某目標地點揀貨然后返回出口。本文就是通過偏離度的方法計算從出口到揀貨再回到出口的最短路徑。2、偏離度下的路徑優(yōu)化本文是在S形啟發(fā)方式揀貨的基礎(chǔ)之上來設(shè)計揀貨路徑的。

3、所謂S形啟發(fā)式的揀貨方法，就是揀貨人員通過出口進入到倉庫以后，從一條縱向的通道進去揀貨然后再進入下一個縱向的通道，揀貨員的整個路線呈現(xiàn)S形，一直到回到出口完成揀貨任務(wù)。目前大部分倉儲企業(yè)的揀貨方式都是以此方式為基礎(chǔ)的。2.1 偏離度的概述在本算法中偏離度的含義是指倉儲人員從進入倉庫入口處到實際的貨物之間的距離，也就是描述了出發(fā)地與目標地之間具體的偏差程度，偏差程度由多個偏差度組成。由于在實際的揀貨過程中不一定或者一般都不是單一的某一種貨物的揀貨，而是多種貨物或者多訂單一起的揀貨。在這種情況下可將偏離度定義為多路徑下出發(fā)點與目的地點多個偏離度的和?，F(xiàn)假設(shè)在一次貨物的揀貨過程中共有I種貨物需要揀貨

4、，那么實際的偏離度為這I種偏離度之和，假設(shè)該倉庫系統(tǒng)有K個縱向的通道，那么在每一種貨物的揀貨過程中其偏離度的計算為幾個通道路徑之和，可以通過權(quán)重系數(shù)以及每種貨物在第i個通道距離出口點的距離來計算。其中該入口可以是從前向通道進入，也可以是從后向的通道進入。那么綜合的偏離度可由所有偏離度綜合計算得出。由于是多路徑的計算，那么在實際的路徑選擇中就會出現(xiàn)若干個不同的偏離度，假設(shè)路徑為m條，那么就會出現(xiàn)相應(yīng)的多個不同的偏離度。最后可以通過比較多個不同的偏離度來計算最優(yōu)路徑。偏離度示意圖如圖2所示。2.2 偏離度下的路徑優(yōu)化原理在S形啟發(fā)方式揀貨的基礎(chǔ)上，基于偏離度下的路徑優(yōu)化原理實際上是利用了計算機的強

5、大計算能力，假設(shè)本次揀貨有若干個種類，那么該算法會對每種貨物的偏離度進行計算，然后計算出總的偏離度。因為倉儲人員揀貨方式的種類是可以遍歷的，也就是倉儲人員對這若干種貨物進行揀貨，當貨物揀貨完畢并且回到原始地點的時候，那么其所經(jīng)歷的路徑雖然是多種多樣的，但是對于計算機來講這是可以窮盡的。計算機通過計算每一條路徑的偏離度得到這若干種物品的一個綜合偏離度，然后對比若干種路徑的偏離度，最小的偏離度所對應(yīng)的路徑就是倉儲人員取貨所應(yīng)該走的路徑。揀貨通道的示意圖如圖3所示。圖4為基于偏離度原理的路徑優(yōu)化圖，圖中黑色的小方塊為待揀貨的貨物，由起始點指向各個貨物存儲的點的箭頭描述了各種貨物當前的偏離度，但是由于

6、路徑的不唯一造成了偏離度的不唯一，也就是說圖中每個物體的偏離度都不是唯一的，而是都具有多個偏離度。如果倉儲人員要選擇最短的路徑即最小偏離度的路徑，就要首先通過計算機計算出倉儲人員可能走的每一條路徑的綜合偏離度，然后根據(jù)綜合的偏離度的大小來確定到底該選擇哪一條路徑。2. 3 偏離度下路徑優(yōu)化方法的判斷方法偏離度下路徑優(yōu)化的判斷方法就是首先根據(jù)此次所揀貨物種類的不同，通過計算機對倉儲人員所有走過的路徑進行計算并進行存儲。確定了每一條路徑之后，計算每一條路徑針對每一個物品的偏離度，然后再計算該路徑下所有待揀貨物的綜合偏離度，最后每一條路徑都會得到一個綜合的偏離度。在這些偏離度所對應(yīng)的路徑當中，最小偏

7、離度對應(yīng)的路徑便是該算法下應(yīng)該優(yōu)先選擇的路徑。（1）最后一個揀貨點是k通道在計算出每條路徑所對應(yīng)的偏離度之后，每個偏離度所對應(yīng)的路徑也就確定了，那么倉儲人員所應(yīng)該走過的路徑也就是確定的，圖5為經(jīng)過計算后倉儲人員經(jīng)過最后k通道的路徑示意圖。（2）最后一個揀貨點不是k通道在另外的一個試驗中，還是利用隨機數(shù)的形式讓若干個貨物隨機分布在倉庫的各個位置，將其種類以及其相應(yīng)種類位于哪個通道都記錄到計算機當中，并針對若干種貨物的分布以及倉庫通道的分布計算所有倉儲人員可能走過的路徑，并將其存儲起來。最后計算每條路徑上所有物品的綜合偏離度，選取最小的偏離度所對應(yīng)的路徑就是要選擇的路徑。在該實驗中倉庫的路徑分布以

8、及貨物的分布如圖6所示，得到的最佳路徑在圖中已經(jīng)標出。可以看出在這個試驗中該算法的最后一個揀貨點不是k通道而是k-1通道。3、仿真數(shù)據(jù)結(jié)果的比較分析假設(shè)針對圖1中所模擬的倉庫，利用S 形啟發(fā)式方法計算出倉儲人員從進入倉庫到揀貨完成所需要的路徑，然后根據(jù)揀貨點的不同分別計算出多個不同的揀貨點所對應(yīng)的S形啟發(fā)方式下的路徑。再根據(jù)偏離度的路徑優(yōu)化方法計算最優(yōu)路徑。經(jīng)仿真10 次求平均值繪制出表1.以隨機揀貨點的數(shù)量為橫坐標，以這兩種方法優(yōu)化計算所得出的對應(yīng)于特定數(shù)量的隨機揀貨點的路徑作為豎坐標，分別取15對點就可以在同一坐標系中繪制出兩條具有類似意義的折線，其中一條折線代表S 形啟發(fā)式方法所得到的隨機的揀貨點與揀貨路徑之間的關(guān)系。另一條