優(yōu)秀論文_公交線路選乘優(yōu)化模型

1、<p>　　公交線路選乘優(yōu)化模型</p><p>　　摘要 本文針對(duì)城市公交網(wǎng)絡(luò)的特點(diǎn),以最小換乘次數(shù)為第一目標(biāo)，最小途經(jīng)站數(shù)為第二目標(biāo)，并綜合考慮乘車(chē)費(fèi)用、交通便利程度等其他因素。</p><p>　　對(duì)問(wèn)題一建立了動(dòng)態(tài)遞歸搜索模型，提出了廣度優(yōu)先算法，依此確定公交線路和換乘地點(diǎn)共同組成的最優(yōu)路徑，可使出行者快捷方便地獲取公交線路信息及乘換地點(diǎn)，包括所經(jīng)每一站點(diǎn)的所有公交線路；

2、所得結(jié)果為：S3359→S1828換乘1次，經(jīng)45個(gè)公汽站點(diǎn)，所花費(fèi)的時(shí)間為101分鐘； S1557→S0481，換乘2次，出行耗時(shí)106分鐘，乘車(chē)費(fèi)用為3元，共經(jīng)32個(gè)公汽站點(diǎn)；S0971→S0485換乘1次，出行耗時(shí)128分鐘，乘車(chē)費(fèi)用為3元，共經(jīng)由41個(gè)公汽站點(diǎn)；S0008→S0073換乘1次，最短耗時(shí)83分鐘，乘車(chē)費(fèi)用為2元，共經(jīng)過(guò)26個(gè)公汽站點(diǎn)；S0148→S0485換乘2次，出行時(shí)間為106分鐘，乘車(chē)花費(fèi)為3元，共經(jīng)由32個(gè)

3、公汽站點(diǎn)；S0087→S3676換乘1次，出行時(shí)間為65分鐘，路費(fèi)為2元，共經(jīng)過(guò)20個(gè)公汽站點(diǎn)。</p><p>　　對(duì)問(wèn)題二建立了分類(lèi)枚舉篩選模型，分析了在最小換乘次數(shù)下的三類(lèi)通行模式，最后求解出符合大多數(shù)人出行習(xí)慣的最優(yōu)乘車(chē)路線；所得結(jié)果為：S3359→S1828換乘1次，經(jīng)45個(gè)公汽站點(diǎn)，所花費(fèi)的時(shí)間為101分鐘； S1557→S0481換乘2次，出行耗時(shí)為106分鐘，乘車(chē)費(fèi)用為3元，共經(jīng)32個(gè)公汽站點(diǎn)；S

4、0971→S0485換乘1次，出行耗時(shí)為128分鐘，乘車(chē)費(fèi)用為3元，共經(jīng)由41個(gè)公汽站點(diǎn)；S0008→S0073換乘1次最短耗時(shí)為83分鐘，乘車(chē)費(fèi)用為2元，共經(jīng)過(guò)26個(gè)公汽站點(diǎn)；S0148→S0485換乘2次，出行時(shí)間106分鐘，乘車(chē)花費(fèi)為3元，共經(jīng)由32個(gè)公汽站點(diǎn)；S0087→S3676地鐵直達(dá)，耗時(shí)33分鐘，費(fèi)用為3元，經(jīng)過(guò)的地鐵站數(shù)為10站。</p><p>　　對(duì)問(wèn)題三建立了擬蟻群搜索模型及蟻群內(nèi)嵌局部搜

5、索算法，此算法綜合考慮了影響公交選乘的諸多因素，如出行者的人文需要等，有效地解決了任意兩站點(diǎn)間的最優(yōu)路徑的選擇問(wèn)題，最后結(jié)合實(shí)際情況，對(duì)模型進(jìn)一步優(yōu)化，提出了人工神經(jīng)網(wǎng)絡(luò)彈性模型，為原模型提供了一個(gè)改進(jìn)方向。</p><p>　　此外，鑒于交通承壓能力有限，即超過(guò)一定限度的人流量可能會(huì)引起交通堵塞，對(duì)于問(wèn)題一、二，在給出最優(yōu)乘車(chē)方案的同時(shí)，又提供了一些推薦線路來(lái)滿足乘客的不同需求。</p><

6、p>　　關(guān)鍵詞：換乘；最優(yōu)路徑；公交線路；廣度優(yōu)先算法；蟻群內(nèi)嵌局部搜索算法</p><p><b>　　一、問(wèn)題的提出</b></p><p>　　舉世矚目的北京奧運(yùn)會(huì)明年8月將隆重召開(kāi)，屆時(shí)大量觀眾將前往各場(chǎng)館觀看比賽，其中大多數(shù)人將會(huì)選擇乘坐公共交通，為了能給公眾提供更加通暢、便利的出行條件，現(xiàn)準(zhǔn)備研發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢計(jì)算機(jī)系統(tǒng)，以滿足查

7、詢者的各種需要。</p><p>　　現(xiàn)在的問(wèn)題是根據(jù)公交線路及相關(guān)信息，從實(shí)際情況出發(fā)考慮，設(shè)計(jì)一個(gè)查詢系統(tǒng)，解決以下問(wèn)題：</p><p>　　1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型及算法，求出6對(duì)起始站→終到站之間的最佳路線：S3359→S1828， S1557→S0481，S0971→S0485，S0008→S0073，

8、 S0148→S0485，S0087→S3676。</p><p>　　2、同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。</p><p>　　3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，給出任意兩站點(diǎn)線路選擇問(wèn)題的數(shù)學(xué)模型。</p><p><b>　　二、 問(wèn)題的分析</b></p><p>　　該問(wèn)題是在滿足一定約束條件下的最優(yōu)

