乘公交看奧運方案設(shè)計

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

2、完整的全名）黔南民族師范學(xué)院參賽隊員（打印并簽名）：1.曹龍2. 彭開連3. 陳勇指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）:薛先貴日期：2011年_8_月_15_日乘公交，看奧運摘要：本文將公交線路(3957個公汽站點和520條公汽線路、39個地 鐵站點和2條地鐵線路、地鐵與公汽間轉(zhuǎn)換關(guān)系)關(guān)系抽象為有向賦 權(quán)圖，并建立時間直達(dá)矩陣、費用直達(dá)矩陣、換乘直達(dá)線路數(shù)矩陣， 利用最短路模型、搜索法及0-1整數(shù)規(guī)劃模型進(jìn)行解答。對于問題一， 在只考慮公汽的情況下，我們用修改floyd算法求出最小轉(zhuǎn)乘次數(shù)、 最少費用、最少時間，并由搜索法得出最優(yōu)線路；對于問題二，在考 慮公汽和地鐵的情況下，同樣，我們也

3、用修改floyd算法求出最小轉(zhuǎn) 乘次數(shù)、最少費用、最少時間，并由搜索法得出最優(yōu)線路；對于第三 問題，我們則需要考慮步行時間進(jìn)去，在問題二的基礎(chǔ)上并利用0-1整數(shù)規(guī)劃模型進(jìn)行優(yōu)化組合取得最優(yōu)線路。關(guān)鍵字:線路選擇 有向賦權(quán)圖 修改floyd算法 搜索法 優(yōu)化模型一、問題重述：奧運會是世界上舉行的一項重大的賽事活動第29屆奧運會明年8月將在我國北京舉行，屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中 大部分人將會乘坐公共交通工具(簡稱公交，包括公汽、地鐵等)出 行。近年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá) 800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線 路的選擇問題。針對市

4、場需求，我們準(zhǔn)備研制開發(fā)一個解決公交線路 選擇問題的自主查詢計算機(jī)系統(tǒng)，關(guān)鍵在于線路選擇的模型與算法， 應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。具體問題如下：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般 數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以 下6對起始站-終到站之間的最佳路線(要有清晰的評價說明)。(1) 、S3359 S1828(2)、S1557 S0481(3)、S0971S0485（4）、S0008 S0073（5）、S014IS0485（6）、S0087S 36762、同時考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點之間的步

5、行時間，請你給出任意兩站點之間 線路選擇問題的數(shù)學(xué)模型?；緯r間參數(shù)設(shè)定：相鄰公 汽站平 均行駛 時間（包 括停站 時間）相鄰地 鐵站平 均行駛 時間（包 括停站時間）公汽換 公汽平 均耗時/（步行 時間）地鐵換 地鐵平 均耗時/（步行 時間）公汽換 地鐵平 均耗時/（步行 時間）地鐵換 公汽平 均耗時/（步行 時間）時間份 鐘）32.55/(2)4/(2)6/(4)7/(4)即:換乘公汽等待3分鐘，換乘地鐵等待2分鐘公汽站t地鐵站（通 道公汽站.換乘耗時11分鐘：步行4+4=8分鐘，等車3分鐘. 基本票價參數(shù)設(shè)定：票、交=一價X單一計價分段計價公汽1元0 20 站：1 元；21 40站：2元

6、；40站以 上: 3元地鐵3元（無論地鐵線路間是否換乘）公交線路及相關(guān)信息（見數(shù)據(jù)文件B2007data.rar）二、問題分析：本論文主要研究公交線路選擇的問題，即要求：a如何換車b車與車之間的關(guān)系c滿足乘車人關(guān)心的問題：1）換乘次數(shù)最少；2）費用最低；3）時間最短（初始等車時間 2（3）min也不包括在內(nèi)，最后結(jié)果可加上。；在眾多的條件中，為了切合人們的實際需要，優(yōu)先考慮是否有直 達(dá)，若無直達(dá)公汽，則我們主要從最方便、最經(jīng)濟(jì)、最快捷等出發(fā)，建 立以換乘次數(shù)、費用、時間為最優(yōu)的數(shù)學(xué)模型。三、模型假設(shè)：1、所有公交線路的每天的工作始末時間相同；2、公汽、地鐵均到站停車；3、各公交車都運行正常，不

