量子遺傳算法在公交車輛調度中的應用

崔明月， 黃榮杰， 劉紅釗， 劉旭焱， 蔣華龍

(1. 南陽師范學院 物理與電子工程學院， 河南 南陽 473061； 2. 重慶大學 自動化學院， 重慶 40044)

0 引 言

隨著我國經濟建設的飛速發展，機動車輛數量不斷增加，交通擁堵日趨嚴重。目前，國家針對交通擁堵問題，已經制定了優先發展公交車的策略，但是現有的公交系統運營中存在線路不規范、等車時間長等一系列問題。因此，如何優化公交調度是很重要的一個環節，其系統由調度中心、車載設備、電子站牌等幾部分組成，其主要功能是實現公交車輛的自動調度和指揮[1]。公交車輛模型的建立以及優化調度算法則是整個調度系統的核心，通過優化調度算法產生指導公交車輛調度的時刻表，調度人員依照調度時刻表進行車輛的調度。

目前國內外許多學者主要從調度系統的集成和公交調度的優化算法兩方面對公交調度進行研究和探討，并取得一定的研究成果[2-7]。1981年，Ceder等人[2]給出了以赤字方程為概念的方法，進而減少公共交通系統的車輛總數；1993年，Malacly Carev[3]研究了公交車輛的非準點到站的分布，并對不同發車間隔下乘客的到達分布進行了研究；1998年，PaoloDelle Site等人[4]研究了客運走廊上的公交調度優化模型等。不同的智能優化算法，用來協助公交調度人員對車輛進行實時調度，文獻[5]利用遺傳算法求解公交調度模型的多目標優化問題；文獻[6]則采用模擬退火算法對公交車輛調度進行求解等。正是因為許多學者在這兩個方面的研究成果，為公交系統的有序穩定發展奠定了深厚的基礎。

在實際交通中，公交線路上的信號燈周期對公交車輛到站的時間有一定影響，然而現有的公交運營調度優化模型未考慮信號燈周期的影響，本文通過引入信號燈周期因素對公交調度的影響，建立以乘客等車時間與公交公司成本費用為目標多目標優化模型。同時考慮到文獻[7]中采用了拒絕策略直接拋棄法來解決效率低問題，采用懲罰策略建立了一種新的適應度函數，效率明顯提高。遺傳算法(GA)是解決多目標優化問題的有效算法，由于基本遺傳算法存在易陷入局部最優、早熟收斂和收斂速度慢等缺陷[8]，因此采用由GA與量子計算相結合而成的量子遺傳算法[9-12](QGA)來求解多目標優化問題。QGA具有量子態的疊加性和相干性以及量子比特的糾纏性等特點，可以加快求解的收斂速度。

1 公交運營參數優化模型的建立

1.1 問題描述

公交車輛運營調度是根據公交站點的客流情況進行合理安排車輛班次，即確定恰當的發車間隔的問題。在實際的交通系統中，信號燈周期對車輛的運行時間有一定的影響，但現有模型中未考慮信號燈周期對乘客等車時間的影響，故本文將信號燈周期引入到乘客總等車時間中。在公交車輛運營中，主要考慮公交公司的運營成本和乘客的利益，即公交公司總是希望發車的車輛數最少，也就是發車的時間間隔盡量大，而乘客期望等車時間盡可能短。因此，公交車輛運營調度，既要保證公交公司費用最小，也要盡可能地使得乘客費用最低，只有這樣才能獲得最大的社會效益。

為建立公交運營參數優化模型，做出如下假設[7]：

(1) 在特定的時間段內，所有車輛都沿著規定線路運行；

(2) 所有在車站候車的乘客在第一班車到達時均上車，不會留有乘客,即車容量被認為是足夠大的；

(3) 公交車不準等客；

(4) 所有線路均不準越站和超車；

(5) 在給定的時間段內，各路線的發車間隔是固定的；

(6) 在運營的時間段，每班車都會遇到信號燈。

通過對交通數據的分析，首先引入一天內乘客的等車總時間數以及公交公司的發車次數這兩個目標函數，然后將一天內公交公司運營時間劃分為若干個時間段，同時采用加權求和方法將兩個目標函數進行合成一個目標函數，以其作為多目標函數來建立問題的數學模型。再者，引入公交車輛的滿載率作為優化組合問題的約束條件。

