多目標蟻群算法城市車輛調度站部署的研究*

黃兆年 李海山 趙 君

(武漢數(shù)字工程研究所 武漢 430205)

?

多目標蟻群算法城市車輛調度站部署的研究*

黃兆年 李海山 趙 君

(武漢數(shù)字工程研究所 武漢 430205)

因為蟻群算法在解決NP難問題有很多優(yōu)勢,正反饋機制可以引導整個系統(tǒng)向最優(yōu)解的方向進化,最后得出最優(yōu)解,來解決國內城市運營費用非常大、車輛調度站和交通樞紐部署不合理的問題。

蟻群算法; 車輛調度站部署; 運營費用

Class Number TP301

1 引言

車輛調度站部署問題關鍵在于部署車輛調度站到城市的交通節(jié)點上,使整個交通的總體車流量達到最小,同時使整個交通系統(tǒng)的運營費用也達到最小。

假設武漢市交通樞紐的數(shù)目為M,車輛調度站的數(shù)目為N,車輛調度站部署到交通樞紐的解空間為MN,是一個類似于裝箱問題的NP-hard問題[3],需要找到一個近似優(yōu)化解。很多啟發(fā)式算法被提出用來解決這個問題,比較典型的為貪心算法。本文將車輛調度站部署問題定義為一個多目標優(yōu)化問題,同時優(yōu)化兩個目標:最小化的交通樞紐的數(shù)量來優(yōu)化武漢龐雜的交通問題;最小化車輛來改善武漢市公交車的總車輛流量。

2 問題建模

設車輛調度基站的集合為CAR={car1,car2,…,carn},交通樞紐集合TRANS={trans1,trans2,…,transm},交通樞紐總數(shù)為m。調度基站部署到交通樞紐的方案為一個映射函數(shù)f(x),其中x為調度站,函數(shù)值為調度站部署的交通樞紐。

2.1 交通費用模型

為了充分利用多維資源,第j個交通調度站用定義為人員總費用和車輛的運營費用,具體描述為

(1)

設yj表示車輛調度站i是否放置在交通樞紐j上,則交通線路上所有交通樞紐的運營費用為

(2)

2.2 城市交通線路流量模型

相鄰交通樞紐間車輛流量用n×n矩陣表示,車輛調度站間的距離用m×m矩陣表示,具體描述為

其中,dij為交通樞紐i發(fā)送到交通樞紐j的車流量,cij為調度站i到調度站j的距離。

那么整個交通系統(tǒng)網(wǎng)絡總流量為

(3)

2.3 多目標優(yōu)化

本文優(yōu)化目標包含最小化交通樞紐運營費用和最小化網(wǎng)絡總流量,因此將車輛調度站放置問題建模為一個多目標優(yōu)化問題。具體描述為

(4)

(5)

Subject to:

yi,xij∈{0,1} ?j∈{1,…,m} and ?i∈{1,…,n}

其中,第一條限制條件表示yj、xij的取值范圍,0為否,1為是;第二條限制條件表示一個車輛調度站只能放置到一個交通樞紐上。

3 改進蟻群算法優(yōu)化

3.1 改進ACO算法

蟻群算法(Ant Colony Optimization,ACO),又稱螞蟻算法,是一種用來在圖中尋找優(yōu)化路徑的機率型算法。它由Marco Dorigo于1992年在其博士論文中提出,其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進化算法,初步的研究表明該算法具有許多優(yōu)良的性質。

3.2 信息素定義

信息素表示車輛調度站放置到指定交通樞紐上的支持率。信息素強度越大越選擇當前交通樞紐。改進ACO算法信息素包含兩種信息素,分別為數(shù)據(jù)中心交通樞紐資源浪費信息素和網(wǎng)絡總流量信息素。

交通樞紐資源浪費信息素初始值和交通網(wǎng)絡總流量信息素初始值分別為

(6)

(7)

其中,W0為初始車輛調度站放置方案下根據(jù)式(2)計算得到運營費用,T0為初始車輛調度站放置方案下根據(jù)式(3)計算得到的整個交通網(wǎng)絡車輛總流量,i為車輛調度站,j為交通樞紐。

3.3 啟發(fā)信息定義

啟發(fā)信息表示將車輛調度站放置到指定交通樞紐的期望程度。使用網(wǎng)絡總流量增加值ΔT來表示啟發(fā)信息。計算方法如下:

算法1 總流量增加值計算。

輸入:待放置的車輛調度站A,考察的交通樞紐B;

輸出:交通總車流量增加值ΔT。

步驟:

1) 令ΔT=0;

2) 遍歷dAj(j=1,2,…,nandj≠A),如果車輛調度站j已放置,ΔT=ΔT+dAj×cBf(j);

