城市公交線路優(yōu)化的數(shù)學(xué)模型和算法

安志宏 劉旭浩

摘要： 隨著我國城市化的不斷發(fā)展，城市的交通狀況成了擺在我們面前的亟待解決的一個(gè)問題.建立數(shù)學(xué)模型的方式，以“分離目標(biāo)，逐次優(yōu)化”為原則，假設(shè)的乘客OD量和公交行駛時(shí)間已知，對(duì)公交線網(wǎng)進(jìn)行布設(shè)和優(yōu)化，并且逐步修正.在保證線路走向能與主要客流方向基本一致的情況下，實(shí)現(xiàn)全服務(wù)區(qū)總乘行時(shí)間最短，換乘次數(shù)最少，客流分布均勻的目標(biāo).

關(guān)鍵詞： 最優(yōu)路徑公交網(wǎng)絡(luò)乘客OD量

隨著城市建設(shè)的迅猛發(fā)展，公交出行已成為人們的一個(gè)重要出行方式。公共交通作為一個(gè)城市經(jīng)濟(jì)發(fā)展的象征性基礎(chǔ)設(shè)施，它為廣大居民的日常出行提供了方便，因此也關(guān)系到一個(gè)城市的基本保障問題.優(yōu)化公交網(wǎng)絡(luò)，提高公交運(yùn)載效率越發(fā)受到社會(huì)的關(guān)注，成為人們的迫切需求.

公交規(guī)劃就是一個(gè)多目標(biāo)的優(yōu)化問題.進(jìn)行公交優(yōu)化設(shè)計(jì)需要區(qū)分主次，設(shè)定專門的優(yōu)化措施.為此，我們提出了“分離目標(biāo)，逐步解決”的辦法.主要是利用數(shù)學(xué)模型，通過計(jì)算機(jī)進(jìn)行處理，得到一個(gè)初步優(yōu)化完善的公交網(wǎng)絡(luò).再適當(dāng)做些調(diào)整，使得線路能夠分布相對(duì)均勻，消除空白的公交區(qū)域.

1.Dijkstra算法

Dijkstra算法是很有代表性的最短路算法，其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合.一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知.初始時(shí)，S中僅含有源.設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長度.Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改.一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長度.

2.公交線路布設(shè)模型

2.1公交線路的布設(shè)原則

公交網(wǎng)絡(luò)本身具有快捷、靈活、網(wǎng)絡(luò)覆蓋率高的特點(diǎn)，適合中短距離出行.一般公共汽車的起訖站點(diǎn)相隔在500m到800m之間，如果是在城市中心的話站點(diǎn)之間可以縮短到400m，時(shí)間上在客流高峰的時(shí)候發(fā)車間隔會(huì)在3到5分，除此之外的時(shí)間可以增加到6到8分，站點(diǎn)設(shè)置一般能和其他站點(diǎn)有較好的換乘[1].

2.2城市客流集散點(diǎn)的計(jì)算

在已知公交OD矩陣的條件下，將研究區(qū)域劃分成若干地理性質(zhì)相似的區(qū)域，也可以依據(jù)行政意義進(jìn)行劃分，把每一個(gè)分好的小區(qū)看作一個(gè)單一的節(jié)點(diǎn)，同時(shí)又要能被城市中的主要干路線路貫通，然后通過具體分析可以確定以下指標(biāo)，并且作為節(jié)點(diǎn)的重要度指標(biāo).這些指標(biāo)有地理位置、路況、OD集散程度、人口數(shù)量、金融指標(biāo)等[2].

節(jié)點(diǎn)的加權(quán)平均值為：L■=■α■·■，L■表示區(qū)域內(nèi)節(jié)點(diǎn)i的重要度；

α■表示第j項(xiàng)指標(biāo)的權(quán)重；M是指標(biāo)數(shù)量；e■是節(jié)點(diǎn)i的第j項(xiàng)的指標(biāo).

