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

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

2、所得結果為：S3359→S1828換乘1次，經45個公汽站點，所花費的時間為101分鐘； S1557→S0481，換乘2次，出行耗時106分鐘，乘車費用為3元，共經32個公汽站點；S0971→S0485換乘1次，出行耗時128分鐘，乘車費用為3元，共經由41個公汽站點；S0008→S0073換乘1次，最短耗時83分鐘，乘車費用為2元，共經過26個公汽站點；S0148→S0485換乘2次，出行時間為106分鐘，乘車花費為3元，共經由32個

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

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

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

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

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

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

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

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

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

12、<p>　　⑶優(yōu)先考慮換乘次數(shù)最少的乘車路線，其次考慮出行耗時最少。</p><p>　?、冉ㄖ┕さ茸鳂I(yè)不會影響道路的通行。</p><p>　?、晒卉囋谛旭傔^程中不會因為意外事故而耽誤時間。</p><p><b>　　四、符號的說明</b></p><p>　　L+三位數(shù)字：公汽線路編號格式，如L00

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

14、）：公交線路Lxxx的上行線（xxx為線路編號）</p><p>　　Lxxx（下）：公交線路Lxxx的下行線</p><p><b>　　A：起始公交站點</b></p><p><b>　　B：終點公交站點</b></p><p>　　StartNode：用于存放經過起始站A的所有公交線路，St

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

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

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

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

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

20、路，并將其分別存入StartNode和EndNode中；</p><p>　?、菍蓴?shù)組中的元素進行比較，如果存在相同的公交線路即StartNode[i]=EndNode[j]，則將此公交線路打印輸出，結束算法。此時說明A和B之間存在著一條可以直達的公交線路：</p><p>　?、葘⒔涍^A、B的所有公交線路與這些公交線路所包含的站點建立連接矩陣CompareA和CompareB，矩陣中的

21、值為與公交線路對應的站點名稱；</p><p>　　⑸比較兩矩陣中的元素CompareA[i，j]、CompareB[m，n],若存在這樣的i、j、m、n滿足CompareA[i,j]=CompareB[m,n],說明在起始站和終點站之間存在著換乘一次的線路，CompareA[i,j]即為換乘站點，并且該線路是連接起始站和終點站的滿足條件的路線，輸出結果：</p><p>　?、视妙愃朴诘?/p>

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

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

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

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

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

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

28、p><p><b>　?、?lt;/b></p><p>　　（時間：115分 費用：3元）</p><p><b>　?、?</b></p><p>　　（時間：130分/133分/130分/130分 費用：3元/3元/3元/3元）</p><p><b>　?、?lt;/

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

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

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

32、34分 費用：3元）</p><p><b>　　③</b></p><p>　?。〞r間：134分 費用：3元）</p><p><b>　　④</b></p><p>　?。〞r間：134分 費用：3元）</p><p>　　4）S0008→S0073</p>

33、<p>　　從S0008出發(fā)抵達S0073轉乘次數(shù)為1次的有多條線路，我們以途徑公汽站點最少為選擇目標，通過反復比較，尋找到的最佳乘車線路為：</p><p>　　此線路出行最短耗時為83分鐘，乘車費用為2元，共經過26個公汽站點。在搜索得到的線路中還有與此線路耗時同樣少的線路，但基于此線路的本身特色，我們選用此線路為最佳方案。因為從公汽站S2263到公汽站S0073,我們可以選擇 L057（上）,L2

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

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

36、8分 費用：3元）</p><p>　　5）S0148→S0485</p><p>　　從S0148到S0485轉乘次數(shù)最少為2次，尋找途徑總站數(shù)最小的為最優(yōu)路徑，得出的最佳選擇線路為：</p><p>　　此線路出行時間為106分鐘，乘車花費為3元，共經由32個公汽站點，該線路省時、經濟，是綜合所有線路中最佳的一條。另外，我們再在可行路線中篩選出交通阻抗較小的線路

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

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

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

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

