2007數(shù)模競賽B題-城市公交線路選擇優(yōu)化模型你要的

1、公汽換乘公汽平均耗時： 6 地鐵換乘地鐵平均耗時： 5 地鐵換乘公汽平均耗時： 8 公汽換乘地鐵平均耗時： 6分鐘（其中步行時間 2分鐘） 分鐘（其中步行時間 2分鐘） 分鐘（其中步行時間 4分鐘） 分鐘（其中步行時間 4分鐘）2007B 題：乘公交，看奧運（數(shù)據(jù)有變化）我國人民翹首企盼的第 29 屆奧運會明年 8月將在北京舉行，屆時有大量觀 眾到現(xiàn)場觀看奧運比賽， 其中大部分人將會乘坐公共交通工具 （簡稱公交， 包括 公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交 線路已達 800 條以上，使得公眾的出行更加通暢、 便利，但同時也面臨多條線路 的選擇問題。針對市場需求

2、， 某公司準備研制開發(fā)一個解決公交線路選擇問題的 自主查詢計算機系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)， 其核心是線路選擇的模型與算法， 應(yīng)該從實際情況 出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線 路選擇問題 的一般數(shù)學(xué)模型與 算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站一終到站 之間的最佳路線（要有清晰的評價說明） 。、S376XS2857（2）、S155LS0481 （3）、S1874S2322、S0008S0073（5）、S014IS0485 （6）、S0087S36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知

3、道所有站點之間的步行時間，請你給出任意兩站點之間線路選擇問 題的數(shù)學(xué)模型?！靖戒?1】基本參數(shù)設(shè)定相鄰公汽站平均行駛時間 （包括停站時間 ）： 3 分鐘相鄰地鐵站平均行駛時間 （ 包括停站時間 ） ： 2.5 分鐘公汽票價：分為單一票價與分段計價兩種， 標記于線路后； 其中分段計價的票價 為：020站：1元；2140站：2元；40站以上：3元地鐵票價： 3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合 ?！靖戒?2】公交線路及相關(guān)信息 （見公汽線路信息，對原數(shù)據(jù)文件 B2007data.rar 有少量更改）城市公交線路選擇優(yōu)化模型摘要本文針對城市公交線路

4、選擇問題建立了兩個模型， 一個是基于集合尋線算法 模型，另一個是圖論模型?；诩蠈ぞ€算法模型中，首先固定換乘次數(shù) n ，通過集合論的相關(guān)知識把 確定換乘點的具體位置 , 轉(zhuǎn)化成確定一些集合間的交集，從而建立集合尋線算 法，再根據(jù)集合相關(guān)公式，得到所有可行線路；進一步考慮時間和費用等因素， 對可行線路進行處理比較，得出最佳線路。圖論模型中， 通過圖論的知識將整個北京市交通線路構(gòu)建出一個有向圖， 每 個站點與有向圖的頂點一一對應(yīng)， 同一線路上的相鄰站點對應(yīng)為有向邊， 通過不 同目標（時間、費用）給有向圖進行不同的賦權(quán)，分別將不同目標轉(zhuǎn)化為賦權(quán)有 向圖尋找最短有向路， 根據(jù)最短路徑算法， 得到最佳

5、線路。 最后綜合評價了兩個 模型的優(yōu)缺點。關(guān)鍵詞： 集合尋線算法；最短路算法；換乘點；賦權(quán)有向圖1 問題提出北京將于 2008 年舉行奧運會， 屆時會有從四面八方而來觀看奧運比賽觀眾， 其中大部分人將會乘坐公共交通工具(簡稱公交，包括公汽、地鐵等)出行。隨 著現(xiàn)代化的步伐加快，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達 800 條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問 題。在現(xiàn)實生活中， 公交線路以及其相應(yīng)經(jīng)過的站點非常多且密， 乘客往往難以 知道如何選擇公交線路， 所以針對市場需求以及公交線路選擇上的問題， 某公司 準備研制開發(fā)一個解決公交線路選擇問題的自主查

