鄭雪峰　陳培友　高太光

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

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

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

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

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

二、蟻群算法描述

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

1. 最大最小蟻群算法

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

(1)

0，其他

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

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

(2)

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

2. MMAS算法的改進(jìn)

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

(3)

(4)

(5)

(6)

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

三、實(shí)例分析

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

表1已知條件表

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

表2算法的比較

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

參考文獻(xiàn):

[1]施朝春.帶有時(shí)間窗的多配送中心車輛調(diào)度問題研究[J].計(jì)算機(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]張強(qiáng)，熊盛武.多配送中心糧食物流車輛調(diào)度混合蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(7) :4 1

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

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