最優(yōu)路徑算法在票務(wù)清分系統(tǒng)中的研究與應(yīng)用.pdf

1、軌道交通因其造價高、投資大、工期長等因素的影響，整個城市軌道交通路網(wǎng)的建設(shè)過程中會涉及到不同的投資方、建設(shè)方和運營方。隨著路網(wǎng)規(guī)模的不斷擴(kuò)大和線路交叉，形成了跨越不同運營線路的乘車情況，為了客觀、公平、公正地把交易款劃分給被乘運線路，產(chǎn)生了軌道交通清分系統(tǒng)。建立清分系統(tǒng)需要解決異線站點之間的換乘路徑問題，即無向圖中求解給定頂點對之間K條最優(yōu)路徑問題。
　　 在研究了求解K優(yōu)路徑問題的基本理論和2nd最優(yōu)路徑搜索算法的基礎(chǔ)上，借助

2、于“背離”路徑的概念，提出了一種新的Kth最優(yōu)路徑搜索算法。通過K-1次2nd最短路徑搜索算法的迭代，求解出網(wǎng)絡(luò)中任意兩個給定節(jié)點之間的Kth最優(yōu)路徑，由于2nd最短路徑搜索算法在計算上的簡單性，本算法同樣具有簡潔、快速的特點。
　　 使用斐波那契堆優(yōu)化Dijkstra算法中的最小優(yōu)先隊列，使Dijkstra算法的性能達(dá)到最優(yōu)。針對算法在搜索過程中產(chǎn)生的環(huán)路，在分析了刪除邊去環(huán)算法的基礎(chǔ)上，提出用2nd算法的思想去環(huán)，在產(chǎn)生環(huán)路

3、節(jié)點的背離路徑中搜索次優(yōu)路徑作為新的背離路徑，解決了算法的瓶頸問題，使整體路徑求解算法的效率有了顯著的提高。
　　 在此基礎(chǔ)上，對算法所涉及到的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了調(diào)整，用鄰接多重表來存儲路網(wǎng)結(jié)構(gòu)圖，用其MARK域標(biāo)記節(jié)點所在的路徑以判斷是否存在環(huán)路。用固定長度的隊列存儲最終形成的路徑，使不符合要求的路徑盡早的排除，進(jìn)一步提高算法的效率。該算法的時間復(fù)雜度為O(VlgV+E+K*m*t)。
　　 最后，結(jié)合上海軌道交通路網(wǎng)模型