航空航天乘公交看奧運(yùn)方案設(shè)計(jì)

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

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

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

4、們準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢(xún)計(jì)算機(jī)系統(tǒng),關(guān)鍵在于線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢(xún)者的各種不同需求。具體問(wèn)題如下:1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問(wèn)題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站終到站之間的最佳路線（要有清晰的評(píng)價(jià)說(shuō)明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同時(shí)考慮公汽與地鐵線路，解決以上問(wèn)題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意

5、兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型?；緯r(shí)間參數(shù)設(shè)定:相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)公汽換公汽平均耗時(shí)/(步行時(shí)間)地鐵換地鐵平均耗時(shí)/(步行時(shí)間)公汽換地鐵平均耗時(shí)/(步行時(shí)間)地鐵換公汽平均耗時(shí)/(步行時(shí)間)時(shí)間(分鐘)32.55/(2)4/(2)6/(4)7/(4)即:換乘公汽等待分鐘，換乘地鐵等待分鐘.公汽站地鐵站（通道）公汽站.換乘耗時(shí)11分鐘：步行4+4=8分鐘, 等車(chē)3分鐘.公交票價(jià)方式基本票價(jià)參數(shù)設(shè)定:單一計(jì)價(jià)分段計(jì)價(jià)公汽1元020站：1元；2140站：2元；40站以上：3元地鐵3元（無(wú)論地鐵線路間是否換乘）公交線路及相關(guān)信息 （見(jiàn)數(shù)

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

7、，并且是雙向的,并且經(jīng)過(guò)終點(diǎn)后 要重新收費(fèi);5、假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過(guò)地鐵站換乘，且無(wú)需支付地鐵費(fèi)；6、人們對(duì)換乘車(chē)次數(shù)盡量少的偏好程度總是大于對(duì)花費(fèi)時(shí)間相對(duì)短和花費(fèi)金錢(qián)相對(duì)少的偏好程度;7 初始等車(chē)時(shí)間2(或3)min也不包括在內(nèi);8、 同一公交線的往返路線視為兩條單行線;9、 考慮兩地鐵之間不通過(guò)公汽乘換（即只：公汽站地鐵站（通道）公汽站）。四、模型建立:對(duì)于公交線路選擇，我們主要考、慮乘換次數(shù)、費(fèi)用、時(shí)間各因素最優(yōu)。 在線路選擇問(wèn)題中，將公交路線關(guān)系抽象成一個(gè)有向賦權(quán)圖，當(dāng)從i可直達(dá)j時(shí)（同為公汽或地鐵站點(diǎn)），定義弧(i,j)；其上的權(quán)為：。表示由i直達(dá)j付出的代

8、價(jià)，可以為時(shí)間或費(fèi)用 (不包括換乘代價(jià)；多條線路可達(dá)時(shí)只保留最小代價(jià))； 公交乘換方式：公汽公汽，公汽地鐵，地鐵公汽，地鐵地鐵，公汽地鐵公汽。 A） i站點(diǎn)是公汽站點(diǎn)，j站點(diǎn)為地鐵站點(diǎn)：（1）若j站點(diǎn)對(duì)應(yīng)的所有換乘(公汽)站點(diǎn)k，均不能從i直達(dá)(不在i站點(diǎn)所在公汽線路L上)，則 =;（2） 若j站點(diǎn)對(duì)應(yīng)的換乘（公汽）站點(diǎn)k, 可從i站點(diǎn)直達(dá)k，則費(fèi)用為 = ； 注：對(duì)于時(shí)間則需要加上k到j(luò)的步行時(shí)間. (若有多種選擇，取最小成本者即可)B） j站點(diǎn)是公汽站點(diǎn)，i站點(diǎn)為地鐵站點(diǎn)：（1）若從i站點(diǎn)對(duì)應(yīng)的任何換乘(公汽)站點(diǎn)k，均不能直達(dá)j站點(diǎn)，則 =. （2）若從i站點(diǎn)對(duì)應(yīng)的換乘(公汽)站點(diǎn)k，能

