佳公交線路實(shí)時(shí)查詢模型附算法

1、1最佳公交線路的實(shí)時(shí)查詢模型及算法摘要本文針對(duì)查詢者的不同需求，為公交查詢系統(tǒng)提供了最佳線路查詢的模型與算法。查詢者的需求從換乘次數(shù)少、時(shí)間少和費(fèi)用少三方面進(jìn)行考慮。故查詢算法從換乘次數(shù)（從實(shí)際出發(fā)，換乘不超過(guò)兩次）入手：對(duì)直通的任意兩站點(diǎn)，可設(shè)計(jì)出較簡(jiǎn)單的最佳直通線路查詢算法（直通算法）。故對(duì)需要查詢的兩站點(diǎn)，算法先由線路、站點(diǎn)的原始數(shù)據(jù)判斷此兩站點(diǎn)是否直通，若是，便可通過(guò)直通算法進(jìn)行查詢。不論是否存在直通線路，算法都考慮對(duì)換乘的情形

2、進(jìn)行查詢?？紤]到城市公交系統(tǒng)中的站點(diǎn)基數(shù)較大，可行的換乘方案數(shù)也將較大，故查詢算法根據(jù)所有可行的一、二換乘點(diǎn)必與起、止站點(diǎn)直通的原則，對(duì)可能成為給定兩站點(diǎn)的換乘點(diǎn)的站點(diǎn)進(jìn)行了篩選，得到相關(guān)站點(diǎn)集，較大的縮小了查詢的范圍。得到相關(guān)站點(diǎn)集后，建立了反映站點(diǎn)集中任意兩站點(diǎn)直通關(guān)系的連通矩陣，并通過(guò)矩陣乘法，較快地得出了所有可行的一次、二次換乘點(diǎn)。考慮到所有可行的換乘點(diǎn)可能較多，特別是二次換乘的情形，故查詢算法采用分支定界法以較高效率對(duì)最佳方案

3、進(jìn)行了最后的篩選。在考慮地鐵的公交系統(tǒng)時(shí)，本文從實(shí)際出發(fā)，對(duì)模型進(jìn)行了一定的修改。同時(shí)，本文考慮了引入站點(diǎn)之間的步行時(shí)間的情況，提出了線路選擇的模型。由于篩選算法、矩陣乘法和分支定界法的高效性，整個(gè)查詢算法具有很高的效率，并能在換乘次數(shù)不超過(guò)兩次的條件下，求得全局最優(yōu)解，得出滿足查詢者不同需求的所有最佳方案。并且，從系統(tǒng)設(shè)計(jì)的角度出發(fā)，整個(gè)系統(tǒng)需要預(yù)存的數(shù)據(jù)量很小，系統(tǒng)的實(shí)用性很強(qiáng)。對(duì)給定的六對(duì)站點(diǎn)，采用本算法進(jìn)行查詢，在1.7GHZ的

4、CPU環(huán)境下，平均運(yùn)行時(shí)間為：1.27秒，最長(zhǎng)運(yùn)行時(shí)間為7.43秒，驗(yàn)證了算法的實(shí)時(shí)性。同時(shí)，對(duì)每一對(duì)站點(diǎn)，得到了滿足不同查詢需求的所有最佳線路方案，驗(yàn)證了模型與算法的精確性。關(guān)鍵詞：最佳線路、實(shí)時(shí)、篩選算法、分支定界3站點(diǎn)構(gòu)成的連通矩陣進(jìn)行分析，可以得出所有可行的換乘方案。可行的換乘方案數(shù)目也可能很多，特別是對(duì)城市中心地帶。故在確定最佳方案時(shí)，應(yīng)考慮采用較高效的對(duì)比算法。鑒于第一個(gè)換乘站點(diǎn)和第二個(gè)換乘站點(diǎn)的確定具有先后順序，兩者的層次

5、分明，故可考慮用分支定界算法。對(duì)于公汽地鐵混合公交系統(tǒng)，地鐵票價(jià)與站點(diǎn)數(shù)無(wú)關(guān)、地鐵間的換乘和同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間的換乘均屬免費(fèi)、地鐵線的引入增強(qiáng)了整個(gè)公交網(wǎng)絡(luò)的連通性、地鐵相對(duì)公汽更便捷且無(wú)阻塞，這些因素在會(huì)對(duì)兩站點(diǎn)間的連通關(guān)系及換乘點(diǎn)的選擇產(chǎn)生影響，需要綜合考慮。對(duì)于考慮了步行時(shí)間的最佳線路選擇問(wèn)題，由于存在在某站下車步行到另一站上車的情況，會(huì)對(duì)整個(gè)公交網(wǎng)絡(luò)的連通性產(chǎn)生較大影響，具有一定的復(fù)雜性。而步行時(shí)間無(wú)具體數(shù)據(jù)，故

6、只給出一般模型和求解思路。三、三、變量說(shuō)明：已知的520條公汽線路編號(hào))52021(??iLi：交通網(wǎng)絡(luò)中各個(gè)公汽站點(diǎn)(123957)isi??：經(jīng)過(guò)站點(diǎn)的線路集)395721(??iSiis：經(jīng)過(guò)站點(diǎn)的線路數(shù)量(包括上下行，算兩次))395721(??iNiis：線路屬性向量，記錄該向量為來(lái)回、上下行、環(huán)行。)52021(??iLSi：分別為從站點(diǎn)到站點(diǎn)的直通、一次換乘、二次換乘票價(jià)()(012)kCijk?sisj：分別為從站點(diǎn)到站

7、點(diǎn)的直通、一次換乘、二次換乘時(shí)間()(012)ktijk?sisj：起始站點(diǎn)，：終止站點(diǎn)0sds四、四、基本假設(shè)1.換乘次數(shù)不超過(guò)兩次。2.不考慮交通事故等意外情況。3.不考慮車輛內(nèi)部的擁擠情況及交通阻塞。4.換乘時(shí)間及相鄰兩站的行駛時(shí)間都取為平均值。5.若兩站點(diǎn)連通且直通線路上的中間站點(diǎn)數(shù)不超過(guò)3個(gè)，則不考慮換乘。五、五、模型建立先對(duì)數(shù)據(jù)進(jìn)行處理，縮小搜索范圍；然后設(shè)計(jì)快速算法找出任意兩個(gè)站點(diǎn)經(jīng)過(guò)直通、換乘一次及換乘兩次連通的所有可行

8、線路；最后根據(jù)查詢者在換乘次數(shù)、時(shí)間和費(fèi)用上的不同需求從可行線路中篩選出相應(yīng)的最佳線路。5.1公汽最佳線路選擇模型公汽最佳線路選擇模型5.1.1建模前的準(zhǔn)備建模前的準(zhǔn)備名詞解釋：名詞解釋：1.直通：站點(diǎn)i到站點(diǎn)j不需要換乘，則稱站點(diǎn)i直通到站點(diǎn)j。2.連通矩陣A：由n個(gè)站點(diǎn)構(gòu)成的的0、1方陣。當(dāng)時(shí)，=1表示站點(diǎn)nn?ij?ijai聯(lián)通到站點(diǎn)j；反之，=0。當(dāng)時(shí)，規(guī)定=0。ijaij?ija3.單一站點(diǎn)：站點(diǎn)i只在一條線路上，只考慮來(lái)回線