考慮時間窗的定制公交線路時空分層優(yōu)化模型*

溫 冬 張萌萌

（山東交通學(xué)院交通與物流工程學(xué)院 濟南250357）

0 引 言

隨著城市化進程的加快，人們的生活節(jié)奏逐漸加快，乘坐公交出行成為了人們的生活常態(tài)，如何讓公交出行變的更加的舒適與高效，是目前各大公交公司所面臨的一大挑戰(zhàn)，因此，能夠為乘客提供1人1座，直達出行服務(wù)的定制公交進入到人們的生活，如何設(shè)置定制公交的運行線路及站點使其能更好的服務(wù)乘客成為了目前公交領(lǐng)域的研究熱點。

1998年Harms等[1]在報告中介紹了瑞士2個共享汽車合作社的出現(xiàn)和專業(yè)化過程。隨后國內(nèi)外的學(xué)者開始進行定制公交相關(guān)的研究。與國內(nèi)相比國外對此方面的研究相對較早，例如，國外的需求響應(yīng)式公交[2-3]及靈活性公交系統(tǒng)[4-5]等都是定制公交的原型。隨著大數(shù)據(jù)時代的到來，研究人員分別從公交以及出租車GPS定位數(shù)據(jù)、IC卡刷卡數(shù)據(jù)等多源數(shù)據(jù)[6-9]入手對公交的服務(wù)能力、人們的出行行為以及市場需求進行了研究分析。目前對于定制公交的研究可以分為線路設(shè)計與調(diào)度優(yōu)化2個部分，對于公交線路設(shè)計的研究，楊敬鋒等[10]從空間角度出發(fā)提出了定制公交出行熱力圖分析模型的構(gòu)建方法；在公交線路構(gòu)建與優(yōu)化方面，李莎[11]綜合考慮乘客與公交企業(yè)雙方的利益，提出了1種基于備選線路集組合生成的方法來進行定制公交線網(wǎng)優(yōu)化的設(shè)計；乘客的出行意愿及出行方式也影響著定制公交線路的布設(shè)與優(yōu)化，靳文舟等[12]提出了1種基于小波神經(jīng)網(wǎng)絡(luò)的定制公交目標乘客出行意愿預(yù)測模型，以此來對乘客選擇哪種交通方式出行進行預(yù)測；國內(nèi)外學(xué)者們分別以不同的目標構(gòu)建了不同的優(yōu)化函數(shù)，通過各種啟發(fā)式算法對模型進行求解，Li Wenyong等[13]根據(jù)最小費用最大流和Dijkstra算法，建立了站點規(guī)劃的0-1模型，在保證站點數(shù)及載客量的約束下，讓線路的距離最短以及服務(wù)率最高；雷永巍等[14]以需求服務(wù)率最大及費用最小為優(yōu)化目標，通過蟻群算法對所建立的動態(tài)網(wǎng)絡(luò)調(diào)度模型進行了求解；對于公交調(diào)度的研究，李穎[15]分別從人員條件、車輛條件及道路條件研究，對定制公交的運行規(guī)則、預(yù)約響應(yīng)規(guī)則、車輛的發(fā)車與停車規(guī)則進行研究，建立了定制公交的站點規(guī)劃模型及車輛的靜態(tài)預(yù)約與動態(tài)預(yù)約調(diào)度模型；陶浪等[16]以乘客的出行時間最短及車輛油耗最低作為目標函數(shù)，并通過遺傳算法對函數(shù)進行求解，得到最終的公交線路方案；王健等[17]研究了帶時間窗約束的定制公交線路調(diào)度方法，以總公交車運營里程最小為目標，以公交站點及公交容量為約束建立公交車調(diào)度優(yōu)化模型，最后通過遺傳算法及貪心算法對模型進行求解，找到最優(yōu)的公交線路方案；張宇寧等[18]以公交運營成本最小為目標建立了線路規(guī)劃模型，通過lingo軟件對模型進行求解，并以虛擬乘客數(shù)據(jù)進行了案例分析驗證了模型的有效性；陳汐等[19]以乘客出行成本及車輛運營成本最小為優(yōu)化目標，構(gòu)建了多區(qū)域運營模式的通勤定制公交線路規(guī)劃模型，并通過2階段啟發(fā)式算法對構(gòu)建的模型進行了求解。

