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

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

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

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