基于改進蟻群算法的物流配送路徑優(yōu)化

1、基于改進蟻群算法的物流配送路徑優(yōu)化 項目基金：本文受國家重點基礎研究發(fā)展規(guī)劃（973）項目（2002CB312106）和浙江省重大科技攻關項目（2005C13023）支持童若鋒 作者簡介：童若鋒（1969.4-），男（漢族），浙江金華人，教授，博士，主要研究方向為CAD&CG等。E-mail：。 張維澤 許星 董金祥（浙江大學人工智能研究所，杭州 310027）摘要：本文建立了帶約束條件的物流配送問題的數(shù)學模型，運用蟻群算法解決物流配送路徑優(yōu)化問題，并將遺傳算法的復制、交叉、變異等遺傳算子引入蟻群算法，同時改進信息素的更新方式、客戶點選擇策略，以提高算法的收斂速度和全局搜索能力。經(jīng)過多次實驗和

2、計算，證明了用改進的蟻群算法優(yōu)化物流配送線路，可以有效而快速地求得問題的最優(yōu)解或近似最優(yōu)解。關鍵詞：物流配送；路徑優(yōu)化；蟻群算法；蟻群系統(tǒng)Optimizing Logistic Distribution Routing Problem Based on Improved Ant Colony AlgorithmRuoFeng Tong, Weize Zhang, Xing Xu, Jinxiang Dong(Institute of Artificial Intelligence, ZheJiang University, HangZhou 310027)Abstract: After con

3、structing the expressions of the constraints in logistic distribution and building the mathematical model, this paper proposes an improved ant colony algorithm to solve distribution problem. Several genetic operators such as crossover and mutation are inducted into the ant colony algorithm, and pher

4、omone updating strategy is ameliorated to improve the efficiency. The result of experiments demonstrates that the optimal or nearly optimal solutions to the logistic distribution routing can be quickly obtained by improved ant colony algorithm.Key words: logistic distribution; optimizing routing; an

5、t colony algorithm (ACA); ant system (AS)1 引言物流配送路徑優(yōu)化問題1是典型的組合優(yōu)化問題，屬于一類NP完全難問題，具有很高的計算復雜性。隨著市場經(jīng)濟的繁榮，物流配送業(yè)迅猛發(fā)展，越來越多的企業(yè)看到了物流配送在企業(yè)生產(chǎn)銷售流程中的重要作用。傳統(tǒng)的手工配送路線選擇完全是依靠勞動者的經(jīng)驗和智慧，需要耗費很多的時間和精力。隨著企業(yè)規(guī)模的逐漸壯大，業(yè)務規(guī)模也不斷擴大，配送網(wǎng)點的數(shù)量也逐漸增多，安排配送路線的復雜度越來越高，手工安排配送線路已經(jīng)很難滿足企業(yè)的業(yè)務需求，采用計算機進行路線安排勢在必行。求解配送路徑優(yōu)化問題的方法很多，常用的有旅行商法、動態(tài)規(guī)劃法、節(jié)約

6、法、掃描法、分區(qū)配送算法、方案評價法等。這些算法雖然能夠解決此類問題，但也存在一定的缺陷，節(jié)約法的組合點零亂、邊緣點難以組合的問題，掃描法非漸進優(yōu)化等2。如何針對物流配送路徑優(yōu)化問題的特點，構(gòu)造運算簡單、尋優(yōu)性能優(yōu)良的啟發(fā)式算法，是一個值得深入研究的課題。近年來遺傳算法、禁忌搜索算法3等都在此問題上進行了運用，并取得了成功2, 4, 5。但也存在各自的問題，如遺傳算法局部搜索能力不強，總體上可行解的質(zhì)量不是很高6，禁忌搜索算法對于初始解具有較強的依賴性3等等。目前研究的熱點是混合算法6, 7，通過混合在一定程度上彌補算法的缺陷。蟻群算法是受到人們對自然界中真實蟻群的集體行為的研究成果的啟發(fā)而在

