畢業(yè)設(shè)計(jì)-公交線路查詢算法研究與實(shí)現(xiàn)

1、<p><b>　　摘 要</b></p><p>　　隨著中國經(jīng)濟(jì)的發(fā)展與社會(huì)信息化水平的推進(jìn)，以計(jì)算機(jī)技術(shù)為代表的信息技術(shù)的應(yīng)用已經(jīng)深入到各行各業(yè)中了。公交作為國家的經(jīng)濟(jì)大動(dòng)脈是城市的重要組成部分，在國家經(jīng)濟(jì)和人民生活中發(fā)揮著重要作用并與人們的生活息息相關(guān)。</p><p>　　以西安市為例，全市現(xiàn)有線路200余條，站點(diǎn)幾千個(gè)，覆蓋了西安市的絕大部分區(qū)

2、域，公交已成為市民最重要的出行方式。在關(guān)于公交的眾多問題當(dāng)中，公交換乘是人們最關(guān)心的問題。</p><p>　　每一個(gè)市民所熟悉的公交線路是有限的，當(dāng)去一個(gè)不熟悉的地方，如何乘坐公交車前往是市民常常遇到的問題，因此我們需要構(gòu)建一個(gè)城市公交換乘系統(tǒng)，當(dāng)市民輸入出發(fā)站點(diǎn)與目的站點(diǎn)后，該系統(tǒng)能夠根據(jù)一定的規(guī)則，例如，換乘次數(shù)最少，路程最短，票價(jià)最低等，給出一些乘車的方案，市民按照乘車方案的文字描述或電子地圖(GIS)的

3、直觀顯示，可以準(zhǔn)確快捷的從出發(fā)點(diǎn)到目的地。</p><p>　　本文首先分析了圖論及相關(guān)的背景知識(shí)，這其中包含了對(duì)公交網(wǎng)絡(luò)進(jìn)行數(shù)學(xué)建模及對(duì)其求解平均換乘次數(shù)等。在此基礎(chǔ)上針對(duì)市民乘車的實(shí)際問題提出了多種不同的換乘算法，包括改進(jìn)的Dijkstra算法，利用數(shù)據(jù)庫在集合運(yùn)算方面的優(yōu)秀性能而提出的擴(kuò)展集合算法(廣度優(yōu)先搜索算法)及其改進(jìn)，用鄰接矩陣構(gòu)造換乘矩陣實(shí)現(xiàn)的換乘算法；人工智能方面的算法(啟發(fā)式搜索算法)—A*算

4、法在換乘方面的應(yīng)用及其改進(jìn)算法—A*！算法，基于螞蟻算法實(shí)現(xiàn)的公交換乘算法，基于Web GIS的算法。</p><p>　　最后，在分析完上述算法并比較其優(yōu)劣勢(shì)后，在Microsoft Visual C++編程環(huán)境下實(shí)現(xiàn)了一種算法并對(duì)其進(jìn)行分析與測(cè)試。各種測(cè)試表明，作者所開發(fā)的公交線路查詢系統(tǒng)完全符合理論假設(shè)并有一定實(shí)用價(jià)值。</p><p>　　關(guān) 鍵 詞：公交換乘 數(shù)學(xué)建模 D

5、ijkstra算法 擴(kuò)展集合算法 換乘矩陣算法 A*算法 A*！算法 螞蟻算法 Web GIS</p><p><b>　　ABSTRACT</b></p><p>　　With the development of china’s economic and the improvement of social information l

6、evel, the application of information technology including computer technology have been deeply rooted in every kinds of business. Bus, as the big artery of national economic, is one of the most important parts of a city.

7、 It exerts a great important function in national economic and individual’s life and has a strong relation with people’s activity.</p><p>　　Take XI’AN as an example, there are more than 200 bus lines and tho

8、usands of sites there. They cover almost every region of XI’AN and become the most important travel method. Bus transfer is the most concerned problem in all these problems.</p><p>　　The bus-lines which ever

9、y citizen are familiar with are limited. When we come to a place that we never come to before, how to get there with bus is the most frequent problem. So we need to build a city bus transfer system. When the users input

10、 the start site and the destination site, according to some rules, for example, the least transfer, the shortest path, and the lowest price, etc, the system can give us some suggestions on bus transfer, we can get to our

11、 destinations in the light of these </p><p>　　In this essay, the author first introduced some knowledge about graph theory and some other backgrounds, including building up a math model about bus network, re

12、solving average transfer times based on this, etc. Based on this model, the author propose lots of different transfer algorithms, including Dijkstra algorithm and its improvement; expanding set algorithm (breath first se

13、arch about graph) and its improvement which depending on the database’s excellent performance on set mathematic operati</p><p>　　At last, after analysised the algorithms mentioned above and compared the supe

14、riorities and inferiors of these algorithms, the author implement one of these algorithms in the visual C++ environment, then do some analysis and tests. The tests manifest the bus </p><p>　　transfer system

15、the author developed fits the theories very well and has some practical values. </p><p>　　Keywords: bus transfer math module Dijkstra algorithm expanding set algorithm transfer matrix algorith

16、m A* algorithm A*! algorithm ant algorithm WEB GIS</p><p><b>　　目 錄</b></p><p>　　第一章 緒 論1</p><p>　　1.1城市公交問題提出的背景與意義1</p><p>　　1.2我國城市公交及國內(nèi)外研究現(xiàn)狀2&l

17、t;/p><p>　　1.3研究的目的，內(nèi)容及方法3</p><p>　　1.4公交換乘問題及公交網(wǎng)絡(luò)建模的概況4</p><p>　　第二章 公交網(wǎng)絡(luò)的拓?fù)浣?</p><p>　　2.1圖的相關(guān)概念7</p><p>　　2.2城市公交網(wǎng)絡(luò)模型的建立9</p><p>　　2.2.1

18、公交乘車模型9</p><p>　　2.2.2公交網(wǎng)絡(luò)的有向圖結(jié)構(gòu)10</p><p>　　2.2.3公交網(wǎng)絡(luò)拓?fù)鋱D中的權(quán)值的設(shè)定13</p><p>　　2.3公交網(wǎng)絡(luò)性能與平均換乘次數(shù)14</p><p>　　2.3.1公共交通網(wǎng)的技術(shù)指標(biāo)14</p><p>　　2.3.2公共交通線路網(wǎng)平均換乘次數(shù)的研

19、究16</p><p>　　2.3.3平均公交換乘次數(shù)的實(shí)例分析19</p><p>　　第三章 求解公交換乘問題的各類算法設(shè)計(jì)22</p><p>　　3.1Dijkstra算法及其改進(jìn)22</p><p>　　3.1.1Dijkstra算法簡(jiǎn)介22</p><p>　　3.1.2將Dijkstra算法

20、直接運(yùn)用在公交換乘方面所存在的問題22</p><p>　　3.1.3改進(jìn)的Dijkstra算法23</p><p>　　3.1.4 Dijkstra算法的應(yīng)用范圍23</p><p>　　3.2擴(kuò)展集合算法23</p><p>　　3.2.1算法概要24</p><p>　　3.2.2算法的不足24<

21、;/p><p>　　3.2.3算法的改進(jìn)25</p><p>　　3.2.4算法的應(yīng)用28</p><p>　　3.2.5應(yīng)用領(lǐng)域30</p><p>　　3.2.6補(bǔ)充：基于擴(kuò)展集合思想算法的其他實(shí)現(xiàn)31</p><p>　　3.3人工智能算法33</p><p>　　3.3.1啟發(fā)式搜

22、索算法—A*算法33</p><p>　　3.3.2螞蟻算法35</p><p>　　3.4基于WEB GIS的公交線路查詢算法37</p><p>　　3.4.1 GIS的概念及其發(fā)展現(xiàn)狀37</p><p>　　3.4.2 WEB GIS的概念，特點(diǎn)，及應(yīng)用38</p><p>　　3.4.3基于WEB

23、GIS的公交最短路徑算法實(shí)現(xiàn)39</p><p>　　3.4.4本算法分析42</p><p>　　第四章 公交線路查詢系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)43</p><p>　　4.1公交線路查詢系統(tǒng)需求分析43</p><p>　　4.2公交線路查詢系統(tǒng)概要設(shè)計(jì)44</p><p>　　4.3公交線路查詢系統(tǒng)詳細(xì)設(shè)計(jì)4