1.2 優化模型的建立

為了便于后文的闡述，模型中的變量定義如下：

(1)S′為時段集合,S′=1,2,…,k,…,S，其中：k表示第k時段，S表示第s時段，同時表示時段總數。

(2)mk表示第k時段發的第m次車，同時表示第k時段總發車車次。

(3)J′為車站集J′=1,…,j,…,q，j表示第j個車站，q表示第q個車站，同時也表示線路的車站總數。

(4) Δtk表示第k時段的發車間隔。

(5)Tk表示第k時段的時段長度。

(6)m表示1天中總的發車車次。

(7)ukj表示第k時段第j站的上車乘客數。

(8)ρkj表示第k時段第j站的乘客到達率(假設乘客到達服從均勻分布)，是隨機變量。

(9)dk表示第k時段信號燈的周期。

基于1.1節中的條件和分析，同時結合文獻[7]，可以得到公交車輛發車間隔的優化模型，式(1)和式(2)分別表示公交公司利益的1天內總發車次數最少和乘客利益的乘客總等車時間最短：

(1)

(2)

式中,mk=int(Tk/Δtk)，int(·)表示取整函數。

目標函數式(1)與式(2)可理解為乘客和公交公司兩方面的利益，且這兩類目標是相互對立的。當在同一路段不同時間段以及不同的路段時，乘客和公交公司的利益不是同等重要的，可以引入系數α′和β′表征兩者利益的重要程度。本文將兩者利益看成同等重要，即取α′和β′相等，因此，可以將式(1)和(2)這兩個單目標函數合并為1個多目標函數，表達式如下：

(3)

根據公交運營車輛的實際狀況，式(3)的約束條件為

(4)

式(4)表示一天內的車輛平均滿載率大于0.70。

式(3)中的α′和β′滿足α′+β′=1，若使α′和β′相等，即α′=β′=0.5，式(4)中的Q表示車輛的最大容納量，其值通常為120人。在實際交通中，信號燈周期多為固定周期，因此，本文選取dk=1 min(k=1,…,K)。

發車間隔均應在最大發車間隔Umax和最小發車間隔Umin之間，即Δtk∈Umax,Umin，作為目標函數中一個約束條件，對于具體問題可以將這兩個參數進行調整。

在遺傳算法中，采用輪盤賭的方式進行優質基因選擇，所以對適應度函數進行最大值尋優比較方便，因此將目標函數改寫為：

(5)

優化目標為

(6)

由于本文的優化目標是一個約束優化問題，遺傳算法中處理約束的方法典型方法有拒絕策略，修復策略，懲罰策略等。文獻[7]采用拒絕策略，這種策略具有簡單，易于實現的優點，但其效率最低，當可行解不容易達到時，很難達到一個初始種群[13]。本文采用懲罰策略對約束條件進行處理，通過對違反約束的問題進行懲罰將約束問題轉化為無約束問題。

對約束條件(4)進行分析，可變為：

(7)

由式(7)可知g(Δtk)>0。原約束函數(4)的意義等同于g(Δtk)≥1，因此設計新的帶罰函數的目標函數為：

H(Δtk)=f(Δtk)g(Δtk)

(8)

這樣設計目標函數的意義在于，當0

2 公交車輛運營調度的求解

2.1 量子遺傳算法

2.1.1量子染色體

量子遺傳算法采用一種基于量子比特的編碼方式，而傳統遺傳算法常用編碼方式主要有二進制編碼、十進制編碼以及符號編碼。其中量子比特為最小信息單元，一個量子比特的狀態可以取值0或1，其狀態可以表示為[14]：

|Ψ>=α|0>+β|1>

(9)

(10)

在本文的實際求解中，發車間隔Δtk∈Umax,Umin，參照文獻[7],Umax，Umin分別為15和2。因為23<15<24，所以，每個Δtk需要4位，本文把每天運營時間分成五個時段，即K=5，所以每個染色體共需要20位。同時，因為Δtk≥Umin，所以本文采用簡單修復策略對非法編碼進行修復。即，檢查染色體相應字段對應的Δtk，如果Δtk<2，這將相應染色體的第二位設置為1，其余三位隨機生成，從而保證Δtk≥Umin。

