畢洪山，何光營，韓 印

(1.上海理工大學(xué) 管理學(xué)院，上海 200093;2.上海電力學(xué)院 現(xiàn)代教育技術(shù)中心，上海 200090;

3，上海理工大學(xué) 交通系統(tǒng)工程研究所，上海 200093)

配送網(wǎng)絡(luò)是物流系統(tǒng)的核心環(huán)節(jié)，直接影響物流的效率.[1-2]配送網(wǎng)絡(luò)規(guī)劃是指根據(jù)投資及運行費用等約束條件，在已有設(shè)施和線路的基礎(chǔ)上，針對新的配送客戶出現(xiàn)的情況進(jìn)行搜索的一種配送方案，目的是在滿足相關(guān)的其他約束條件和可靠性要求的同時，使配送網(wǎng)絡(luò)建設(shè)投資的費用和相關(guān)的運行費用最小.這種搜索本質(zhì)上是一個復(fù)雜的優(yōu)化組合問題.科研人員已經(jīng)研究了很多智能算法，如遺傳算法、人工神經(jīng)網(wǎng)絡(luò)粒子群算法等，本文提出了一種基于改進(jìn)的蟻群算法來求解配送網(wǎng)絡(luò)擴(kuò)展優(yōu)化問題的數(shù)學(xué)模型，并設(shè)計了相應(yīng)的求解算法.

1 配送網(wǎng)絡(luò)拓?fù)鋱D的數(shù)學(xué)模型

配送網(wǎng)絡(luò)的數(shù)學(xué)模型直接影響車輛路徑的求解.[3]在此模型中，設(shè)定參數(shù)約束車輛的載重和行駛的路線長度，并不涉及貨物的類型.車輛路徑規(guī)劃問題是一個NP完全的問題，該問題可以看作是旅行商問題(Traveling Salesman Problem，TSP)和裝箱問題(Bin Packing Problem)的復(fù)合問題.

本文提出多目標(biāo)數(shù)學(xué)模型.設(shè)某配送中心(Distribution Center，DC)可以調(diào)度的車輛為T:

配送中心要服務(wù)的客戶群為P:

當(dāng)p=0時表示車輛在配送中心.每輛車的載重為B，bt即為t車的載重.客戶群P中每個客戶的需求為 D，dp即為客戶 p的需求.客戶間的運輸成本為C，cij即為從客戶i到到客戶j的運輸成本.模型建立后，優(yōu)化的結(jié)果要滿足調(diào)度車輛最少和行車路線最短.為此定義參數(shù)xit，yijt且滿足:

配送網(wǎng)絡(luò)的數(shù)學(xué)模型為:

客戶需求為D，要求每個客戶必須都被服務(wù)到，即:

此時參數(shù)xit滿足:

此時再考察參數(shù)yijt，有:

參數(shù)xit和yijt考察完畢后就可以保證客戶僅被一輛車訪問.

計算中產(chǎn)生的子回路必須消除，堵子回路采用如下公式:

參數(shù)取值滿足如下條件:

2 蟻群算法及其實現(xiàn)

2.1 蟻群算法簡介

蟻群算法(Ant Colony Optimization，ACO)是一種用來在圖中尋找優(yōu)化路徑的概率型算法.[4-7]經(jīng)過長時間的觀察發(fā)現(xiàn)，在尋找食物的過程中，蟻群群體搜索食物源路徑的行為有很強的智能性.

蟻群算法是一種模擬進(jìn)化算法，初步研究表明，該算法對群體智能搜索最短路徑問題有很強的指導(dǎo)性.

針對大群體多參數(shù)優(yōu)化路徑設(shè)計的問題，將蟻群算法的設(shè)計結(jié)果與相應(yīng)遺傳算法的設(shè)計結(jié)果進(jìn)行對比，通過數(shù)值仿真結(jié)果表明，蟻群算法是一種新型的模擬進(jìn)化優(yōu)化方法.

螞蟻最初尋找食物時的路線圖如圖1所示.

圖1 螞蟻開始尋找食物時的路線

蟻群在路徑1和路徑2上對等分布，當(dāng)某個螞蟻發(fā)現(xiàn)食物源后，它能在其走過的路徑上留下一種蟻群所特有的分泌物質(zhì)，即為信息素，而其他螞蟻在移動的過程中能夠感知到這種信息素的存在及其濃度，并以此修正自己前進(jìn)的方向，大量的螞蟻傾向于向信息素濃度強的方向前進(jìn).長時間后由大量螞蟻組成的蟻群的群體行為便呈現(xiàn)一種信息素正反饋的現(xiàn)象，即某一路徑上走過的螞蟻越多，那么后來者選擇該路徑的概率就越大，如圖2所示.

圖2 螞蟻發(fā)現(xiàn)最短路徑后的路線

2.2 蟻群算法的實現(xiàn)

