運(yùn)用蟻群算法解決物流中心揀貨路徑問題

熊芳敏, 岑宇森, 曾碧卿

( 1. 華南師范大學(xué)南海校區(qū)計(jì)算機(jī)工程系，廣東佛山 528225；2. 廣東肇慶學(xué)院計(jì)算機(jī)學(xué)院，廣東肇慶 526061)

運(yùn)用蟻群算法解決物流中心揀貨路徑問題

熊芳敏1, 岑宇森2, 曾碧卿1

( 1. 華南師范大學(xué)南海校區(qū)計(jì)算機(jī)工程系，廣東佛山 528225；2. 廣東肇慶學(xué)院計(jì)算機(jī)學(xué)院，廣東肇慶 526061)

研究了運(yùn)用蟻群優(yōu)化算法解決物流中心揀貨路徑問題，并與傳統(tǒng)的基于穿越策略的揀貨路徑策略做比較．執(zhí)行結(jié)果顯示以蟻群優(yōu)化算法解決物流中心倉儲(chǔ)揀貨作業(yè)，可明顯減少揀貨路徑的距離及揀貨時(shí)間，提高物流中心的作業(yè)效率與服務(wù)水平．

蟻群算法； 物流； 揀貨路徑； 優(yōu)化

在物流中心的各項(xiàng)內(nèi)部作業(yè)中，揀貨作業(yè)是一項(xiàng)重要且繁雜的工作．揀貨是將顧客訂單上不同種類的產(chǎn)品予以分類，再依據(jù)產(chǎn)品的數(shù)量將產(chǎn)品從貨架上取出．揀貨員在揀貨作業(yè)的過程中，由于采用不同的揀貨路徑策略，造成揀貨順序與行走路徑有所差異，進(jìn)而影響揀貨路徑的距離和揀貨效率．最為常用的揀貨策略是穿越策略．

所謂穿越策略是揀貨員揀貨時(shí)，從走道一端進(jìn)入，另一端離開．當(dāng)走道較窄時(shí)，揀貨人員可同時(shí)揀取走道兩側(cè)貨架上的商品．反之，如果走道較寬時(shí)，則揀貨人員就必須橫跨走道，如圖1所示．因?yàn)樗?jīng)過路徑的軌跡類似“Z”字型，所以也稱為“Z型穿越策略”．

圖1 穿越策略路線圖Fig.1 Z-traversal strategy

由于穿越策略沒有對(duì)倉庫內(nèi)的具體結(jié)構(gòu)和貨物擺放特點(diǎn)做出分析，所以揀貨員所走的路徑往往不是最短路徑和最省時(shí)間[1-3]．而對(duì)于物流中心，能否在合理的時(shí)間內(nèi)完成揀貨作業(yè)，直接關(guān)系著物流中心的經(jīng)營成本與服務(wù)質(zhì)量．本文分析物流中心傳統(tǒng)倉儲(chǔ)中的揀貨路徑問題，并建立適當(dāng)?shù)臄?shù)學(xué)模型，然后利用蟻群優(yōu)化算法尋找最優(yōu)揀貨路徑，以縮短揀貨路徑距離及減少揀貨作業(yè)時(shí)間，從而提高物流中心的作業(yè)效率與服務(wù)水平．

1 蟻群算法模型及描述

蟻群優(yōu)化算法(Ant Colony Optimization,ACO)是20世紀(jì)90年代由意大利學(xué)者M(jìn).Dorigo、V.Maniezzo、A.Colorini等人通過模擬自然界螞蟻覓食行為提出的一種全新的模擬進(jìn)化算法．螞蟻在覓食過程中，會(huì)依據(jù)一定的模式來選擇行走的路徑，并且會(huì)在走過的路徑上留下獨(dú)特的信息素，以利用信息素去尋找食物以及往來巢穴的路徑．如圖2所示，假設(shè)當(dāng)螞蟻有2條以上的直線路徑可選擇時(shí)，每條路徑起初被選擇的概率是相等的，如圖2(A)．若中間出現(xiàn)障礙物時(shí)(如圖2(B)所示)，由于螞蟻必須在障礙物兩側(cè)的路徑做選擇，選擇較短路徑的螞蟻(如圖2(C)所示)，在外出尋找食物到回巢的時(shí)間一定少于選擇另一較長路徑的螞蟻所花費(fèi)的時(shí)間．因此，較短路徑上遺留的信息素也會(huì)比較多，而下一批要出發(fā)的螞蟻則會(huì)選擇擁有較多信息素的路徑行走．此過程持續(xù)循環(huán)，則螞蟻都會(huì)趨向于行走相同的較短路徑．反之，另一路徑上的信息素則會(huì)慢慢蒸發(fā)不見，導(dǎo)致被選擇的概率越來越?。鶕?jù)此原理所發(fā)展出求解最優(yōu)路徑的算法，稱為蟻群優(yōu)化算法[4-5]．