9、直達(dá)j站點(diǎn)， 則費(fèi)用為 =；注：對(duì)于時(shí)間則需要加上i到k的步行時(shí)間.定義：矩陣算子“”如下：設(shè)D（k-1）、D均為n階方陣， D(k) = D（k-1） D (考慮換乘代價(jià))當(dāng)考慮費(fèi)用矩陣間的運(yùn)算時(shí)，=0；當(dāng)考慮時(shí)間矩陣間的運(yùn)算時(shí)，表示在k的換乘時(shí)間。 D(k)= D(k-1)D表示k次換乘的最低代價(jià)(費(fèi)用或時(shí)間)，即通過(guò)修改floyd算法求解。i,j,k表示換乘時(shí)間 ：i = j 或k = i，j時(shí)，i,j,k = 0其他情形：若不可換乘(當(dāng)i ，j為公汽站點(diǎn)而k為地鐵站點(diǎn)，或者i ，j為地鐵站點(diǎn)而k為公汽站點(diǎn)時(shí))，則 i,j,k = 0若可換乘，則：?jiǎn)栴}一模型 ： 因?yàn)閮H考慮公汽線路，為了

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

11、同樣，將題中所提供的公汽（含地鐵轉(zhuǎn)換的公汽）網(wǎng)絡(luò)抽象成一個(gè)有向賦權(quán)圖,建立直達(dá)矩陣D =。算法設(shè)計(jì)基本與模型一相當(dāng)。 當(dāng)D為時(shí)間直達(dá)矩陣時(shí)，按D(k)= D(k-1) D式重復(fù)地進(jìn)行運(yùn)算得到，當(dāng)，時(shí)，表示從 i站點(diǎn)到 j站點(diǎn)最少換乘k次能夠到達(dá)，且即表示換乘k次到達(dá)所需的最短時(shí)間。 當(dāng)D為費(fèi)用直達(dá)矩陣時(shí)，按D(k)= D(k-1) D重復(fù)地進(jìn)行運(yùn)算得到，運(yùn)算適當(dāng)次數(shù)后若 D(k)= D(k-1)，則表示已得到所有站點(diǎn)間的最小費(fèi)用，即表示從i站點(diǎn)到j(luò)站點(diǎn)所需的最少費(fèi)用。根據(jù)最少乘換次數(shù)等約束條件，再利用圖的鄰接搜索法可得出兩站點(diǎn)之間的選擇線路。問(wèn)題三模型：?jiǎn)栴}三是在模型二的基礎(chǔ)上添加步行時(shí)間進(jìn)行

12、考慮。 優(yōu)先考慮乘換次數(shù)。對(duì)直達(dá)時(shí)間矩陣按D(k)= D(k-1) D式重復(fù)地進(jìn)行運(yùn)算得到，當(dāng)，時(shí)，表示從 i站點(diǎn)到 j站點(diǎn)最少換乘k次能夠到達(dá)。在運(yùn)算過(guò)程中可記錄下?lián)Q乘站點(diǎn)信息，隨之可得到相關(guān)線路信息。若有若干條最小換乘路線，則比較另外兩個(gè)目標(biāo)選擇最佳線路（即建立0-1整數(shù)規(guī)劃模型）。 設(shè)共有m條單行公交線，構(gòu)造一個(gè)m+2個(gè)點(diǎn)構(gòu)成的完全圖。 點(diǎn)：a為起點(diǎn)（出發(fā)點(diǎn)），b為終點(diǎn)（目的地），此外每條公交線也視為一個(gè)點(diǎn)。 邊：邊表示兩點(diǎn)之間的步行關(guān)系。 邊權(quán)：步行時(shí)間為邊權(quán)。針對(duì)不同的邊可分為上車(chē)前、下車(chē)后和換車(chē)時(shí)步行時(shí)間，構(gòu)成步行時(shí)間矩陣 。行：依次表示的是m條公交線與起點(diǎn)，列：依次表示的是m條公

