公交換乘算法

本文格式為Word版，下載可任意編輯——公交換乘算法

提供了一次、二次的換乘算法

三個(gè)表（最簡(jiǎn)單化，不考慮模糊查詢，單行線等其他東西）：

1，站點(diǎn)表stop(stop_id,stop_name)

2，路線表line(line_id,line_name)

3，路線站點(diǎn)表(點(diǎn)線路關(guān)系表)linestops(line_id,stop_id,seq)此處的seq指某站點(diǎn)在某線路中的順序。

現(xiàn)在分析算法：

1，直達(dá)線路

首先根據(jù)兩個(gè)站點(diǎn)名獲取兩個(gè)站點(diǎn)各自的id，這里定義為id1,id2

然后查詢

selectline_idfrom

(selectline_idfromlinestopswherestop_id=id1)A,

(selectline_idfromlinestopswherestop_id=id2)B

whereA.line_id=B.line_id

即得到可直達(dá)的線路列表

2,一次換乘

首先根據(jù)兩個(gè)站點(diǎn)名獲取兩個(gè)站點(diǎn)各自的id，這里定義為id1,id2

然后搜尋兩個(gè)站點(diǎn)通過直達(dá)方式各自能夠到達(dá)的站點(diǎn)集合，最終他們的交集就是我們所需要的換乘站點(diǎn)。

selectstop_idfrom

(

selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id1)

)A,

(

selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id2)

)B

whereA.stop_id=B.stop_id

得到換乘站（可能有多個(gè)或0個(gè)）后，剩下的就是顯示能夠到達(dá)換乘站的兩邊線路，這通過前面的直達(dá)查詢即可。

3，二次換乘

首先根據(jù)兩個(gè)站點(diǎn)名獲取兩個(gè)站點(diǎn)各自的id，這里定義為id1,id2

算法的中心思想是：站點(diǎn)1能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合A，站點(diǎn)2能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合B，A和B之間有直達(dá)的線路。

一步一步來(lái)：

站點(diǎn)1能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合A：

selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id1)

站點(diǎn)2能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合B：

selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id2)

而直達(dá)的查詢是

selectline_idfrom

提供了一次、二次的換乘算法

(selectline_idfromlinestopswherestop_id=id1)C,

(selectline_idfromlinestopswherestop_id=id2)D

whereC.line_id=D.line_id

我們把=id1和=id2換成in(select)A和in(select...)B

這樣最終我們的查詢是

selectline_idfrom

(selectdistinctline_idfromlinestopswherestop_idin)C,

(selectdistinctline_idfromlinestopswherestop_idin)D

whereC.line_id=D.line_id

其中是

（selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id1))

其中是

（selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id2))

這樣子我們找到了作為中間換乘的線路（可能有多條或者0條），對(duì)列舉的的每一條假設(shè)命名為X線，下一步就是找出可以從站點(diǎn)1到達(dá)X任意一個(gè)站點(diǎn)的直達(dá)線路、和可以從站點(diǎn)2到達(dá)X任意一個(gè)站點(diǎn)的直達(dá)線路即可。

那么與前面的算法相像，我們?cè)谡军c(diǎn)1所有能夠到達(dá)的站點(diǎn)中去尋覓和線路X相交的站點(diǎn)，然后再去找這兩個(gè)點(diǎn)的線路

selectstop_idfrom

(selectdistinctstop_idfromlinestopswhereline_idin

(selectline_idfromlinestopswherestop_id=id1))A,

(selectstop_idfromlinestopswhereline_id=X)B

whereA.stop_id=B.stop_id

找到站點(diǎn)了，下面就是根據(jù)已經(jīng)解決的直達(dá)查詢找線路了。

站點(diǎn)2類似。

以上的算法有一個(gè)優(yōu)點(diǎn)，全部是sql完成搜尋，所以asp代碼只需寥寥幾行循環(huán)而已。但是缺點(diǎn)是：慢,終究可能涉及了數(shù)百次sql查詢。而且只是用最簡(jiǎn)單的sql方法去算出所有可以換乘的方案，不涉及最優(yōu)/最短的算法。假使是最短路徑，那得用特別結(jié)構(gòu)和算法。

另外:

