頡棟棟

摘 要：針對公交乘客對出行舒適度的要求，在考慮動態(tài)需求的環(huán)境下，提出了乘客滿意度出行函數(shù)。通過分析不同的擁擠現(xiàn)象，建立了非線性優(yōu)化模型，同時設(shè)計(jì)遺傳算法對所建模型進(jìn)行求解。最后，通過算例驗(yàn)證了模型與算法的實(shí)效性。

關(guān)鍵詞：乘客滿意度；動態(tài)需求

一、引言

隨著我國社會經(jīng)濟(jì)的快速發(fā)展、城市規(guī)模的不斷擴(kuò)大，城市交通擁堵現(xiàn)象日趨嚴(yán)重。優(yōu)先發(fā)展城市公共交通是解決城市交通問題的主要出路，所以提高公交系統(tǒng)對乘客的吸引力便成為迫在眉睫的問題，而這個吸引力的體現(xiàn)就是公交系統(tǒng)的服務(wù)水平，而公交時刻表就是衡量服務(wù)水平最直接的指標(biāo)之一。

對公交時刻表的研究已有許多文獻(xiàn)，[1]根據(jù)線路斷面乘客量給出了時刻表設(shè)計(jì)的方法；Palma以乘客總延誤時間為目標(biāo)研究理想狀態(tài)下的時刻表。[2]基于西安市的公交客流調(diào)查數(shù)據(jù)，討論了四種不同情況下發(fā)車的間隔。這四種情況分別為：在客流需求給定的情況下，可以提供發(fā)車間隔來滿足乘客出行；當(dāng)車輛的數(shù)量有限的情況下，也相應(yīng)的改變發(fā)車間隔，提高服務(wù)質(zhì)量；若在相鄰時段內(nèi)，發(fā)車間隔的確定應(yīng)采用平滑法；發(fā)車時刻表的確定，應(yīng)考慮不同的時間采用不同的發(fā)車間隔。[3]通過對公交列車化現(xiàn)象的分析，以公交運(yùn)營成本最小和乘客收益最大為目標(biāo)建立模型，確定最小發(fā)車間隔。并利用算例驗(yàn)證模型了模型的可行，結(jié)果表明：最小間隔的確定必須滿足車輛在運(yùn)行時不能串行的同時也要滿足乘客的利益。

在考慮公交的運(yùn)行隨機(jī)性的方面，[4]考慮在實(shí)際運(yùn)營中乘客需求具有隨機(jī)性，固定需求下優(yōu)化的公交時刻表不適應(yīng)運(yùn)營的要求，隨機(jī)需求下的期望值模型忽略了不利可能事件對運(yùn)營的負(fù)面影響，針對此情況研究隨機(jī)需求下公交時刻表設(shè)計(jì)的魯棒性優(yōu)化。[5]針對需求隨機(jī)變動條件下公交運(yùn)營設(shè)計(jì)的綜合優(yōu)化問題，首先將公交運(yùn)行情況抽象到三維網(wǎng)絡(luò)中，給出公交車輛運(yùn)營服務(wù)的時空網(wǎng)絡(luò)圖，由此構(gòu)造基于隨機(jī)期望值規(guī)劃的公交時刻表設(shè)計(jì)與車輛運(yùn)用綜合優(yōu)化模型，該模型綜合考慮了公交企業(yè)的經(jīng)濟(jì)效益和公交乘客所得到的公交服務(wù)水平的優(yōu)化，并給出公交服務(wù)頻次和車輛分配協(xié)調(diào)的啟發(fā)式算法。[6]研究了車輛隨機(jī)行駛時間情況下的單線路公交時刻表設(shè)計(jì)問題?？紤]了公交運(yùn)營者主觀偏好對最優(yōu)時刻表設(shè)計(jì)的影響，建立了以車輛到站時刻偏差和車輛超時行駛時間的權(quán)重之和最小為優(yōu)化目標(biāo)的隨機(jī)期望值模型。

