公交查詢系統(tǒng)的最佳乘車方案設(shè)計(含程序)

./公交查詢系統(tǒng)的最佳乘車方案設(shè)計摘要本文研究的問題是針對已知的公交線路信息如何設(shè)計出最佳的乘車方案。首先,進行數(shù)據(jù)處理,用excel建立起公交線路矩陣。然后,上網(wǎng)查閱了公交乘客乘車心理分析的資料,得出影響乘客出行的三個主要因素依次為為：換乘次數(shù)、出行時間、出行費用隨后,建立了站點—線路序列模型。利用公交乘客的出行過程抽象為站點—線路的交替轉(zhuǎn)換的思想,從而確定了出行者出行路線的一般數(shù)學(xué)表達式。針對問題一,僅考慮公汽的情況下,以換乘次數(shù)最少為第一目標、出行時間為第二目標、乘車費用為第三目標,建立起多目標最優(yōu)化分層求解模型。并依靠站點—線路序列模型確定的出行線路表達式,采用圖論中計算方法并結(jié)合廣度搜索法經(jīng)matlab編程<見附錄一>得到了公交乘客的最少換乘次數(shù),所經(jīng)過的站點,出行時間、出行費用<見表1>。針對問題二,在問題一的基礎(chǔ)上考慮了地鐵線路,處理的方法是將地鐵線當成特殊的公交線,將地鐵站點當成公交站點并與給定的公交站連接。按照問題一的模型和算法得到乘客的最少換乘次數(shù),出行時間、出行費用<見表2>。針對問題三,在問題二的基礎(chǔ)上考慮了所有站點之間的步行時間,由成人步行速度估算出該時間大小。步行線路與公汽線路相同但每條均有上行和下行。將步行線路矩陣與公交線路矩陣整合后按照問題二的算法得到乘客的最少換乘次數(shù),出行時間、出行費用<見9.2>。最后,建立公交負載模型對前三問的模型進行了改進?？紤]到了實際中公交線路堵車的情況,將堵車線路拆分為兩段新的線路并相應(yīng)改變公交線路矩陣。算法與前三問算法相同,但使得最佳路徑的選擇更加靈活且更符合實際情況。關(guān)鍵詞：分層求解交替序列多目標最優(yōu)化改進廣度搜索法1問題重述1.1問題背景我國人民翹首企盼的第29屆奧運會明年8月將在舉行,屆時有大量觀眾到現(xiàn)場觀看奧運比賽,其部分人將會乘坐公共交通工具〔簡稱公交,包括公汽、地鐵等出行。這些年來,城市的公交系統(tǒng)有了很大發(fā)展,市的公交線路已達800條以上,使得公眾的出行更加通暢、便利,但同時也面臨多條線路的選擇問題。針對市場需求,某公司準備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。1.2需要解決的問題為了設(shè)計這樣一個系統(tǒng),其核心是線路選擇的模型與算法,應(yīng)該從實際情況出發(fā)考慮,滿足查詢者的各種不同需求。請你們解決如下問題：問題一：僅考慮公汽線路,給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù),利用你們的模型與算法,求出以下6對起始站→終到站之間的最佳路線〔要有清晰的評價說明。<1>、S3359→S1828<2>、S1557→S0481<3>、S0971→S0485<4>、S0008→S0073<5>、S0148→S0485<6>、S0087→S3676問題二：同時考慮公汽與地鐵線路,解決以上問題。問題三：假設(shè)又知道所有站點之間的步行時間,請你給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。2模型的假設(shè)及符號說明2.1模型假設(shè)假設(shè)1：假設(shè)乘客都是理性乘車且能順利到達目的地假設(shè)2：假設(shè)不考慮紅綠燈造成的等待時間,不考慮堵車,車禍等因素假設(shè)3：假設(shè)乘客能接受的最大換乘次數(shù)為2次假設(shè)4：假設(shè)乘客乘車過程中不能2次經(jīng)過同一站點。假設(shè)5：假設(shè)公交與地鐵換乘距離固定,換乘步行時間為常數(shù)2.2符號說明符號說明S公汽站點集,L表示公汽線路集,D地鐵站點集,T表示地鐵線路集,vik出行者選擇第條公交線路所經(jīng)過的第個站點<或>出行者選擇第條公交線路所乘坐的第輛公交工具<或>Ni換乘次數(shù)Si途經(jīng)的車站數(shù)ti行程時間Qi所需費用3問題分析本文研究的問題是設(shè)計一個公交線路選擇的自助查詢的計算機系統(tǒng),并從實際情況出發(fā)考慮,以滿足查詢者的各種不同需求。設(shè)計該系統(tǒng)的核心是線路選擇的模型與算法。針對問題一：問題一要求只考慮公汽線路,給出最佳路徑。通過查閱相關(guān)資料,知道對乘客影響最大的三個因素：換乘次數(shù),行程時間,所需費用<重要性從大到小>。據(jù)此,我們建立以換乘次數(shù)為第一目標,行程時間最為第二目標,所需費用為第三目標的多目標最優(yōu)化模型。對于換乘次數(shù),聯(lián)系被選擇線路上的站點—線路交替序列TRi個數(shù)可以表示出來；站點總數(shù)則采用給同一線路上的站點排序的方法也可以求到,由于只考慮了公汽之間的換乘,則出行時間只與換乘次數(shù)和所歷站數(shù)有關(guān)；對于出行費用則在換乘次數(shù)的基礎(chǔ)上,引入分段計價的加價函數(shù)也可求得。針對問題二：問題二在一得基礎(chǔ)上考慮可以搭乘地鐵,乘客的選擇更加靈活。主要變化為：地鐵票價稍高但是固定且在地鐵航線之間換乘而不需另外支付交通費用,相鄰站點之間的距離較公汽站點大,而運行時間卻相對減少；地鐵與公汽之間進行換乘時,由于地鐵站點不可能與公汽站點都建在同一個地方,因此從地鐵站到公汽站的步行時間相對較多,而且位于與地鐵換乘的公汽站點還可以通過本地鐵站進行免費耗時換乘到下一個公汽站。我們可以把跨公交站的步行視為一種免費耗時的交通方式,據(jù)此分層求解。針對問題三：考慮到出行者在步行時,所經(jīng)過的任意兩站點之間的路徑都應(yīng)該是至少有一條公汽線路上的公交工具通過,由問題三的條件可知,步行時所經(jīng)過的兩站點之間的步行時間是一個已知值。當換乘的兩站之間站數(shù)不多時,我們考慮步行,這要可以減少換乘次數(shù),節(jié)約金錢。4數(shù)據(jù)處理及分析4.1數(shù)據(jù)處理數(shù)據(jù)統(tǒng)計我們運用Excel軟件對給的"公汽線路信息"和"地鐵線路信息"進行統(tǒng)計得到如下數(shù)據(jù)：表1公汽線路站點數(shù)地鐵線路分段計價單一票價上下行路徑相同環(huán)形路線公汽站點地鐵站點直行線路環(huán)形線路283條237條409條89條22條3957個39個1條1條公交系統(tǒng)共有公汽線路520條地鐵線路共2條根據(jù)表一并結(jié)合本文參數(shù)設(shè)定中的票價信息,綜合考慮,分析如下：在分段計價路線中,共有27條的公汽站點數(shù)不超過20,有148條的公汽站點數(shù)在21~40之間,公汽站點數(shù)超過40的線路有108條。因此,從單獨的計算角度來考慮,可以將分段計價中站數(shù)不超過20的線路歸為單一票制1元的線路,因此上述信息可修正為：票價信息為單一票制1元的線路264條；在分段計價的路線中,共有256條,其中有148條的公汽站點數(shù)在21~40之間,公汽站點數(shù)超過40的線路有108條。數(shù)據(jù)的儲存與處理由于所給的數(shù)據(jù)格式不利于程序軟件直接讀取和操作,我們運用Excel將數(shù)據(jù)處理為規(guī)格式,建立起公交線路矩陣A。把公汽線路信息以及地鐵線路信息分別導(dǎo)入到Excel表格中將公汽數(shù)據(jù)中的上下行相同、上下行不同、環(huán)行的線路分別找出并歸類。將上下行相同的上行序列倒序后作為下行序列。則每條線路對應(yīng)兩個行向量。環(huán)行線路若有n個站點,則依次以每個站點為起點和終點建立起n條首位相同的線路序列。運用Excel的查找替換功能將公汽站點編號"S"和地鐵站點編號"D"分別用0和111代替。目的是為了在汽車站和地鐵站區(qū)別的條件下讓matlab可以識別和進行矩陣操作。將所有的序列整合到同一個excel表中,建立交線路矩陣A,每一行儲存一條線路站點信息,沒有信息的點用"0”公交線路矩陣A建立交線路矩陣A后,我們可以把矩陣A導(dǎo)入MATLAB中,運用改進廣度搜索算法求解最佳路徑。5模型的準備5.1乘客心理調(diào)查公交車線路達800條以上,每一個公交站點可能有多條線路貫穿,通往不同的起點或終點,同樣,一個目的地也可由多條線路到達,錯綜復(fù)雜的公交車路線猶如網(wǎng)狀般將各站點聯(lián)系起來,將城市的行人們帶到其各自的目的地。我們通過互聯(lián)網(wǎng)查閱相關(guān)資料發(fā)現(xiàn),影響乘客公交線路的選擇,主要有以下幾個因素：換乘次數(shù),行程時間,所需費用,途經(jīng)的總站數(shù)等。其中有18.6%的乘客出行時,首先考慮的是乘車費用,30.4%的乘客首先考慮的是行程時間,42%的乘客首先考慮的是換乘次數(shù)。圖1：乘客出行調(diào)查圖就乘客本身而言,公交乘客出行更多考慮的是出行的方便性和舒適性,下面就影響公交乘客出行的各因素進行具體分析,不妨將以上影響因素作如下歸納解釋：<1>換乘次數(shù)：出行者完成一次從出發(fā)點到終點出行過程中所換車的次數(shù)。<2>行程時間：出行者在一次乘公交出行過程中所用的總時間。<3>所需費用：出行者在完成一次由起點到達目的地過程中所花的車費。<4>途徑的總站數(shù)：出行者完成一次出發(fā)點到終點過程中所經(jīng)過的車站總數(shù)5.2影響選擇因素分析"換乘次數(shù)"和"行程時間"是影響出行者的兩個獨立的因素,經(jīng)研究表明多數(shù)的公交乘客希望換乘次數(shù)最少,況且公交公司對公交線路的設(shè)計也是盡量減少乘客的平均換乘次數(shù)；而且公交乘客出行時還受到行、地理位置等客觀因素的影響,這樣更不希望有較多的換乘。其次對于看奧運非常心切的出行者來講,出行耗時對他們也是比較關(guān)鍵的。在此當給出供乘客選擇的公交路線也應(yīng)當盡可能的滿足公交乘客的需求。當然,在此基礎(chǔ)上我們還要考慮乘車費用。綜上所述,可以以換乘次數(shù)最少為第一目標,再選擇易于量化的"出行時間"和"所需費用"作為第二位的優(yōu)化目標。由此,我們認為,乘客在選擇路線時,可以根據(jù)自己的不同需求,對線路進行選擇。5.3最優(yōu)乘車方案算法分析在站點上放置一個便于乘客查詢到達目的地的理想乘車方案的計算機系統(tǒng),必須讓計算機收集到本站到其他任意一站的路徑與換乘信息,因此單獨設(shè)計這樣的算法是相當困難的,而且算法的精度要求也比較高。對本文附件中的公交系統(tǒng)中所列的3957個公汽站點和39個地鐵站點來說,直接要得到所有任意兩站點之間的最優(yōu)公交路徑的計算量是相當大的。當面對這樣一個密集的交通網(wǎng)絡(luò)來說,對路線的選擇主要是將面臨一個類問題,根據(jù)類問題的處理特點,可以用某種主次改進的方法來求解。由于每次改進中的計算量都是多項式界的,改進的次數(shù)也是多項式界的。目前已找到具有這種特性的算法,如橢球算法,卡馬卡算法,但都相當復(fù)雜。因此要滿足出行者的路線需求,則有必要對目標進行歸類篩選,以降低不必要的選擇、計算與搜索。不妨采用改進的廣度優(yōu)先搜索算法,基于改進次數(shù)為多項式界的算法理論,本文選擇從某次乘公交的起點和終點的兩端進行同時搜索,在滿足換乘次數(shù)最少的條件下尋找不同線路中的共同站點或不同站點之間的相同線路,并計算其總路線的中的乘車時間和站點數(shù)。6站點—線路交替序列模型的建立6.1模型的建立本文所要解決的根本問題是設(shè)計一個公交線路選擇的自助查詢的計算機系統(tǒng),并從實際情況出發(fā)考慮,以滿足查詢者的各種不同需求。設(shè)計該系統(tǒng)的核心是線路選擇的模型與算法。我們建立交替序列模型尋找最優(yōu)線路。模型的預(yù)處理出行者所選擇出行的起始站為v0,終到站為vd,從v0到vd的所有路徑的集合也為TR,其中第i條路徑為TRi,所乘坐的第節(jié)公交工具為pik。進一步分析和考慮出行者乘公交的具體情況,一個出行者的出行可簡單描述為如下路徑圖2：出行者選乘公交路徑規(guī)律分析示意圖起始站起始站中轉(zhuǎn)站1乘第1節(jié)公交離開公交結(jié)束選乘初次車出發(fā)……中轉(zhuǎn)站2中轉(zhuǎn)站3選擇路線乘第2節(jié)公交第1次換乘終到站乘第3節(jié)公交第2次換乘中轉(zhuǎn)站Ni乘第Ni+1節(jié)公交第Ni次換乘從圖中容也可以反應(yīng),出行者出行乘公交的路徑可看著是站點、車次、站點、車次的交替進行,直至到達終到站。為區(qū)別前后的車次或站點,使得前后排列的站點與車次都有一定的順序,由于出行者不能在同一站點上出現(xiàn)兩次,即vik各不相同,特別地令,；交替序列的表示分析可知,選擇線路上的站點—線路交替序列為：其中站點—線路交替序列表示從起始點選擇線路,換乘到達,……,最終到達的第種路徑。起始站到達終到站的公交線路選擇集,即：對于乘客而言,我們只要知道他的出行起始站v0和終到站vd之后,便可以在路徑集TR中找到他最需要的出行路線。本模型對路線的選擇圍確定了界限,這樣也明確了尋求最優(yōu)線路的討論圍,即搜索的路徑<公交線路pik>和節(jié)點<公交站點vik>都是相互關(guān)聯(lián)的。7問題一的解答7.1多目標最優(yōu)化分層求解模型的建立確定目標函數(shù)本文所要解決的根本問題最佳乘車路線的設(shè)計問題。建立以換乘次數(shù)Ni為第一目標,再選擇易于量化的"出行時間ti"作為第二目標的多目標最優(yōu)化模型。為了便于求解我們定義目標函數(shù)U表示以Ni為第一目標,ti作為第二目標Qi作為第三目標：確定約束條件1.目標函數(shù)U最小時,換乘次數(shù)和乘車時間也要求最小,因此U與Ni及ti是正相關(guān)的。2.由于在優(yōu)先選擇權(quán)上,按相應(yīng)條件,在目標函數(shù)中,應(yīng)優(yōu)于,相關(guān)變量的確定求解Ni取最小值時,再進行其它變量的確定與計算,才能選擇到相應(yīng)的目標。即需要在可行域中進行優(yōu)先性的條件搜索。I換乘次數(shù)設(shè)表示有序集中的元素的個數(shù),為便于區(qū)別,現(xiàn)標記,換乘次數(shù)可表示為II所通過的總站數(shù)設(shè)非環(huán)行線路上的兩個站點和在沿著公交工具行進方向上的站數(shù)按照正整數(shù)從小到大的排序分別為和,其中仍然記；,于是由數(shù)據(jù)處理中的相關(guān)統(tǒng)計結(jié)果可知：當線路為環(huán)行線路時,設(shè)該環(huán)行路線上的總站數(shù)為,為上的任意一站,,分別為公交工具在沿著行進方向上的最后一站和前一站,于是可標記；；；…；；…所以出行者乘坐線路的公交所經(jīng)過的站點數(shù)目為：所以,出行者途經(jīng)的總站數(shù)為共條行車路線上車站數(shù)的總和,即III乘客所用時間設(shè)出行者選擇第i條線路從起始站v0到達終到站vd所耗的平均總時間為ti,換乘一次所耗的平均時間為=5分鐘,相鄰兩站點之間乘車的平均時間為=3分鐘。則有IV乘車總費用公汽線路上的單一制票價為1元,分段計價的票價標準為出行者通過本線路0~20個站：1元；21～40站：2元；40站以上：3元。公汽的單一票價為Qi0,出行者在所選擇的出行線路中所應(yīng)支付的車旅費為Qi,所乘同一公交線路上的最高收費為,分段計價時加價的最少站數(shù)為,于是有：其中表示取不超過的最大整數(shù),參數(shù)：〔元,〔元,.綜上所述,對問題立多目標優(yōu)化分層求解模型7.2模型的求解線路的抽象處理從A站到B站的行車路線時,首先考慮是否有經(jīng)過A站直接到達B站。如果存在不只一條的直達線路,在考慮所走路線的遠近,選擇距離最近的乘車方案；如果沒有直達車,就會考慮換一次車的方案。即經(jīng)過A站的車與經(jīng)過B站的車是否有公共站點C。如果有,則可在公共站點C處轉(zhuǎn)車到達站點B。如果沒有換一次車的方案,則又要考慮乘坐經(jīng)過A點的車到某一站C下車,經(jīng)過C站點的車與經(jīng)過B站點的車是否有公共站點D,如果有,就到公共站點D轉(zhuǎn)車,兩次轉(zhuǎn)車可到達站點B；如果沒有,則需要轉(zhuǎn)乘三次或三次以上才可到達目的地。在上述情況中如果存在不止一種的選擇方案,則在考慮乘車距離,選擇路程最短的乘車方案。<d>換乘多次車的情況<d>換乘多次車的情況圖2公交線路換乘方案示意圖<a>直達的情況<b>換乘一次車的情況ABCBA<c>換乘兩次車的的情況ABCDABCD運用matlab求解如下〔具體程序見附錄一表1問題一的結(jié)果路徑換乘次數(shù)時間<分>費用<元>總站數(shù)19533329733311224421772272973331592217.3結(jié)果分析我們以換乘次數(shù)為第一目標,假設(shè)乘客可以接受的換乘次數(shù)不超過2次,將問題簡化。只考慮乘公汽,所求的6條路徑?jīng)]有直達的其中第1,3,4,6條要換乘一次；第2,5條路徑要換乘2次。8問題二的解答8.1多目標最優(yōu)化分層求解模型的建立確定目標函數(shù)問題二在問題一的基礎(chǔ)上考慮可以搭乘地鐵。乘客的選擇更加靈活。其主要變化的因素有：1地鐵票價稍高但是固定且在地鐵航線之間換乘而不需另外支付交通費用,相鄰站點之間的距離較公汽站點大,而運行時間卻相對減少2地鐵與公汽之間進行換乘時,由于地鐵站點不可能與公汽站點都建在同一個地方,因此從地鐵站到公汽站的步行時間相對較多,而且位于與地鐵換乘的公汽站點還可以通過本地鐵站進行免費換乘到下一個公汽站。確定約束條件變量的確定當并入地鐵公汽的交通網(wǎng)絡(luò)時,增加地鐵站與其周圍的公汽站之間的步行線連接轉(zhuǎn)換后,本問題可轉(zhuǎn)化為問題一中的模型求解,同樣有出行者通過公汽換乘、地鐵換乘、公汽與地鐵之間的換乘后從起始站v0到達終到站vd的可行路徑集為：其中pik的屬性將被擴大,它將表示公汽、地鐵、步行這三類交通路線中的某一類交通路線；而的含義與問題一中的含義相同,仍表示公交站點或地鐵站點。I換乘次數(shù)與途經(jīng)總站數(shù)同樣設(shè)路徑的換乘次數(shù)為途經(jīng)總站數(shù)為,同問題一對,仍然有：II出行者乘公交所用時間在地鐵——公汽的公交系統(tǒng)中,出行者將會表現(xiàn)在公汽運行耗時,地鐵運行耗時,地鐵換乘公汽耗時,公汽換乘地鐵耗時,公汽換乘公汽耗時,地鐵換乘地鐵耗時,公汽通過指定地地鐵換乘公汽耗時。為簡化變量,考慮出行者的異站步行也納入到公交線的行列中,則所消耗的時間可歸結(jié)為：交通工具運行耗時,交通線路換乘耗時兩類。設(shè)出行者從起始站到達終到站所用的總時間為,從公交站點乘線路公交工具到達公交站點所消耗的時間〔包括相鄰兩站點間的停站時間為：,由線路的公交工具換乘到線路的公交工具所消耗的時間為：,由基本參數(shù)設(shè)定的信息可得：其中IV乘車總費用在問題二的討論中,乘車的總體花費會受到出行者換乘次數(shù),乘坐分段計價車時通過的站數(shù)的影響,而在本問題中,有假設(shè)知道同一地鐵站對應(yīng)的任意兩個公汽站可以通過地鐵站換乘而不需要支付地鐵費,同樣根據(jù)問題一中,對乘公交所支付費用的討論思想,仍然令乘坐公汽的單一票價為Qi0,出行者在所選擇的出行線路中所應(yīng)支付的車旅費為Qi,所乘同一公交線路上的最高收費〔含地鐵收費為Qil,分段計價時加價的最少站數(shù)為L0,于是有：其中表示取不超過A的最大整數(shù)；參數(shù)：〔元,〔元,綜上所述,對問題立多目標最優(yōu)化分層求解模型8.2模型的求解設(shè)計算法1輸入乘車的起始站點及目的站點；2求經(jīng)過站點A的所有線路集S<I>和經(jīng)過站點B的所有線路集T<J>；3判斷S<I>=T<J>如果有,則找到了從站點到站點的直達線路S<I>即T<J>,輸出結(jié)果,結(jié)束運算,如果沒有則進行下一步。4求線路S<I>上的站點E<I,U>以及線路T<J>上的站點F<J,V>；5判斷是否存在相同站點,即=,或者存在緊鄰站點,即滿足；如果滿足=,則線路,即為一次轉(zhuǎn)車的線路,即為轉(zhuǎn)車站點且換車時不用更換站點；如果滿足但滿足,則線路,即為一次專車線路,即為轉(zhuǎn)車站點但換車時要步行到緊鄰站點。如果沒有,再執(zhí)行下面步驟。6求經(jīng)過的線路集,經(jīng)過的線路集；7判斷=嗎？如果有,則線路,,為兩次換車的線路,換車站點為和,輸出結(jié)果,結(jié)束運算；如果沒有則執(zhí)行下面步驟。8求線路上的站點和線路上的站點；9判斷是否存在相同站點,即=,或者存在相鄰站點,即滿足；如果滿足=,則線路,,,即為三次轉(zhuǎn)車的線路,,,即為轉(zhuǎn)車站點,且換車時不用更換站點；如果滿足但滿足,則在站點專車時要步行到緊鄰站點。算法流程圖開始開始獲取起點和終點真假假假輸出,,輸出,,輸出,,,,,,,選擇換乘次數(shù)最少且花費時間最短的乘車方案最為最終結(jié)果真真真結(jié)束運用matlab求解結(jié)果如下〔具體程序見附錄二表2問題二的結(jié)果路徑換乘次數(shù)時間<分>費用<元>195329731122417722973034.538.3結(jié)果分析對比問題一與問題二的求解結(jié)果可知,前面5條路線求解的最佳路徑是一樣的,原因在于在換乘次數(shù)和行程時間差不多的情況下,地鐵較貴為3元。所以,這種情況下,盡量不乘坐地鐵。比較第6條路徑,我們發(fā)現(xiàn)乘坐地鐵使得行程時間大大縮短,并且由于地鐵站和起始站在一起,乘坐地鐵不用換乘。故考慮地鐵后,第6條路徑大大優(yōu)化。9問題三的解答9.1多目標最優(yōu)化分層求解模型的建立確定目標函數(shù)考慮到出行者在步行時,所經(jīng)過的任意兩站點之間的路徑都應(yīng)該是至少有一條公汽線路上的公交工具通過,由問題三的條件可知,步行時所經(jīng)過的兩站點之間的步行時間是一個已知值。據(jù)實際情況,假設(shè)步行者步行在相鄰兩公汽站所用時間平均是公汽經(jīng)過這兩站〔包括停站時間所用時間的倍,則由基本參數(shù)設(shè)定可知,步行者通過這樣兩站點所用的平均時間為分鐘,于是將行人步行所經(jīng)過的線路也納入到公交線路中,其特點是費時費力但選擇靈活。確定約束條件確定變量設(shè)出行者以步行、乘公交、換乘等任意的出行方式從初始站V0到達終到站Vd的可行路徑集為：,其中,上式中的、都與問題二中、的含義分別相同,I換乘次數(shù)、途經(jīng)總站數(shù)設(shè)該路徑的換乘次數(shù)為途經(jīng)總站數(shù)為,仍然有II出行者乘公交所用時間在步行—地鐵—公汽的公交系統(tǒng)中,出行者將會出現(xiàn)公汽運行耗時,地鐵運行耗時,地鐵換乘公汽耗時,公汽換乘地鐵耗時,公汽換乘公汽耗時,地鐵換乘地鐵耗時,公汽通過指定地地鐵換乘公汽耗時,公交站點之間的步行耗時。同樣考慮出行者的異站步行納入到公交線的行列中來簡化變量,則所耗時間仍然可分為：交通工具運行耗時〔包括步行耗時,交通線路換乘耗時兩類。同樣設(shè)出行者從起始站到達終到站所用的總時間為,從公交站點乘線路公交工具到達公交站點所消耗的時間〔包括相鄰兩站點間的停站時間為：,由線路的公交工具換乘到線路的公交工具所消耗的時間為：,則由基本參數(shù)設(shè)定的信息可得：其中為公汽行進時是出行者步行時的平均倍率。III乘車總費用在問題三的討論中,乘車的總體花費會受到出行者換乘次數(shù),乘坐分段計價車時通過的站數(shù)的影響,而在本問題中,有假設(shè)知道同一地鐵站對應(yīng)的任意兩個公汽站可以通過地鐵站換乘而不需要支付地鐵費,步行的出行者在步行的公交站點線路上也不需要支付公交費用,同樣由問題一中對乘公交所支付的費用的討論思想,同樣令乘坐公汽的單一票價為,出行者在所選擇的出行線路中所應(yīng)支付的車旅費為,所乘同一公交線路上的最高收費〔含地鐵收費為,分段計價時加價的最少站數(shù)為,于是有：其中表示取不超過的最大整數(shù),在本題中；；綜上所述,對問題立多目標最優(yōu)化分層求解模型9.2模型的求解由于成年人的平均行走速度為1.5m/s,相鄰車站的距離大約為1000m,我們假設(shè)相鄰車站距離,人步行所要的時間約為11min運用matlab求解如下〔具體程序見附錄三先在站點S3359乘坐436路車到S1784,然后步行到S1828；一共費時104分鐘,總花費為：3元先在站點S971乘坐13路車到S2184,然后步行到S485；一共費時131分鐘,總花費為：4元先在站點S87乘坐454路車到S3496,然后步行到S3676；一共費時68分鐘,總花費為：2元