6、詢計算機系統(tǒng)。該系統(tǒng)的核心在于線路選擇的模型與算法， 應(yīng)該從實際情況出發(fā)， 滿足查詢 者的各種不同需求。根據(jù)附錄 1、附錄 2，解決如下問題：1.僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算 法。并根據(jù)附錄數(shù)據(jù)，利用建立的模型與算法，求出以下6對起始站一終到站之 間的最佳線路。 S3359 S1828 (2) S1557 S0481 (3) S0971 S0485 S0008 S0073 (5) S0148 S0485 (6) S0087 S36762.同時考慮公汽與地鐵線路，解決以上問題。3.假設(shè)知道所有站點之間步行時間，給出任意兩站點之間線路選擇的數(shù)學(xué)模型。2 問題

7、分析為了研制開發(fā)一個解決公交線路最佳選擇 (即乘客在多條公交線路中根據(jù)自 己的需求獲得最適合自己的線路) 問題的自主查詢計算機系統(tǒng)， 只要乘客給出起 點站A和終點站B兩個站點，系統(tǒng)就給出最佳交通線路，使得公眾出行更加通暢、 便利。而問題核心是如何在多條線路選擇中獲得最佳線路。乘客往往不能只乘一輛公交便直達終點， 而是要通過換乘一輛或多輛公交才 能到達終點站， 但若多次換乘公交， 可能導(dǎo)致乘客所花時間及其費用的增加， 更 會給乘客造成不便。 在奧運將在北京舉行的背景下， 我們知道乘客前往觀看奧運 比賽時，主要注重的是能否及時到達， 所以在為乘客選擇線路時， 力求乘坐花費 的時間盡可能少以及路程盡

8、可能短的線路， 同時考慮換乘車輛以及乘車費用盡量 少的最佳線路， 而現(xiàn)實是很難同時滿足上面三個目標的。 為了使問題簡單化， 我 們分別以乘車時間、乘車費用以及換乘次數(shù)為目標函數(shù)，得到各自的較優(yōu)線路， 再通過對比，有效地處理這些線路，最終得出查詢系統(tǒng)給出的結(jié)果。3 模型準備3.1模型假設(shè)1.假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘 （無需支 付地鐵費）；2.假設(shè)所有交通線路都不出現(xiàn)停運或者線路變動；3.假設(shè)公汽的環(huán)行行駛線路是單向的。3.2符號約定c ：相鄰公汽站平均行駛時間（包括停站時間） ， c 3min ；d ：相鄰地鐵站平均行駛時間（包括停站時間） ， d 2.5min

9、；e ：公汽換乘公汽平均耗時， e 5min （其中步行時間 2min ）； f ：地鐵換乘地鐵平均耗時， f 4min （其中步行時間 2min ）； g ：地鐵換乘公汽平均耗時， g 7min （其中步行時間 4min ）； h ：公汽換乘地鐵平均耗時， h 6min （其中步行時間 4min ）； tij ：交通工具與交通工具換乘所需時間；k ：地鐵票價， k 3 元；n ：換乘次數(shù)；Nij ：乘客在可選擇的從起始站到終點站線路中第i 條線路的換乘點 （包括始點和終點），j 0,1,2, ,n 1 , Nio為起點，Mr為終點；Mj：乘客從第j 1換乘點上車到第j換乘點的下車所付的票價，

10、j 1,2, ,n 1 ;Wj ：公交車從第 j 1 換乘點到第 j 換乘點經(jīng)過的站點數(shù)（含第 j 換乘點） j 1,2, ,n 1；C j ：公交車在第 i 線路上從第 j 換乘點到第 j 1 換乘點線路；kj :公交車在第i線路上從第j 1換乘點到第j換乘點經(jīng)過每站所需時間； Tni :只換乘n次乘客從起始站到終點站選擇第i條線路所需要的總時間； Sni :只換乘n次乘客從起始站到終點站選擇第i條線路所需要的總費用。4 基于集合尋線算法的模型4.1 集合尋線算法的建立現(xiàn)實乘客換乘的次數(shù) n 很小，公司在設(shè)計一個城市公交線路時，為了使線路 更合理，一般不會使乘客要通過多次換乘(超過3 次)才