13、交線與終點(diǎn)。 點(diǎn)權(quán)：第個(gè)公交線點(diǎn)還有三個(gè)信息為點(diǎn)權(quán)。 1）公交線名稱(chēng)及上行或下行； 2）類(lèi)型及票價(jià)方式； 3）乘車(chē)站數(shù)表矩陣 ，其中 表示從c到d經(jīng)過(guò)i號(hào)公交線時(shí)需要乘車(chē)的站數(shù),c到d利用不上i時(shí)取無(wú)窮大。這個(gè)矩陣的行列表示用S。 于是原問(wèn)題轉(zhuǎn)化為在這個(gè)圖上求a到b的最短路。 最短的可以理解為換乘車(chē)數(shù)最少、乘車(chē)的總站數(shù)最少、總的步行時(shí)間最少、總車(chē)費(fèi)最少這樣幾個(gè)目標(biāo)的各種組合方式。 可以用0-1整數(shù)規(guī)劃解決這個(gè)問(wèn)題，方法是分出恰乘一次公交車(chē)，恰乘兩次公交車(chē)，恰乘三次公交車(chē)等等情況分別求出下列模型解然后比較得出最優(yōu)解。 優(yōu)化模型：恰乘一次公交車(chē)的模型如下：變量全部是0-1變量，共有3*(m)個(gè)。

14、表示選不選擇去第i條公交線的路；表示選不選擇乘第i線公交車(chē)；表示選不選擇從第i條公交車(chē)下車(chē)后走到目的地的路。 (它們都是取1表示選擇而取0表示不選擇。)恰乘一次公交車(chē)的模型如下： 目標(biāo)函數(shù)：據(jù)用戶選擇的情況用點(diǎn)權(quán)和邊權(quán)構(gòu)造，共同點(diǎn)都是最小值。 ( 1)步行時(shí)間最少: 目標(biāo)函數(shù) (2)總時(shí)間最少: 目標(biāo)函數(shù) 其中，(3)車(chē)費(fèi)最少: 目標(biāo)函數(shù)：約束條件（共2m+1個(gè)）：只選擇一條公交線； 要乘第i條公交線就要走相應(yīng)的兩條路。恰乘兩次公交車(chē)的模型如下：步行時(shí)間:時(shí)間最少：費(fèi)用最少：約束條件： 可以選擇兩條公交線路； 乘公交線要走的兩條相應(yīng)的路線。恰乘乘三次公交車(chē)模型:步行時(shí)間的目標(biāo)函數(shù)在的基礎(chǔ)上添加

15、;時(shí)間最少的目標(biāo)函數(shù)在的基礎(chǔ)上添加;費(fèi)用最少:約束條件即在的基礎(chǔ)上添加的變量即可。五、模型求解:問(wèn)題一：由于題目所給的公交乘路信息是.txt文本文件，為了將實(shí)際問(wèn)題能用數(shù)學(xué)模型來(lái)解決，我們編寫(xiě)程序?qū)⑵鋵?dǎo)入matlab。（程序見(jiàn)附錄1）。對(duì)于問(wèn)題1，我們僅僅考慮公汽線路，為此，我們將所有的公汽路線與站點(diǎn)（3957個(gè)）關(guān)系構(gòu)成一個(gè)圖網(wǎng)，為了求得最小代價(jià)的選擇路線，我們先建立起直達(dá)矩陣（程序見(jiàn)附錄2），再由改進(jìn)floyd算法（程序見(jiàn)附錄3）即可求出兩公汽站點(diǎn)之間線路選擇的最小代價(jià)（乘換次數(shù)、時(shí)間最短、費(fèi)用最少），乘換次數(shù)為主、時(shí)間最短和費(fèi)用最少為次為約束條件用搜索法（見(jiàn)附錄程序5）搜出最優(yōu)線路，具體

