賈龍剛　王敏

摘 要：軌道交通線路站點(diǎn)布設(shè)需要考慮的因素較多，其中比較重要的是線路總長(zhǎng)度和總的客流吸引量。為此，文章通過對(duì)站點(diǎn)布設(shè)原則及方法進(jìn)行分析，并考慮站間距合理范圍，從而建立了站點(diǎn)布設(shè)的網(wǎng)絡(luò)模型。邊權(quán)分別代表兩點(diǎn)間的站間距及站間線路客流吸引量。采用雙目標(biāo)最短路原理并結(jié)合k-最短路算法和Dijkstra算法對(duì)模型進(jìn)行了求解。在實(shí)際決策中，決策者可以通過調(diào)整目標(biāo)上限的方法獲得有效路徑集合，再根據(jù)實(shí)際情況或者個(gè)人偏好進(jìn)行取舍。

關(guān)鍵詞：城市軌道交通；站點(diǎn)布設(shè)；站間距；雙目標(biāo)最短路；k-最短路算法；Dijkstra算法

0 引言

當(dāng)前，全國各大城市修建城市軌道交通的熱浪正在興起。但是對(duì)軌道交通的線網(wǎng)規(guī)劃、站點(diǎn)設(shè)置的相關(guān)研究我國起步較晚，目前還處于探索階段。作為乘客集中和疏散的基地——站點(diǎn)，其服務(wù)功能首先是通過站點(diǎn)實(shí)現(xiàn)的，出行者是否選擇軌道交通很大程度上取決于乘客到達(dá)站點(diǎn)的方便程度。也就是說，軌道交通站點(diǎn)的布設(shè)方案直接影響到其吸引乘客的范圍、服務(wù)水平、系統(tǒng)的運(yùn)營效率甚至城市的形態(tài)布局、路網(wǎng)結(jié)構(gòu)等。但是對(duì)于車站站點(diǎn)布設(shè)問題，目前還缺乏強(qiáng)大的理論體系作支撐。對(duì)于目前已建成的站點(diǎn)，有些由于在規(guī)劃設(shè)計(jì)時(shí)融入了設(shè)計(jì)者的主觀意識(shí)、經(jīng)驗(yàn)等因素，從而導(dǎo)致了某些軌道交通站站點(diǎn)分布不合理，成本巨大，并且難以與其他運(yùn)輸方式形成分工合理、優(yōu)勢(shì)互補(bǔ)、互相協(xié)調(diào)的局面，因而從一定程度上阻礙了其功能的全面發(fā)揮，影響了其在分擔(dān)客流中的骨干地位。

文獻(xiàn)[1]通過尋找備選點(diǎn)，并生成線路虛擬站點(diǎn)分布，以此建立了軌道交通站點(diǎn)布設(shè)的方法，但此方法僅僅從站間距角度考慮布設(shè)，沒有將其他因素考慮進(jìn)來；文獻(xiàn)[2]僅從列車運(yùn)行工況得到了站間距的上下限，但列車運(yùn)行工況是一個(gè)復(fù)雜的牽引過程，其走行路程不能從簡(jiǎn)單的物理學(xué)公式計(jì)算；文獻(xiàn)[3]使用分析方法建立了站點(diǎn)選址模型及估算站點(diǎn)數(shù)目，利用最小生成樹得出了地鐵建設(shè)費(fèi)用和運(yùn)行費(fèi)用之和最小的方案，但此方法僅僅從工程造價(jià)角度考慮站點(diǎn)布設(shè)，沒有從運(yùn)輸角度進(jìn)行研究；文獻(xiàn)[4]從車站費(fèi)用效益方面考慮，得出了車站壽命期內(nèi)總凈收益最大的優(yōu)化模型，此方法雖然能獲取工程建設(shè)各項(xiàng)費(fèi)用，但是它的缺陷是很難估計(jì)出車站建成后帶來的具體效益，因此該方法理論上可行。

