圖論結課論文

1、乘公交，看奧運通信學院10級研一8班 學號【摘要】本文要解決的問題是以即將舉行的08年北京奧運會為背景而提出的。人們?yōu)榱四墁F(xiàn)場觀看奧運會，必然會面對出行方式與路線選擇的問題。因此如何快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的關鍵。鑒于公交系統(tǒng)網(wǎng)絡的復雜性，我們沒有采用常規(guī)的Dijkstra算法，而采用了高效的廣度優(yōu)先算法。其基本思想是從經(jīng)過起（始）點的路線出發(fā)，搜尋出轉乘次數(shù)不超過兩次的可行路線，然后對可行解進行進一步處理。為滿足不同查詢者要求，我們對三個問題都分別建立了以時間、轉乘次數(shù)、費用最小為目標的優(yōu)化模型。本文的主要特點在于，所用算法的效率十分顯著。在對原始數(shù)據(jù)僅做簡單

2、預處理的條件下，搜索任意站點間的最優(yōu)路線所需的平均時間不超過0.5秒。另外，本文所建立的模型簡單、所用算法比較清晰，易于程序實現(xiàn)，對公交線路自主查詢計算機系統(tǒng)的實現(xiàn)具有現(xiàn)實指導作用。關鍵字：轉乘次數(shù) 廣度優(yōu)先算法 查詢效率 實時系統(tǒng)一 問題的重述為了迎接2008年奧運會，北京公交做了充分的準備，首都的公交車大都煥然一新，增強了交通的安全性和舒適性，公交線路已達800條以上，使得公眾的出行更加通暢、便利。但同時也面臨多條線路的選擇問題。為滿足公眾查詢公交線路的選擇問題，某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。這個系統(tǒng)的核心是線路選擇的模型與算法，另外還應該從實際情況出發(fā)考

3、慮，滿足查詢者的各種不同需求。需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型算法，求出以下6對起始站到終到站最佳路線。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時考慮公汽與地鐵線路，解決以上問題。二 符號說明：第i條公汽線路標號,i=1,2 10400,當時, 表示上行公汽路線, 當時, 表示與上行路線相對應的下行公汽路線；：經(jīng)過第i條公汽路線的第g個公汽站點標號；：第j條地鐵路線標號

4、, j=1,2；：經(jīng)過第j條地鐵線路的第h個地鐵站點標號；：轉乘n次的路線；：選擇第k種路線的總時間；：選擇第k種路線公汽換乘公汽的換乘次數(shù)；：選擇第k種路線地鐵換乘地鐵的換乘次數(shù)；：選擇第k種路線地鐵換乘公汽的換乘次數(shù)；：選擇第k種路線公汽換乘地鐵的換乘次數(shù)；：第k種路線、乘坐第m輛公汽的計費方式，其中：表示實行單一票價，表示實行分段計價；：第k種路線，乘坐第m輛公汽的費用； ：選擇第k種路線的總費用；：選擇第k種路線，乘坐第m輛公汽需要經(jīng)過的公汽站個點數(shù)；：選擇第k種路線，乘坐第n路地鐵需要經(jīng)過的地鐵站個點數(shù)； ：表示對于第k種路線的第m路公汽的路線是否選擇步行，為0-1變量，表示不選擇步

5、行，表示選擇步行；：對于第k種路線的第n路地鐵的路線是否選擇步行，為0-1變量，表示不選擇步行，表示選擇步行；三 模型假設3.1基本假設1、相鄰公汽站平均行駛時間(包括停站時間)： 3分鐘2、相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鐘3、公汽換乘公汽平均耗時：5分鐘(其中步行時間2分鐘)4、地鐵換乘地鐵平均耗時：4分鐘(其中步行時間2分鐘)5、地鐵換乘公汽平均耗時：7分鐘(其中步行時間4分鐘)6、公汽換乘地鐵平均耗時：6分鐘(其中步行時間4分鐘)7、公汽票價：分為單一票價與分段計價兩種；單一票價：1元其中分段計價的票價為：0 20站：1元2140站：2元40站以上：3元8、地鐵票價：

