改進的粒子群優化算法求解車輛調度問題

摘 要：采用對基本粒子群優化算法引入遺傳操作來提高種群多樣性，這樣雖能避免產生局部極小，但收斂速度會降低，通過加入收縮因子來達到兩者的均衡。優化和仿真結果表明改進算法性能更優，能有效地解決公交車輛的智能排班問題。

關鍵詞：粒子群優化；遺傳算子；收縮因子；車輛調度

中圖分類號：TP301.6 文獻標志碼：A

文章編號：1001-3695(2008)09-2674-02



Improved particle swarm optimization method to solve vehicle dispatching problem

LEI Xiujuan1，2，SHI Zhongke2，FU Ali1

(1.College of Computer Science， Shaanxi Normal University， Xi’an 710062， China;2.College of Automation， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:This paper introduced an improved method，which was to achieve a balance between diversity of population and convergence rate through combining the genetic operator and constriction factor. The optimization and simulation results show that the performance of the improved PSO is more excellent and it can solve the intelligent dispatch problem of public transportation effectively.

Key words:particle swarm optimization (PSO);genetic operator；constriction factor；vehicle dispatch

公共交通是城市交通的重要組成部分，做好公交車的調度對于完善城市交通環境、改進市民出行狀況、提高公交公司的經濟和社會效益都具有重要意義。公交調度必須考慮乘客的利益及企業的運營成本，屬于多目標優化問題。本文采用改進的基于遺傳算子的粒子群優化算法來求解此問題。

1 模型

在給出給定路線下的車輛調度模型前，首先要作一些簡化和假設，將實際問題轉換為一個數學問題。對此種情況下的車輛調度建立模型^[1，2]，需作如下假設：a）針對城市公交系統中的某一路線公交車輛調度；b）模型建立時只考慮這一路線的單行情況；c）這一路線的各公交車輛為同一車型；d）這一路線的每輛公交車經過各個車站時不存在留有乘客的現象；e）在同一時間段內的相鄰兩輛公交車發車的時間間隔相等；f）各時段乘客到站服從均勻分布；g）公交車各個站間運行時間一定；h）全程票價統一。

在上述模型的假設條件下，某一固定路線下的公交車輛調度問題描述如下：在一個公交車輛調度問題中，已知某一總里程為L的公交路線總共有J個車站；公交公司的車輛一天的運營時間為且運營時間可分成K個時段，第K個時段的發車間隔為Δtk；此路線的公交車輛型號是相同的，并且按時到達各站；每個車站的乘客服從均勻分布，每個乘客全程的公交票價為n。現從公交公司的運行盈利和公交公司的服務水平（乘客的等待時間最短）兩方面出發，根據一天各個站點的乘客流量以及運營條件求解此路線的車輛運行時刻表，即運營時間各個時段的發車時間間隔。

模型中決策變量的選取是否合理關乎函數模型與實際問題之間是否匹配。根據以上公交車輛調度問題的描述，所要得到的是車輛的發車間隔，因此模型中的決策變量是Δtk，k∈K。其中K={1，…，k，…，K}，表示第k個時段的發車間隔。

1.1 目標函數和約束條件^[1]

公交車輛調度既要考慮公交公司的利益也要充分考慮乘客的利益，因此設定公交車輛調度問題的目標函數時從以下兩個方面考慮：a)從公交公司的角度出發，使公交公司的發車次數最少來保證公司的利益，也即公交公司的運營成本最低。b)從乘客的角度出發，使得全天所有乘客的等車時間最小來保證乘客的利益，也即乘客等車所損失的費用最低。

模型的約束條件主要考慮兩個方面：a)發車的最小間隔和最大的時間間隔要滿足有關部門的規定；b)公交公司要盈利，必須使公交公司所收得的票錢總和要大于公交公司最低的消耗成本，也就是要滿足下式：

00；將全天按客流劃分為早高峰、上平峰、下平峰、晚高峰、低谷五個時段，即模型中的k=5。具體時間段各站客流量如表1所示^[2]。

時間段站點/人

1234

6：00~8：306746254939

8：30~12：00495374133282

12：00~16：00190119232316

16：00~19：00515507355324

19：00~21：00909934105

仿真中算法的初始化參數如下：粒子群規模20，學習因子c1=c2=1，交叉概率.5，變異概率Pm=0.05，最大迭代數T=200，試驗中取n的值均為1，在實際情況中可以根據需要取值。

這里要說明的是目標函數中α、β值不同優化的結果也會不同。圖1是α=0.8，β=0.2時的種群分布圖。對于α=0.5，β=0.5以及α=0.2，β=0.8的圖類似，不再給出。表2中，α=0.8，β=0.2時最優化得到的結果是=（18，20，20，10，19），也就是發車間隔為（18，20，20，10，19），對應的發車次數為（8，10，12，18，6），f(xmin)= 454.269 5，也就是最小費用為454.269 5，其他類似。

由仿真結果來看，α、β對優化結果的影響是很大的。α值越大，即充分考慮公交公司的利益；β值越大，即充分考慮乘客的利益；α、β均為0.5，也就是將公交公司的利益和乘客利益視為平等的地位。從優化后得到的發車次數來看，當充分考慮乘客利益時，發車頻率就高一些，隨著α值的減小、β值的增大，發車頻率逐漸增大。從另一方面來看，在早高峰、晚高峰客流量較大，發車頻率較高；低谷時客流量較少，發車頻率也隨之減少，基本符合實際情況。計算結果比文獻[2]采用遺傳算法進行優化得到的結果更優。

4 結束語

本文采用在收縮因子的基礎上融入基于遺傳特性的PSO來解決公交車的智能調度問題，仿真結果與分析表明，此方法收斂較快、性能較好，且優化結果基本符合實際情況。

實際上，文獻[6]得出選擇操作使種群的熵朝著減小的方向進化，減小了種群的多樣性；交叉操作可提高種群的熵，但并不保證使熵達到最大值；變異操作對于二進制編碼，當t→∞時，使種群熵達到最大值，變異操作可顯著地提高種群的多樣性。本文將交叉和變異操作引入其中，實際上提高了種群的多樣性，這就意味著雖能避免產生局部極小，但收斂速度會降低，因此再加上收縮因子來提高收斂速度就達到了兩者的均衡。此方法為交通優化調度相關問題的解決提供了一種有益的思路。

參考文獻：

［1］耿金花， 尹濤， 童剛.公交優化調度模型[J].青島科技大學學報，2004，25(4):358-360.

[2]劉芹.基于信息平臺的車輛調度研究與仿真[D].西安: 西北工業大學，2006:38-41.

[3]KENNEDY J，EBERHART R C.Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks[C].Piscataway:IEEE Service Center，1995:19421948.

[4]EBERHART R C，SHI Y H.Comparing Inertia weights and constriction factors in particle swarm optimization[C]// Proc of IEEE Congress on Evolutionary Computation Piscataway:IEEE Service Center，2000:84-88.

[5]高鷹.具有遺傳特性的粒子群優化算法及在非線性盲分離中的應用[J].廣州大學學報:自然科學版，2006，5(5):49-53.

[6]張小績， 戴冠中， 徐乃平.遺傳算法種群多樣性的研究[J].控制理論與應用，1998，15(1):17-22