公交線路模型

1、承諾書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正文引用處和參 考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī) 則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）：B我們的參賽報名號為（如果賽區(qū)設置報名號的話）：所屬學校（請?zhí)顚懲暾娜?/p>

2、）：參賽隊員（打印并簽名）：1.指導教師或指導教師組負責人（打印并簽名）：數(shù)模指導組日期：2011 年8月26日編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：公交查詢系統(tǒng)的研究與設計摘要本文旨在設計一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。問題一，鑒于實際生活中公交路線復雜多樣，我們將不同公交線路抽象化。把公汽 換乘和直達綜合考慮，模型比較復雜，所以我們首先建立公汽直達數(shù)據(jù)庫Q，用戶查詢 時，系統(tǒng)首先查詢Q，得到所有直達車方案。在需要轉(zhuǎn)乘時，針對不同用戶需求，分別 以轉(zhuǎn)乘次數(shù)最少、總耗時最

3、短、總費用最少為目標，量化不同目標為有向賦權圖的不同 權矩陣，始、終點連通為約束建立0-1整數(shù)線性規(guī)劃模型來設計最佳路線。為了能提供多種公交線路備選方案，我們首先使用基于Dijkstra的鄰接算法求解， 得到不同目標下的多種優(yōu)化方案；對于鄰接算法不易求解的多次轉(zhuǎn)乘最優(yōu)方案，我們采 用Lingo軟件直接求得全局最優(yōu)解。綜合方案集（見5.1.6模型表1.1-1.6），其中6條 線路時間最短目標分別為67、102、106、62、105、49（分鐘）。問題二，同時考慮公汽和地鐵系統(tǒng)，首先把各地鐵站點和周圍鄰近的公汽站點集抽 象為同一新站點，同時將兩條地鐵線路抽象化，計算公汽地鐵直達數(shù)據(jù)庫:】二，再結合

4、 地鐵的費用與地汽換乘等待時間把地鐵線與公汽線結合，建立多目標0-1整數(shù)線性規(guī)劃 模型（見5.2.7模型）；對于轉(zhuǎn)乘次數(shù)以2次為分界分別使用鄰接算法和Lingo軟件求解得 出6條線路的全局最優(yōu)解。綜合方案集（見5.2.9模型表2.1-2.6），其中6條線路時間最短 目標分別為65、102、98、56.5、89.5、30（分鐘）。問題三，將步行考慮在內(nèi)，將此系統(tǒng)抽象為最短路問題下的有向賦權圖，并在此基 礎上以換乘次數(shù)最少為主要約束，以總行程時間最短、費用最低為目標，建立多目標0-1 整數(shù)線性規(guī)劃模型，并給出求解的一般步驟與算法。關鍵詞：鄰接算法；有向賦權圖；直達隊列表；分層序列法；疊加有向賦權圖

5、問題的重述為了迎接2008年奧運會，北京公交做了充分的準備，公交線路已達800條以上， 使得公眾的出行更加通暢、便利，但同時也面臨了多條線路的選擇問題。為方便公眾查 詢公交線路，某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。這個系統(tǒng)的核心是線路選擇的模型與算法，另外還應該從實際情況出發(fā)考慮，滿足 查詢者的各種不同需求。需要解決的問題有：僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法。 并根據(jù)數(shù)據(jù)，利用模型算法，求出以下6對起始站到終到站最佳路線。（1）S3359一S1828（2）S1557一S0481（3）S0971一S0485（4）S0008一S00

6、73（5）S0148一S0485（6）S0087一S3676同時考慮公汽與地鐵線路，解決以上問題。又知道了所有站點之間的步行時間，給出任意兩站點之間線路選擇問題的數(shù)學模型。問題的分析本題主要在三種不同情況下，研究任意兩站點之間的線路選擇問題。問題一，在僅考慮公汽線路的情況下，首先要根據(jù)題目給出的公交線路信息數(shù)據(jù)對 每條線路進行抽象化處理。然后由于乘坐公交有直達和轉(zhuǎn)乘兩種情況，為了方便用戶查 詢，我們先要運用MATLAB內(nèi)建元胞結構來建立公汽直達數(shù)據(jù)庫;】，之后再結合有向賦 權圖建立最短路模型來設計需要轉(zhuǎn)乘時的路線。問題二，由于地鐵與鄰近站點可換乘，可將每個地鐵站點及其周邊鄰近的所有公交 站點抽