2.1.2量子變異

與傳統的編碼方式不同，量子進化算法中的染色體是利用一種概率表示的。在量子理論中，狀態間的轉移是通過量子門變換矩陣實現的，量子旋轉門的旋轉角度也可以表示量子染色體的變異，從而將最優個體的信息添加到變異染色體中，實現加快算法收斂的目的。設計如下的變異算子：

式中：Uθ表示量子旋轉門，其中旋轉角度大小為Δθi，可以根據αi,βi落在的坐標軸上的象限來定旋轉的方向，sαi,βi表示旋轉角的方向，其具體確定方法詳見文獻[15]。再者，我們還可以利用其他的量子變換門等構造其他變異算子。

2.1.3量子交叉

交叉是進化算法中的一種搜索最優解的手段，通常采用的交叉操作主要有單點交叉、多點交叉、均勻交叉以及算術交叉等，這些操作在交叉的兩個個體相同時不再奏效了。因此，我們根據量子的相干特性實現一種交叉操作，即“全干擾交叉”。這里假設種群數為5，染色體的長度為9，表1給出了這種新的交叉操作。

表1 全干擾交叉

普通的交叉操作存在局部性與片面性等不足，然而“全干擾交叉”能夠充分利用種群中的盡可能多的染色體信息，在種群進化出現早熟時，能夠產生新的個體，給進化過程注入新的動力。該交叉操作主要是利用量子的相干特性，可避免普通染色體在進化后期階段出現的早熟現象。

普通的交叉操作存在局部性與片面性等不足，然而“全干擾交叉”能夠充分利用種群中的盡可能多的染色體信息，在種群進化出現早熟時，能夠產生新的個體，給進化過程注入新的動力。該交叉操作主要是利用量子的相干特性，可避免普通染色體在進化后期階段出現的早熟現象。

2.2 量子遺傳算法求解步驟

量子遺傳算法[8]是基于量子計算原理的一種智能進化算法，是量子計算與遺傳算法相結合的產物，它建立在量子的態矢量表示的基礎之上，將量子比特的幾率幅應用于染色體的編碼，使得一條染色體可以表達多個狀態的疊加，并利用量子邏輯門實現染色體的更新操作，從而實現了目標的優化求解。具體的實現流程圖如圖1所示。

3 實驗驗證

利用上述模型，選取某一公交線路[5,12]，在線路上共有4個站點，公交公司的運營時間是每天的6:00～21:00，將6:00～8:30和16:00～19:00這兩個時段作為上下班的高峰時段，以及8:30～12:00與12:00～16:00這兩個時段作為平峰時段，最后把19:00～21:00作為低峰時段，也就是把每天運營時間分成5個時段，即K=5，其客流量如表2所示。

表2 客流量

本文分別采用量子遺傳算法和標準遺傳算法進行式(3)所示模型進行優化求解。其參數選擇如下:發車間隔變化區間為2,15，α′=β′=0.5，量子遺傳算法種群規模為N=10；標準遺傳算法的參數選取如下：種群規模為100，交叉概率Pc=0.95，變異概率為Pm=0.005，為便于比較，進化代數統一為100代。應用量子遺傳算法得到各時段的發車間隔與發車次數如表3所示。

表3 發車班次及發車間隔

為了證明量子遺傳算法更加有效解決多目標優化組合問題，本文采用同樣的數據與標準遺傳算法進行收斂性比較，結果如圖2所示。由圖2可以看出量子遺傳算法的收斂速度快于標準遺傳算法。

由本文所得到的發車時刻表與文獻[16]中α=β=0.5時得到的發車時刻表安排進行比較，可以看出信號燈周期對公交公司發車時間的安排有一定的影響。因此，考慮了信號燈周期因素對乘客等車時間的影響是合理的。

4 結 語

考慮了信號燈周期對乘客等車時間的影響，提出了公交公司和乘客利益為目標優化組合問題。本文為保證解的精確性，提出了一種基于懲罰原則新的適應度函數，同時為了克服遺傳算法的不足，采用量子遺傳算法優化不同時間段的發車時間間隔，進而兼顧公交公司和乘客的利益，使得社會整體效益達到最優，從而達到優化配置公交公司資源。同時，實驗結果也表明量子遺傳算法對公交調度進行優化是可行且有效的，且信號燈周期對發車時間間隔是有影響的。