11、到達終點站。則不妨假設(shè)換乘次數(shù) n 0,2 ，n Z 。我們可以看到問題中關(guān)鍵要解決的是找出換乘點 Nij 的具體位置，顯然換乘 點是公交線路的交叉點， 或者說站點至少要有兩條公交線路經(jīng)過。 由于公交線路 不是一條直線段或者有一定幾何規(guī)律的曲線， 所以我們通過代數(shù)的相關(guān)知識， 把 具有同一屬性的站點放入同一集合中， 這樣就把問題轉(zhuǎn)化成代數(shù)問題。 基于此思 想，我們建立以下集合尋線算法：步驟1:找出經(jīng)過終點B站的所有公交線路Bj存放到集合Y Bj | B Bj, 以及這些線路 Bj 經(jīng)過的所有站點存放到集合 Q。步驟2 :找出經(jīng)過起始站A的所有公交線路Ai，存放到集合X Ai | A Ai， 以

12、及這些公交線路 Ai 經(jīng)過的站點存放到集合 P。步驟3:判斷X和Y的關(guān)系：1若X 丫 ，即存在i, j Z，使得A Bj，表示起始站A到終點站B 之間有一條或幾條直達線路， 乘客不必換乘公交車， 算出這些直達線路各自所需 要的時間和票價；通過比較大小，得到該情況下的乘車最少時間Tmin 和最少費用Smin ，以及其相應(yīng)的線路。2若X Y，則說明起始站A與終點站B之間不存在公交車直達的情況，只能通過換乘才能到達終點站 B，則要尋找換乘點。步驟 4：查找公交線路 Ai 與公交線路 Bj 的所有共同站點 a ，存放到集合I a|a A Bj。集合I中的元素是換乘點。步驟 5：判斷集合 I ：1如果集

13、合 I，即乘客可以通過一次換乘就能到達終點站。記錄換乘點及其相應(yīng)線路。2如果集合 I，即乘客不能通過一次換乘到達終點站，則要選取新的起始點。步驟 6：選取新的起始點：從集合P中任取一站點A ( AA )，即遍歷集合P中所有的元素，以站點A代替原來的起始站A。轉(zhuǎn)到步驟2,這樣就能找出所有經(jīng)過兩次換乘的線路。步驟7:通過重復(fù)上面的6個步驟可得經(jīng)過n次換乘的所有可能線路。4.2模型的建立4.2.1 時間及費用計算我們固定換乘次數(shù)n，通過集合尋線算法，得到通過n次換乘的所有可達線 路，再對這些線路進行下面的運算： 從起點站A到終點站B，Ai :經(jīng)過起點站A的第i條公交線路；Bj :經(jīng)過終點站B的第j條

14、公交線路；只通過n次換乘到達可選擇的線路共有U條，設(shè)第i條乘坐線路的換乘點為 Nj , j 0,1, , n 1， Nio為起點，Ni,n i為終點,第i條線路上從第j換乘點到第 j 1換乘點線路為Cij，其途徑的站點數(shù)Wj，j 0,1, m，所付的票價相1)1，2，3，0，3)鄰站點平均行駛時間 kij ，第 j 個換乘點需要的換乘時間為 tij 。 只考慮公汽線路:a.第i線路所需要的總時間：nTnikij Wijniij ijj11)ntij ij j12)ncWij enj1其中，c表示公汽相鄰兩站的平均行使時間，e汽車換乘需要的平均耗時b.第i線路所需要的總費用：其中 , M ij1

15、，1，2，3，nSMniijj15段乘坐單一票價公汽0 Wij 20Wij 404020WijWij0，同時考慮公汽與地鐵線路: a.第i線路所需要的總時間:TninkijWij j12)其中，kije，Cj段乘坐按段收費公汽tijg，h，ntijj1c，Cij 段乘坐汽車 d，Cij 段乘坐地鐵 公汽換乘公汽 地鐵換乘地鐵 地鐵換乘公汽 公汽換乘地鐵3)b.第i線路所需要的總費用:1，3，nMijj1Cij 段乘坐汽車單一票價線 路C ij 段乘坐地鐵Sni4)M ij0 Wij 2020 Wij 40 Cij 段乘坐按段收費汽車Wij40Wij 0同時考慮公汽、a.第i線路所需要的總時間:

16、地鐵和步行時間:1)1，2，3，0，3)nn5）6）Tnikij Wij tijj 1 j 1c，Cij 段乘坐的是汽車 其中， kij d，Cij 段乘坐的是地鐵 v，Cij 段為步行e,公汽換乘公汽f，地鐵換乘地鐵tijij g，地鐵換乘公汽h,公汽換乘地鐵b.第i線路所需要的總費用：nSniM ijj11,Cij 段乘坐汽車單一票價線 路3, Cij 段乘坐地鐵1,0Wij202,20 Wij 40 Cij 段乘坐按段收費汽車3,Wij400, Wij0注意：由于步行不需費用,所以要給個步行線路約束：步行時間不超過 T 。4.2.2目標函數(shù)的確定固定了換乘次數(shù) n ,確立以下目標：1）

17、時間目標：min（Tni）,即找出只通過n次換乘乘車時間最少的最佳線路及 其時間；2） 費用目標：min（SnJ，即找出只通過n次換乘乘車費用最少的最佳線路及 其費用4.2.3最佳線路的處理由于公交線路很多，在同一目標下，乘客可能還有較多條最佳線路的選擇， 那么我們不可能把所有最佳線路給乘客選擇， 乘客也不能接受， 所以我們可根據(jù) 下面幾點進行處理：1） 盡量滿足時間最短的情況下，選擇費用最少的線路；2） 盡量不要把換乘站點安排在熱門站點（即較多線路交叉點，不妨設(shè)最佳 線路大于 5 條時，通過查找經(jīng)過換乘站點的所有交通線路，遍歷所有換乘站點， 記錄每一個站點對應(yīng)的 r ， r 較大就是熱門站點

18、） ；3） 可以隨機抽取幾條給乘客，避免某條線路上過于繁忙；4） 盡量不要把繁忙線路（累加每一條線路上所有站點對應(yīng)的r 得到較大的 的線路為繁忙線路）安排為最佳線路，避免交通阻塞；4.2.4算法的時間復(fù)雜度 由于所選的換乘次數(shù)最多兩次，所以此算法的時間復(fù)雜度為 O（n2）。圖12）同時考慮公汽和地鐵5基于圖論的模型及其算法實現(xiàn)5.1圖論模型的建立以每個站點為頂點，若站點 A到站點B有公交線路并且A與B為相鄰站點， 則連一條A到B有向邊，根據(jù)所給的站點與線路我們建立一個得到一個有重邊的 有向圖D（V,E）。一條公交線路就是D（V, E）的一條有向路。5.1.1以時間為目標的線路模型1 ）僅考慮公

19、汽線路對于有向圖D（V,E），給每條有向邊都賦權(quán)c （相鄰公汽站點行駛時間），若 站點A有n條公汽線路，則把A變成n個點入入,An （相當于增加了 n 1假想 點，換乘公汽線路需要從Ai變?yōu)锳j），A1,A2, , An的每兩頂點都連對稱有向邊， 即這是一個n階雙向完全有向圖（見圖1）,每條邊都賦權(quán)e（公汽換乘公汽耗時）， 于是得到一個賦權(quán)有向圖D（V, E,W）。則任意兩公汽站點之間線路最少時間選擇問題就轉(zhuǎn)化為求D（V,E,W）的對應(yīng)兩頂點的最短有向路問題。對于有向圖D（V,E），給每條公汽線路的有向邊都賦權(quán)C,每條地鐵線路的有向邊都賦權(quán)d,若站點B有m n條公交線路（其中m條公汽線，n條地

20、鐵線）， 則把B變成m n個頂點O1Q2L ,Om； RR, L,R （相當于增加了 m n 1個假想點），邊為m n個頂點都連對稱有向邊，它一個m n階完全雙向有向圖（見圖2）。 O1,O2,L , Om間的邊賦權(quán)e （公汽換乘公汽耗時），R,F2L ,Pn間的邊賦權(quán)f （地鐵 換乘地鐵耗時），O1,O2,L ,Om的每點到P,F2L ,巳的每點的邊賦權(quán)h （公汽換乘地 鐵耗時），P,F2,L ,Pn的每點到O1,O2,L ,Om的每點的邊賦權(quán)g （地鐵換乘公汽耗 時）。得到一個賦權(quán)有向圖H（V,E,W）。則任意兩公汽站點之間線路最少時間選擇問題就轉(zhuǎn)化為求H （V, E,W）的對應(yīng)兩頂點的最

