基于乘客滿(mǎn)意度的公交時(shí)刻表設(shè)計(jì)優(yōu)化

頡棟棟

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

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

一、引言

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

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

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

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

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

二、問(wèn)題分析

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

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

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

fitness=1Z（8）

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

（一）選擇操作

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

（二）交叉操作

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

（三）變異操作

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

圖3 染色體變異前

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

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

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

五、算例

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

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

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

六、結(jié)論

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

2011年甘肅省第十二批科技計(jì)劃（自然科學(xué)基金計(jì)劃第二批）（項(xiàng)目編號(hào)：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ā)車(chē)間隔的確定方法的探討[J].西安公路交通大學(xué)學(xué)報(bào).1997，17（2B）：44-48.

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

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

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

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

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

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