16、結(jié)果如下所示：起點(diǎn)站終點(diǎn)站乘換次數(shù)時(shí)間（分鐘）車(chē)費(fèi)（元）線路S3359S18281893S1557S048121123S0971S048511193S0008S00731832S0148S048521063S0087S36762523問(wèn)題二：對(duì)于問(wèn)題2，我們?cè)诳紤]公汽線路的同時(shí)，還需將地鐵線路（2條地鐵線路，39個(gè)地鐵站點(diǎn)）考慮進(jìn)去，同樣，將所提供的公汽（含地鐵轉(zhuǎn)換的公汽）網(wǎng)絡(luò)抽象成一個(gè)有向賦權(quán)圖,建立直達(dá)矩陣（程序見(jiàn)附錄4），再由改進(jìn)floyd算法（程序見(jiàn)附錄3）即可求出兩公汽站點(diǎn)之間線路選擇的最小代價(jià)（乘換次數(shù)、時(shí)間最短、費(fèi)用最少），以換乘次數(shù)為主、時(shí)間最短與費(fèi)用最少為次為約束條件用搜索法

17、（見(jiàn)附錄程序6）搜出最優(yōu)線路，具體結(jié)果如下所示：起點(diǎn)站終點(diǎn)站乘換次數(shù)時(shí)間（分鐘）車(chē)費(fèi)（元）線路S3359S18281893S1557S048121123S0971S048511193S0008S00731832S0148S048521063S0087S36760503問(wèn)題三：?jiǎn)栴}3又增設(shè)了所有站點(diǎn)之間的步行時(shí)間，為了給出任意兩站點(diǎn)之間線路選擇問(wèn)題的數(shù)學(xué)模型。我們則考慮大眾化的想法（優(yōu)先考慮乘換次數(shù)）：1若兩個(gè)站點(diǎn)之間有直達(dá)的公交車(chē)，若只有一條，我們毫無(wú)條件地選擇；若不止一條，則我們可以利用模型三的優(yōu)化模型進(jìn)行時(shí)間和費(fèi)用的比較，取最優(yōu)解；2同理，若要經(jīng)過(guò)轉(zhuǎn)乘一次、二次等轉(zhuǎn)乘情況，若轉(zhuǎn)乘線路只有一

18、種，則選擇之；若轉(zhuǎn)乘線路有多種，則利用模型三的優(yōu)化模型進(jìn)行時(shí)間和費(fèi)用的比較，取最優(yōu)解。六、模型優(yōu)缺點(diǎn):將公交圖網(wǎng)能用有向賦權(quán)圖并建立直達(dá)矩陣，再利用最短路算法及搜索算法得出線路選擇的最優(yōu)線路（含時(shí)間最少、費(fèi)用最少等）；對(duì)于第三問(wèn)題中的模型，在加入步行時(shí)間后，我們能考慮到在乘換次數(shù)最少為優(yōu)先的條件下，利用優(yōu)化模型進(jìn)行比較是全面些。鑒于公交系統(tǒng)網(wǎng)絡(luò)的復(fù)雜性，我們雖然采用了修改floyd算法，編譯運(yùn)行上不太好，有待改進(jìn)。7、 參考文獻(xiàn):1蔡志杰，丁頌康 數(shù)學(xué)工程學(xué)報(bào)-公交線路選擇模型 2007年12月 1005-3085（2007）08-0117-042朱參世 一種 Warshall和 Fl oyd

19、算法的優(yōu)化方法研究 2010年第四期 1006-2475（2010）04-0043-033劉韻，何建農(nóng) 基于交通網(wǎng)絡(luò)最短路徑搜索的改進(jìn)算法 2007年 1002-8331（2007）14-0220-03附錄:function A = T_SORT( A ,n , p )%建立排序函數(shù)% 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,:),&

20、#39;descend');for i=1:SIZE(1)A(i,:)=A(i,idx);endend1、%數(shù)據(jù)處理讀入matlab：%讀取數(shù)據(jù) clear L a fid = fopen('1.1 公汽線路信息.txt','r'); i=1; while 1 tline = fgetl(fid); if ischar(tline), break, end if strcmp(tline,'') continue end if strcmp(tline(1),'L') str=tline; continue elseif

21、strcmp(tline,'END') break end if strcmp(tline,'單一票制1元。') P=1; continue elseif strcmp(tline,'分段計(jì)價(jià)。') P=2; continue end if strcmp(tline(1:2),'上行') Li,1=str; Li,2=P; Li,3='上行' Li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),'下行') Li,1=str; Li,