6、3元（無論地鐵線路間是否換乘）9、假設同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘，且無需支付地鐵費3.2 其它假設10、查詢者轉乘公交的次數(shù)不超過兩次；11、所有環(huán)行公交線路都是雙向的；12、地鐵線T2也是雙向環(huán)行的；13、各公交車都運行正常，不會發(fā)生堵車現(xiàn)象；14、公交、列車均到站停車四 問題的分析在北京舉行奧運會期間，公眾如何在眾多的交通路線中選擇最優(yōu)乘車路線或轉乘路線去看奧運，這是我們要解決的核心問題。針對此問題，我們考慮從公交線路的角度來尋求最優(yōu)線路。首先找出過任意兩站點（公眾所在地與奧運場地）的所有路線，將其存儲起來，形成數(shù)據(jù)文件。這些路線可能包含有直達公交線路，也有可能是

7、兩條公交線路通過交匯而形成的（此時需要轉乘公交一次），甚至更多公交線路交匯而成。然后在這些可行路線中搜尋最優(yōu)路線。對于路線的評價，我們可以分別以總行程時間，總轉乘次數(shù)，總費用為指標，也可以將三種指標標準化后賦以不同權值形成一個綜合指標。而最優(yōu)路線則應是總行程時間最短，總費用最少或總轉乘次數(shù)最少，或者三者皆有之。之所以這樣考慮目標，是因為對于不同年齡階段的查詢者，他們追求的目標會有所不同，比如青年人比較熱衷于比賽，因而他們會選擇最短時間內(nèi)到達奧運賽場觀看比賽。而中年人則可能較傾向于綜合指標最小，即較快、較省，轉乘次數(shù)又不多。老年人總愿意以最省的方式看到奧運比賽。而對于殘疾人士則總轉乘次數(shù)最少為好

8、。不同的路線查詢需求用圖4.1表示如下： 圖4.1 公交線路查詢目標圖經(jīng)分析，本問題的解決歸結為一個求最短路徑的問題，但是傳統(tǒng)的Dijkstra最短路徑算法并不適用于本問題，因為Dijkstra算法采用的存儲結構和計算方法難以應付公交線路網(wǎng)絡拓撲的復雜性,而且由于執(zhí)行效率的問題，其很難滿足實時系統(tǒng)對時間的嚴格要求。為此我們在實際求解的過程中，采用了效率高效得廣度優(yōu)先算法，其基本思路是每次搜索指定點，并將其所有未訪問過的近鄰點加入搜索隊列，循環(huán)搜索過程直到隊列為空。此方法在后文中有詳細說明。五 建模前的準備為了后面建模與程序設計的方便，在建立此模型前，我們有必要做一些準備工作。51數(shù)據(jù)的存儲由于

9、所給的數(shù)據(jù)格式不是很規(guī)范，我們需要將其處理成我們需要的數(shù)據(jù)存儲格式。從所給文件中讀出線路上的站點信息，存入txt文檔中，其存儲格式為：兩行數(shù)據(jù)，第一行表示上行線上的站點信息，第二行表示下行線的站點信息，其中下行路線標號需要在原標號的基礎上加上520，用以區(qū)分上行線和下行線。如果上行線與下行線的站點名不完全相同，那么存儲的兩行數(shù)據(jù)相應的不完全相同，以公交線L009為例：L009:3739 0359 1477 2159 2377 2211 2482 2480 3439 1920 1921 0180 2020 3027 2981L529:2981 3027 2020 0180 1921 1920 3

10、439 3440 2482 2211 2377 2159 1478 0359 3739L529為L009所對應的下行線路。如果下行線是上行線原路返回，那么存儲的兩行數(shù)據(jù)中的站點信息剛好順序顛倒，以公交線路L001為例：L001:0619 1914 0388 0348 0392 0429 0436 3885 3612 0819 3524 0820 3914 0128 0710L521:0710 0128 3914 0820 3524 0819 3612 3885 0436 0429 0392 0348 0388 1914 0619如果是環(huán)線的情況（如圖5.1所示），則可以等效為兩條線路:順時針方