圖2 螞蟻覓食原理圖Fig.2 Ant foraging chart

假設(shè)現(xiàn)在有m只螞蟻要尋找經(jīng)過n個(gè)節(jié)點(diǎn)的最短路徑，蟻群優(yōu)化算法的流程可以描述如下[4-5]：

步驟1：將m只螞蟻隨機(jī)放在n個(gè)節(jié)點(diǎn)上(m≥n)．

步驟2：建立禁忌列表(tabu list)存放螞蟻?zhàn)哌^的節(jié)點(diǎn)[6]．

步驟3：每只螞蟻?zhàn)叩较乱粋€(gè)節(jié)點(diǎn)的概率是隨機(jī)選擇的，并且將所走的節(jié)點(diǎn)記錄在禁忌列表中，重復(fù)此步驟，直到禁忌列表填滿為止．螞蟻隨機(jī)選取的概率公式為：

(1)

步驟4：根據(jù)禁忌表計(jì)算每只螞蟻所走的路線長度，并且記錄到目前為止所走的最短路徑，然后根據(jù)式(2)和式(3)計(jì)算每只螞蟻在每條路徑上所遺留的信息素．

(2)

(3)

步驟5：根據(jù)式(4)更新所有路徑上的信息素?cái)?shù)量，同時(shí)更新時(shí)間點(diǎn)t為t+n．

ij(t+n)=ρ·ij(t)+Δij,

(4)

步驟6：如果尚未到達(dá)停止條件，則將所有禁忌表清空，并且重復(fù)步驟2至步驟6，直到滿足停止條件為止．

2 應(yīng)用蟻群優(yōu)化算法解決訂單揀貨路徑問題架構(gòu)

本文利用蟻群優(yōu)化算法解決物流中心倉儲(chǔ)的訂單揀貨路徑問題，具體架構(gòu)如圖3所示．首先，收集物流中心所存儲(chǔ)的商品的基本信息(如：商品體積、商品編號(hào)、商品名稱及商品代號(hào)等)，并將商品安排在適當(dāng)?shù)拇鎯?chǔ)位置；接著，按照客戶訂單信息(如：商品數(shù)量、訂單號(hào)碼、商品名稱及商品代號(hào)等)，計(jì)算每筆訂單的總體體積，在依據(jù)揀貨車載運(yùn)商品的體積限制，依照訂單的接單次序依次將訂單劃分為若干揀貨批次；最后，利用蟻群優(yōu)化算法，配合揀貨批次的信息(如商品編號(hào)及存儲(chǔ)位置坐標(biāo)等)，獲得該批次商品的最佳揀貨路徑．

圖3 應(yīng)用蟻群優(yōu)化算法解決訂單揀貨路徑問題架構(gòu)

Fig.3 Structure of applying ACO to solve order form picking

3 實(shí)驗(yàn)過程與結(jié)果分析

本文與某大型食品物流中心合作，進(jìn)行實(shí)例探討．該物流中心在每天晚上固定時(shí)間停止接收客戶訂單，并依照顧客訂單揀貨需求，使用穿越策略進(jìn)行揀貨作業(yè)，實(shí)現(xiàn)商品在次日送達(dá)顧客手中．

3.1收集倉儲(chǔ)基本資料

本文從物流中心收集的數(shù)據(jù)分為2類：

(1)商品資料：商品編號(hào)排序、商品名稱、商品代號(hào)、體積．

(2)訂單資料：訂單日期、訂單編號(hào)、商品名稱、商品代號(hào)、商品數(shù)量．

3.2建立商品存儲(chǔ)位置

此物流中心的倉儲(chǔ)布署為無中間走道的長條式儲(chǔ)位，為了改善揀貨效率及突出本文所提算法的優(yōu)越性，經(jīng)過與該物流中心主管討論并確認(rèn)其可行性后，修改了其原始倉儲(chǔ)設(shè)計(jì)，在倉儲(chǔ)儲(chǔ)位中增加一條寬度為二公尺的穿越走道，而商品儲(chǔ)位位置安排則是按照商品編號(hào)依序排列．

3.3訂單分批

建立商品存儲(chǔ)位置后，按照顧客訂單及商品體積資料，計(jì)算每一筆訂單商品的總體體積，接著，依據(jù)訂單的先后順序，在滿足揀貨車體積承載的限制下，完成所有顧客訂單的分批工作．籍此，即可得知每個(gè)揀貨批次所需揀取商品及其存儲(chǔ)位置．本文以2009年3月1日訂單為例，其訂單分批完成后的第一筆揀貨單資料如表1所示．

表1 2009年3月1日的第一筆揀貨單資料Tab.1 The first picking order form on Mar. 1, 2009

