螞蟻算法在復雜性運輸路徑問題中的應用

賈春梅

摘要:車輛路徑問題中,行駛路線往往取決于一系列約束條件,如配送中心個數,貨物需求量,交發貨時間,車輛容量限制等。要想達到一定的目標,如路程最短,費用最小,時間盡量少,車輛盡量少等,就得借助于合適的算法去解決實際的問題。螞蟻算法在解決著名的旅行商(TSP)問題上已取得了很好的成效,目前已陸續滲透到其他問題的求解上。文章主要針對多車場多車型車輛路徑問題,用蟻群算法以及蟻群算法的優化算法去解決一些實際問題。

關鍵詞:車輛路徑問題;螞蟻算法;優化算法

中圖分類號:O227文獻標識碼:A

Abstract: In the vehicle routing problem(VRP), the traveling route usually depends on a series of restrictive conditions, such as the number of the distribution centers, the quantity of the demanding freight, the delivery time and the vehicle capacity constraints. To achieve a certain goal, such as the shortest distance, the minimum cost, the least time and the vehicles as few as possible and so on, we have to use appropriate algorithms to solve practical problems. Ant algorithm has achieved a good result in solving the well-known traveling salesman problem(TSP), now it has been infiltrated into the other problems' solving. In this paper, mainly for Multiple-depot and Heterogeneous-vehicle vehicle routing problems, we adopt ant algorithm and its improved method to solve some practical problems.

Key words: VRP; ant algorithm; optimization algorithm

1研究背景

根據物流管理中對運輸車輛優化調配的要求,1959年,Dantzig和Ramser[1]首先提出了車輛路徑問題(Vehicle Routing Problem,VRP)的數學模型。近幾十年來,VRP[2]一直都備受學術界關注。VRP和TSP一脈相承,同屬組合優化領域的NP-hard 問題,但因VRP的約束條件眾多,因而其復雜程度也就遠遠高于TSP[3-4]。特別是對于大規模的VRP問題,尋找到高效的精確算法的可能性不大,因此,尋求高效近似的優化算法是非常必要和現實的。國內外專家和學者對VRP及其求解方法進行了大量的研究,提出了許多關于不同類型VRP的不同的求解算法。但往往是解決單一性問題,對復雜問題還缺少深入地研究。

2車輛路徑問題的分類

車輛路徑問題是從任務目標、車輛載貨狀況、車場數目、車輛類型、車輛對車場的所屬關系、是否有時間限制等多個方面進行分類分析,然而現實生活中,往往是多個類型組合的問題。本文結合不同的分類方式,根據蟻群算法以及改進的蟻群算法求解以下四類車輛路徑問題:(1)裝卸混合問題;(2)多車場多車型路徑問題;(3)開放式車輛路徑問題;(4)帶時間窗限制的車輛路徑問題。本文重點分析其中的多車場多車型路徑問題。

3螞蟻算法的原理和算法設計

螞蟻算法(ant algorithm),是一種源于昆蟲世界的新的仿生類算法,作為通用型隨機優化方法,其思想吸收了自然界螞蟻群體的行為特性,通過其內在的搜索機制,在一些典型的困難組合優化問題求解中取得了成效,展現出了廣闊的發展前景。研究表明,對于解決有多種約束條件的VRP,螞蟻算法相對于其它一系列算法,有其更大的優勢。本文側重于運用蟻群算法以及改進的蟻群算法去解決存在一系列約束條件的各類車輛路徑問題[5-6]。

3.1螞蟻行為描述

根據仿生學家的長期研究發現:螞蟻運動時會通過在路上釋放出一種信息素來尋找路徑。結合圖1來形象說明:

圖1中,設A點是蟻巢,E點是食物源。HC為障礙物。一開始從A點到達E點的路徑選擇是隨機的,BHD和BCD路徑上都存在數量相等的螞蟻,顯然螞蟻通過BCD的路徑時間較短,所以在該路徑上的信息素濃度就相對比較大,后來的螞蟻就會選擇信息素濃度較大的路徑。隨著時間的推移,螞蟻將會以越來越大的概率選擇路徑BCD,最終將會完全選擇路徑BCD,從而找到由蟻巢到食物源的最短路徑。螞蟻算法的優越性包括:分布式計算、自組織性、正反饋、啟發性、較強的魯棒性。

3.2基本螞蟻算法的數學模型

假設:有n個城市點需要訪問,共有m只螞蟻,被放置于倉庫位置,螞蟻k從i點出發選擇下一個要到達的城市j點,選擇主要依據于以下兩點:

