基于雙向搜索的公交路徑選擇算法及優(yōu)化模型_第1頁
基于雙向搜索的公交路徑選擇算法及優(yōu)化模型_第2頁
基于雙向搜索的公交路徑選擇算法及優(yōu)化模型_第3頁
基于雙向搜索的公交路徑選擇算法及優(yōu)化模型_第4頁
基于雙向搜索的公交路徑選擇算法及優(yōu)化模型_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、第27卷第6期吉林大學學報(信息科學版 Vol . 27No . 62009年11月Journal of J ilin University (I nf or mati on Science Editi on Nov . 2009文章編號:167125896(2009 0620579206收稿日期:2009208216基金項目:國家十一五科技支撐計劃基金資助項目(2006BAC21B0124 ; 吉林省科技發(fā)展計劃基金資助項目(20080527作者簡介:張玉春(1965 , 女, 吉林四平人, 吉林大學副教授, 主要從事計算機應用與開發(fā)研究, (Tel 86213086802957(E 2ma

2、il zhangycjlu 1edu 1cn ?;陔p向搜索的公交路徑選擇算法及優(yōu)化模型張玉春a , 韓秀華b , 臧雪柏c (吉林大學a . 公共計算機教學與研究中心; b . 交通學院, 長春130025;c . 計算機科學與技術學院, 長春 摘要:為了解決人們出行公交路徑選擇問題, , , 提出一種基于雙向搜索的公交網絡路徑選擇算法。、出行費用和換乘次數(shù)等因素, 給出一個綜合評價指數(shù)模型, ?;跀?shù)據(jù)庫理論, 算法用數(shù)據(jù)庫表示公交網絡, , 易于實現(xiàn), 執(zhí)行效率較高。關鍵詞:; ; ; ; 綜合評價指數(shù)模型:ASelecti A lgorithm and Op ti m u m Mode

3、l of Public Trans portati on RoutesBased on T wo 2W ay SearchZHANG Yu 2chun a , HAN Xiu 2hua b , Z ANG Xue 2bai c(a . Center of Public Computer Teaching and Research; b . College of Traffic, J ilin University,Changchun 130025, China; c . College of Computer Science and Technol ogy, J ilin University

4、, Changchun 130012, China Abstract:I n order t o s olve the public trans portati on r oute choice p r oble m , the feature of public trans portati on net w ork, compares algorith m s of shortest r oute, and selecti on algorith m of public trans portati on net w ork r outes is analyzed based on t w o

5、 2way search . I n order t o select op ti m um r oute, thinking about the fact ors which are ti m e of transfers, cost of running and ti m es of transfers, a compound evaluati on index model is obtained . An exa mp le is given t o valldate possibility of the algorith m and the model . Based on the d

6、atabase theory, the algorithm exp res 2ses the public trans portati on net w ork with the database, realizes the most superi or riding pass choice with the da 2tabase inquiry technol ogy, it is easy t o realize, and t o be efficient .Key words:public trans portati on net w ork; shortest r oute; op t

7、i m um r oute; breadth first search; compound eval 2uati on index model引言當前, 我國許多大城市都存在著交通擁擠堵塞的問題, 而大力發(fā)展公共交通是解決城市交通問題的重要措施。隨著我國城市建設的發(fā)展和國際交往的增多, 在當前和今后一段時期內, 城市公共交通線路都會不可避免地經常發(fā)生調整變動, 城市中各類人員對公交信息的查詢需求不斷增加。但我國城市公交乘客信息系統(tǒng)的發(fā)展處于一個落后的水平, 廣大乘客可以獲得信息的方式很少, 公交信息的完整性和準確性得不到保證, 而且沒有專門的機構負責信息的發(fā)布和管理。如果能提供一種服務, 為市

8、民特別是外來旅游、出差、就醫(yī)等急需了解本地道路情況的人們提供方便、快捷、經濟、高效地利用公交線路的方案, 他們的出行和生活將更加方便。1問題的提出一般情況, 人們總是喜歡選擇從起點到終點的最短路徑。比如, 司機開車要從A 地到達B 地, 就會考慮走路程最短或時間最少的路徑, 這是考慮路程或時間的最短路徑問題。然而在公交網絡模型中, 最短路徑并不是決定公交出行路徑選擇的主要因素, 最優(yōu)路徑的選擇會受到出行費用、出行耗時、出行距離、換乘次數(shù)等因素的綜合影響。出行耗時是乘客在一次出行過程中所需的時間, 它包括車上耗時和車外耗時; 間, 比如從出發(fā)地到上車站點所用時間、車站等車時間、地所用時間。換車的

9、次數(shù)1。, 也和出行耗時相關聯(lián)。, 。如果直接用圖論中的方法描述公交網絡、。2211一個圖G 可以表示為G =(V, E , 其中V 是有窮而非空的頂點集合, E 是邊集合, 可用一對頂點(v i , v j 表示。如果邊是頂點的有序對, 則這個圖是有向圖。對G 中的一條邊(v i , v j , 相應地有一個數(shù)L (v i , v j 稱為邊的權, 也稱為邊的長度。圖G 連同其上的權被稱為賦權圖。一個頂點序列v 0, v 1, v 2, , v k , 稱為從v 0到v k 的一條路經, 路徑的長度L (v 0, v k =L (v 0, v 1 +L (v 1, v 2 +L (v k -

10、1, v k 。從v 0到v k 的所有路徑中, 權L (v 0, v k 最小的路徑稱為從v 0到v k 的最短路徑2。212公交網絡特點公交網絡是個賦權有向圖, 站點是頂點, 邊的權值可以是路段的長度、路段通行時間等, 同一條路段上可以有多條公交線路, 每條公交線路都有固定的行駛路線和??空军c。公交網絡有如下特點3:1 連通性。如果兩條不同公交線路經過同一站點并都能在該站點換車, 則這兩條公交線路是連通的, 但換車需要消耗時間和費用等。相反, 如果兩條公交線路沒有相交點或有相交點, 但該點不是公交站點或不是同時有站點, 則這兩條公交線路是不連通的, 不連通的兩條公交線路是不能換乘的。2 節(jié)

11、點特性。由于不同的公交線路即使行駛線路有重疊, 但他們的??空军c不可能完全重疊, 所以乘客換乘時, 有時需要步行一段距離才能到達另外一條公交線路的站點。在描述公交網絡時, 考慮到不同公交線路之間的換車問題, 往往需要把空間上相近但不重疊的不同線路上的站點, 合理抽象成公交網絡圖上的相關節(jié)點。3 最短路徑意義。公交網絡的最短路徑有別于道路網絡上的最短路徑。道路網絡的最短路徑是兩點之間最短距離或最短時間, 既為最優(yōu)路徑。公交網絡中兩點之間的路徑受公交線路的制約, 從一條公交線路到另一條公交線路的換車會增加時間成本和費用成本, 所以就不能為尋找簡單的最短距離的路徑而隨意換車。通常, 在公交路徑選擇時

12、, 要綜合考慮出行時間、費用、方便性(如換乘 等交通阻抗, 交通阻抗值越小路徑越優(yōu), 它們也被稱之為最短路經因素, 是乘客選擇公交線路的依據(jù)。圖論中求最短路徑算法著重考慮任意兩個頂點間最短路徑, 只要兩個頂點有道路連接, 就可進行搜索, 而不考慮該路徑換乘問題, 這就可能造成搜索到的路徑需多次換乘, 因換乘帶來的換乘時間和車票費用會增加交通阻抗。筆者給出了基于最小換乘次數(shù)的路徑選擇算法及綜合評價指數(shù)優(yōu)化模型。3公交網絡最短路徑常用算法比較目前, 出行決策模型方面的研究主要集中在以換乘次數(shù)最少為主要目標, 出行耗時最少(或出行距離最短 為次要目標的一個問題求解模型。求解模型的算法主要有改進的D

13、ijksta 算法和廣度優(yōu)先搜085吉林大學學報(信息科學版 第27卷索或深度優(yōu)先搜索算法4, 5。傳統(tǒng)的D ijkstra 算法不適合公交網絡中最短路徑的選擇。在公交網絡中, 將每個公交站點看成網絡上的頂點, 每相鄰站點間的路段看作一條邊。如果采用D ijkstra 算法, 要計算從站點A 到站點B 之間的最短距離, 只要網絡圖中兩個頂點之間有邊存在, 它就會進行搜索, 而不考慮換乘問題, 這樣搜索的路徑可能是從站點A 到站點B 距離最短的, 但可能需要換乘多次才能到達, 這樣會增加時間和費用消耗。因為換乘次數(shù)少是大部分乘客出行時考慮的首要因素, 所以這樣的路徑對于司機來說非常有用, 但對乘

14、客卻不是最佳選擇。改進的D ijkstra 算法可以借助于最小換乘次數(shù)矩陣, , 但D ijkstra 最短路徑算法要求網絡拓撲圖簡潔, 對于復雜的公交網絡拓撲, 網絡拓撲圖, 這無疑增加了程序的復雜性。, 增加了算法不必要的執(zhí)行次數(shù)。, , 用數(shù)據(jù)庫表示公交網絡, 6, 完全可以滿足用戶出行查詢的需求。選擇算法4廣度優(yōu)先搜索遵循從初始結點開始一層層擴展, 直到找到目標結點的搜索規(guī)則, 它只能較好地解決頂點不是很多、層次不是很深的情況。如果擴展結點較多, 而目標結點又處在較深層, 搜索量巨大, 往往就會出現(xiàn)內存空間不夠用的情況, 影響算法的執(zhí)行效率。雙向搜索對廣度優(yōu)先的搜索方式進行了改進, 在

15、路徑的搜索過程中, 初始結點向目標結點和目標結點向初始結點同時進行擴展, 直至在兩個擴展方向上出現(xiàn)同一個子結點, 搜索結束。出現(xiàn)的這個同一子結點, 稱之為相交點。如果確實存在一條從初始結點到目標結點的最短路徑, 則按雙向搜索進行搜索必然會出現(xiàn)“相交”, 即有相交點, 所求路徑為:初始結點相交點目標結點。雙向搜索對廣度優(yōu)先搜索加入了一定的“智能因素”, 使搜索能盡快接近目標結點, 減少了在空間和時間上的復雜度。筆者對雙向廣度優(yōu)先搜索算法進行了改進, 把集合的思想和廣度優(yōu)先搜索方法相結合, 采用從兩端集合同時逐步向外擴展和兩個集合之間逐漸逼近, 直到兩個集合有交集出現(xiàn)的搜索方法。集合可以是線路集合

16、也可以是站點集合。在一個龐大的交通網絡中, 此方法能較塊地尋找出基于最少換乘的最短路徑。為了便于表明算法, 有如下規(guī)定:1 所有線路集合R =R i |i =1, 2, , n; 所有站點集合S =S i |i =1, 2, , m ; 2 R (S i 為經過站點S i 的所有線路集合, S i S; S (R i 為線路R i 上所有站點集合, R i R; 3 V (R i , R j 為R i 和R j 共同經過的站點集合, R i , R j R; 4 L (R, S 為R 中經過站點S 的線路集合; 5 矩陣C 為行、列交叉的二維表, 行為線路、列為站點, C =C ij |R i

17、 R, S j S, i =1, 2, , n, j =1, 2, , m , 且若R i 經過站點S j , 則C ij =1, 否則C ij =0。算法步驟如下。1 分別建立經過起始站點V O 、終點站點V D 的線路集合R (V O 和R (V D 。2 如果R 0=R (V O R (V D <, 則V O 到V D 可直達, 所乘線路為R 0中的任意一條, 路徑為:V O R 0V D , 轉到步驟7 ; 否則要換乘, 執(zhí)行步驟3 。3 建立R (V O 、R (V D 中所有線路經過的站點集合S (R (V O 和S (R (V D 。4 如果S 1=S (R (V O S

18、(R (V D <, 則V O 到V D 經過一次換乘可到達, 一次換乘路徑為:V OL (R (V O , S 1 S 1L (R (V D , S 1 V D , 轉到步驟7 ; 否則需要兩次或多次換乘, 執(zhí)行步驟5 。5 分別建立與R (V O 和R (V D 中線路相交的線路集合R (R (V O 和R (R (V D 。6 如果R 2=R (R (V O R (R (V D <, 則V O 到V D 經過兩次換乘可以到達。設V 21=V (R (V O ,185第6期張玉春, 等:基于雙向搜索的公交路徑選擇算法及優(yōu)化模型R 2 , V 22=V (R (V D , R 2

19、 , 兩次換乘路徑為:V O L (R (V O , V 21 V 21R 2V 22L (R (V D , V 22 V D , 轉到步驟7 ; 否則要經過多次換乘, 認為不可到達。7 由上述步驟得到的路徑是基于最小換乘次數(shù)的。路徑如果有一條, 即為最優(yōu)路徑, 如果有多條, 求出每條路徑的出行耗時或出行距離, 值最小的即為最優(yōu)路徑。5算法示例設有一個包含7條公交線路的公交網, 其線路矩陣如表1所示。表1線路矩陣Tab 11L ine S 1S 2S 3S 4S 5S 67S 89S 10S 11R 11111R 21R 31R 411R 5111R 6111R 711111選擇起點為S 1,

20、 終點為S 7的有效路徑, 其步驟如下。1 由線路表可知, 起點線路集合R (S 1 =R 1, R 4, 終點線路集合R (S 7 =R 5, R 6。2 R 0=R (S 1 R (S 7 =<, 表明從S 1到S 7要換乘。3 R (S 1 中所有線路上站點集合S (R (S 1 =S 1, S 2, S 3, S 4, S 5, S 9, S 10, R (S 7 中所有線路上站點集合S (R (S 7 =S 6, S 7, S 8, S 10, S 11。4 S 1=S (R (S 1 S (R (S 7 =S 10, 則從S 1到S 7一次換乘可到達, 路徑為:S 1L (R

21、 (S 1 , S 10 S 10L (R (S 7 , S 10 S 7, 具體路徑是:S 1R 4S 10R 5S 7。5 與R (S 1 中線路相交的線路集合R (R (S 1 =R 2, R 5, R 7, 與R (S 7 中線路相交的線路集合R (R (S 7 =R 3, R 4, R 7。6 R 2=R (R (S 1 R (R (S 7 =R 7, 則S 1到S 7經過兩次換乘也可到達。V 21=V (R (S 1 , R 7 =S 3, S 4, S 9, S 10, V 22=V (R (S 7 , R 7 =S 10, S 11, 路徑可表示為:S 1L (R (S 1 ,

22、 V 21 V 21R 2V 22L (R (S 7 , V 22 S 7, 共有8條, 分別為:S 1R 1S 4(或S 9 R 7S 10R 5S 7; S 1R 1S 4(或S 9 R 7S 11R 6S 7; S 1R 4S 3(或S 10 R 7S 10R 5S 7; S 1R 4S 3(或S 10 R 7S 11R 6S 7。6綜合評價指數(shù)模型乘客選擇公交線路的主要依據(jù)是線路交通阻抗。公交線路交通阻抗值是指乘客在公交線路上出行的出行時間、費用、方便性(如換乘 等綜合費用指數(shù)。由上述可知, 從S 1到S 7經過一次換乘或兩次換乘都可以到達。如果是基于最小換乘次數(shù), 步驟4 得到的路徑

23、是最優(yōu)路徑。但如果基于最少出行耗時或最短出行距離, 步驟4 得到的路徑不一定是最優(yōu)的。1999年在南京市的8個主要公交站點進行了一次出行時首選考慮因素的心理問詢調查, 調查結果是41116%的乘客首選換乘最少, 30193%的乘客首選耗時最少10。筆者給出了一個綜合考慮換乘次數(shù)、出行時間和出行費用的綜合評價指數(shù)模型, 分別計算出每條路徑的綜合評價指數(shù), 其值最小的路徑既為最優(yōu)路徑。定義路徑的綜合評價指數(shù)M in:(R k =1T k +2M ks . t . T k =t c k +t b k +t d k +t hk 1+2=1285吉林大學學報(信息科學版 第27卷t c k =s k i

24、 =1t ck i ; th k =n k t h ; M k =n k +1i =1m k i其中R k 表示第k 條可行路徑, 由s k (s k >0 個相鄰路段組成, T k 和M k 分別表示路徑R k 上的出行耗時和出行費用。T k 包括乘車時間t c k (行駛時間和停站時間 、步行時間t b k 、等車時間t d k 和換乘耗時t h k 。t c k i 為第i 條路段的乘車時間, n k (n k =0, 1, 2 為換乘次數(shù), t h 為平均換乘時間, m k i 為第i 條路線的票價, 共有n k +1條線路。1和2表示權重, 1=1表示注重時效性; 2=1表示注

25、重經濟性; 10且20表示注重綜合性11。為換乘代價因子, 。通過求解最小的出行時間達到抑制換乘的作用。的程度確定。損失程度越大, 越不方便, 則值越大。在綜合評價指數(shù)模型中含有不同指數(shù), 其量綱也不同M k 轉化為時間價值H k , 采用居民人均國民收入值進行轉換12H k =M k ×480××26010000=1215M k (m in k (1, , 的綜合評價指數(shù), 取值最小的路經為最優(yōu)路經。綜合評價指數(shù)值越小, 、費用也越小, 也即說明路徑越優(yōu)。, 假設從起始站點S0148到目的站點S0485有兩條可行路徑, 一次換乘路徑R 1和兩次換乘路徑R 2。為

26、了簡化計算, 在這里忽略步行時間和等車時間, 根據(jù)綜合評價指數(shù)模型計算的指數(shù)值如表2所示。表2站點S0148S0485路徑的綜合評價指數(shù)值Tab 12Stand S0148S0485r oute compound evaluati on index1(R 1 (R 2 03715621501571157515110106108810其中R 1的出行耗時為106m in, 出行費用為3元; R 2的出行耗時為88m in , 出行費用為5元。結果表明, 當1=0時, 注重經濟性, 最優(yōu)路徑為R 1; 當1=015時, 注重綜合性, 最優(yōu)路徑為R 1; 當1=1, 注重時效性, 最優(yōu)路徑為R 2。

27、這與實際生活中乘客選擇出行路徑的想法吻合。7結語筆者應用該算法建立了一個長春市公交查詢仿真系統(tǒng)。該系統(tǒng)基于V isual Basic 610開發(fā)環(huán)境, 數(shù)據(jù)庫采用M icr os oft Access2003。系統(tǒng)擁有近100條線路、600個站點, 權重值1和2可由乘客決定。在尋求任意給出的兩個站點之間最佳路徑時, 運算速度較快, 所選路徑合理。由于在建模過程中簡化了許多實際因素, 過于理想化, 因此, 要想建立更好的公交查詢系統(tǒng), 還需要把模型進一步復雜化, 并加入一些實時因素, 充分體現(xiàn)交通網絡的動態(tài)變化特性, 更加逼真地模擬公交網絡, 以滿足乘客的需求。參考文獻:1王建林. 基于換乘次數(shù)

28、最少的城市公交網絡最優(yōu)路徑算法J .經濟地理, 2005, 25(5 :6732676.WANG J ian 2lin . The Public Trans portati on Op ti m u m Route A lgorith m Based on the Least Transfer J .Econom ic Geography, 2005, 25(5 :6732676.2陳簫楓, 蔡秀云, 唐德強. 最短路徑算法分析及其在公交查詢的應用J .工程圖學學報, 2001(3 :20224.CHE N Xiao 2feng, CA I Xiu 2yun, T ANG De 2qiang

29、. Shortest Path A lgorith m Analysis and Its App licati on t o Bus Route Query J .Journal of Engineering Graphics, 2001(3 :20224.3劉光明, 蔡先華, 苗聰, 等. 一種城市公交查詢的算法及其應用J .交通運輸工程與信息學報, 2005, 3(2 :872385第6期張玉春, 等:基于雙向搜索的公交路徑選擇算法及優(yōu)化模型584 91. 吉 林 大 學 學 報 (信 息 科 學 版 第 27 卷 4 向萬里 , 劉洪升 . 城市公交網絡出行路徑選擇的計算機算法研究 J

30、. 蘭州交通大學學報 : 自然科學版 , 2006, 25 X I NG W an 2li, L I Hong2sheng Computer A lgorithm of Route Choice of Trip in U rban Transit Network J . Journal of A U . 40 (3 : 763 2 766. 87 2 91. 340 2 344. I p roved A lgorithm Based on Relational Database Technology for Querying m CHEN Hao, N I G Hong2yun. Shorte

31、st Path Searching A lgorithmbased on Set Calculation J . Computer Engineering, 2007, N on Compound Evaluation Index J . Journal of J ilin University: Infor mation Science Edition, 2008, 26 ( 2 : 180 2 185. neering and Infor mation, 2007, 5 ( 1 : 22 2 27. 33 ( 20 : 199 2 203. 2008, 26 ( 2 : 180 2 185

32、. Southeast University: Natural Science Edition, 2000, 30 ( 6 : 87 2 91. Transit Network J . Journal of Central South University: Science and Technology, 2009, 40 ( 3 : 763 2 766. network J . Journal of J ilin University: Engineering and Technology Edition, 2006, 36 (3 : 340 2 344. J . Journal of Tr

33、ansportation Engineering and Information, 2008 ( 4 : 118 2 125. YANG Xin 2 iao, WANG W ei, MA W en2teng GIS Based Public Transit Passenger Route Choice Model J . Journal of m . ( 1 : 121 2 124. 5 伍雁鵬 , 彭小奇 , 楊恒伏 . 改進的基于關系數(shù)據(jù)庫技術的公交查詢算法 J . 中南大學學報 : 自然科學版 , 2009, WU Yan2 peng, PENG Xiao 2qi, YANG Heng2

34、fu. 6 白子建 , 趙淑芝 , 田振中 . 公共交通網絡優(yōu)化的禁忌算法設計與實現(xiàn) J . 吉林大學學報 : 工學版 , 2006, 36 ( 3 : 7 王世祥 , 饒維亞 . 數(shù)據(jù)庫系統(tǒng)中公交網絡換乘線路的優(yōu)化選擇模型 J . 計算機系統(tǒng)應用 , 2008 ( 4 : 112 2 116. 8 張晉偉 , 鄒云 . 公交網絡最優(yōu)線路查詢模型及軟件開發(fā) J . 交通運輸工程與信息學報 , 2008 ( 4 : 118 2 125. 9 陳 昊 , 寧紅云 . 基于集合運算的最短路徑搜索算法 J . 計算機工程 , 2007, 33 ( 20 : 199 2 203. 12 勝學 , 范炳全 . 公交網絡最優(yōu)路徑求解算法 J . 交通運輸工程與信息學報 , 2007, 5 ( 1 : 22 2 何 27. puter System s App lications, 2008 ( 4 : 112 2 116. 10 新苗 ,

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論