7、近年來提出的一種基于種群的模擬進化算法，屬于隨機搜索算法，由意大利學者M. Dorigo8, 9等人首先提出。M. Dorigo等人首次提出該方法時，充分利用了蟻群搜索食物的過程與著名的旅行商問題（TSP）之間的相似性，通過人工模擬螞蟻搜索食物的過程（即通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑)來求解TSP。蟻群算法可用來解決各種不同的組合優(yōu)化問題，特別適合于在離散優(yōu)化問題的解空間進行多點非確定性搜索，如旅行商問題（TSP）、二次分配問題（QAP）、作業(yè)安排調(diào)度問題（JSP）等等；此外在通信網(wǎng)絡負載問題和水科學10等應用研究中也被廣泛應用。它具有通用性和魯棒性，是基于總

8、體優(yōu)化的方法。蟻群算法原型本身就是一個尋找最短路徑的模型，因此它在路徑優(yōu)化方面有著天然的優(yōu)勢，目前已經(jīng)有不少蟻群算法在TSP問題中成功運用的例子，如Ant-Q11、MMAS12等。物流配送路徑優(yōu)化問題和TSP問題相比有共同點都是尋找遍歷所有客戶點的最短路徑的問題，也有其特性有更多更復雜的約束條件和優(yōu)化目標。本文就是針對這種特點，研究一種基于蟻群算法的優(yōu)化路徑算法，通過引入遺傳算子，在局部搜索過程中能夠避免算法早熟、停滯，同時改進信息素的更新方式、客戶點選擇策略，增強蟻群算法的正反饋作用，從而提高收斂速度和全局搜索能力，使得其在物流配送路徑優(yōu)化問題中有較好的實際效果。2 物流配送的數(shù)學模型2.1

9、 問題的描述一般配送路徑問題可描述如下：有L個客戶點，已知每個客戶點的需求量及位置，至多用K輛汽車從配送中心到達這批需求點，并且在完成配送任務后，返回物流中心，每輛汽車載重量一定。要求安排車輛行駛線路使得運輸距離最短，且滿足以下幾個約束條件：1) 每條線路上的客戶點需求量之和不超過汽車載重量；2) 每條配送路徑的總長度不超過汽車一次配送的最大行駛距離；3) 每個客戶點的需求必須且只能由一輛汽車來完成。其目的是使總成本（如距離、時間等）為最小。2.2 數(shù)學模型的建立2.2.1 符號的定義L：客戶點總數(shù)；qi：客戶點i的貨物需求量，其中i=1，2，L；dij：從客戶點i到客戶點j的距離。特別的，當

10、i，j=0時，表示配送中心，例如：d0,3表示從配送中心到客戶點3的距離，d2,0表示從客戶點2到配送中心的距離。i，j=0，1，2，L；K：車輛的總數(shù)；Qk：車輛k的最大裝載量，其中k=1，2，K；Dk：車輛k的最大行駛距離，其中k=1，2，K；nk：車輛k配送的客戶總數(shù)，當nk=0時，表示車輛k沒有參與配送。k=1，2，K；Rk：車輛k配送的客戶點的集合。當nk=0時，Rk=；當nk0時，其中rki表示該客戶點在車輛k的配送線路中順序為i。k=1，2，K。2.2.2 約束條件根據(jù)前文對物流配送路徑優(yōu)化問題的描述，我們可以提取出以下幾個約束條件：1) 每條線路上的客戶點需求量之和不超過汽車載

11、重量：，nk02) 每條配送路徑的總長度不超過汽車一次配送的最大行駛距離：， nk03) 每個客戶點的需求必須且只能由一輛汽車來完成：，k1k24) 配送線路遍歷所有客戶點：2.2.3 優(yōu)化目標根據(jù)本文中物流配送路徑優(yōu)化問題的優(yōu)化目標，我們列出優(yōu)化目標的數(shù)學形式：3 優(yōu)化配送路線的蟻群算法3.1 基本蟻群算法蟻群算法是一種由于受自然界生物的行為啟發(fā)而產(chǎn)生的“自然”算法。它是從對蟻群行為的研究中產(chǎn)生的。蟻群中的螞蟻以“信息素”（pheromone）為媒介的間接的異步的聯(lián)系方式是蟻群算法的最大的特點。螞蟻在行動（尋找食物或者尋找回巢的路徑）中，會在它們經(jīng)過的地方留下一些化學物質(zhì)（我們稱之為“信息”