e■為區(qū)域內(nèi)所有節(jié)點(diǎn)的第j項(xiàng)指標(biāo)算數(shù)平均值.

客流集散強(qiáng)度：E■=∑■q■·δ■■，q■是OD點(diǎn)k，1間的OD客流量（人）

δ■■=1，當(dāng)j，k間的最短路徑經(jīng)過i0，否則

式子中權(quán)重值α■的確定即確定出各個(gè)標(biāo)準(zhǔn)對(duì)于每個(gè)節(jié)點(diǎn)重要程度的影響效果.

2.3線路起訖點(diǎn)確定

客流量集散地點(diǎn)確定以后，就可以根據(jù)公交區(qū)域的客流量（OD量），即根據(jù)交通區(qū)域的發(fā)生量還有吸收量最終找到起訖點(diǎn).

2.3.1按照客流量設(shè)定站點(diǎn)

當(dāng)交通小區(qū)處于高峰時(shí)期，發(fā)生量和吸引量都超過了此線路中間站點(diǎn)的最大運(yùn)載能力的時(shí)候，僅僅依靠中間站點(diǎn)無法完成運(yùn)載任務(wù)，那么這個(gè)交通小區(qū)就要設(shè)置為起訖站點(diǎn)，從而增加運(yùn)載量.所以可以依據(jù)中間站點(diǎn)的運(yùn)載量設(shè)定起訖站.某一個(gè)交通小區(qū)發(fā)生量和運(yùn)載量超過某一個(gè)值時(shí)候，需要設(shè)定站點(diǎn).

單個(gè)中間站點(diǎn)運(yùn)輸力為C■=60B/t■，C■是中間站點(diǎn)運(yùn)載力（即人次/高峰小時(shí)）；t■是高峰每小時(shí)的發(fā)車時(shí)間間距；B是高峰小時(shí)每輛車從中間站搭乘乘客數(shù)量的平均值，所取的值可以通過調(diào)查得出.交通小區(qū)中間站運(yùn)載力為c（i）=c■N（i），全規(guī)劃區(qū)域的站點(diǎn)個(gè)數(shù)N■=ρs/d，N■為全規(guī)劃區(qū)域站點(diǎn)的數(shù)量；ρ是規(guī)劃的公交網(wǎng)絡(luò)的密度；S是規(guī)劃區(qū)域的面積；d為站點(diǎn)的平均間隔.

先根據(jù)各個(gè)交通小區(qū)的出行數(shù)量的相對(duì)值大小確定出中間站的數(shù)量N（i），N（i）=N■T（i）/T，T（i）為交通小區(qū)公交乘客發(fā)商量或者是吸引量的總和；T為全規(guī)劃區(qū)域的公交發(fā)生量的總和.T=■T（i），一個(gè)起訖站點(diǎn)的最大運(yùn)載力為C■=60Rr/（t■k■）.

2.3.2按照實(shí)際的要求設(shè)置起訖點(diǎn)

一些特殊的地區(qū)，如汽車車站、熱門旅游景點(diǎn)、船運(yùn)港灣、生活區(qū)等，為了滿足乘客的出行路線，服務(wù)人民生活，即使總的發(fā)生量和吸引量沒有達(dá)到設(shè)站的要求，也可以設(shè)定起訖站點(diǎn).

2.4公交線路的校正和優(yōu)化

2.4.1設(shè)置網(wǎng)絡(luò)的最佳走向

確定起訖點(diǎn)以后，就要根據(jù)路段的不同將行駛所用時(shí)間作為阻抗，從而來求得各個(gè)起訖站點(diǎn)配對(duì)以后的最短路徑.又由于這里想到要把優(yōu)化的網(wǎng)絡(luò)經(jīng)過集散點(diǎn)，因此又提出了一個(gè)“集散點(diǎn)吸引系數(shù)”.

2.4.2直達(dá)乘客數(shù)量的校正

2.4.2.1公交線路長短的校正

