溫馨,曾培勇,張全
(沈陽工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,沈陽 110870)
基于QPSO算法的智能公交調(diào)度優(yōu)化研究
溫馨,曾培勇,張全
(沈陽工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,沈陽110870)
針對城市智能公交調(diào)度優(yōu)化問題,在充分考慮公交企業(yè)運(yùn)營成本和乘客候車成本的基礎(chǔ)上,引入乘客抱怨度這一指標(biāo)建立一個三目標(biāo)的公交調(diào)度優(yōu)化模型,并通過線性加權(quán)法,將三個目標(biāo)函數(shù)合并為一個目標(biāo)函數(shù)。由于粒子群算法易陷入局部最優(yōu)的缺點,特引入量子特征,利用量子粒子群算法具有判斷早熟現(xiàn)象和能夠跳出局部最優(yōu)的特點,獲得公交發(fā)車時間間隔的最優(yōu)解。
近年來,隨著國民經(jīng)濟(jì)的飛快發(fā)展,居民擁有機(jī)動車的數(shù)量逐漸增多,交通壓力已經(jīng)過度飽和,這不僅影響了居民的正常生活,也制約了我國經(jīng)濟(jì)的發(fā)展。因此,具有大客運(yùn)量,人均占用道路少的城市公交被認(rèn)為是解決城市交通問題的最佳策略[1]。在日常生活中,由于每天各時段的客流量是隨機(jī)的,而傳統(tǒng)的公交調(diào)度卻采用固定發(fā)車間隔的策略,因而會導(dǎo)致公交車載客量不均、乘車舒適度低的情況。所以,如何改善公交調(diào)度手段、提高公交運(yùn)營效率,是當(dāng)前公交系統(tǒng)面臨的主要問題。
針對上述的不足,本文建立以發(fā)車間隔為變量,公交企業(yè)、乘客利益以及乘客抱怨度為目標(biāo)的模型,采用了量子粒子群算法進(jìn)行智能調(diào)度,以便于同時兼顧乘客和公交企業(yè)的利益。
1.1模型假設(shè)
數(shù)學(xué)模型是對實際問題的抽象、概括,因此不可能考慮到所有的復(fù)雜因素,必須對外部條件做相應(yīng)的限制[2]。本文對公交線路靜態(tài)調(diào)度問題中做出假設(shè):
①本文針對城市公交系統(tǒng)中的一條公交線路,且只考慮單程車運(yùn)行;②同一線路中所有車輛的型號、容量、乘客乘車費(fèi)用相同;③一天被分為不同的時段,且同一時段內(nèi),相鄰兩車的發(fā)車間隔相同;④乘客到達(dá)車站服從均勻分布;⑤乘客按秩序上車,公交車達(dá)到最大滿載率則停止上客;⑥公交車運(yùn)營過程中,忽略交通擁堵或事故等客觀因素。
1.2模型建立
公交線路靜態(tài)調(diào)度優(yōu)化模型旨在確定兼顧乘客和企業(yè)利益的最優(yōu)發(fā)車間隔,是一個多目標(biāo)優(yōu)化。本文主要以乘客候車?yán)?、公交企業(yè)利益,以及乘客抱怨度三者為目標(biāo)建立模型。
(1)符號說明
i:公交站點的數(shù)量,i={1,2,…,m};j:一天內(nèi)不同時段的個數(shù),j={1,2,…,n};tj:第j時段的發(fā)車間隔;Tj:第j時段總的時間長度;nj:第j時段的發(fā)車次數(shù),nj=Tj/tj;C1:乘車費(fèi)用;C2:公交車運(yùn)營一次的費(fèi)用;puij:第j時段第i車站乘客的平均到達(dá)率;pp:一天內(nèi)總的乘客數(shù),pp=乘客等車時間的容忍上限;lr:公交車最低滿載率;hr:公交車最高滿載率;np:公交車額載;tr:乘客容忍的公交車滿載上限;mtj:第j時段最大發(fā)車間隔;pi1:公交車在第i站的上車人數(shù);pi2:公交車在第i站的下車人數(shù);pij:公交車在到達(dá)第j時段第i車站時車上已有的人數(shù),pij=p(i-1)j+pi1-pi2;bp:乘客的等車時間抱怨度(超過乘客的等車時間上限)即:如果tj>htj,則bp存在,否則bp=0;bl:乘客的擁擠程度抱怨度(超過乘客所能容忍的滿載上限)即:如果pij>nj×np×tr,則bl存在,否則bl=0;δ:乘客每分鐘候車時間的費(fèi)用。
(2)目標(biāo)函數(shù)
本文綜合考慮乘客和公交企業(yè)利益,選取企業(yè)利益最大、乘客候車?yán)婧捅г苟?(等車時間和擁擠程度)最小3個目標(biāo)。為了量綱的統(tǒng)一,將其均化為費(fèi)用的函數(shù),即:
公交企業(yè)利益:
乘客候車等待利益:
乘客的抱怨度:
c=bp+bl
等車時間抱怨度:
擁擠程度抱怨度:
通過分析,該模型包括三個目標(biāo):maxa、minb、minc。由于三者間的矛盾性,特引入具有修正主體利益的加權(quán)系數(shù),將其轉(zhuǎn)化為單目標(biāo)函數(shù)[3-5]。因此,該模型的目標(biāo)函數(shù)為:
(3)約束條件
為了獲得更加合理,更好滿足人們出行要求的公交車發(fā)車時刻表,本文對車輛的滿載率以及發(fā)車間隔進(jìn)行了約束。即:公交車的滿載率以及各時段的發(fā)車間隔均具有上下限約束[6]。
①滿載率約束:
②時間間隔約束:
由于兩個約束都是與時間間隔有關(guān)的不等式,因此可整理成下式:
2.1基于粒子群算法的智能公交調(diào)度
粒子群優(yōu)化是由Kennedy和Eberhart[7-8]于1995年提出的一種優(yōu)化算法,是將群體中的個體看作是在N維搜索空間中沒有質(zhì)量和體積的粒子,且每個粒子在解空間中運(yùn)動,并由速度決定它的運(yùn)動方向和距離,同時通過追隨自身的個體最好位置pbest與群體的全局最好位置gbest來實現(xiàn)對候選解的進(jìn)化[9]。
首先初始化一群隨機(jī)粒子,通過多次迭代找到最優(yōu)解。在迭代過程中,每個粒子通過兩個極值(個體極值pbest和全局極值gbest)來不斷更新自己的方向和位置。迭代時,初始化的每個粒子所在的位置即為個體極值,粒子種群最好的位置即為全局極值。當(dāng)完成一次迭代操作后,對每個粒子迭代前后的位置進(jìn)行比較,如果比之前的個體極值好則進(jìn)行更新;再對種群中所有粒子的個體極值進(jìn)行比較,得到所有個體極值中的最優(yōu)解,如果他比之前的全局極值好,則將他更新為全局極值。經(jīng)過多次迭代后,最終得到的全局極值即為所求的最優(yōu)解。在找到這兩個最優(yōu)值時,粒子根據(jù)下面公式來更新自己的速度和位置[10]:
其中,ω為權(quán)重,vi,d表示第i粒子經(jīng)過j次迭代后的速度;xi,d表示第i粒子經(jīng)過j次迭代后的位置;pbest 和gbest分別表示第i粒子經(jīng)過j次迭代后得到的個體極值和全局極值;c1c2為學(xué)習(xí)因子;r1r2為[0,1]區(qū)間的隨機(jī)數(shù)。
2.2基于量子粒子群算法的智能公交調(diào)度
量子粒子群算法是在PSO的思想上引入量子行為,即在進(jìn)化過程中,粒子以一定概率取加或減,更新每個粒子的位置,從而生成新的粒子群體,同時計算個體和全局最好值,并將與上一代比較,好壞更替。以此循環(huán),直到找出符合條件的最優(yōu)解。更新位置公式如下:
其中,b為收縮擴(kuò)張系數(shù),α,u為0到1之間的隨機(jī)數(shù),如果產(chǎn)生的u大于0.5,則取加,反之取減。
假設(shè)公交線路運(yùn)營長度6.4公里,共設(shè)8站,一天內(nèi)的運(yùn)營時間被分為5個時段:6:00-8:30,8:30-12:00,12:00-16:00,16:00-19:00,19:00-21:00,其中6:00-8:30和16:00-19:00是高峰期,19:00-21:00是低峰期,8:30-12:00,12:00-16:00是平峰期。表1和表2分別給出該線路一天各時段統(tǒng)計乘客的上、下車數(shù)量。主要參數(shù)C1=1,C2=36,δ=0.2,lr=0.5,hr=1.2,tr=0.9,np=45,mtj=[12,16,16,12,22],htj=[9,13,13,10,18],λ1= 0.5,λ2=0.3,λ3=0.2。粒子群規(guī)模為200,最大迭代次數(shù)為200。
表1 該線路一天內(nèi)各時段的上車乘客數(shù)
表2 該線路一天內(nèi)各時段的下車乘客數(shù)
對比結(jié)果:
①粒子群算法
②量子粒子群算法
由上述兩種算法結(jié)果對比可以看出,量子粒子群算法求出的結(jié)果更優(yōu)。符合高峰時期車輛發(fā)車間隔小,低峰時期車輛發(fā)車間隔大。
本文在充分考慮公交企業(yè)和乘客利益的基礎(chǔ)上,引進(jìn)乘客的抱怨度,建立了三目標(biāo)函數(shù),并運(yùn)用兩種算法對其進(jìn)行求解,最后發(fā)現(xiàn)量子粒子群算法求出的結(jié)果更優(yōu),更符合實際。它不僅減少了乘客的等車時間以及抱怨度,也減少了公交企業(yè)的運(yùn)營成本。解決了傳統(tǒng)公交固定發(fā)車間隔的缺陷,從而改善了公交服務(wù)質(zhì)量,增強(qiáng)了公交車吸引力,使人們更愿意乘坐公交車出行。
[1]周曉云,吳兆根.RFID在公共交通領(lǐng)域的應(yīng)用[J].中國無線電,2005(5):49-50.
[2]陳茜.城市常規(guī)公交線路車輛調(diào)度優(yōu)化研究[D].東南大學(xué),2003
[3]任曉莉.基于禁忌搜索的智能公交調(diào)度研究[J].測控技術(shù),2014,33(2):124-126.
[4]李治廷.基于粒子群與蟻群混合算法的公交調(diào)度研究[D].大連理工大學(xué),2013,6.
[5]童剛.公交調(diào)度模型及算法.青島科技大學(xué)學(xué)報[J],2004,25(3):253-257.
[6]張曉培.基于遺傳—牛頓算法的公交優(yōu)化調(diào)度[D].長沙理工大學(xué),2011.
[7]Eberhart,R,Kennedy,J.A new optimizer using particle swarm theory[C].Proc.6 Int.Symposium on Micro Machine and Human Science,1995:39-43.
[8]Kennedy,J,Eberhart,R.Particle swarm optimization[C].IEEE International Conference on Neural Networks(Perth,Australia),IEEE Service Center,Piscataway,NJ,1995,IV:1942-1948.
[9]孫俊.量子行為粒子群優(yōu)化:原理及其應(yīng)用.清華大學(xué)出版社.2011,8.
[10]尹相勇.基于實時專家系統(tǒng)的公共交通區(qū)域調(diào)度優(yōu)化模型及實用方法研究[D].北京交通大學(xué),2004.
Intelligent Bus Scheduling;Comfort of Passengers;Linear Weighted;Quantum Particle Swarm Optimization;Departure Interval
Research on the Optimization of Intelligent Bus Scheduling Based on QPSO Algorithm
WEN Xin,ZENG Pei-yong,ZHANG Quan
(School of Information Engineering,Shenyang University of Technology,Shenyang 110870)
1007-1423(2015)26-0007-04
10.3969/j.issn.1007-1423.2015.26.002
2015-09-01
2015-09-10
智能公交調(diào)度;乘客抱怨度;線性加權(quán)法;量子粒子群算法;發(fā)車時間間隔
In view of the city intelligent bus scheduling optimization problem,based on the full consideration of the bus company operating costs and the passengers waiting costs,establishes a bus scheduling optimization model with three goals by introducing an additional factor,i.e.,the comfort of passengers.By means of the linear weighted method,integrates three objective functions.Since the particle swarm optimization algorithm is easy to fall into local optimum,uses the QPSO to achieve the optimal solution of bus departure interval by its capacity of judging precocious phenomena and jumping out of local optimum.