根據(jù)出行者輸入的起點(diǎn)和終點(diǎn)，確定出行要選擇的起始公交站點(diǎn)A和目的公交站點(diǎn)B。探尋數(shù)據(jù)庫(kù)，查詢站點(diǎn)A和站點(diǎn)B之間是否有一致的車經(jīng)過，假使有一條或幾條直達(dá)線路，通過比較選擇距離最短的公交線路推薦給出行者。假使沒有，則計(jì)算站點(diǎn)A和站點(diǎn)B之間有沒有一個(gè)公共站點(diǎn)C，從站點(diǎn)C可以換乘到達(dá)站點(diǎn)B。這就有兩種狀況：(1)假使有，屬于一次換乘。計(jì)算站點(diǎn)A和公共站點(diǎn)C之間有沒有一致的公交車經(jīng)過并存入集合X；同樣，計(jì)算站點(diǎn)B和公共站點(diǎn)C之間有沒有一致的公交車經(jīng)過并存入集合Y。將這兩個(gè)集合比較后就可以得到從站點(diǎn)A經(jīng)過公共站點(diǎn)C到達(dá)站點(diǎn)B的公交線路，在這些線路中進(jìn)行比較，選擇距離最短的推薦給出行者。（2）假使沒有公共站點(diǎn)C，就出現(xiàn)了要換乘兩次的狀況。將經(jīng)過站點(diǎn)A的每條公交線路的所有站點(diǎn)存入集合O；同樣，經(jīng)過站點(diǎn)B的每條線路的所有站點(diǎn)存入集合P。比較這兩個(gè)集合，先乘經(jīng)過站點(diǎn)A的某一路車到達(dá)某一站點(diǎn)D，計(jì)算站點(diǎn)D與站點(diǎn)B之間有沒有公共站點(diǎn)E,假使有則站點(diǎn)D、E為換乘站點(diǎn)。這種方案可能有多種，

提供了一次、二次的換乘算法

比較選擇距離最短的推薦給出行者。假使不存在公共站點(diǎn)E，說明經(jīng)過兩次換乘無(wú)法從站點(diǎn)A到達(dá)站點(diǎn)B，中止探尋計(jì)算。

公交出行最優(yōu)路線具體算法：

1）輸入起始站點(diǎn)A和目的站點(diǎn)B；

2）探尋系統(tǒng)數(shù)據(jù)庫(kù)，經(jīng)過起始站點(diǎn)A的公交線路存為X(i)(i=1,2,3…,m,m為正整數(shù))，經(jīng)過目的站點(diǎn)B的公交線路存為Y(j)(j=1,2,3,…n,.n為正整數(shù))；

3）判斷是否有X(i)=Y(j)，將滿足條件的存入Z。若Z＝1，則該條公交線路X(i)即Y(j)為從站點(diǎn)A到站點(diǎn)B的直達(dá)最優(yōu)線路，輸出結(jié)果并終止運(yùn)算。Z≥1，計(jì)算Z中各條線路的距離，選擇一條距離最短的線路，輸出結(jié)果并終止運(yùn)算；

4）探尋系統(tǒng)數(shù)據(jù)庫(kù)，公交線路X(i)所包含的站點(diǎn)存為O(i,u)(u=1,2,3…,g,g為正整數(shù))公交線路Y(j)所包含的站點(diǎn)存為P(j,v)(v=1,2,3…,h,h為正整數(shù))；

5）判斷是否有O(i,u)=P(j,v)，將滿足條件的存入W。若W＝1，則站點(diǎn)O(i,u)即P(j,v)為從站點(diǎn)A到站點(diǎn)B的一次換乘站點(diǎn)，公交線路X(i)，Y(j)為換乘一次的最優(yōu)路線，輸出結(jié)果并終止運(yùn)算。若W≥1，分別計(jì)算每條換乘路線的距離，選擇一條距離最短的線路，輸出結(jié)果并終止運(yùn)算；

6）探尋系統(tǒng)數(shù)據(jù)庫(kù)，經(jīng)過站點(diǎn)O(i,u)的公交線路存為R(k)(k=1,2,3…,p,p為正整數(shù))，公交線路R(k)所包含的站點(diǎn)存為G(k,t)(t=1,2,3…,q,q為正整數(shù))；

7）判斷是否有G(k,t)=P(j,v)，將滿足條件的存入S。若S＝1，則站點(diǎn)G(k,t)即P(j,v)為從站點(diǎn)A到站點(diǎn)B的二次換乘站點(diǎn)，公交線路X(i)，R(k)，Y(j)為換乘二次的最優(yōu)路線，輸出結(jié)果并終止運(yùn)算。若S≥1，分別計(jì)算每條換乘二次的路線距離，選擇一條距離最短的線路，輸出結(jié)果并終止運(yùn)算；