24、5</p><p>　　4.3.1數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)45</p><p>　　4.3.2系統(tǒng)模塊詳細(xì)設(shè)計(jì)45</p><p>　　4.4公交線路查詢系統(tǒng)的編碼與測(cè)試49</p><p>　　第五章 全文總結(jié)50</p><p>　　5.1本文小結(jié)50</p><p>　　5.2補(bǔ)充討

25、論50</p><p><b>　　致 謝51</b></p><p><b>　　參考文獻(xiàn)52</b></p><p>　　附錄A 主算法的代碼53</p><p>　　附錄B 程序中數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)(頭文件)57</p><p><b>　　第一章

26、緒 論</b></p><p>　　1.1城市公交問題提出的背景與意義</p><p>　　在中國，伴隨著經(jīng)濟(jì)的崛起，城市也在不斷發(fā)展，城鎮(zhèn)化的水平越來越高，城市的規(guī)模也越來越大了。為了滿足城市發(fā)展的需要，城市公共交通運(yùn)輸?shù)母采w面越來越廣，公交線路也日漸增多，乘坐公交出行變得越來越便捷，越來越多的出行者選擇公交作為自己的首選出行方案。與此同時(shí)，公交給人們帶來極大的便利的時(shí)候，也

27、因線路眾多，給人們?cè)谶x擇出行線路時(shí)帶來一定的麻煩。人們?cè)谒熘墓痪€路有限的情況下，想要到達(dá)一個(gè)陌生的地點(diǎn)是有一定難度的，或者即使到達(dá)目的地也因不了解線路而耗費(fèi)更多的時(shí)間或金錢。因此，提供方便，經(jīng)濟(jì)，高效，優(yōu)化的公交出行線路方案，不僅能夠方便本市市民的出行，對(duì)于外來游客，出差等的人的出行與生活都能帶來極大的便利。對(duì)于緩解城市的交通堵塞，提高城市的交通運(yùn)輸效率也是有幫助的。當(dāng)前胡總書記提出要建立和諧社會(huì)主義，運(yùn)用科學(xué)發(fā)展觀，建立此系統(tǒng)能

28、夠充分反映出城市建設(shè)的人性化，以人為本的思想，對(duì)于社會(huì)和諧，城市的健康快速發(fā)展是有好處的。隨著車輛數(shù)的增多，城市交通問題日趨嚴(yán)重，行車不暢通，車輛延誤，并且產(chǎn)生了巨大的空氣污染與噪音污染，與可持續(xù)發(fā)展思想不符，公交作為城市可持續(xù)發(fā)展交通的重要組成部分，在使用本系統(tǒng)后將吸引</p><p>　　公交作為城市動(dòng)態(tài)大系統(tǒng)中的一個(gè)重要組成部分，是城市發(fā)展中不可缺少的物質(zhì)條件與基礎(chǔ)產(chǎn)業(yè)，也是聯(lián)系社會(huì)生產(chǎn)，流通和人民生活的紐

29、帶。沒有城市公交的高速運(yùn)轉(zhuǎn)，就沒有城市的現(xiàn)代化。通過世界上絕大多數(shù)發(fā)達(dá)國家的城市發(fā)展模式與經(jīng)驗(yàn)來看，優(yōu)先發(fā)展公共交通已經(jīng)被大多數(shù)國家作為解決大，中城市交通問題的最佳策略。它是城市可持續(xù)發(fā)展的保障，因此在我國各大城市建立高效的，功能強(qiáng)大，人性化的公交</p><p><b>　　系統(tǒng)刻不容緩。</b></p><p>　　1.2我國城市公交及國內(nèi)外研究現(xiàn)狀</p&

30、gt;<p>　　截至1994年底，全國城鎮(zhèn)人口為34301萬人，占全國人口的28.26%，百萬人口以上的大城市有32個(gè)，按目前的城市化進(jìn)程，預(yù)計(jì)在2010年或稍后，城市人口可達(dá)6.5億，城市化水平在50%左右。展望城市未來的發(fā)展，城市客運(yùn)交通的發(fā)展必須與之相配套。對(duì)大城市自身而言，還呈現(xiàn)如下的特點(diǎn)：1.大城市自行車擁有量趨于飽和，越來越多的私家車的出現(xiàn)加重了交通擁堵；2.城市用地?cái)U(kuò)大，導(dǎo)致公交出行距離增加，換乘問題至關(guān)重

31、要；3.道路網(wǎng)絡(luò)設(shè)施供應(yīng)不足，路網(wǎng)容量不足，結(jié)構(gòu)不合理；4.公交管理手段落后，還沒有全面信息化，智能化。</p><p>　　西方國家對(duì)這些方面重視的較早，如美國，日本，歐洲諸國等，他們已投入了極大的人力，財(cái)力在城市公交網(wǎng)絡(luò)的構(gòu)建上，現(xiàn)在已經(jīng)形成了使用計(jì)算機(jī)網(wǎng)絡(luò)與通信系統(tǒng)進(jìn)行管理的智能交通系統(tǒng)ITS（Intelligence Transport System），從而可以實(shí)時(shí)，準(zhǔn)確，高效的在大范圍內(nèi)全方位的進(jìn)行運(yùn)輸

32、綜合管理，使得人，車，路三者之間的關(guān)系更加和諧統(tǒng)一，極大的改善交通狀況。</p><p>　　智能交通系統(tǒng)(Intelligent Transport System簡(jiǎn)稱ITS)ITS是一個(gè)廣泛包括各種技術(shù)的統(tǒng)稱，是在較完善的道路設(shè)施基礎(chǔ)上，將先進(jìn)的計(jì)算機(jī)、電子技術(shù)、信息技術(shù)、傳感器技術(shù)和系統(tǒng)工程技術(shù)集成，運(yùn)用于地面交通的實(shí)際需求，建立起全方位、實(shí)時(shí)準(zhǔn)確、高效的地面交通系統(tǒng)。它能使交通基礎(chǔ)設(shè)施發(fā)揮出最大的效能，提高

33、服務(wù)質(zhì)量，使社會(huì)能夠高效地使用交通設(shè)施和資源，從而獲得巨大的社會(huì)經(jīng)濟(jì)效益。智能交通系統(tǒng)不但可能解決交通的擁擠，而且對(duì)交通安全、交通事故的處理和救援、客貨運(yùn)輸管理、公路收費(fèi)系統(tǒng)等方面都會(huì)產(chǎn)生巨大的影響。</p><p>　　1995年3月美國交通部首次正式出版了“國家智能交通系統(tǒng)項(xiàng)目規(guī)劃”，明確規(guī)定了智能交通系統(tǒng)的7大領(lǐng)域和29個(gè)用戶服務(wù)功能，并確定了到2005年的年度開發(fā)計(jì)劃。其中7大領(lǐng)域包括：出行和交通管理系統(tǒng)

34、、出行需求管理系統(tǒng)、公共交通運(yùn)營系統(tǒng)、商用車輛運(yùn)營系統(tǒng)、電子收費(fèi)系統(tǒng)、應(yīng)急管理系統(tǒng)、先進(jìn)的車輛控制和安全系統(tǒng)。應(yīng)用發(fā)展較快的幾個(gè)方面分別是，車輛安全系統(tǒng)(占51%)，電子收費(fèi) (占37%)，公路及車輛管理系統(tǒng)(占28%)，實(shí)時(shí)自動(dòng)定位系統(tǒng)(占20%),商業(yè)車輛管理系統(tǒng)(占14%)。</p><p>　　日本組成了由四省一廳參加的全國統(tǒng)一智能交通系統(tǒng)開發(fā)組織(VERTIS)，并于1996年制定了“推進(jìn)ITS總體構(gòu)想

