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

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

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

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

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

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

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

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

8、線路；最后根據(jù)查詢者在換乘次數(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個站點(diǎn)構(gòu)成的的0、1方陣。當(dāng)時，=1表示站點(diǎn)nn?ij?ijai聯(lián)通到站點(diǎn)j；反之，=0。當(dāng)時，規(guī)定=0。ijaij?ija3.單一站點(diǎn)：站點(diǎn)i只在一條線路上，只考慮來回線