周榮虎 （鹽城工業(yè)職業(yè)技術(shù)學(xué)院，江蘇 鹽城 224005）

根據(jù)農(nóng)產(chǎn)品時效性的特點(diǎn)，農(nóng)產(chǎn)品配送中心路線規(guī)劃時，除了要考慮常規(guī)物流配送一般影響因素外，還要考慮時間約束問題、客服水平問題、農(nóng)產(chǎn)品保鮮度問題等，配送距離的長短決定了配送費(fèi)用和效率，司機(jī)在選擇派送路徑的時候根據(jù)自己的習(xí)慣，隨機(jī)或者盲目性的選擇農(nóng)產(chǎn)品配送路徑，這一習(xí)慣往往造成繞路、重復(fù)路徑等問題，無形中增加了運(yùn)輸成本、不能保證派送的時效性、降低了客戶滿意度，農(nóng)產(chǎn)品配送路徑的優(yōu)化非常有必要，蟻群算法的出現(xiàn)為配送路徑優(yōu)化問題提供了有效的工具。

1 問題描述

20 世紀(jì)90 年代Marco Dorigo 在他的博士論文中提出螞蟻算法，蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對PID 控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法是一種用來在圖中尋找優(yōu)化路徑的概率型算法。它是通過人工模擬螞蟻尋找食物的過程，即個體之間的信息交流和協(xié)作最終找到從蟻穴到食物源的最短路徑。

1.1 蟻群算法特點(diǎn)

1.1.1 較強(qiáng)的魯棒性

相對于其它算法，蟻群算法對初始線路要求不高，即蟻群算法的求解結(jié)果不依賴于初始線路的取舍，而且在搜索過程中不需要進(jìn)行人工的調(diào)整。其次，蟻群算法的參數(shù)數(shù)目少，設(shè)置簡單，易于蟻群算法應(yīng)用到其他組合優(yōu)化問題的求解。

1.1.2 是一種正反饋的算法

從真實(shí)螞蟻的覓食過程中不難看出，螞蟻能夠最終找到最短路徑，直接依賴于最短路徑上信息激素的堆積，而信息激素的堆積卻是一個正反饋的過程，正反饋是蟻群算法的重要特征，它使得算法演化過程得以進(jìn)行。

1.2 問題描述

1.2.1 隨機(jī)性選擇派送路徑問題

派送員在派送農(nóng)產(chǎn)品的時候?qū)β窂降倪x擇存在隨機(jī)性問題，沒有一套科學(xué)的方法去選擇路徑，大部分派送員的派送路徑都是根據(jù)習(xí)慣或者隨機(jī)的選擇而定。

1.2.2 盲目性選擇農(nóng)產(chǎn)品配送路徑問題

派送員在進(jìn)行農(nóng)產(chǎn)品派送的時候存在盲目性問題。派送員在農(nóng)產(chǎn)品出倉后不按照規(guī)劃好的路徑排列農(nóng)產(chǎn)品，而是隨便裝入車中。邊走邊按照運(yùn)單上的客戶地址進(jìn)行派發(fā)農(nóng)產(chǎn)品。繞路或者派送路徑重復(fù)的情況頻頻出現(xiàn)，不僅浪費(fèi)派送時間并且增加了派送成本。

2 模型建立與假設(shè)

2.1 蟻群算法原理

螞蟻總能找到一條往返于食物源和巢穴之間的最優(yōu)路徑，這是因?yàn)槲浵佋谧哌^的路徑上釋放出一種特殊的信息素，路徑越長，釋放的信息素濃度越低。螞蟻再次選擇路徑的時候，信息素濃度較高的路徑被選中的概率相對較大，因此形成一個正反饋，最優(yōu)路徑上的信息素濃度越來越大，而其他的路徑上信息素濃度卻會隨著時間增加而減少。最終整個蟻群會找出最短路徑。具體情況如圖1 所示:

設(shè)E 是螞蟻巢穴，F(xiàn) 是食物源，BD 是一個障礙物。路徑ABC 的距離是路徑ADC 的2 倍。因?yàn)樵贓 到F 的直線距離中間有障礙物的存在。螞蟻必須經(jīng)過B 或D 往返于E,F 兩點(diǎn)之間。設(shè)每個時間單位分別有30 只螞蟻由E 到達(dá)A，由F 到達(dá)C。為方便說明，設(shè)螞蟻?zhàn)哌^后留下的信息素在路徑上的停留時間為l。在初始時刻（如圖1a），由于路徑AB、CB、AD、CD 上都沒有信息素，A 和C 兩點(diǎn)所在的螞蟻可以隨機(jī)選擇路徑。從統(tǒng)計(jì)的角度可以認(rèn)為它們以相同的概率選擇AB、AD 或者CB、CD。因?yàn)樾畔⑺嘏c路徑的長短成反比，在經(jīng)過一個時間單位后，路徑ADC 上的信息素是路徑ABC 上信息素的2 倍。在t=1 時刻（如圖1b），將有20 只螞蟻分別由A 和C到達(dá)D，有10 只螞蟻分別由A 和C 到達(dá)B。隨著時間的推移，螞蟻選擇路徑ADC 的概率會越來越大，直到所有螞蟻完全選擇路徑ADC，螞蟻便找到了從蟻穴到食物源的最短路徑。

圖1 蟻群算法原理示意圖

2.2 最短路徑模型建立

農(nóng)產(chǎn)品配送路徑優(yōu)化問題就是找到一條派送員以公司點(diǎn)部為起點(diǎn)，經(jīng)過每一個有需求的客戶且僅一次，最后返回到起點(diǎn)的最短路徑。本節(jié)將蟻群算法的原理運(yùn)用到進(jìn)行農(nóng)產(chǎn)品配送路徑優(yōu)化問題中。

2.2.1 提出假設(shè)

2.2.2 最短路徑模型建立

2.2.3 基本蟻群算法模型

式（6） 中，Q3是常量，Lk表示第k 只螞蟻在一次循環(huán)后路徑的長度。即如果螞蟻經(jīng)過ij，則信息素增量為一個常量除以螞蟻k 的一次循環(huán)路線長。這里信息素增量只與螞蟻的循環(huán)路線和Q3有關(guān)系，而和具體的dij無關(guān)。

蟻量模型和蟻密模型利用的是局部信息，螞蟻在完成一步（從一個客戶到達(dá)另外一個客戶） 便更新所有路徑上的信息素。而蟻周模型利用的是整體信息，螞蟻在一個循環(huán)（對所有n 個客戶的訪問） 以后，才更新所有路徑上的信息素。因此在求解農(nóng)產(chǎn)品配送路徑優(yōu)化問題時，蟻周模型比前面兩種模型好。

當(dāng)所有螞蟻在一次循環(huán)結(jié)束后。所有m 只螞蟻從同一點(diǎn)部M 出發(fā)隨機(jī)的前往n 個客戶處，重復(fù)上述步驟直到所有螞蟻都選擇一條相同路徑的時候或者到達(dá)最大循環(huán)次數(shù)Nmax選出最短路徑。蟻群算法的步驟為：將m 只螞蟻隨機(jī)放入n 個客戶處，m只螞蟻分別從n 個客戶處出發(fā)，由式（2） 選擇下一次經(jīng)過的客戶，Tabuk 為放入的已去過的客戶，一次循環(huán)后，根據(jù)式（3）、式（6） 更新每條路徑上的信息素，反復(fù)重復(fù)以上步驟，直到終止條件成立，求出目標(biāo)函數(shù)最優(yōu)值為止。

2.3 實(shí)例計(jì)算

為方便計(jì)算，本文選取蘇州車坊鎮(zhèn)SF 速運(yùn)獨(dú)墅湖點(diǎn)部M 中的收派員A 的區(qū)域B 中的10 個客戶為例（以K0,K1,…,K9，命名）。運(yùn)用蟻群算法對此10 個客戶的農(nóng)產(chǎn)品配送路徑進(jìn)行規(guī)劃來說明蟻群算法在農(nóng)產(chǎn)品配送路徑優(yōu)化問題中的實(shí)用性。