3.4求解揀貨路徑

本文使用C++語言編譯蟻群優(yōu)化算法，并依據(jù)訂單分批后的揀貨單資料求解最優(yōu)揀貨路徑，其中蟻群優(yōu)化算法的參數(shù)設(shè)定如表2所示．

表2 蟻群優(yōu)化算法參數(shù)設(shè)定值Tab.2 enact parameters value of ACO

表2中的參數(shù)是根據(jù)以往學(xué)者提出的蟻群算法參數(shù)優(yōu)化設(shè)置的策略所得[6-8]．

以2009年3月1日的訂單批次結(jié)果為例，針對(duì)每一筆揀貨單，利用蟻群優(yōu)化算法重復(fù)求解10次的執(zhí)行結(jié)果，如表3所示．

3.5結(jié)果比較與分析

該物流中心原本是采用穿越策略進(jìn)行揀貨作業(yè)，以2009年3月1日的訂單為例，比較以蟻群優(yōu)化算法及穿越策略所獲得的揀貨路徑，整理如表4所示．

根據(jù)表4可知，相對(duì)于傳統(tǒng)的穿越策略，運(yùn)用蟻群優(yōu)化算法求解揀貨路徑問題可以有效地減少揀貨距離．以第一筆揀貨單為例，以穿越策略及利用蟻群優(yōu)化算法所獲得的揀貨路徑如圖4所示．

表3蟻群優(yōu)化算法求解揀貨路徑結(jié)果整理(以2009年3月1日的訂單批次為例)

Tab.3 Results of using ACO to solve order picking route problem (e.g. order forms on Mar. 1, 2009)

揀貨單編號(hào)平均揀貨距離/m最大揀貨距離/m最小揀貨距離/m揀貨距離標(biāo)準(zhǔn)差/m平均CPU時(shí)間/s18208298125.38.329389389380.066.2310481061102710.880.849709759692.2102.5599810059857.481.5

表4傳統(tǒng)穿越策略與蟻群優(yōu)化算法的揀貨路徑結(jié)果比較

Tab.4 Comparisons between traditional Z-traversal strategy and ACO on picking route

揀貨單編號(hào)以穿越策略的揀貨距離/m以蟻群算法獲得的揀貨路徑平均距離/m平均改善距離/m平均改善百分比/%11083820262.924.2821322938384.029.05316471048595.036.2141529970559.036.5651691998693.040.98

由圖4可知，應(yīng)用傳統(tǒng)穿越策略揀貨時(shí)，需要從走道一端進(jìn)入再從走道另一端離開，以揀取該走道的所有待取商品，接著，再揀取下一個(gè)走道的商品，因此，在揀貨上將會(huì)繞行多余的路程[2-3]．相反，蟻群優(yōu)化算法所獲取的揀貨路徑有數(shù)個(gè)回轉(zhuǎn)點(diǎn)，故能籍此縮短揀貨的路徑距離．

圖4 蟻群優(yōu)化算法及穿越策略所獲得的揀貨路徑圖Fig.4 Picking route chart achieved by ACO and traversing strategy

仿照前述方式，本文將2009年3月2日—7日的訂單進(jìn)行批次后，利用蟻群優(yōu)化算法所獲得的最佳揀貨路徑，其相對(duì)于傳統(tǒng)的穿越策略在揀貨距離上的改善結(jié)果整理如表5所示．

依據(jù)表5可知，對(duì)于每日的訂單而言，蟻群優(yōu)化算法皆可有效減少揀貨距離，而且大部分的揀貨距離改善平均可以達(dá)到20%以上，其中以改善30%～40%的居多．此外，蟻群算法的CPU執(zhí)行時(shí)間平均大約為3 min，即使是最長的執(zhí)行時(shí)間也不會(huì)超過5 min．若以目前該物流中心每天最多的60車次來計(jì)算，也只需要花費(fèi)5 h的CPU運(yùn)算時(shí)間即可獲得最佳路徑．而該物流中心的作業(yè)方式為每日晚間7點(diǎn)截止收單，并于凌晨2點(diǎn)開始揀貨．因此，根據(jù)揀貨路徑的改善結(jié)果以及算法所耗費(fèi)的CPU時(shí)間，對(duì)于該物流中心而言，本文所提出的利用蟻群優(yōu)化算法解決倉儲(chǔ)的訂單揀貨路徑的方法，是行之有效的．

表5 揀貨距離改善統(tǒng)計(jì)表Tab.5 Improving picking distance statistic table

4 結(jié)論