21、短有向路問題。3）同時考慮公交與步行時間A15A3在賦權(quán)有向圖H(V,E,W)中任兩點之間(除去假想點)連接對稱有向邊， 其邊賦權(quán)為v，從而得到一個新的賦權(quán)有向圖J(V, E,W)。則任意兩公汽站點之間線路最少時間選擇問題就轉(zhuǎn)化為求J(V,E,W)的對應(yīng)兩頂點的最短有向路問題。5.1.2以費用為目標的線路模型1)僅考慮公汽的線路對于公交線路有向圖D(V,E)，給所經(jīng)過的同一公汽線路上的最大站點數(shù)n的有向路進行賦權(quán)：若單一票價，則賦權(quán)fo ；若分段計價，則賦權(quán)1,0 n 20fn)2,21 n 40，于是得到一個動態(tài)賦權(quán)有向圖 G(V, E,W)。3,n 41則任意兩公汽站點之間線路最少費用選擇

22、問題就轉(zhuǎn)化為求動態(tài)賦權(quán)有向圖 G(V,E,W)的對應(yīng)兩頂點的最短有向路問題。2)同時考慮公汽和地鐵對于城市公交線路自然圖D(V,E)，給所經(jīng)過的同一公汽線路上的最大站點 有向路進行賦權(quán)：若單一票價，則賦權(quán)fo ；若分段計價，則賦權(quán)1,0 n 20f1(n)2,21 n 40(n為最大站點數(shù))，給所經(jīng)過的同一地鐵線路賦權(quán)f?，于是3,n 41得到一個動態(tài)賦權(quán)有向圖H(V,E,W)。于是任意兩公交站點之間線路最少費用選擇問題就轉(zhuǎn)化為求H(V,E,W)的對應(yīng)兩頂點的最短有向路問題。3)同時考慮公交和步行由于步行是不需要費用的，則在賦權(quán)圖是H(V,E,W)上任意兩點間連上對稱 的有向邊，但其權(quán)為0,顯

23、然費用最少為0,即步行到終點站。顯然是不合理的。 故這里不能用賦權(quán)圖對應(yīng)線路。5.2最短路徑算法 上面模型可以通過如算法實現(xiàn):f(i) minWj f(j), i n 1,2,1步驟1：通過計算式子j(其中n是終點，1f( n) 0是起點，終點的f( n) 0，從終點出發(fā)逐步向起點推算，j是與i相鄰，f(j)為 已知j點到終點的最小線路)，得到最短路。此算法時間復(fù)雜度為：0(n2)步驟2：通過對上面最短路經(jīng)過的站點的搜索和判斷，找出換乘點和換乘次數(shù)。 步驟3：把步驟1最短路的權(quán)值與步驟2換乘目標值相加，得到最終的最短路。6模型的求解 因為乘坐的費用比較少，乘客還是偏重與對時間的選擇，本文下面的

24、求解都 是以時間為目標得到的最佳線路。6.1基于集合尋線算法模型的求解6.1.1僅考慮公汽根據(jù)模型求解出問題中通過模型得到了 6對查詢點都不能通過一條線路直接到達，也得到1, 2次換乘的最佳線路。見下表：S335X S1828的不同線路乘車方 案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次 數(shù)1L436 下行S1784L16732101312L436 下行S1784L21732101313L015下行S2903L027上行S1784L167下行2173324L015下行S2903L027上行S1784L217下行2173325L015下行S2903L201上行S1790L041上

25、行2173326L015下行S2903L201上行S0458L041上行2173327L015下行S2903L201上行S1792L041上行2173328L015下行S2903L201上行S1783L041上行2173329L015下行S2903L201上行S1671L041上行21733210L123上行S2903L027上行S1784L167下行21733211L123上行S2903L027上行S1784L217下行21733212L123上行S2903L201上行S1790L041上行217332S155 S0481的不同最優(yōu)解路線乘車方 案線路一換乘點1線路二換乘點2線路三總站數(shù)總時

26、間總費用換乘次數(shù)1L084下行S1919L189下行S3186L46032106222L363下行S1919L189下行S3186L4603210622S0971 S0485的最佳路線乘車方案線路一換乘點1線路二換乘點2線路總站數(shù)總時間總費用換乘次數(shù)1L013下行S2184L417下行41128312L013上行S1690L140下行S2654L46932106323L013下行S2517L296上行S2480L41732106324L024下行S1690L140下行S2654L46932106325L094上行S1690L140下行S2654L46932106326L119下行S1690L1