圖2 收斂性比較

[1] 張飛舟,晏 磊，范躍祖,等.智能交通系統中的公交車輛調度方法研究[J]. 中國公路學報，2003，16(2):82-85.

ZHANG Fei-zhou, YAN Lei, FAN Yue-zu,etal. Research on dispatching methods of public traffic vehicles in intelligent transport system[J]. China Journal of Highway and Transport, 2003, 16(2): 82-85.

[2] Ceder A, Golany B, Tal O. Creating bus time tables with maximal synebronization[J]. Transportation Research, 2001, 35(10): 913-928.

[3] Malacly C．Optimizing scheduled times allowing for behavioural response [J]．Transportation Research, 1998, 32(5):329-342.

[4] Paolo D S, Francesco F．Bus service optimization with fuel saving objective and various financial constrains [J]. Transportation Research, 2001, 35(2):157-176.

[5] 童 剛. 遺傳算法在公交調度中的應用研究[J].計算機工程,2005,31(13):29-31.

TONG Gang. Application Study of Genetic Algorithm on Bus Scheduling [J]. Computer Engineering, 2005,13: 29-31.

[6] 鄭小花,陳淑燕,武林芝. 模擬退火算法在公交調度中的應用[J].信息化研究,2009,35(9):45-50.

ZHENG Xiao-hua, CHEN Shu-yan, WU Lin-zhi. The Application of Simulated Annealing Algorithm in Public Transport Scheduling [J]. Informatization Research, 2009,35(9):45-50.

[7] 崔世彬.遺傳算法在公交調度中的應用研究[D].吉林:吉林大學，2004.

[8] 王小平,曹立明. 遺傳算法理論、應用與軟件實現[M].西安:西安交通大學出版社，2006.

[9] 黃力明. 基于量子遺傳算法的圖像分割[J].計算機應用與軟件，2009，26(9):247-249.

HUANG Li-ming. Image segmentation based on quantum genetic algorithm [J]. Computer Applications and Software, 2009, 26(9):247-249.

[10] 劉衛寧,靳洪兵,劉 波. 基于改進量子遺傳算法的云計算資源調度[J]. 計算機應用,2013, 33(8):2151-2153.

LIU Wei-ning, JIN Hong-bin, LIU Bo. Cloud computing resource scheduling based on improved quantum genetic algorithm [J]. Journal of Computer Applications, 2013, 33(8):2151-2153.

[11] 李賢陽,黃 嬋. 一種結合改進OTSU法和改進遺傳算法的圖像分割方法[J]. 實驗室研究與探索,2012, 31(12):57-61.

LI Xian-yang, HUANG Chan. A Novel Method for Image Segmentation Based on Improved OTSU and Improved Genetic Algorithm[J]. Research and Exploration in Laboratory, 2012,31(12):57-61

[12] 李 浩, 李士勇.一種基于量子遺傳算法的擴展T-S模型辨識[J]. 控制與決策,2013,28(8): 1268-1272.

LI Hao, LI Shi-yong. An expanded T-S model identification based on quantum genetic algorithm [J]. 2013, 28(8): 1268-1272.

[13] 汪定偉,王俊偉,王洪峰,等. 智能優化方法[M]. 北京:高等教育出版社,2006.

[14] LIU S X, YANG Y, MU D B,etal. An Application of TS Model and Phase Based Quantum Genetic Algorithm in Oilfield [J]. Applied Mechanics and Materials, 2014, 513: 1392-1397.

[15] 楊淑媛,焦李成,劉 芳. 量子進化算法[J].工程數學學報,2006,23(2):235-246.

YANG Shu-Yan, JIAO Li-cheng, LIU Fang. The quantum evolutionary algorithm [J]. Chinese Journal of Engineering Mathematics, 2006, 23(2): 235-246.

[16] 付阿利,雷秀娟. 粒子群優化算法在公交車智能調度中的應用[J]. 計算機工程與應用,2008, 44(15): 239-241.

FU A-li, LEI Xiu-juan. Intelligent dispatching of public transit vehicles using particle swarm optimization algorithm [J]. Computer Engineering and Applications, 2008, 44(15): 239- 241.