蟻群算法在揀貨路徑優化中的應用研究

摘要：揀貨路徑優化問題在提高物流中心效率中具有重要的作用。為獲得揀貨路徑的近似最優解蟻群算法被應用于固定貨架揀貨路徑的優化問題，依據蟻群算法的數學模型，設計了適用于固定貨架揀貨路徑的蟻群算法運算步驟，由試驗驗證了算法的有效性。

關鍵詞：蟻群算法；揀貨路徑；固定貨架

中圖分類號：TP182文獻標識碼：A文章編號：1009-3044(2008)29-0466-02

Ant Colony Algorithm Applies to the Optimization of Order-picking Routing Problem

YU Jie1， SU Zhi-zhong2， SUN Yan-fei1

(1.Information Technology Department，Zibo Vocational College，Zibo 255000，China;2.Post-graduate Department，Shanghai University of Technology，Shanghai 200093，China)

Abstract: The optimization of order-picking routing problem in raising the efficiency of logistics centre has an important role. Order-picking routing in order to obtain the approximate optimal solution ant colony algorithm is used in fixed shelf picking routing optimization problem. Based on the mathematical model， the computing steps of the ant colony algorithm are designed for fixed shelf order-picking routing. The validation of the algorithm is obtained using the test.

Key words: ant colony algorithm; order-picking routing; fixed shelf

1 引言

現今的企業競爭環境日益激烈與復雜，傳統的大批量少品種流通模式越來越不能滿足當前市場多品種小批量的需求，企業為了提高在市場上的競爭優勢，在無法通過提高售價來實現高額利潤時，只能以降低自己的運作成本增加利潤來提高企業的競爭力。對大多數企業而言，物流成本占商品最終售價的比重僅次于產品的生產成本，一些商業或流通企業紛紛準備或開始籌建自己的配送中心，以求降低成本，提高客戶服務質量和水平。

在企業物流環節所涵蓋的作業范圍里，訂單的揀取過程是配送中心中所有作業中最費力的，其勞動量占配送中心中所有作業量的60%[1]。尤其是在配送時限要求越來越短的配送中心，揀取活動通常要在有限的時間內完成，從而導致配載和訂單揀取的難度大大增加。在自動化程度不高的揀貨活動中經常遇到這樣一個問題：揀貨員常因揀貨路徑不明，致使揀貨人員或搬運設備行走搬運的距離過長，導致揀貨效率不高。因此采用科學合理的方法優化揀貨路徑是物流配送業務中非常重要的一項工作。

揀貨路徑優化問題作為一個NP（Nondeterministic Polynomia1）難題，很難找到此問題的精確解。對這類問題的解可以通過啟發式算法來求解，比如蟻群算法[2-3]、貪婪算法[4]等。蟻群算法是通過模擬自然界蟻群從巢穴到食物源的最短路徑的覓食過程來求解一些NP難題的。它具有正反饋、并行計算、較強的魯棒性等諸多特點，在很多領域有著廣泛的應用。本文將蟻群算法應用于揀貨路徑優化問題中并由試驗驗證了算法的有效性。

2 基本蟻群算法的數學模型

蟻群算法ACA（Ant Colony Algorithm）源于對自然界螞蟻尋找從蟻巢到食物的最短路徑并找到回巢路徑方法的研究。螞蟻在覓食的過程中，在走過的路徑下留下一種稱之為信息素（pheromone）的物質，其它螞蟻就是靠這種信息素的指引往返于食物源與巢穴之間，各條路徑上的信息素都會隨著時間的遷移而不斷蒸發減少，但某條路徑上走過的螞蟻越多，則路徑上殘留的信息素強度就越高。螞蟻在運動的過程中總是傾向朝信息素強度高的方向移動。因此，由大量螞蟻組成的集體行為便表現出一種信息正反饋現象:當幾只螞蟻分別沿著不同的路徑回巢，長度越短的路徑上信息素的強度越高，其它螞蟻選擇這樣路徑的概率也越大，路徑上的信息素強度也會更高，使更多的螞蟻集中到最短的路徑上來。蟻群算法就是模擬上述螞蟻覓食行為，設計虛擬的螞蟻，使其隨機搜索不同的路徑，并留下會隨時間變化而蒸發的“信息素”，根據“信息素”強度來尋找最短路徑。

以求解平面上N個城市的TSP問題為例來說明蟻群系統模型。旅行商問題（TSP）是指對于給定的n個城市以及各城市之間的距離，求出經過每個頂點一次且僅一次并使總距離最小的路徑。假設m是蟻群中螞蟻的數量個數，n代表城市的個數，di，j代表城市i，j之間的距離，i，j=0，1，2……n-1，τi，j (t)表示t時刻路徑(i，j)上的信息素數量，i，j=0，1，……，n-1。初始時刻，各條路徑上的信息素數量相等，設τi，j (t) =C (C 為常數)。螞蟻在運動過程中，會根據各條路徑上的信息量決定移動方向，Pi，j k(t)時刻螞蟻k由城市i轉向城市j的概率

其中公式(1)中ηi，j(t)=1/di，j表示t時刻的能見度，反映由城市i到城市j的啟發程度，α和β兩個權重參數來控制信息素和啟發式的值。Allowedk={0，1，......，n-1}- tabuk表示螞蟻k允許訪問的下一個城市，tabuk為禁忌表，記錄螞蟻k曾走過的城市，下次訪問時將禁止從禁忌表中選擇城市。