公交網(wǎng)絡(luò)的路線距離不能過于長和短，必須按照該城市里的實(shí)際情況來確定，對(duì)已經(jīng)擬定的待選路線來篩定.對(duì)于那些不滿足該條件的首末點(diǎn)之間我們不設(shè)定公交線路，這時(shí)候就要把直達(dá)的乘客數(shù)量Z■設(shè)置為0.

2.4.2.2防止線路間的自相配對(duì)

同一個(gè)節(jié)點(diǎn)是不可以作為相同單向路線起訖站點(diǎn)，因此令Z■=0.

2.4.2.3對(duì)于同一區(qū)域設(shè)定多個(gè)站點(diǎn)的校正

當(dāng)有些劃定區(qū)域的出行量值非常大的時(shí)候，就要確定多個(gè)起訖站點(diǎn)了，這個(gè)時(shí)候，在直達(dá)乘客的矩陣?yán)?，相?duì)應(yīng)的起點(diǎn)那一行和終點(diǎn)那一列就要校正，校正次數(shù)和這個(gè)區(qū)域的起訖站點(diǎn)數(shù)量是一致的.

2.4.3所設(shè)定線路的優(yōu)化校正

優(yōu)化線路需要考慮以下問題：校正乘客的OD量，確定OD量的剩余數(shù)值，校正行車時(shí)間，以及復(fù)線系數(shù).

3.實(shí)例

我們假設(shè)一個(gè)交通路線分區(qū)和基本路段的路線圖，OD量我們假設(shè)已經(jīng)通過調(diào)查求出.圖中線路上的數(shù)字是該條路段車輛的行駛時(shí)間（單位：分鐘）.

待選路線中的直達(dá)乘客數(shù)量表示為：

再按照線路的長度要求，防止自相的配對(duì)、一個(gè)區(qū)域設(shè)定多個(gè)站然后再次對(duì)直達(dá)的乘客量進(jìn)行校正.經(jīng)過最后的計(jì)算.OD在[B，C]的乘客量是最大的.這就要設(shè)定一個(gè)B到C、C到B的公交網(wǎng)，那么最短路徑就會(huì)是6-12-18-17-16-15-14-20-19.

通過之前的復(fù)線系數(shù)把第一條公交路通過行車行駛時(shí)間修正（其中的數(shù)值可以參考待選的最短路徑）.到這里，第一條線路設(shè)置工作就全部結(jié)束了，除去B和C點(diǎn)以外，再一次查詢最短路徑，逐次去布設(shè)第二條、第三條公交線，最后得到完整的網(wǎng)絡(luò)線路圖.

現(xiàn)實(shí)生活中公交網(wǎng)絡(luò)問題受到諸多因素的影響，需要綜合考慮這些因素的制約，而且需要搜集大量的數(shù)據(jù)，并進(jìn)行實(shí)際論證，需要通過數(shù)學(xué)建模的方法進(jìn)行研究，合理且便于操作的方法，這也是后續(xù)研究的方向.

參考文獻(xiàn)：

[1]成邦文，王齊莊，胡緒祖.城市公共交通線網(wǎng)優(yōu)化設(shè)計(jì)模型和方法[M].系統(tǒng)工程理論與實(shí)踐.

[2]李維斌.汽車運(yùn)輸工程[M].北京：人民交通出版社，1987.

[3]趙志峰.城市公共交通線路網(wǎng)規(guī)劃方法[J].上海交通大學(xué)學(xué)報(bào)，1988，22（6）.

[4]易漢文.城市公交線路系統(tǒng)的規(guī)劃與設(shè)計(jì)[M].系統(tǒng)工程，1987，5（1）.

[5]肖位樞主編.圖論及其解法[M].北京：航空工業(yè)出版社，1993.

[6]胡運(yùn)權(quán).運(yùn)籌學(xué)教程（第三版）[M].北京：清華大學(xué)出版社，2007.4.