基于改進MMAS的多配送中心車輛調(diào)度問題研究

鄭雪峰　陳培友　高太光

[摘要]針對城市多配送中心車輛調(diào)度問題，在分析最大最小蟻群算法的基礎(chǔ)上，提出了改進MMAS算法，該算法重點對信息素的揮發(fā)機制進行探討，并引入自適應(yīng)機制對信息素的確定方案進行改進。實驗結(jié)果證明，改進MMAS算法對于優(yōu)化多配送中心物流車輛路徑問題是有效的。

[關(guān)鍵詞]多配送中心最大最小蟻群算法車輛調(diào)度

車輛凋度問題(Vehicle Scheduling Problem，VSP)是物流研究中的一個重要的領(lǐng)域，對于減少企業(yè)物流配送成本，提高服務(wù)品質(zhì)有很重要的意義。如何在達到客戶滿意度的同時通過路徑優(yōu)化降低運送成本，成為多配送中心車輛調(diào)度問題研究的一個重要方面。目前，在解決路徑優(yōu)化等問題時，蟻群算法是理論和實踐關(guān)注的焦點，本文研究了最大最小蟻群算法（MMAS，max-min ant system），并對信息素的計算公式進行改進，達到在多配送中心車輛調(diào)度中確保解的全局性，構(gòu)造以降低配送總費用為目標(biāo)的配送方案。

一、多配送中心車輛調(diào)度問題描述

在城市尤其是大規(guī)模城市的車輛調(diào)度中，由于節(jié)點規(guī)模都比較大，物流配送車輛又受到交通擁擠等因素的影響，如果每個節(jié)點只有一個配送中心，難以保證配送的及時性，容易導(dǎo)致整個服務(wù)水平降低，進而降低客戶滿意度。同時，從配送成本上考慮，在規(guī)模大的節(jié)點內(nèi)單一配送中心的成本也較高。為了解決以上問題，多數(shù)物流公司在同一個大節(jié)點內(nèi)一般設(shè)立多個配送中心，如圖1，其中矩形代表倉庫，橢圓形代表配送中心，圓點代表客戶。由圖1可知，從物流公司倉庫到配送中心的距離是不變的，可變的是循環(huán)到不同客戶配送線路距離。

二、蟻群算法描述

由于受到自然界真實蟻群集體行為的啟發(fā)，由意大利學(xué)者M．Dorigo等人首先提出了一種基于種群的模擬優(yōu)化算法—蟻群算法(ant system,AS)，該算法在物流配送路徑優(yōu)化應(yīng)用過程中，存在的問題是車輛選擇路徑時容易陷入局部最優(yōu)解，MMAS算法在一定程度上消除了基本蟻群算法中的停滯現(xiàn)象。

1. 最大最小蟻群算法

設(shè)m是蟻群中螞蟻的總數(shù)，n是節(jié)點的總數(shù)，dij(i,j=1,2,...,n)表示節(jié)點i和節(jié)點j之間的距離。假設(shè)目前螞蟻處于節(jié)點i，以τij（t）表示t時刻節(jié)點i與節(jié)點j之間的信息素濃度，ηij（t）表示t時刻螞蟻由節(jié)點i轉(zhuǎn)移到節(jié)點j的期望程度（可見度），則t時刻螞蟻k由節(jié)點i轉(zhuǎn)移到節(jié)點j概率為：

(1)

0，其他

其中，使用禁忌集合tabuk(k=1,2,...,m) 記錄螞蟻k當(dāng)前走過的節(jié)點，則式中allowedk={1,2,...,n}-taubk表示允許螞蟻k下一步走過節(jié)點的集合；α表示路徑上的信息量對螞蟻選擇路徑所起作用的大??；β表示在選擇公式中兩點間可見度對螞蟻選擇路徑所起作用的大小；ηij（t）取值一般為1/dij。

為了避免殘留信息過多引起的殘留信息淹沒啟發(fā)信息的問題，在每個螞蟻完成對所有n個節(jié)點的訪問后(即一個循環(huán))，需對路徑上的信息素濃度進行如下調(diào)整：①一次循環(huán)中只有最短路徑的螞蟻才可以進行信息素修改增加；②把信息素的取值范圍限制在一個特定區(qū)間[τmin,τmax]內(nèi)，超出這個范圍的值被強制設(shè)為τmin或τmax，避免了信息素的無限制累加和可能出現(xiàn)的信息素為零的現(xiàn)象；③設(shè)信息素的初始值設(shè)為τmax，這樣可以使算法遍歷搜索空間，不致早熟，同時把信息素殘留系數(shù)ρ設(shè)置較小，以便螞蟻在開始搜索時選擇更多路徑；④采用了平滑機制（pheromone trail smoothing,PTS）,當(dāng)系統(tǒng)停滯時，所有的信息素重新被初始化,當(dāng)所有螞蟻完成一次迭代后，螞蟻釋放的信息素為

(2)

