城市公交線路選擇算法優(yōu)化

湯亭亭，嚴(yán) 凌，孫夢瑤

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

生活水平的提高，給人們的出行活動(dòng)在一定范圍內(nèi)帶來了便利，但是隨之而來交通問題的負(fù)反饋使得人們意識(shí)到了合理發(fā)展交通方式的重要性。公共交通已經(jīng)成為城市化發(fā)展和全面提升城市化水平的首要問題[1]。近年來，在公交優(yōu)先的思想下，國內(nèi)各個(gè)城市開始大力發(fā)展公共交通，期望用大容量公共交通系統(tǒng)來改善交通環(huán)境。國外學(xué)者也將乘客出行效率作為整體的優(yōu)化目標(biāo)，在優(yōu)化過程中盡可能地減少換乘次數(shù)、降低出行時(shí)耗[2]。研究表明，居民在公交線路選擇過程中首要關(guān)心的是換乘次數(shù)，其次是花費(fèi)的時(shí)間[3]。當(dāng)乘坐公交出行換乘過于繁瑣而且時(shí)間花費(fèi)大于人們的預(yù)期時(shí)，人們往往會(huì)在下次出行時(shí)重新選擇交通方式。公交站點(diǎn)是乘客起點(diǎn)上車、換乘、終點(diǎn)下車的必須環(huán)節(jié)，根據(jù)調(diào)查數(shù)據(jù)顯示，在公交車的延誤耗時(shí)里，由于站點(diǎn)停車而造成的損失時(shí)間占據(jù)了公交車總運(yùn)行時(shí)間的19%～21%[4]。因此，本文將換乘次數(shù)和站點(diǎn)數(shù)量作為主要的限定條件，盡可能的減少在一次出行過程中的換乘次數(shù)與所經(jīng)過的站點(diǎn)數(shù)量，這將有效地減少乘客乘坐公交的出行時(shí)間，提高出行效率。

1 問題提出及分析

1.1 問題提出

公交路徑的最優(yōu)選擇方案目前依舊是NP 問題[5]，解決此類問題的方法主要可分為三種：第一種是最短路徑的搜索算法，主要代表有Dijkstra 算法，該算法可以快速高效地找出整個(gè)路網(wǎng)所有公交站點(diǎn)間的最短路徑。但是沒有考慮到公交線路之間的換乘次數(shù)，往往得到的公交路徑確實(shí)是最短的，但卻可能需要經(jīng)過數(shù)次換乘才能到達(dá)目的地；第二種是采用數(shù)據(jù)庫或者集合的查詢算法；第三種是基于智能技術(shù)的查詢算法，如遺傳算法。后兩種算法在計(jì)算過程中容易將一些不合理的路徑加入到搜索結(jié)果中，容易產(chǎn)生維數(shù)爆炸問題，不適用于規(guī)模較大的公交網(wǎng)絡(luò)[6]。

1.2 問題分析

最短路經(jīng)典的Dijkstra 算法是計(jì)算網(wǎng)絡(luò)中一個(gè)節(jié)點(diǎn)到其它任意節(jié)點(diǎn)的最短路徑，以已知的起點(diǎn)向外一層一層擴(kuò)散直到尋找到終點(diǎn)為止，該方法的優(yōu)點(diǎn)是可以找到全局最優(yōu)解[7]。但是該算法只考慮路徑最短，并未將換乘次數(shù)考慮在內(nèi)，忽略了乘車人所能接受換乘次數(shù)的心理因素。廣度優(yōu)先迭代從起點(diǎn)開始一層一層往下遍歷所有站點(diǎn)，直至找到目標(biāo)站點(diǎn)，但是存在搜索量大并且耗費(fèi)空間等明顯的缺點(diǎn)。

本文借鑒先前學(xué)者的研究方法，將集合與廣度優(yōu)先迭代相互結(jié)合使用[8]，兩端的集合逐步向外擴(kuò)展并且不斷靠近直至出現(xiàn)兩個(gè)集合共有的交集，在這個(gè)龐大的無向公交路網(wǎng)中，找到所需換乘的最少公交線路的所有路徑。但找的不一定是唯一線路，所以再使用Dijkstra 算法在選擇的換乘最少的線路中找出最優(yōu)線路。

2 廣度優(yōu)先迭代與Dijkstra 算法相結(jié)合的居民出行公交線路優(yōu)化

2.1 基本假設(shè)

（1）一條線路的公交不構(gòu)成環(huán)形回路；

（2）公交車上行和下行站點(diǎn)線路相同；

