(精品論文)最優(yōu)公交線路查詢的設(shè)計(jì)與實(shí)現(xiàn)本科生畢業(yè)論文(設(shè)計(jì))

本科生畢業(yè)論文（設(shè)計(jì)）開題報(bào)告題 目: 最優(yōu)公交線路查詢的設(shè)計(jì)與實(shí)現(xiàn) 姓 名: 學(xué) 院: 理學(xué)院 專 業(yè): 信息與計(jì)算科學(xué) 班 級: 學(xué) 號: 指導(dǎo)教師: 職稱: 大學(xué)教務(wù)處制本課題的意義：隨著城市的發(fā)展和人民生活水平的提高，人們出行的次數(shù)和出行的路程都在增加，作為城市樞紐的公共交通承擔(dān)著越來越重的運(yùn)輸任務(wù)。同時，公交線路的條數(shù)和公交車數(shù)量也在迅速增多，公交的服務(wù)時間在延長，到站路程在擴(kuò)大，服務(wù)質(zhì)量在提高，給人民的日常生活帶來了很多便利。在油價(jià)上漲和能源短缺的今天，人們的出行將更多的依賴公共車。然而，隨著人們所到目的地范圍擴(kuò)大，出行往往需要轉(zhuǎn)乘多輛公交車才能到達(dá)目的地，如何在短時間、換乘次數(shù)最少、成本最低的情況到達(dá)目的地，是人們所關(guān)注的問題。因此，我們的課題運(yùn)用計(jì)算機(jī)及網(wǎng)絡(luò)技術(shù)，結(jié)果國內(nèi)外先進(jìn)的數(shù)學(xué)計(jì)算方法，設(shè)計(jì)一套能夠方便人們通過多種網(wǎng)絡(luò)查詢模式，查詢到出行時所需的最佳公交換乘方法，給人們出行節(jié)約更多的時間和金錢。國內(nèi)外研究概況：隨著運(yùn)籌學(xué)，圖論等學(xué)科的不斷發(fā)展，在1959年，荷蘭計(jì)算機(jī)科學(xué)家艾茲格迪科斯徹發(fā)現(xiàn)了Dijkstra算法，該算法在公交路線查詢中是一種比較常用、方便的算法，但它的復(fù)雜度為結(jié)點(diǎn)數(shù)平方的數(shù)量級。當(dāng)網(wǎng)絡(luò)模型中結(jié)點(diǎn)數(shù)和邊數(shù)較多的情況下，算法的計(jì)算量較大，時間花費(fèi)較多。因此，Dijkstra 算法在理論上是正確的，但在實(shí)際應(yīng)用中不盡人意。1968年人們開發(fā)出A*算法，該算法是一種啟發(fā)式搜索方法，它特別適用于公交查詢等統(tǒng)，它是利用已有的一些先驗(yàn)知識來對解空間進(jìn)行搜索。由于已經(jīng)有了問題的一些先驗(yàn)知識，因此A*算法往往比一些遍歷搜索方法在計(jì)算時間上要快得多，但它不能像Dijkstra算法一樣搜索到的一定是最短的路徑，只能是相對短的路徑。之后，在20世紀(jì)90年代初意大利學(xué)者M(jìn) Dorigo ，V Maniezzo ，A Colorni等通過模擬螞蟻搜索路徑的行為，發(fā)明出螞蟻算法。該算法可以帶記憶功能，選擇某路徑的次數(shù)越多，說明此路徑是比較優(yōu)的路徑，其信息素的值也越大，為以后選擇路徑提供必要的信息。系統(tǒng)使用的時間越長，為乘客提供的信息越全面，越準(zhǔn)確，系統(tǒng)也越智能化。應(yīng)用前景：基于網(wǎng)絡(luò)環(huán)境下的B/S公交換乘系統(tǒng)將是今后幾年內(nèi)城市公交建設(shè)發(fā)展和研究的方向，在該項(xiàng)查詢技術(shù)成熟并運(yùn)用的很短時間內(nèi)，亦可以在B/S公交換乘系統(tǒng)的基礎(chǔ)上設(shè)計(jì)出實(shí)時路況系統(tǒng)。為人們出行提供便利，對人們了解交通現(xiàn)狀和城市道路發(fā)展規(guī)模提供了必不可少的平臺。研究的內(nèi)容：1 調(diào)查出行者在出行時以哪些因素為首要考慮因素？2 了解并分析目前公交網(wǎng)絡(luò)的設(shè)計(jì)以何種理論為依托？3 思考如何才是公交換乘最短路概念？4 了解、并分析國內(nèi)外目前已有公交路線查詢系統(tǒng)的理論及設(shè)計(jì)方法。5 如何將集合，廣度和深度優(yōu)先搜索的思想應(yīng)用于B/S模式下公交換乘系統(tǒng)中去？6 結(jié)合傳統(tǒng)的公交查詢方法和國內(nèi)外先進(jìn)的公交路線算法理論，設(shè)計(jì)出一套適用于我國城市的最佳公交換乘路線查詢系統(tǒng)。研究的目標(biāo)：采用國內(nèi)外先進(jìn)的設(shè)計(jì)算法原理，結(jié)合JSP語言開發(fā)出基于B/S模式下的公交查詢系統(tǒng)。擬解決的關(guān)鍵問題：1、 如何收集齊全所有城市的公交線路信息？2、 根據(jù)實(shí)際調(diào)查和理論分析，歸納出公交換乘最短路概念。3、 分析、對比、總結(jié)出最少換乘路徑的最優(yōu)算法。4、 在進(jìn)行系統(tǒng)設(shè)計(jì)時，需對運(yùn)籌學(xué)、圖論、概率論、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、java語言等多門復(fù)雜學(xué)科進(jìn)行深入了解。5、 如何運(yùn)用MVC、連接池、ajax等先進(jìn)的程序設(shè)計(jì)技術(shù)來優(yōu)化系統(tǒng)查詢功能。研究方法、實(shí)驗(yàn)方案：本課題的研究方法主要綜合分析法，包括對各類文獻(xiàn)、書本的分析等。1、上網(wǎng)瀏覽法.通過瀏覽大量關(guān)于公交路線查詢的網(wǎng)絡(luò)資源的文章、開發(fā)文檔、B/S軟件實(shí)例2、分析比較法：對1中的同類軟件進(jìn)行分類和比較，指出同類軟件在建設(shè)上的優(yōu)缺點(diǎn)。3、研究開發(fā)法：最后，采用JSP語言開發(fā)系統(tǒng)一套。技術(shù)路線：學(xué)習(xí)傳統(tǒng)查詢理論和方法分析目前查詢系統(tǒng)的優(yōu)缺點(diǎn) 總結(jié) 歸納嘗試更高效、準(zhǔn)確的算法優(yōu)化算法軟件開發(fā)完善各種文檔撰寫論文可行性分析：1. 目前，國內(nèi)外已有公交查詢系統(tǒng)的雛形，但不完善和全面。2. 公交算法理論在國內(nèi)外有較完善的理論基礎(chǔ)。3. 通過多種調(diào)查方法的結(jié)果顯示，人們對在什么地點(diǎn)和時間等環(huán)節(jié)進(jìn)行公交換乘還不是很熟悉，需要一套較智能和便利的查詢系統(tǒng)來為他們提供所需的最佳換乘方案。特色或創(chuàng)新之處：1、 通過網(wǎng)絡(luò)終端（電腦，手機(jī),掌上電腦等），即可快速查詢到所查城市公交信息及出行換乘方案。2、目前國內(nèi)無完善和全面的公交換乘自動生成系統(tǒng)。3、本系統(tǒng)基于JAVA環(huán)境，系統(tǒng)使用越頻繁，查詢效率越高。研究計(jì)劃及預(yù)期進(jìn)展：2006年9月至2007年1月，做初步的調(diào)查，論證其可行性，確定研究詳細(xì)內(nèi)容，完成開題報(bào)告2007年1月15日至2007年2月28日，收集材料，研究算法，優(yōu)化算法2007年3月1日至2007年3月15日 系統(tǒng)設(shè)計(jì)研究制作，完成中期檢查報(bào)告2007年3月15日至2007年3月20日，整理資料分析材料。2007年3月20日至2007年3月30日，撰寫論文初稿。已具備的條件、尚缺少的條件和擬解決的途徑（包括利用教學(xué)實(shí)驗(yàn)中心、科研實(shí)驗(yàn)室、實(shí)習(xí)基地、校外其它企事業(yè)單位等條件的計(jì)劃與落實(shí)情況）已具備條件：1. 基礎(chǔ)文獻(xiàn)的收集工作已經(jīng)完成2. 對一些關(guān)于路徑搜索的算法有一定的研究3. 有關(guān)于軟件工程的思想4. 有開發(fā)軟件的能力尚缺少的條件：1. 各城市公交路線的數(shù)據(jù)2. 缺少一定的權(quán)威性著作，尤其是國外的文獻(xiàn)，還有待于收