基于ransac-sql的大規(guī)模公交網(wǎng)絡(luò)出行路徑選擇算法

0求解多目標(biāo)規(guī)劃問(wèn)題的算法隨著城市化進(jìn)程的加快，公共交通的半徑也在增加。因此，對(duì)于城市公共交通，行人在移動(dòng)過(guò)程中會(huì)同時(shí)發(fā)送多次。如果你的交換次數(shù)過(guò)多，這將給行人帶來(lái)極大的不便。因此，國(guó)內(nèi)外對(duì)城市公交公共交通的決策和優(yōu)化進(jìn)行了大量研究，以盡量減少行人的交通不便。目前,出行決策模型方面的研究主要集中在以換乘次數(shù)最少和出行距離最短為目標(biāo)形成的一個(gè)多目標(biāo)規(guī)劃問(wèn)題.求解模型的算法主要是在將多目標(biāo)問(wèn)題模型轉(zhuǎn)化為帶有懲罰函數(shù)的單目標(biāo)問(wèn)題后用改進(jìn)的Dijksta算法或Floyd算法求解;另一類(lèi)主要是將多目標(biāo)規(guī)劃轉(zhuǎn)化為有主次之分的兩個(gè)單目標(biāo)規(guī)劃后用廣度優(yōu)先搜索或深度優(yōu)先搜索算法求出行方案,然后在此基礎(chǔ)上應(yīng)用最短路徑算法;第一類(lèi)算法存在的不足主要是將最少換乘次數(shù)目標(biāo)和出行距離最短目標(biāo)用統(tǒng)一的尺度去度量,在統(tǒng)一為同一個(gè)量度的過(guò)程中難以標(biāo)定換算的系數(shù);第二類(lèi)主要是在用深度優(yōu)先搜索或廣度優(yōu)先搜索算法求出行選擇方案的過(guò)程中搜索了大量不合理的出行路徑,增加了算法不必要的執(zhí)行次數(shù).最重要的是大部分算法難以應(yīng)用于大規(guī)模的實(shí)際公交網(wǎng)絡(luò)或計(jì)算機(jī)實(shí)現(xiàn)時(shí)采用的數(shù)據(jù)結(jié)構(gòu)大多是基于數(shù)組和鏈表結(jié)構(gòu),這種方法在應(yīng)用到大規(guī)模公交網(wǎng)絡(luò)中時(shí)容易產(chǎn)生維數(shù)爆炸或不方便管理維護(hù)數(shù)據(jù).根據(jù)文獻(xiàn)中對(duì)城市出行居民出行心理和行為調(diào)查研究的結(jié)果,本文建立以換乘次數(shù)最少和出行距離最短依次為目標(biāo)的出行選擇模型,為方便管理維護(hù)數(shù)據(jù),公交網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)采用大型數(shù)據(jù)庫(kù)來(lái)存儲(chǔ),求解算法采用基于數(shù)據(jù)庫(kù)技術(shù)中的存儲(chǔ)過(guò)程和Transact-SQL語(yǔ)言來(lái)實(shí)現(xiàn)以提高算法執(zhí)行效率.1線路和網(wǎng)點(diǎn)的設(shè)置考慮到實(shí)際公交網(wǎng)絡(luò)規(guī)模都很大,尤其是大城市、特大城市的公交網(wǎng)絡(luò);比如,北京市將近650條公交線路,站點(diǎn)數(shù)約1萬(wàn)個(gè)左右,為使得公交線路、站點(diǎn)等相關(guān)數(shù)據(jù)易于維護(hù)、更新、管理及考慮計(jì)算機(jī)實(shí)現(xiàn)的方便程度和執(zhí)行效率,這里考慮采用大型數(shù)據(jù)庫(kù)SQLServer來(lái)存儲(chǔ)線路、站點(diǎn)及站間距等有關(guān)數(shù)據(jù).1.1線路運(yùn)行方向城市公交網(wǎng)絡(luò)主要是由線路和站點(diǎn)組成,線路方向類(lèi)型主要有:東行、西行、南行、北行和環(huán)形線路,而實(shí)際線路號(hào)并沒(méi)有區(qū)分方向,為維護(hù)數(shù)據(jù)的一致性和區(qū)別有方向的線路,在設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)時(shí)根據(jù)實(shí)際運(yùn)行方向給線路加上方向,比如101路公交線對(duì)應(yīng)101路(東行)和101路(西行)兩條不同線路或其它的方向(方向按實(shí)際情況確定),環(huán)形線路不考慮方向.線路主要是由公交站點(diǎn)組成,地理位置接近的同名站點(diǎn)考慮為同一站點(diǎn),對(duì)于地理位置不接近的站點(diǎn),對(duì)其中一個(gè)站點(diǎn)附加較出名的地理名稱(chēng)或建筑物名稱(chēng)形成別名來(lái)區(qū)別,比如:蘭州市公交網(wǎng)絡(luò)中,在黃河市場(chǎng)附近(較出名地理位置)有橋北站點(diǎn),而在距此很遠(yuǎn)的中山橋(較出名建筑物)也有橋北站點(diǎn),那么可將其中之一的站點(diǎn)名后附加較出名地理位置名稱(chēng)或建筑物名稱(chēng),如橋北(中山橋).1.2設(shè)置合理路徑或乘車(chē)路段根據(jù)公交網(wǎng)絡(luò)組成及分析,考慮如何區(qū)分東、西行或南、北行等有方向的線路,給線路內(nèi)部的站點(diǎn)附加線路內(nèi)站點(diǎn)序號(hào),比如:3路(東行)線路中的(起始)站點(diǎn)A、中間站點(diǎn)B、中間站點(diǎn)C、(終止)站點(diǎn)D依次標(biāo)以自然數(shù)1,2,3,4,那么3路(西行)線路中的站點(diǎn)順序?yàn)?起始)站點(diǎn)D、中間站點(diǎn)C中間站點(diǎn)B、(終止)站點(diǎn)A,線路內(nèi)部序號(hào)依次為1,2,3,4.那么在出行路徑選擇中就可以通過(guò)站點(diǎn)在線路內(nèi)部的序號(hào)來(lái)確定這是不是一條合理路徑(或者乘車(chē)路段),例如,路徑R1:站點(diǎn)A(序號(hào)為1)—3路(東行)—站點(diǎn)B(序號(hào)為2)為合理路徑,而路徑R2:站點(diǎn)A(序號(hào)為4)—3路(東行)—站點(diǎn)B(序號(hào)為2)就是不合理路徑(或者乘車(chē)路段),因?yàn)楦鶕?jù)公交站點(diǎn)在線路內(nèi)部的序號(hào)和一條合理路徑(或者乘車(chē)路段)模式“站點(diǎn)1—線路號(hào)—站點(diǎn)2”可知站點(diǎn)1的序號(hào)要低于站點(diǎn)2的序號(hào).綜上,借助大型數(shù)據(jù)庫(kù)SQLServer設(shè)計(jì)如下數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)線路、站點(diǎn)、站間距等數(shù)據(jù).表1(line_stop)存儲(chǔ)線路、站點(diǎn)、站點(diǎn)在線路內(nèi)部的序號(hào),表2(distance)存儲(chǔ)站點(diǎn)間距資料,它們的具體數(shù)據(jù)結(jié)構(gòu)如表1和表2所示.2通過(guò)構(gòu)造和無(wú)特別關(guān)聯(lián)線路集合找準(zhǔn)出行方案為了便于應(yīng)用于實(shí)際中的大規(guī)模公交網(wǎng)絡(luò),本文借助數(shù)據(jù)庫(kù)技術(shù)中實(shí)現(xiàn)關(guān)系代數(shù)運(yùn)算簡(jiǎn)潔、迅速的優(yōu)點(diǎn),采用Transact-SQL語(yǔ)言編程思路和數(shù)據(jù)庫(kù)中在服務(wù)器端運(yùn)行且可以提高運(yùn)算性能、效率的存儲(chǔ)過(guò)程技術(shù),設(shè)計(jì)了簡(jiǎn)潔、高效率的計(jì)算機(jī)算法.算法主要思路:將出行決策模型中的兩個(gè)目標(biāo)分層計(jì)算來(lái)實(shí)現(xiàn),即先利用Transact-SQL語(yǔ)言編寫(xiě)存儲(chǔ)過(guò)程實(shí)現(xiàn)關(guān)系代數(shù)中的有關(guān)運(yùn)算從而得出直達(dá)、1次換乘、2次換乘出行方案,并將直達(dá)出行選擇方案、1次換乘出行選擇方案和2次換乘出行決策方案依次存儲(chǔ)在數(shù)據(jù)庫(kù)表zhida_fangan_trip、transfer_one_time_trip和表transfer_two_time_trip中,然后編寫(xiě)帶參數(shù)的存儲(chǔ)過(guò)程依次求解最佳出行方案.表zhida_fangan_trip、transfer_one_time_trip中的數(shù)據(jù)結(jié)構(gòu)如表3,4所示,表transfer_two_time_trip的數(shù)據(jù)結(jié)構(gòu)類(lèi)似表4.算法實(shí)現(xiàn)的具體步驟如下:Step1創(chuàng)建帶出發(fā)站點(diǎn)和目的地站點(diǎn)參數(shù)的存儲(chǔ)過(guò)程;Step2從表line_stop中找出經(jīng)過(guò)起始出發(fā)站點(diǎn)的所有線路集合#line_set_1(數(shù)據(jù)庫(kù)中為臨時(shí)表),從表line_stop中找出經(jīng)過(guò)目的地站點(diǎn)的所有線路集合#line_set_2;Step3將集合#line_set_1和#line_set_2取交集得到集合#line_set_3;Step4判斷集合#line_set_3是否為空,即臨時(shí)表#line_set_3中是否有記錄,若不為空,則存在從起始出發(fā)站點(diǎn)直達(dá)目的地站點(diǎn)的出行方案,并將方案存入數(shù)據(jù)庫(kù)直達(dá)出行方案表zhida_fangan_trip中,轉(zhuǎn)step13.若為空,轉(zhuǎn)step5;Step5#line_set_3為空表示沒(méi)有直達(dá)出行線路存在.找出線路集合#line_set_1的所有站點(diǎn)的集合#transfer_stop_set_1,找出線路集合#line_set_2的所有站點(diǎn)的集合#transfer_stop_set_2;Step6將站點(diǎn)集合#transfer_stop_set_1和#transfer_stop_set_2取交集得集合#transfer_stop_set_3;Step7判斷集合#transfer_stop_set_3是否為空.如果不為空,則表示集合#transfer_stop_set_3是1次換乘站點(diǎn)集合,轉(zhuǎn)step8;如果為空,表示通過(guò)1次換乘不能到達(dá)目的地,轉(zhuǎn)step10;Step8找1次換乘出行方案:找出經(jīng)過(guò)1次換乘站點(diǎn)集合#transfer_stop_set_3的所有線路集合line_set_4(具體實(shí)現(xiàn)時(shí)為數(shù)據(jù)庫(kù)表,表中只有stop_name一個(gè)站點(diǎn)名稱(chēng)字段);Step9找出集合#line_set_1和集合line_set_4的交集line_set_5(具體實(shí)現(xiàn)時(shí)為數(shù)據(jù)庫(kù)表,表中只有l(wèi)ine_name一個(gè)線路名稱(chēng)字段)為第1次乘車(chē)的線路集合;找出集合line_set_4和#line_set_2的交集line_set_6(具體實(shí)現(xiàn)時(shí)為數(shù)據(jù)庫(kù)表,表中只有l(wèi)ine_name一個(gè)線路名稱(chēng)字段)為第1次換乘線路集合;按照“起始站點(diǎn)A—第1次乘車(chē)線路R1(集合)—第1次換乘站點(diǎn)B”模式及站點(diǎn)A和換乘站點(diǎn)B在線路R1中序號(hào)的大小判斷線路是否可行(例如3路(東行)線路可以,則3路(西行)線路不可以)來(lái)得到1次換乘方案中的前半程方案,后半程方案如此類(lèi)推,最后將可行1次換乘出行方案存入數(shù)據(jù)庫(kù)1次換乘出行方案表transfer_one_time_trip中.Step10找2次換乘出行方案:找出經(jīng)過(guò)站點(diǎn)集合#transfer_stop_set_1中任一站點(diǎn)的所有線路集合#transfer_line_1,找出經(jīng)過(guò)站點(diǎn)集合#transfer_stop_set_2中任一站點(diǎn)的所有線路集合#transfer_line_1;找出集合#transfer_line_1和#transfer_line_1的交集#transfer_line_one,即為第1次換乘線路集合;Step11如果集合#transfer_line_one為空,轉(zhuǎn)Step15,否則,轉(zhuǎn)Step12;Step12找出2次換乘方案中第1次換乘集合#transfer_line_one中的所有站點(diǎn)集合#temp_transfer_stop;找出集合#temp_transfer_stop和#transfer_stop_set_1的交集#transfer_stop_11,即為2次換乘出行方案中的第1次換乘站點(diǎn)集合;找出集合#temp_transfer_stop和#transfer_stop_set_2的交集#transfer_stop_21,即為2次換乘出行方案中的第2次換乘站點(diǎn)集合;找出經(jīng)過(guò)集合#transfer_stop_21的所有線路集合#line_set_12;找出集合#line_set_12與#line_set_2的交集#transfer_line_two,即為2次換乘出行方案的第2次換乘線路集合;找出經(jīng)過(guò)1次換乘站集合#transfer_stop_11的所有線路集合#line_set_10,找出集合#line_set_10和#line_set_1的交集得2次換乘出行方案中的第1次乘車(chē)線路集合#line_set_11,按照step9中判斷合理出行路徑(或路段)的方式找出出行方案存入數(shù)據(jù)庫(kù)2次換乘出行方案表transfer_two_time_trip中.Step13創(chuàng)建帶輸入、輸出參數(shù)的求每一出行方案的出行距離的存儲(chǔ)過(guò)程;Step14根據(jù)求得的出行距離找出最佳出行路徑,算法終止.Step15沒(méi)有2次換乘以?xún)?nèi)的公交出行方案,建議選擇其它交通方式出行,算法終止.以上步驟中的集合運(yùn)算在算法的計(jì)算機(jī)實(shí)現(xiàn)過(guò)程中均表示對(duì)應(yīng)數(shù)據(jù)庫(kù)中的表(table),表名前加有符號(hào)#的表示為數(shù)據(jù)庫(kù)中的臨時(shí)表,否則為數(shù)據(jù)庫(kù)中的永久表(或?qū)ο?,算法步驟中的集合運(yùn)算均只需一條SQL語(yǔ)句即可實(shí)現(xiàn)集合運(yùn)算,如Step2和Step3的具體實(shí)現(xiàn)語(yǔ)句如下:SELECTline_nameINTO#line_set_1FROMline_stopWHEREstop_name=@begin_stop_nameSELECTline_nameINTO#line_set_2FROMline_stopWHEREstop_name=@end_stop_nameSELECTline_nameINTO#line_set_3FROM#line_set_1WHEREline_nameIN(SELECTline_nameFROM#line_set_2)采用SQLServer中Transact-SQL語(yǔ)言來(lái)編寫(xiě)在服務(wù)器端運(yùn)行的存儲(chǔ)過(guò)程,存儲(chǔ)過(guò)程將要處理數(shù)據(jù)的程序移動(dòng)到離數(shù)據(jù)更近的地方,從而有力地保證了算法實(shí)現(xiàn)的計(jì)算機(jī)執(zhí)行效率.3最佳出行路徑創(chuàng)建在SQLServer中建立了公交網(wǎng)絡(luò)數(shù)據(jù)庫(kù),并在系統(tǒng)中建立了相應(yīng)的數(shù)據(jù)表,錄入了蘭州市24條公交線路數(shù)據(jù)和259個(gè)公交站點(diǎn)(如果按每條線路包含的公交站點(diǎn)計(jì)算,即有的站點(diǎn)有多條不同公交線路通過(guò),那么,則有866個(gè)站點(diǎn)),基于本文中的假設(shè):非環(huán)形線路都考慮雙向運(yùn)營(yíng),即或東行或西行或南行或北行中的兩個(gè)方向,那么數(shù)據(jù)庫(kù)系統(tǒng)中共有48條有方向的公交線路數(shù)據(jù)資料.經(jīng)在SQLServer查詢(xún)分析器工具中執(zhí)行查找出行換乘方案的帶任意出發(fā)站點(diǎn)、目的地站點(diǎn)參數(shù)的存儲(chǔ)過(guò)程,找到直達(dá)出行方案、1次換乘出行方案和2次換乘出行方案的執(zhí)行時(shí)間均不到1秒,執(zhí)行時(shí)間基本上是以毫秒級(jí)來(lái)度量,而且經(jīng)人工在蘭州市公共交通地圖(有詳細(xì)站點(diǎn)和線路)上檢驗(yàn)所得方案均是合理的最佳方案.算法程序運(yùn)行的軟、硬件環(huán)境:ACER臺(tái)式機(jī),操作系統(tǒng)為Windows2003Server,CPU為IntelPentium2.6GHz,內(nèi)存為256MB,數(shù)據(jù)庫(kù)服務(wù)器為SQLServer2000EnterpriseEdition.例如在SQLServer查詢(xún)分析器工具中輸入、執(zhí)行存儲(chǔ)過(guò)程:find_trip_strategy‘蘭州車(chē)站’,‘交通大學(xué)’.系統(tǒng)馬上輸出查詢(xún)到的方案如表5所示:因?yàn)槌绦驔](méi)有找到直達(dá)出行方案,所以輸出的是1次換乘出行方案,在找到1次換乘出行方案后,程序不再查找2次換乘出行方案,因?yàn)楸疚闹械哪繕?biāo)是以換乘次數(shù)最少為首要目標(biāo),即認(rèn)為出行換乘次數(shù)比出行距離占有不可替代的權(quán)重.然后利用創(chuàng)建的求出行方案旅行距離的存儲(chǔ)過(guò)程即可找