先在站點S8乘坐

159

路車到S400,然后步行到S73；一共費時86

分鐘,總花費為：2元9.3結(jié)果分析對比分析問題二和問題三的求解結(jié)果,考慮當兩站間相隔站數(shù)不多時,可以步行這一情況后,選擇路徑,換乘次數(shù)和費用減少,所消耗的時間增加。比如,考慮這一情況后,時間增加了9min,不用換乘了。步行是一種耗時省錢,選擇靈活的方式。10模型的改進、評價及推廣10.1模型的改進在實際生活中選擇了最短的公交線路但并不一定耗時就是最少的,因為各線路還可能存在堵車的情況,即公交線路的負載超載。因此,模型的改進以"提高最優(yōu)路徑選擇的靈活性展開"。另外,我們也可以在路徑選擇過程中考慮旅游景點的問題,選擇路徑盡量便于乘客的旅游觀光。綜合以上兩點,改進后模型更加貼近實際,更加合理。10.2模型的評價：優(yōu)點：<1>用圖論的知識將公交線路進行抽象處理,將現(xiàn)實問題數(shù)學(xué)化,使得求 解簡單方便。<2>據(jù)。<3>考慮了公交線路實際的負載情況,使得路徑的選擇更加靈活,符合實際情況。缺點： <1>只適用于找出直達、換乘一次或換乘兩次的最優(yōu)線路,具有局限性。 <2>轉(zhuǎn)乘兩次結(jié)果的計算時間超過了3分鐘,算法的時間復(fù)雜程度偏大。 <3>10.3模型的推廣：該模型不但可以應(yīng)用城市公交出行線路的選擇,還可以應(yīng)用于各種物流問題,如貨物從生產(chǎn)地運往銷售地如何選擇交通方式和運輸線路。參考文獻[1]新苗、王煒、馬文騰,基于GIS的公交乘客出行路徑選擇模型[J],東南大學(xué)學(xué)報〔自然科學(xué)版,30〔6：87-88,20XX。[2]傳峰、胡志偉,城市公交路網(wǎng)性能評估的網(wǎng)絡(luò)圖方法[J],系統(tǒng)工程,21〔3：58-61,2003.[3]巧霞、馬志強、發(fā),以最小換乘次數(shù)和站數(shù)為目標的公交出行算法[J],計算機應(yīng)用,24〔12：136-137,20XX。[4]啟帆、方道元,數(shù)學(xué)建模[M],：大學(xué),188-189,1999年[5]王建林,基于換乘次數(shù)最少的城市公交網(wǎng)絡(luò)最優(yōu)路徑算法[J],交通職業(yè)技術(shù)學(xué)院院報,25〔5：673-676,2000.[6]蕭楓、蔡秀云、唐德強,最短路徑算法分析及其在公交查詢的應(yīng)用[J],工程圖學(xué)學(xué)報,<3>：20-24,2001.附錄一%第一問程序loadbase_dat11.txt%導(dǎo)入汽車路線信息數(shù)據(jù)庫〔矩陣basedata=base_dat11;fprintf<'請輸入起初站號：'>;begin0=input<''>;bg=0;fprintf<'請輸入終點站號：'>;end0=input<''>;%查找和起點相關(guān)的路線條數(shù)并記下該路線A=zeros<86>;%記載與起點相關(guān)的路線條數(shù)<包括起點為線路中間某點>Lhao=zeros<1,86>;%記載與起點相關(guān)的路線條數(shù)<包括起點為線路中間某點>所對應(yīng)的汽車路數(shù)fori=1:size<basedata,1>basedata0=qzreos<basedata<i,:>>;luhao0=basedata0<1>;%記下公汽路號basedata0=basedata0<2:end>;if<basedata0<1>==basedata0<end>>%為環(huán)形線路form=1:size<basedata0,2>-1ifbasedata0<m>==begin0bg=bg+1;A<bg,1:size<basedata0,2>-m>=basedata0<m:end-1>;A<bg,size<basedata0,2>-m+1:size<basedata0,2>-1>=basedata0<1:m-1>;Lhao<bg>=luhao0;break;elsecontinue;endendelseforj=1:size<basedata0,2>%考慮到中間站為輸入的起始點if<basedata0<j>==begin0>bg=bg+1;A<bg,1:<size<basedata0,2>-j+1>>=basedata0<j:size<basedata0,2>>;Lhao<bg>=luhao0;break;elsecontinue;endendendend%比較各條可行路線中的最優(yōu)路線A0=A<1:bg,:>;%記下可行路線的條數(shù)及具體線路Lh0=Lhao<1:bg>;%記下可行路線對應(yīng)的汽車路數(shù)qq=0;%判斷是否換乘[en,state,l,tt,z]=direct<begin0,end0>;ifstate==1%不用換乘en=qzreos<en>;s0=size<en>;fprintf<'不用換乘！\n'>;fprintf<'直接從站點S%d乘坐%3d路車到達終點站S%4d.\n',begin0,l,end0>;fprintf<'具體路線為：\n'>;fprintf<'%d',en>;fprintf<'\n'>;fprintf<'總用時為：%3d分鐘\n',tt>;fprintf<'總費用為：%3d元\n',z>;else%下面是求出換乘一次的情況下的最優(yōu)路線T=zeros<1,bg>;%用于記錄換行后的每條全路線的用時F=zeros<1,bg>;%用于記錄換行后的每條全路線的總費用LU=zeros<2,bg>;%用于記錄換行的最優(yōu)路線的汽車路數(shù)L=zeros<bg,172>;%用于記錄換行后的每條全路線的具體路徑en0=zeros<1,172>;%最佳路線LU0=zeros<2,1>;%最佳路線對應(yīng)的汽車路數(shù)〔有先后t=0;%最佳路線對應(yīng)的時間z0=0;%最佳路線對應(yīng)的總費用fori=1:bg%先對每一條路線做處理H=zeros<85,172>;%可能的換乘全路徑L0=zeros<1,85>;%每個站點可能的最佳換乘路徑對應(yīng)用時F0=zeros<1,85>;%每個站點可能的最佳換乘路徑對應(yīng)費用Lu=zeros<1,85>;%每個站點可能的換乘路徑對應(yīng)汽車路數(shù)h=0;%記錄每條路線上的換乘站數(shù)forj=2:86%由于是換乘,故從每條線路的第二站開始[e1,s1,l1,tt0,z00]=direct<A0<i,j>,end0>;ifs1==1h=h+1;s=size<e1,2>;L0<h>=5+<j-2>*3+<s-2>*3;%求每一條路線的費用ifj<=20F0<h>=1+z00;elseifj>40F0<h>=3+z00;elseF0<h>=2+z00;end%H<h,1:j-1>=A0<i,1:j-1>;H<h,j:j+s-1>=e1;H<h,j+s>=A0<i,j>;%記錄下?lián)Q乘點Lu<h>=l1;elsecontinue;endend%找出某條路線最佳的換乘點ifh~=0min0=999;forn=1:hifL0<n>==0continue;elseifL0<n><min0min0=L0<n>;n0=n;%記住用時最小的路線編號T<i>=min0;L<i,:>=H<n0,:>;LU<1,i>=Lh0<i>;%換乘前的汽車路數(shù)LU<2,i>=Lu<n0>;%換乘后的汽車路數(shù)F<i>=F0<n0>;elsecontinue;endendelsecontinue;endend%%據(jù)用時最短找到最佳路徑min0=999;fori=1:bgifT<i>==0continue;elseifT<i><min0min0=T<i>;n0=i;%記住用時最小的路線編號%找到了最佳路線en0=L<n0,:>;t=min0;%最佳路線對應(yīng)的時間LU0<:,1>=LU<:,n0>;z0=F<n0>;elsecontinue;endendifen0<1>~=0en0=qzreos<en0>;en00=en0<1:size<en0,2>-1>;fprintf<'需要換乘一次！\n'>;fprintf<'具體路線為：\n'>;fprintf<'%d',en00>;fprintf<'\n'>;fprintf<'即：先在站點S%d乘坐%d路車到S%d,然后改乘%d路車到S%d；一共費時%d分鐘,總花費為：%d元\n',begin0,LU0<1>,en0<end>,LU0<2>,en0<end-1>,t,z0>;elseqq=1;endendifqq==1TT=zeros<1,bg>;%用于記錄換行后的每條全路線的用時LL=zeros<bg,258>;%用于記錄換行后的每條全路線的具體路徑LLU=zeros<3,bg>;%用于記錄換行的最優(yōu)路線的汽車路數(shù)FF=zeros<1,bg>;%用于記錄換行后的每條全路線的總費用HH0=zeros<1,bg>;%后面的隱藏換乘點en0=zeros<1,258>;%最佳路線LU0=zeros<3,1>;%最佳路線對應(yīng)的汽車路數(shù)〔有先后t=0;%最佳路線對應(yīng)的時間z0=0;%最佳路線對應(yīng)的總費用h0=0;%最佳隱藏換乘點fori=1:bgHH=zeros<bg,258>;%可能的換乘全路徑H0=zeros<1,85>;%后面的隱藏換乘點LL0=zeros<1,85>;%每個站點可能的最佳換乘路徑對應(yīng)用時FF0=zeros<1,85>;%每個站點可能的最佳換乘路徑對應(yīng)費用LLu=zeros<2,85>;%每個站點可能的換乘路徑對應(yīng)汽車路數(shù)<有前后兩次>h=0;%記錄每條路線上的換乘站數(shù)w=size<qzreos<A0<i,:>>,2>;forj=2:w%由于是換乘,故從每條線路的第二站開始[e2,s2,l2,ttt0,zz00]=direct1<A0<i,j>,end0>;ifs2==1h=h+1;e3=e2<1:end-1>;%最后一個為換乘點s=size<e3,2>;LL0<h>=2+<j-1>*3+ttt0;%求每一條路線的費用ifj<=20FF0<h>=1+zz00;elseifj>40FF0<h>=3+zz00;elseFF0<h>=2+zz00;end%HH<h,1:j-1>=A0<i,1:j-1>;HH<h,j:j+s-1>=e3;HH<h,j+s>=A0<i,j>;%路線的最后一個元素記錄第一個換乘點LLu<:,h>=l2;H0<h>=e2<end>;elsecontinue;endend%找出某條路線最佳的換乘點ifh~=0min0=99999;forn=1:hifLL0<n>==0continue;elseifLL0<n><min0min0=LL0<n>;n0=n;%記住用時最小的路線編號TT<i>=min0;LL<i,:>=HH<n0,:>;LLU<1,i>=Lh0<1,i>;%換乘前的汽車路數(shù)LLU<2:3,i>=LLu<:,n0>;%換乘后的汽車路數(shù)FF<i>=FF0<n0>;HH0<i>=H0<n0>;elsecontinue;endendelsecontinue;endend%%據(jù)用時最短找到最佳路徑min0=99999;fori=1:bgifTT<i>==0continue;elseifTT<i><min0min0=TT<i>;n0=i;%記住用時最小的路線編號%找到了最佳路線en0=LL<n0,:>;t=min0;%最佳路線對應(yīng)的時間LU0<:,1>=LLU<:,n0>;z0=FF<n0>;h0=HH0<n0>;elsecontinue;endendifen0<1>~=0en0=qzreos<en0>;en00=en0<1:size<en0,2>-1>;fprintf<'需要換乘二次！\n'>;fprintf<'具體路線為：\n'>;fprintf<'%d',en00>;fprintf<'\n'>;fprintf<'即：先在車站S%d乘坐%d路車到S%d,然后改乘%d路車到S%d,最后轉(zhuǎn)乘%d路車到達S%d一共費時%d分鐘,總花費為：%d元\n',begin0,LU0<1>,en0<end>,LU0<2>,h0,LU0<3>,en0<end-1>,t,z0>;endend附錄二%第二問程序loada1.txt%導(dǎo)入汽車路線信息數(shù)據(jù)庫〔矩陣basedata=a1;fprintf<'請輸入起始站號：'>;begin0=input<''>;bg=0;fprintf<'請輸入終點站號：'>;end0=input<''>;ed=0;%查找和起點相關(guān)的路線條數(shù)并記下該路線A=zeros<88>;%記載與起點相關(guān)的路線條數(shù)<包括起點為線路中間某點>B=zeros<88>;%記載與終點相關(guān)的路線條數(shù)<包括起點為線路中間某點>Lhao=zeros<88,1>;%記載與起點相關(guān)的路線條數(shù)<包括起點為線路中間某點>所對應(yīng)的汽車路數(shù)LHao=zeros<88,1>;%記載與終點相關(guān)的路線條數(shù)<包括起點為線路中間某點>所對應(yīng)的汽車路數(shù)fori=1:size<basedata,1>basedata0=qzreos<basedata<i,:>>;luhao0=basedata0<1>;%記下公汽路號basedata0=basedata0<2:end>;if<basedata0<1>==basedata0<end>>%為環(huán)形線路form=1:size<basedata0,2>-1ifbasedata0<m>==begin0bg=bg+1;A<bg,1:size<basedata0,2>-m>=basedata0<m:end-1>;A<bg,size<basedata0,2>-m+1:size<basedata0,2>-1>=basedata0<1:m-1>;Lhao<bg>=luhao0;endifbasedata0<m>==end0ed=ed+1;B<ed,1:size<basedata0,2>-m-1>=basedata0<m+1:end-1>;B<ed,size<basedata0,2>-m:size<basedata0,2>-1>=basedata0<1:m>;LHao<ed>=luhao0;break;elsecontinue;endendelseforj=1:size<basedata0,2>%考慮到中間站為輸入的起始點if<basedata0<j>==begin0>bg=bg+1;A<bg,1:<size<basedata0,2>-j+1>>=basedata0<j:size<basedata0,2>>;Lhao<bg>=luhao0;break;endif<basedata0<j>==end0>ed=ed+1;B<ed,1:j>=basedata0<1:j>;LHao<ed>=luhao0;break;elsecontinue;endendendend%比較各條可行路線中的最優(yōu)路線A0=A<1:bg,:>;%記下與起點相關(guān)的可行路線的條數(shù)及具體線路Lh0=Lhao<1:bg>;%記下與起點相關(guān)的可行路線對應(yīng)的汽車路數(shù)B0=B<1:ed,:>;%記下與終點相關(guān)的可行路線的條數(shù)及具體線路LH0=LHao<1:ed>;%記下與終點相關(guān)的可行路線對應(yīng)的汽車路數(shù)%求每條與起點相關(guān)的路線上可乘地鐵點D=zeros<bg,88>;%記載起始站點的相關(guān)換乘點D0=zeros<ed,88>;%記載終點站點的相關(guān)換乘點fori=1:bgd0=qzreos<A0<i,:>>;forj=1:size<d0,2>forp=521:size<basedata,1>basedata00=qzreos<basedata<p,:>>;ifbasedata00<2>==A0<i,j>if11100<basedata00<3>&&basedata00<3><22266D<i,j>=basedata00<3>;%記下入地鐵點break;elsecontinue;endelsecontinue;endendifD<i,j>~=0break;elsecontinue;endendendfori=1:edd0=qzreos<B0<i,:>>;forj=1:size<d0,2>forp=521:size<basedata,1>basedata00=qzreos<basedata<p,:>>;ifbasedata00<2>==B0<i,j>if11100<basedata00<3>&&basedata00<3><22266D0<i,j>=basedata00<3>;%記下入地鐵點break;elsecontinue;endelsecontinue;endendifD0<i,j>~=0break;elsecontinue;endendend%確定起始點入站的地點Z=zeros<3,bg>;%記載每條線路的入地鐵的線路站點及地鐵站點fori=1:bgd0=qzreos<A0<i,:>>;forj=1:size<d0,2>ifD<i,j>~=0Z<1,i>=D<i,j>;%入地鐵的地鐵站點Z<2,i>=A0<i,j>;%入地鐵的線路站點Z<3,i>=j-1;elsecontinue;endendend%確定終點入站的地點Z0=zeros<3,ed>;%記載每條線路的入地鐵的線路站點及地鐵站點fori=1:edd0=qzreos<B0<i,:>>;forj=1:size<d0,2>ifD0<i,j>~=0Z0<1,i>=D0<i,j>;%入地鐵的地鐵站點Z0<2,i>=B0<i,j>;%入地鐵的線路站點Z0<3,i>=size<d0,2>-j;elsecontinue;endendend%分別算出所有可行線路的耗間H=zeros<bg,ed>;%記錄耗時F=zeros<bg,ed>;%記錄費用fori=1:bgforj=1:edH<i,j>=Z<3,i>*3+6+ditiejishi<Z<1,i>,Z0<1,j>>+6+Z0<3,j>*3;F<i,j>=jifei<Z<3,i>>+3+jifei<Z0<3,j>>;endend%求出矩陣中最小的數(shù)的坐標號,即對應(yīng)為最佳路徑P=0;Q=0;o=999999;fori=1:bgforj=1:edifH<i,j>==0continue;elseifH<i,j><oo=H<i,j>;P=i;Q=j;elsecontinue;endendendl1=Lh0<P>;s1=Z<2,P>;d1=Z<1,P>;ifd1>20000d1=d1-22200;elsed1=d1-11100;ends2=Z0<2,Q>;l2=LH0<Q>;d2=Z0<1,Q>;ifd2>20000d2=d2-22200;elsed2=d2-11100;endt0=H<P,Q>;f0=F<P,Q>;fprintf<'最佳路線為：'>;fprintf<'先乘坐%d路車到S%d,換乘地鐵D%d,再在地鐵站點D%d換乘%d路車的S%d到達終點站S%d.\n',l1,s1,d1,d2,l2,s2,end0>;fprintf<'總耗時為：%3.2f\n',t0>;fprintf<'總費用為：%3.2f\n',f0>;附錄三%第三問程序loadbase_dat11.txt%導(dǎo)入汽車路線信息數(shù)據(jù)庫〔矩陣basedata=base_dat11;fprintf<'請輸入起初站號：'>;begin0=input<''>;bg=0;fprintf<'請輸入終點站號：'>;end0=input<''>;%查找和起點相關(guān)的路線條數(shù)并記下該路線A=zeros<86>;%記載與起點相關(guān)的路線條數(shù)<包括起點為線路中間某點>Lhao=zeros<1,86>;%記載與起點相關(guān)的路線條數(shù)<包括起點為線路中間某點>所對應(yīng)的汽車路數(shù)fori=1:size<basedata,1>basedata0=qzreos<basedata<i,:>>;luhao0=basedata0<1>;%記下公汽路號basedata0=basedata0<2:end>;if<basedata0<1>==basedata0<end>>%為環(huán)形線路form=1:size<basedata0,2>-1ifbasedata0<m>==begin0bg=bg+1;A<bg,1:size<basedata0,2>-m>=basedata0<m:end-1>;A<bg,size<basedata0,2>-m+1:size<basedata0,2>-1>=basedata0<1:m-1>;Lhao<bg>=luhao0;break;elsecontinue;endendelseforj=1:size<basedata0,2>%考慮到中間站為輸入的起始點if<basedata0<j>==begin0>bg=bg+1;A<bg,1:<size<basedata0,2>-j+1>>=basedata0<j:size<basedata0,2>>;Lhao<bg>=luhao0;break;elsecontinue;endendendend%比較各條可行路線中的最優(yōu)路線A0=A<1:bg,:>;%記下可行路線的條數(shù)及具體線路Lh0=Lhao<1:bg>;%記下可行路線對應(yīng)的汽車路數(shù)qq=0;%判斷是否換乘[en,state,l,tt,z]=direct<begin0,end0>;ifstate==1%不用換乘en=qzreos<en>;b0=size<en,2>;%判斷是否為環(huán)路線ss=0;%記錄是否為環(huán)形線路的狀態(tài)fori=1:b0 ifS<i>==l ss=1; break; else continue; endendifss==1%為環(huán)線線路fprintf<'該起始終點站在同一環(huán)形線路上！\n'>;fprintf<'直接從%d走到終點站%d即可；費時為15分鐘,費用為零.\n',begin0,end0>;elsefprintf<'無需步行；直接從站點%d乘坐%3d路車到達終點站S%4d.\n',begin0,l,end0>;fprintf<'具體路線為：\n'>;fprintf<'%d',en>;fprintf<'\n'>;fprintf<'總用時為：%3d分鐘\n',tt>;fprintf<'總費用為：%3d元\n',z>;endelse%下面是求出換乘一次的情況下的最優(yōu)路線T=zeros<1,bg>;%用于記錄換行后的每條全路線的用時F=zeros<1,bg>;%用于記錄換行后的每條全路線的總費用LU=zeros<2,bg>;%用于記錄換行的最優(yōu)路線的汽車路數(shù)L=zeros<bg,172>;%用于記錄換行后的每條全路線的具體路徑en0=zeros<1,172>;%最佳路線LU0=zeros<2,1>;%最佳路線對應(yīng)的汽車路數(shù)〔有先后t=0;%最佳路線對應(yīng)的時間z0=0;%最佳路線對應(yīng)的總費用fori=1:bg%先對每一條路線做處理H=zeros<85,172>;%可能的換乘全路徑L0=zeros<1,85>;%每個站點可能的最佳換乘路徑對應(yīng)用時F0=zeros<1,85>;%每個站點可能的最佳換乘路徑對應(yīng)費用Lu=zeros<1,85>;%每個站點可能的換乘路徑對應(yīng)汽車路數(shù)h=0;%記錄每條路線上的換乘站數(shù)forj=2:86%由于是換乘,故從每條線路的第二站開始[e1,s1,l1,tt0,z00]=direct<A0<i,j>,end0>;ifs1==1h=h+1;s=size<e1,2>;L0<h>=5+<j-2>*3+<s-2>*3;%求每一條路線的費用ifj<=20F0<h>=1+z00;elseifj>40F0<h>=3+z00;elseF0<h>=2+z00;end%H<h,1:j-1>=A0<i,1:j-1>;H<h,j:j+s-1>=e1;H<h,j+s>=A0<i,j>;%記錄下?lián)Q乘點Lu<h>=l1;elsecontinue;endend%找出某條路線最佳的換乘點ifh~=0min0=999;forn=1:hifL0<n>==0continue;elseifL0<n><min0min0=L0<n>;n0=n;%記住用時最小的路線編號T<i>=min0;L<i,:>=H<n0,:>;LU<1,i>=Lh0<i>;%換乘前的汽車路數(shù)LU<2,i>=Lu<n0>;%換乘后的汽車路數(shù)F<i>=F0<n0>;elsecontinue;endendelsecontinue;endend%%據(jù)用時最短找到最佳路徑min0=999;fori=1:bgifT<i>==0continue;elseifT<i><min0min0=T<i>;n0=i;%記住用時最小的路線編號%找到了最佳路線en0=L<n0,:>;t=min0;%最佳路線對應(yīng)的時間LU0<:,1>=LU<:,n0>;z0=F<n0>;