在定制公交線路規(guī)劃與模型構(gòu)建方面，國內(nèi)外研究學(xué)者進行了較為全面的研究，針對定制公交需求時空分布離散的情況，研究人員采用聚類的方式進行孤立點分析，該方法對孤立的散點有較好效果，但是對于孤立的散點簇效果不好，且只能對點的空間分布進行分析，并未進行時間層面的分析，在線路模型的構(gòu)建研究中沒有考慮出行者到達離開合乘站點及上下車的時間花費。針對上述存在的問題本文利用ArcGis對需求點進行漁網(wǎng)與核密度分析，找出熱點時段與熱點區(qū)域，能夠方便快捷的在時空層面對孤立點及孤立點簇進行剔除。通過聚類分析得到了合成站點以及上車與下車2類交通小區(qū)，在優(yōu)化模型構(gòu)建方面本文考慮了乘客從需求點到目的地的時間花費，以乘客的出行時間作為約束對線路的發(fā)車時間進行優(yōu)化，本文求解得到的線路方案在保證整體服務(wù)率的基礎(chǔ)上，也很好的保證了每條線路的滿載率，使得到的出行線路能夠很好的滿足公交公司與乘客的利益，讓乘客的出行變得更加的高效快捷。

1 出行需求時空分析

1.1 需求熱點區(qū)域識別

定制公交出行需求是企業(yè)通過網(wǎng)絡(luò)向乘客征集的，需求空間分布離散，在進行線路設(shè)計時要對需求進行篩選以此排除異常數(shù)據(jù)及時間空間偏差大的需求，找到可服務(wù)的出行需求，本文提出通過漁網(wǎng)與核密度分析的方式找到出行需求的熱點時段與熱點區(qū)域，最后將對應(yīng)區(qū)域的出行需求進行提取，實現(xiàn)數(shù)據(jù)的篩選。

定制公交需求數(shù)據(jù)包括乘客的上車點（名稱及經(jīng)緯度）、下車點（名稱及經(jīng)緯度）、上車時間、下車時間等屬性要素。根據(jù)研究區(qū)域的空間范圍基于Gis構(gòu)建能夠覆蓋整個區(qū)域的漁網(wǎng)圖，網(wǎng)格的大小根據(jù)研究的精度，設(shè)置為邊長為L的正方形網(wǎng)格。通過將構(gòu)建的漁網(wǎng)與需求點進行空間連接得到每個網(wǎng)格區(qū)域的出行熱度。

需求點核密度分析用于計算柵格像元周圍點要素的密度，認為每1個點上都覆蓋著1個平滑曲面，曲面最中心的位置值最高，隨著離中心的距離增大曲面的值逐漸變小，當(dāng)達到搜索半徑的距離時值為零，曲面疊加位置的值為曲面對應(yīng)位置值的權(quán)重之和。

式中：density為對應(yīng)位置的核密度；radius為密度搜索的最大半徑距離；poph為需求點對應(yīng)的重要度；disth為需求點h與所求密度位置點的距離。

根據(jù)公交站點的輻射范圍，調(diào)整密度搜索的最大半徑。對需求的上車與下車點進行核密度分析，通過將密度分析與漁網(wǎng)分析的結(jié)果進行對比來判斷熱點區(qū)域識別的準確性。

1.2 需求點聚類分析

對漁網(wǎng)分析后提取出的需求數(shù)據(jù)進行線路設(shè)計，需要為乘車需求設(shè)置相應(yīng)的合乘站點以及乘車小區(qū)，合乘站點的選取要能夠滿足人們所能接受的最遠出行距離，因此需要對需求點進行聚類分析。

本文采用層次聚類與K-means聚類相結(jié)合的方式，對需求數(shù)據(jù)進行聚類分析，避免了層次聚類與K-means聚類所分別存在的聚類缺陷。

1）層次聚類。通過計算需求點之間的歐式距離將聚類結(jié)果展示為1棵有層次的嵌套聚類樹，每1層都對應(yīng)著1個距離標準。

2）K-means聚類。要隨機的在需求點中選k個點作為聚類點，通過歐式距離進行類的判別，通過均值更新聚類中心反復(fù)迭代，得到最終的分類結(jié)果。

首先，通過層次聚類得到各個需求點與距離的聚類樹，從而找到對應(yīng)距離下需求點被分的類別數(shù)；然后，按照得到的類別數(shù)進行K-means聚類，從而得到需求點的最終類別。需求點通過上述聚類操作后得到對應(yīng)的合乘站點，再將得到的合乘站點按照此方法再次進行聚類得到對應(yīng)的乘車區(qū)域類別。假設(shè)定制公交每個站點的輻射距離為f，交通小區(qū)的輻射半徑為r，通過聚類，將需求點聚類得到P個聚類中心站點與Z個服務(wù)交通小區(qū)。