9、線路選擇問(wèn)題，涉及到途中轉(zhuǎn)乘次數(shù)、出行耗時(shí)、出行費(fèi)用等因素，此外不同的觀眾在線路選擇上可能會(huì)根據(jù)自己的情況有不同的要求，有的會(huì)側(cè)重于對(duì)時(shí)間的考慮，有的則會(huì)優(yōu)先考慮費(fèi)用問(wèn)題。我們從一般人的心理角度出發(fā)，如果到達(dá)目的地的公交車(chē)的轉(zhuǎn)乘次數(shù)超過(guò)兩次，那么這樣的方案的方便可達(dá)性較差，一般是不會(huì)被人采納的，于是我們約定換乘次數(shù)不超過(guò)兩次，并且為滿足普適情況，優(yōu)先考慮轉(zhuǎn)乘次數(shù)，力求換乘次數(shù)最少。在滿足此條件的前提下，對(duì)可能的線路進(jìn)行篩選，然后再考慮出

10、行耗時(shí)，讓乘車(chē)所用的時(shí)間盡可能最短,再對(duì)可行線路作進(jìn)一步篩選，最后再適當(dāng)考慮出行費(fèi)用，確定出行的最佳線路。</p><p>　　對(duì)于問(wèn)題（2），由于要同時(shí)考慮地鐵線路，我們?cè)谵D(zhuǎn)乘不超過(guò)兩次的基礎(chǔ)上，根據(jù)地鐵的分布情況，利用地鐵與公汽站點(diǎn)之間的關(guān)聯(lián)及地鐵線路之間的聯(lián)系，在第一問(wèn)的基礎(chǔ)上對(duì)算法進(jìn)行了修改，并逐步添加約束條件，最后搜索出最佳的乘車(chē)路線。</p><p>　　對(duì)于問(wèn)題（3），在前兩

11、問(wèn)的基礎(chǔ)上再考慮步行，綜合考慮的因素很多，同時(shí)要根據(jù)出行者的實(shí)際需要，對(duì)不同的需求賦予權(quán)重，可以說(shuō)是對(duì)公交選乘問(wèn)題的綜合。</p><p><b>　　三、模型假設(shè)</b></p><p>　?、懦丝蛽Q乘公交車(chē)的次數(shù)最多不得超過(guò)2次。</p><p>　?、瞥丝偷牟叫姓緮?shù)不得超過(guò)兩站，并且在終點(diǎn)站與其前一站之間不允許步行。</p>