文章采用雙目標(biāo)最短路的優(yōu)化方法對(duì)地鐵站點(diǎn)布設(shè)問題進(jìn)行優(yōu)化，目的在于通過此方法為軌道交通站點(diǎn)布設(shè)問題提供新的解決思路，以供決策人員參考。

1 軌道交通站點(diǎn)布設(shè)的原則與方法

1.1 布設(shè)原則

一般來說，軌道交通站點(diǎn)布設(shè)應(yīng)遵循以下原則[1]：

1.站點(diǎn)選擇應(yīng)該與城市土地開發(fā)現(xiàn)狀、土地利用、道路網(wǎng)建設(shè)情況等結(jié)合起來，既要滿足路網(wǎng)遠(yuǎn)期規(guī)劃要求，又要充分考慮城市的可持續(xù)發(fā)展。

2.以人為本，最大限度滿足旅客出行需求，合理選址，方便乘客換乘，提高出行質(zhì)量，因此站點(diǎn)應(yīng)盡可能選擇在大型客流集散點(diǎn)，如：車站，醫(yī)院，學(xué)校、大型商場(chǎng)等附近。

3.站點(diǎn)選擇應(yīng)經(jīng)濟(jì)可行，避開地質(zhì)不良地段，減少對(duì)環(huán)境的干擾、破壞。

4.充分發(fā)揮列車性能，站點(diǎn)盡量均勻，站間距在允許范圍內(nèi)可適當(dāng)調(diào)整，以滿足人們出行需求。

5.站點(diǎn)布設(shè)應(yīng)與其他交通方式協(xié)調(diào)發(fā)展，優(yōu)勢(shì)互補(bǔ)，使其各盡其責(zé)。

1.2 布設(shè)方法

對(duì)某一條線路來說，在其規(guī)劃的最初階段，就已經(jīng)確定了其走向。因此，這里的布設(shè)方法也是針對(duì)線路走向已經(jīng)確定的線路。這里所要研究的是各個(gè)點(diǎn)的布設(shè)選址，其具體方法如下：

1.對(duì)預(yù)測(cè)的出行OD矩陣進(jìn)行處理，對(duì)線網(wǎng)上主要的客流集散點(diǎn)進(jìn)行標(biāo)定。并將矩陣對(duì)角線元素置為0，其目的是消除小區(qū)內(nèi)部出行，然后對(duì)矩陣各行各列求和，得到各個(gè)交通小區(qū)區(qū)外的吸引量和發(fā)生量。按照其量的大小進(jìn)行排序，并按照小區(qū)總數(shù)量一定的百分比（一般取10%-15%）從大到小選點(diǎn)作為主要客流集散點(diǎn)，也是備選站點(diǎn)。

2.確定起點(diǎn)和終點(diǎn)。一條線路的起訖點(diǎn)一般都選擇大型客流集散點(diǎn)。

3.確定中間點(diǎn)位。以起點(diǎn)為圓心，以站間距的下限和上限dmin和dmax為半徑分別畫圓弧，其形成的圓環(huán)區(qū)域即為第一個(gè)站點(diǎn)的備選區(qū)域，其備選站點(diǎn)按照第1點(diǎn)的客流集散點(diǎn)進(jìn)行選取。記第一個(gè)站點(diǎn)的若干個(gè)備選點(diǎn)為A1，A2，A3……An，如圖1所示。再分別以A1，A2，A3……An各個(gè)點(diǎn)為圓心，dmin和dmax為半徑圓弧，得到各自的第二個(gè)站點(diǎn)的備選區(qū)域，同樣的記第二個(gè)站點(diǎn)的若干個(gè)備選站點(diǎn)為B1，B2，B3……Bn。以此類推直到最后的終點(diǎn)為止，將各個(gè)點(diǎn)連接起來形成一個(gè)網(wǎng)絡(luò)圖，如圖2所示。

2 軌道交通站間距上下限確定