7、會發(fā)生堵車現(xiàn)象；4、環(huán)線可以看作以任意站作為起點站和終點站，并且是雙向的 ，并且 經(jīng)過終點后要重新收費；5、假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘， 且無需支付地鐵費；6、人們對換乘車次數(shù)盡量少的偏好程度總是大于對花費時間相對短和花費金錢相對少的偏好程度；7初始等車時間2（或3）min也不包括在內(nèi)；8同一公交線的往返路線視為兩條單行線；9、考慮兩地鐵之間不通過公汽乘換（即只：公汽站 -地鐵站（通道） t公汽站）。四、模型建立：對于公交線路選擇，我們主要考、慮乘換次數(shù)、費用、時間各因 素最優(yōu)在線路選擇問題中，將公交路線關(guān)系抽象成一個有向賦權(quán)圖，當(dāng)從i可直達(dá)j時（同為公汽或地鐵站

8、點），定義?。╥,j）;其上的權(quán)為：i 二 ji站點往j站點無直達(dá)車否則lij表示由i直達(dá)j付出的代價，可以為時間或費用（不包括換乘代價；多條線路可達(dá)時只保留最小代價）;公交乘換方式：公汽公汽，公汽地鐵，地鐵公汽，地鐵地鐵，公汽地鐵公汽。A) i站點是公汽站點，j站點為地鐵站點：(1) 若j站點對應(yīng)的所有換乘(公汽)站點k，均不能從i直達(dá)(不在i 站點所在公汽線路L上)，則dij(°)= 乂；(2) 若j站點對應(yīng)的換乘(公汽)站點k,可從i站點直達(dá)k，貝卩費用為 dij(°)二 dJ0)；注:對于時間則需要加上k到j(luò)的步行時間.(若有多種選擇，取最 小成本者即可)B) j站

9、點是公汽站點，i站點為地鐵站點：(1) 若從i站點對應(yīng)的任何換乘(公汽)站點k，均不能直達(dá)j站點， 則 d ij (0) =乂 .(2) 若從i站點對應(yīng)的換乘(公汽)站點k,能直達(dá)j站點，則費用為 d ij (0)二 dkj(°)注：對于時間則需要加上i到k的步行時間.定義：矩陣算子“?！比缦拢涸O(shè)D (k-1 )、D均為n階方陣，D(k) = D (k-1) O D(考慮換乘代價)dk = min匕:dk*dkj+$=1,2川,n當(dāng)考慮費用矩陣間的運算時，i，j，k=0 ；當(dāng)考慮時間矩陣間的運算時，i，j，k表示在k的換乘時間。D(k)= D(k-1) OD表示k次換乘的最低代價(費

10、用或時間),即通過 修改floyd算法求解。8 i,j,k表示換乘時間：i = j 或 k = i, j 時，8 i,j,k = 0其他情形：若不可換乘(當(dāng)i , j為公汽站點而k為地鐵站點，或者i , j為地鐵站點而k為公汽站點時)，則S i,j,k = 0f5,若公汽換乘公汽4若地鐵換乘地鐵i,j若可換乘，貝心問題一模型：l,k3,(只考慮換乘時間)若地鐵換乘公汽2,(只考慮換乘時間)若公汽換乘地鐵因為僅考慮公汽線路，為了能得到兩站點之間的最好選擇線路，將題中所提供的公汽網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖，建立直達(dá)矩陣 DnDFd他n。當(dāng)D為時間直達(dá)矩陣時，按D(k)= D(k-1) O D式重復(fù)地

11、進(jìn)行O(k)k 1_k _運算得到D，當(dāng)dij 一 ' , dij .時，表示從i站點到j(luò)站點最少換.(k)乘k次能夠到達(dá)，且即dij表示換乘k次到達(dá)所需的最短時間。當(dāng)D為費用直達(dá)矩陣時，按 D(k)= D(k-1) O D重復(fù)地進(jìn)行O 運算得到D，運算適當(dāng)次數(shù)后若 D(k)= D(k-1)，則表示已得到所有(k)站點間的最小費用，dij即表示從i站點到j(luò)站點所需的最少費用。 根據(jù)最少乘換次數(shù)等約束條件，再利用圖的鄰接搜索法可得出兩站點之間的選擇線路。問題二模型：當(dāng)還需要考慮地鐵時，為了能得到兩站點之間的最好選擇線路,同樣，將題中所提供的公汽(含地鐵轉(zhuǎn)換的公汽)網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖

12、，建立直達(dá)矩陣D = D =(d iJ0)nxn。算法設(shè)計基本與模型一相當(dāng)D為時間直達(dá)矩陣時，按 D(k)二D(k-1) O D式重復(fù)地進(jìn)行(k)k JkO運算得到D，當(dāng)dij " , dij “:時，表示從i站點到j(luò)站點最少(k)換乘k次能夠到達(dá)，且即dij表示換乘k次到達(dá)所需的最短時間。當(dāng)D為費用直達(dá)矩陣時，按 D(k)= D(k-1) O D重復(fù)地進(jìn)行O一D(k)一 一運算得到D，運算適當(dāng)次數(shù)后若 D(k)= D(k-1)，則表示已得到所有(k)站點間的最小費用，dij即表示從i站點到j(luò)站點所需的最少費用。根據(jù)最少乘換次數(shù)等約束條件，再利用圖的鄰接搜索法可得出 兩站點之間的選擇

13、線路。問題三模型：問題三是在模型二的基礎(chǔ)上添加步行時間進(jìn)行考慮。D (0) _ / d (0)、優(yōu)先考慮乘換次數(shù)。對直達(dá)時間矩陣-ij nn按D(k)= D(k-1)(k)k Jk _O D式重復(fù)地進(jìn)行O運算得到D，當(dāng)dij ":，dij":時，表示從i 站點到j(luò)站點最少換乘k次能夠到達(dá)。在運算過程中可記錄下?lián)Q乘站 點信息，隨之可得到相關(guān)線路信息。若有若干條最小換乘路線，則比 較另外兩個目標(biāo)選擇最佳線路(即建立 0-1整數(shù)規(guī)劃模型)。設(shè)共有m條單行公交線，構(gòu)造一個 m+2個點構(gòu)成的完全圖。點：a為起點(出發(fā)點)，b為終點(目的地)，此外每條公交線 也視為一個點。邊：邊表示兩