11、向：S1S2S3S4S1S2S3S4；逆時針方向：S1S4S3S2S1S4S3S2。經(jīng)過分析，此兩條”單行路線”線路的作用等同于原環(huán)形路線圖5.1 環(huán)行線路示意圖以環(huán)形公交線L158為例，此環(huán)形路線存儲數(shù)據(jù)如下：L153: 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606L673: 534 2606 2604

12、 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649在這里，L153被看作成上行路線，L673被當成下行路線。這樣對于每條公交線路都可以得到兩行線路存儲信息。52搜尋經(jīng)過每個站點的公交路線處理5.1所得信息，找出通過每個站點的所有公交路線，并將它們存入數(shù)據(jù)文件中。例如，通過搜尋得出經(jīng)過站點S0001的線路和經(jīng)過站點S0002的線路如下：經(jīng)

13、過S0001的線路有：L421經(jīng)過S0002的線路有：L027 L152 L365 L395 L48553統(tǒng)計任意兩條公交線路的相交（相近）站點依次統(tǒng)計出任意兩條公交線路之間相交(相近)的站點，將其存入1040×1040的矩陣A中，但是這個矩陣的元素是維數(shù)不確定的向量，具體實現(xiàn)的時候可以將用隊列表示。例如：公交線路L001與公交線路L025相交的站點為A125=S0619，S1914，S0388，S0348。六 模型的建立與求解61模型一的建立 該模型針對問題一，僅考慮公汽線路，先找出經(jīng)過任意兩個公汽站點與最多轉乘兩次公汽的路線，然后再根據(jù)不同查詢者的需求搜尋出最優(yōu)路線。611 公汽

14、路線的數(shù)學表示任意兩個站點間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分別對應圖6.1的四種情況。該圖中的A、B為出發(fā)站和終點站，C、D、E、F為轉乘站點。圖6.1 公汽路線圖對于任意兩個公汽站點與，經(jīng)過的公汽線路表示為，有；經(jīng)過的公汽線路表示為，有；1）直達的路線（如圖6.1（a）所示）表示為：2）轉乘一次的路線（如圖6.1（b）所示）表示為：其中：SC為，的一個交點；3）轉乘兩次的路線（如圖6.1（c）所示）表示為： 通過以上轉乘路線的建模過程，可以看出不同轉乘次數(shù)間可作成迭代關系，進而對更多轉乘次數(shù)的路線進行求尋。不過考慮到實際情況，轉乘次數(shù)以不超過2次為佳，所以本文未對轉乘三次

15、及三次以上的情形做討論。612最優(yōu)路線模型的建立 找出了任意兩個公汽站點間的可行路線，就可以對這些路線按不同需求進行選擇，找出最優(yōu)路線了:1）以時間最短作為最優(yōu)路線的模型：行程時間等于乘車時間與轉車時間之和。 （6.1式）其中，第k路線是以上轉乘路線中的一種或幾種。2）以轉乘次數(shù)最少作為最優(yōu)路線的模型： （6.2式）此模型等效為以上轉乘路線按直達、轉乘一次、兩次的優(yōu)先次序來考慮。3）以費用最少作為最優(yōu)路線的模型： （6.3式）其中， （6.4式）613模型的算法描述針對該問題的優(yōu)化模型，我們采用廣度優(yōu)先算法找出任意兩個站點間的可行路線，然后搜索出最優(yōu)路線?，F(xiàn)將此算法運用到該問題中，結合圖6.2

16、敘述如下：（該圖中的、表示公汽站點，、表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點到點直達、轉乘一次、轉乘兩次的情況）圖6.2 公交直達、轉乘圖（1）首先輸入需要查詢的兩個站點與（假設為起始站，為終點站）；（2）搜索出經(jīng)過的公汽線路（i=1,2,m）和經(jīng)過的公汽線路(=1,2, ，n)，存入數(shù)據(jù)文件；判斷是與是否存在相同路線，若有則站點與之間有直達路線(如圖6.2中的)，則該路線是換乘次數(shù)最少(換乘次數(shù)等于0)的路線，若有多條直達路線，則可以在此基礎上找出時間最省的路線；這樣可以找出所有直達路線，存入數(shù)據(jù)文件；（3）找出經(jīng)過的公汽線路(如圖6.2中的)中的另一站點和經(jīng)過的公汽線路中

