摘要：近年來，隨著長株潭城市群的經(jīng)濟(jì)快速發(fā)展，人口數(shù)量也急劇增加，給人們的出行帶來了極大的問題。該文從用戶的角度出發(fā)設(shè)計了一個適用于用戶的長株潭公交一體化查詢系統(tǒng)。在對用戶的需求進(jìn)行了分析以后，對系統(tǒng)開發(fā)環(huán)境、關(guān)鍵技術(shù)、總體要求分析、系統(tǒng)流程模型、數(shù)據(jù)流圖、總體設(shè)計等方面進(jìn)行了深入的分析。該文采用Dijkstra算法為基礎(chǔ)理論進(jìn)行算法的優(yōu)化，從而使用戶在以最少時間、最少花費(fèi)、最少換乘等條件下進(jìn)行公交的換乘工作。

關(guān)鍵詞：長株潭；公共交通；公交查詢；一體化；換乘查詢

中圖分類號：TP315 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）02-0292-07

近年來，由于長株潭經(jīng)濟(jì)的快速發(fā)展，城市人口相比于以前也增加了很多。為了能方便人們的出行，所以需要增加城市中的道路數(shù)量。隨之帶來了一個城市公交路線的調(diào)整的問題，但同時這也給人們的出行了帶來不便。正是由于這個原因，急需要一個公交查詢系統(tǒng)來方便人們用來查詢長株潭最新的公交車信息和道路狀況，人們就可以不用因?yàn)楣痪€路的變換而頭疼了。城市公交的主要職責(zé)就是為人民的出行來服務(wù)的，在城市生活中占據(jù)了極其重要的作用。

城市公交對城市的經(jīng)濟(jì)發(fā)展和居民生活具有直接影響，對城市經(jīng)濟(jì)的發(fā)展具有全局性、先導(dǎo)性的影響。因?yàn)槌鞘泄痪哂蟹奖?、快捷、容量大等?yōu)點(diǎn)，所以成為現(xiàn)代城市交通的主體。但現(xiàn)在的問題是隨著公交系統(tǒng)的日益龐大，公交信息也在經(jīng)常發(fā)生變化，人們對于公交信息就不能及時、準(zhǔn)確的獲得，這樣必然會給廣大市民的出行帶來不便。因此，一個方便、快捷的公交信息查詢方式，不僅能夠使三市間的交通更方便，也能通過三市連接區(qū)的公共交通體系，實(shí)現(xiàn)三市人、物、資金乃至信息的充分流動。而且更能體現(xiàn)出一個城市的智能公交系統(tǒng)的水平，更顯示出城市的數(shù)字化、信息化水平。

1 系統(tǒng)需求分析

本系統(tǒng)集JSP技術(shù)和JavaBean技術(shù)的有效結(jié)合，成功設(shè)計并實(shí)現(xiàn)了一個公交查詢系統(tǒng)，解決了公交查詢實(shí)現(xiàn)中遇到的數(shù)據(jù)庫連接、模糊查詢、分頁技術(shù)等相關(guān)技術(shù)問題；該系統(tǒng)完備的功能模塊處理，能滿足用戶的查詢，發(fā)布留言、查詢與瀏覽公交信息等諸多需求，使網(wǎng)絡(luò)公交查詢更加便捷。該系統(tǒng)基于JSP和JavaBean技術(shù)的實(shí)踐，對其它網(wǎng)絡(luò)公交查詢的開發(fā)具有一定的理論意義和實(shí)際應(yīng)用價值。

1）本系統(tǒng)采用B/S體系結(jié)構(gòu)分別為不同身份的用戶進(jìn)行服務(wù)。為公交管理人員提供的服務(wù)主要包括：添加、修改、刪除、檢查結(jié)果記錄管理及查詢；為普通用戶提供的服務(wù)主要包括：各種不同的查詢；為系統(tǒng)管理員提供的服務(wù)主要包括：用戶帳戶管理及對系統(tǒng)配置的功能。