12、）。這些物質(zhì)能被同一蟻群中后來的螞蟻感受到，并作為一種信號影響后到者的行動（具體表現(xiàn)在后到的螞蟻選擇有這些物質(zhì)的路徑的可能性，比選擇沒有這些物質(zhì)的路徑的可能性大得多），而后到者留下的信息會對原有的信息素進行加強，并且如此循環(huán)下去。這樣，被越多螞蟻選擇的路徑，在后到螞蟻的選擇中被選中的可能性就越大（因為殘留的信息濃度較大的緣故）。由于在一定的時間內(nèi)，越短的路徑會被越多的螞蟻訪問，因而積累的信息量也就越多，在下一個時間內(nèi)被其他的螞蟻選中的可能性也就越大。這個過程會一直持續(xù)到所有的螞蟻都走最短的那一條路徑為止。我們用人工螞蟻代替車輛對客戶點進行配送，螞蟻在i客戶點選擇服務的下一個客戶點j時，主要考慮

13、兩個因素，一是i，j兩顧客點之間的關系的親密程度，稱為可見度，記為hij；另外考慮的是由迄今完成的循環(huán)所得路徑方案體現(xiàn)出來的由i到j的可行性，即信息素濃度tij。在t時刻螞蟻k由客戶點i轉(zhuǎn)移到客戶點j的概率：其中，allowedk=0,1,n-1-tabuk表示螞蟻k尚未服務的客戶點。可見度當下一個要服務的客戶點會使運載總量超出汽車載重量，或者使運距超過一次最大行駛距離時，就返回到配送中心，人工螞蟻代表下一輛車出發(fā)，繼續(xù)配送。當一次循環(huán)結(jié)束后，螞蟻遍歷了所有客戶點，完成一次配送。當所有螞蟻完成一次循環(huán)后，根據(jù)各螞蟻遍歷的好壞（目標函數(shù)值），計算信息素增量，更新相關路徑上的信息素，更新規(guī)則：3.

14、2 蟻群算法的改進3.2.1 遺傳算法對蟻群算法的改進遺傳算法的操作算子是遺傳算法的核心內(nèi)容，我們將復制、交叉、變異這些遺傳算子引入蟻群算法中，以提高算法的收斂速度和全局搜索能力。復制遺傳算法中，復制的主要思想是認為父代中的優(yōu)質(zhì)個體可能更接近全局最優(yōu)解，應該在子代中繼承并繼續(xù)進化。復制操作使得父代中優(yōu)質(zhì)的個體能夠在子代中得以保存，避免交叉變異等操作導致優(yōu)質(zhì)個體在種群中丟失。蟻群算法中，在每一代搜索完成后，我們將當前父代中最優(yōu)的解復制到子代中，使得最優(yōu)的個體能在子代中繼續(xù)積累信息素，這樣能加快算法的收斂速度。編碼遺傳算法中的交叉和變異操作是建立在基因編碼上的，因此在引入交叉和變異操作之前，我們首

15、先對物流配送模型進行編碼。假設有L個客戶點，K輛配送車輛，本文采用的編碼方式是將這L個客戶點分別用1到L這L個自然數(shù)標識；第一輛車從配送中心出發(fā)時用0標識，其他車輛則分別用L+1，L+2，L+K-1表示。由于同一輛車可以多次配送，所以，2次以上配送的車輛出發(fā)時，依次用L+K，L+K+1，表示。新的一輛車從配送點出發(fā)，或者編碼結(jié)束，就表示前一輛的路線結(jié)束，返回配送中心。這樣就將一次配送表示為一組由0和自然數(shù)組成的編碼。例如，有6個客戶點，我們分別用1至6表示，3輛車負責，那么編碼：0，1，2，3，7，4，5，8，6表示3輛車的配送線路分別是：車輛101230，車輛20450，車輛3060。又如編