35、”。并推出了一個(gè)投資預(yù)算達(dá)7.8兆億日元，為期長(zhǎng)達(dá)20年的發(fā)展計(jì)劃，包含了智能子系統(tǒng)部分應(yīng)用、改善基礎(chǔ)設(shè)施建設(shè)及系統(tǒng)和產(chǎn)品的研究開發(fā)。同時(shí)日本國內(nèi)豐田、三菱、東芝等100多家企業(yè)也聯(lián)合設(shè)立智能運(yùn)輸系統(tǒng)的開發(fā)和經(jīng)營機(jī)構(gòu)，加大智能交通產(chǎn)品開發(fā)的力度。近年，日本投入了15億日元開發(fā)了全國公路電子地圖系統(tǒng)，打開了車輛電子導(dǎo)航市場(chǎng)。</p><p>　　而我國的城市公交信息系統(tǒng)的研究處于相對(duì)落后的水平，廣大乘客獲取信息的渠

36、道與方式很少，公交信息的完整性與準(zhǔn)確性得不到保證，而且沒有專門的機(jī)構(gòu)負(fù)責(zé)信息的發(fā)布與管理。我國的公交信息系統(tǒng)的現(xiàn)狀如下：</p><p>　　1.乘客獲取的公交信息很少，而且以常規(guī)的手段為主。</p><p>　　我國乘客一般獲取公交信息的手段有交通圖，向熟悉的人問詢等。乘客獲得公交信息很少，除去線路，站點(diǎn)等信息，有關(guān)班次，車輛到離站時(shí)間的信息基本沒有。</p><p&

37、gt;　　2.乘客出行中獲取信息困難，基本上沒有實(shí)時(shí)信息。</p><p>　　除杭州等少數(shù)幾個(gè)城市的乘客可以通過分布于城市中的若干電子站牌獲得一些公交車輛的運(yùn)營信息以外，在其他城市，出行中的乘客無法獲得任何實(shí)時(shí)信息。</p><p>　　3.缺乏專門的交通信息發(fā)布管理機(jī)構(gòu)，乘客獲得的信息的準(zhǔn)確性得不到保證。</p><p>　　目前，我國大多數(shù)城市對(duì)于交通信息的發(fā)

38、布沒有專門的管理機(jī)構(gòu)和規(guī)章制度。在服務(wù)需求量較小時(shí)尚可應(yīng)付，而隨著從業(yè)人員與企業(yè)的增多，城市交通信息服務(wù)變得混亂和低效，有些甚至是對(duì)乘客的誤導(dǎo)。</p><p>　　4.我國公交信息系統(tǒng)與網(wǎng)絡(luò)的結(jié)合是低層次的。</p><p>　　在我國一些城市出現(xiàn)了基于網(wǎng)絡(luò)的公交信息服務(wù)系統(tǒng)，如西安公交網(wǎng)，中國公交查詢網(wǎng)等，可提供一定的信息查詢服務(wù)，但總體上還處于一個(gè)較低的層次，信息是靜態(tài)的，不能實(shí)時(shí)動(dòng)

39、態(tài)的滿足需求[1]。</p><p>　　1.3研究的目的，內(nèi)容及方法</p><p>　　本文研究的目的就是針對(duì)乘客公交信息系統(tǒng)中的核心問題—公交線路換乘問題提出一些算法，以期能夠更快，更人性化的提供給乘客們公交出行方案，使得乘客能</p><p>　　更便捷的到達(dá)目的地。本文的創(chuàng)新之處就在于系統(tǒng)的總結(jié)歸納并提出了解決公交換乘問題的各種算法，比較算法的優(yōu)劣勢(shì)，分析

40、其應(yīng)用場(chǎng)合，針對(duì)不同的場(chǎng)合提出不同的算法。</p><p>　　在內(nèi)容安排上，本文分為五章來敘述。本文的第一章主要是介紹一些背景知識(shí)及概況，在第二章中我們將此問題抽象成數(shù)學(xué)模型，利用圖論分析，加入各種參變量，求解模型，獲得各種有用結(jié)論，如最大換乘次數(shù)等。在此基礎(chǔ)上運(yùn)用算法分析的知識(shí)，對(duì)其時(shí)間復(fù)雜度，空間復(fù)雜度，NP完全性等問題逐一分析。第二章主要是在數(shù)學(xué)理論上分析此問題的深層次內(nèi)涵，從理論高度上統(tǒng)攬全局。第三章是

41、本文的核心章節(jié)，包含了以第二章為基礎(chǔ)而引出的各種算法?；旧弦悦恳环N算法為一小節(jié)分別加以論述。第三章將以這樣幾種算法為主：利用數(shù)據(jù)庫在集合運(yùn)算方面的優(yōu)秀性能而提出的廣度搜索算法(擴(kuò)展集合算法)及其改進(jìn)，用鄰接矩陣構(gòu)造換乘矩陣實(shí)現(xiàn)的換乘算法；人工智能方面的算法：?jiǎn)l(fā)式搜索算法—A*算法在換乘方面的應(yīng)用及其改進(jìn)算法—A*！算法，基于螞蟻算法實(shí)現(xiàn)的公交換乘算法，基于Web GIS的算法。當(dāng)然，其中還會(huì)包括一些對(duì)它們的改進(jìn)算法，也會(huì)不斷的對(duì)其反

42、復(fù)比較論證。部分算法將給出偽代碼的描述，并會(huì)有選擇性的實(shí)現(xiàn)這其中的一種算法，這也將作為下一章的基礎(chǔ)。作者選擇Visual C++集成開發(fā)環(huán)境實(shí)現(xiàn)算法，在此基礎(chǔ)上，第四章將主要闡述公交換乘系統(tǒng)的具體實(shí)現(xiàn)方案(模</p><p>　　曾經(jīng)有計(jì)算機(jī)科學(xué)家定義計(jì)算機(jī)科學(xué)為研究算法的科學(xué)[2]。研究算法無疑是計(jì)算機(jī)科學(xué)的重要領(lǐng)域，也是本文的核心內(nèi)容，貫穿始終。這是本文的最重要的分析方法—算法設(shè)計(jì)與分析。對(duì)于本文所涉及的問題

43、，運(yùn)用組合數(shù)學(xué)中的圖論的相關(guān)理論也是重要的手段。另外，在算法實(shí)現(xiàn)的時(shí)候，充分運(yùn)用軟件工程，UML的思想與方法，形成格式良好的代碼和相關(guān)文檔。</p><p>　　1.4公交換乘問題及公交網(wǎng)絡(luò)建模的概況</p><p>　　公交網(wǎng)絡(luò)中乘客出行路徑選擇的問題，可以表述為在公交網(wǎng)絡(luò)(可以抽象為一張有向圖)中，乘客任意的給定兩點(diǎn)，程序給出一套最優(yōu)出行路線的方案。求解公交</p>&l

44、t;p>　　換乘的算法是公交線路信息系統(tǒng)的關(guān)鍵技術(shù)，也是智能公交系統(tǒng)與公交網(wǎng)絡(luò)優(yōu)化等問題的重要研究領(lǐng)域。</p><p>　　國外對(duì)公交換乘問題的研究是伴隨著公交客流分配領(lǐng)域的研究而發(fā)展起來的，Anderson J在1977年就提出了一種稱為Volvo方法的公交路徑選擇算法，該算法將乘客換乘次數(shù)最少作為乘客出行路徑選擇的首要目標(biāo)，而將不同路線的發(fā)車頻率作為第二目標(biāo)進(jìn)行路徑搜索；Spiess和FLorian于

45、1989年提出了公交網(wǎng)絡(luò)出行策略理論，即將兩點(diǎn)間吸引乘客乘坐的某種線路組合稱為一種出行策略，以各種策略發(fā)車頻率的高低作為乘客選擇某種策略概率的計(jì)算依據(jù)，該方法的缺點(diǎn)是需要枚舉所有的出行策略；Nicholas Koncz 等于1996年提出了公交網(wǎng)絡(luò)靜態(tài)多路徑優(yōu)化的算法，對(duì)公交網(wǎng)絡(luò)中一次和二次換乘的問題進(jìn)行了詳細(xì)的描述，但該算法不能處理二次以上換乘的情況；而國外關(guān)于公交路徑選擇算法的最新研究成果是Gentile等于2004年提出的站點(diǎn)實(shí)時(shí)

46、信息條件下的公交乘客路徑選擇算法。</p><p>　　在國內(nèi)，上世紀(jì)90年代后，隨著一些大城市的公交信息系統(tǒng)的建立，國內(nèi)的一些學(xué)者也開始對(duì)公交網(wǎng)絡(luò)路徑選擇問題進(jìn)行研究。張國伍于1992年在擴(kuò)展Floyd算法的基礎(chǔ)上，提出了公交網(wǎng)絡(luò)多條最短路徑算法；王祖祥等于1993年研究了公交網(wǎng)絡(luò)中乘客換乘次數(shù)最少的約束條件下的最短路徑算法，并給出了多條路徑集的生成技術(shù)；肖宏年等于1995年對(duì)公交網(wǎng)絡(luò)中的換乘現(xiàn)象進(jìn)行了細(xì)致的分

47、析，并提出了以換乘次數(shù)最少為目標(biāo)的換乘矩陣算法。之后國內(nèi)對(duì)公交網(wǎng)絡(luò)路徑搜索算法的研究大多是對(duì)換乘矩陣算法的改進(jìn)，但該類算法的缺陷是算法執(zhí)行時(shí)間隨著換乘次數(shù)的增加成指數(shù)式增長(zhǎng)，一般要設(shè)置一個(gè)最大換乘次數(shù)的限制才能使用，這也是國內(nèi)大多數(shù)此類系統(tǒng)的算法基礎(chǔ)。楊新苗等于2000年進(jìn)行了公交乘客心理調(diào)查，提出了以Dijkstra算法為基礎(chǔ)，以換乘次數(shù)與出行距離作為雙重約束的最優(yōu)路徑搜索算法；</p><p>　　此外，近年

48、來一些學(xué)者將人工智能算法—啟發(fā)式算法，遺傳算法等引入到該類問題的研究中。但從總體上來說，國內(nèi)外學(xué)者在對(duì)公交出行線路問題的研究中，由于換乘現(xiàn)象總是得不到有效的描述，因此至今仍未出現(xiàn)一種既能合理的反映乘客出行公交路線選擇心理特點(diǎn)，同時(shí)又具有很高執(zhí)行效率的算法。</p><p>　　綜上所述，換乘現(xiàn)象能否被合理描述，是制約公交乘客出行時(shí)有效選擇最優(yōu)路徑的關(guān)鍵，這一點(diǎn)在很大程度上依賴于對(duì)公交網(wǎng)絡(luò)進(jìn)行適當(dāng)?shù)臄?shù)學(xué)拓?fù)淠Ｐ偷慕?/p>