（3）完整的公交車線路可以覆蓋所有的公交車站點(diǎn)；

（4）公交車的起點(diǎn)和終點(diǎn)的站點(diǎn)固定；

（5）使用Dijkstra算法時(shí)公交站點(diǎn)站距均設(shè)為1，便于尋找站點(diǎn)最少的線路。

2.2 廣度優(yōu)先迭代搜索最少換乘線路

將整個(gè)城市的公交站點(diǎn)線路看成一個(gè)聯(lián)通無向交通網(wǎng)絡(luò)，任意兩點(diǎn)經(jīng)過有限次數(shù)的換乘后都可以到達(dá)。考慮到實(shí)際情況和居民出行心理，需要對(duì)換乘次數(shù)規(guī)定一個(gè)上限。經(jīng)過數(shù)據(jù)研究，乘客所能接受的最多換乘次數(shù)為三次[9]。

第一步：首先假定A,B 為兩個(gè)已經(jīng)確定的起訖點(diǎn)，并且存在于公交路網(wǎng)的公交站點(diǎn)中。設(shè)經(jīng)過A點(diǎn)的所有公交線路為sA(i)，經(jīng)過B點(diǎn)的所有公交線路為sB(j)。

上式中i 和j 分別代表通過A 點(diǎn)和B 點(diǎn)的公交線路，n和m均為正整數(shù)。

判斷集合A和集合B的公交線路交集zl,若集合|zl|=1,則表明AB 兩點(diǎn)有且僅有一條直達(dá)的公交線路，直接輸出集合 |zl|中的線路，結(jié)束運(yùn)算；若集合|zl|＞1，則表明有數(shù)條公交線路可以直達(dá)，使用Dijkstra算法尋找站點(diǎn)最少的線路；若集合|zl|=0，則說明兩站點(diǎn)之間沒有直達(dá)線路，繼續(xù)下一步操作。

第二步：搜索公交線路sA(i)的所有站點(diǎn)數(shù)據(jù)，存入公交站點(diǎn)矩陣M(i,m)(m 為正整數(shù))，搜索公交線路sB(j)的所有公交站點(diǎn)數(shù)據(jù)，存入公交站點(diǎn)矩陣N(j,n)(n為正整數(shù))。判斷矩陣M和矩陣N是否存在名稱相同的站點(diǎn)，若存在，則將該站點(diǎn)存入集合 |XS|中。若集合|XS|=1，則表明AB兩點(diǎn)之間有且僅有一條換乘一次的線路，輸出兩條公交線路名稱i 和j。若集合|XS|＞1，表明有多種換乘線路可以到達(dá)，用Dijkstra算法進(jìn)行下一步處理。若|XS|=0，表明兩站點(diǎn)換乘一次無法到達(dá)，繼續(xù)執(zhí)行。

第三步：將所有經(jīng)過m 站點(diǎn)的公交線路存入公交線路集合M(k)(k 為正整數(shù))。與第二步相同，搜索公交線路sM(k)的所有站點(diǎn)數(shù)據(jù)，存入公交站點(diǎn)矩陣K(m,k)，判斷矩陣K 和矩陣N 中是否存在相同站點(diǎn)，將滿足該條件的站點(diǎn)名稱存入集合YS中。若集合|YS|=1，則表明AB 兩點(diǎn)之間有且僅有一條換乘兩次的線路，輸出三條公交線路名稱i，k 和j。若集合|YS|＞1，表明有多種經(jīng)過兩次換乘線路可以到達(dá)，用Dijkstra 算法進(jìn)行下一步處理。若|YS|=0，表明兩站點(diǎn)換乘兩次還是無法到達(dá)。繼續(xù)執(zhí)行。

第四步：與第三步操作基本相同，將所有經(jīng)過n站點(diǎn)的公交線路存入公交線路集合N(f)(f 為正整數(shù))。搜索公交線路sN(f)的所有站點(diǎn)數(shù)據(jù)，存入公交站點(diǎn)矩陣F(n,f),判斷矩陣F和矩陣K是否存在相同的站點(diǎn)，將相同站點(diǎn)名稱放入公交站點(diǎn)集合WS中。集合|WS|=1，表明AB兩站點(diǎn)有一條換乘三次到達(dá)的線路，輸出四條線路i,k,f 和j。若集合|WS|＞1，表明線路存在多種換乘三次的方式，需做最短路判斷。若|WS|=0，表明兩站點(diǎn)間即使換乘三次也無法到達(dá)。

公交換乘示意圖如圖1所示。