16、碼：0，1，2，3，8，4，5，9，6表示的配送線路為：車輛101230，車輛30450，車輛1第二次配送060。交叉交叉操作是遺傳算法中增加種群多樣性，防止算法早熟、停滯的操作。在蟻群算法中引入交叉操作，可以有效地擴大搜索空間，避免算法陷入局部最優(yōu)解。在蟻群算法每一代搜索完成之后，我們將其中的最優(yōu)解和次優(yōu)解進行編碼交叉操作，交叉規(guī)則如下：1) 假設兩組編碼分別是S1和S2，首先隨機生成交叉段的長度和交叉段起始位置；2) 找出S1和S2中的交叉段，假設S1：P1|P2|P3，S2：Q1|Q2|Q3，P2和Q2分別是S1和S2的交叉段；將Q2插入S1中，位于P2前面，這樣形成新的編碼S3：P1|

17、Q2|P2|P3；3) 在S3中，刪除P1、P2、P3中與Q2重復的編碼。形成交叉編碼S3；4) 同樣的方法用在S2上，生成新的編碼S4；5) 比較S1、S2、S3、S4的結(jié)果，選出最優(yōu)的兩組編碼并保存。變異變異操作也是增加種群多樣性的一種進化手段。適度的變異，既能保持種群內(nèi)個體的多樣化，又能提高算法的效率。在蟻群算法中，我們在完成交叉操作后，對種群中最優(yōu)個體進行變異操作，操作方法為：1) 隨機生成變異次數(shù)N；2) 隨機生成兩個不同的自然數(shù)n1，n21（第一位不變，保證編碼以物流中心為起點）；3) 在最優(yōu)個體的編碼S中，將第n1位和第n2位的編碼對調(diào)；4) 重復2)、3)N次，生成新的編碼S；

18、3) 比較S和S的結(jié)果，保存較優(yōu)解。3.2.2 蟻群算法的其他改進策略在引入遺傳算法對蟻群算法進行改進后，算法的收斂速度和全局搜索能力得到了提高。我們下面還將從信息素的更新方式、客戶點選擇策略進行改進，以提高蟻群算法的自適應性。信息素傳遞參數(shù)r的選取按照基本蟻群算法，r是一個常量，如果r過大，則會使未搜索過的路徑被選擇的概率相對減小，影響全局搜索能力；而如果r過小，又會影響算法的收斂速度。因此我們在改進算法中將對r作適當調(diào)整。在算法初期，我們希望算法能盡快找到較優(yōu)解，因此r要比較大，增大信息濃度的影響，加快算法收斂速度；而當算法停滯不前時，我們要減小r，從而減小信息素對蟻群的影響，增大蟻群對解

19、空間的搜索，以脫離局部最優(yōu)解的束縛。4-1式中，r表示連續(xù)沒有進化的循環(huán)的次數(shù)，rmax是一個常量，l(0,1)是一個常量，控制r衰減速度，rmin是r的最小值，防止r過小影響收斂速度。當r達到預先設置的一個數(shù)值rmax時，我們就減小r，r重新計數(shù)，如此反復，直至r達到預設最小值rmin為止。確定性搜索和探索性搜索的選則加速收斂就是要在已得到的較優(yōu)解的基礎上，盡量快的進化，以得到更優(yōu)解。由于蟻群算法是一種啟發(fā)式算法，不斷地“探索”是蟻群算法進化的必要手段，而正是這種“探索”限制了蟻群算法收斂速度。例如，當算法得到一個較優(yōu)解，而且該解有可能進一步優(yōu)化，但由于“探索”范圍很大，使得螞蟻選擇該路徑的