2.3.1 實(shí)例說明

（1） 某鄉(xiāng)村的客觀條件

采用10 個客戶為研究對象，標(biāo)記為1,…,10 分別代表K0,K1,…,K910 個客戶。在派送農(nóng)產(chǎn)品的時候不是取兩地之間的直線距離，而是沿道路距離，通過測量建立點(diǎn)部到各個客戶的距離以及客戶與客戶之間的距離表如表1 所示。

表1 點(diǎn)部到每個客戶的距離以及客戶之間的距離 單位：米

（2） 參數(shù)設(shè)置

為方便計(jì)算，提出以下假設(shè)條件：①10 個客戶都需要有簽收。②所有螞蟻每次都由點(diǎn)部出發(fā)，走完所有客戶后又回到點(diǎn)部。③每只螞蟻在一次循環(huán)過程中經(jīng)過每一個客戶且僅一次。④每個客戶到點(diǎn)部M 以及客戶與客戶之間的路徑長度已知。

本文用100 000 次循環(huán)作為計(jì)算終止條件（這里一次循環(huán)是指所有螞蟻完成一次遍歷所有客戶且僅一次后回到出發(fā)點(diǎn)部）。螞蟻總數(shù)目設(shè)置為客戶的總數(shù)目(m=n=1)0 。即10 只螞蟻同時從點(diǎn)部M 出發(fā)開始循環(huán)，直到所有螞蟻都返回點(diǎn)部則完成一次循環(huán)。具體參數(shù)設(shè)置如表2 所示。

在表2 中，Lk表示的是第k 只螞蟻的一次循環(huán)路線的長度，如果第k 只螞蟻經(jīng)過的路線為：M→K0→K1→K7→K8→K2→K5→K4→K3→K6→K9→M。

表2 實(shí)例中所用參數(shù)設(shè)置

即第k 只螞蟻本次循環(huán)的路徑總長度為2 575 米。本文就是運(yùn)用蟻群算法計(jì)算出一只螞蟻從點(diǎn)部出發(fā)經(jīng)過每個客戶且只經(jīng)過一次最后回到點(diǎn)部的最短路徑。從而縮短農(nóng)產(chǎn)品配送路徑，節(jié)省運(yùn)輸成本。

2.3.2 運(yùn)用蟻群算法對農(nóng)產(chǎn)品配送路徑進(jìn)行編程計(jì)算

結(jié)合蟻群算法的原理，對農(nóng)產(chǎn)品配送路徑進(jìn)行優(yōu)化設(shè)計(jì)，并運(yùn)用C++對設(shè)計(jì)好的最短路徑模型進(jìn)行編程計(jì)算。運(yùn)用蟻群算法優(yōu)化農(nóng)產(chǎn)品配送路徑的步驟為：10 只螞蟻從同一點(diǎn)部M同時出發(fā)，將參數(shù)代入式（2） 選擇下一次經(jīng)過的客戶，Tabuk 為放入的已去過的客戶，一次循環(huán)后，將參數(shù)代入式（3）、式（6） 更新每條路徑上的信息素，反復(fù)重復(fù)以上步驟，直到終止條件成立，求出式（1） 最短路徑模型的最優(yōu)值為止。按照上述步驟編輯好的程序如附錄所示。附錄在VC 上運(yùn)行結(jié)果如圖2 所示：

圖2 附錄在VC 上的運(yùn)行結(jié)果

2.3.3 結(jié)果分析

由圖2 可知螞蟻從獨(dú)墅湖點(diǎn)部M 出發(fā)經(jīng)過10 個客戶且每個客戶只經(jīng)過一次的排列順序?yàn)椋篗 9 7 8 6 5 4 3 2 1 0 M。因此派送員A 在為10 個客戶派送農(nóng)產(chǎn)品的時候，從點(diǎn)部M 出發(fā)后，首先應(yīng)去客戶K9處，最后到達(dá)客戶K0處。其走過的路徑即為此次農(nóng)產(chǎn)品配送過程中走過的最短路徑。最短路徑L 的排列順序?yàn)椋篗→K9→K7→K8→K6→K5→K4→K3→K2→K1→K0→M。

