公交線路管理系統(tǒng)換乘算法設(shè)計

1、公交線路管理系統(tǒng)換乘算法設(shè)計摘要：城市公交線路管理系統(tǒng)是城市道路交通的重要組成部分，主要涉及公交站點(diǎn)管理、線路管理、路線查詢和信息發(fā)布等功能。公交車線路管理系統(tǒng)是典型的管理信息系統(tǒng)（MIS），其重點(diǎn)是設(shè)計有效的查詢算法，幫助用戶快速、方便地選擇出行路線。討論了一種基于集合理論的線路查詢算法，并分析了它的特點(diǎn)。關(guān)鍵詞：線路查詢；換乘算法；算法優(yōu)化0引言許多國家都十分重視公交線路管理的研究和應(yīng)用，其中一個重要的目的就是提供及時準(zhǔn)確的信息和服務(wù)。與歐美國家相比，我國的公共交通智能化水平還比較低。在大中城市中，一般有數(shù)千站點(diǎn)、數(shù)百公交線路。出行前，當(dāng)對乘車路線不確定時，如果事先訪問公交線路查詢系統(tǒng)，就

2、可以快速地得到有關(guān)信息，從而方便用戶出行。人們對公交線路查詢算法作了大量研究，提出了最短距離算法、最短路徑矩陣、最小換乘次數(shù)算法、最少時間算法、最大費(fèi)用算法等。這些算法都有自己的優(yōu)點(diǎn)，但有些實(shí)現(xiàn)起來過于復(fù)雜。對此，筆者通過建立站點(diǎn)、線路集合的方法，來尋找簡單、實(shí)用而快速的換乘算法，為公交線路查詢算法提供一種新的思路和方法。1系統(tǒng)分析1.1需求分析首先，普通用戶可以注冊進(jìn)入系統(tǒng)，而管理員直接用口令進(jìn)入后臺系統(tǒng)。其次，當(dāng)普通用戶登錄到系統(tǒng)以后，可以查看公交信息、實(shí)現(xiàn)多種查詢功能，也可以進(jìn)入留言板留言發(fā)表意見。而管理員除了有用戶所具有的權(quán)利外，還可以對線路信息、站點(diǎn)信息、用戶信息和用戶留言等進(jìn)行增刪

3、改操作。22系統(tǒng)相關(guān)用例圖用戶用例圖如圖1所示，管理員用例圖如圖2所示。站點(diǎn)查詢主要是查詢站點(diǎn)周圍的信息，如交通、文化、商業(yè)、旅游、企業(yè)等情況。線路查詢主要是查詢一條線路的上行線、下行線的各個站點(diǎn)的情況。換乘查詢就是根據(jù)指定的起始站點(diǎn)和終止站點(diǎn)查詢出出行路線。這也是系統(tǒng)設(shè)計的重點(diǎn)。其中線路管理中包括線路設(shè)置（上行線、下行線）、線路修改等。2系統(tǒng)總體設(shè)計2.1系統(tǒng)總體構(gòu)架系統(tǒng)以B/S模式開發(fā)，根據(jù)功能不同來分，系統(tǒng)總體可以分為3個模塊：前臺查詢模塊、管理員登錄模塊、后臺管理模塊。前臺查詢模塊是對所有用戶公開的，不用登錄，不設(shè)權(quán)限和級別，方便所有用戶使用和查詢。管理員登錄模塊判斷用戶是否合法，是否

4、有權(quán)限進(jìn)入后臺管理，保護(hù)后臺管理頁面。管理員可以添加、刪除和修改相關(guān)信息。公交線路管理系統(tǒng)的軟件結(jié)構(gòu)如圖3所示。2.2主要數(shù)據(jù)庫設(shè)計（1）用戶信息表。這個數(shù)據(jù)表用來存儲普通用戶和管理員用戶的資料，包括用戶名、密碼等信息。（2）線路信息。這個數(shù)據(jù)表用來存儲線路的基本信息，包括有線路代碼、名稱、起始站點(diǎn)、終點(diǎn)站、站點(diǎn)數(shù)目、線路長度等。（3）站點(diǎn)信息。這個數(shù)據(jù)表用來存儲站點(diǎn)信息，包括有站點(diǎn)代碼、站點(diǎn)名稱、站點(diǎn)周圍交通、文化等信息。（4）線路與站點(diǎn)關(guān)系。這個數(shù)據(jù)表用來存儲線路與站點(diǎn)關(guān)系的具體信息，包括線路、站點(diǎn)代碼、站點(diǎn)次序。圖3系統(tǒng)軟件結(jié)構(gòu)3換乘查詢算法設(shè)計3.1一次換乘的設(shè)計思路在這里只考慮直達(dá)車