2 時空分層優(yōu)化模型構(gòu)建

優(yōu)化模型的構(gòu)建分為2個部分：①空間優(yōu)化模型，以乘客的出行時間作為目標函數(shù)，以線路長度、公交容量作為約束條件，進行線路構(gòu)建；②時間優(yōu)化模型，以乘客出行總延誤作為優(yōu)化目標函數(shù)，以乘客預(yù)約的上車與下車時間作為約束，對線路的發(fā)車時間進行調(diào)整，從而得到最終的線路方案。

進行空間優(yōu)化，構(gòu)建的空間優(yōu)化模型見式（2）～（4）。

式中：ni為站點i的上車或下車人數(shù)；t上車或下車為單個乘客上車或者下車所消耗的時間，s/人；lsi，ljx分別為每1個乘客上車需求點s到達其上車的合成站點i的距離，m，以及每1個乘客下車合成點j到達對應(yīng)下車目的地x的距離，m；g，p分別為上車人數(shù)與下車人數(shù)；v乘客為乘客的行走速度，m/s。第一層優(yōu)化的目標函數(shù)見式（4）。

本層目標函數(shù)中，首先，從公交公司的角度考慮了線路運行的時間花費U1；其次，從乘客的角度出發(fā)考慮了每1個乘客的上下車時間花費及每1個乘客從需求站點到合乘站點、從合成站點到目的地的時間花費U2；最后，將2類時間花費求和得到最終的優(yōu)化目標U。

模型結(jié)合每個乘客的發(fā)起點、需求點與合乘站點的空間位置，考慮了乘客到達與離開站點的時間以及每個站點乘客的上下車的時間，結(jié)合本文設(shè)置的約束條件，使得求解得到的公交線路更具人性化。

所構(gòu)建的空間優(yōu)化模型式（2）～（3）滿足以下約束條件。

2）定制公交線路長度應(yīng)小于等于線路中最遠OD點對距離的1.4倍，滿足公交線路的非直線系數(shù)為1.4，即

式中：lk為線路k的長度為線路中最遠OD點對i和j之間的距離。

3）所有的站點都要有線路通過，即要滿足

式中：ki，kj分別為第k條線路的上車點跟下車點；N為上車區(qū)域跟下車區(qū)域的站點總數(shù)。

4）站點的訪問順序，即車輛要先訪問需求OD的上車站點再訪問其下車站點，即

式中：index(i)，index(j)分別為需求OD的上車站點i的索引與下車站點j的索引。

5）若線路中包含某個OD點對的上車點，那么其必須包含其對應(yīng)的下車點，即i，j∈Ak，其中i和j分別為OD點對對應(yīng)的上車與下車站點，Ak為OD點對所在的線路k的站點集合。

6）每條線路的上車人數(shù)等于下車人數(shù)，ci=cj。

7）每1個上車區(qū)域跟所有的下車區(qū)域進行1次匹配。

在進行第二層時間優(yōu)化函數(shù)T的構(gòu)建時考慮了乘客的出行時間窗，以乘客預(yù)約的上下車時間及公交線路的到達時間作為約束條件，以線路乘客的總延誤最小作為優(yōu)化目標，來進行公交發(fā)車時間的優(yōu)化，構(gòu)建的目標函數(shù)見式（5）。

通過上述構(gòu)建的雙層優(yōu)化模型可以得到區(qū)域間的公交線路、發(fā)車時間、線路里程，以及載客容量等線路信息。

3 模型求解算法

針對2節(jié)構(gòu)建的分層優(yōu)化模型，采用遺傳算法對模型進行求解。

3.1 線路算法流程

1）將上車站點與下車站點按照設(shè)定的輻射距離進行聚類，將上車站點劃分為Y個區(qū)域，下車站點劃分為X個區(qū)域，進行區(qū)域與區(qū)域間的線路設(shè)計。

2）將上車需求進行存儲，每個上車需求包括的字段有：上車站點與下車站點編號、上車區(qū)域與下車區(qū)域編號、預(yù)期的上車與下車時。

3）按照區(qū)域的編號，提取上車區(qū)域跟下車區(qū)域（進行區(qū)域間的線路設(shè)計）。

4）按照上車區(qū)域各個站點乘客需求的上車時間對乘客分類；按照設(shè)定的時段a對需求點進行再分類。

5）尋找出每個階段的上車需求分別對應(yīng)的上車點，對這些點進行應(yīng)用遺傳算法進行線路的求解。

6）1個時間段結(jié)束后自動跳轉(zhuǎn)到下1個時間段，然后重復(fù)5）。

