螞蟻算法在配送運輸問題上的路徑優化研究?

馮豪杰

（河南理工大學礦山空間信息技術國家測繪地理信息局重點實驗室 焦作 454003）

1 引言

隨著經濟持續不斷發展，我國物流需求規模只增不減，隨之而來的是物流成本逐年攀升，配送車輛調度問題在企業運營中的作用越來越大，確切需要在物流配送成本方面制定新對策，去促進降低成本，從而提高其經營運營能力，這對物流業的發展具有重大的現實與實際意義［1～4］。車輛路徑問題和車輛排程問題統稱為物流配送車輛優化調度問題，該問題的提出，就受到、網絡分析、圖論、計算機應用、組合數學等學科的專家與運輸計劃制定者以及管理者的極大重視，并進行了大量的理論研究和實驗驗證，將其研究成果運用在運輸、配送等系統中［5～6］。

2 螞蟻算法的原理

根據仿生學家的長期研究發現：在覓食的過程中螞蟻雖沒有視覺，但會在走過的路徑上釋放一種特殊分泌物—信息素［7～8］，該信息素會被伙伴識別，碰到一個沒有走過的路口時，會隨機挑選一條路徑行走，同時釋放等量的信息素，路徑越長則在這條路徑上消耗的時間越多，信息素揮發的越多，相反，遺留的信息素濃度越低［9～12］。當后來的螞蟻再遇到某個路口時，信息素濃度高的路徑被選中的概率較大，這樣便形成了一個正反饋機制［13～15］。最優路徑上的信息素濃度越來越高，其他路徑上信息素濃度會隨著時間的流逝而逐漸消減，甚至消失，最終整個蟻群會找出最優路徑［16～17］。圖1為螞蟻算法的最短路徑與原理示意圖。

圖1中表示60只螞蟻要經過障礙物尋找到食物。

T=0時刻：ABC與ADC兩段路都是30只螞蟻；

T=10時刻：ABC與ADC兩段路分別為45、15只螞蟻；

T=20時刻：ABC與ADC兩段路分別為60、0只螞蟻。

圖1 螞蟻算法原理

3 路徑優化的螞蟻算法設計與實現

傳統螞蟻算法是一種理想化狀態，沒有考慮到現實生活中諸多細節。在覓食過程中沒有考慮到天氣狀況、路狀、搜索時間過長以及揮發系數等，需要把這些因素綜合全部考慮到該算法中。

3.1 相關系數的改進

螞蟻算法雖具有全局性特征，但通常會忽略局部環境中的相關因素的影響，這也是在長時間路徑選擇中需要考慮的。路徑選擇次數的增多，路徑上的信息素濃度會逐漸揮發掉，此時我們要考慮局部信息素濃度揮發程度，用揮發系數β來控制信息素濃度的揮發程度，β的大小直接關系到螞蟻群算法的全局搜索能力及其收斂速度，因此通過自適應的調整β的大小來提高算法的全局性，0≤β≤1。

假設β的初始值為1，當蟻群算法求得的最優解在有限次循環內沒有明顯改進時，β以下式作自適應調整：

其中 βmin為 β的最小值，可以防止 β過小降低算法的收斂速度。

在經過時間t1后，蟻群會完成路徑的一個循環選擇，這時殘留在每條路徑上的信息素濃度為

式中Q表示信息素濃度，影響算法的收斂快慢，通常為常數；LK表示螞蟻K在本次循環中走過的所有路徑的總長度。

3.2 局部最優的改進

由于初始信息素濃度相等，導致開始時螞蟻盲目搜索，產生大量無關路徑，對信息素濃度局部更新產生誤導。該問題不僅會導致初始搜索時間過長，并且無關路徑信息素濃度被加強，阻礙最優路徑搜索過程。本文根據無向圖路徑信息，在初始信息素濃度時加入方向性引導，初始化信息素公式修改如下：

其中Q表示信息素濃度，代表每次搜索分配的總信息素，一般為給定的參數；dij，djk分別表示節點j與起點i和終點k的直線距離。起點i與終點k的最短距離為兩點之間的直線距離，從式（4）中可以得出，當節點j越趨于連線ik時，（dij+djk）越小，則X（0）越大，蟻群越傾向于選擇該節點方向為移動的方向；反之，則偏離該節點。該算法在搜索起始點時對節點引入不同權值，對起始搜索產生很合理的方向引導，減弱了對較長路徑的搜索，從而加速了尋找到全局最優解的速度。

3.3 配送運輸路徑優化算法的實現

物流業發展中，對車輛配送路徑優化問題的求解方面，可借助人工螞蟻替代車輛來服務客戶點，返回到配送中心的標準是下一個服務客戶點的運載總量比最遠行駛距離或是汽車載重量多的時候，并不同車輛完成的此次運輸，在此基礎上，車輛可以對其他客戶進行全方位服務，繼而該車輛的人工螞蟻就可以完成一次巡游標志，該標記是對客戶進行的一次服務，一次服務也可以是一次循環，之后，需要根據螞蟻巡游路徑的時間長短將其他信息素進行分配，從而更好地對信息素增量進行不同程度的更新，以此進行不斷的更新，得到最優路徑或是選擇相同路徑，這樣就可以完成求解了。

3.4 實例驗證

為了驗證本文改進算法的優越性與有效性，選擇AutoCAD進行實例驗證。將基本螞蟻算法與本文改進的算法所得到的具體參數就行對比，可得到如表1的結果。

表1 兩種算法的對比

從表1中可以看出，在使用的車輛是相同的情況下，本文的算法到達目的地所使用的行程更短，說明本文算法在通行效率上更具有優勢。

4 結語

針對實際道路配送運輸問題，本文提出了改進的螞蟻算法，對相關系數的改進和對局部最優的優化為突破口。實例驗證本文算法在行駛里程等方面更具有優越性。