49、立。公交網(wǎng)絡(luò)比單純的線路網(wǎng)絡(luò)要復(fù)雜得多，比如其中可能存在“共線”的情況，即在兩個(gè)站點(diǎn)之間存在多條線路并且使用同一路段的情況，這也是對(duì)公交網(wǎng)絡(luò)建模中的難點(diǎn)，還</p><p>　　有公交網(wǎng)是有方向性的，分“上行”，“下行”等。早期的研究者大多采用道路網(wǎng)絡(luò)的建模方式描述公交網(wǎng)絡(luò)，在這方面，Dial(1971)，Leclercq (1972)，Sheffi Y(1985)，De Cea(1989)等完成了一些基礎(chǔ)工作；

50、Nguyen等人將圖論中的有向超級(jí)圖理論引入公交網(wǎng)絡(luò)的研究中，提出了公交超級(jí)網(wǎng)絡(luò)模型，該模型能夠使用一個(gè)統(tǒng)一的數(shù)據(jù)模型同時(shí)描述公交站點(diǎn)，公交線路，上車弧，下車弧，換乘弧等；Anez等提出了用對(duì)偶圖描述公交網(wǎng)絡(luò)的方法，但數(shù)據(jù)冗余較大。</p><p>　　我國對(duì)公交網(wǎng)絡(luò)抽象建模的研究起步較晚。楊新苗等根據(jù)FTA的研究結(jié)果，結(jié)合我國的城市道路網(wǎng)絡(luò)特點(diǎn)，提出了一種基于GIS的公交網(wǎng)絡(luò)表示方法；陸忠等(2002)使用節(jié)點(diǎn)

51、—弧段模型對(duì)公交網(wǎng)絡(luò)拓?fù)浣＃⑨槍?duì)交叉口附近公交站點(diǎn)相鄰的幾種情況進(jìn)行分類，提出了相鄰公交站點(diǎn)合并的原則；黃正東(2003)在Choi等人的研究基礎(chǔ)上，再用動(dòng)態(tài)分段技術(shù)在道路網(wǎng)絡(luò)上標(biāo)示出站點(diǎn)與公交線路，并針對(duì)有些公交線路上下行不重合的現(xiàn)象提出了有向線的概念[3]。</p><p>　　第二章 公交網(wǎng)絡(luò)的拓?fù)浣?lt;/p><p>　　網(wǎng)絡(luò)模型的設(shè)計(jì)主要包括三個(gè)方面：軟件模型設(shè)計(jì)，數(shù)學(xué)模型設(shè)

52、計(jì)，數(shù)據(jù)庫設(shè)計(jì)。軟件模型主要解決網(wǎng)絡(luò)的邏輯表現(xiàn)方式，數(shù)據(jù)結(jié)構(gòu)和提供給上層應(yīng)用的程序接口。它與具體數(shù)據(jù)結(jié)構(gòu)和算法無關(guān)。數(shù)學(xué)模型主要解決的是路徑搜索算法的問題，用數(shù)學(xué)的方法來抽象網(wǎng)絡(luò)模型的特征，提供快速路徑搜索的解決方案，圖論給我們提供了很好的工具。應(yīng)該說明的是，數(shù)學(xué)模型的建立與算法的設(shè)計(jì)是緊密相連的，本章主要論述的是數(shù)學(xué)模型的建立，算法的設(shè)計(jì)將在下一章中闡述。數(shù)據(jù)存貯結(jié)構(gòu)的設(shè)計(jì)是模型持久化的依據(jù)，與軟件模型和數(shù)學(xué)模型都相關(guān)，它為各種算法提

53、供了信息支持。</p><p><b>　　2.1圖的相關(guān)概念</b></p><p>　　我們稱G=(V,E)為圖，如果：(1)V是一個(gè)非空的有限集合，(2)E是V中元素的無序?qū)M成的有限集合。把V中的元素叫做圖的頂點(diǎn)，E中的元素叫做圖的邊。稱G=(V,E)是有向圖，如果：(1)V是一個(gè)非空的有限集合，(2)E是V中元素的有序?qū)M成的有限集合。把V中的元素叫做圖的頂

54、點(diǎn)，E中的元素叫做圖的有向邊或邊。</p><p>　　定義一：圖G=(V,E)的一個(gè)頂點(diǎn)與邊的交錯(cuò)序列，且邊的端點(diǎn)為和 ，i=1,2,…,k,則稱為一條道路(Path)，和 分別稱為的起點(diǎn)和終點(diǎn)。特別的，若中所有的邊均不相同，則稱其為簡(jiǎn)單道路。以為起點(diǎn)，為終點(diǎn)的道路稱為—道路。</p><p>　　定義二：對(duì)于圖G=(V,E)，構(gòu)造一矩陣，其中，，則稱矩陣A是圖G的鄰接矩陣。</p

55、><p>　　定義三：信號(hào)流圖是一種頂點(diǎn)與弧都具有權(quán)值的有向圖。在工程系統(tǒng)中，特別是線性系統(tǒng)(線性網(wǎng)絡(luò))中得到廣泛的應(yīng)用，成為分析線性系統(tǒng)的一種有力工具。</p><p>　　信號(hào)流圖的幾種運(yùn)算：</p><p>　　(1)加法規(guī)則(并聯(lián)法則)</p><p>　　兩個(gè)頂點(diǎn)間m條同向邊可以用一條與它們同向的邊代替，該邊的增益為m個(gè)同向邊的權(quán)的和。

56、</p><p>　　(2)乘法法則(串聯(lián)法則)</p><p>　　M+1個(gè)頂點(diǎn)若有邊相連，則可用有向邊代替，的增益為有向邊的權(quán)的乘積。</p><p><b>　　(3)頂點(diǎn)消去法則</b></p><p>　　一般的，以x為終點(diǎn)的有向邊和以x為始點(diǎn)的有向邊，其增益分別為和 。則可將頂點(diǎn)x消去，得有向邊：</p