圖1 公交換乘示意圖

最后設(shè)定換乘次數(shù)上限為三次，在換乘次數(shù)不大于三次的迭代前提下找到可行線路并輸出。在實(shí)際編程運(yùn)行過程中，基本任意兩站點(diǎn)都可以做到三次換乘到達(dá)。

由于得到的換乘最少線路不一定唯一，所以需要進(jìn)一步篩選。采用Dijkstra 算法對(duì)換乘最少的線路進(jìn)行進(jìn)一步處理，得到最終的最優(yōu)公交乘車線路。

2.3 Dijkstra算法尋找站點(diǎn)最少線路

用篩選得到的最少換乘次數(shù)的公交線路構(gòu)建有邊權(quán)重的有向無環(huán)圖，將所有公交站點(diǎn)間的距離設(shè)置為1，不相連的站點(diǎn)間距離設(shè)置為無窮大，所有換乘站點(diǎn)看作是所到達(dá)的節(jié)點(diǎn)。接著采用Dijkstra 算法的思想在確定換乘最少的線路中尋找站點(diǎn)最少的線路。首先設(shè)置兩個(gè)集合S 和V，集合S 是一個(gè)逐步擴(kuò)大的頂點(diǎn)集合，用來存放已經(jīng)確定最短路徑的頂點(diǎn)。集合V是初始的尚未確定最短距離的所有頂點(diǎn)的集合。在運(yùn)行中集合S 按照相臨站點(diǎn)路徑長度遞增的順序逐個(gè)添加，直至包含所有頂點(diǎn)，使得V-S為空集。

（1）將已經(jīng)確定的公交起點(diǎn)站點(diǎn)設(shè)為源點(diǎn)O1，則開始時(shí)集合S 只包含頂點(diǎn)O1，再次設(shè)置一個(gè)集合U，令U=V-S，此時(shí)集合U 包含除源點(diǎn)O1的所有頂點(diǎn)。源點(diǎn)O1對(duì)應(yīng)的距離值為0,即D[O1]=0。對(duì)于集合U中所有頂點(diǎn)對(duì)應(yīng)的距離做如下規(guī)定：如果圖中相臨站點(diǎn)間有弧(O1,Vk)，則Vk頂點(diǎn)的距離為這個(gè)邊的權(quán)值，不相連邊的值記為無窮大；

（2）從U 中選擇一個(gè)距離最小的頂點(diǎn)Vk加入到集合S中；

（3）集合S 每加入一個(gè)頂點(diǎn)Vk，就要對(duì)在集合U中的各個(gè)頂點(diǎn)的距離進(jìn)行一次修改，將新加入的頂點(diǎn)Vk作為中間頂點(diǎn)進(jìn)行距離值判斷，若(O1,Vk)+(Vk,Vj)＜(O1,Vj) ，則用 (O1,Vk)+(Vk,Vj) 來代替(O1,Vj)的距離值。

（4）重復(fù)（2）和（3）的操作步驟，將所有集合U 中修改過的最短距離值的頂點(diǎn)加入到集合S中，直到S集合中包含圖中所有頂點(diǎn)，使得S=V。得到的最終結(jié)果為換乘次數(shù)相等的線路間的站點(diǎn)比較，最終得出站點(diǎn)最少的換乘線路。

以換乘一次為例，如圖2 所示，假設(shè)通過廣度優(yōu)先迭代可以確定公交起訖點(diǎn)之間最少換乘次數(shù)為一次，并且有三種換乘線路。此時(shí)構(gòu)建有邊權(quán)重的有向無環(huán)圖，起訖點(diǎn)和換乘站點(diǎn)設(shè)為頂點(diǎn)，公交站距設(shè)為1，可以確定每條邊的距離，不相連的頂點(diǎn)距離設(shè)置為無窮大。

圖2 換乘一次線路圖

圖3 換乘一次有邊權(quán)重的無向圖

如圖3 所示，首先確定集合S={O(0)} ，集合U={A(4),B(2),C(2),D(∞)} ，選擇距離最少的頂點(diǎn)加入到擴(kuò)充集合S 中，S={O(0),B(2),C(2)} ，接著判斷(O,B)+(B,C)是否小于(O,C) ，規(guī)定不相連的頂點(diǎn)距離 為 無 窮 大 所 以 (O,B)+(B,C)＞(O,C) ，同 理(O,B)+(B,A)＞(O,A) ，最 終 結(jié) 果 集 合S={O(0),A(4),B(2),C(2),D(4)}，可以得出訖點(diǎn)O到達(dá)終點(diǎn)D 的最短距離為4，最優(yōu)換乘線路為O→B→D。