3) 遍歷diA(i=1,2,…,nandi≠A),如果車輛調度站i已放置,ΔT=ΔT+diA×cf(i)B;首先假設車輛調度站放置到指定交通樞紐上,然后根據(jù)式(2)計算當前交通樞紐的總費用。

為了兼顧考慮最小化交通樞紐資源浪費和最小化網(wǎng)絡總流量,啟發(fā)信息計算公式為

(8)

其中,i為車輛調度站,j為交通樞紐。啟發(fā)信息越大,越大概率選擇該交通樞紐放置車輛調度站。

3.4 狀態(tài)轉移規(guī)則

螞蟻在車輛調度站i選擇交通樞紐j的規(guī)則為狀態(tài)轉移規(guī)則的定義如下:

(9)

其中,i為車輛調度站;j為交通樞紐;τij,w的初始值用式(6)計算;τij,t的初始值用式(7)計算;啟發(fā)信息ηij使用式(8)計算;Ωk(i)為滿足車輛調度站i需求的所有交通樞紐集合;σ是在每次選擇中生成的0到1范圍內的隨機數(shù),是兩種信息素相對重要性系數(shù),可以增強對解空間的搜索、避免陷入局部最優(yōu)解;α為信息素因子;β為啟發(fā)信息因子;q0為狀態(tài)轉移概率,是0～1范圍內的實數(shù)。

每步選擇時,生成0～1范圍內的一個隨機數(shù)q,當q≤q0時,在滿足車輛調度站i資源需求的交通樞紐集合中,根據(jù)式(10)選擇具備最大值的交通樞紐;當q>q0,隨機選擇一個滿足車輛調度站i資源需求的交通樞紐,增強了搜索的隨機性且降低了計算復雜性。

3.5 信息素局部更新規(guī)則

在螞蟻每一步搜索完成時,都需要對該步信息素進行更新,這種規(guī)則為信息素局部更新規(guī)則。良好的信息素局部更新規(guī)則可以有效地減少信息素,避免陷入局部最優(yōu)解。交通樞紐運營費用和交通總體流量信息素局部更新規(guī)則計算公式為

τij,w(t)=(1-ρl)×τij,w(t-1)+ρl×τ0,w,

τij,t(t)=(1-ρl)×τij,t(t-1)+ρl×τ0,t

(10)其中,ρl為信息素局部蒸發(fā)系數(shù),取值范圍為0～1。

3.6 信息素全局更新規(guī)則

在蟻群每一次迭代完成時,需要對Pareto[4]解集中所有最優(yōu)解構建的車輛調度站放置方案進行信息素更新,更新規(guī)則為信息素全局更新規(guī)則。交通樞紐資源浪費信息素全局更新規(guī)則和網(wǎng)絡總流量信息素全局更新規(guī)則計算公式如下:

τij,w(t)=(1-ρg)×τij,w(t-1),

τij,t(t)=(1-ρg)×τij,t(t-1)

(11)

其中,ρg為信息素全局蒸發(fā)系數(shù),取值范圍為0～1;λ為當前迭代過程Pareto解集中最優(yōu)解的個數(shù)。

3.7 算法描述

下面介紹改進ACO算法的具體流程。

基于多目標蟻群優(yōu)化的車輛調度站放置算法的步驟如下:

2)NA個螞蟻分別建立車輛調度站放置方案。每個螞蟻建立方案過程:(1)隨機排列車輛調度站表、交通樞紐表;(2)響應車輛調度站表中一個車輛調度站放置請求,根據(jù)式(9)為車輛調度站選擇合適的交通樞紐,放置車輛調度站到該交通樞紐上,從車輛調度站表中刪除該車輛調度站;(3)根據(jù)式(11)更新該步的兩個信息素τij,w(t)和τij,t(t);(4)如果車輛調度站表非空,返回(2),否則方案建立過程結束。

3) 根據(jù)交通樞紐資源浪費最小化和網(wǎng)絡總流量最小化兩目標,評估步驟2產(chǎn)生的NA個解,更新Pareto最優(yōu)解集合P。

4) 遍歷P中所有最優(yōu)解,根據(jù)式(6)、式(7)分別對交通樞紐資源浪費信息素τij,w(t)和總車流量信息素τij,t(t)進行全局更新。

5) 迭代次數(shù)加1。如果迭代次數(shù)小于迭代次數(shù),跳到步驟2);否則跳到步驟6)。

6) 算法結束,輸出Pareto最優(yōu)解集P。

4 數(shù)據(jù)實驗及分析

