基于QPSO算法的智能公交調度優化研究

溫馨，曾培勇，張全

（沈陽工業大學信息科學與工程學院，沈陽　110870）

基于QPSO算法的智能公交調度優化研究

溫馨，曾培勇，張全

（沈陽工業大學信息科學與工程學院，沈陽110870）

針對城市智能公交調度優化問題，在充分考慮公交企業運營成本和乘客候車成本的基礎上，引入乘客抱怨度這一指標建立一個三目標的公交調度優化模型，并通過線性加權法，將三個目標函數合并為一個目標函數。由于粒子群算法易陷入局部最優的缺點，特引入量子特征，利用量子粒子群算法具有判斷早熟現象和能夠跳出局部最優的特點，獲得公交發車時間間隔的最優解。

0　引言

近年來，隨著國民經濟的飛快發展，居民擁有機動車的數量逐漸增多，交通壓力已經過度飽和，這不僅影響了居民的正常生活，也制約了我國經濟的發展。因此，具有大客運量，人均占用道路少的城市公交被認為是解決城市交通問題的最佳策略［1］。在日常生活中，由于每天各時段的客流量是隨機的，而傳統的公交調度卻采用固定發車間隔的策略，因而會導致公交車載客量不均、乘車舒適度低的情況。所以，如何改善公交調度手段、提高公交運營效率，是當前公交系統面臨的主要問題。

針對上述的不足，本文建立以發車間隔為變量，公交企業、乘客利益以及乘客抱怨度為目標的模型，采用了量子粒子群算法進行智能調度，以便于同時兼顧乘客和公交企業的利益。

1　智能公交調度模型

1.1模型假設

數學模型是對實際問題的抽象、概括，因此不可能考慮到所有的復雜因素，必須對外部條件做相應的限制［2］。本文對公交線路靜態調度問題中做出假設：

①本文針對城市公交系統中的一條公交線路，且只考慮單程車運行；②同一線路中所有車輛的型號、容量、乘客乘車費用相同；③一天被分為不同的時段，且同一時段內，相鄰兩車的發車間隔相同；④乘客到達車站服從均勻分布；⑤乘客按秩序上車，公交車達到最大滿載率則停止上客；⑥公交車運營過程中，忽略交通擁堵或事故等客觀因素。

1.2模型建立

公交線路靜態調度優化模型旨在確定兼顧乘客和企業利益的最優發車間隔，是一個多目標優化。本文主要以乘客候車利益、公交企業利益，以及乘客抱怨度三者為目標建立模型。

（1）符號說明

i：公交站點的數量，i=｛1，2，…，m｝；j：一天內不同時段的個數，j=｛1，2，…，n｝；tj：第j時段的發車間隔；Tj：第j時段總的時間長度；nj：第j時段的發車次數，nj=Tj/tj；C1：乘車費用；C2：公交車運營一次的費用；puij：第j時段第i車站乘客的平均到達率；pp：一天內總的乘客數，pp=乘客等車時間的容忍上限；lr：公交車最低滿載率；hr：公交車最高滿載率；np：公交車額載；tr：乘客容忍的公交車滿載上限；mtj：第j時段最大發車間隔；pi1：公交車在第i站的上車人數；pi2：公交車在第i站的下車人數；pij：公交車在到達第j時段第i車站時車上已有的人數，pij=p（i-1）j+pi1-pi2；bp：乘客的等車時間抱怨度（超過乘客的等車時間上限）即：如果tj＞htj，則bp存在，否則bp=0；bl：乘客的擁擠程度抱怨度（超過乘客所能容忍的滿載上限）即：如果pij＞nj×np×tr，則bl存在，否則bl=0；δ：乘客每分鐘候車時間的費用。

（2）目標函數

本文綜合考慮乘客和公交企業利益，選取企業利益最大、乘客候車利益和抱怨度 （等車時間和擁擠程度）最小3個目標。為了量綱的統一，將其均化為費用的函數，即：

公交企業利益：

乘客候車等待利益：

乘客的抱怨度：

c=bp+bl

等車時間抱怨度：

擁擠程度抱怨度：

通過分析，該模型包括三個目標：maxa、minb、minc。由于三者間的矛盾性，特引入具有修正主體利益的加權系數，將其轉化為單目標函數［3-5］。因此，該模型的目標函數為：

（3）約束條件