57、><p><b>　　其增益分別為：</b></p><p><b>　　(4)反向法則</b></p><p>　　對(duì)于有向邊改變?yōu)?，其上的?quán)值a變?yōu)椤?lt;/p><p><b>　　(5)自環(huán)消去法則</b></p><p>　　一般的，對(duì)于有m條以x為終

58、點(diǎn)的有向邊和自環(huán)的頂點(diǎn)x，如將m條有向邊上的增益除以（1-環(huán)的增益），則可將自環(huán)消去，以x為起點(diǎn)的有向邊的增益不變[2]。</p><p>　　以上這些法則是進(jìn)行公交網(wǎng)絡(luò)分析與化簡(jiǎn)的重要原則，故先列舉出來。</p><p>　　2.2城市公交網(wǎng)絡(luò)模型的建立</p><p>　　城市公交網(wǎng)絡(luò)包含兩個(gè)最基本的元素就是線路和站點(diǎn)，本系統(tǒng)內(nèi)的所有交通工具都包含這兩個(gè)元素，并

59、且具有相同的基本特征：每個(gè)站點(diǎn)都有若干條線路經(jīng)過，經(jīng)過站點(diǎn)的這些線路用名字唯一標(biāo)識(shí)；每條線路由一系列站點(diǎn)組成，并按一定的次序經(jīng)過這些站點(diǎn)，一條線路上的所有站點(diǎn)都可以用名字唯一標(biāo)識(shí)。路徑搜索是建立在線路和站點(diǎn)的關(guān)系上的，搜索的結(jié)果應(yīng)該是站點(diǎn)和路徑的集合，表示如何乘車和怎樣經(jīng)過各個(gè)站點(diǎn)。在這個(gè)抽象層次上可以將不同種類的交通工具統(tǒng)一起來，將公交網(wǎng)絡(luò)用線路和站點(diǎn)的集合來表示。同時(shí)，不同類型的交通工具的線路和站點(diǎn)也有自己的特點(diǎn)，像地鐵、城市輕軌之

60、類的有軌交通工具，機(jī)動(dòng)性較小，速度快，準(zhǔn)時(shí)，而且受路面條件和交通狀況的影響很小，但是車次較少；輪渡是某些城市特有的交通工具，用于渡江，線路固定，速度慢，沒有中間站點(diǎn)，這兩種交通工具的行駛狀況基本上可以看作是靜態(tài)的，相對(duì)來說公交網(wǎng)絡(luò)就復(fù)雜得多，而且也是城市公交系統(tǒng)的主要部分，下面詳細(xì)分析這種網(wǎng)絡(luò)的特點(diǎn)和表示方法。</p><p>　　2.2.1公交乘車模型</p><p>　　選擇公交出行，

61、乘車方案有多個(gè)，因此，出行者要做出選擇。出行者考慮的因素很多，如換乘次數(shù)，旅途時(shí)間，費(fèi)用等，絕對(duì)不能簡(jiǎn)單的抽象成最短路問題，那樣做是沒有意義的。研究表明一般的出行者以換乘次數(shù)最少為優(yōu)先考慮的目標(biāo)，公交網(wǎng)絡(luò)的設(shè)計(jì)也以減少平均換乘次數(shù)為重要目標(biāo)，本文是以最小換乘次數(shù)為首要目標(biāo)的。</p><p>　　在構(gòu)造此模型時(shí)，以最小途經(jīng)站數(shù)為第二目標(biāo)。這樣，構(gòu)造的公交乘車的一般模型如下所示：</p><p&

62、gt;　　給定起點(diǎn)站和終點(diǎn)站，可行的公交路徑集為：</p><p>　　TR={ }，表示的是在起點(diǎn)選擇線路到達(dá)，再換乘到達(dá)，……，直至最終到達(dá)。換乘次數(shù)，途經(jīng)總站數(shù)。</p><p>　　出行者的目標(biāo)函數(shù)：，目標(biāo)函數(shù)性質(zhì)： [4]。</p><p>　　2.2.2公交網(wǎng)絡(luò)的有向圖結(jié)構(gòu)</p><p>　　一般來說，在交通樞紐位置的地段會(huì)有很

63、多公交線路經(jīng)過，為了不至于在同一個(gè)站點(diǎn)?？刻嗟钠嚩枞煌?，會(huì)在相隔不遠(yuǎn)的幾個(gè)地方建立幾個(gè)車站，讓公交車分別?？坑诓煌木€路來減輕線路密集的壓力，這些站點(diǎn)通常具有相同的名字，這些站點(diǎn)之間距離不遠(yuǎn)，一般認(rèn)為在它們之間步行是可以接受的，這一點(diǎn)在搜索路徑的時(shí)候尤其重要。例如，西安的南門站有東西南北四個(gè)。 </p><p>　　A B</p><p><b>　　

64、C</b></p><p>　　(在交通擁擠的路口有可能站點(diǎn)A，B，C名字相同)</p><p>　　圖2.1同名但不同位置的站點(diǎn)</p><p>　　公交線路是比較復(fù)雜的，一般可以分為以下三類：</p><p>　　(1)完全的雙向線路。這種線路有兩個(gè)端點(diǎn)站，在這兩個(gè)端點(diǎn)站之間雙向行車，而且兩個(gè)方向上的行車路線是相同的，經(jīng)過同樣

65、的站點(diǎn)序列和街道序列，但是線路上同一個(gè)名字的站點(diǎn)都是分列街道的兩旁，所以同一個(gè)名字對(duì)應(yīng)兩個(gè)在地理位置上不同站點(diǎn)。這種線路一般來說在兩個(gè)方向上的交通狀況是不同的，因?yàn)樗麄兎謩e在左行線和右行線上行駛。</p><p>　　A1 B1 C1 D1 </p><p>　　A2 B2 C2 D2 </p>

66、<p>　　圖2.2完全的雙向線路</p><p>　　(2)環(huán)形線路。這種線路的行車路線是單向的環(huán)形，線路內(nèi)可以用名字唯一標(biāo)識(shí)一個(gè)在地理位置上唯一的站點(diǎn)，這種線路表示起來比較簡(jiǎn)單。</p><p><b>　　圖2.3環(huán)形線路</b></p><p>　　(3)部分路段是單行線的線路。有些在兩個(gè)端點(diǎn)站之間雙向行車的線路，在個(gè)別比較

67、窄或者比較擁擠的路段會(huì)實(shí)行單向行車，而在其他的路段則跟完全的雙向線路一樣，因此在這樣的線路中兩個(gè)方向上的站點(diǎn)序列和街道序列會(huì)有部分不同，但是總體特點(diǎn)跟完全的雙向線路類似。</p><p>　　A1 B1 C1 D1</p><p>　　A2 B2 D2</p><p><b>　　E</b

68、></p><p>　　圖2.4部分路段是單行線的線路</p><p>　　綜上所述，對(duì)于站點(diǎn)，并不能簡(jiǎn)單的用名字來唯一的標(biāo)識(shí)，所以要引入一個(gè)正整數(shù)m來標(biāo)識(shí)唯一站點(diǎn)，對(duì)于雙行線的線路兩邊的同名站點(diǎn)是否需要區(qū)分則由地理信息數(shù)據(jù)的分辨率和具體應(yīng)用的需要來決定。同樣，這些因素還決定雙向線路上每個(gè)方向的線路是否用不同的公交線路來表示，為了滿足這種要求，公交線路也不能用名字來唯一標(biāo)識(shí)，同樣需要

69、增加一個(gè)唯一的正整數(shù)ID值。另外，對(duì)于同一名字的線路上同名站</p><p>　　點(diǎn)是否需要區(qū)分應(yīng)該取決于同名線路是否區(qū)分方向。</p><p>　　城市的交通狀況是非常復(fù)雜多變的，整個(gè)城市公交網(wǎng)絡(luò)是一個(gè)規(guī)模比較大的動(dòng)態(tài)網(wǎng)絡(luò)系統(tǒng)，而公交網(wǎng)絡(luò)的最優(yōu)路徑搜索本質(zhì)上是一個(gè)多目標(biāo)的決策問題，人們?cè)诓樵兊臅r(shí)候往往是多種情況綜合考慮，其中主要的因素是乘車時(shí)間、票價(jià)和轉(zhuǎn)車的次數(shù)，這些因素有些是網(wǎng)絡(luò)的靜態(tài)