27、40下行S2654L46932106327L263下行S1690L140下行S2654L4693210632SOOOIS0073最佳路線乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L159下行S2683L058下行2683212L159下行S0291L058下行2683213L159下行S3614L058下行2683214L159下行S0491L058下行2683215L159下行S2559L058下行2683316L159下行S3315L058下行2683317L159下行S2559L464上行2683318L159下行S0400L474上行2683219L159下

28、行S2633L474上行26832110L159下行S3053L474上行26832111L355下行S2263L345上行26832112L355下行S3917L345上行26832113L355下行S2303L345上行26832114L463下行S2083L057上行26832115L198上行S3766L296上行S2184L345196732S014M S0485的不同最優(yōu)解路線乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L308上行S36L156上行S2210L417下行32106222L308上行S36L156上行S3332L417下行32106223L

29、308上行S36L156上行S3351L417下行3210622S0087 S3676的最佳路線乘車方案線路一換乘點1線路二換乘點2線路三總站數(shù)總時間總費用換乘次數(shù)1L454上行S3496L209下行2065212L021下行S0088L231環(huán)行S0427L462下行124632通過模型得到了 6對查詢點都不能通過一條線路直接到達，換乘一次，兩次的較優(yōu)線路，根據(jù)乘客的不同的需求，確定目標，選擇適合自己的最佳線路。例 如上面從站點S3359到站點S1828，如果乘客不想多次換乘，那么他就可以選擇 換乘一次的兩條線路的一條，如果乘客想盡快到達終點站，那么他可以選擇換乘兩次的10條線路中的一條。6

30、.1.2同時考慮公汽和地鐵我們先算出問題中6對查詢點一定上要一次地鐵的最佳線路見表3:表3乘坐一次地鐵的最佳線路始點T終占八、公汽線路一換乘點地鐵線路地鐵 起點地鐵終占八、公汽線路二換乘點時間費用S3359TS1828線路超過二次換乘，無法提供具體線路S1557TS0481L084 下行S0978T2D32D24L516 上行S0537116.55S0971TS0485L094 上行S0567T1D1D20L417 下行S207999.55S0008TS0073L159 下行S2633T1D13S12L057 上行S060975.55S0144S0485L024 下行S1487T1D2D20L

31、417 下行S2079915S0087TS3676一一T2D27D36一一363再與只考慮公汽的最佳線路進行比較，選擇時間最短的，得到S3354S1828, S1557 S0481, S0008 S0073 只乘坐公汽，S0971HS0485, S014M S0485, S0087 S3676要乘坐地鐵才能獲得最短時間。6.2圖論模型的求解因為根據(jù)此模型得到的結(jié)果，根上面模型基本一致，在此本文就不再贅述， 有興趣的讀者可以通過算法得到。7模型評價7.1基于集合尋點算法的模型的評價基于集合尋點算法的模型所給的查詢系統(tǒng)是固定換乘次數(shù)n基礎(chǔ)上，算出能通過n次換乘的所有線路。再通過對不同換乘數(shù)所得到的

32、這些最佳線路，對這些 線路的時間，費用的分別比較，通過層層的對比篩選排除，通過一些條件對最佳 線路的進行處理，最后乘客可以根據(jù)自己的不同需求進行選擇。其優(yōu)點：模型中緊緊抓住選擇最佳線路問題的突破點一一換乘次數(shù)，通過集合的相關(guān)知識把難點一一換乘點的具體位置的確定，轉(zhuǎn)化成確定一些集合間的交 集，從而把站點，線路與集合中的元素一一對應(yīng)起來，建立起集合尋線算法，再 根據(jù)集合相關(guān)公式，通過線路計算式子，有效地計算出最佳線路，并且考慮一些 因素，如時間等對最佳線路進行處理。 算法中有效的摒棄一些無效站點， 從而大 大減少了計算量和時間，明顯比運用圖論求得最短路要有效的多。 能為查詢者提 供不同換乘次數(shù)下時