22、2=P; Li,3='下行' Li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),'環(huán)行') Li,1=str; Li,2=P; Li,3='環(huán)行1' Li,4=strcat(tline(4:end),tline(10:end); i=i+1; %計(jì)算來(lái)回 Li,1=str; Li,2=P; Li,3='環(huán)行2' Li,4=strcat(tline(4:end),tline(10:end); i=i+1; continue elseif strcmp(tline(

23、1),'S') Li,1=str; Li,2=P; Li,3='來(lái)回1' Li,4=tline; i=i+1; %計(jì)算來(lái)回 Li,1=str; Li,2=P; Li,3='來(lái)回2' Li,4=tline; i=i+1; continue end endfclose(fid);for i=1:size(L,1) tline=Li,4; t=findstr(tline,'S'); temp=zeros(1,length(t); if strcmp(Li,3,'來(lái)回2') | strcmp(Li,3,'環(huán)行2&#

24、39;) for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4); end else for j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4); end end L2i,1=temp; end for i=1:3957 if floor(i/10)=0 Citi=strcat('S000',num2str(i); elseif floor(i/100)=0 Citi=strcat('S00',num2str(i);

25、elseif floor(i/1000)=0 Citi=strcat('S0',num2str(i); else Citi=strcat('S',num2str(i); end end Cit3958='D01：S0567，S0042，S0025' Cit3959='D02：S1487' Cit3960='D03：S0303，S0302' Cit3961='D04：S0566' Cit3962='D05：S0436，S0438，S0437，S0435' Cit3963='D0

26、6：S0392，S0394，S0393，S0391' Cit3964='D07：S0386，S0388，S0387，S0385' Cit3965='D08：S3068，S0617，S0619，S0618，S0616' Cit3966='D09：S1279' Cit3967='D10：S2057，S0721，S0722，S0720' Cit3968='D11：S0070，S2361，S3721' Cit3969='D12：S0609，S0608' Cit3970='D13：S2633，

27、S0399，S0401，S0400' Cit3971='D14：S3321，S2535，S2464' Cit3972='D15：S3329，S2534' Cit3973='D16：S3506，S0167，S0168' Cit3974='D17：S0237，S0239，S0238，S0236，S0540' Cit3975='D18：S0668' Cit3976='D19：S0180，S0181' Cit3977='D20：S2079，S2933，S1919，S1921，S1920

28、9; Cit3978='D21：S0465，S0467，S0466，S0464' Cit3979='D22：S3457' Cit3980='D23：S2512' Cit3981='D24：S0537，S3580' Cit3982='D25：S0526，S0528，S0527，S0525' Cit3983='D26：S3045，S0605，S0607' Cit3984='D27：S0087，S0088，S0086' Cit3985='D28：S0855，S0856，S0854，

29、S0857' Cit3986='D29：S0631，S0632，S0630' Cit3987='D30：S3874，S1426，S1427' Cit3988='D31：S0211，S0539，S0541，S0540' Cit3989='D32：S0978，S0497，S0498' Cit3990='D33：S1894，S1896，S1895' Cit3991='D34：S1104，S0576，S0578，S0577' Cit3992='D35：S3010，S0583，S0582

30、9; Cit3993='D36：S3676，S0427，S0061，S0060' Cit3994='D37：S1961，S2817，S0455，S0456' Cit3995='D38：S3262，S0622' Cit3996='D39：S1956，S0289，S0291'2、%建立公汽間的直達(dá)矩陣clear SS(1:3957,1:3957)=zeros(1,1,'uint16');%按UInt16格式 建立1行1 列的零巨陣for i=1:1040 t=L2i,1; for j=1:length(t)-1 for

31、 k=j+1:length(t) temp=St(j),t(k); str=Li,1; n,m=size(temp); if n=1 && temp(1,1)=0 temp(n,1)=str2double(str(2:end); if Li,2=2 if (k-j)>40 temp(n,2)=3; elseif (k-j)>20 temp(n,2)=2; else temp(n,2)=1; end else temp(n,2)=1; end temp(n,3)=k-j; else temp(n+1,1)=str2double(str(2:end); if Li,2=

32、2 if (k-j)>40 temp(n+1,2)=3; elseif (k-j)>20 temp(n+1,2)=2; else temp(n+1,2)=1; end else temp(n+1,2)=1; end temp(n+1,3)=k-j; end St(j),t(k)=temp; end endendfor i=1:3957 for j=1:3957 if length(Si,j)=1 Si,j=T_SORT(Si,j',3,1)' end endendTime=zeros(3957,3957,'uint8');for i=1:3957 f

33、or j=1:3957 if length(Si,j)=1 Time(i,j)=size(Si,j,1); end endendTT=zeros(3957,3957,'uint8');for i=1:3957 for j=1:3957 temp=Si,j; if temp(1,1)=0 TT(i,j)=temp(1,3); end endEnd%時(shí)間、費(fèi)用的直達(dá)矩陣(換乘直達(dá)線路數(shù)矩陣)ee,rr=size(S); ss=zeros(ee); for i=1:ee for j=1:rr if Si,j=0 ss(i,j)=length(Si,j(:,1); end end en

34、d for i=1:ee for j=1:rr if ss(i,j)=0; ss(i,j)=Inf; end end end for i=1:ee for j=1:rr if i=j; ss(i,j)=0; end end end2.2 (間直達(dá)矩陣)ee,rr=size(S); ttt=zeros(ee); for i=1:ee for j=1:rr if Si,j=0 ttt(i,j)=min(Si,j(:,3); end end end for i=1:ee for j=1:rr if ttt(i,j)=0; ttt(i,j)=Inf; end end end for i=1:ee fo

35、r j=1:rr if i=j; ttt(i,j)=0; end end end2.3 (費(fèi)用直達(dá)矩陣)ee,rr=size(S); ppp=zeros(ee); for i=1:ee for j=1:rr if Si,j=0 ppp(i,j)=min(Si,j(:,2); end end end for i=1:ee for j=1:rr if ppp(i,j)=0; ttt(i,j)=Inf; end end end for i=1:ee for j=1:rr if i=j; ppp(i,j)=0; end end end3、%算子算法function D,path,k,min1,path

36、1=floyd(a,start,terminal)D=a;n=size(D,1);path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end, end, endwhile 1<=j<=nfor k=1:n DO(k,j)=D(k,j); endendfor k=1:n for i=1:n for j=1:n if D(i,k)+DO(k,j)<D(i,j) D(i,j)=D(i,k)+DO(k,j); path(i,j)=path(i,k); end if D(i,k-1)+DO(k-1,j)<D

37、(i,j) D(i,j)=inf; if D(i,k)+DO(k,j)<D(i,j) D(i,j)=inf; k end,end end endendif nargin=3 min1=D(start,terminal); m(1)=start; i=1; path1= ; while path(m(i),terminal)=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m;end4、%考慮地鐵的直達(dá)矩陣fid = fopen('B2007data/2.1 地鐵T1線換乘公汽信

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

39、 if ischar(tline), break, end if strcmp(tline,'') continue end if strcmp(tline(1),'D') Di,1=tline(5:end); i=i+1; end end fclose(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=&#

40、39;' for j=1:23 DL1,1=strcat(DL1,1,'S',num2str(tx(j); end for j=24:41 DL2,1=strcat(DL2,1,'S',num2str(tx(j); end DL2,1=strcat(DL2,1,'S',num2str(tx(24); for i=1:1040 for j=1:41 tline=Dj,1; t=findstr(tline,'S'); for k=1:length(t) Li,4=regexprep(Li,4, strcat('S

41、9;,tline(t(k)+1:t(k)+4),. strcat('S',num2str(tx(j); end end end Lt1=L; Lt11041,1='T001' Lt11041,2=3; Lt11041,3='來(lái)回1' Lt11041,4=DL1,1; Lt11042,1='T001' Lt11042,2=3; Lt11042,3='來(lái)回2' Lt11042,4=DL1,1; Lt11043,1='T002' Lt11043,2=3; Lt11043,3='環(huán)行1' L

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

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