上述算法在Java平臺上實現(xiàn),在XP環(huán)境下運行,實現(xiàn)了改進ACO算法和FFD算法。仿真實驗使用100個車輛調度站,100個交通樞紐,1個車輛流量矩陣,1個交通樞紐距離矩陣。通信目的虛擬機隨機選擇,交通樞紐的車輛流量是[1,100]范圍內的隨機整數(shù),由此生成車輛流量矩陣。設置α=1,β∈{1,2},q0∈{0.1,0.4,0.6,0.9},迭代次數(shù)為100,運行10次取平均結果,如圖1所示。

圖1 結果圖

如圖1結果所示, 1) 貪心算法得出的結論比蟻群算法得出的結果要大; 2) 兩個蟻群算法都收斂,而且這兩個矛盾的變量存在多個近似最優(yōu)解,決策者可以根據(jù)自己的需要來選擇一個最佳的方案。試驗中進行多次迭代,圖1只顯示了兩次迭代的結果。不同的迭代會產(chǎn)生不同的方案,可以通過多次迭代來產(chǎn)生很多個近似最優(yōu)解,這樣結果更加準確。從其他文獻中知道q0=0.9時算法比其他參數(shù)組合算法收斂性好,本文直接設置q0=0.9,但是作為實驗,可以設置不同的q0,來觀察算法的收斂性。

5 結語

本文首先介紹了蟻群算法在多目標優(yōu)化中的研究,并且結合現(xiàn)在普遍的城市交通比較復雜的NP難問題,通過Pareto多目標優(yōu)化算法得出多個相似最優(yōu)解,來解決這個NP難問題。當問題比較復雜,不能明確判斷是否到某一代就進化到達到最優(yōu),當種群中個體的適應度值在一定代數(shù)內沒有提高時,就讓這個算法停止,多目標優(yōu)化得到的不是一個解,而是Pareto最優(yōu)解的集合。

[1] 王晶,方偉,陳靜怡,等.云計算環(huán)境下的自適應資源管理技術綜述[J].上海市重點學科基金項目,2011,9(22):172-174.

[2] 李強,郝沁汾,肖利民,等.云計算中虛擬機放置的自適應管理與多目標優(yōu)化[J],計算機學報,2011,12(1):5-8.

[3] 張錦,謝克明.蟻群算法在醫(yī)藥物品配送路徑優(yōu)化中的應用[J].太原理工大學學報,2009(6):600-603.

[4] 徐滬萍,姚念.基于物聯(lián)網(wǎng)的醫(yī)藥物流管理信息系統(tǒng)研究[J].武漢理工大學學報(信息與管理工程版),2013(3):361-364.

[5] 熊道勇,肖人岳.遺傳算法和螞蟻算法混合求解旅行商問題[J].科學技術與工程,2009(10):5817-5819.

[6] 張文潔,鄧衛(wèi).基于蟻群算法的動態(tài)路徑選擇問題[J].交通科技與經(jīng)濟,2009,11(1):51-53.

[7] 谷遠利,李善梅,邵春福.基于蟻群算法的交通控制與誘導協(xié)同研究[J].系統(tǒng)仿真學報,2008,20(10):2754-2761.

[8] SONG Ying, WANG Hui, LI Yaqiong, et al. Multi-tiered ondemand resource scheduling for VM-based data center[C]//Shanghai: Intemational Symposium on Cluster, Cloud and Grid Computing,2009:148-155.

[9] Vasileios Pappas. ZHANGu Improving the scalability of data center networks with traffic-Aware virtual machine[C]//SanDiego, CA: IEEE INFOCOM,2010:1-9.

[10] Deb K, Thiele L, Laumanns M, et al. Scalable multi-objective optimization test problems[C]//Fogel DB, ed. Proc. of the IEEE Congress on Evolutionary Computation, CEC 2002. Piscataway: IEEE Service Center,2002:825-830.

A Multi-objective Ant Colony Optimization Algorithm for Vehicle Scheduling Transportation Placement

HUANG Zhaonian LI Haishan ZHAO Jun

(Wuhan Digital Engineering Institute, Wuhan 430205)

Because the ACO in solving the NP hard problems has many advantages, positive feedback mechanism can guide the whole system evolution in the direction of the optimal solution. Finally optimal solution is obtained to solve the domestic urban traffic operating expenses, vehicle scheduling transportation hub unreasonable deployment problem.

ant colony optimization, vehicle scheduling transportation hub, urban traffic operating expenses

2015年2月5日,

2015年3月29日

黃兆年,男,碩士研究生,研究方向:系統(tǒng)結構,容錯技術。李海山,男,博士,研究員,研究方向:容錯技術。趙君,男,博士,高級工程師,研究方向:網(wǎng)絡通信。

TP301

10.3969/j.issn1672-9730.2015.08.012