70、特性或者在比較長(zhǎng)的時(shí)期內(nèi)是靜態(tài)特性，比如轉(zhuǎn)車次數(shù)和票價(jià)，另一些是隨著交通狀況的動(dòng)態(tài)變化而變化的，比如乘車時(shí)間。而定義查詢條件本質(zhì)上就是定義一個(gè)以這些因素為自變量的函數(shù)，這樣就能夠?qū)⒍嗄繕?biāo)決策轉(zhuǎn)化成用函數(shù)值表示的單目標(biāo)決策。</p><p>　　如果用賦權(quán)圖模型來表示公共交通網(wǎng)絡(luò)將非常直觀而且很適合于最優(yōu)路徑搜索的問題，若能夠?qū)⒉樵儣l件轉(zhuǎn)換成圖的邊權(quán)值，則最優(yōu)路徑搜索就可以化為賦權(quán)圖的最短路問題。由于公交線路包含多

71、種類型，而且在公共汽車網(wǎng)絡(luò)中，不同方向的行車路線可以會(huì)有不同的行駛情況，所以應(yīng)該有有向圖來表示。</p><p>　　公交網(wǎng)絡(luò)的有向圖有多種不同的表示方法，以下是幾種比較合理的有向圖模型是：</p><p>　　1)令圖G=(V,E)表示公交網(wǎng)絡(luò)，V是公交站點(diǎn)的集合，若站點(diǎn)到有邊當(dāng)且僅當(dāng)(1)到可以步行到達(dá)，或者(2)有公交線路從到，并且沒有中間站點(diǎn)。</p><p&g

72、t;　　不允許包含中間站點(diǎn) 步行</p><p>　　(第一種情況的邊) (第二種情況的邊)</p><p>　　圖2.5第一種有向圖模型的邊定義 </p><p>　　2)令圖G=(V,E)表示公交網(wǎng)絡(luò)，V是公交站點(diǎn)的集合，若站點(diǎn)到有邊當(dāng)且僅當(dāng)(1)站點(diǎn)到有線路

73、直達(dá)，或者(2)存在一條道路 ，到之間有車直達(dá)并且允許從步行至，或者(3) 存在一條道路 ，到之間有車直達(dá)并且允許從步行至。 </p><p>　　(第一種情況的邊) (第二種情況的邊) (第三種情況的邊)</p><p>　　圖2.6第二種有向圖模型的邊定義(允許包含中間站點(diǎn))</p><p>　　“可以步行到達(dá)”

74、的概念的解釋：上面分析公交站點(diǎn)的時(shí)候提到有些站點(diǎn)相距很近，之所以分別設(shè)置兩個(gè)站是為了分流過多的經(jīng)過線路，這樣的站點(diǎn)之間就是 “可以步行到達(dá)”的，這么處理為了讓路徑搜索的結(jié)果更合理，因?yàn)槿藗冊(cè)趯?shí)際乘車的時(shí)候一般情況下是不會(huì)拒絕這種步行的，而且這樣有可能得到比在原地等車好得多的方案，而界定相距多少是很近則可以由具體的應(yīng)用來決定，也可以動(dòng)態(tài)的設(shè)置亦可以根據(jù)實(shí)際經(jīng)驗(yàn)來靜態(tài)設(shè)定[5]。</p><p>　　2.2.3公交網(wǎng)

75、絡(luò)拓?fù)鋱D中的權(quán)值的設(shè)定</p><p>　　上述有向圖的邊表示的是站點(diǎn)之間的連接關(guān)系，而邊的權(quán)值則用來量化這種關(guān)系，是路徑優(yōu)先等級(jí)的衡量標(biāo)準(zhǔn)，上文中已經(jīng)分析了人們?cè)诓樵冞^程中所關(guān)心的各種因素。我們會(huì)碰到的各種因素是分擔(dān)在各條線路之上的，假設(shè)由集合C表示。令W1=f(C)，W1就用來表示綜合了C中的各種因素的每條線路上的權(quán)值。</p><p>　　在上述有向圖模型2)中的情形(1)里，C就是

76、從到的綜合因素，而在情形(2)中，由于有步行的路段，W1還應(yīng)該加上以步行距離d為自變量的函數(shù)值來表示人對(duì)步行的厭惡程度及步行的時(shí)間，即W1=f(C)+g(d)。情形(3)與情形(2)類似進(jìn)行計(jì)算。</p><p>　　轉(zhuǎn)車次數(shù)是一種針對(duì)站點(diǎn)的權(quán)值，而一般的路徑搜索算法都是針對(duì)邊權(quán)值的，因此有必要將轉(zhuǎn)車次數(shù)轉(zhuǎn)換為邊權(quán)值，增加一個(gè)轉(zhuǎn)車權(quán)重W2到每條邊上，轉(zhuǎn)車權(quán)重的折算方法最終是折算成對(duì)C中每個(gè)變量的另一種賦值方案，令

77、它的修改量的集合為，采用W1對(duì)C的量化關(guān)系f，得到最后的邊權(quán)值表達(dá)式：W= W1 +W2=f(C)+f()+g(d) 式(2-1)。</p><p>　　需要注意的是，在建立了初步的模型之后，應(yīng)按照前述信號(hào)流圖的幾類化簡(jiǎn)法則，對(duì)公交網(wǎng)絡(luò)進(jìn)行化簡(jiǎn)， 如果圖中有多條從到的平行邊，則W1取其權(quán)值之和； </p><p>　　并且對(duì)網(wǎng)絡(luò)進(jìn)行消去與自環(huán)合并的工作，得到一個(gè)化簡(jiǎn)后的模型。</p&

78、gt;<p>　　如果將W1看成一般意義下的交通費(fèi)用(時(shí)間和經(jīng)濟(jì)兩方面的開銷)，則這種邊權(quán)值表達(dá)式可以寫成“邊權(quán)值=普通交通費(fèi)用+轉(zhuǎn)車權(quán)重”。這樣做的優(yōu)點(diǎn)是將轉(zhuǎn)車次數(shù)和其它的權(quán)值統(tǒng)一起來考慮。而且量化了轉(zhuǎn)車的影響，如果將W2設(shè)成動(dòng)態(tài)配置的話還可以根據(jù)查詢者的不同要求來選擇，這樣的結(jié)果更符合實(shí)際情況，比如如果多轉(zhuǎn)車可以顯著減少乘車時(shí)間的話，那么這種方案應(yīng)該比少轉(zhuǎn)車的方案更優(yōu)化。</p><p>　　g

79、(d)和W2的設(shè)定突出了心理作用在路徑搜索中的影響，正如心理因素在經(jīng)濟(jì)中的影響一樣，這種因素使人們?cè)诳紤]方案的可行性的時(shí)候不僅僅考慮諸如時(shí)間和費(fèi)用等客觀條件，還會(huì)考慮主觀的對(duì)旅途舒適程度的一種喜好，這種喜好可以通過量化成邊權(quán)值的方式來體現(xiàn)。</p><p>　　實(shí)際的公交網(wǎng)絡(luò)應(yīng)該是一個(gè)實(shí)時(shí)的動(dòng)態(tài)網(wǎng)絡(luò)，對(duì)應(yīng)的有向圖的邊權(quán)值應(yīng)該是動(dòng)態(tài)變化的，其動(dòng)態(tài)性主要體現(xiàn)在以下兩個(gè)方面：(1)系統(tǒng)本身的動(dòng)態(tài)性。由于路面的交通狀況是

80、實(shí)時(shí)變化的，所以對(duì)系統(tǒng)中主要的公交運(yùn)行網(wǎng)絡(luò)來說，兩個(gè)站點(diǎn)之間的行駛時(shí)間也是實(shí)時(shí)變化的，包括路口的交通信號(hào)燈、堵車、臨時(shí)路面維修等情況都會(huì)影響行駛時(shí)間。(2)查詢條件的動(dòng)態(tài)性。不同的查詢者對(duì)影響權(quán)值的各種因素的關(guān)注程度不同，這將引起所有的函數(shù)關(guān)系，如f和g等發(fā)生變化，而且還有可能需要人為的限制一些線路，比如指定要通過哪座橋或者不通過哪座橋或者避開某些堵車的路段等，另外不同的查詢者可能對(duì)轉(zhuǎn)車次數(shù)和其他因素之間的制約關(guān)系有不同的看法，這將影響

