基于蟻群算法的配送路徑規(guī)劃研究

陳 文，鄭少鋒

（福建船政交通職業(yè)學(xué)院，福建 福州 350007）

關(guān)于物流配送路徑規(guī)劃一直是物流領(lǐng)域研究的熱點(diǎn)和難點(diǎn)問題，從國外研究情況來看，1993年Ronald等人提出物流系統(tǒng)設(shè)計(jì)的四個(gè)核心戰(zhàn)略規(guī)劃區(qū)域模型（Four major strategic planning areas in logistics system design），他認(rèn)為四個(gè)核心區(qū)域?yàn)榭蛻舴?wù)水平、選址決策、庫存決策和運(yùn)輸決策（Customer service levels，Location decisions，Inventory decisions，Transport decisions），對于配送中心選址方法可簡單分為定性和定量兩大類，定性方法主要是層次分析法和模糊綜合評(píng)價(jià)相結(jié)合對各個(gè)方案進(jìn)行指標(biāo)評(píng)價(jià)，找出最優(yōu)地址。定量方法包括重心法、運(yùn)輸規(guī)劃法、Cluste法、CFLP法、Baumol－Wolfe模型、混合0—1整數(shù)規(guī)劃法、雙層規(guī)劃法、遺傳算法等。蟻群算法是一種新型的優(yōu)化方法，該算法不依賴于具體問題的數(shù)學(xué)描述，具有全局優(yōu)化能力。

本文提出了一種基于改進(jìn)蟻群算法的物流配送路徑規(guī)劃方法，將物流配送中心看成一個(gè)聚類過程，再利用蟻群系統(tǒng)中螞蟻通過信息素留存尋找最優(yōu)路徑的機(jī)制，結(jié)合螞蟻使物體聚堆的行為模式，合理設(shè)計(jì)轉(zhuǎn)移概率、禁忌列表及信息素更新方式，使系統(tǒng)配送中心的配送路徑最短，從而確定配送中心的配送路徑。

1 蟻群算法

仿生學(xué)家經(jīng)過大量細(xì)致觀察研究發(fā)現(xiàn)，螞蟻個(gè)體之間通過一種稱為外激素的物質(zhì)進(jìn)行信息傳遞，螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下信息素，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并且以此指導(dǎo)自己的運(yùn)動(dòng)方向。受此啟發(fā)，它由意大利學(xué)者M(jìn)arco Dorigo于1991年在他的博士論文中引入，提出了一種基于螞蟻種群的新型優(yōu)化算法——蟻群算法。

蟻群算法（ant colony optimization,ACO），又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，螞蟻總能找到巢穴與食物源之間得最短路徑。經(jīng)研究發(fā)現(xiàn)，螞蟻的這種群體協(xié)作功能是通過一種遺留在其來往路徑上叫做信息素（Pheromone）的揮發(fā)性化學(xué)物質(zhì)來進(jìn)行通信和協(xié)調(diào)的?；瘜W(xué)通信是螞蟻采取得基本信息交流方式之一，在螞蟻的生活習(xí)性中起著重要的作用。通過對螞蟻覓食行為的研究發(fā)現(xiàn)，整個(gè)蟻群就是通過這種信息素進(jìn)行相互協(xié)作，形成正反饋，從而使多個(gè)路徑上的螞蟻都逐漸聚集到最短的那條路徑上。

1.1 研究目的

本研究擬通過學(xué)習(xí)螞蟻覓食回巢的生物本能，對物流配送進(jìn)行仿真模擬，找出優(yōu)化的配送路徑，提高物流配送的效率和效益。

1.2 研究的對象

先對6個(gè)同配送點(diǎn)的配送方案進(jìn)行研究，然后延伸到100個(gè)配送點(diǎn)，并找出最佳路徑。以上步驟均通過計(jì)算機(jī)編程進(jìn)行演化分析。把研究的成果進(jìn)行實(shí)際應(yīng)用的演算和驗(yàn)證。

1.3 研究方法

本文使用蟻群算法，進(jìn)行人工模擬配送路線，并用計(jì)算機(jī)編程進(jìn)行模擬，就如同一只人工螞蟻，背著背包，到若干個(gè)結(jié)點(diǎn)，搬運(yùn)食物回蟻巢。

規(guī)則1 環(huán)境：人工螞蟻所在的環(huán)境是一個(gè)虛擬的世界，有確定的路線橋，且兩點(diǎn)間路線橋不相交；有信息素，信息素都同質(zhì)（不區(qū)分，找到食物時(shí)分泌的信息素和回巢時(shí)分泌的信息素），環(huán)境以一定的速率讓信息素消失。

規(guī)則2 移動(dòng)：人工螞蟻只會(huì)沿著路線橋覓食，當(dāng)走到結(jié)點(diǎn)（覓食點(diǎn)），人工螞蟻會(huì)判斷是否有信息素及其濃度，優(yōu)先選擇信息素濃度大的路線橋?yàn)槁窂剑煌瑫r(shí)會(huì)有一定的概率，隨機(jī)選擇別的路線橋；如路線橋上均無信息素則隨機(jī)選擇路線橋。

