量子遺傳算法在公交車輛調(diào)度中的應(yīng)用

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

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

0 引 言

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

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

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

1 公交運營參數(shù)優(yōu)化模型的建立

1.1 問題描述

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

為建立公交運營參數(shù)優(yōu)化模型，做出如下假設(shè)[7]：

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

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

(3) 公交車不準等客；

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

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

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

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

1.2 優(yōu)化模型的建立

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

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

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

(3)

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

(4)

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

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

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

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

(5)

優(yōu)化目標為

(6)

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

對約束條件(4)進行分析，可變?yōu)椋?/p>

(7)

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

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

(8)

這樣設(shè)計目標函數(shù)的意義在于，當0

2 公交車輛運營調(diào)度的求解

2.1 量子遺傳算法

2.1.1量子染色體

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

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

(9)

(10)

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

2.1.2量子變異

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

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

2.1.3量子交叉

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

表1 全干擾交叉

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

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

2.2 量子遺傳算法求解步驟

量子遺傳算法[8]是基于量子計算原理的一種智能進化算法，是量子計算與遺傳算法相結(jié)合的產(chǎn)物，它建立在量子的態(tài)矢量表示的基礎(chǔ)之上，將量子比特的幾率幅應(yīng)用于染色體的編碼，使得一條染色體可以表達多個狀態(tài)的疊加，并利用量子邏輯門實現(xiàn)染色體的更新操作，從而實現(xiàn)了目標的優(yōu)化求解。具體的實現(xiàn)流程圖如圖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)所示模型進行優(yōu)化求解。其參數(shù)選擇如下:發(fā)車間隔變化區(qū)間為2,15，α′=β′=0.5，量子遺傳算法種群規(guī)模為N=10；標準遺傳算法的參數(shù)選取如下：種群規(guī)模為100，交叉概率Pc=0.95，變異概率為Pm=0.005，為便于比較，進化代數(shù)統(tǒng)一為100代。應(yīng)用量子遺傳算法得到各時段的發(fā)車間隔與發(fā)車次數(shù)如表3所示。

表3 發(fā)車班次及發(fā)車間隔

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

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

4 結(jié) 語

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

圖2 收斂性比較

[1] 張飛舟,晏 磊，范躍祖,等.智能交通系統(tǒng)中的公交車輛調(diào)度方法研究[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] 童 剛. 遺傳算法在公交調(diào)度中的應(yīng)用研究[J].計算機工程,2005,31(13):29-31.

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

[6] 鄭小花,陳淑燕,武林芝. 模擬退火算法在公交調(diào)度中的應(yīng)用[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] 崔世彬.遺傳算法在公交調(diào)度中的應(yīng)用研究[D].吉林:吉林大學，2004.

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

[9] 黃力明. 基于量子遺傳算法的圖像分割[J].計算機應(yīng)用與軟件，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] 劉衛(wèi)寧,靳洪兵,劉 波. 基于改進量子遺傳算法的云計算資源調(diào)度[J]. 計算機應(yīng)用,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] 李賢陽,黃 嬋. 一種結(jié)合改進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] 汪定偉,王俊偉,王洪峰,等. 智能優(yōu)化方法[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].工程數(shù)學學報,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] 付阿利,雷秀娟. 粒子群優(yōu)化算法在公交車智能調(diào)度中的應(yīng)用[J]. 計算機工程與應(yīng)用,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.