3 實(shí)例分析

3.1 公交線路站點(diǎn)數(shù)據(jù)爬取

為了對(duì)模型和算法進(jìn)行驗(yàn)證，本文選取長沙市公交線路作為驗(yàn)證對(duì)象，用python 編程爬蟲技術(shù)，從8684 公交網(wǎng)站爬取長沙市目前的所有公交站點(diǎn)線路，包括每條線路的公交站點(diǎn)名稱與公交站點(diǎn)的經(jīng)緯度數(shù)據(jù)，共有32286條有效站點(diǎn)數(shù)據(jù)。爬取后保存成csv 文件便于后面調(diào)用。爬取后的數(shù)據(jù)如圖4 所示。

3.2 編程實(shí)現(xiàn)

圖4 長沙市公交站點(diǎn)爬取數(shù)據(jù)

使用python 語言按照上面的基本思路進(jìn)行編程實(shí)現(xiàn)，隨機(jī)選取兩個(gè)起訖站點(diǎn)運(yùn)行結(jié)果，其截圖如圖5所示。

圖5 長沙火車站（南坪）到窯嶺東站點(diǎn)運(yùn)行結(jié)果圖

隨機(jī)選取的公交站點(diǎn)起始站點(diǎn)為長沙火車站（南坪），到達(dá)站點(diǎn)為窯嶺東，如圖5所示，從運(yùn)行結(jié)果可以看出最優(yōu)公交線路為9 路，共有五個(gè)公交站點(diǎn)。百度地圖給出兩戰(zhàn)點(diǎn)間的最優(yōu)線路如圖6所示，其最優(yōu)線路也是9 號(hào)線路，并且公交站點(diǎn)數(shù)目也是五個(gè)，初步驗(yàn)證了該算法的有效性。

再次隨機(jī)選取兩個(gè)相距較遠(yuǎn)的公交站點(diǎn)，再次驗(yàn)證算法在多次換乘中運(yùn)行的有效性，其運(yùn)行結(jié)果如圖7所示。

選取的公交站起始站點(diǎn)為楓樹山小學(xué)大橋校區(qū)，到達(dá)站為長沙簡牘博物館。從運(yùn)行結(jié)果可以看出，兩站點(diǎn)之間需要經(jīng)過一次換乘，換乘的線路為917路和122路公交車。將運(yùn)行結(jié)果與百度地圖進(jìn)行對(duì)比分析，如圖8 所示。從圖8 可以看出，百度地圖給出的推薦路線包含了我們所給出的換乘路線，在時(shí)間最短的的運(yùn)行線路中，百度地圖給出了地鐵換乘線路，但是地鐵換乘線路需要步行的距離較長，需要步行2.2km，距離過長。而公交換乘線路出行時(shí)間僅次于地鐵換乘并且步行距離短。

4 結(jié)語

本文采用改進(jìn)的雙向廣度優(yōu)先搜索算法，首先尋找出換乘次數(shù)最少的所有可能的公交路線，再結(jié)合傳統(tǒng)的Dijkstra 算法，將公交站點(diǎn)數(shù)目作為邊權(quán)重的判別方式，能夠準(zhǔn)確地找出在公交線路網(wǎng)絡(luò)中任意兩站點(diǎn)間的最優(yōu)線路。雙向搜索極大地降低了算法在時(shí)間和空間上的復(fù)雜度，提升了算法的運(yùn)行效率，而且用Dijkstra 算法處理簡化后的換乘路網(wǎng)，極大地提高了運(yùn)行效率，避免了需要遍歷所有站點(diǎn)的繁瑣過程，簡化了運(yùn)行過程。

圖6 長沙火車站（南坪）到窯嶺東站點(diǎn)百度地圖推薦線路

圖7 楓樹山小學(xué)大橋小區(qū)到長沙簡牘博物館站點(diǎn)運(yùn)行結(jié)果圖

從上面兩個(gè)實(shí)例運(yùn)算與現(xiàn)有百度地圖做對(duì)比可以說明該公交路徑選擇算法可以準(zhǔn)確地尋找出任意兩公交站點(diǎn)間換乘次數(shù)最少和行程時(shí)間最短的線路，得到了較好的運(yùn)行效果，驗(yàn)證了算法的有效性。

圖8 楓樹山小學(xué)大橋校區(qū)到長沙簡牘博物館站點(diǎn)百度地圖推薦線路