規(guī)則3 覓食：人工螞蟻沿路線橋到各個(gè)結(jié)點(diǎn)覓食，當(dāng)?shù)竭_(dá)該覓食點(diǎn)后，為防止人工螞蟻原地轉(zhuǎn)圈，它會(huì)記住最近剛走過哪些點(diǎn)（禁忌表），如發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)是已覓食過的結(jié)點(diǎn)，則會(huì)避開該點(diǎn)。

規(guī)則4 信息素：每只人工螞蟻在遍歷完各點(diǎn)后，系統(tǒng)會(huì)利用蟻周算法更新信息素，對總路徑最短的路線進(jìn)行精英激勵(lì)，會(huì)大量增加該路線信息素；如果總路徑較長則少量增加信息素；信息素在人工螞蟻遍歷完后，將會(huì)按一定速率自動(dòng)揮發(fā)所有路線橋上的信息素。

2 研究步驟

2.1 初始化結(jié)點(diǎn)

各個(gè)結(jié)點(diǎn)進(jìn)行坐標(biāo)化，數(shù)據(jù)存入zuobiao（序號(hào)：X,Y）表中，見表1，然后構(gòu)造成路線橋距離矩陣存入jiedian（序列：1,2,3,…,n）表中，見表2，此次研究擬選用zuobiao表中的結(jié)點(diǎn)和數(shù)據(jù)：

表1 zuobiao表

表2 jiedian表

2.2 信息素表示

所有的路線橋上的信息素全部為0，并把信息素?cái)?shù)據(jù)存入xinxisu（序號(hào)：1,2,3,...,n）表中，見表3，用0表示無信息素。

表3 xinxisu表

2.3 初始化禁忌表

人工螞蟻比較聰明，當(dāng)?shù)竭_(dá)該覓食點(diǎn)后，它會(huì)記住已找到的結(jié)點(diǎn)，并把結(jié)點(diǎn)信息存入jinji（序號(hào)，禁忌，先后順序）表中，其中0表示未用，1表示已用，詳見jinji表，見表4。

表4 jinji表

第1只人工螞蟻運(yùn)行狀態(tài)：人工螞蟻從巢穴出發(fā)，判斷與該結(jié)點(diǎn)連接的各個(gè)路線橋上的信息素的濃度，因信息素均為0，則用隨機(jī)函數(shù)進(jìn)行選擇路線→在jinji表中把起點(diǎn)設(shè)置為1（已用），先后順序?yàn)?，離開起點(diǎn)→沿著該路線橋到達(dá)下一覓食結(jié)點(diǎn)，信息素為0，則用隨機(jī)函數(shù)進(jìn)行選擇路線→同樣在jinji表中把第1個(gè)覓食結(jié)點(diǎn)設(shè)置為1（已用），先后順序?yàn)?，離開第1個(gè)結(jié)點(diǎn)→沿著該路線橋到達(dá)下一覓食結(jié)點(diǎn)，判斷信息素，隨機(jī)函數(shù)選擇路線橋→……→當(dāng)6個(gè)覓食結(jié)點(diǎn)全部走完后，人工螞蟻?zhàn)詣?dòng)沿著路線橋回到巢穴結(jié)點(diǎn)，從而形成完整的閉合回路→計(jì)算總路線橋長度，用L1表示，同時(shí)更新xinxisu表，在路線橋閉合回路全部灑上強(qiáng)度為3的信息素。

第2只人工螞蟻運(yùn)行狀態(tài)：人工螞蟻從巢穴出發(fā)，判斷與該結(jié)點(diǎn)連接的各個(gè)路線橋上的信息素的濃度，原則上沿著信息素濃度大的路線橋通往下一覓食結(jié)點(diǎn)，但也會(huì)有“叛逆”的情況，用隨機(jī)函數(shù)產(chǎn)生這種小概率事件，如人工螞蟻遇到小概率事件，則沿著小概率事件選擇的路線橋爬行到下一覓食結(jié)點(diǎn)→在jinji表中把起點(diǎn)設(shè)置為1（已用），先后順序?yàn)?，離開起點(diǎn)→沿著該路線橋到達(dá)下一覓食結(jié)點(diǎn)，判斷連接該覓食結(jié)點(diǎn)各個(gè)方向上的信息素濃度，正常是沿著信息素濃度大的方向移動(dòng)，同時(shí)考慮小概率事件是否發(fā)生，如發(fā)生則沿著小概率選擇的優(yōu)先路線前進(jìn)?！瑯釉趈inji表中把第1個(gè)覓食結(jié)點(diǎn)設(shè)置為1（已用），先后順序?yàn)?，離開第1個(gè)結(jié)點(diǎn)→沿著該路線橋到達(dá)下一覓食結(jié)點(diǎn)，判斷信息素濃度，并優(yōu)先考慮小概率事件→……→當(dāng)6個(gè)覓食結(jié)點(diǎn)全部走完后，人工螞蟻?zhàn)詣?dòng)沿著路線橋回到巢穴結(jié)點(diǎn)，從而形成完整的閉合回路→計(jì)算總路線橋長度，用L2表示，更新xinxisu表，判斷該輪路線橋總長度是否是最短，如最短則在第2只螞蟻?zhàn)哌^的路線橋上全部灑上激勵(lì)的信息素，其值為3，同時(shí)，在全部路線橋上按1個(gè)信息素/每輪的速率，揮發(fā)信息素。