2）本系統(tǒng)是以JSP語言為前臺的應(yīng)用程序進(jìn)行開發(fā)，后臺使用Oracle數(shù)據(jù)庫。系統(tǒng)采用JSP技術(shù)來開發(fā)，采用B/S模式來實(shí)現(xiàn)瀏覽器端和服務(wù)器端的訪問，系統(tǒng)所使用的技術(shù)有足夠的可行性和明顯的針對性。

3）本系統(tǒng)采用結(jié)構(gòu)化設(shè)計的方法來實(shí)現(xiàn)系統(tǒng)總體功能。能夠極好的提高系統(tǒng)的各項(xiàng)指標(biāo)。結(jié)構(gòu)化設(shè)計的主要方法是通過將整個系統(tǒng)合理的劃分成為幾個功能相對獨(dú)立的模塊，然后對模塊之間和模塊內(nèi)部的聯(lián)系以及和數(shù)據(jù)庫的聯(lián)系進(jìn)行正確的處理，定義各個模塊的內(nèi)部結(jié)構(gòu)，進(jìn)而達(dá)到實(shí)現(xiàn)整個系統(tǒng)的功能的目的。

通過對本系統(tǒng)主要功能的分析，得出本系統(tǒng)的主要設(shè)計結(jié)果。對于面向用戶的前臺模塊的主要設(shè)計分為：線路查詢、站點(diǎn)查詢、公交換乘模塊、留言板模塊。具體功能如表1所示。

表1 前臺模塊的功能設(shè)計

對于面向管理員的后臺模塊，主要需要實(shí)現(xiàn)的是一些管理員所需要的工作，具體功能如表2所示。

表2 后臺模塊

2 基于公交路徑最優(yōu)的查詢算法

2.1 Dijkstra算法

二十世紀(jì)五十年代后期，迪杰斯特拉（Dijkstra）提出了一個算法專門用來解決最短路徑問題，并以自己名字命名此算法。

Dijkstra算法的具體過程描述如下：

1）在本文中用weight來表示帶權(quán)有向圖，weight是一個二維數(shù)組。行和列分別表示這個帶權(quán)有向圖中的節(jié)點(diǎn)。也就是說weight[i][j]表示弧上的權(quán)值。但是如果這個弧不存在，也就是說不存在直接從vi到vj的路徑，則將weight[i][j]設(shè)置為∞（在實(shí)際的計算機(jī)編程中可用一個比較大的值來表示最大值）。為了將已經(jīng)找到從v到某些節(jié)點(diǎn)的最短路徑的節(jié)點(diǎn)記錄下來，使用了一個集合S表示，這個集合的初始狀態(tài)為空集。在這個基礎(chǔ)上，我們可以將這個帶權(quán)有向圖中的除節(jié)點(diǎn)v以外的其他節(jié)點(diǎn)到節(jié)點(diǎn)v的初始長度設(shè)置為L[i]=weight[locate Vex（G，v）][i]vi∈V，設(shè)置循環(huán)次數(shù)為n；

2）設(shè)置最短路徑的終點(diǎn)為節(jié)點(diǎn)vj，那么vj的取值就是所有能到達(dá)此節(jié)點(diǎn)的路徑的最小值，我們也就求出了所需要的最短路徑了。由于j滿足集合S的條件，所以令S=S∪{j}；

3）根據(jù)上面的結(jié)果，可以修改從初始點(diǎn)到任意V-S這個集合中的最短路徑的長度。也就是說如果根據(jù)上面求出的最短路徑使得V-S中的某個點(diǎn)的路徑變短了則進(jìn)行修改，否則不需要修改L[j]的值。

4）將循環(huán)次數(shù)減1，判斷是否為0。如果為0則算法結(jié)束，否則跳轉(zhuǎn)到2）。由上面的算法可以看出，Dijkstra算法可以求出從起始點(diǎn)到目標(biāo)點(diǎn)的最短路徑，但同時也會求出從始點(diǎn)到其他任意節(jié)點(diǎn)的最短路徑。