33、間與路程最少的最佳線路，以及對于多條最佳線路，查詢系統(tǒng)盡量采用不太熱門的公交線路，隨機地為查詢者提供指定數(shù)目的線路， 避免同 一最佳線路過熱的情況發(fā)生。其缺點：就是此模型只能為查詢者提供換乘次數(shù)較少下的最佳線路， 當換乘 次數(shù)大于三時，模型實現(xiàn)的時間較長。7.2 圖論模型的評價由圖論模型所得的查詢系統(tǒng)， 是以圖論知識中的最短路有向圖為基礎(chǔ)， 對不 同線路經(jīng)過同一站點時， 假設(shè)多個假想點，并將各不同站點之間所需時間作為權(quán)， 對各線路站點賦權(quán)， 分別確定以時間、 費用、換乘為目標轉(zhuǎn)化為尋找有向的完全 圖，并根據(jù)實際情況，建立出動態(tài)賦權(quán)有向圖，得出最佳線路。其優(yōu)點：模型充分利用公交線路其實就是一個有

34、向圖， 而且在比較成熟的最 短路算法基礎(chǔ)上，通過插入換乘時間，得到最佳線路。算法還是比較容易實現(xiàn)。其缺點：模型在引入步行， 求費用最少， 卻不能實現(xiàn)。而且運用最短路算法， 得到不一定是真正意義上的最佳線路，只能是近似最佳線路。8 模型的推廣 建立此模型的思想， 不但能應(yīng)用到現(xiàn)在這種公交線路中， 并能推廣到海、陸、 空多種交通線路之間尋找最優(yōu)線路。 通過實際情況對模型的進行調(diào)整， 模型就能 適應(yīng)更多情況。例如圖論模型中對有向圖的權(quán)進行調(diào)整就能實現(xiàn)不同時間差站點 的最佳線路的選擇。參考文獻1姜啟源，謝金星數(shù)學(xué)模型M（第三版）.北京：高等教育出版社，2003.2孫惠泉. 圖論及其應(yīng)用 M. 北京:,

35、2004.3邊肇祺,張學(xué)工等.模式識別M（第二版）.北京:清華大學(xué)出版社，1999.4蔡自興 ， 徐光祐 . 人工智能及其應(yīng)用 M（ 第二版 ）. 北京 ： 清華大學(xué)出版 社，1996. 袁新生，邵大宏，郁時煉.LINGO和EXCELS數(shù)學(xué)建模中的應(yīng)用M.北京：科學(xué) 出版社，2007.gcl=gcl+1;qq=0;i=i+4;。 &char(Data(i+4)=S分單上下環(huán)程序 附錄 部分程序 %數(shù)據(jù)的初始處理 clc fid=fopen(QCLS.txt,r);Data=fread(fid);len=length(Data);gcl=0;qq=0;for i=1:len-1if char(D

36、ata(i)=L&qq=0gcl=gcl+1; GCLSgcl1=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3);i=i+4;elseif char(Data(i)=L&qq=1for j1=1:length(GCLSgcl3)GCLSgcl4j1=GCLSgcl3length(GCLSgcl3)+1-j1;endGCLSgcl1=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3);elseif char(Data(i)*256+Data(i+1)= x=3;i=i+3;qq=1;s=0;elseif char(D

37、ata(i)*256+Data(i+1)= GCLSgcl2=1;i=i+8;elseif char(Data(i)*256+Data(i+1)= GCLSgcl2=2;i=i+11;elseif char(Data(i)*256+Data(i+1)= x=3;i=i+4;qq=0;s=0;elseif char(Data(i)*256+Data(i+1)= x=4;i=i+4;qq=0;s=0;elseif char(Data(i)*256+Data(i+1)= x=5;i=i+4;qq=0;s=0;elseif char(Data(i)=Ss=s+1;GCLSgclxs=strcat(Data(i),Data(i+1),Data(i+2),Data(i+3),Data(i+4); clci=i+4; end endfor i1=1:520if length(GCLSi1)=5 n=length(GCLSi13); GCLSFi11=GCLSi11; GCLSFi12=GCLSi12;for i2=1:nGCLSFi13i2=GCLSi13n-i2+1;endn=length(GCLSi14);GCLSFi11=GCLSi11;GCLSFi12=GCLSi12;for i2=1:nGCLSFi14i2=GCLSi14n-i2+1;endelseif