20、概率相對減小，從而使得路徑上的信息量濃度逐漸衰減，該路徑也逐漸被“遺忘”了。為了解決這一問題，我們引入一個新的常量：q00,1)，螞蟻k在每次選擇路徑之前，先隨機產(chǎn)生一個q0,1)，螞蟻k選擇路徑s將根據(jù)下式： 式子中，當qq0時，是基本蟻群算法中的探索性搜索；當qq0時，是從已得的結(jié)果中，找出概率最大的路徑作為選擇，是對已得成果的“利用”，為確定性搜索。確定性搜索彌補了探索性搜索在收斂速度上受限制的缺陷，通過適當調(diào)整q0，能夠使得確定性搜索和探索性搜索合理搭配，加快蟻群算法的收斂速度。我們還要對q0的取值進行討論。當qq0時，算法是采用確定性搜索，此時螞蟻以概率q0選擇距離最短的路徑；當qq

21、0時，算法是采用探索性搜索，此時螞蟻以概率l- q0隨機選擇路徑。在算法迭代的初期q0選取較大的初始值，以較大的概率進行確定性搜索，這樣可以加快尋找局部較優(yōu)路徑的速度；在算法的中期q0選取較小的值，增大探索性搜索的概率，從而擴大搜索空間；在算法的后期，恢復q0的初始值，加快收斂的速度。結(jié)合改進后的蟻群算法，我們可以得到基于改進后蟻群算法的物流配送路徑優(yōu)化問題的算法流程圖：開始G=0，初始化信息C，設置進化代數(shù)G_MAX，對每只螞蟻初始化車輛序列G=G_MAX嗎隨機產(chǎn)生q0,1)tabu滿了嗎更新最佳路徑，清空tabu，G=G+1，更新q0，若連續(xù)未進化代數(shù)r=rmax，r=MAXlr，rmin

22、得到最優(yōu)路徑，輸出結(jié)果結(jié)束NYNY更新tabutabu=0嗎返回物流中心，選擇下一輛車YN對最優(yōu)解進行復制、交叉、變異qq0嗎確定性搜索探索性搜索NY圖1 算法流程圖4 實驗與計算文獻13運用改進的遺傳算法求解物流配送路徑優(yōu)化問題。我們就以該文獻中的例子進行計算比較。例 某配送中心用2輛汽車對8個客戶配送貨物。設汽車的載量為8,000kg，每次配送的最大行駛距離為40km。配送中心與客戶、客戶與客戶之間的距離如下表（0表示物流中心，18表示8個客戶點ID）：01234567800467.5920101681406.541057.51110266.507.510107.57.57.537.547

23、.501059915491010100107.57.5105205105100797.56107.57.597.570710716117.597.59701088107.515107.510100表1 配送中心、客戶之間距離（單位：km）客戶的需求如下表：客戶ID12345678需求量12121422表2 客戶貨物需求量（單位：噸）文獻13中，種群大小為50，迭代次數(shù)100次。以下是文獻13中給出的10次計算的平均結(jié)果為71.7km，僅有一次找到最優(yōu)解67.5km。用本文的蟻群算法，參數(shù)如下：蟻群共20只螞蟻，循環(huán)10代；a、b分別取1和2。10次計算均找到最優(yōu)解67.5km。我們再以文獻6和

24、文獻14中的例子進行實驗比較。例2 某物流中心有5輛配送車輛，車輛的最大載重量均為8T，一次配送的最大行駛距離均為50km，需要向20個客戶送貨。物流中心的坐標為（14.5km，13.0km），20個客戶的坐標及其貨物需求量見下表：IDx軸坐標（km）y軸坐標（km）需求量(T)IDx軸坐標（km）y軸坐標（km）需求量(T)112.88.50.1116.716.90.9218.43.40.41214.82.61.3315.416.61.2131.88.71.3418.915.21.51417.111.01.9515.511.60.8157.41.01.763.910.61.3160.22.8

25、1.1710.67.61.71711.919.81.588.68.40.61813.215.11.6912.52.11.2196.45.61.71013.85.20.4209.614.81.5表3 客戶位置坐標及貨物需求量我們計算10次的結(jié)果如下：次序12345678910總距離113.0109.6110.2111.7110.4111.2109.1109.6107.8110.4表4 計算結(jié)果及具體方案10次計算的平均結(jié)果110.3083km較文獻6的平均結(jié)果122.0km和文獻14的平均結(jié)果112.5km都有提高，而且最優(yōu)解107.84km，對應的具體方案為：04317112000819151