17、的另一站點。判斷與中是否存在相同的點，若存在(如圖6.2中的)則站點與間有一次換乘的路線(如圖6.2中的與)，該相同點即為換乘站點；這樣又找出了一次換乘路線，存入數(shù)據(jù)文件；（4）再搜索出經(jīng)過(如圖6.2中的)線路上除了站點的另一站點(如圖6.2中的)的公汽線路(如圖6.2中的)，找出公汽線路上的其他站點；判斷，如果與經(jīng)過的公汽線路中的其他站點存在相同的點(如圖6.2中的)，則與間有二次換乘的路線(如圖6.2中的、)，該相同點和點是換乘站點；將此二次換乘的路線存入數(shù)據(jù)文件中；（5）對上述存儲的經(jīng)過兩個站點與的不同路線，根據(jù)不同模型進行最優(yōu)路線進行搜索，得出查詢者滿意的最優(yōu)路線。6. 1. 4模型

18、一的求解根據(jù)以上算法和前面建立的模型一，用VC+進行編程（程序見附錄）就可以得出不同目標下的最優(yōu)路線。1） 以耗時最少為目標的最優(yōu)路線起始站S3359到終到站S1828耗時最少為64 min，耗時最少的最優(yōu)路線（轉乘次數(shù)較少，費用較省的路線）有28條(注：表6.1選擇了其中的10條表示)；起始站S1557到終到站S0481耗時最少為106 min，耗時最少的最優(yōu)路線有2條；起始站S0971到終到站S0485耗時最少為106 min，耗時最少的最優(yōu)路線有2條；起始站S0008到終到站S0073耗時最少為67 min，耗時最少的最優(yōu)路線有2條；起始站S0148到終到站S0485耗時最少為106 m

19、in，耗時最少的最優(yōu)路線有3條；起始站S0087到終到站S3676耗時最少為46 min，耗時最少的最優(yōu)路線有12條；其耗時最少的最優(yōu)路線如表6.1所示。表6.1 耗時最少的最優(yōu)路線表起始站公汽線路中轉站公汽線路中轉站公汽線路終到站轉乘次數(shù)所需費用S3359L0535S2903L1005S1784L0687S182823S3359L0535S2903L1005S1784L0737S182823S3359L0123S2903L1005S1784L0687S182823S3359L0123S2903L1005S1784L0737S182823S3359L0652S2903L1005S1784L06

20、87S182823S3359L0652S2903L1005S1784L0737S182823S3359L0844S2027L1005S1784L0687S182823S3359L0844S2027L1005S1784L0737S182823S3359L0844S1746L1005S1784L0687S182823S3359L0844S1746L1005S1784L0737S182823S1557L0604S1919L0709S3186L0980S048123S1557L0883S1919L0709S3186L0980S048123S0971L0533S2517L0810S2480L0937S0

21、48523S0971L0533S2517L0296S2480L0937S048523S0008L0198S3766L0296S2184L0345S007323S0008L0198S3766L0296S2184L0345S007323S0148L0308S0036L0156S2210L0937S048523S0148L0308S0036L0156S3332L0937S048523S0148L0308S0036L0156S3351L0937S048523S0087L0541S0088L0231S0427L0097S367623S0087L0541S0088L0231S0427L0982S36762

22、3S0087L0541S0088L0901S0427L0097S367623S0087L0541S0088L0901S0427L0982S367623S0087L0206S0088L0231S0427L0097S367623S0087L0206S0088L0231S0427L0982S367623S0087L0206S0088L0901S0427L0097S367623S0087L0206S0088L0901S0427L0982S367623S0087L0974S0088L0231S0427L0097S367623S0087L0974S0088L0231S0427L0982S367623S00