7、象成一個點處理。對于兩條地鐵線路可按照與問題一相同的抽象方法處理。在此 基礎上按照問題一的思路確定任意兩站點間的最佳方案。問題三，綜合考慮公交和地鐵站點的實際分布情況，人們有時會選擇步行小段距離 之后再轉(zhuǎn)車來節(jié)省時間或減少轉(zhuǎn)車次數(shù)，本問研究此種情況下的出行方案。模型的假設相鄰公汽站平均行駛時間（包括停站時間）：3分鐘。相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘。公汽換乘公汽平均耗時：5分鐘（其中步行時間2分鐘）。地鐵換乘地鐵平均耗時：4分鐘（其中步行時間2分鐘）。地鐵換乘公汽平均耗時：7分鐘（其中步行時間4分鐘）。公汽換乘地鐵平均耗時：6分鐘（其中步行時間4分鐘）。公汽票價：分為單一票

8、價與分段計價兩種；單一票價：1元其中分段計價的票價為：020站：1元2140站：2元40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）。假設同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘，且無需支付地鐵 費。假設各公交車都運行正常，不會發(fā)生堵車現(xiàn)象。假設公交、列車均到站停車。假設始發(fā)終點出入地鐵需要步行4分鐘；符號說明二.：孤:.是否在該有向賦權圖上；:,:站點i一的總乘車時間；三：站點i一的乘車費用；Si :站點；A.:站點*一的直達路線數(shù)；上=:直達線路數(shù)矩陣；二=；： 最少換乘次數(shù)矩陣；/ j :0-1決策變量；/ j :?。╥, j）是否在該路徑上；、:站點i一一 土間是否

9、地鐵換乘地鐵；二.:站點i 一 的乘車時間；三:站點i 一 的乘車總費用；:人為設定參數(shù)，表示乘客可接受的最多換乘次數(shù)；二T2 :總等待時間，總步行時間；Z,=3 :i - 最短直達為公汽（表示乘始發(fā)坐公汽等待3分鐘），等于2為地鐵。模型的建立與求解5.1問題一的模型建立與求解5.1.1圖論抽象化處理模型實際生活中，公交線路復雜多樣，不利于問題的求解，于是我們將三種公汽線路進 行抽象化處理，方法如下：（1）上、下行線原路返回線路這種線路有兩個端點站，在兩個端點之間雙向行車，并且兩個方向上的行車路線相 同，經(jīng)過同樣的站點序列。由于線路的方向不同，將上行線和下行線抽象為兩條線路處 理。如圖所示：S

10、1 S2 S3 S41111（2）線路為環(huán)行線實際情況中環(huán)形路線一般是雙環(huán)，即將環(huán)形路線抽象為順時針和逆時針兩條線路。如圖所示：（3）下行線與上行線經(jīng)過站點不同由于下行線與上行線經(jīng)過站點不同，該種線路顯然可以被抽象為兩條不同線路。如下圖所示:S1 S2 S3 S4 S5 S6 S9S7S85.1.2公汽直達數(shù)據(jù)庫Q的建立在現(xiàn)實生活中，乘客在進行公交路線選擇時，通常會優(yōu)先選擇直達車，那么在查詢 系統(tǒng)內(nèi)部應設有任意兩站點的直達線路表，以方便查詢時快速查詢是否有直達車，若有， 則直接輸出所有直達車輛；若無，再搜索換乘路線。在建立公汽直達數(shù)據(jù)庫Q的時候，由于本題站點較多，若采用通常方式，占的內(nèi)存 較大