以上設(shè)置方案中需要解決的是站間距范圍問題，實(shí)際在地鐵設(shè)計(jì)中，為了最大限度吸引客流，站間距需要視情況而定。站間距過短會(huì)直接導(dǎo)致列車旅行速度降低，能耗增大；另外站間距過短會(huì)使得站點(diǎn)數(shù)量過多，導(dǎo)致工程投資增加。站間距過大時(shí)，雖然旅行速度提高，但是會(huì)使旅客增加換乘的銜接時(shí)間。因此，站間距需要確定合理的上下限值。

一般來說，不應(yīng)小于公交車站距500米，但考慮到列車行駛技術(shù)條件，不應(yīng)小于列車從啟動(dòng)加速至限制速度后立即減速制動(dòng)至停車所運(yùn)行的距離。根據(jù)廣州地鐵一號(hào)線和上海地鐵二號(hào)線采用的德國車輛技術(shù)資料，列車最高運(yùn)行速度80km/h，其牽引特性曲線如圖3所示[5]，列車常規(guī)制動(dòng)的加速度為，假定該制動(dòng)加速度適用于所有負(fù)載，并且為了簡(jiǎn)化，線路條件為平直空曠地帶。

列車基本阻力R的計(jì)算公式如下[5]：。其中v為列車速度（km/h），區(qū)段運(yùn)行時(shí)間（h），區(qū)段

運(yùn)行距離（km），其中為速度間隔內(nèi)的起點(diǎn)速度，為速

度間隔內(nèi)的終點(diǎn)速度，為速度間隔內(nèi)平均速度所對(duì)應(yīng)的單位合力，，（N·KN-1），F(xiàn)為牽引力。

根據(jù)上述資料和計(jì)算公式，當(dāng)速度間隔取為10km/h時(shí)，列車能實(shí)現(xiàn)80km/h的最小站間距為1.012km[6]，因此軌道交通站間距在正常情況下不應(yīng)小于1km。

對(duì)于可根據(jù)具體的城市區(qū)域，參照國內(nèi)外城市經(jīng)驗(yàn)選取，但是不能大于乘客平均乘行距離，根據(jù)各城市站間距對(duì)比分析，最大沒有超過3km[1]。

實(shí)際上對(duì)于站間距，應(yīng)分為市區(qū)和郊區(qū)兩部分分別考慮。對(duì)于市區(qū)來說，人口比較密集，為了方便乘客出行及換乘，軌道交通站間距應(yīng)設(shè)置小一些，雖然列車可能頻繁啟動(dòng)、停車，但是其產(chǎn)生的社會(huì)效益遠(yuǎn)遠(yuǎn)大于其弊端，如東京地鐵日比谷線最小間距只有400m，充分說明了此種站點(diǎn)設(shè)置有利于吸引客流；對(duì)于郊區(qū)，人口比較稀疏，人們的出行距離一般比較長(zhǎng)，若設(shè)置小站間距將會(huì)頻繁加速、制動(dòng)，不但影響列車運(yùn)行效率，而且耽誤人們出行時(shí)間，因此郊區(qū)的站間距可以適當(dāng)加大。

3 模型描述及算法分析

3.1 模型描述

對(duì)圖2的方案圖的有向邊進(jìn)行賦權(quán)，其中第一個(gè)權(quán)值代表線路的客流吸引量，第二個(gè)權(quán)值代表實(shí)際距離。因此，目前的問題是需要求出從起點(diǎn)至終點(diǎn)的一條線路，使這條線路客流吸引量最大，并且經(jīng)過的各個(gè)站點(diǎn)長(zhǎng)度之和最短的一條路。此問題是典型的雙目標(biāo)最短路問題，至于目標(biāo)中的最大吸引量可以用其中最大的值分別減去各個(gè)客流量，轉(zhuǎn)化為求最小來處理。

對(duì)于雙目標(biāo)最短路問題，一般的有，對(duì)于網(wǎng)絡(luò)圖G=（N，E），N為頂點(diǎn)集合，E為有向邊集合，，. 令和分別為從起點(diǎn)至終點(diǎn)路徑的目標(biāo)1和目標(biāo)2的值。