81、W2的取值[5]。</p><p>　　2.3公交網(wǎng)絡(luò)性能與平均換乘次數(shù)</p><p>　　2.3.1公共交通網(wǎng)的技術(shù)指標(biāo)</p><p>　　為了評(píng)價(jià)公交網(wǎng)絡(luò)的性能優(yōu)劣，必須使用一些技術(shù)指標(biāo)來進(jìn)行評(píng)價(jià)。主要的指標(biāo)有如下幾種[6]：</p><p>　　(1)城市公共交通網(wǎng)線路密度</p><p>　　它的定義是公共

82、交通線路通行的街道長(zhǎng)度與城市用地面積之比，計(jì)算公式為：</p><p>　?。ǎ?式(2-2)</p><p><b>　　式中：</b></p><p><b>　　——線路網(wǎng)密度</b></p><p>　　L——公共交通線路網(wǎng)長(zhǎng)度</p><p><b&

83、gt;　　F——城市面積</b></p><p>　　(2)公共交通線路網(wǎng)非直線性系數(shù)</p><p>　　它定義為乘客實(shí)際乘車路程與乘車起始點(diǎn)之間的直線距離的比。對(duì)于棋盤式街道網(wǎng)：</p><p>　　圖2.7 棋盤式街道網(wǎng)示意圖</p><p>　　非直線性系數(shù)：； 式(2-3)&

84、lt;/p><p><b>　　對(duì)于輻射式街道網(wǎng)：</b></p><p>　　a c 中心點(diǎn)</p><p>　　起點(diǎn) 終點(diǎn)</p><p>　　圖2.8 輻射式街道網(wǎng)示意圖</p><p>　　非直線性系數(shù)：；

85、式(2-4)</p><p><b>　　對(duì)于環(huán)形街道網(wǎng)：</b></p><p><b>　　R R</b></p><p>　　圖2.9 環(huán)形街道網(wǎng)示意圖</p><p>　　非直線性系數(shù)：。

86、 式(2-5)</p><p>　　(3) 城市公共交通線路重復(fù)系數(shù)</p><p>　　它定義為營業(yè)線路總長(zhǎng)度與線路網(wǎng)長(zhǎng)度之比值，在公共交通發(fā)達(dá)的城市一般為1.25至2.5之間。計(jì)算公式：。</p><p>　　(4)公共交通換乘系數(shù)</p><p>　　換乘系數(shù)是衡量乘客的直達(dá)程度。根據(jù)客流起點(diǎn)與到終點(diǎn)流量圖或主要集散點(diǎn)

87、，在其間設(shè)置大站快車線，盡量減少乘客換乘。大城市不應(yīng)超過1.5，中、小城市不應(yīng)超過1.3。 </p><p>　　(5)城市公共交通線路長(zhǎng)度</p><p>　　市區(qū)公共汽車、電車主要線路的單程長(zhǎng)度，一般為8-10km，不超過13km，或取車輛運(yùn)送時(shí)間30-40min的行程為宜；大城市的直徑線路，包括郊區(qū)線路，最長(zhǎng)不宜超過60min的行程，中小城市的郊區(qū)線路不宜超過40min的行程。線路過

88、長(zhǎng)會(huì)帶來如下問題：行車時(shí)間較難保證，準(zhǔn)點(diǎn)率下降；沿線客流不容易均勻，使平均載客量降低。</p><p>　　(6)城市軌道交通線路的布置方式</p><p>　　在市中心區(qū)范圍，地下鐵路應(yīng)采用埋設(shè)式，快速有軌電車宜采用埋設(shè)式或高架式；在城市邊緣地區(qū)，地下鐵道線可鋪設(shè)在地面上，但必須全封閉，快速有軌電車宜采取地面獨(dú)立路基的方式。</p><p>　　(7)規(guī)劃公共交通

89、線路網(wǎng)的站點(diǎn)覆蓋面積</p><p>　　按300m步行半徑計(jì)，不得小于城市用地的面積50%，按500m半徑計(jì)算，不得小于90%。</p><p>　　2.3.2公共交通線路網(wǎng)平均換乘次數(shù)的研究</p><p>　　所謂平均換乘次數(shù)就是任何一個(gè)人從公交路網(wǎng)的任何一個(gè)站點(diǎn)到另外任何一個(gè)站點(diǎn)，所需要的換乘公交車的平均次數(shù)，這里包含了所有的公交線路和站點(diǎn)。公交網(wǎng)絡(luò)的宏觀設(shè)

90、計(jì)指標(biāo)之一——平均換乘次數(shù)能夠在一定程度上反映公交網(wǎng)絡(luò)設(shè)計(jì)和實(shí)施的現(xiàn)狀，平均換乘次數(shù)反映了公交網(wǎng)絡(luò)的可達(dá)性。</p><p>　　有很多的方法來求解平均換乘次數(shù)。以下考慮存在步行情況下的平均換乘次數(shù)的計(jì)算方法[7]。</p><p>　　本算法基于如下假設(shè)：</p><p>　　假設(shè)一：不考慮出行者從最初出發(fā)點(diǎn)到達(dá)第一個(gè)公交站點(diǎn)的步行，假設(shè)出行者的最初出發(fā)點(diǎn)是整個(gè)公

91、交網(wǎng)絡(luò)中的一個(gè)公交站點(diǎn)。</p><p>　　假設(shè)二：由專家給出一個(gè)步行換乘距離，如果兩個(gè)站點(diǎn)距離在步行換乘距離之內(nèi)時(shí)，稱這兩個(gè)站點(diǎn)為鄰近站點(diǎn)。假設(shè)任何出行都會(huì)最大化的利用鄰近站點(diǎn)減少換乘。</p><p>　　假設(shè)三：假設(shè)出行者從一個(gè)站點(diǎn)到達(dá)它的鄰近站點(diǎn)都選擇步行，不考慮出行者通過自行車到達(dá)鄰近站點(diǎn)或者其它交通方式到達(dá)鄰近站點(diǎn)的影響，因?yàn)槿绻鲂姓咄ㄟ^自行車到達(dá)鄰近站點(diǎn)或者其它交通方式到

92、達(dá)鄰近站點(diǎn)，不容易判斷鄰近站點(diǎn)的距離長(zhǎng)度。</p><p>　　假設(shè)四：在分析站點(diǎn)對(duì)之間的換乘次數(shù)時(shí)，不考慮不同路線不同車次以及不同車次的發(fā)車頻率的影響，只考慮網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)網(wǎng)絡(luò)換乘次數(shù)的影響。</p><p>　　假設(shè)五：在城市范圍內(nèi)，任意兩個(gè)站點(diǎn)間的換乘次數(shù)小于10次，實(shí)際上對(duì)于絕大多數(shù)現(xiàn)代城市來說，任意兩個(gè)站點(diǎn)間的換乘次數(shù)大于或者等于10次是不可思議的，提出本假設(shè)是為了方便下面算法的

93、計(jì)算。</p><p>　　基于以上的分析與假設(shè)，可以按照如下思路考慮存在步行的情況下，任何一個(gè)公交站點(diǎn)間的平均換乘次數(shù)：</p><p>　　首先把公交網(wǎng)絡(luò)轉(zhuǎn)換成一個(gè)有向圖，圖中的頂點(diǎn)為公交站點(diǎn)，圖中任意兩點(diǎn)之間如果有邊相連則代表這兩個(gè)公交站點(diǎn)有線路相連通，邊上的箭頭代表了線路的方向。將所有的邊都賦值，如果兩個(gè)站點(diǎn)有公交線路連通，邊的值賦1;如果兩個(gè)站點(diǎn)步行連通距離在步行換乘距離以內(nèi)，將