11、，所以本文采用MATLAB內(nèi)建元胞結構，當元胞內(nèi)隊列不存在時不占用空間。具體元胞結構設計如下:CellfljCell14008CelI2TlCell2T2CeU230611(24000Cellfa?,!CeU27T2Cell27TSCell27T1003車號耗時（分鐘）費用（元）L053391上圖中Cell27,1008代表公汽直達數(shù)據(jù)庫Q中第27行第1008個元胞（即從站 點S0027到站點S1008的直達公交線路信息），元胞中隊列的每一行代表一輛直達車 信息。5.1.3基于不同目標的有向賦權圖定義_ 由圖論相關知識可將題中所提供的公汽網(wǎng)絡抽象成一個有向賦權圖 號=:三二,號中的每個頂點為每

12、個不同的站點，如果從號中的頂點到有直達路線，那么這兩點之間就用有向邊相連，記做三，方向為從i指向，表示可從值達，相 應的有一個數(shù)稱為該有向邊的權，這樣公汽網(wǎng)絡就抽象為一個有向賦權圖。在 本模型中，賦權圖中的權定義如下：時間:、_、,其分量為.站點-到站點直達時間無直達線路費用:w = :._,其分量為 ：=（PMvj）站點到站點Y的直達費用+oo無直達線路5.1.4最小換乘次數(shù)的確定如果用戶查詢的站點間無直達車輛，則查詢系統(tǒng)需給出換乘方案，此時，我們需要 得知查詢的站點間公交的最小換乘次數(shù)。由公汽直達數(shù)據(jù)庫R我們可得任意兩站點的直達線路數(shù)，由此可構造表示兩兩站點 間直達路線數(shù)目的直達線路數(shù)矩陣

13、上=；如：_，通過矩陣運算可得到任兩站點間換乘線 路數(shù)矩陣，進而得到任兩站點間的最少換乘次數(shù)矩陣二=1二.：.，.，從而可得任兩站間所 需的最少換乘次數(shù)。 直達線路數(shù)矩陣的建立引入直達線路數(shù)矩陣如：_/，N表示所有公汽所經(jīng)過的的站點總數(shù)。矩陣元素己.表示第i個站點到第個站點直達線路數(shù)n,其中，當時為無效路徑，設定值為0, 即：_ fa (i# j)% lO (i = j)最少換乘線路數(shù)矩陣的建立以與表示方陣上的-次幕，為站點K的直達路線數(shù)，則：A?i =A?k1-Akjk=l其中，元素苴.為通過-r.- 1;次換乘從站點一的線路數(shù)。如上=】表示從站點2 到站點3有1條2次換乘路線，其換乘站點可

14、通過運算參數(shù)記錄得到。引入矩陣三=:：-.；，其矩陣元素二: .為使得一頊=。的n的最小值，一日1,8)，即:貝叮矽-二：表示從站點i 一 必要的最少換乘次數(shù)，以矩陣。=表示最少換乘次數(shù) 矩陣，則：C = B 1其中，元素匚.表示從站點i 一必要的最少換乘次數(shù)?；谧钌贀Q乘次數(shù)矩陣二，每對起始站一終到站的最少換乘次數(shù)如下: 表2.0最小換乘次數(shù)表：線路編號123456起始站S3359S1557S0971S0008S0148S0087終到站S1828S0481S0485S0073S0485S3676最少換乘1211215.1.5最短路模型目標函數(shù)的建立(1)換乘次數(shù)最少基于5.1.3建立的有向賦

15、權圖，引入0-1決策變量二.表示孤:)是否在起點與終 點的路徑上，則=p 弧(i, j)在站點片到站點M的路徑上氣=。其他情徂若站點了.與站點可通過轉(zhuǎn)乘到達，則由站點到站點匚之間換乘次數(shù)為經(jīng)過的總孤 數(shù)減1，即換乘次數(shù)最小可表示為：(2)行程總時間最短基于5.1.3建立的有向賦權圖，行程總時間最短表示為:(3)行程總費用最少設表示i 一 車輛票價屬性，則=(1表示單一票制1元% =(2分段計價設s：.表示i一，所過站數(shù)，那么1一，直達費用權* f _表示為:_ 1% = 2司 E 1,20Plj = 1 2 qSj = 27sbE 21,400 鬼=可 E 4L H行程總費用最少可表示為：Mi

16、n PijXLj(li)EE約束條件的建立換乘次數(shù)約束基于對換乘次數(shù)最少這一目標的分析，可得在有向賦權圖中換乘次數(shù)表達式，以c表 示乘客所能接受的最大換乘次數(shù)，則換乘次數(shù)約束可表示為：CMkEc 0, +oo),且為整數(shù)在實際應用中，查詢系統(tǒng)中的:值可由查詢用戶自己設定。(2)最短路起止點約束由于號為有向圖，則其中頂點分為“起點”、“中間點”、“終點”三類，對于起點只C（i=，）G = e）i # s,司有出的邊而無入的邊，對于中間點既有入的邊也有出的邊，對于終點只有入的邊無出的 邊。若求頂點s-e的最短路徑，以二.表示進入第個頂點的邊，以二.:表示出第個頂點的 邊，則SB中的三類點約束可表示

17、為：j=lj=l(Lj)eE(ij)EE模型的建立基于以上部分，建立多目標最短路模型0-1規(guī)劃表達式如下(s為起點，e為終點):Zssi -1 -c(tjl) EEAA( 1(i=s)乩Xjj - y XL = J% = 3行程總費用最少可表示為（正常票價-地鐵換乘免費）：的。耳跖一 3衣亦現(xiàn)缸上=*1 = 131213約束條件的建立（1）換乘次數(shù)約束基于對換乘次數(shù)最少這一目標的分析，可得在有向賦權圖中換乘次數(shù)的表達式，以 表示乘客所能接受的最大換乘次數(shù)，則換乘次數(shù)約束可表示為：X-1 -c)EEce 0,8)且為整數(shù)從實際出發(fā)，查詢系統(tǒng)中的c值可由查詢用戶自己設定，當最小換乘次數(shù)小于二.時，