假設(shè)有m只螞蟻，有n個隨機(jī)選擇的城市，m只螞蟻要遍歷 n個城市.[8-10]那么每一只螞蟻 a的每一步行動b必須依據(jù)某個函數(shù)選擇下一個沒有到過的城市節(jié)點，同時在完成某一步或者整個循環(huán)后，立刻更新所有經(jīng)過的路徑上的殘留信息素濃度.

根據(jù)以上原理構(gòu)建轉(zhuǎn)移函數(shù)，根據(jù)轉(zhuǎn)移函數(shù)的概率選擇下一個城市節(jié)點，在t時刻城市i和城市j間的路徑上殘留信息素濃度為Sij(t)，即由算法本身提供的信息.由城市i轉(zhuǎn)移到城市j的啟發(fā)信息素為Gij，該啟發(fā)信息素由目標(biāo)函數(shù)給出，由設(shè)定的算法實現(xiàn).那么某時刻位于城市i的螞蟻a選擇城市j為目標(biāo)城市的概率為Pij(a).

同時，為了避免對同一城市節(jié)點的重復(fù)訪問，每只螞蟻必須保存一個列表t(k)，用于記錄到目前為止已經(jīng)訪問過的城市.在某一只螞蟻完成對所有城市的訪問后，算法必須對殘留信息素進(jìn)行更新處理，減小舊的信息素，同時加入螞蟻訪問路徑留下的最新的信息素Sij(t).

3 應(yīng)用蟻群算法設(shè)計配送網(wǎng)絡(luò)

3.1 定義配送網(wǎng)絡(luò)中的螞蟻

(1)每只螞蟻隨機(jī)分布在不同的源結(jié)點，且能夠獨立地尋找從源結(jié)點到目的結(jié)點的較優(yōu)路徑，不同螞蟻之間是并行的.[11]

(2)螞蟻之間通過GPS定位系統(tǒng)給配送中心反饋實時路況信息素，配送中心再將此信息素放送給螞蟻.以此方式間接完成螞蟻之間信息素的傳遞.

(3)路徑上共有 n個結(jié)點，螞蟻經(jīng)過該路徑時釋放的信息素平均分配在這n個結(jié)點上.

(4)在行駛過程中，螞蟻收集的信息包括行駛時間長度、路況信息、惡劣路況等，由配送中心做出標(biāo)記.

(5)螞蟻到達(dá)目的結(jié)點后必須沿著同樣的路徑返回源結(jié)點.用螞蟻一個來回所花費的代價的倒數(shù)作為信息素，并將該信息素值平均分配在該路徑的所有結(jié)點上.

(6)螞蟻返回源結(jié)點后配送中心即刪除該螞蟻.

3.2 改進(jìn)蟻群算法的轉(zhuǎn)移概率

t時刻位于城市i的螞蟻a選擇城市j為目標(biāo)城市的概率是Pij(a)，路徑上信息素濃度為:

αij(t+m)= βαij(t)+Sαij(t+m)得出轉(zhuǎn)移概率為:

從i和j的積中取得n個數(shù)，目的是為加強下一節(jié)點的概率計算，減小選擇下一節(jié)點的盲目性.根據(jù)信息素濃度確定出螞蟻從該節(jié)點到其相鄰節(jié)點的轉(zhuǎn)移概率，并取得轉(zhuǎn)移概率的最大值運動到下一個節(jié)點.

隨著時間的推移，所有螞蟻因線路長度或退化而不再向前運動.計算每個螞蟻所花費的時間和成本，取滿足約束條件的線路費用最小的一條作為配送網(wǎng)絡(luò)優(yōu)化后的第一條線路，然后將第一條線路信息通過GPS系統(tǒng)發(fā)送到終端，修改它們的軌跡，讓螞蟻轉(zhuǎn)移到線路一.重新調(diào)用螞蟻算法修正線路一.線路一隨時間進(jìn)化為最優(yōu)線路.

4 配送網(wǎng)絡(luò)的系統(tǒng)流程及編程

4.1 系統(tǒng)流程

整個配送網(wǎng)絡(luò)系統(tǒng)設(shè)計總體流程為:首先設(shè)定算法的參數(shù)，再比較各條配送線路的長度，通過轉(zhuǎn)移概率取得下一個配送節(jié)點.[12]詳細(xì)流程如圖3所示.

4.2 C語言實現(xiàn)配送網(wǎng)絡(luò)

系統(tǒng)實現(xiàn)的核心偽碼表示如下:

double d_xxs=1//初始信息量的多少

double d_ljxxs[][]//每條路徑上的信息量

double d_ljxxs[][]//代表對應(yīng)路徑上的信息素增量

double d_city[][]//城市距離矩陣

double f_qf[][]//啟發(fā)函數(shù)其值

f_qf[i][j]=1/d_city[i][j]

int i_no[][]//i_no[a][b]=1 表示螞蟻 a已經(jīng)走過了b城市

