佳公交線路實時查詢模型附算法

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

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

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

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

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

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

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

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