其中參數(shù)δ決定了對以前信息素保留的多少：δ=0是完全保留，PTS不起作用；δ=1則完全去掉以前的信息素分布，重新開始計算。這種機制在較長時間計算中對于消除停滯現(xiàn)象有比較好的作用。

2. MMAS算法的改進

MAS中僅對最好路徑上的信息素進行全局更新，而螞蟻在行進過程中常常選擇信息量較大的路徑，當(dāng)許多螞蟻選中同一條路徑時，該路徑中的信息量就會陡然增大，從而造成堵塞現(xiàn)象，表現(xiàn)在使用該算法解決問題時就容易導(dǎo)致早熟和局部收斂。目前，我國大部分城市規(guī)模的不斷擴張和電子商務(wù)的迅速發(fā)展，使得企業(yè)面對的顧客群體日益壯大，道路容量超負(fù)荷，車輛堵塞成為常見現(xiàn)象。為了解決這類較大規(guī)模的問題，本文從解的分布狀態(tài)入手，提出了一種新的自適應(yīng)改變τ值的方法：在每次迭代后對所有路徑上的信息素進行判斷，如果在[τmin,τmax]內(nèi)，按公式（3）進行計算；如果τij超出[τmin,τmax]界限，則按照公式（4）和公式（5）對值進行修正。

(3)

(4)

(5)

(6)

其中是一個與收斂次數(shù)m'成正比的函數(shù)，收斂次數(shù)m'越多， 的取值越大，這里c為常數(shù),△τij的計算參照公式(6)，公式（6）中Q代表的是總信息量。該方案根據(jù)解的分布情況自適應(yīng)地進行信息素的更新，從而動態(tài)地調(diào)整所有路徑上的信息素強度，既避免了MMAS算法中易出現(xiàn)的早熟和局部收斂，又提高了全局搜索能力，更大程度的降低了運送成本。

三、實例分析

哈爾濱市L乳業(yè)有限公司位于松北區(qū)，在生產(chǎn)車間旁建有立體倉庫，公司先將產(chǎn)品運送至倉庫，再由該倉庫向市區(qū)的配送中心送貨，然后由配送中心向各大超市進行貨物的配送。本文主要研究L乳業(yè)有限公司向哈爾濱市區(qū)各大型超市配送袋裝鮮牛奶的情況，目的是合理地安排公司配送車輛在哈爾濱市區(qū)的行車路線，在準(zhǔn)時到達的基礎(chǔ)上使總運輸成本最低。該企業(yè)在哈爾濱市有兩個配送中心，每個配送中心有3臺配送車輛，每臺車載重量均為10t，配送的最大行駛距離為50km。共有20個客戶（超市），每個客戶的貨物需求量都小于或等于2t。在運送車輛相同的情況下，設(shè)運輸費用與路程成正比，所以要求組織適當(dāng)?shù)男熊嚶肪€，使總的運送路程最短。其中兩個配送中心的地址坐標(biāo)分別為：配送中心I(6，9.2)、配送中心II(14.2，12)，20個客戶的坐標(biāo)及其貨物需求量見表1。為了方便描述問題，在這里對兩點間距離取直線距離。

表1已知條件表

使用C語言對MMAS算法和改進的MMAS算法編程，分別在相同配置的P-C機上運算，初始參數(shù)設(shè)置為：α=1,β=1,ρ=0.3，NC=800。表2是兩種算法運行結(jié)果的比較。

表2算法的比較

通過實驗結(jié)果比較，改進的MMAS算法得到的最短路徑優(yōu)于MMAS算法，搜索成功率高。雖然改進的MMAS教MMAS算法運行時間長，但該類問更注重經(jīng)濟成本的優(yōu)化，所以在時間上的增量是可以接受的?？傊倪M的MMAS算法對于解決多配送中心物流車輛路徑問題是有效的，它解決了局部收斂，確保車輛調(diào)度的全局性，并且可有效降低全局配送費用，節(jié)約經(jīng)濟成本，具有一定的實用性和推廣價值。

參考文獻:

[1]施朝春.帶有時間窗的多配送中心車輛調(diào)度問題研究[J].計算機工程與應(yīng)用,2009，45(34) :21.

[2]Dorigo M，Gambar D．Ant colony algorithm for the traveling salesman problems in biological systems[J]．IEEE Transactions on Evolutionary Computation,1997，43(2)：73—81．

[3]Johnson D S，McGeoch L A．The travelling salesman problem：A case studyin local optimization[M]．New York：Wilgyand Sons，1997：215—310．

[4]張強，熊盛武.多配送中心糧食物流車輛調(diào)度混合蟻群算法[J].計算機工程與應(yīng)用,2011,47(7) :4 1

[5]胡小兵，袁銳等．蟻群算法原理的仿真研究[J]．計算機仿真，2004，21(8)：125—128．

[6]張紀(jì)會，高齊圣等．自適應(yīng)螞蟻群算法[J]．控制理論與應(yīng)用，2000，17(1)：1-3．