23、87L0974S0088L0901S0427L0097S367623S0087L0974S0088L0901S0427L0982S3676232） 以轉乘次數(shù)最少為目標的最優(yōu)路線起始站S3359到終到站S1828的最少轉乘次數(shù)為1次，轉乘次數(shù)最少的最優(yōu)路線（所需時間較短，費用較省的路線）有2條；起始站S1557到終到站S0481的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有2條與耗時最少的最優(yōu)路線相同（表示在表6.1中，下同）；起始站S0971到終到站S0485的最少轉乘次數(shù)為1次，轉乘次數(shù)最少的最優(yōu)路線有1條；起始站S0008到終到站S0073的最少轉乘次數(shù)為1次，轉乘次數(shù)最少的最優(yōu)路線有9

24、條；起始站S0148到終到站S0485的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有3條與耗時最少的最優(yōu)路線相同；起始站S0087到終到站S3676的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有6條與耗時最少的最優(yōu)路線相同；其余轉乘次數(shù)最少的最優(yōu)路線路線如表6.2所示。表6.2 轉乘次數(shù)最少的最優(yōu)路線表起始站公汽線路中轉站公汽線路終到站耗時所需費用S3359L0956S1784L0687S18281013S3359L0956S1784L0737S18281013S0971L0533S2184L0937S04851283S0008L0679S0291L0578S0073832S0008L0679

25、S0491L0578S0073832S0008L0679S2559L0578S0073832S0008L0679S2683L0578S0073832S0008L0679S3614L0578S0073832S0008L0875S2263L0345S0073832S0008L0875S2303L0345S0073832S0008L0875S3917L0345S0073832S0008L0983S2083L0057S00738323）以費用最少為目標的最優(yōu)路線起始站S3359到終到站S1828的最少費用為3元，最少費用的最優(yōu)路線（所需時間較短，轉乘次數(shù)較少的路線）有30條，其中28條路線所需時間為6

26、4 min，轉乘次數(shù)為2次，另外兩條路線所需時間為101 min，轉乘次數(shù)為1次；起始站S1557到終到站S0481的最少費用為3元，最少費用的最優(yōu)路線有2條，所需時間為106 min，轉乘次數(shù)為2次；起始站S0971到終到站S0485的最少費用為3元，最少費用的最優(yōu)路線有3條，其中兩條所需時間為106 min，轉乘次數(shù)為2次，另外一條所需時間為128 min，轉乘次數(shù)為1次；起始站S0008到終到站S0073的最少費用為2元，最少費用的最優(yōu)路線有9條，所需時間為83 min，轉乘次數(shù)為1次；起始站S0148到終到站S0485的最少費用為3元，最少費用的最優(yōu)路線有3條，所需時間為106min，

27、轉乘次數(shù)為2次；起始站S0087到終到站S3676的最少費用為3元，最少費用的最優(yōu)路線有12條，所需時間為46 min，轉乘次數(shù)為2次；621模型二的建立 該模型針對問題二，將公汽與地鐵同時考慮，找出可行路線，然后尋找最優(yōu)路線。對于地鐵線路，也可以將其作為公交線路，本質上沒有什么區(qū)別，只不過乘車費用、時間，換乘時間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公交的轉乘站即可作為兩者的交匯點。因此該模型的公交換乘路線模型與模型一中的基本相同?，F(xiàn)建立模型二下的最優(yōu)路線模型。1）以時間最短的路線作為最優(yōu)路線的模型：可行路線的總時間為乘公交（公汽和地鐵）時間與公汽與地鐵換乘、公汽間、地鐵間換乘時間之和

28、。 （6.5式）其中，第k路線為同時考慮公汽與地鐵的轉乘路線中的一種或幾種。2）以轉乘次數(shù)最少的路線作為最優(yōu)路線的模型： （6.6式）此模型等效為以上轉乘路線按直達、轉乘一次、兩次（包括公交與地鐵間的轉乘）的優(yōu)先次序來考慮。3）以費用最少的路線作為最優(yōu)路線的模型：可行路線的費用為乘公交和地鐵費用的總和。 （6.7式）其中，仍滿足（6.4式）。622模型二的求解 不難發(fā)現(xiàn)，問題一是問題二解的一部分。在問題二中，新產(chǎn)生的最優(yōu)解主要源于在通過換乘地鐵、換乘附近相近站點的路線上，如下圖所示： 從點A到B，圖(a)表示的是通過兩公交線路上相鄰公汽站S1,S2進行一次轉乘；圖(b)表示利用地鐵站進行二次轉