18、 輸出無解。最短路起止點約束由于乏為有向圖，則其中頂點分為“起點”、“中間點”、“終點”三類。對有向 圖而言，若求頂點s - m的最短路徑，以二.表示進入第，個頂點的邊，以二.表示出第個 頂點的邊，則s - m中的三類點約束可表示為：V V I恥X *=己與*j=ij=i(1 s, ej地鐵間換乘約束站點i - *間是否地鐵換乘地鐵，使用丁七表示，那么丁七與走的路徑上.需要滿足：玨 + Yjk 三 2Yijk (Lj，k) EE； =2地鐵轉(zhuǎn)地鐵情況只可能在D12與D18轉(zhuǎn)乘，故換乘總次數(shù)不能夠大于2：$ Yijk2 Zi?Zjk=2第 kkE 0-1規(guī)劃模型的建立由和可得該模型的表達式：Mi

19、n yii - 1國Min T1 + T2+烏玲Min 島外- 業(yè) (LjJc)EE； q缸矣二31 j 二 DIM 18(i=s)-1 (i= e)% E 04ziizjk = 2zzjk = 2(Lj)*tiJ.kJeE1zij-zjk = 2模型說明：換乘次數(shù)約束，表示轉(zhuǎn)乘次數(shù)應在乘客所能接受的最多轉(zhuǎn)乘次數(shù)。最短路規(guī)劃中的起點，終點約束，其中m為起點，日為終點。5.2.6最短路模型的求解模型的評價方法一、基于數(shù)據(jù)庫您與Dijkstra算法的“鄰接算法”求解此模型能夠求解出轉(zhuǎn)乘次數(shù)不超過兩次的所有可行方案，設計方案的速度較快，人 們可依據(jù)自己的不同需求選擇出行方案，故模型實用性較強；但本模

20、型還存在一定的局 限性，一般不用于轉(zhuǎn)乘次數(shù)超過兩次的情況。方法二、使用Lingo軟件求解無轉(zhuǎn)乘次數(shù)限制的方案（針對不同目標分別求解）上述最優(yōu)化模型規(guī)模較大，但是通過模型分析章節(jié)抽象，模型所有約束與目標都已 經(jīng)線性化，所以可采用Lingo軟件嚴格按照0-1模型求解。此方法在不限制最小轉(zhuǎn)乘數(shù) 時可以求得全局最優(yōu)解。模型的結果表2.1 一線S3359S1828部分出行方案列表：求解方法轉(zhuǎn)乘總時 間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費 用Lingo/鄰接1104S1784-L436L167-3鄰接1104S1784-L436L217-3鄰接1110S1241-L436L167-3鄰接1140S236

21、4-L469L217-3Lingo465S2903,D12,D37,S1671L15,L201,T02,L428,L417鄰接267S3697S1784L484L485L1673鄰接267S3697S1784L484L485L2173鄰接267S2027S1784L324L485L1673鄰接273D06S1784L484L485L1673鄰B接279S1842S1671L123L475L0413表2.2二線S1557-S0481部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費 用Lingo31021919,3186,903L84,L189,L91,L2394鄰接21

22、09D20S3186L084L189L4603鄰接2109D20S3186L363L189L4603鄰接2112D20S3186L084L189L4603鄰接2112D20S3186L363L189L4603鄰接2112D20S2424L084L417L2543鄰接2112D20S2424L084L417L3123鄰接2112D20S2424L084L417L4473鄰接2121D20S1402L084L030L4603鄰接2121D20S1402L363L030L4603表2.3三線S0971-S0485部分出行方案列表:求解方法轉(zhuǎn)乘總時 間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費 用鄰；接1

23、131S2184-L013L417-3鄰接1146S2119-L013L395-3Lingo398D01,D15,3351L094,T001,L156,L4176Lingo/鄰接299D01D21L094T001L0515鄰接299D01D21L094T001L1045鄰；接299D01D21L094T001L3955鄰；接299D01D21L094T001L4505鄰；接2124S2324S2482L013L132L4174鄰；接2124S2324S2482L013L242L4174鄰；接2127S3405S2515L013L079L4174表2.4四線S0008-S0073部分出行方案列表

24、:求解方法轉(zhuǎn)乘時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費 用Lingo356.5D15,D12,D25L200,T001,T002,L1035鄰接183D13L159L4742鄰接186S3614L159L0582鄰接186S2083L463L0572鄰接186S3315L159L0583鄰接186S2303L355L3452鄰接258D30D25L150T002L1035鄰B接258D30D25L159T002L1035鄰B接263.5D30D24L150T002L1035鄰B接263.5D30D24L259T002L1035表2.5五線S0148S0485部分出行方案列表:求解方法轉(zhuǎn)乘總時

25、間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費 用Lingo389.5D02,D15,3351L024,T001,L156,L4176Lingo/鄰接290.5D02D21L024T001L0515鄰接290.5D02D21L024T001L1045鄰接290.5D02D21L024T001L3955鄰接290.5D02D21L024T001L4505鄰接290.5D02D21L024T001L4695鄰接2109S0036S2210L308L156L4173鄰接2112S0036D20L308L157L4173鄰接2124S0036S1406L308L157L0453鄰接2124S0036S208

26、2L308L156L0453表2.6六線S0087S3676部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo030-T002-3鄰接033-L231-1鄰接042-L381-15.3問題三的模型建立與求解基于前面的分析公眾出行時除了出行時間最短外，需要考慮的因素還包括轉(zhuǎn)乘次數(shù) 和行程費用。再依據(jù)分層序列法，建立最短路問題的0-1整數(shù)規(guī)劃模型。建立本模型首 先要創(chuàng)建鄰接點矩陣E，需要考慮的兩個賦權值為乘車時間和步行時間，即賦權圖中任 意兩點之間的權值有兩個，即乘車時間W：.和步行時間/.，且都為已知量。令乘車時間 對應的決策變量為二.（0-1變量），步行時間

27、對應的決策變量為匚.（0-1變量）。5.3.1目標函數(shù)的建立：（1）行程總時間最短Min T1+T2+ 2 壇 0再（2）行程總費用最少Min P產(chǎn) 3%5.3.2約束條件的建立（1）最短路約束由于行走路線中任意兩點間只會選擇一種出行方式，因此： 1同時，決策變量還應滿足最短路問題中的主要限制條件，如下：AAf 1（i = s）.（氣 + 環(huán)）一）（理+*）= T。=司j=ij=i（o （i#s,e）（2）換乘次數(shù)約束公眾在考慮出行時間盡量短的同時，也會考慮到換乘次數(shù)給出行帶來的不便。以c表 示乘客所能接受的最大換乘次數(shù)，根據(jù)乘車次數(shù)確定換乘次數(shù)約束可表示為： % - M c（3）地鐵間換乘約

28、束站點i 一 一 k間是否地鐵換乘地鐵，使用Y：-表示，那么丁七與走的路徑孔 需要滿 足：Xii + yjk 企 2Yijk （Lj,k）EE爭辱=2地鐵轉(zhuǎn)地鐵情況只可能在D12與D18轉(zhuǎn)乘，故換乘總次數(shù)不能夠大于2：L Vijk 2 ZirZjk = 2 65.3.3模型的建立根據(jù)問題分析中的目標分析和主要約束分析可建立多目標最短路模型，0-1規(guī)劃表 達式（s為起點，e為終點）：MinMin12 耳聲j+ 3Yjjk珂 M Yijke)=1=#:(Ljk)*%知=2zij 2jk = 2(Lj)擊(LD*(Lj-kJ*zij2jk = 2Kjk 丑 YijkZ *后2氣 + ViM 1 氣