26、6136005142129107100180也較文獻14中的最優(yōu)解108.6km有了提高。本文的最優(yōu)結(jié)果圖示如下：圖25 結(jié)束語本文根據(jù)物流配送路徑優(yōu)化問題的特點，提出一種基于蟻群算法的優(yōu)化路徑算法。該算法通過引入遺傳算子，在局部搜索過程中能夠避免算法早熟、停滯，同時改進信息素的更新方式、客戶點選擇策略，增強蟻群算法的正反饋作用，從而提高了算法的收斂速度和全局搜索能力。實驗結(jié)果表明，改進后的蟻群算法可以快速有效地求得優(yōu)化物流配送路徑的最優(yōu)解或近似最優(yōu)解。本文的研究工作，對蟻群算法及物流配送路徑優(yōu)化問題的研究有一定的參考價值。參考文獻1Bernd Bullnheimer, Richaxd F H

27、artl, Christine strauss. An improved Ant System algorithm for the Vehicle Routing Problem J. Annals of Operations Researeh, 89(1999)319-328.2LANG Mao-xiang. Study of the optimizing of physical distribution routing problem based on genetic algorithm J. China Journal of Highway and Transport, 2002, 15

28、(3): 76-79. (in Chinese) 郎茂祥. 基于遺傳算法的物流配送路徑優(yōu)化問題研究J. 中國公路學報，2002,15(3)：76-79. 3XU Ning, LI Chun-guang, ZHANG Jian, et al. Studies on Some Modern Optimization Algorithms. SYSTEMS ENGINEERING AND ELECTRONICS. 2002 Vol.24 No.12: 101-104. 徐 寧，李春光，張健等. 幾種現(xiàn)代優(yōu)化算法的比較研究. 系統(tǒng)工程與電子技術， 2002年，第24卷第12期：101-104.4CHA

29、NG Yun-tao, PENG Guo-xiong. Urban arterial road coordinate control based on genetic algorithm J. Journal of Traffic and Transportation Engineering, 2003, 3(2):106-112. (in Chinese) 常云濤，彭國雄. 基于遺傳算法的城市干道協(xié)調(diào)控制J. 交通運輸工程學報，2003，3(2)：106-112.5LIN Yang, CAI Yuan-li, HUANG Yong-xuan. Dynamic origin-destinati

30、on matrix estimation for freeways J. Journal of Changan University (Natural Science Edition), 2003, 23(6): 83-86. (in Chinese) 林 勇，蔡遠利，黃永宣. 高速公路動態(tài)OD矩陣估計J. 長安大學學報(自然科學版)，2003，23(6)：83-86.6LANG Mao-xiang, HU Si-ji. Study on the Optimization of Physical Distribution Routing Problem by Using Hybrid Gene

31、tic Algorithm. CHINESE JOURNAL OF MANAGEMENT SCIENCE, 2002 Vol.10 No.5: 51-56. 郎茂祥、胡思繼，用混合遺傳算法求解物流配送路徑優(yōu)化問題的研究，中國管理科學，2002，10(10)：51-56.7Chen Haijun, Chen Tieyin. Application of Hybrid Genetic Algorithm in Vehicle Routing Problem. COMPUTER & DIGITAL ENGINEERING, 2005 Vol.33 No.4: 91-95. 陳海軍，陳鐵英. 混合遺傳

32、算法在路徑選擇問題的應用. 計算機與數(shù)字工程，第33卷（2005）第4期：91-958Marco Dorigo, Vittorio Maniezzo, Alberto Colnrni. Ant System: Optimization by a Colony of Cooperating Agents. IEEE Transactions on Systems, Man, and Cybernetics-PART B: Cybernetics, VOL. 26, No. 1, Feb. 1996.9V. Maniezzo, A. Carbonaro. Ant Colony Optimization: an overview, in C.Ribeiro Ess