本文研究透過蟻群優(yōu)化算法求解物流中心倉儲(chǔ)中的最佳揀貨路徑，以節(jié)省更多的揀貨路徑與時(shí)間．根據(jù)實(shí)例探討的結(jié)果可知，蟻群優(yōu)化算法所獲得的揀貨路徑明確優(yōu)于傳統(tǒng)的穿越策略揀貨路徑，且蟻群優(yōu)化算法的每次CPU執(zhí)行時(shí)間最多不超過5 min．因此，物流中心有充裕的時(shí)間整理訂單、分批、執(zhí)行蟻群優(yōu)化算法程序，并將程序執(zhí)行結(jié)果交由揀貨員進(jìn)行揀貨，籍此可明顯減少揀貨員揀貨時(shí)間與行走路徑長度．因此，本文認(rèn)為，將蟻群優(yōu)化算法應(yīng)用在物流中心的倉儲(chǔ)揀貨作業(yè)上是一種有效且可行的方法．

[1] 彭本紅, 鄧謹(jǐn).第三方物流合作伙伴關(guān)系的競爭協(xié)調(diào)模型和治理模式探討[J].商業(yè)研究,2006(21):114-117.

PENG Benhong,DENG Jing. Competition-coordination mode and governance pattern in third-party logistics partnership[J]. Commercial Research,2006(21):114-117.

[2] 雷宣云,葉飛,楊立洪.不完全信息條件下的虛擬企業(yè)合作伙伴選擇模型[J].工業(yè)工程,2005,8(4):63-65;69.

LEI Xuanyun,YE Fei, YANG Lihong. Parthers selection model for virtual enterprises under the conditions of imperfect information[J]. Industrial Engineering Journal,2005,8(4):63-65;69.

[3] 李紹新,張延?jì)? 改進(jìn)的遺傳算法在蛋白質(zhì)結(jié)構(gòu)預(yù)測中的應(yīng)用[J]. 華南師范大學(xué)學(xué)報(bào):自然科學(xué)版,2009(1): 56-60.

LI Shaoxin, ZHANG Yanjiao. The application of improved genetic algorithms for predicting protein structures[J]. Journal of South China Normal University:Natural Science Edition, 2009(1): 56-60.

[4] DORIGO M,MANIEZZO V, COLORNI A. Ant system:opti-mization by a colony of cooperating agents [J]. IEEE Transactions on Systems, Man and Cybernetics-Part B, 1996, 26(1):28-41.

[5] BEKTAS T. The multiple traveling salesman problem[J]. An Overview of Formulations and Solution Procedures, 2006,34(33)：209-219.

[6] 黃美玲,白似雪.蟻群神經(jīng)網(wǎng)絡(luò)在旅行商問題中的應(yīng)用[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2007, 19(5): 600-603.

HUANG Meiling,BAI Sixue. Application research for TSP based on neural Network-Ant colony algorithm[J]. Journal of Computer-Aided Design and Computer Graphics, 2007,19(5):600-603.

[7] 蔣玲艷,張軍,鐘樹鴻.蟻群算法的參數(shù)分析[J].計(jì)算機(jī)工程與應(yīng)用,2007,43 (20):31-36.

JIANG Lingyan,ZHANG Jun, ZHONG Shuhong. Analysis of parameters in ant colony system[J]. Computer Engineering and Applications,2007,43 (20):31-36.

[8] 劉利強(qiáng),戴運(yùn)桃,王麗華.蟻群算法參數(shù)優(yōu)化[J].計(jì)算機(jī)工程,2008,34(11):208-210.

LIU Liqiang,DAI Yuntao,WANG Lihua. Ant colony algorithm parameters optimization[J]. Computer Engineering, 2008,34(11):208-210.

Keywords： ant colony optimization algorithm; logistics; order picking tour; optimization

【責(zé)任編輯 莊曉瓊】

RESOLVINGORDERPICKINGTOURPROBLEMSINTHEDISTRIBUTIONCENTERTHROUGHANTCOLONYOPTIMIZATIONALGORITHM

XIONG Fangmin1, Cen Yusen2, ZENG Biqing1

(1.Department of Computer and Engineering, School of Naihai, South China Normal University, Foshan, Guangdong 528225, China; 2.School of Computer Science, Zhaoqing University, Zhaoqing, Guangdong 526061, China)

The order picking problems in a warehouse of the distribution center through ant colony optimization algorithm (ACO) is studied, which is compared with the traditional picking tours based on the Z-traversal strategy. The results reveal that the ACO can reduce both the picking tour distances and the operation time significantly, thus the operation efficiency and service quality can be improved in a traditional warehouse of the distribution center.

2009-09-17

廣東省自然科學(xué)基金資助項(xiàng)目 (8151063101000040)

熊芳敏(1979—),女,廣東梅州人, 華南師范大學(xué)南海校區(qū)講師，主要研究方向：系統(tǒng)智能和軟件工程，Email:xfangmin@126.com.

1000-5463(2010)02-0050-05

TP391

A