94、兩站點(diǎn)的有向邊賦予0 .1。</p><p>　　在上述賦值過程中，會(huì)遇到一類特殊情況，如下圖2.10,A,B,C分別為3個(gè)公交站點(diǎn)，站點(diǎn)A與B的距離在步行換乘距離之內(nèi)，站點(diǎn)B與C的距離也在步行換乘距離之內(nèi)，但是站點(diǎn)A與C的距離在步行換乘距離之外，按照假設(shè)，行人不可能選擇從A步行到B，再從B步行到C的路線，我們?cè)O(shè)與上述B站點(diǎn)類似的站點(diǎn)稱為“中間站點(diǎn)”。我們將處于A和C之間的“中間站點(diǎn)”B分為B1與B2兩個(gè)站點(diǎn)，將

95、圖2.10轉(zhuǎn)化為圖2.11，在圖2.11中，B1與B2沒有連接，它們與其余所有站點(diǎn)的連接情況與B站點(diǎn)相同，上述變換通過增加新的站點(diǎn)的方法消除計(jì)算過程中的“中間站點(diǎn)”的影響。</p><p>　　A C</p><p><b>　　B</b></p><p>　　圖2.

96、10 存在“中間站點(diǎn)”的情況</p><p>　　A C</p><p><b>　　B1 B2</b></p><p>　　圖2.11 “中間站點(diǎn)”消除后的情況</p><p><b>　　

97、具體算法步驟如下:</b></p><p><b>　　步驟一：</b></p><p>　　將公交網(wǎng)絡(luò)圖化為簡(jiǎn)單有向圖，簡(jiǎn)單圖中的頂點(diǎn)為公交站點(diǎn)，統(tǒng)計(jì)公交網(wǎng)絡(luò)中任意兩點(diǎn)的步行距離，簡(jiǎn)單圖任意兩點(diǎn)之間如果有邊相連則代表這兩個(gè)公交站點(diǎn)有線路相連通或者這兩個(gè)點(diǎn)為鄰近站點(diǎn)，邊上的箭頭代表了線路的方向。</p><p><b>　

98、　步驟二：</b></p><p>　　將公交簡(jiǎn)單有向圖的任意兩相連邊賦值。如果兩個(gè)站點(diǎn)有公交線路連通，邊的值賦1，如果兩個(gè)站點(diǎn)為鄰近站點(diǎn)，將兩站點(diǎn)的有向邊賦予0.1。</p><p><b>　　步驟三：</b></p><p>　　按照上述方法構(gòu)造新的網(wǎng)絡(luò)，添加新的站點(diǎn)，消除“中間站點(diǎn)”的影響。</p><p

99、><b>　　步驟四：</b></p><p>　　按照Floyd算法計(jì)算任意兩點(diǎn)之間的最短路，得出最后的最短路矩陣。</p><p><b>　　步驟五：</b></p><p>　　將最后的最短路矩陣中新添加的站點(diǎn)恢復(fù)為原來的中間站點(diǎn)，得到新的最短路矩陣，方法如下：將以某中間站點(diǎn)構(gòu)造出的站點(diǎn)到其余站點(diǎn)的最短距離作

100、為該中間站點(diǎn)到其余站點(diǎn)的最短距離，即去掉最短路矩陣中間站點(diǎn)構(gòu)造出的站點(diǎn)并以原來的中間站點(diǎn)代替，以中間站點(diǎn)構(gòu)造出的站點(diǎn)所在最終的最短路矩陣的行或列的最小值作為中間</p><p>　　站點(diǎn)所對(duì)應(yīng)行或列的元素，得到新的矩陣。按照假設(shè)五，所得到的新的矩陣中元素的整數(shù)部分減去1后對(duì)應(yīng)站點(diǎn)間的公交換乘次數(shù)，元素的小數(shù)部分代表對(duì)應(yīng)站點(diǎn)間的步行換乘次數(shù)，如果兩站點(diǎn)對(duì)應(yīng)的矩陣元素為0.1，表示這兩個(gè)站點(diǎn)只需步行換乘就可到達(dá)，至此

101、，上述矩陣能夠充分反映公交網(wǎng)絡(luò)的換乘情況[8]。</p><p>　　2.3.3平均公交換乘次數(shù)的實(shí)例分析</p><p>　　假設(shè)有一個(gè)8個(gè)站點(diǎn)的公交網(wǎng)絡(luò)，計(jì)算該網(wǎng)絡(luò)的平均換乘次數(shù)。為了簡(jiǎn)化起見，假設(shè)該公交網(wǎng)絡(luò)為雙向的，并且各站點(diǎn)間都可以通過換乘到達(dá)，實(shí)際上上述算法對(duì)于單向網(wǎng)絡(luò)也適用，計(jì)算過程如下[9]：</p><p>　　按照算法步驟一、二，算例中的公交簡(jiǎn)單圖

102、如下，根據(jù)賦值情況我們得知，站點(diǎn)B與C, C與D, D與E為鄰近站點(diǎn)。 F</p><p><b>　　G</b></p><p><b>　　1</b></p><p>　　1 1 1 </p><p>　　A 1 H</p><

103、;p>　　1 1</p><p><b>　　E</b></p><p>　　B 0.1 0.1</p><p>　　C 0.1 D</p><p>　　圖2.12 公交網(wǎng)絡(luò)轉(zhuǎn)換為簡(jiǎn)單圖賦值情況 </p><p>　　按照算法步驟三構(gòu)造新的公交

104、簡(jiǎn)單圖如下，將C, D站點(diǎn)分別以C1，C2和D1， D2表示。 F</p><p><b>　　G</b></p><p>　　1 1 1 1 1 11</p><p>　　A H</p><p>　

105、　1 1 </p><p><b>　　E </b></p><p>　　B 0.1 0.1</p><p>　　C1 C2 0.1 D1 D2</p><p>　　圖2.13公交網(wǎng)絡(luò)消除中間站點(diǎn)后的簡(jiǎn)單圖情況</p><p>　

106、　按照Floyd算法計(jì)算任意兩點(diǎn)間的最短路，得出最短路矩陣如下：</p><p>　　按照步驟五，將C1，C2站點(diǎn)所在的行或列以C行或C列代替，C行或C列各元素為C1，C2行或列相對(duì)應(yīng)元素的最小值，D 1，D2站點(diǎn)所在的行或列以D行或D列代替，D行或D列各元素為D1，D2行或列相對(duì)應(yīng)元素的最小值。新矩陣如下所示：</p><p>　　至此所得到的矩陣已經(jīng)能夠反映該公交網(wǎng)絡(luò)的換乘情況，比如B

107、行與C列對(duì)應(yīng)元素為0.1，表示從B站點(diǎn)可步行到達(dá)C站點(diǎn)，C行與F列對(duì)應(yīng)元素為2.1，表示從C站點(diǎn)到F站點(diǎn)需要經(jīng)過一次公交換乘，一次步行換乘。最后我們可以根據(jù)各站點(diǎn)間的公交客流量來具體計(jì)算該網(wǎng)絡(luò)的平均換乘次數(shù)(計(jì)算過程略)。</p><p>　　上述算法中的假設(shè)二由專家給出一個(gè)步行換乘距離，由于不同的出行者可能有自己不同的步行換乘距離，為了便于計(jì)算，可以采取統(tǒng)計(jì)的方法，也可以采用抽樣調(diào)查的方法，調(diào)查出某個(gè)時(shí)間段步行

108、換乘距離不同的出行者占總出行者的比例，再計(jì)算不同步行換乘距離的公交網(wǎng)絡(luò)的平均換乘次數(shù)，然后進(jìn)行加權(quán)平均，計(jì)算出最終結(jié)果。</p><p>　　設(shè)有一個(gè)公交網(wǎng)絡(luò)，步行換乘距離不同的出行者比例及相應(yīng)平均換乘次數(shù)如下表所示：</p><p><b>　　表2.1</b></p><p>　　由上表所得到該公交網(wǎng)絡(luò)的平均換乘次數(shù)為：</p>

109、<p>　　1.1*0.25+1.05*0.55+0.95*0.20=1.0425</p><p>　　第三章 求解公交換乘問題的各類算法設(shè)計(jì)</p><p>　　3.1Dijkstra算法及其改進(jìn)</p><p>　　3.1.1Dijkstra算法簡(jiǎn)介</p><p>　　這是一種求解從圖中的一點(diǎn)到其余各點(diǎn)的最短路徑的算法