29、E 04% E (0,1)5.3.4模型的求解在公交和地鐵交通網(wǎng)絡系統(tǒng)對應的最短路權值確定的情況下，本模型線性可以考慮 運用Lingo軟件編程求解，針對不同目標分別求解可能比較容易。另外，針對本模型我 們給出一種近似求解的算法。在所有站點之間的步行時間確定的情況下，公眾出行時可以考慮步行小段距離再換 乘車次比較符合實際?；谶@種思想，可以考慮將位置比較接近的站點抽象為一個點。 此時可以根據(jù)問題二站點的抽象方法，將這種點抽象為一個點處理。為方便描述，將公 交和地鐵整個系統(tǒng)描述為公交，算法思想如下：步驟1：輸入起始站點人和目的站點B；根據(jù)輸入的站點進行優(yōu)化，映射入緊鄰站點集A =，、三:, B =

30、 D: ：?；。步驟2：查詢直達隊列表是否有4到8的乘車方案，若有則直接輸出結果；若無，繼續(xù)。步驟3：在公交站點數(shù)據(jù)庫中查出過站點上及緊鄰站點上=Am 的站點-】；，及經(jīng)過站點8及緊鄰站點二：.三的公交線路支： = 】， r-；步驟4：判斷是否有L.i； = & ；，若有一條線路滿足要求，則該公交線路即為最優(yōu)線路 輸出結果；若沒有，繼續(xù)。步驟5：從公交線路數(shù)據(jù)庫中查出經(jīng)過站點上的公交線路L)的站點三:.i E；：.i =1 ： 3 .】二，M =二 , ti：，以及經(jīng)過站點三的公交線路:十：)的站點f =二 3 ，如 n =】1 3，p：o步驟6：判斷是否有E(i,g) = F(g,h)。若有

31、一個站點滿足要求，該站點即為一次換乘站 點。從入站點出發(fā)，在該站點換乘即可以到達站點?？赡苡幸粚蚨鄬痪€路 滿足要求，從中選擇一條距離最短的公交線路即為最優(yōu)線路，輸出結果。若有 幾個站點滿足要求，則先分別求出每一個站點的距離最短的換乘方案，然后選 擇所有方案中距離最短的換乘方案為最優(yōu)線路，輸出結果；若沒有，繼續(xù)。步驟7：從公交站點數(shù)據(jù)庫中查得經(jīng)過三:.i二的公交線路=二 . 從公交 線路數(shù)據(jù)庫中查得線路T：.k；的站點 ；：/ = _ 2 5 . E；- - = 12 5 ,】；。步驟8：判斷是否有二:.k注；=7： 1】；。若有某個站點E滿足要求。則站點E為第二個換乘 站點。從起始站點A經(jīng)過一次換乘（假設換乘點為站點C）,可以到達站點三，從 站點三可以換乘公交車直達目的站點。按照步驟4-6的方法求出從起始站點A到 站點E的一次換乘的最優(yōu)線路，在按照2-3的方法求出從站點三到目的站點的最優(yōu) 線路