14、點之間的步行關(guān)系。邊權(quán)：步行時間為邊權(quán)。針對不同的邊可分為上車前、下車后和換車時步行時間，構(gòu)成步行時間矩陣Sj = S(m 1) (m 1)。行：依次表示的是m條公交線與起點，列：依次表示的是 m條公交線與終點。點權(quán)：第個公交線點還有三個信息為點權(quán)1)公交線名稱及上行或下行;匚L,公汽,E 二2) 類型T,地鐵,及票價方式；3) 乘車站數(shù)表矩陣G二gcd gi )m( ,' T 1 , 2h m ,，其中g(shù)Cd表示從ic到d經(jīng)過i號公交線時需要乘車的站數(shù),c到d利用不上i時張取無 窮大。這個矩陣的行列表示用 S。于是原問題轉(zhuǎn)化為在這個圖上求 a到b的最短路。最短的可以理解為換乘車數(shù)最少

15、、乘車的總站數(shù)最少、總的步行 時間最少、總車費最少這樣幾個目標(biāo)的各種組合方式?？梢杂?-1整數(shù)規(guī)劃解決這個問題，方法是分出恰乘一次公交車， 恰乘兩次公交車，恰乘三次公交車等等情況分別求出下列模型解然后 比較得出最優(yōu)解。優(yōu)化模型：恰乘一次公交車的模型如下：變量全部是0-1變量，共有3*(m)個。Xi,1, M m表示選不選擇去第i條公交線的路；yi，匸引mg示選不選擇乘第i線公交車；Zi, 1, 2" 表示選不選擇從第i條公交車下車后走到目的地的路。(它們都是取1表示選擇而取0表示不選擇。)恰乘一次公交車的模型如下：目標(biāo)函數(shù)：據(jù)用戶選擇的情況用點權(quán)和邊權(quán)構(gòu)造，共同點都是最小值。(1)步

16、行時間最少：(2)總時間最少:目標(biāo)函數(shù)min a SniASd,miZdyWc討dVV其中3, E 二 L,2.5,E 二T,3E=L,2E訂min v Sm.1,cXc r Sd,m 1乙目標(biāo)函數(shù).cdd<(3) 車費最少:min F 二3,",zi Tiy i g m :：1, m :：；120E 二 T,E 二 L,單一，E二L,分段目標(biāo)函數(shù):約束條件(共2m+1個):m' y =1i4只選擇一條公交線;yi 乞X , yi <Zi i =1,2,|(,m要乘第i條公交線就要走相應(yīng)的兩條路。恰乘兩次公交車的模型如下:步行時間: mmmin m/W1*Sd,m

17、 1 Zd時間最少:mmi n'Sn1,c1X1c14mm+y+yJ Sm 十c2Xc2 Jc2Wd=1i1十ySd,miZyigm 十i1=1mi1 “i21i2mi2 “+zi21i2 |yi2gm1m1VEyi2WE 1費用最少:min F6,E2, E-iiy i 1 g m 1, m 120Ji2+ 二 y i2 g mTm*12o約束條件:m送yi1mi13%2 2可以選擇兩條公交線路;- Xii, yi2 - Xi2%咗Z"乘公交線要走的兩條相應(yīng)的路線。恰乘乘三次公交車模型步行時間的目標(biāo)函數(shù)在的基礎(chǔ)上添加mJSm1,c3Xc3c3=1時間最少的目標(biāo)函數(shù)在的基礎(chǔ)上

18、添加mm匚 Sm+1 c3Xc3 J 曲i3Ti3i3yi3gm 1m 1VE費用最少:min F9,E=T=* 3, E = L_ mi31 VJ yi3g m-1,m4ti3£ "mz.空i2mVy i2 g m 1,m 1i1 蘭20 20ii 1 y i1 g m+m+l20約束條件即在的基礎(chǔ)上添加i3的變量即可。五、模型求解：問題一：由于題目所給的公交乘路信息是.txt文本文件，為了將實際問題 能用數(shù)學(xué)模型來解決，我們編寫程序?qū)⑵鋵?dǎo)入 matlab。（程序見附錄 1）°對于問題1,我們僅僅考慮公汽線路，為此，我們將所有的公汽 路線與站點（3957個）關(guān)系

19、構(gòu)成一個圖網(wǎng)，為了求得最小代價的選 擇路線，我們先建立起直達(dá)矩陣（程序見附錄2）,再由改進(jìn)floyd算法（程序見附錄3）即可求出兩公汽站點之間線路選擇的最小代價（乘換次數(shù)、時間最短、費用最少），乘換次數(shù)為主、時間最短和費用最 少為次為約束條件用搜索法（見附錄程序 5）搜出最優(yōu)線路，具體結(jié) 果如下所示：起點站T終點 站乘換 次數(shù)時間（分 鐘）車費（元）線路S3359t S18281893S3359 匕嗎 S1784 乂叫 S1828S1557t S048121123S1557藝叫 S1919乂叫S3186-Wd S0481S0971t S048511193L013dL417dS0971、S218

20、4* S485S0008t S00731832S0008匕63 S2083顯9 S0073S0148t S048521063S0148-E°9 S0036乂叫_ _ _ _ .L156uS3351、S0485S0087t S36762523S0148仝叫 S0036-12叫S2210竺S0485問題二:對于問題2,我們在考慮公汽線路的同時，還需將地鐵線路（2條地鐵線路，39個地鐵站點）考慮進(jìn)去，同樣，將所提供的公汽（含地鐵轉(zhuǎn)換的公汽）網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖，建立直達(dá)矩陣（程 序見附錄4），再由改進(jìn)floyd算法（程序見附錄3）即可求出兩公汽 站點之間線路選擇的最小代價（乘換次數(shù)、時

21、間最短、費用最少），以換乘次數(shù)為主、時間最短與費用最少為次為約束條件用搜索法 （見 附錄程序6）搜出最優(yōu)線路，具體結(jié)果如下所示：起點站T終點 站乘換 次數(shù)時間 （分 鐘）車費（元）線路S3359t S18281893S3359 蘭竺t S1748三叫 S1828S1557t S048121123S1557匕叫S1919旦叫S3186匕 J S0481S0971t S048511193S097-101 型t S2184 土亠 S0485S0008t S00731832|_159dL474S0008 旦叫 S0400 蘭 J S0073S0148t S048521063T1S0148旦 J S14

22、87竺d21tS046A9 S0485S0087t S36760503T 2S0087 竺36- S3676問題三：問題3又增設(shè)了所有站點之間的步行時間，為了給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。我們則考慮大眾化的想法（優(yōu)先考慮 乘換次數(shù)）：1若兩個站點之間有直達(dá)的公交車，若只有一條，我們 毫無條件地選擇；若不止一條，則我們可以利用模型三的優(yōu)化模型進(jìn) 行時間和費用的比較，取最優(yōu)解；2同理，若要經(jīng)過轉(zhuǎn)乘一次、二 次等轉(zhuǎn)乘情況，若轉(zhuǎn)乘線路只有一種，則選擇之；若轉(zhuǎn)乘線路有多種， 則利用模型三的優(yōu)化模型進(jìn)行時間和費用的比較，取最優(yōu)解。六、模型優(yōu)缺點：將公交圖網(wǎng)能用有向賦權(quán)圖并建立直達(dá)矩陣，再利用最

23、短路算法及搜索算法得出線路選擇的最優(yōu)線路（含時間最少、費用最少等）；對于第三問題中的模型，在加入步行時間后，我們能考慮到在乘 換次數(shù)最少為優(yōu)先的條件下，利用優(yōu)化模型進(jìn)行比較是全面些。鑒于公交系統(tǒng)網(wǎng)絡(luò)的復(fù)雜性，我們雖然采用了修改floyd算法，編譯運行上不太好，有待改進(jìn)。七、參考文獻(xiàn)：1蔡志杰，丁頌康數(shù)學(xué)工程學(xué)報-公交線路選擇模型2007年12月 1005-3085 （ 2007） 08-0117-042朱參世一種Warshall和Fl oyd 算法的優(yōu)化方法研究 2010年第四期 1006-2475（2010）04-0043-033劉韻，何建農(nóng) 基于交通網(wǎng)絡(luò)最短路徑搜索的改進(jìn)算法2007年10

24、02-8331（ 2007）14-0220-03附錄：% 建立排序函數(shù)function A = T_SORT（ A ,n , p ）% T_SORT（ A ,n , p ）% A根據(jù)第n行排序% p=1升序，2降% powered_BY_* SIZE=size(A);if p=1xx,idx=sort(A(n,:);for i=1:SIZE(1)A(i,:)=A(i,idx);endelseif p=2xx,idx=sort(A(n,:),'descend');for i=1:SIZE(1)A(i,:)=A(i,idx);endend1、%數(shù)據(jù)處理讀入matlab :%讀取數(shù)據(jù)

25、clear L afid = fopen('1.1公汽線路信息.txt','r');i=1;while 1tline = fgetl(fid);if ischar(tline), break, endif strcmp(tline,")continueendif strcmp(tline(1),'L')str=tline;continueelseif strcmp(tline,'END')breakendif strcmp(tline,'P=1;continueelseif strcmp(tline,'P

26、=2;continueendif strcmp(tline(1:2),'單一票制1元。)分段計價。)上行')Li,1=str;Li,2=P;上行'Li,3='Li,4=tline(4:end);i=i+1;continue下行')環(huán)行')elseif strcmp(tline(1:2),'Li,1=str;Li,2=P;Li,3='下行'；Li,4=tline(4:end);i=i+1;continueelseif strcmp(tline(1:2),'Li,1=str;Li,2=P;Li,3='環(huán)行 1&

27、#39;Li,4=strcat(tline(4:end),tline(10:end);i=i+1;% 計算來回Li,1=str;Li,2=P;Li,3='環(huán)行 2'Li,4=strcat(tline(4:end),tline(10:end);i=i+1;continueelseif strcmp(tline(1),'S')Li,1=str;Li,2=P;Li,3='來回 1'Li,4=tline;i=i+1;% 計算來回Li,1=str;Li,2=P;Li,3='來回 2'Li,4=tline;i=i+1;continueende

28、ndfclose(fid);for i=1:size(L,1)tline=Li,4;t=findstr(tline,'S');temp=zeros(1,length(t);環(huán)行2')if strcmp(Li,3,'來回 2') | strcmp(Li,3,'for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4);endelsefor j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4);endendL2i

29、,1=temp;end for i=1:3957if floor(i/10)=0Citi=strcat('S000',num2str(i);elseif floor(i/100)=0Citi=strcat('S00',num2str(i);elseif floor(i/1000)=0Citi=strcat('S0',num2str(i);elseCiti=strcat('S',num2str(i);endendCit3958='D01Cit3959='D02Cit3960='D03Cit3961='

30、D04Cit3962='D05Cit3963='D06Cit3964='D07Cit3965='D08Cit3966='D09Cit3967='D10Cit3968='D11Cit3969='D12Cit3970='D13Cit3971='D14Cit3972='D15Cit3973='D16Cit3974='D17Cit3975='D18Cit3976='D19:S0567 , S0042 ,:S1487':S0303 , S0302':S0566'

31、:S0436 , S0438 ,:S0392 , S0394 ,:S0386 , S0388 ,:S3068 , S0617 ,:S1279':S2057 , S0721 ,:S0070 , S2361 ,:S0609 , S0608':S2633 , S0399 ,:S3321 , S2535 ,:S3329 , S2534':S3506 , S0167 ,:S0237 , S0239 ,:S0668':S0180 , S0181'S0025'S0437 , S0435'S0393 , S0391'S0387 , S0385&#

32、39;S0619 , S0618 ,S0722 , S0720'S3721'S0401 , S0400'S2464'S0168'S0238 , S0236 ,S0616'S0540'Cit3977='D20:S2079 ,S2933 ,S1919 , S1921 , S1920'Cit3978='D21:S0465 ,S0467 ,S0466 , S0464'Cit3979='D22:S3457'Cit3980='D23:S2512'Cit3981='D24:S053

33、7 ,S3580'Cit3982='D25:S0526 ,S0528 ,S0527 , S0525'Cit3983='D26:S3045 ,S0605 ,S0607'Cit3984='D27:S0087 ,S0088 ,S0086'Cit3985='D28:S0855 ,S0856 ,S0854 , S0857'Cit3986='D29:S0631 ,S0632 ,S0630'Cit3987='D30:S3874 ,S1426 ,S1427'Cit3988='D31:S0211 ,S

34、0539 ,S0541 , S0540'Cit3989='D32:S0978 ,S0497 ,S0498'Cit3990='D33:S1894 ,S1896 ,S1895'Cit3991='D34:S1104 ,S0576 ,S0578 , S0577'Cit3992='D35:S3010 ,S0583 ,S0582'Cit3993='D36:S3676 ,S0427 ,S0061 , S0060'Cit3994='D37:S1961 ,S2817 ,S0455 , S0456'Cit399

35、5='D38:S3262 ,S0622'Cit3996='D39:S1956 ,S0289 ,S0291'2、建立公汽間的直達(dá)矩陣clear SS(1:3957,1:3957)=zeros(1,1,'uint16');%按Ulnt16 格式建立 1 行 1 列的零巨陣for i=1:1040t=L2i,1;for j=1:length(t)-1for k=j+1:length(t)temp=St(j),t(k);str=Li,1;n,m=size(temp);if n=1 && temp(1,1)=0temp(n,1)=str2d

36、ouble(str(2:end);if Li,2=2if (k-j)>40temp(n,2)=3;elseif (k-j)>20temp(n,2)=2;elsetemp(n,2)=1;endelsetemp(n,2)=1;temp(n,3)=k-j;elsetemp(n+1,1)=str2double(str(2:end);if Li,2=2if (k-j)>40temp(n+1,2)=3;elseif (k-j)>20temp(n+1,2)=2;elsetemp(n+1,2)=1;endelsetemp(n+1,2)=1;endtemp(n+1,3)=k-j;endS

37、t(j),t(k)=temp;endendendfor i=1:3957for j=1:3957if length(Si,j)=1Si,j=T_SORT(Si,j',3,1)'endendendTime=zeros(3957,3957,'uint8');for i=1:3957for j=1:3957if length(Si,j)=1Time(i,j)=size(Si,j,1);endendendTT=zeros(3957,3957,'uint8');for i=1:3957for j=1:3957temp=Si,j;if temp(1,1)=0

38、TT(i,j)=temp(1,3);endEnd%時間、費用的直達(dá)矩陣(換乘直達(dá)線路數(shù)矩陣)ee,rr=size(S);ss=zeros(ee);for i=1:eefor j=1:rrif Si,j=0 ss(i,j)=length(Si,j(:,1);endendendfor i=1:eefor j=1:rrif ss(i,j)=0;ss(i,j)=Inf;endendendfor i=1:eefor j=1:rrif i=j;ss(i,j)=0;endendend2.2 (間直達(dá)矩陣)ee,rr=size(S);ttt=zeros(ee);for i=1:eefor j=1:rrif S

39、i,j=0ttt(i,j)=min(Si,j(:,3);endendendfor i=1:eefor j=1:rrif ttt(i,j)=0;ttt(i,j)=Inf;end endfor i=1:eefor j=1:rrif i=j；ttt(i,j)=O;endendend2.3 (費用直達(dá)矩陣)ee,rr=size(S);ppp=zeros(ee);for i=1:eefor j=1:rrif Si,j=0ppp(i,j)=min(Si,j(:,2);endendendfor i=1:eefor j=1:rrif ppp(i,j)=0;ttt(i,j)=Inf;endendendfor i

40、=1:eefor j=1:rrif i=j;ppp(i,j)=0;endendend3、。算子算法function D,path,k,min1,path1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:nforj=1:nif D(i,j)=infpath(i,j)=j;end, end, endwhile 1<=j<=nfor k=1:nDO(k,j)=D(k,j);endendfor k=1:nfor i=1:nforj=1:nif D(i,k)+DO(k,j)<D(i,j)D(i,j)=D(i

41、,k)+DO(k,j);path(i,j)=path(i,k);endif D(i,k-1)+DO(k-1,j)<D(i,j)D(i,j)=inf;if D(i,k)+DO(k,j)<D(i,j)D(i,j)=inf;kend,endendendendif nargin=3min1=D(start,terminal);m(1)=start;i=1;path1=;while path(m(i),terminal)=terminalk=i+1;m(k)=path(m(i),terminal);i=i+1;endm(i+1)=terminal;path1=m;end4、考慮地鐵的直達(dá)矩陣

42、fid = fopen('B2007data/2.1地鐵 T1 線換乘公汽信息.txt','r');i=1;while 1tline = fgetl(fid);if ischar(tline), break, endif strcmp(tline,")continueendif strcmp(tline(1),D)Di,1=tline(5:end);i=i+1;endendfclose(fid);fid = fopen('B2007data/2.2地鐵 T2 線換乘公汽信息.txt','r');while 1tline

43、= fgetl(fid);if ischar(tline), break, endif strcmp(tline,")continueendif strcmp(tline(1),D)Di,1=tline(5:end);i=i+1;endendfclose(fid);tx=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25，26,12,27,28,29,30,31,32,18,33,34,35,36,37,38,39+3957;DL1,1="DL2,1="for j=1:23DL1,1=

44、strcat(DL1,1,'S',num2str(tx(j);endfor j=24:41DL2,1=strcat(DL2,1,'S',num2str(tx(j);endDL2,1=strcat(DL2,1,'S',num2str(tx(24);for i=1:1040for j=1:41tline=Dj,1;t=findstr(tline,'S');for k=1:length(t)Li,4=regexprep(Li,4,strcat('S',tline(t(k)+1:t(k)+4),strcat('S&

45、#39;,num2str(tx(j);endendendLt 仁L;Lt11041,1='T001'Lt11041,2=3;Lt11041,3=' 來回 1'Lt11041,4=DL1,1;Lt11042,1='T001：Lt11042,2=3;Lt11042,3=' 來回 2'Lt11042,4=DL1,1;Lt11043,1='T002'Lt11043,2=3;Lt11043,3=' 環(huán)行 1'Lt11043,4=strcat(DL2,1,DL2,1(6:end);Lt11044,1='T002

46、'Lt11044,2=3;Lt11044,3=' 環(huán)行 2'Lt11044,4=strcat(DL2,1,DL2,1(6:end);for i=1:1044tline=Lt1i,4;t=findstr(tline,'S');環(huán)行2')temp=zeros(1,length(t);if strcmp(Lt1i,3,'來回 2') | strcmp(Lt1i,3,'for j=length(t):-1:1temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4);endelsefor

47、 j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4);endendLt2i,1=temp;end5、N=87;M=3676;%直達(dá)if Time(N,M)=0temp=SN,M;for i=1:size(temp,1)disp(strcat('直達(dá)車為：L',num2str(temp(i,1)endreturnend clear U U2% 一次轉(zhuǎn)車t=1:3957;T2=Time(N,:).*Time(:,M)：if sum(T2)=0x=1;t=t(T2=0);for i=1:length(t)t1=SN,t(i);t

48、2=St(i),M;t1= double(t1);t2=double (t2);for j=1:size(t1,1)for k=1:size(t2,1)U(x,1)=1;%轉(zhuǎn)站次數(shù)總時間U(x,2)=(t1(j,3)+t2(k,3)*3+5+3;%U(x,3)=t(i);%轉(zhuǎn)站點U(x,4:5)=t1(j,1) t2(k,1);%車輛%是否始發(fā)站temp=0;for k1=1:1040if str2double(Lk1,1(2:end)=U(x,5)if L2k1,1(1,1)=t(i)temp=1;breakendendendU(x,6)=temp;U(x,7)=-sum(Time(:,t(

49、i)+.sum(Time(t(i),:);%人流負(fù)載U(x,8)=t1(j,2)+t2(k,2);%費用x=x+1;endendendreturnend%二次轉(zhuǎn)車t=1:3957;x=1;for i=1:3957if Time(N,i)=0for j=1:3957if Time(j,M)=0 && Time(i,j)=0t1=SN,i;t2=Si,j;t3=Sj,M;t1= double(t1);t2=double (t2);t3=double( t3);for k1=1:size(t1,1)for k2=1:size(t2,1)for k3=1:size(t3,1)U2(x,

50、1)=2;%轉(zhuǎn)站次數(shù)%總時間U2(x,2)=(t1(k1,3)+t2(k2,3)+t3(k3,3)*3+10+3;U2(x,3)=t(i);%轉(zhuǎn)站點U2(x,4)=t(j);%轉(zhuǎn)站點車輛1,2U2(x,5:6)=t1(k1,1) t2(k2,1);%是否始發(fā)temp=0;for kk=1:1040if str2double(Lkk,1(2:end)=U2(x,6)if L2kk,1(1,1)=t(i)temp=1;breakendendendU2(x,7)=t3(k3,1);%車輛 3%始發(fā)站數(shù)for kk=1:1040if str2double(Lkk,1(2:end)=U2(x,7)if

51、L2kk,1(1,1)=t(j)temp=temp+1;breakendendendU2(x,8)=temp;%人流量U2(x,9)=sum(Time(t(j),:)-.sum(Time(:,t(j)-.sum(Time(:,t(i)+.sum(Time(t(i),:);費用U2(x,10)=t1(k1,2)+t2(k2,2)+t3(k3,2);x=x+1;endendendendendendend6、N='S0087'M='S3676'%映射if strcmp(N(1),'S')for i=1:41t=findstr(Di,1,N);if is

52、empty(t)N=tx(i);breakendendif ischar(N)N=str2double(N(2:end);endendif strcmp(M(1),'S')for i=1:41t=findstr(Di,1,M);if isempty(t)M=tx(i);breakendendif ischar(M)M=str2double(M(2:end);endend%直達(dá)if Time(N,M)=0temp=SN,M;for i=1:size(temp,1)if temp(i,1)>1040disp(strcat('直達(dá)地鐵為：',Lt1temp(i,1),1)disp(strcat('直達(dá)汽車為：',Lt1temp(i,1),1)endendendclear U U2% 一次轉(zhuǎn)車t=1:3996;T2=Time(N,:).*Time(:,M)：if sum(T2)=0x=1;t=t(T2=0);for i=1:length(t)t1