2.4 總路線長度最優(yōu)的判定

判斷路線橋該輪路線橋總長度是否是最短，可分為如下三種情況。

L1＜L2 增加L2閉合回路上的信息素+1 把L1設(shè)為最短路徑，用L min表示，后續(xù)人工螞蟻的Ln均與L min比較

L1=L2 增加L2閉合回路上的信息素+3 把L2設(shè)為最短路徑，用L min表示，后續(xù)人工螞蟻的Ln均與L min比較

L1＞L2 增加L2閉合回路上的信息素+3 把L2設(shè)為最短路徑，用L min表示，后續(xù)人工螞蟻的Ln均與L min比較

后續(xù)n只人工螞蟻和第2只螞蟻一樣覓食（n=80），最終沿著信息素最濃的路線橋爬行各個(gè)覓食點(diǎn)，其路徑橋?yàn)樽疃搪肪€。

2.5 參數(shù)選取

（1）隨機(jī)小概率為0.05，結(jié)點(diǎn)6個(gè)，信息素對精英螞蟻獎(jiǎng)勵(lì)+3，對一般螞蟻+1，信息素?fù)]發(fā)速率為1/輪。

（2）人工螞蟻選取80只（迭代80輪）。

（3）覓食結(jié)點(diǎn)的狀態(tài)。其中第1只人工螞蟻比較特殊，路線橋選擇不是按信息素的濃度進(jìn)行選擇，而是人工賦予隨機(jī)選擇函數(shù)。在離開原點(diǎn)時(shí)選擇概率為1/6，到第一個(gè)結(jié)點(diǎn)后選擇概率為1/5，到第二個(gè)結(jié)點(diǎn)后選擇概率為1/4,……,1/1回到巢穴。

2.6 進(jìn)行演算

覓食結(jié)點(diǎn)的狀態(tài)選取3種狀態(tài)：離散型、聚合型、平均型；隨機(jī)小概率事件按分形理論選取20個(gè)不同的參數(shù)，如下值：0.5、1.5、2.5、3.5、4.5、5.5、6.5、7.5、8.5、9.5、5、15、25、35、45、55、65、75、85、95；每輪螞蟻選擇 80 只；為了剔除異常收斂，每輪均進(jìn)行10次演算求出平均值，作為該輪穩(wěn)定的最短路徑。綜合考慮狀態(tài)的聚合度、覓食結(jié)點(diǎn)個(gè)數(shù)、隨機(jī)小概率事件，通過編程和建立數(shù)據(jù)庫，模擬最優(yōu)路線結(jié)果如下：

3 實(shí)例分析

為了驗(yàn)證本算法的正確性，在Matlab平臺(tái)上對其進(jìn)行了仿真實(shí)驗(yàn)。建立如下數(shù)學(xué)模型，選取福州市某配送中心10個(gè)點(diǎn)進(jìn)行配送，并且要求路徑最短，如表5所示，10個(gè)點(diǎn)經(jīng)過坐標(biāo)化后是接近平均型分布，小概率事件選取0.5，人工螞蟻選取80只，每輪進(jìn)行10次迭代并取平均值。結(jié)合迭代運(yùn)算，得出最優(yōu)路徑如下：

表5 10個(gè)配送點(diǎn)坐標(biāo)

蟻群算法可以比較完美地解決配送路徑問題，但也存在不足之處，特別是在信息不完全的情況下，比如兩點(diǎn)之間有捷徑，模擬最優(yōu)線路與實(shí)際線路會(huì)有偏差，同時(shí)算法可能會(huì)陷入局部最優(yōu)，可以通過控制收斂速度和加快趨向最優(yōu)路徑對蟻群算法進(jìn)行優(yōu)化。

[1]李云清.物流系統(tǒng)規(guī)劃[M].上海：同濟(jì)大學(xué)出版社，2004.

[2]秦固.基于蟻群優(yōu)化的多物流配送中心選址算法[J].系統(tǒng)工程理論與實(shí)踐，2006(4):120-124.

[3]魏娜.關(guān)于物流配送中心選址優(yōu)化問題研究[D].大連：東北財(cái)經(jīng)大學(xué)（碩士學(xué)位論文），2006.

[4]高雷阜,等.基于最大最小螞蟻系統(tǒng)的物流配送中心選址算法的研究[J].運(yùn)籌與管理，2007(12):42-46.

[5]許慧，王正友，楊歡慶.蟻群算法及其聚類應(yīng)用[J].礦山機(jī)械，2007(1):115-117.

[6]Dorigo M,Maniezzo V,Colomi A.Ant system:Optimization by acolony of cooperating agents[J].IEEE Trans on Systems,Man and Cybernatics,1996,26(1):28-41.

[7]王勇，何宇.基于改進(jìn)蟻群算法的多物流配送中心選址[J].經(jīng)濟(jì)論從，2012(4):281-298.