7）1對上下車區(qū)域求解全部結(jié)束后，再進行另外區(qū)域的線路求解，返回4）～6）。

8）當(dāng)所有的上車與下車區(qū)域全部匹配完成以后，結(jié)束第1層優(yōu)化模型。

9）根據(jù)時間調(diào)節(jié)函數(shù)對每個區(qū)域?qū)χg形成的線路進行時間調(diào)節(jié)。

算法的計算流程見圖1。

圖1 算法流程Fig.1 Algorithm flow

3.2 遺傳算法構(gòu)造與求解

遺傳算法應(yīng)用在某個上下車區(qū)域?qū)Φ牟煌臅r間段中，以其中1對上下車區(qū)域為例，對遺傳算法的具體的運算流程進行說明。

采用自然數(shù)編碼的規(guī)則，1個站點作為1個基因，不同站點的組合構(gòu)成1條染色體，過程如下。

1）以生成的隨機線路的第1個站點作為線路起點，其下車點作為終點，1個上車站點都是對應(yīng)的多個下車站點，其所對應(yīng)的下車站點的排列順序按照離上車點距離的由近到遠進行排列。

2）容量約束，看上車點的乘客數(shù)量是否超出車輛的容量，若超出容量則在上車點后加0，若滿足條件則去查看其是否滿足非直線系數(shù)的約束，若不滿足就在起點后加0，若滿足條件就去檢驗線路的第2個起點。

3）同樣當(dāng)線路中有2個起點后，首先要去驗證加上第2個起點之后，第1個起點的各個約束條件是否還能滿足，若不滿足，就在第1個起點后面加0，單獨的作為1條線路，將第2個上車點作為新的起點去重復(fù)1）、2）、3）；若滿足條件則驗證加入的起點2是否滿足2個約束條件的限制。

4）對生成的每1個排列方案都進行約束條件的檢查，使得每1個組合方案都是可行解。

5）最后將每1組的染色體長度按照每組最長的染色體補全，具體方法就是在短的染色體長度后面加0，讓所有染色體長度相等。

種群選擇的規(guī)則如下。

1）根據(jù)建立的優(yōu)化函數(shù)U，計算每個個體的函數(shù)值。

2）計算種群中每個個體遺傳到下1代中的概率。

3）計算累計頻率。

4）根據(jù)生成隨機數(shù)選擇對應(yīng)個體。

交叉規(guī)則：按照自然數(shù)編碼的規(guī)則，將種群中的個體隨機的兩兩配對，設(shè)置好對應(yīng)的交叉概率。利用隨機函數(shù)產(chǎn)生每條染色體中參與交叉的基因的個數(shù)：[1，染色體長度/2]，再利用隨機函數(shù)產(chǎn)生參與交叉的基因的索引位置。

變異規(guī)則：同交叉操作相似，隨機確定參與變異的基因個數(shù)與位置索引，將選到的基因進行隨機排序后填充到對應(yīng)染色體空缺的位置。

3.3 線路發(fā)車時間優(yōu)化

步驟1。輸入第一層算法得到的公交線路方案。

步驟2。根據(jù)每個站點之間的距離以及公交車的運行速度得到每個站點之間的時間長度。

步驟3。以線路所處發(fā)車時段的起點為第1種發(fā)車時間，并以tmin為間隔枚舉得到所處時段內(nèi)的所有的發(fā)車方案。

步驟4。依次計算每種發(fā)車方案下線路的時間調(diào)節(jié)函數(shù)的值，取最小值對應(yīng)的發(fā)車時間為線路的最終發(fā)車時間。

4 案例分析

以濟南市定制公交的需求數(shù)據(jù)為例，按照本文提出的時空雙層優(yōu)化方案進行定制公交站點以及線路的設(shè)計，對比了以線路里程作為目標函數(shù)的算法求解得到的線路，以及對本文算法得到的線路方案進行評價。

4.1 方案設(shè)計

通過網(wǎng)絡(luò)收集得到的人們出行需求數(shù)據(jù)見表1。

表1 定制公交需求數(shù)據(jù)Tab.1 Demand data of customized buses

獲得的需求數(shù)據(jù)包括乘客的公交卡賬戶、上車點與下車點及其經(jīng)緯度坐標、期望的上車與下車時間。對需求點進行漁網(wǎng)與核密度分析，得到上車與下車的熱點區(qū)域，進行數(shù)據(jù)的初步篩選，對應(yīng)得到核密度與漁網(wǎng)分析的結(jié)果見圖2～4。

圖2 需求點核密度Fig.2 Kernel density of demand points