(1)τt,t時刻從城市i到j路徑上殘留的信息素濃度。

(2)η由城市i轉移到j的可見度,又稱啟發信息。算法給出在t時刻位于城市i的螞蟻k選擇城市j作為目標城市的概率是

Pt=(1)

令tabuk=1,2,…,m為每只螞蟻保存的一個禁忌列表,用于記錄螞蟻k當前已經訪問過的城市,而N

=0,1,2,n-1-tabu則用來記錄到目前為止還未被訪問過的城市,α為信息素的相對重要程度,β為啟發信息的相對重要程度。

當一只螞蟻完成對所有城市的訪問后,信息素開始局部更新,公式如下:

τt+1=1-ρτt+τρ(2)

式中τt表示原來i、j之間的路徑上的信息素濃度,τt+1表示經過一個時間單位后i、j路徑上的信息素濃度,ρ定義為信息素的揮發度,一般取為0,1,則1-ρ即為信息素的殘留度,τ為路徑上的信息素初始濃度,一般設定為一個常數C。

在m只螞蟻全部完成對所有n個城市的訪問后,對殘留信息進行全局更新處理,更新公式如下:

τt+n=1-ρτt+Δτ(3)

式中τt+n表示經過n個時間單位后,i、j路徑上的信息素濃度,Δτ為螞蟻k在時間段t 到t+n的過程中在路徑i、j上留下的殘留信息素。

4基于螞蟻算法對多車場多車型車輛路徑問題(MDMHVRP)的研究

(1)研究現狀

在當前物流領域中,對車輛路徑問題的研究主要集中在單車場問題上,對多車場車輛路徑問題的研究尚不成熟[7]。由于物流行業配送貨物的多樣性,在研究單車場問題上也是結合了多車型的實際情況。為節約物流配送費用,針對單車場多車型路徑問題存在的不足,本文試著對多車場多車型車輛路徑問題(Multi-depots Meta-heuristic Vehicle Routing Problem, MDMHVRP)進行了探討,提出運用自適應最大—最小蟻群算法(adaptive max-min ant colony algorithm, A-MMACA)來解決問題。

(2)MDMHVRP 的數學模型

本文著重考慮了多個車場下運用多種車型[8]進行配送的運輸問題,試建立數學模型如下:

配送貨物由H輛車從m個車場向n個客戶點配送。配送任務可用一個加權圖GV,E來表示,其中節點集V

=1,2,…,n, n+1,…,n+m,V的前n個節點為客戶點,后m個節點為車場點;E=d|i,j∈V代表從節點i到節點j的行駛路徑集合。λ表示路況對配送車輛的影響。標準路況下,λ=1,好于標準路況則λ<1,反之則λ>1,路況系數乘以配送點之間的實際路徑長度d,就是考慮了路況影響之后的等價路徑長度;L是一條可行路徑,fL表示該路徑對應的總費用;客戶i點的需求量為q;Q為車輛h的最大容量;客戶點i的重要性用權值Φ來表示;客戶i點的時間窗為a,b;t為車輛h從客戶i點到客戶j點的行駛時間(或代價);車輛在客戶點i服務所用時間s=s+ξqs=0,它包括固定服務時間s和可變服務時間ξq(用需求量q的系數倍表示);s是一個決策變量,表示車輛h到達客戶點i的時刻。

(3)求解MDMHVRP的算法

1)多車場多車型的選擇步驟

①把各車場中每輛車的信息(所屬車場、車輛編號、車輛型號等)存入一個結構體,結構體的每一個數據表示車輛所在車場的編號,第二個數據表示車輛在該車場內的編號,第三個數據表示車輛型號,不同的型號代表不同的車輛容量。這樣各車場中的車輛就形成了一個車輛序列。

②搜索最適合當前配送任務的車場。

③當搜索過程選中某一個車場時,抽出此車場中車輛的序列。

④按車型從小到大順序進行排列,小車型優先,然后依次派出較大車型。

⑤把車輛序列中車型以約束形式加入路徑,控制路徑的組成。

如果車場2中車輛的型號為1、2、4,路徑初始解為0—4—5—2—0—1—3—0—7—6—0,則車場0的插入點是在1、2、4這個序號順序的車輛的容量限制的影響下產生的,即0—4—5—2—0要滿足車型1的車輛容量要求而路徑0—1—3—0要滿足車型2的車輛容量限制。同樣,其他的性能指標,如不同車輛的最大運行距離、速度大小等都可以以這種形式加入,來影響初始解的產生和優化[9]。