為了獲得更加合理，更好滿足人們出行要求的公交車發車時刻表，本文對車輛的滿載率以及發車間隔進行了約束。即：公交車的滿載率以及各時段的發車間隔均具有上下限約束［6］。

①滿載率約束：

②時間間隔約束：

由于兩個約束都是與時間間隔有關的不等式，因此可整理成下式：

2　模型求解

2.1基于粒子群算法的智能公交調度

粒子群優化是由Kennedy和Eberhart［7-8］于1995年提出的一種優化算法，是將群體中的個體看作是在N維搜索空間中沒有質量和體積的粒子，且每個粒子在解空間中運動，并由速度決定它的運動方向和距離，同時通過追隨自身的個體最好位置pbest與群體的全局最好位置gbest來實現對候選解的進化［9］。

首先初始化一群隨機粒子，通過多次迭代找到最優解。在迭代過程中，每個粒子通過兩個極值（個體極值pbest和全局極值gbest）來不斷更新自己的方向和位置。迭代時，初始化的每個粒子所在的位置即為個體極值，粒子種群最好的位置即為全局極值。當完成一次迭代操作后，對每個粒子迭代前后的位置進行比較，如果比之前的個體極值好則進行更新；再對種群中所有粒子的個體極值進行比較，得到所有個體極值中的最優解，如果他比之前的全局極值好，則將他更新為全局極值。經過多次迭代后，最終得到的全局極值即為所求的最優解。在找到這兩個最優值時，粒子根據下面公式來更新自己的速度和位置［10］：

其中，ω為權重，vi，d表示第i粒子經過j次迭代后的速度；xi，d表示第i粒子經過j次迭代后的位置；pbest 和gbest分別表示第i粒子經過j次迭代后得到的個體極值和全局極值；c1c2為學習因子；r1r2為［0，1］區間的隨機數。

2.2基于量子粒子群算法的智能公交調度

量子粒子群算法是在PSO的思想上引入量子行為，即在進化過程中，粒子以一定概率取加或減，更新每個粒子的位置，從而生成新的粒子群體，同時計算個體和全局最好值，并將與上一代比較，好壞更替。以此循環，直到找出符合條件的最優解。更新位置公式如下：

其中，b為收縮擴張系數，α，u為0到1之間的隨機數，如果產生的u大于0.5，則取加，反之取減。

3　仿真結果分析

假設公交線路運營長度6.4公里，共設8站，一天內的運營時間被分為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分別給出該線路一天各時段統計乘客的上、下車數量。主要參數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。粒子群規模為200，最大迭代次數為200。

表1　該線路一天內各時段的上車乘客數

表2　該線路一天內各時段的下車乘客數

對比結果：

①粒子群算法

②量子粒子群算法

由上述兩種算法結果對比可以看出，量子粒子群算法求出的結果更優。符合高峰時期車輛發車間隔小，低峰時期車輛發車間隔大。

4　結語

本文在充分考慮公交企業和乘客利益的基礎上，引進乘客的抱怨度，建立了三目標函數，并運用兩種算法對其進行求解，最后發現量子粒子群算法求出的結果更優，更符合實際。它不僅減少了乘客的等車時間以及抱怨度，也減少了公交企業的運營成本。解決了傳統公交固定發車間隔的缺陷，從而改善了公交服務質量，增強了公交車吸引力，使人們更愿意乘坐公交車出行。

［1］周曉云，吳兆根.RFID在公共交通領域的應用［J］.中國無線電，2005（5）：49-50.

［2］陳茜.城市常規公交線路車輛調度優化研究［D］.東南大學，2003

［3］任曉莉.基于禁忌搜索的智能公交調度研究［J］.測控技術，2014，33（2）：124-126.

［4］李治廷.基于粒子群與蟻群混合算法的公交調度研究［D］.大連理工大學，2013，6.

［5］童剛.公交調度模型及算法.青島科技大學學報［J］，2004，25（3）：253-257.

［6］張曉培.基于遺傳—牛頓算法的公交優化調度［D］.長沙理工大學，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］孫俊.量子行為粒子群優化：原理及其應用.清華大學出版社.2011，8.

［10］尹相勇.基于實時專家系統的公共交通區域調度優化模型及實用方法研究［D］.北京交通大學，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

智能公交調度；乘客抱怨度；線性加權法；量子粒子群算法；發車時間間隔

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.