陳 文，鄭少鋒

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

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

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

1 蟻群算法

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

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

1.1 研究目的

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

1.2 研究的對象

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

1.3 研究方法

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

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

規(guī)則2 移動：人工螞蟻只會沿著路線橋覓食，當走到結(jié)點（覓食點），人工螞蟻會判斷是否有信息素及其濃度，優(yōu)先選擇信息素濃度大的路線橋為路徑；同時會有一定的概率，隨機選擇別的路線橋；如路線橋上均無信息素則隨機選擇路線橋。

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

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

2 研究步驟

2.1 初始化結(jié)點

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

表1 zuobiao表

表2 jiedian表

2.2 信息素表示

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

表3 xinxisu表

2.3 初始化禁忌表

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

表4 jinji表

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

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

2.5 參數(shù)選取

（1）隨機小概率為0.05，結(jié)點6個，信息素對精英螞蟻獎勵+3，對一般螞蟻+1，信息素揮發(fā)速率為1/輪。

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

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

2.6 進行演算

覓食結(jié)點的狀態(tài)選取3種狀態(tài)：離散型、聚合型、平均型；隨機小概率事件按分形理論選取20個不同的參數(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 只；為了剔除異常收斂，每輪均進行10次演算求出平均值，作為該輪穩(wěn)定的最短路徑。綜合考慮狀態(tài)的聚合度、覓食結(jié)點個數(shù)、隨機小概率事件，通過編程和建立數(shù)據(jù)庫，模擬最優(yōu)路線結(jié)果如下：

3 實例分析

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

表5 10個配送點坐標

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

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

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

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

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

[5]許慧，王正友，楊歡慶.蟻群算法及其聚類應(yīng)用[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].經(jīng)濟論從，2012(4):281-298.