int ant[][]//螞蟻 a 的路徑的數(shù)組為 ant[a][]

double d_solu[];

int i_br[];

double qfyz，qwqfyz，ssxcl，e.

圖3 蟻群算法流程示意

Pija(t)表示t時刻螞蟻a由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率;qfyz代表信息素啟發(fā)因子，表示某路徑的相對重要性，可以真實地反映螞蟻在移動過程中所積累的信息素在其他螞蟻運動時所起的指導(dǎo)作用，其值越大，則螞蟻越傾向于選擇其他螞蟻經(jīng)過的路徑，這樣就加強了螞蟻間的協(xié)作性;qwqfyz代表期望的啟發(fā)式參數(shù)，表示路徑能見度的相對重要性，其真實反映了螞蟻在運動過程中啟發(fā)信息是在其他螞蟻選擇路徑時受到重視程度的大小，其值越大，轉(zhuǎn)移概率貪心性越強;ssxcl代表信息殘留因子;e代表信息素強度，用于計算螞蟻留在路徑上的信息量;int num表示迭代次數(shù)的運行費用和可靠性.

根據(jù)概率函數(shù)計算螞蟻的轉(zhuǎn)移概率的函數(shù)如下:

程序中輸入不同的節(jié)點數(shù)坐標(biāo)，得到的實驗數(shù)據(jù)如表1所示.

表1中，l為配送完相應(yīng)節(jié)點的總路徑長度，t為配送完相應(yīng)節(jié)點的總行駛時間，不記錄在客戶處停留的時間.

從表1可以看出，節(jié)點數(shù)越多，改進(jìn)后的蟻群算法的優(yōu)勢越明顯，即大型配送系統(tǒng)更適合該改進(jìn)后的蟻群算法.

表1 蟻群算法的實驗數(shù)據(jù)

5 結(jié)語

本文將蟻群算法應(yīng)用于配送網(wǎng)絡(luò)拓?fù)鋱D設(shè)計中.以運行費用和行車時間之和為目標(biāo)函數(shù)，建立了相應(yīng)的求解算法.改進(jìn)了蟻群算法的轉(zhuǎn)移概率，在對可行性解空間進(jìn)行搜索時提高了效率，加速了收斂.最后通過C語言實現(xiàn)了算法.實驗結(jié)果表明，本文提出的基于蟻群算法的配送網(wǎng)絡(luò)拓?fù)鋱D在最短路徑搜索上是可行的.

[1]馬向國.現(xiàn)代物流配送中心規(guī)劃、仿真及應(yīng)用案例[M].北京:中國發(fā)展出版社，2014:10-126.

[2]李珍萍，周文峰.物流配送中心選址與路徑優(yōu)化問題——建模與求解[M].北京:機(jī)械工業(yè)出版社，2014:200-260.

[3]趙燕偉，張景玲，王萬良.物流配送的車輛路徑優(yōu)化方法[M].北京:科學(xué)出版社，2014:60-80.

[4]李麗香，彭海朋，楊義先.混沌蟻群算法及應(yīng)用[M].北京:中國科學(xué)技術(shù)出版社，2013:100-190.

[5]馬良，朱剛，寧愛兵.蟻群優(yōu)化算法[M].北京:科學(xué)出版社，2008:15-160.

[6]邱鐵.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社，2004:50-141.

[7]錢潔，鄭建國.網(wǎng)絡(luò)化制造模式下基于改進(jìn)蟻群算法的供應(yīng)鏈調(diào)度優(yōu)化研究[J].系統(tǒng)工程理論與實踐，2014，34(5):1 267-1 275.

[8]楊信廷，錢建平，范蓓蕾，等.農(nóng)產(chǎn)品物流過程追溯中的智能配送系統(tǒng)[J].農(nóng)業(yè)機(jī)械學(xué)報，2011，42(5):125-130.

[9]蔡延光，張敏捷，蔡顥，等.基于蟻群優(yōu)化算法的同構(gòu)多核任務(wù)分配與調(diào)度[J].江蘇大學(xué)學(xué)報:自然科學(xué)版，2014，35(6):679-684.

[10]王躍崗，車阿大.基于相鄰交換復(fù)合蟻群算法的多產(chǎn)品供應(yīng)鏈調(diào)度優(yōu)化[J].計算機(jī)集成制造系統(tǒng)，2014，20(5):1 171-1 180.

[11]史恩秀，陳敏敏，李俊，等.基于蟻群算法的移動機(jī)器人全局路徑規(guī)劃方法研究[J].農(nóng)業(yè)機(jī)械學(xué)報，2014，45(6):53-57.

[12]張景玲，趙燕偉，王海燕，等.多車型動態(tài)需求車輛路徑問題建模及優(yōu)化[J].計算機(jī)集成制造系統(tǒng)，2010，16(3):543-550.