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

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

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

0 引 言

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

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

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

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

1.1 問題描述

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

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

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

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

(3) 公交車不準(zhǔn)等客；

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

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

(6) 在運(yùn)營(yíng)的時(shí)間段，每班車都會(huì)遇到信號(hào)燈。

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

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

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

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

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

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

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

(5)Tk表示第k時(shí)段的時(shí)段長(zhǎng)度。

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

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

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

(9)dk表示第k時(shí)段信號(hào)燈的周期。

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

(1)

(2)

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

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

(3)

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

(4)

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

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

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

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

(5)

優(yōu)化目標(biāo)為

(6)

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

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

(7)

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

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

(8)

這樣設(shè)計(jì)目標(biāo)函數(shù)的意義在于，當(dāng)0

2 公交車輛運(yùn)營(yíng)調(diào)度的求解

2.1 量子遺傳算法

2.1.1量子染色體

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

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

(9)

(10)

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

2.1.2量子變異

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

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

2.1.3量子交叉

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

表1 全干擾交叉

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

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

2.2 量子遺傳算法求解步驟

量子遺傳算法[8]是基于量子計(jì)算原理的一種智能進(jìn)化算法，是量子計(jì)算與遺傳算法相結(jié)合的產(chǎn)物，它建立在量子的態(tài)矢量表示的基礎(chǔ)之上，將量子比特的幾率幅應(yīng)用于染色體的編碼，使得一條染色體可以表達(dá)多個(gè)狀態(tài)的疊加，并利用量子邏輯門實(shí)現(xiàn)染色體的更新操作，從而實(shí)現(xiàn)了目標(biāo)的優(yōu)化求解。具體的實(shí)現(xiàn)流程圖如圖1所示。

3 實(shí)驗(yàn)驗(yàn)證

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

表2 客流量

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

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

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

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

4 結(jié) 語

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

圖2 收斂性比較

[1] 張飛舟,晏 磊，范躍祖,等.智能交通系統(tǒng)中的公交車輛調(diào)度方法研究[J]. 中國(guó)公路學(xué)報(bào)，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].計(jì)算機(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].吉林:吉林大學(xué)，2004.

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

[9] 黃力明. 基于量子遺傳算法的圖像分割[J].計(jì)算機(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)寧,靳洪兵,劉 波. 基于改進(jìn)量子遺傳算法的云計(jì)算資源調(diào)度[J]. 計(jì)算機(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é)合改進(jìn)OTSU法和改進(jìn)遺傳算法的圖像分割方法[J]. 實(shí)驗(yàn)室研究與探索,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] 李 浩, 李士勇.一種基于量子遺傳算法的擴(kuò)展T-S模型辨識(shí)[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ìn)化算法[J].工程數(shù)學(xué)學(xué)報(bào),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]. 計(jì)算機(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.