圖3 上車需求漁網(wǎng)圖Fig.3 Hot spot map of boarding demand

通過對需求點進行核密度分析與漁網(wǎng)分析驗證了所選的熱點區(qū)域的有效性，為接下來的工作做好準備。

圖4 下車需求漁網(wǎng)圖Fig.4 Hot spot map of alighting demand

對篩選得到的需求點進行聚類分析，一共聚類得到113個上車站點與17個下車站點共130個站點，具體的站點路網(wǎng)分布結(jié)果見圖5。

圖5 站點分布圖Fig.5 Site distribution

再對上述的站點進行空間聚類，將上述113個上車站點劃分為5個區(qū)域，將17個下車站點劃分為4個區(qū)域，得到的分類數(shù)據(jù)，見表2。進行上車區(qū)域與下車區(qū)域的線路設(shè)計，本實例中選擇30 min為1個時段，對該時段內(nèi)的需求進行線路方案的設(shè)計。

表2 需求分類統(tǒng)計Fig.2 Demand classification statistics

按照本文方法以分類得到的上車區(qū)域2與下車區(qū)域3為例，進行公交線路設(shè)計，并對結(jié)果的可行性進行驗證，2個區(qū)域不同時段的乘客需求見表3。

表3 區(qū)域間不同時段需求人數(shù)Tab.3 Number of people needed in different periods between regions

對上述區(qū)域之間的乘客需求，按照常用的定制公交線路的求解方法，以最短路作為線路設(shè)計的目標函數(shù)，沒有從公交公司以及乘客的角度出發(fā)進行線路優(yōu)化，該方法得到的線路方案見表4。

表4 普通算法求解的定制公交線路Tab.4 Customized bus routes solved by the common algorithm

按照本文提出的雙層優(yōu)化模型中的第一層優(yōu)化函數(shù)，將乘客的出行時間距離以及上下車時間加入到目標函數(shù)中，通過遺傳算法求解得到的定制公交的線路方案見表5。

表5 本文算法求解的定制公交線路Tab.5 Customized bus route solved by the algorithm proposed in the work

通過對比上述2種結(jié)果可以得出，本文提出的優(yōu)化模型在考慮了乘客需求后，得到的公交線路里程比未考慮時得到的線路里程整體更短，且本優(yōu)化算法從公交公司的角度出發(fā)，在保證整體服務(wù)率的基礎(chǔ)上去除了服務(wù)乘客少的線路，從而保證了每條線路的滿載率。

按照本文優(yōu)化模型的第二層，對得到的公交線路按照乘客出行時間需求在時間層面進行優(yōu)化，從而得到每一條線路的具體的發(fā)車時間見表6。

表6 定制公交線路方案Tab.6 Customized bus-route schemes

4.2 方案評價

針對上述得到的線路方案，現(xiàn)在分別從服務(wù)率、人均節(jié)省時間以滿載率對方案進行相關(guān)評價，具體評價結(jié)果見表7。

表7 線路方案評價表Tab.7 Evaluation of route schemes

通過表7可以看出，區(qū)域?qū)⒌墓坏钠骄?wù)率為96%，可以保證乘客1人1座保證乘車的舒適性；不同時段人均節(jié)省時間及車輛滿載率分別為：06：00—06：30平均每個乘客節(jié)省時34.3 min，滿載率為80%，06：30—07：00平均每個乘客節(jié)省時間7分鐘，滿載率93%，07：00—07：30平均每個乘客節(jié)省時間5 min，滿載率92%，07：30—08：00平均每個乘客節(jié)省時間16 min，滿載率93%。

5 結(jié)束語

1）本文以定制公交的站點及線路設(shè)計為研究對象，綜合考慮了乘客需求點的空間分布以及時間分布特性，以線路長度、線路容量以及乘客的出行時間作為約束條件，構(gòu)建了公交線路設(shè)計的雙層優(yōu)化模型，在空間與時間的角度同時對線路進行求解。

2）通過利用遺傳算法對構(gòu)建定制公交模型進行求解最終得到不同時段每條線路的途徑站點、服務(wù)率以及線路的發(fā)車時間等信息。通過對結(jié)果進行對比分析可知通過本模型求解得到的公交線不僅提升了服務(wù)率，乘客的出行時間都得到了節(jié)省并且公交的滿載率較高。

3）本文通過構(gòu)建時間與空間的雙層優(yōu)化模型，在第一層模型構(gòu)建時沒有將時間約束添加到模型中，在后續(xù)的研究中考慮將時間因素與空間因素進行直接的融合，構(gòu)建單層優(yōu)化模型對線路進行求解。