為了得到時(shí)變網(wǎng)絡(luò)下的雙目標(biāo)模型，需要定義如下變量：

3.2 模型算法分析

雙目標(biāo)最短路問題屬于多目標(biāo)最短路問題中的一種常見情況，文獻(xiàn)[7，8]對(duì)一般的雙目標(biāo)最短路算法進(jìn)行了研究，并提出了一種交互式雙目標(biāo)算法。文獻(xiàn)[9，10]對(duì)雙目標(biāo)有效路徑進(jìn)行了一定研究。

文章利用k-最短路算法[11]結(jié)合有效路徑進(jìn)行求解，運(yùn)算過程中決策者可以根據(jù)需要對(duì)目標(biāo)值的上限進(jìn)行修改，從而獲得有效路徑的集合。

在此，先給出以下定義：

定義一： 若和是從起點(diǎn)O到終點(diǎn)D之間兩條路徑。如果，，且至少一個(gè)為嚴(yán)格不等式，則稱在Pareto最優(yōu)意義下，路徑有效于路徑。

定義二：若p為從起點(diǎn)O到終點(diǎn)D之間的一條路徑，令。若不存在任何一條路徑有效于p，則稱p為模型BOSPM的有效路徑。

定義三：若為從起點(diǎn)O到終點(diǎn)D之間目標(biāo)最短路，為路徑的目標(biāo)的值，為從起點(diǎn)O到終點(diǎn)D之間目標(biāo)最短路，為路徑的目標(biāo)的值，則稱為BOSPM的理想點(diǎn)。若=，令==，則稱為BOSPM的絕對(duì)最短路徑。

由于實(shí)際求解過程中，往往不存在絕對(duì)最短路徑，通常只需要找到滿足決策者要求的有效路徑。這里可以利用Dijkstra算法得到考慮單個(gè)目標(biāo)時(shí)的最短路，并獲得其最小值和。根據(jù)得到的目標(biāo)1和目標(biāo)2的最小值，給出一個(gè)可以接受的目標(biāo)1和目標(biāo)2的上限值up和up，然后利用k-最短路算法分別得到up和up的解集空間和，取二者交集，因此能夠同時(shí)滿足兩個(gè)目標(biāo)限制條件，且具有較小的目標(biāo)值。如圖4所示，假設(shè)A，B分別為目標(biāo)和的最優(yōu)解，這樣集合的路徑就落在矩形CDEF之內(nèi)。

可能有三種情況：（1），（2），（3）。對(duì)于（1），表示交集為空集，此時(shí)需要繼續(xù)調(diào)整目標(biāo)1和目標(biāo)2的上限值，直到產(chǎn)生交集；對(duì)于（2），此時(shí)的路徑可能為最優(yōu)路徑，若對(duì)此結(jié)果不滿意可以重新調(diào)整目標(biāo)1和目標(biāo)2的上限值；對(duì)于（3）集合內(nèi)路徑不止1條，決策者可以根據(jù)個(gè)人偏好或采用模糊多目標(biāo)格序決策進(jìn)行進(jìn)一步選擇。

4 算法步驟及復(fù)雜度

4.1 算法步驟

經(jīng)過前面的分析，很容易得到雙目標(biāo)最短路問題的算法步驟：

（1）利用Dijkstra算法分別算出網(wǎng)絡(luò)圖G=（N，E）中目標(biāo)1和目標(biāo)2的最短路和。

（2）若=，則算法結(jié)束，否則轉(zhuǎn)步驟（3）

（3）令和為路徑和的目標(biāo)值，并給出目標(biāo)1和目標(biāo)2的上限up和up。

（4）利用k-最短路算法分別算出上限up和up的路徑集合和

（5）取和的交集

（6）若轉(zhuǎn)步驟（7）；若，決策者認(rèn)為此方案可行則停止，否則轉(zhuǎn)步驟（7）；若，若決策者認(rèn)為都可行則停止，否則轉(zhuǎn)步驟（7），