41、公交站點B；</p><p>　?、扑阉鞒鼋涍^A和B的所有公交線路，并將其分別存入StartNode和EndNode中；</p><p>　?、菍⒌罔F站與所對應的公交站建立相對應的二維數(shù)組DNode,其中DNode[i][j]表示站點i對應的一公交站點；</p><p>　?、葘⒌罔F線路T1,T2與經過的地鐵站點建立兩個一維數(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，說明通過A、B站點可以換乘地鐵，返回i,m的值，i

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

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

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

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

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

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

49、求的最優(yōu)路徑；</p><p>　　5.2.2、模型求解</p><p>　　根據常理我們可知，在出行費用相差不大的情況下，公眾會傾向于選擇乘車時間較短的路線，可以說時間的權重比起金錢來更大，因為如果趕不上精彩的比賽，即使少花幾個人民幣也并沒有什么意義。因而我們在換乘次數(shù)最少的基礎上，并鑒于時間更少的考慮對某些線路進行篩選，在搜索中發(fā)現(xiàn)，前5對站點中，任意起始站或終點站均無地鐵直接相通，根

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

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

52、481</p><p>　　耗時：106分鐘，費用：3元，途徑站點總數(shù)：32個</p><p>　?、跾0971→S0485</p><p>　　耗時：128分鐘，費用：3元，途徑站點總數(shù)：41個</p><p>　　④S0008→S0073</p><p>　　耗時：83分鐘，費用：2元，途徑站點總數(shù)：26個<

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

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

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

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

57、<p>　　z= Pk(i,s)</p><p><b>　　邊上信息總量 </b></p><p>　　為權重系數(shù)，表示殘留信息與距離的相對重要性，以及應根據公交線路的擁擠程度，公交公司調度，發(fā)車情況等綜合考慮。 </p><p>　　Mk為螞蟻k已經訪問過的結點集合 </p><p>　　sMk為

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

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

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

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

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

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

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

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

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

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

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

69、出站點A和B之間換乘次數(shù)為一次時所有公交線路后，調用該結果，將其存在一個二維數(shù)組中，分別求出該二維數(shù)組每行的長度即站點的個數(shù)，比較得出站點數(shù)最少的線路，返回該線路；</p><p>　?、垲愃粕鲜龅乃惴梢詫Q乘兩次時的情況作出改進，最終得到滿足條件的最優(yōu)線路；</p><p>　?、瓶紤]到前來觀看比賽的觀眾來自五湖四海，他們可能會利用這次機會，希望沿途也能欣賞到北京的文物古跡，重要城市建

70、筑等，可以選擇環(huán)行的車次。我們可以把問題三的模型，適當調整該參數(shù)的權重。 </p><p>　　由于不知道各公交站點的分布情況，但在實際問題中，可以得到城市的交通圖，這樣會有利于我們縮小搜索的范圍。</p><p>　　我們在考慮該問題時，產生了很多想法?；诘谌齻€模型的實用性，我們在閱讀有關神經網絡的書籍時，有了新的改進方向。我們認為在（3）的基礎上給出了一個人工神經網絡彈性模型，通過交

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

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

73、] 陳煥宇，袁貞明，張佳，基于WebIS的公交導乘線路層次性、遞增式選擇算法，Computer Era No.12：26-27，2003。</p><p>　　[2]刑文訓，謝金星，現(xiàn)代優(yōu)化計算方法，北京：清華大學出版社，1999。</p><p>　　[3]張宗永，孫靜，譚家華，蟻群算法的改進及應用，上海交通大學學報，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//定義最大站點數(shù)；</p><p>　　int msg[LIN

75、ES][STATIONS];//公交線路所經過的站點數(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("無法打開指定文件！\n");</p><p>　　in

78、t num,i=0,j=0;</p><p>　　char sg;//定義線路站點區(qū)別標志；</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)//線路標志；</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)//站點標志；</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("開始取數(shù)據...");//以下為讀取數(shù)據的輸出對照，可以略過；</p><p>　　for(i=0;i<LINES;i++)</p><p>

82、;<b>　　{</b></p><p>　　if(msg[i][0])printf("第%d條線路經過的站點：\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ù)據讀取完成！\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",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>