由于Dijkstra算法在實(shí)際的操作過程中具有穩(wěn)定性、能適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，此算法在很多需要求出最短距離的問題中得到應(yīng)用。雖然Dijkstra算法具有以上這些優(yōu)點(diǎn)，但公交信息查詢網(wǎng)絡(luò)并不像其他的一般的線路查詢算法，它具有它們所不曾有的特性，這也直接導(dǎo)致Dijkstra算法不能直接用來解決公交信息查詢網(wǎng)絡(luò)中的線路查詢問題。如果采用該算法，缺點(diǎn)主要表現(xiàn)在：抽象存儲圖結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)復(fù)雜；系統(tǒng)反應(yīng)時間較長；冗余的節(jié)點(diǎn)較多。

2.2 查詢算法的改進(jìn)

本文的主要理論依據(jù)是“最優(yōu)路徑的子路徑都是最優(yōu)路徑”，這個理論也就意味著如果一個比較長的路徑是最優(yōu)路徑的話，那么這個路徑上的所有子路徑也是最優(yōu)的，反過來也是可以的。該文先求出換乘次數(shù)比較少的最優(yōu)路徑，然后利用這些最優(yōu)路徑求取換乘次數(shù)比較多的最優(yōu)路徑。并利用關(guān)系數(shù)據(jù)庫技術(shù)進(jìn)行最優(yōu)路徑集合的生成和優(yōu)化，從而進(jìn)行多目標(biāo)路徑搜索。算法基本思路如下：假設(shè)最大換乘次數(shù)為k，定義最優(yōu)路徑表，即STR0（直達(dá)路徑表），STR1（1次換乘路徑表），[…]，STRk（k次換乘路徑表）。

為了更清楚的表述本系統(tǒng)的問題，需要將在查詢過程中所用到的數(shù)據(jù)表的定義列出來。本系統(tǒng)定義了站點(diǎn)表（station）、線路站點(diǎn)關(guān)系表（line）、車次表（bus）。

本文利用關(guān)系數(shù)據(jù)庫技術(shù)本身的特點(diǎn)，也就是如果用表line和表station直接連接即可得到表STR0，然后再用表STR0進(jìn)行自連接即可得到表STR1，接著用表STR0和表STR1相連即可得到表STR2，[…]，同理用表STR0和表STR（k-1）連接即可得到表STRk。

為了得到最優(yōu)路徑表，需要將其中的非最優(yōu)路徑的換乘路徑表進(jìn)行刪除，然后進(jìn)行重新命名即表STRB0，表STRB1，[…]，表STRBk。根據(jù)表之間的關(guān)系可以明顯看出如果兩個表具有相同的換乘次數(shù)，那么它們的優(yōu)化路徑表的表結(jié)構(gòu)也會相同。

在查詢算法的最后，將所有優(yōu)化路徑表生成STRBEST（最優(yōu)路徑表）。然后就可以將STRBEST用于公交線路最優(yōu)路徑的查詢，具體表結(jié)構(gòu)如表4所示。

表4 STRBEST結(jié)構(gòu)

由于對一個路徑是否是最優(yōu)的評價標(biāo)準(zhǔn)是換乘次數(shù)最少或是花費(fèi)最少，所以如果將最少換乘算法作為標(biāo)準(zhǔn)的話，本算法可以成為最少換乘算法。如果想要花費(fèi)最少，則本算法可以變成最少花費(fèi)算法。

3 車次信息的設(shè)計與實(shí)現(xiàn)

查詢車次的流程圖如圖1所示。

4 結(jié)束語

公交路線查詢系統(tǒng)實(shí)現(xiàn)了站點(diǎn)查詢和線路查詢功能，解決了站點(diǎn)查詢和線路查詢的問題。能夠幫助出行人員最快時間內(nèi)查詢到想要的準(zhǔn)確線路信息和站點(diǎn)信息。系統(tǒng)還在普通查詢的基礎(chǔ)上實(shí)現(xiàn)了模糊查詢功能。在實(shí)現(xiàn)了以上功能的情況下系統(tǒng)還創(chuàng)新性的實(shí)現(xiàn)了換乘功能，能夠在沒有直達(dá)線路的情況下為用戶提供最短路徑和快速、經(jīng)濟(jì)有效地轉(zhuǎn)乘線路。