29、乘；圖(c)表示利用另一條公汽路線為中介進行二次轉乘。鐵路線路引入給題目的求解增加了難度，為了形象了解為數(shù)不多的兩條鐵路間的交叉關系，我們通過matlab編程（程序見附錄）作出了兩條鐵路的位置關系圖，如圖6.3所示。圖6.3 T1與T2鐵路位置關系圖注：圖四中的直線表示T1鐵路線，圓表示T2鐵路線，數(shù)值表示站點，例如1表示T1鐵路線上的D1鐵路站，26表示T2鐵路線上的D26鐵路站。此圖與網(wǎng)上查詢到的北京地鐵示意圖（如圖6.4所示）相吻合。圖6.4 北京地鐵示意圖同樣將地鐵線路等效為公交線路得出任意兩個站點間的可行線路，再將目標函數(shù)分別用模型二建立的模型表達式表達，用VC+進行編程（程序見附錄

30、）求得出考慮地鐵情況的最優(yōu)路線。1）以轉乘次數(shù)最少為目標的最優(yōu)路線起始站S0008到終到站S0073的最少轉乘次數(shù)為1次，轉乘次數(shù)最少的最優(yōu)路線有1條；起始站S0087到終到站S3676的最少轉乘次數(shù)為0次，即有直達路線，直達下的最優(yōu)路線有1條；起始站S0148到終到站S0485的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有10條；起始站S0971到終到站S0485的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有20條（注表6.4中羅列其中10條）；起始站S1557到終到站S0481的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有17條（注表6.4中羅列其中10條）；起始站S3359到終到站S18

31、28的最少轉乘次數(shù)為2次，轉乘次數(shù)最少的最優(yōu)路線有2條。2）以耗時最少為目標的最優(yōu)路線起始站S3359到終到站S1828耗時最少為64 min，耗時最少的最優(yōu)路線（轉乘次數(shù)較少，費用較省的路線）有28條(注：表6.1選擇了其中的10條表示)；起始站S1557到終到站S0481耗時最少為109 min，耗時最少的最優(yōu)路線有17條與轉乘次數(shù)最少的最優(yōu)路線相同；起始站S0971到終到站S0485耗時最少為96 min，耗時最少的最優(yōu)路線有20條與轉乘次數(shù)最少的最優(yōu)路線相同；起始站S0008到終到站S0073耗時最少為55 min，耗時最少的最優(yōu)路線有3條；起始站S0148到終到站S0485耗時最少為

32、87.5 min，耗時最少的最優(yōu)路線有10條與轉乘次數(shù)最少的最優(yōu)路線相同；起始站S0087到終到站S3676耗時最少為33 min，耗時最少的最優(yōu)路線有1條與轉乘次數(shù)最少的最優(yōu)路線相同；3） 最少費用的最優(yōu)路線起始站S3359到終到站S1828的最少費用為3元，最少費用的最優(yōu)路線（所需時間較短，轉乘次數(shù)較少的路線）有2條；起始站S1557到終到站S0481的最少費用為3元，最少費用的最優(yōu)路線有17條；起始站S0971到終到站S0485的最少費用為5元，最少費用的最優(yōu)路線有20條；起始站S0008到終到站S0073的最少費用為2元，最少費用的最優(yōu)路線有1條；起始站S0148到終到站S0485的最少費用為5元，最少費用的最優(yōu)路線有10條；起始站S0087到終到站S3676的最少費用為2元，最少費用的最優(yōu)路線有1條；在此種情況下，我們就只考慮可以通過地鐵站換乘的情況，不通過地鐵站的情況即為模型1的求解結果。模型2的求解結果見附件1。八 參考文獻1 344000 溫小文 臧德彥，城市公交信息查詢系統(tǒng)設計初探，江西測繪，第65期，20062 龔劬 圖論與網(wǎng)絡最優(yōu)化算法 重慶大學出版社，20003 1671-4512(2003)Sl-0313 張帥 彭玉青 趙鎮(zhèn) 李志強，螞蟻算法在公交查詢最短路徑求法中的應用，