12、<p>　?、莾?yōu)先考慮換乘次數(shù)最少的乘車(chē)路線，其次考慮出行耗時(shí)最少。</p><p>　?、冉ㄖ┕さ茸鳂I(yè)不會(huì)影響道路的通行。</p><p>　?、晒卉?chē)在行駛過(guò)程中不會(huì)因?yàn)橐馔馐鹿识⒄`時(shí)間。</p><p><b>　　四、符號(hào)的說(shuō)明</b></p><p>　　L+三位數(shù)字：公汽線路編號(hào)格式，如L00

13、3</p><p>　　S+四位數(shù)字：公汽站點(diǎn)編號(hào)格式，如S0028</p><p><b>　　T1：地鐵線路編號(hào)</b></p><p><b>　　T2：地鐵線路編號(hào)</b></p><p>　　D+兩位數(shù)字：地鐵站點(diǎn)編號(hào)格式，如D01</p><p>　　Lxxx（上

14、）：公交線路Lxxx的上行線（xxx為線路編號(hào)）</p><p>　　Lxxx（下）：公交線路Lxxx的下行線</p><p><b>　　A：起始公交站點(diǎn)</b></p><p><b>　　B：終點(diǎn)公交站點(diǎn)</b></p><p>　　StartNode：用于存放經(jīng)過(guò)起始站A的所有公交線路，St

15、artNode[i] 是該數(shù)組中的元素</p><p>　　EndNode：用于存放經(jīng)過(guò)終點(diǎn)站B的所有公交線路，EndNode[j]是該數(shù)組中的元素</p><p>　　StartStack：存放經(jīng)過(guò)起始站的所有公交線路包含的站點(diǎn)名稱</p><p>　　EndStack：存放經(jīng)過(guò)終點(diǎn)站的所有公交線路包含的站點(diǎn)名稱</p><p>　　Com

16、pareA：經(jīng)過(guò)A的所有公交線路與這些公交線路所包含的站點(diǎn)建立的連接矩陣，</p><p>　　CompareA[i，j]]是其中的某一元素</p><p>　　CompareB：經(jīng)過(guò)B的所有公交線路與這些公交線路所包含的站點(diǎn)建立的連接矩陣，</p><p>　　CompareB[m，n]是其中的某一元素</p><p>　　RCompare

17、A矩陣：經(jīng)過(guò)StartNode數(shù)組中某一元素的公交線路與其所包含的站點(diǎn)建立的矩陣</p><p>　　DNode：地鐵站與所對(duì)應(yīng)的公交站建立相對(duì)應(yīng)的二維數(shù)組</p><p>　　T1Node：地鐵線路T1與經(jīng)過(guò)的所有地鐵站建立的一維數(shù)組</p><p>　　T2Node：地鐵線路T2與經(jīng)過(guò)的所有地鐵站建立的一維數(shù)組</p><p>　　t1：

18、相鄰公汽站平均行駛時(shí)間t1(包括停站時(shí)間) 即3分鐘</p><p>　　t2：相鄰地鐵站平均行駛時(shí)間t2(包括停站時(shí)間) 即2.5分鐘</p><p>　　五、模型的建立與求解</p><p><b>　　5.1 問(wèn)題一</b></p><p>　　5.1.1、動(dòng)態(tài)遞歸搜索模型及廣度優(yōu)先算法</p>&l

19、t;p>　　任意輸入兩公交站點(diǎn)作為起始站和終點(diǎn)站，查詢出這兩站之間在換乘次數(shù)最少情況下的最優(yōu)的線路，可以采用遞歸分層搜索的方法，將不同的情況分類(lèi)，給出各自的實(shí)現(xiàn)算法，并在最原始算法的基礎(chǔ)上增加條件，一次次的遞歸搜索，最終搜索出滿足給定條件假設(shè)的最優(yōu)路徑，其具體算法描述如下：</p><p>　?、泡斎肫鹗脊徽军c(diǎn)A和終點(diǎn)公交站點(diǎn)B；</p><p>　?、扑阉鞒鼋?jīng)過(guò)A和B的所有公交線

20、路，并將其分別存入StartNode和EndNode中；</p><p>　?、菍?duì)兩數(shù)組中的元素進(jìn)行比較，如果存在相同的公交線路即StartNode[i]=EndNode[j]，則將此公交線路打印輸出，結(jié)束算法。此時(shí)說(shuō)明A和B之間存在著一條可以直達(dá)的公交線路：</p><p>　?、葘⒔?jīng)過(guò)A、B的所有公交線路與這些公交線路所包含的站點(diǎn)建立連接矩陣CompareA和CompareB，矩陣中的

21、值為與公交線路對(duì)應(yīng)的站點(diǎn)名稱；</p><p>　?、杀容^兩矩陣中的元素CompareA[i，j]、CompareB[m，n],若存在這樣的i、j、m、n滿足CompareA[i,j]=CompareB[m,n],說(shuō)明在起始站和終點(diǎn)站之間存在著換乘一次的線路，CompareA[i,j]即為換乘站點(diǎn)，并且該線路是連接起始站和終點(diǎn)站的滿足條件的路線，輸出結(jié)果：</p><p>　?、视妙?lèi)似于第

22、二步的方法，找出經(jīng)過(guò)CompareA中任意元素CompareA[i,j]的所有的公交線路及其所包含的站點(diǎn)數(shù)，建立CompareA[i,j]的線路與站點(diǎn)之間的矩陣，將其存放到數(shù)組RCompareA中；</p><p>　?、藢?shù)組RCompareA與CompareB中的數(shù)組元素RCompareA[i,j]、CompareB[m,n]相比較，若存在合適的值，使得RComoareA[i,j]=CompareB[m,n]

23、,說(shuō)明在A和B之間存在換乘二次的線路，RComoareA[i,j]，CompareB[m,n]即為換乘站點(diǎn)，輸出結(jié)果：</p><p>　　5.1.2、模型求解</p><p>　　1) S3359→S1828 </p><p>　　我們?cè)谵D(zhuǎn)乘次數(shù)盡量最少的前提下共搜索出有效路徑8條,并進(jìn)一步結(jié)合出行時(shí)間這個(gè)市民普遍關(guān)注的因素,最終刪選出的最佳線路為：</p

24、><p>　　此線路換乘1次，同時(shí)這是根據(jù)公汽換乘耗時(shí)及相鄰公汽站平均行駛時(shí)間,擇優(yōu)出的耗費(fèi)時(shí)間最少的路線,共經(jīng)45個(gè)公汽站點(diǎn)，所花費(fèi)的時(shí)間為101分鐘。同時(shí)我們計(jì)算出8條線路的乘車(chē)費(fèi)用，均在3-4元的范圍內(nèi)，且所選路線的費(fèi)用也是最少的，為3元，可見(jiàn)在此情況下，費(fèi)用不是影響線路選擇的主要因素，我們只需作適當(dāng)?shù)目紤]即可。與此同時(shí)，我們考慮到此線路由于是最優(yōu)的乘車(chē)方案，屆時(shí)選本線路的觀眾可能較多，加大了對(duì)交通樞紐的壓力，

25、我們推薦如下可行方案，作為備用：</p><p><b>　?、?lt;/b></p><p>　　（時(shí)間：107分/107分 費(fèi)用：3元/3元）</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：113分 費(fèi)用：3元）</p><p><b>　?、?

26、lt;/b></p><p>　?。〞r(shí)間：125分 費(fèi)用：3元）</p><p>　　2) S1557→S0481</p><p>　　我們就轉(zhuǎn)乘次數(shù)最少為首要目標(biāo)，然后對(duì)篩選出的所有記錄進(jìn)行逐層刪選，根據(jù)已經(jīng)求得的線路的時(shí)間費(fèi)用為參考標(biāo)準(zhǔn)，對(duì)明顯比該標(biāo)準(zhǔn)耗時(shí)多的線路，有時(shí)是一個(gè)系列，進(jìn)行逐次排出，最后篩選剩一條最佳乘車(chē)線路，其線路為：</p>

27、<p>　　此線路共換乘2次，出行耗時(shí)為106分鐘，乘車(chē)費(fèi)用為3元，共經(jīng)32個(gè)公汽站點(diǎn)，為費(fèi)用最少的路線之一，是一條既快又經(jīng)濟(jì)的乘車(chē)方案。此外我們推測(cè)，一般乘車(chē)耗時(shí)較少的路線的乘車(chē)費(fèi)用也相對(duì)較少，因?yàn)檐?chē)費(fèi)在一定程度上是與所經(jīng)站點(diǎn)的個(gè)數(shù)成正相關(guān)。據(jù)此，我們快速排除了一些情況，讓搜索區(qū)間逐步縮小。此外乘車(chē)費(fèi)用對(duì)線路選擇并不起很大的作用，不同方案間的差距在1元，幾乎可以忽略。同理，出于類(lèi)似問(wèn)題的考慮，我們給出如下備選方案：</

28、p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：115分 費(fèi)用：3元）</p><p><b>　?、?</b></p><p>　?。〞r(shí)間：130分/133分/130分/130分 費(fèi)用：3元/3元/3元/3元）</p><p><b>　　③</

29、b></p><p>　?。〞r(shí)間：133分 費(fèi)用：3元）</p><p><b>　?、?lt;/b></p><p>　　（時(shí)間：136分 費(fèi)用：4元）</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：136分/130分 費(fèi)用：4元/4元）</p&

30、gt;<p>　　3) S0971→S0485</p><p>　　可行路徑有多條，其中換乘次數(shù)最少為2次，搜索并逐步篩選得到最佳線路為：</p><p>　　此線路的出行耗時(shí)為128分鐘，乘車(chē)費(fèi)用為3元，共經(jīng)由41個(gè)公汽站點(diǎn)，是滿足換乘次數(shù)最少，且花費(fèi)時(shí)間最短，又非常經(jīng)濟(jì)的最佳選擇，比起其他的線路來(lái)具有一定的優(yōu)勢(shì)，不會(huì)給公眾帶來(lái)因換乘引起的麻煩，同時(shí)減少了誤時(shí)的可能。<

31、;/p><p>　　在滿足最小換乘次數(shù)的前提下，我們進(jìn)一步考慮出行耗時(shí)，提供如下可行方案，作為處理偶然事件調(diào)劑之用：</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：131分 費(fèi)用：3元）</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：1

32、34分 費(fèi)用：3元）</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：134分 費(fèi)用：3元）</p><p><b>　　④</b></p><p>　?。〞r(shí)間：134分 費(fèi)用：3元）</p><p>　　4）S0008→S0073</p>

33、<p>　　從S0008出發(fā)抵達(dá)S0073轉(zhuǎn)乘次數(shù)為1次的有多條線路，我們以途徑公汽站點(diǎn)最少為選擇目標(biāo)，通過(guò)反復(fù)比較，尋找到的最佳乘車(chē)線路為：</p><p>　　此線路出行最短耗時(shí)為83分鐘，乘車(chē)費(fèi)用為2元，共經(jīng)過(guò)26個(gè)公汽站點(diǎn)。在搜索得到的線路中還有與此線路耗時(shí)同樣少的線路，但基于此線路的本身特色，我們選用此線路為最佳方案。因?yàn)閺墓維2263到公汽站S0073,我們可以選擇 L057（上）,L2

34、82（下），L345(上)三條線路中的一條，其中如果選擇前兩條線路將多耗時(shí)3分鐘，但考慮到因?yàn)榇司€路途徑的公汽站最少，也就是說(shuō)乘車(chē)花費(fèi)的時(shí)間在一定程度上也是最少的，會(huì)受到公眾的青睞，但考慮到實(shí)際情況，經(jīng)過(guò)此線路的車(chē)次畢竟有限，過(guò)大的人流量會(huì)給交通帶來(lái)很大的壓力，我們應(yīng)給予多種選擇的方案，讓出行者根據(jù)自己的需要自行選擇，并在一定程度上降低交通不暢的可能。所以相比耗時(shí)相同的路線但并無(wú)可供選擇的余地的線路，即靈活性不高的線路，我們選擇了本條線

35、路。</p><p>　　此外，我們把其它能較好的滿足轉(zhuǎn)乘次數(shù)及出行時(shí)間這兩個(gè)優(yōu)先條件的線路設(shè)為推薦線路，線路如下：</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：88分 費(fèi)用3元）</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：8

36、8分 費(fèi)用：3元）</p><p>　　5）S0148→S0485</p><p>　　從S0148到S0485轉(zhuǎn)乘次數(shù)最少為2次，尋找途徑總站數(shù)最小的為最優(yōu)路徑，得出的最佳選擇線路為：</p><p>　　此線路出行時(shí)間為106分鐘，乘車(chē)花費(fèi)為3元，共經(jīng)由32個(gè)公汽站點(diǎn)，該線路省時(shí)、經(jīng)濟(jì)，是綜合所有線路中最佳的一條。另外，我們?cè)僭诳尚新肪€中篩選出交通阻抗較小的線路

37、，并作為備選線路，使出行者的選擇有一定的伸縮性，以滿足不同公眾的需求，除最佳線路外的推薦線路如下：</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：109分 費(fèi)用：3元）</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：121分 費(fèi)用：3元）</p>

38、;<p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：121分 費(fèi)用：3元）</p><p>　　6）S0087→S3676</p><p>　　從起點(diǎn)站S0087到終點(diǎn)站S3676最小換乘次數(shù)為1次，滿足此最少換乘的條件下，可行路徑只有2條，我們?cè)賰?yōu)先考慮途徑站點(diǎn)數(shù)最少的情況，最后得出最佳選擇線路為：</p>

39、<p>　　此線路的出行時(shí)間為65分鐘，路費(fèi)為2元，共經(jīng)過(guò)20個(gè)公汽站點(diǎn)，出行者可以快捷、方便的前往場(chǎng)館。同理，為了解決可能的人流過(guò)密的情況，我們又提供如下線路，予以緩解交通擁擠的狀況。線路如下：</p><p><b>　?、?lt;/b></p><p>　?。〞r(shí)間：71分 費(fèi)用：2元）</p><p><b>　　5.2

40、、問(wèn)題二</b></p><p>　　5.2.1、分類(lèi)枚舉篩選模型</p><p>　　考慮公交線路和地鐵線路的情況下找出乘客出行的最優(yōu)路徑，同時(shí)要滿足假設(shè)的條件即換乘次數(shù)最少。在最優(yōu)路徑的選取過(guò)程中采用分層討論的方法，在換乘次數(shù)的限制下，將具體的情況分別作出討論，最終得到滿足要求的路徑。算法具體描述如下：</p><p>　?、泡斎肫鹗脊徽军c(diǎn)A和終點(diǎn)

41、公交站點(diǎn)B；</p><p>　?、扑阉鞒鼋?jīng)過(guò)A和B的所有公交線路，并將其分別存入StartNode和EndNode中；</p><p>　?、菍⒌罔F站與所對(duì)應(yīng)的公交站建立相對(duì)應(yīng)的二維數(shù)組DNode,其中DNode[i][j]表示站點(diǎn)i對(duì)應(yīng)的一公交站點(diǎn)；</p><p>　?、葘⒌罔F線路T1,T2與經(jīng)過(guò)的地鐵站點(diǎn)建立兩個(gè)一維數(shù)組T1Node,T2Node中,T1No

42、de[i]、T2Node[j]分別表示T1、T2線路中地鐵站i,j；</p><p>　?、杀容^T1Node,T2Node中的元素，若存在合適的值使得T1Node[i]=T2Node[j]，則將兩數(shù)組中的公共元素存入數(shù)組Same中；</p><p>　?、嗜魸M足（A= =DNode[i][j] ＆＆B= = DNode[m][n]）！=0，說(shuō)明通過(guò)A、B站點(diǎn)可以換乘地鐵，返回i,m的值，i

43、,m的值即為通過(guò)A、B可以轉(zhuǎn)乘的地鐵站點(diǎn)； </p><p>　　⑺將i,m的值分別與T1Node,T2Node中的元素進(jìn)行比較，若在T1Node、T2Node中存在( T1Node[i]=i＆＆T2Node[j]=m)!=0,則說(shuō)明A、B之間要換乘一次，</p><p>　　換乘的地鐵站點(diǎn)是數(shù)組Same中的元素,找出換乘一次的所有地鐵線路，回溯每條地鐵線路計(jì)算每條路徑的總站數(shù)，確定總站數(shù)

44、最小的為最優(yōu)路徑，輸出結(jié)果；否則A、B之間存在一條可以直達(dá)的地鐵線路，</p><p>　　該線路即為兩點(diǎn)之間的最優(yōu)路徑，返回結(jié)果；</p><p>　?、倘?A=DNode[i][j]∣∣B=DNode[i][j])＆＆(</p><p>　　))!=0，說(shuō)明A、B中有且只有一個(gè)與地鐵站直接相通。不妨設(shè)B與地鐵站直接相通（A的情況與此相類(lèi)似），返回該站點(diǎn)i；<

45、;/p><p>　?、蛯ompareA和DNode中的元素進(jìn)行比較</p><p>　　(i)若滿足(CompareA[i]＆＆DNode[j][k])!=0,將公共元素對(duì)應(yīng)的的地鐵站j存入暫態(tài)數(shù)組A中，將i與該數(shù)組中的元素進(jìn)行比較，若滿足i＆＆A[j]!=0,則在A和B之間存在換乘一次的線路</p><p>　　否則A和B之間換乘兩次</p><

46、p>　　(ii)若(CompareA[i]＆＆DNode[j][k])=0，將經(jīng)過(guò)B的地鐵站點(diǎn)對(duì)應(yīng)的公交站點(diǎn)存入暫態(tài)數(shù)組B中，將CompareA[i]、B[j]與任意公交線路進(jìn)行比較，并與二維數(shù)組DNode中的元素相比較，若存在相等的元素，則返回與之相對(duì)應(yīng)的地鐵站名Ni，Nj，若滿足Ni=Nj，說(shuō)明i和j之間不用通過(guò)公汽線路到達(dá)，可以通過(guò)地鐵到達(dá)，此時(shí)A和B之間存在一條一次換乘的線路，</p><p>　　

47、若Ni≠Nj，說(shuō)明A和B之間存在一條換乘兩次的線路即：</p><p>　　否則A、B之間不存在通路。最終找出滿足要求的所有線路，計(jì)算線路中包含的站點(diǎn)數(shù)，站點(diǎn)數(shù)少的即為最優(yōu)路徑；</p><p>　?、稳绻?A=DNode[i][j] ＆＆B=DNode[i][j])=0 說(shuō)明A、B均有地鐵與它們相通。將滿足CompareA[m][n]= DNode[i][j]的元素對(duì)應(yīng)的地鐵站點(diǎn)存入暫態(tài)

48、數(shù)組A中，滿足CompareB[m][n]= DNode[i][j] 的元素對(duì)應(yīng)的地鐵站點(diǎn)存入暫態(tài)數(shù)組B中；</p><p>　?、先?A[i]T1Node(T2Node)＆＆B[j] T1Node(T2Node))!=0,則在A和B之間存在換乘兩次的線路</p><p>　　返回站點(diǎn)i、j以及換乘線路；否則其換乘次數(shù)超過(guò)2次，不符合假設(shè)的情況；找出所有線路中站點(diǎn)最少的，該線路即為滿足要

49、求的最優(yōu)路徑；</p><p>　　5.2.2、模型求解</p><p>　　根據(jù)常理我們可知，在出行費(fèi)用相差不大的情況下，公眾會(huì)傾向于選擇乘車(chē)時(shí)間較短的路線，可以說(shuō)時(shí)間的權(quán)重比起金錢(qián)來(lái)更大，因?yàn)槿绻s不上精彩的比賽，即使少花幾個(gè)人民幣也并沒(méi)有什么意義。因而我們?cè)趽Q乘次數(shù)最少的基礎(chǔ)上，并鑒于時(shí)間更少的考慮對(duì)某些線路進(jìn)行篩選，在搜索中發(fā)現(xiàn)，前5對(duì)站點(diǎn)中，任意起始站或終點(diǎn)站均無(wú)地鐵直接相通，根

50、據(jù)問(wèn)題2的算法可知，在此種情況起始站→終點(diǎn)站的換乘線路模式為：</p><p>　　將此模式下計(jì)算的結(jié)果與問(wèn)題1的結(jié)果進(jìn)行比較，在滿足假設(shè)條件即換乘次數(shù)最少的前提下，分析得到問(wèn)題1中關(guān)于站點(diǎn)對(duì)⑴S3359→S1821、⑶S0971→S0485、⑷S0008→S0073的最佳線路比問(wèn)題2中相應(yīng)站點(diǎn)對(duì)按照換乘線路模式得出的結(jié)果耗時(shí)更少、更優(yōu)化；同時(shí)在換乘次數(shù)相同的情況下，盡量不去考慮由地鐵轉(zhuǎn)乘公汽的乘坐方式，并優(yōu)先考

51、慮耗時(shí)較少的線路，可以得出⑵S1557→S0481、⑸S0148→S0485的最佳線路。</p><p>　　同時(shí)考慮公汽與地鐵線路的情況下，得出6對(duì)起始站→終點(diǎn)站之間的最優(yōu)路徑分別為：</p><p>　?、賁3359→S1821</p><p>　　耗時(shí)：101分鐘，費(fèi)用：3元，途徑站點(diǎn)總數(shù)：45個(gè)</p><p>　?、赟1557→S0

52、481</p><p>　　耗時(shí)：106分鐘，費(fèi)用：3元，途徑站點(diǎn)總數(shù)：32個(gè)</p><p>　?、跾0971→S0485</p><p>　　耗時(shí)：128分鐘，費(fèi)用：3元，途徑站點(diǎn)總數(shù)：41個(gè)</p><p>　?、躍0008→S0073</p><p>　　耗時(shí)：83分鐘，費(fèi)用：2元，途徑站點(diǎn)總數(shù)：26個(gè)<

53、/p><p>　?、軸0148→S0485</p><p>　　耗時(shí)：106分鐘，費(fèi)用：3元，途徑站點(diǎn)總數(shù)：32個(gè)</p><p>　?、轘0087→S3676</p><p>　　我們查找已有的數(shù)據(jù)文件發(fā)現(xiàn)S0087與S3676均有地鐵通過(guò)，并且是同一條地鐵，根據(jù)我們所建立的分類(lèi)枚舉模型可知在S0087與S3676之間存在一條直達(dá)的地鐵線路即換

54、乘次數(shù)為0次，在選擇公交線路時(shí)首要滿足的條件是換乘次數(shù)最少，因而該線路為此條件下這兩點(diǎn)之間的最優(yōu)路徑：</p><p>　　此種出行方式耗時(shí)33分鐘，費(fèi)用為3元，經(jīng)過(guò)的地鐵站數(shù)為10站。</p><p><b>　　5.3、問(wèn)題三</b></p><p>　　5.3.1、擬蟻群搜索模型</p><p>　　由于第三問(wèn)增加

55、了步行換乘的因素，使問(wèn)題更加復(fù)雜，在綜合考慮前兩問(wèn)的轉(zhuǎn)乘次數(shù)最少，出行時(shí)間又盡可能短的前提下，我們模擬螞蟻捕食傳遞信息的生物機(jī)理，考慮到用步行換乘公汽或地鐵的數(shù)據(jù)量太大，必須通過(guò)某種算法來(lái)逐步縮小搜索范圍，通過(guò)人工螞蟻在各站點(diǎn)激素信息量的改變搜索最優(yōu)路徑。我們將基于這種思想的模型表述如下：</p><p><b>　?。?）初始化說(shuō)明：</b></p><p>　　把

56、選定有m只螞蟻組成蟻群，每只螞蟻隨機(jī)在SMum中選擇一結(jié)點(diǎn)作為起始點(diǎn)，每條邊初始信息量設(shè)為=h/di,h為一常數(shù)，di=,i=1,2,ti為附錄1中的數(shù)據(jù)。在t時(shí)刻位于i結(jié)點(diǎn)的螞蟻數(shù)為bi(t),殘留在邊上的信息量為T(mén)t（i），于是有T0（i）=h/di,.</p><p>　?。?）轉(zhuǎn)移與更新過(guò)程</p><p>　　人工螞蟻k在i結(jié)點(diǎn)，根據(jù)以下公式選擇下一個(gè)結(jié)點(diǎn)z：</p>

57、<p>　　z= Pk(i,s)</p><p><b>　　邊上信息總量 </b></p><p>　　為權(quán)重系數(shù)，表示殘留信息與距離的相對(duì)重要性，以及應(yīng)根據(jù)公交線路的擁擠程度，公交公司調(diào)度，發(fā)車(chē)情況等綜合考慮。 </p><p>　　Mk為螞蟻k已經(jīng)訪問(wèn)過(guò)的結(jié)點(diǎn)集合 </p><p>　　sMk為

58、所有未經(jīng)過(guò)的結(jié)點(diǎn)Pk（i，s）為k從i到s的概率 </p><p>　　人工螞蟻每次轉(zhuǎn)移到新的結(jié)點(diǎn)時(shí)，所經(jīng)過(guò)邊的信息量就得到修正稱為局部修正 k經(jīng)過(guò)的邊上會(huì)留下信息量</p><p>　　△ Q為事先選定的常數(shù)</p><p><b>　　邊增量 △</b></p><p>　　在m只螞蟻各自的巡游路線中，根

59、據(jù)下列公式找出最優(yōu)的一條路徑進(jìn)行全局更新，公式為：</p><p>　　為事先擬定的0~1的常數(shù) 這里取0.5</p><p><b>　　v為該蟻?zhàn)叩拈L(zhǎng)度</b></p><p>　　5.3.2、蟻群內(nèi)嵌局部搜索算法</p><p>　?。?）輸入起點(diǎn)A,終點(diǎn)B；</p><p>　?。?）判斷

60、直達(dá)線路是否存在,如果,則有直達(dá)線路（換乘次數(shù)j=0）,將滿足條件的各路線放入一集合Straight中，計(jì)算出Straight中各線路包含的站點(diǎn)，并將其放入集合SMum中，并結(jié)束運(yùn)算。若不存在直達(dá)線路，則運(yùn)行（3）；</p><p>　?。?）搜索j+1次換乘情況，將StartNode和EndNode中的相同線路并入集合Straight中,將StartStack并入到SMum中，考慮j+1次換乘中，步行到相鄰站點(diǎn)

61、的情況，采用局部搜索算法：</p><p>　　Step1： 將Straight集合中元素的相鄰元素xi（i是給定的自然數(shù)）并入該集合中：即Straight：=Straight；在Straight中任意選一個(gè)初始的可行點(diǎn)x0,記錄當(dāng)前最優(yōu)解xb:=x0,令P=N(xb)；</p><p>　　Step2：當(dāng)或滿足其他停止運(yùn)算準(zhǔn)則時(shí)，輸出運(yùn)算結(jié)果，停止運(yùn)算；否則，從N（xb）中任意選一集合S

62、，任意選S中的任意元素作為當(dāng)前記錄的最優(yōu)解xn；若f(xn)<f(xb),則xb:=xn,其中f表示該線路所包含的站點(diǎn)個(gè)數(shù),P：=N（xb）；否則，P：=P-S,重復(fù)Step2，得到i+1次換乘的A，B兩點(diǎn)的所有優(yōu)化線路（包含步行的線路）。</p><p>　　由蟻群算法，選定有m只螞蟻組成蟻群，每只螞蟻隨機(jī)在SMum中選擇一結(jié)點(diǎn)作為起始點(diǎn)，目的點(diǎn)作為食物源；每條邊初始信息量設(shè)為：</p>&

63、lt;p>　　=h/di,h為一常數(shù)，,i=1,2</p><p>　　在t時(shí)刻位于i結(jié)點(diǎn)的螞蟻數(shù)為bi(t),殘留在邊上的信息量為T(mén)t（i）；人工螞蟻k在i結(jié)點(diǎn)，根據(jù)概率Pk(i,s)選擇下一個(gè)結(jié)點(diǎn)z, Pk(i,s); 人</p><p>　　工螞蟻每次轉(zhuǎn)移到新的結(jié)點(diǎn)時(shí)，所經(jīng)過(guò)邊的信息量就得到修正,經(jīng)過(guò)的邊上會(huì)留下信息量</p><p><b>

64、;　　Q為事先選定的常數(shù)</b></p><p><b>　　邊增量 </b></p><p>　　在m只螞蟻各自的巡游路線中，根據(jù)公式：,找出最優(yōu)的一條路徑，進(jìn)行全局更新。</p><p>　?。?） j++,j<=2,重復(fù)步驟3；否則,結(jié)束計(jì)算。</p><p><b>　　六、模型的

65、優(yōu)缺點(diǎn)</b></p><p><b>　　6.1、模型的優(yōu)點(diǎn)</b></p><p>　?、旁撃Ｐ秃?jiǎn)單易懂，通過(guò)該模型可以得出在滿足換乘次數(shù)最小的前提下的多條公交線路，可以給乘客提供了更多的選擇機(jī)會(huì)，具有一定的靈活性，同時(shí)也可以滿足出行者的不同需求；</p><p>　?、圃撃Ｐ徒o出了合理的假設(shè)即換乘次數(shù)不得超過(guò)兩次，符合現(xiàn)代人們

66、的出行心理。在第三個(gè)模型中，假定的步行站數(shù)不超過(guò)兩次，也是如此。</p><p>　?、巧鲜瞿Ｐ透鶕?jù)問(wèn)題的特點(diǎn)，通過(guò)添加約束條件對(duì)某些理論的可行線路進(jìn)行篩選，縮小搜索區(qū)間，節(jié)省了時(shí)間。</p><p>　?、饶Ｐ腿M了螞蟻尋覓食物的機(jī)理，根據(jù)實(shí)際情況，對(duì)蟻群算法進(jìn)行改進(jìn)，此算法具有智能性</p><p><b>　　6.2、模型的缺點(diǎn)</b>

67、</p><p>　　該模型的不足之處是從某些起點(diǎn)站到終點(diǎn)站滿足條件的公交線路很多，需要通過(guò)對(duì)其進(jìn)行篩選，進(jìn)而得出滿足乘客需求的線路，在一定程度上增加了人為的負(fù)擔(dān)，而且用于求解模型的算法，不易在短時(shí)間內(nèi)實(shí)現(xiàn)。</p><p>　　七、模型的改進(jìn)與拓展</p><p>　?、艦榱私鉀Q上述缺點(diǎn)，使得乘客查詢線路最終得到的是滿足需求的最優(yōu)路徑，節(jié)約時(shí)間，減少人為的工作量，

68、可以對(duì)其進(jìn)行下列的改進(jìn)：</p><p>　?、僭跐M足條件StartNode[i]=EndNode[j]下得出A和B之間的一條路經(jīng)，此時(shí)算法不提前結(jié)束，應(yīng)繼續(xù)執(zhí)行，采用C語(yǔ)言中的for循環(huán)實(shí)現(xiàn)，知道找到所有的公共線路為止，將各個(gè)線路對(duì)應(yīng)所包含的站點(diǎn)存入一數(shù)組中，同樣采用for循環(huán)算出個(gè)數(shù)組的長(zhǎng)度即為A與B之間經(jīng)過(guò)的站點(diǎn)數(shù)，比較得出站點(diǎn)數(shù)最小的路線，并將其輸出； </p><p>　?、谠诘?/p>

69、出站點(diǎn)A和B之間換乘次數(shù)為一次時(shí)所有公交線路后，調(diào)用該結(jié)果，將其存在一個(gè)二維數(shù)組中，分別求出該二維數(shù)組每行的長(zhǎng)度即站點(diǎn)的個(gè)數(shù)，比較得出站點(diǎn)數(shù)最少的線路，返回該線路；</p><p>　?、垲?lèi)似上述的算法可以對(duì)換乘兩次時(shí)的情況作出改進(jìn)，最終得到滿足條件的最優(yōu)線路；</p><p>　?、瓶紤]到前來(lái)觀看比賽的觀眾來(lái)自五湖四海，他們可能會(huì)利用這次機(jī)會(huì)，希望沿途也能欣賞到北京的文物古跡，重要城市建

70、筑等，可以選擇環(huán)行的車(chē)次。我們可以把問(wèn)題三的模型，適當(dāng)調(diào)整該參數(shù)的權(quán)重。 </p><p>　　由于不知道各公交站點(diǎn)的分布情況，但在實(shí)際問(wèn)題中，可以得到城市的交通圖，這樣會(huì)有利于我們縮小搜索的范圍。</p><p>　　我們?cè)诳紤]該問(wèn)題時(shí)，產(chǎn)生了很多想法?；诘谌齻€(gè)模型的實(shí)用性，我們?cè)陂喿x有關(guān)神經(jīng)網(wǎng)絡(luò)的書(shū)籍時(shí)，有了新的改進(jìn)方向。我們認(rèn)為在（3）的基礎(chǔ)上給出了一個(gè)人工神經(jīng)網(wǎng)絡(luò)彈性模型，通過(guò)交

71、通圖可以給出每一個(gè)站點(diǎn)的坐標(biāo)，構(gòu)成一個(gè)點(diǎn)集，任取兩點(diǎn)分別作為起點(diǎn)和終點(diǎn)，先將兩點(diǎn)用直線段連接，通過(guò)點(diǎn)與點(diǎn)之間的距離，構(gòu)造一個(gè)效用函數(shù)，通過(guò)變形算法，不斷去擬合滿足最優(yōu)化的站點(diǎn)。但是，搜索的結(jié)果不一定滿足換乘次數(shù)的限制要求，我們規(guī)定，如果超過(guò)給定的換乘次數(shù)，就把該線路舍去并繼續(xù)搜索。擬合過(guò)程示意如下：</p><p><b>　　對(duì)上圖的注釋?zhuān)?lt;/b></p><p>

72、　　表示模擬城市交通的站點(diǎn)</p><p><b>　　表示擬合過(guò)程曲線</b></p><p><b>　　表示最初的理想路線</b></p><p>　　表示最終搜索出的出行線路</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1

73、] 陳煥宇，袁貞明，張佳，基于WebIS的公交導(dǎo)乘線路層次性、遞增式選擇算法，Computer Era No.12：26-27，2003。</p><p>　　[2]刑文訓(xùn)，謝金星，現(xiàn)代優(yōu)化計(jì)算方法，北京：清華大學(xué)出版社，1999。</p><p>　　[3]張宗永，孫靜，譚家華，蟻群算法的改進(jìn)及應(yīng)用，上海交通大學(xué)學(xué)報(bào)，36（11）：1564-1567?！?lt;/p><p

74、><b>　　附錄一</b></p><p>　　#include<stdio.h></p><p>　　#define LINES 530//定義公交線路總數(shù)；</p><p>　　#define STATIONS 4000//定義最大站點(diǎn)數(shù)；</p><p>　　int msg[LIN

75、ES][STATIONS];//公交線路所經(jīng)過(guò)的站點(diǎn)數(shù)數(shù)組；</p><p>　　void read();//聲明read()函數(shù)；</p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int a,b;</b></p&g

76、t;<p>　　scanf("起始站：%4d目的站：%4d",&a,&b);</p><p><b>　　bijiao();</b></p><p><b>　　}</b></p><p>　　void read()</p><p><b>

77、;　　{</b></p><p><b>　　FILE *fp;</b></p><p>　　if(!(fp=fopen("file1.txt","r")))</p><p>　　printf("無(wú)法打開(kāi)指定文件！\n");</p><p>　　in

78、t num,i=0,j=0;</p><p>　　char sg;//定義線路站點(diǎn)區(qū)別標(biāo)志；</p><p>　　while(!feof(fp))</p><p><b>　　{</b></p><p>　　fscanf(fp,"%c%d",&sg,&num);</p&

79、gt;<p>　　if('l'==sg||'L'==sg)//線路標(biāo)志；</p><p><b>　　{</b></p><p><b>　　j=0;</b></p><p><b>　　i++;</b></p><p><

80、b>　　}</b></p><p>　　else if('s'==sg||'S'==sg)//站點(diǎn)標(biāo)志；</p><p><b>　　{</b></p><p>　　msg[i][j]=num;</p><p><b>　　j++;</b></

81、p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　puts("開(kāi)始取數(shù)據(jù)...");//以下為讀取數(shù)據(jù)的輸出對(duì)照，可以略過(guò)；</p><p>　　for(i=0;i<LINES;i++)</p><p>

82、;<b>　　{</b></p><p>　　if(msg[i][0])printf("第%d條線路經(jīng)過(guò)的站點(diǎn)：\n",i);</p><p>　　for(j=0;j<STATIONS;j++)</p><p><b>　　{</b></p><p>　　int cfg=0

83、;</p><p>　　if(msg[i][j])</p><p><b>　　{</b></p><p><b>　　cfg++;</b></p><p>　　printf("%d\t",msg[i][j]);</p><p>　　if(!(cfg%10

84、))putchar('\n');</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　putchar('\n');</p><p><b>　　}</b></p><p>　

85、　puts("數(shù)據(jù)讀取完成！\n");</p><p>　　fclose(fp);</p><p><b>　　}</b></p><p>　　void bijiao()</p><p><b>　　{ </b></p><p>　　char X[53

86、0],Y[530];</p><p><b>　　int i,j;</b></p><p>　　int Z[],G[];</p><p><b>　　read();</b></p><p>　　if(msg[i][0]=='a')</p><p><b&

87、gt;　　{</b></p><p><b>　　X[i]='a';</b></p><p><b>　　}</b></p><p>　　if(msg[i][0]=='b')</p><p><b>　　{</b></p>

88、<p><b>　　Y[j]='b';</b></p><p><b>　　}</b></p><p>　　if(X[i]==Y[j])</p><p><b>　　{ </b></p><p>　　Z[i]=msg[i][j];</p&

89、gt;<p>　　if(Z[i]>=1)</p><p><b>　　{ </b></p><p>　　printf("直達(dá)線路：%d",Z[i]);</p><p><b>　　} </b></p><p>　　else break;</p>

90、<p>　　O[i]=X[i][j];</p><p>　　P[j]=Y[i][j];</p><p>　　if(O[i]==P[j])</p><p><b>　　{</b></p><p>　　W[i]=msg[i][j];</p><p>　　if(W[i]>=1)</

91、p><p><b>　　{</b></p><p>　　printf("換乘一次：%d",W[i]);</p><p><b>　　}</b></p><p>　　else break;</p><p>　　R[i]=X[i][j];</p>&

92、lt;p>　　G[j]=Y[i][j];</p><p>　　if(R[i]==G[j])</p><p><b>　　{</b></p><p>　　W[i]=msg[i][j];</p><p>　　if(W[i]>=1)</p><p><b>　　{</b>