8）以上步驟沒有找到適合的公交線路,輸出“沒有找到換乘次數(shù)不超過兩次的最優(yōu)公交線路〞，終止運(yùn)算。

本文探討的公交出行最優(yōu)路線算法，主要是以距離為標(biāo)準(zhǔn)。在得出了換乘方案之后，可以進(jìn)一步考慮時(shí)間因素，從而找到更具優(yōu)勝性的換乘方案，這有待進(jìn)行進(jìn)一步的探討、研究。

一、公交換乘問題的算法分為兩個(gè)步驟：

1、構(gòu)造并求解換乘矩陣，獲得公交換乘方案(即從起點(diǎn)到終點(diǎn)最少換乘次數(shù)，及換乘站點(diǎn))。有三種實(shí)現(xiàn)形式：

①、求得所有節(jié)點(diǎn)T矩陣，兩個(gè)節(jié)點(diǎn)直達(dá)設(shè)為1，兩個(gè)節(jié)點(diǎn)不通或需要換乘設(shè)為0；參見《公共交通系統(tǒng)最正確路徑算法》

②求得所有線路的T矩陣，兩條線路相交設(shè)為1，兩個(gè)線路不相交設(shè)為0；參見《基于鄰接矩陣的公交換乘算法的研究》(注該算法屬于理想化算法)

③通過上述第2個(gè)步驟縮小范圍，然后用第一個(gè)步驟求得確切結(jié)果

2、根據(jù)最少換乘次數(shù)，縮小求解范圍，求解起始站點(diǎn)與目標(biāo)站點(diǎn)間的最短路徑，進(jìn)而得到最正確路徑。

最短路徑獲得有以下幾種形式：

①、最簡(jiǎn)單的實(shí)現(xiàn)方法：假使上面1的最少換乘次數(shù)、換乘站點(diǎn)都能求解出來(lái)，只需要查詢換乘次數(shù)最少的狀況下，所有可能的路徑中站點(diǎn)數(shù)最少的線路即為所求(前提，假設(shè)所有站點(diǎn)之間的距離大致相等)；

②、假使上面1只求出來(lái)最少換乘次數(shù)，這時(shí)需要用算法求最短路徑，常用的方法是改進(jìn)Dijkstra算法，也就是在Diskstra算法中增加了一條判斷最少換乘算法的一項(xiàng)；

提供了一次、二次的換乘算法

③、在游戲設(shè)計(jì)程序中，經(jīng)常要涉及到最短路徑的上述，最常采用的算法是A*算法，參見《游戲地圖最短路徑探尋設(shè)計(jì)與實(shí)現(xiàn)》和《A算法》

④、K(=3)條漸次短路徑探尋算法，這種算法國(guó)外用的比較多，由于該算法比較麻煩，國(guó)內(nèi)研究不太多，參見《K(≤3)條漸次短路徑探尋算法的研究》、《一種新的Kth最短路徑探尋算法》和《城市軌道交通換乘票務(wù)清分模型的研究》(碩士論文)

⑤、螞蟻算法，參見《一種仿Dijkstra的螞蟻算法》

其中，②③④⑤步驟中都需要依靠最少換乘次數(shù)來(lái)達(dá)到降低繁雜度的目的。

二、上述算法如能得到很好的實(shí)現(xiàn)，需要建立一個(gè)好的數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)存儲(chǔ)形式

我曾問過兩個(gè)實(shí)際搞過這方面的人，一個(gè)人采用數(shù)組來(lái)存儲(chǔ)，另外一個(gè)所采用鏈表與數(shù)組相結(jié)合的方式(即長(zhǎng)鏈表采用數(shù)組，其它采用鏈表的方式)，其實(shí)，之所以有上述兩個(gè)存儲(chǔ)形式，主要是由于這兩個(gè)人算法中側(cè)重面不同，前一個(gè)側(cè)重實(shí)現(xiàn)最少換乘次數(shù)，后一個(gè)則側(cè)重最短路徑的實(shí)現(xiàn)。

2、數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，可參考《城市公交網(wǎng)絡(luò)出行路徑選擇的計(jì)算機(jī)算法研究》、《基于GIS的標(biāo)準(zhǔn)公交基礎(chǔ)信息系統(tǒng)》《基于GIS的公交乘客出行路徑選擇模型》，考慮到公交換乘，所以尋常狀況下，把相近的站點(diǎn)(站點(diǎn)名一樣但地理位置不同的、站點(diǎn)名不一樣但地理位置很接近的)作為公交網(wǎng)絡(luò)拓?fù)浣Y(jié)