所有的螞蟻都循環完一遍后，螞蟻在它每一條訪問的路上留下信息素。信息素根據下式調整：

Lk為螞蟻k本次搜索到的路徑長度。

(2)式中ρ∈(0，1)——表示信息的揮發程度，初始時刻τi，j (0)是1個常數；式(3)表示本次循環中城市i到城市j上信息素的增量。

經過1個時刻，螞蟻k完成一次搜索，找到一條路徑后回到起始點，為下一次迭代做準備。此時進行局部調整，調整螞蟻了k所經過的路徑上的信息素值，調整方式按(3)式進行。經過n個時刻，當n1只螞蟻全部完成搜索后，按(4)式對路徑上的信息素進行全局更新，增加最短路徑上的信息素值，使下次搜索可以更關注最短路徑。

在公式(1)到(4)里面有很多常數，包括α， β， ρ，C， Q。由于這種基本蟻群算法很多學者對此有了很多的研究，通常取a= 1， β=5， ρ= 0.5，效果是比較理想的，而C， Q的取值對于結果沒有什么影響，所以在這里取C=1，Q=100。算法循環停止條件是固定的循環次數或者是進化的趨勢不明顯。

3 蟻群算法應用于固定貨架揀選問題

假設需要取n-1個貨柜的貨物，揀選機從起始點開始出發，需要經過這n-1個節點取出貨物，最后回到起始點。這樣把起始點考慮在內共有n個地址需要揀選機走過。下面定義n個節點的坐標，Ni (Xi，Yi )(i，j=0，1，2，……n-1)。Xi表示固定貨架的列地址，Yi表示固定貨架的層地址。其中Xo= O， Yo = 0。下面開始描述運算的步驟:

step1：初始化所有參數：α， β， ρ，C， Q，設有m個螞蟻，令m=n(城市的個數)，然后將這n個螞蟻分別放在n個節點(也就是貨柜處)上作為各自螞蟻的起始位置；

Step2：得到各揀選點之間的距離di，j，同時計算ηi，j(t)=1/di，j；將△τi，j (0)=0，τi，j (0)=C (i， j=0， 1， 2，… n-1)；

Step3：開始迭代，次數為CN；

Step4：for (int k=0; k

利用公式(1)計算選擇下一個城市的概率大小，隨機的選擇每一個螞蟻下一個城市的地址，把城市加入各自螞蟻的城市tabuk，若tabuk未滿則繼續搜索，直到一條路徑搜索完畢，回到起始點。根據公式(2)(3)更新:τi，j (t+1)和△τi，j(t) 的值。

Step5：記錄本次最短路徑，置空tabuk，若迭代次數

Step6：從CN個最優路徑和結果里面找到一個最短的路徑作為最終結果；

Step7：輸出最佳路徑。

4 蟻群算法試驗

基于上述算法利用matlab7.0編程，完成了以下實例：以一個固定貨架為例，該固定貨架橫向貨柜格數為60，縱向貨柜層數為30，貨格的長度跟高度相同，都為1米。堆垛機的起始坐標是P0 (0，0)(第0列、第0層)，需要揀選的貨物數量是10個，坐標位置各自為P1(3，2)，P2(6，8)，P3(8，15)，P4(15，21)，P5(23，11)，P6(19，22)，P7(40，9)，P8(33，18)，P9(37，16)，P10(50，30)。起始點與各揀貨點之間的距離如下表所示:

從上表得出平均最優解是91.052，最優解90.168。最終的物流優化路徑順序是P1，P2，P3，P4，P6，P5，P8，P9，P7，P10。

通過此表，我們可以得到以下結論:基本蟻群算法在迭代代數為200代以上時候結果沒有太大的變化，隨著迭代次數的增高，需要運算的時間太長，整體運算時間太慢，實時性差。綜合考慮我們可以選取迭代次數在200代的路徑長度作為最優解。

5 結束語

蟻群算法是一種解決組合優化問題的有效算法，本文中將蟻群算法應用于揀貨路徑的優化中，有效提高了揀貨的效率。但是基本蟻群算法在解決大規模(n>30)的旅行商問題時，性能會迅速惡化，主要原因是算法的初始階段信息素的值相等，螞蟻的搜索出現很強的盲目性，使得運算速度比較慢。另外，由于蟻群算法是一種正反饋算法，在算法速度收斂較快，容易陷入局部最優。基于此可考慮先用其他的算法獲取初始種群，然后再用蟻群算法求解，如此將會提高固定貨架揀選路徑優化的運算速度，增強其實時性，使其更具有實用價值。

參考文獻：

[1] 李詩珍，李莉，杜文宏.配送中心單品揀貨模式及其效能分析[J].包裝工程，2006(26):221-224.

[2] Mazzeo S，Loiseau I.An ant colony algorithm for the capacitated vehicle routing[J].Electronic Notes in Discrete Mathematics，2004(18):181-186.

[3] 吳慶洪，張紀會，徐心和.具有變異特征的蟻群算法[J].計算機研究與發展，1999，36(10):1240-1243.

[4] 嚴太山.用基于貪婪算法的混合遺傳算法求解0/1背包問題[J].現代計算機，2007(8):14-17.