2)自適應最大—最小蟻群算法應用步驟

步驟1以較早的服務開始時間優先服務的規則產生一個可行解fL。

步驟2根據公式

(4)

進一步確定τ、τ,其中ρ表示信息素的揮發系數、fL表示當前較好解所對應的費用、n表示客戶點(節點)個數,τ=1nfL且滿足τ≤τ≤τ。此時Δτ=0, N=0, Lr=0,在接下來的步驟一旦信息素更新后,以公式

(5)

重新確定τ, τ。以便避免過早陷于局部最優解。

步驟3將k只螞蟻均勻分布到各客戶點。

步驟4用狀態轉移概率公式(6)計算螞蟻k的狀態空間轉移概率,選擇下一個目標城市。

P=(6)

步驟5應用局部信息素更新式:

(7)

進行信息更新,探索子路徑。其中,Y表示第k只螞蟻到達節點i之前已有Y只螞蟻經過i點,有y只螞蟻選擇了有向弧段i,j,yY表示有向弧段i,j的螞蟻吸引力,Q表示螞蟻每次釋放的信息量。

步驟6判斷Lr

步驟7輸出當前所有螞蟻的路徑,更新禁忌表,保留最優解。

步驟8判斷是否遍歷所有節點,是就繼續步驟9,否則返回步驟4。

步驟9以信息素水平更新式

τ=1-ρτ+w-μ+1Δτ+wΔτρ∈0,1 (8)

對最好螞蟻進行全局更新,保留全局最優解,禁忌表清空。其中,w表示k只螞蟻在一個循環旅行之后,根據旅行總費用按遞增升序排列,排名前w位的精英螞蟻數量,一般取3～6之間的整數,只有路徑i,j被排名第μ1≤μ≤w的最好螞蟻利用時,其信息才增加w-μ+1Δτ,而Δτ=1fL, fL為第μ最好解的路徑費用。此時所有當前最好路徑上的信息素都被加強wΔτ, Δτ=1fL, L為全局最優解對應的長度。

步驟10判斷N=N是否成立,成立則輸出最優解并結束,否則返回步驟3進行第N+1次的循環。

5總結及展望

當前,物流業正朝著全球化、信息化、一體化發展,正積極融入到國民經濟的各個產業鏈中,物流系統中的配送,也顯示出了越來越重要的作用,而其中的車輛路徑問題隨之成為了物流配送中的核心問題。本文的重點是根據車輛路徑問題的不同方面和側重點進行分類,在前人的研究基礎上對四類車輛路徑問題中的多車場多車型問題進行了深入的研究,并用改進的蟻群算法進行求解。蟻群算法雖作為一種全新的仿生優化算法,但研究中更多是依靠試驗和經驗,而沒有定理來確定,因此在改進方法上仍有很大的空間等待完善,比如關于參數的設置等。另外,文中所考慮的實際的隨機不確定性因素很少,今后要進一步加強對隨機不確定性條件下的車輛路徑優化的研究,綜合盡可能多的實際因素去考慮最優車輛路徑的選擇問題。只要積極朝著關鍵性的問題進行突破,相信螞蟻算法會有更加廣闊的發展空間。

參考文獻:

[1] Dantzig G B, Ramser K B. The Truck Dispatch Problem[J]. Operation Research, 1959,6:81-89.

[2] 李相勇. 車輛路徑問題模型及算法研究[D]. 上海:上海交通大學,2007.

[3] 齊少安,宋齊軍. 基于TSP模型的物流配送中心車輛路徑優化[J]. 郵電設計技術,2006(6):62-64.

[4]M Dorigo and L M Gambardella. Ant Colony System: a Cooperative Learning Approach to the Traveling Salesman Problem [J]. IEEE Transactions on Evolutionary Computation, 1997,1(1):53-66.

[5] Reimann M, Doerner K, Hartl RF. D-Ants: Savings Based Ants Divide and Conquer the Vehicle Routing Problem[J]. Computers & Operations Research, 2004,31(4):563-591.

[6] 郭倩倩. 蟻群算法的改進及其在車輛路徑問題中的應用[D]. 成都:西南交通大學,2007.

[7] 章琦. 蟻群算法在車輛路徑問題中的研究[D]. 學位論文,2006.

[8] 葉志堅,葉懷珍,周道平,等. 多車型車輛路徑問題的算法[J]. 公路交通科技,2005,22(5):147-151.

[9] 劉敏. 多目標遺傳算法在車輛路徑優化中的應用研究[D]. 湘潭:湘潭大學,2006.