5、和一次中轉(zhuǎn)。設(shè)bsld1為起始站點(diǎn)代碼，bsld2為終止站點(diǎn)代碼。設(shè)經(jīng)過起始站點(diǎn)的線路集合為A,A=A1,A2,Am，每一個Ai為經(jīng)過起始站點(diǎn)的一條線路。設(shè)經(jīng)過終止站點(diǎn)的線路集合為B,B=B1,B2,Bn，每一個Bi為經(jīng)過終止站點(diǎn)的一條線路。（1）搜索是否有直達(dá)車。在這一步的實(shí)現(xiàn)屮，貝需燮震索紐過起始站點(diǎn)的所有線路和經(jīng)過終止站點(diǎn)的所有線路，找出那些相同的線路，即為直達(dá)線路。（2）若沒有直達(dá)車，則搜索一次換乘是否可達(dá)。根據(jù)兩個站點(diǎn)名獲取兩個站點(diǎn)各自的bsld，然后搜尋通過兩個站點(diǎn)的線路集合A和B。再一一計算它們之間的線路交集。而交集就是我們所需要的換乘站點(diǎn)，這樣可得到換乘站（可能有多個或0個）。

6、女口，判斷Ai和Bj是否有交叉站點(diǎn)。如果有，則這就是換乘的中轉(zhuǎn)站點(diǎn)；如果沒有，則無法通過Ai和Bj線路到達(dá)目的地。如果線路間有多個交叉站點(diǎn)，則只考慮第1個交叉站點(diǎn)。3.2設(shè)計算法流程圖輸入是起始站點(diǎn)和終止站點(diǎn)，經(jīng)過系統(tǒng)處理，可得到所查詢出的出行線路。如果有直達(dá)線路，直接給出線路信息；如果沒有直達(dá)車，則給出中轉(zhuǎn)一次的線路信息，如圖4所示。4結(jié)束語本文討論了公交線路管理系統(tǒng)的軟件結(jié)構(gòu)和查詢算法。其重點(diǎn)是設(shè)計有效的查詢算法，以幫助用戶快速、方便地選擇出行路線。所設(shè)計的查詢算法具有簡單、實(shí)用的特點(diǎn)，適合大中城市的公交線路查詢，如果結(jié)合站點(diǎn)間距離計算，利用蟻群算法可進(jìn)一步優(yōu)化算法設(shè)計。參考文獻(xiàn)：1于小平

7、，楊國東城市公交查詢系統(tǒng)的設(shè)計與實(shí)現(xiàn)J.吉林大學(xué)學(xué)報，2005(6).2華澤、張浩.公交信息服務(wù)系統(tǒng)的設(shè)計與實(shí)現(xiàn)J.計算機(jī)與數(shù)字工程，2007(12).3馮林，孫宇哲.基于層次空間推理的公交最優(yōu)乘車方案J.計算機(jī)工程，2005(21).4吳其慶SP編程思想與實(shí)踐M.北京：冶金工業(yè)出版社，2003.5王祖詳.公交最短路算法和公交路徑集生成技術(shù)J.系統(tǒng)工程，1993(4).DesignonPublicTrafficManagementStstemTransferAlgorithmAbstract:Publictrafficmanagementinformationsystemisanimportantpartofcitypublictrafficsystem,mailyinvoIvesbusstationmanagement,routemanagement,routequeryandinformationdissemination.Publictrafficmanagementsystemisatypicalmanagementinformationsystem(MIS).Thefocalpointisdesigningeffectiverouteinquiryalgorithmtohelpuserselectbusroutequickly.Thispa