（7）繼續(xù)調(diào)整目標(biāo)1和目標(biāo)2的上限值，轉(zhuǎn)步驟（4）。

4.2 算法復(fù)雜度

首先利用Dijkstra算法時(shí)的復(fù)雜度為，然后利用k-最短路算法的復(fù)雜度為，考慮到需要對(duì)上限進(jìn)行修改，但其計(jì)算復(fù)雜度仍可記為[12]。

5 算例

圖5給出了一個(gè)地鐵站點(diǎn)布設(shè)方案圖，邊權(quán)分別代表實(shí)際距離和該線路客流吸引量，如表1所示?，F(xiàn)需要得出從起點(diǎn)到終點(diǎn)的一條線路，使得吸引客流量之和最大，且線路長(zhǎng)度之和最小。

由于是求吸引量最大，不能直接利用上述算法，需要進(jìn)行處理，可用最大值50分別減去各個(gè)吸引量值，如表2所示。

為了表示方便，先利用k-最短路算法求出從起點(diǎn)至終點(diǎn)各個(gè)目標(biāo)的最短路序列，如表3所示。

然，目標(biāo)1和目標(biāo)2的最短路并不在同一條線路上，因此交集，此時(shí)，需要對(duì)兩個(gè)目標(biāo)上限進(jìn)行適當(dāng)擴(kuò)大，并利用k-最短路算法求出有效路徑的集合，如表4所示。

由此可見，若決策者要求目標(biāo)1，2的上下限不超過（4，35），那么最優(yōu)線路只有O-1-5-D，其線路長(zhǎng)度為4，客流吸引量為40+39+37=116。

在實(shí)際決策中，決策者可以根據(jù)實(shí)際情況增加決策變量，演變成多目標(biāo)最短路問題，求解思路類似，從而達(dá)到良好的實(shí)際效果。

6 結(jié)論

文章根據(jù)站點(diǎn)布設(shè)的原則和方法，并結(jié)合列車運(yùn)行工況對(duì)站間距的合理范圍進(jìn)行了分析，建立了站點(diǎn)布設(shè)的雙目標(biāo)最短路模型，并利用Dijkstra算法和k-最短路算法對(duì)有效路徑進(jìn)行搜索，最終得到滿意路徑。此方法可以為實(shí)際的軌道交通站點(diǎn)布設(shè)提供一種新的思路，起到輔助決策作用。

參考文獻(xiàn)

[1] 魏金麗，城市軌道交通站點(diǎn)布設(shè)研究[D]。長(zhǎng)安大學(xué)碩士學(xué)位論文，2006

[2] 李媛媛，市域軌道交通快線的合理站間距研究[D]。北京交通大學(xué)碩士學(xué)位論文，2011

[3] 吳紅兵，城市軌道交通線路與站點(diǎn)規(guī)劃理論研究[D]。重慶大學(xué)碩士學(xué)位論文，2006

[4] 朱蓓玲，合理確定地鐵車站站間距離[J]。鐵道標(biāo)準(zhǔn)設(shè)計(jì)，1999（3）：19-20。

[5] 李君，葉霞飛，城市軌道交通車站分布方法的研究[J]. 同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2004（8）：1009-1014

[6] Current J，Revelle C，Cohon J. An interactive approach to indentify the best compromise solution for two objective shortest path problems[J]. Computer & Ops，Res，1990，17（2）：187-198.

[7] Coutinaho-Rodrigues J，Climcao J，Current J. An interactive bi-objective shortest path approach：search for unsupported non-dominated solution[J]，Computer & Ops. Res，1999，26：789-798

[8] 郝光，張殿業(yè)，王東梅，雙目標(biāo)最短路有效解的快速算法[J]. 公路交通科技，2007（11）：96-99+104

[9] CHEN Y L，An algorithm for finding the k quickest path in a network[J]，Computer & Ops. Res，1992，20（1）：59-65