在求解算法方面，文獻(xiàn)[7]提出了一種利用遺傳算法計(jì)算城市公交時刻表的方法。通過對城市公交時刻表和客流的特征分析，以車輛和乘客到站為約束條件，以乘客等待時間為目標(biāo)函數(shù)，建立模型，并根據(jù)其的獨(dú)特性，設(shè)計(jì)一種特殊編碼的遺傳算法，最后利用實(shí)例對模型進(jìn)行了驗(yàn)證。[8]文獻(xiàn)[13]通過對車站、車輛和出行者的關(guān)系，建立了以乘客在站的等待時間和列車載客量為指標(biāo)的模型，目的是充分使用車底數(shù)，提高運(yùn)營效率。最后給出了遺傳算法的求解步驟，以及利用算例進(jìn)行驗(yàn)證。

本文在已有文獻(xiàn)的基礎(chǔ)上，基于動態(tài)需求，以乘客出行滿意度為目標(biāo)建立模型。并結(jié)合上述文獻(xiàn)設(shè)計(jì)遺傳算法對模型進(jìn)行求解。在文章組織過程中，第1節(jié)對問題進(jìn)行了分析和定義，第2節(jié)建立非線性模型，第3節(jié)設(shè)計(jì)求解算法，第4節(jié)利用算例驗(yàn)證模型和算法，最后給出了本文結(jié)論。

二、問題分析

本文將研究一條由郊區(qū)發(fā)往工作區(qū)的公交線路，該線路包含有多個乘客上車站，一個共同的目的地車站，如圖1所示，共有n個車站，從車站O1到車站On-1全為上車站，車站D為下車站。

四、算法設(shè)計(jì)

本文采用遺傳算法對上述模型進(jìn)行求解。首先，對其進(jìn)行編碼時，本文將研究時間段等間隔劃分，采用0-1編碼方式對染色體進(jìn)行編碼染色體每個基因位都對應(yīng)這研究時段內(nèi)的某一時刻，其中“1”表示在該基因位對應(yīng)的時刻車輛在始發(fā)站發(fā)車，“0”表示不發(fā)車。其次，在遺傳算法中將通過適應(yīng)度的來衡量種群中的個體是否達(dá)到或者接近于最優(yōu)解。適應(yīng)度值大的將被遺傳到下一代的概率大，反之，適應(yīng)度小的被遺傳到下一代的概率小。由于本文的目標(biāo)函數(shù)是最小值優(yōu)化問題，所以將其通過公式（8）進(jìn)行轉(zhuǎn)換。

fitness=1Z（8）

遺傳操作包含選擇操作、交叉操作和變異操作，通過遺傳操作產(chǎn)生了新的一代種群，下面將結(jié)合染色體的編碼形式對其進(jìn)行闡述。

（一）選擇操作

選擇操作是對種群個體進(jìn)行優(yōu)勝劣汰的操作，其核心是：將個體適應(yīng)度函數(shù)值大的遺傳到下一代中，而將適應(yīng)度小的淘汰掉。本文將采用輪盤賭選擇法。其中，輪盤賭選擇的概率與其適應(yīng)度值的大小成正比，如公式（9）所示。

（二）交叉操作

本文采用單點(diǎn)交叉，單點(diǎn)交叉是隨機(jī)選取種群中的兩個染色體，隨機(jī)產(chǎn)生交叉點(diǎn)，根據(jù)交叉概率Pc將其從交叉點(diǎn)處將其斷開，并相互交換。

（三）變異操作

本文采用基本位變異，對染色體隨機(jī)產(chǎn)生變異點(diǎn)，根據(jù)變異概率Pm將其變異成其它等位基因，如圖3所示。

圖3 染色體變異前

由于在上述模型中，兩車輛之間必須滿足最小安全追蹤間隔，而由于染色體的初始化以及交叉變異操作的都是隨機(jī)進(jìn)行的，所以在染色體初始化和交叉變異操作之后須對染色體進(jìn)行調(diào)整。將染色體中不滿足最小安全追蹤間隔的基因進(jìn)行調(diào)整，將第一車輛固定，找到第二車輛，若兩者之間不滿足安全追蹤間隔，則使第二車輛的基因變?yōu)?，將下一個基因變?yōu)?，再判斷在當(dāng)前基因?qū)?yīng)的時刻發(fā)車是否滿足安全追蹤間隔的約束，若不滿足，則繼續(xù)向后推移。