即是派送員由獨(dú)墅湖點(diǎn)部M出發(fā)，分別經(jīng)過10 個客戶且僅一次派送完農(nóng)產(chǎn)品直接返回點(diǎn)部的最短路程為1 475 米。

如果第k 只螞蟻的循環(huán)路徑為：M→K1→K3→K6→K8→K9→K4→K0→K2→K5→K7→M。k

通過多次對10 個客戶的排列順序隨機(jī)組合，沒有找到路徑Lk的長度比1 475 米更小的值。說明派送員A 為10 個客戶派送農(nóng)產(chǎn)品的最短路徑為1 475 米。

在沒有進(jìn)行路徑優(yōu)化的時候，農(nóng)產(chǎn)品員隨機(jī)選擇路徑進(jìn)行農(nóng)產(chǎn)品配送，剛好選擇到最短路徑L 的幾率非常小，但是在運(yùn)用蟻群算法進(jìn)行路徑規(guī)劃后，派送員每次都可以按照規(guī)劃好的路徑進(jìn)行農(nóng)產(chǎn)品配送。為每一個農(nóng)產(chǎn)品派送員規(guī)劃自己區(qū)域內(nèi)的客戶帶來很大的方便，由此可見蟻群算法在農(nóng)產(chǎn)品配送路徑優(yōu)化中具有非常大的實(shí)用性。

3 結(jié)束語

3.1 主要研究工作

本文首先針對農(nóng)產(chǎn)品配送路徑的現(xiàn)狀進(jìn)行分析，然后提出派送員選擇農(nóng)產(chǎn)品配送路徑的時候，存在選擇隨機(jī)性問題和路徑重復(fù)問題。最后針對這兩個問題引入蟻群算法對農(nóng)產(chǎn)品配送路徑進(jìn)行優(yōu)化，尋找一條從農(nóng)產(chǎn)品公司點(diǎn)部M 出發(fā)經(jīng)過每一個需求點(diǎn)且僅一次最后回到點(diǎn)部M 的最短路徑，實(shí)現(xiàn)節(jié)約農(nóng)產(chǎn)品公司的配送成本、提高派送效率、增強(qiáng)客戶滿意度的目標(biāo)。通過本文的研究說明蟻群算法在農(nóng)產(chǎn)品配送路徑優(yōu)化問題中應(yīng)用，有助于農(nóng)產(chǎn)品公司降低運(yùn)輸成本，提高客戶滿意度。

3.2 進(jìn)一步研究問題

本文雖取得了一些有意義的成果，但是還有許多需要進(jìn)一步進(jìn)行研究的方向。

（1） 在論文的實(shí)例中假設(shè)每個客戶都有農(nóng)產(chǎn)品需要簽收，但實(shí)際派送過程中派送員負(fù)責(zé)的客戶中有的客戶在派送沒有簽收。改進(jìn)蟻群算法突破局部最優(yōu)的計(jì)算，把客戶變動的因素設(shè)為變量的同時也能找到農(nóng)產(chǎn)品配送的最短路徑。

（2） 本文假設(shè)派送員在一次農(nóng)產(chǎn)品配送過程中經(jīng)過每一個客戶且僅一次。沒有考慮到突發(fā)狀況和特殊快件的出現(xiàn)，例如實(shí)際生活中有的派送員因?yàn)橐粫r大意而沒有把同一客戶處的農(nóng)產(chǎn)品配送完畢，需要重復(fù)派送。或者有的農(nóng)產(chǎn)品收件人需要提供優(yōu)先派送服務(wù)，下一步可以通過進(jìn)一步改進(jìn)蟻群算法使其在加入突發(fā)狀況后依然能找到最短路徑。