以上算法的步驟如下所示，其中g(shù)表示迭代次數(shù)，Gen表示程序終止代數(shù)，M表示種群大小，P（g）表示第g代的種群，i表示個體，f（g，i）種群P（g）中個體i的適應(yīng)度。

Step1：初始化種群P（0），且置g=0；

五、算例

本算例設(shè)計(jì)一條如圖4所示多對一的城際鐵路，假設(shè)其研究時段為[7：00-8：00]，車輛在每站的停車時間均為1min，1站到2站、2站到3站和3站到4站的運(yùn)行時間分別為10min、5min和15min。在研究時段內(nèi)可用車輛數(shù)為10列，車輛最小安全追蹤間隔為5min，車輛的額定容量為400人。

算法參數(shù)選?。悍N群規(guī)模80，迭代次數(shù)500，交叉概率0.98，變異概率0.1，擁擠因子M=30。利用以上參數(shù)得到車輛的發(fā)車時刻表如表1所示，其總目標(biāo)值為33951.00min，乘客總等待時間為13615.00min。

通過上述計(jì)算結(jié)果可知，在時間段7：20-7：40之間車輛密度較大，而此時段為客流高峰期，所以滿足大客流需要高密度的車輛服務(wù)的規(guī)律，結(jié)果合理。

六、結(jié)論

本文主要針對存在多個上車站和一個下車站的特殊情況，在考慮乘客出行滿意度的條件下，研究了單線路車輛時刻表優(yōu)化問題，同時設(shè)計(jì)了有效的遺傳算法進(jìn)行求解。最后從算例的結(jié)果可知，該模型與算法能夠有效的求解出質(zhì)量較高的時刻表。然而，由于該問題的特殊性，導(dǎo)致所建模型與算法不能推廣至一般問題，這也是進(jìn)一步所需要研究的內(nèi)容。（作者單位：蘭州交通大學(xué)鐵道技術(shù)學(xué)院）

2011年甘肅省第十二批科技計(jì)劃（自然科學(xué)基金計(jì)劃第二批）（項(xiàng)目編號：1112RJZA049）

參考文獻(xiàn)：

[1] Ceder A.Methods for creating bus timetables[J].Transportation Research Part A General，1987，21（1）：59-83.

[2] 孫芙靈.公交調(diào)度中發(fā)車間隔的確定方法的探討[J].西安公路交通大學(xué)學(xué)報(bào).1997，17（2B）：44-48.

[3] 周嘉男，羅霞，黃啟樂，魏強(qiáng).基于緩解公交車輛化現(xiàn)象的最小發(fā)車間隔研究[J].重慶交通大學(xué)學(xué)報(bào)（自然科學(xué)版）.2012，31（4）：836-841.

[4] 孫楊，宋瑞，何世偉.隨機(jī)需求下公交時刻表設(shè)計(jì)的魯棒性優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2011，31（5）：986-992.

[5] 宋瑞，何世偉，楊永凱，等.公交時刻表設(shè)計(jì)與車輛運(yùn)用綜合優(yōu)化模型[J].中國公路學(xué)報(bào)，2006，19（3）：70-76.

[6] 吳影輝，唐加福，宮俊.考慮隨機(jī)行駛時間的單線路公交時刻表設(shè)計(jì)優(yōu)化模型[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2015（10）：1393-1397.

[7] 張明輝，?；菝?一種用于計(jì)算城市公交時刻表的復(fù)合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用.2011，47（20）：210-213.

[8] 徐永實(shí)，徐瑞華.遺傳算法在軌道交通車輛發(fā)車時刻優(yōu)化中的應(yīng)用[J].城市公用事業(yè).2011（2）：27-29.