【正文】 地鐵可以與哪些公交車換乘時(shí)，調(diào)用問題一中經(jīng)過可以換乘公汽車站的線路，如地鐵 T1在 D01車站可以換到三個(gè)公汽站點(diǎn) S0567，S0042， S0025，這說明 T11 可以在第 1 站與經(jīng)過 S0567， S0042， S0025的所有公汽線路，即集合 )()()( 2542567 SSBSSBSSB ?? 中的公汽線路實(shí)現(xiàn)換乘；而 T12 可以在其第 23 站與相同集合中的公汽線路進(jìn)行換乘 。 T23(D32— D18… D39— D24… D31) T24(D32— D31… D24— D39… D18)。 （ 2） 地鐵 T2 為環(huán)形線，我們?nèi)藶樘幚頌樗臈l線路： T11(D24— D25… D39)。 問題二原始數(shù)據(jù)處理 增加地鐵信息后，我們按照題目要求對原有的信息進(jìn)行了適當(dāng)?shù)奶幚?，具體描述如下： （ 1） 按照行駛方向不同，將地鐵 T1 人為處理為兩條線路： T11： D01D23；T12： D23D01。同時(shí)按照題中所給出的假設(shè)“ 同一地鐵站對應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘 (無需支付地鐵費(fèi) )”，在給出地鐵信息后，公汽線路的換乘矩陣需要進(jìn)行相應(yīng)的修改。 觀察所給的數(shù)據(jù)，地鐵線路的信息與公汽信息有所不同，公汽給出的是行走路線，而地鐵線路給出了每個(gè)地鐵站點(diǎn)可以換乘的公交線路。 c) 從人的心理出發(fā)，一些乘客在乘車時(shí)有時(shí)會(huì)以換乘次數(shù)少為選擇路線的標(biāo)準(zhǔn)，問題一的結(jié)果表明換乘次數(shù)少并不能夠得到最經(jīng)濟(jì) 或者 最節(jié)約時(shí)間的換乘方式，如 第三組站 點(diǎn)對 S0971→S0485 可以實(shí)現(xiàn) 換乘 一次 S0971→ S2184→S0485 ，但是需要 128 分鐘，費(fèi)用也為 3 元，此換乘方式與我們最終采用的二次換乘方式相比多用了 22 分鐘，而費(fèi)用完全相同；同樣 第 4 組也可以實(shí)現(xiàn)換乘一次S0008→ S0291→S0073 ，花費(fèi)時(shí)間 83 分鐘，費(fèi)用 2 元，與換乘兩次的最優(yōu)結(jié)果相比較，雖然少花 1 元，但是時(shí)間多用了 16 分鐘。通過檢驗(yàn)， 6 組站點(diǎn)對都不能實(shí)現(xiàn)直接達(dá)到，因此即使存在換乘一 次的線路，所需要的費(fèi)用至少為 2元，這與最終每個(gè)時(shí)間最短的最優(yōu)解花費(fèi) 3 元相比，相差不大，因此我們在求解過程中主要以時(shí)間最短為優(yōu)化目標(biāo)。 算法 II（ 給定公汽線路?？啃畔⒕仃嚒Q乘矩陣， 計(jì)算 任意起點(diǎn)到終點(diǎn)的 最優(yōu)路徑 ） ： 1) 輸入起點(diǎn) mS ，終點(diǎn) nS ， 對最短時(shí)間后者最小費(fèi)用變量賦初值 inf*?T ， inf*?C ，1?k ； 2) 按照 算法 1， 判斷 mS ， nS 是否在一條公汽線路 上 ，若在一條線路上， 1* TT? ，1* CC? ， MinL 存儲(chǔ)乘坐信息， 1??kk 否則轉(zhuǎn)下一步 ； 3) 寫出 )( mSSB ， )( mSSBFL? ； 4) 對任意的 FLLi? ，按照換乘矩陣寫出能夠與 iL 進(jìn)行換乘的所有線路 )( iLTR ， 按照 節(jié)命題 3 判斷 )( iLTR 中的線路能否實(shí)現(xiàn)一次換乘到 nS ； 5) 若存在能夠一次換乘到 nS 的線路，計(jì)算需要的最短時(shí)間或者最小費(fèi)用 kk CT, ，轉(zhuǎn) 6），否則轉(zhuǎn) 7）； 6) 若 kTT?* ，則 kTT ?* 或者若 kCC?* ，則 kCC ?* ， MinL 存儲(chǔ)換乘信息， 1??kk ，否則轉(zhuǎn) 7）； 7) 對于不能實(shí)現(xiàn)換乘一次到達(dá) nS 的線路 jL 中，計(jì)算 mS 通過 jL 能夠換乘到的線路得換乘點(diǎn) pS 需要的時(shí)間或者費(fèi)用， ),( pjm SLSTime 或者 ),( pjm SLSTCost ， 以 *T或者 *C 為標(biāo)準(zhǔn)判斷， 若 *),( TSLSTim e pjm ?或者 *),( CSLSTCost pjm ?，則從下一步搜索路線集合中刪去此換乘方式； 8) 令 FL 為 7）剩下的路線集合，返回 4）； 9) 輸出 *T 或者 *C ，以及換乘信息集合 MinL 。 ii. 在算法設(shè)計(jì)過程中，采用整數(shù)線性規(guī)劃的分 枝 定界思想，以換乘的次數(shù)為分 枝L1 L2 L3 Lj L1040 Lj tr(i,j) 9 變量，以已經(jīng)實(shí)現(xiàn)換乘情形下的時(shí)間或者費(fèi)用為定界變量， 實(shí)現(xiàn)在增加換乘 次數(shù)的同時(shí)判別沒有到達(dá) 終點(diǎn)的換乘序列是否可能達(dá)到最優(yōu)，即若當(dāng)前存儲(chǔ)實(shí)現(xiàn)成功換乘的最短時(shí)間或者最小費(fèi)用為 ? ，則以 ? 為剪枝標(biāo)準(zhǔn)，在沒有達(dá)到終點(diǎn)的線路中，如果所花費(fèi)的時(shí)間或者費(fèi)用已經(jīng)超過 ? ，則不需要進(jìn)一步換乘尋找。 求解問題一的算法 由于上述最短路問題中所涉及的數(shù)據(jù)量較大，并且不同于傳統(tǒng)最短路問題之處在于在圖中我們得到的并不是相鄰兩點(diǎn)的路徑，而是可以換乘的兩條線路換乘 的信息，因此不能直接用求解傳統(tǒng)最短路問題的算法，如 Dijstra算法進(jìn)行計(jì)算。 8 圖 2 所有公汽線路的換乘圖 需要說明的是，由于 ),( jitr 與 iL 與 jL 的順序有關(guān)，因此在后續(xù)提出的動(dòng)態(tài)規(guī)劃模型中，將按照計(jì)算的次序與換乘線路的先后次序?qū)Q乘圖配上 不同的方向，這些方向與計(jì)算),( jitr 以及花費(fèi)的時(shí)間與費(fèi)用有關(guān)。 命題 5：若乘客從 mS 出發(fā)，通過換乘線路 ipii LLL ??? ?21 ，到達(dá) nS ，則 必存在 1?p 個(gè)換 乘數(shù)對 ),(,),(),( 112211 ?? pp bababa ?使得： （ a） 1),1( ?miLS ， 1),( ?nipLS ； （ b） )),1((),(,),3,2(),(),2,1(),( 112211 ippitrbaiitrbaiitrba pp ???? ??? （ c） ),(,),1( 11232211 nipL S NbabababamiL S N ppp ????? ???? 同時(shí)花費(fèi)的時(shí)間 ),( 1 nipim SLLSTim e ?為 bbppp TpnipL SNbipT imabpiT imabiT imamiL SNiT im )1()),(,(),),1((),2()),1(,( 112211 ??????? ????花費(fèi)的費(fèi)用 ),( 1 nipim SLLST C ost ?為 )),(,(),),1((),2()),1(,( 112211 nipL S NbipC o s tabpiC o s tabiC o s tamiL S NiC o s t ppp ??? ????? ?。 命題 4：若 mS 經(jīng)由 iL 轉(zhuǎn)乘 kL 再轉(zhuǎn)乘 jL 到 nS ， 而 ),( kitr ， ),( jktr 分別為 iL 到 kL ， kL到 jL 的換乘數(shù)對集合，則必存在 ),(),( 11 kitrba ? ， ),(),( 22 jktrba ? 使得 1),(,1),( ?? njLSmiLS ， 2121 ,),(,),( abbnjL S NamiL S N ??? ， 7 同時(shí)，花費(fèi)時(shí)間 ),( njkim SLLLSTim e 為 bbTnjL S NbjT imabkT imamiL S NiT im 2)),(,(),()),(,( 2211 ??? 花費(fèi)費(fèi)用 ),( njkim SLLLST C ost 為 )),(,(),()),(,( 2211 njL S NbjC o s tabkC o s tamiL S NiC o s t ??。 同時(shí) ,花費(fèi)時(shí)間 ),( njim SLLSTime為 ： bbTnjL S NbjT imamiL S NiT im ?? )),(,()),(,( ， 其中 bbT 表示公汽換乘公汽的時(shí)間 ，在本題取值為 5?bbT 。 同時(shí)集合 }),(|{)( ??? jitrLLTF ji 表示能夠與 iL 實(shí)現(xiàn)直接換乘的線路集合。 注意到換乘數(shù)對與換乘線路之間的關(guān)系，若 ),( ba 為線路 iL 到 jL 的換乘數(shù)對，則),( ab 為線路 jL 到 iL 的換乘數(shù)對 。 定義：設(shè) iL 與 jL 在 kS 處相交， ji? , kS 在 iL 上為第 a 站， ),( kiLSNa? ，在 jL 上為第 b 站， ),( kjLSNb? ，則稱二元數(shù)對 ),( ba 為線路 iL 到 jL 的 換乘 數(shù)對，記}),(|),{(),( 的一個(gè)換乘數(shù)對到線路為線路 ji LLbabajitr ? 。 證明：按照?？肯蛄康亩x， ji LL, 均為元素為 0 或者 1 的向量。同時(shí)可以得到 花費(fèi)的時(shí)間),( nim SLSTime 為 )),(),((3)),(),(,( miL S NniL S NniL S NmiL S NiT im ?? 花費(fèi)的車費(fèi) ),( nim SLSTCost 為 )),(),(,( niL S NmiL S NiC o st 。 相應(yīng)于費(fèi) 用函數(shù)，用函數(shù) )(),( abTbaiTim bb ?? 表示從該線路的第 a 站到第 b 站的時(shí)間函數(shù)，其中 bbT 表示相鄰公汽站平均行駛時(shí)間，在本題中取值為 3?bbT 。 可以發(fā)現(xiàn)單一收費(fèi)情形可以并入上述公式，因此 所有公汽線路（包括單一收費(fèi)與分段收費(fèi)）的費(fèi)用計(jì)算可以合并為一個(gè)函數(shù) 1),( ?? kcbaiCost i，其中 )2,20 1m in( ??? abk 。 （ 3）每條線路的計(jì)費(fèi)信息 定義向量 ),( 1 0 4 021 cccC ?? 為每條線路的計(jì)費(fèi)信息， 按照題中所給出的計(jì)費(fèi)信息，元素取值為 ???? 條線路為分段計(jì)費(fèi)第 條線路為單一計(jì)費(fèi)第 iic i 10 。 定義向量 :),(iLSLi ? 為線路 iL 的停靠向量 ， )( iLLB 為線路 iL 停靠的站點(diǎn)集合 ：}1),(|{)( ?? jiLSSLLB ji 。 LS 為 1040 行 3957 列的矩陣，元素為 0 或者 1，反 映 每條線路是否經(jīng)過每個(gè)站點(diǎn) ，元素取值為 ： ????jiji SL SLjiLS 不經(jīng)過站點(diǎn)線路 經(jīng)過站點(diǎn)線路01),( 。 圖 1 通過以上處理，我們將所有情況統(tǒng)一轉(zhuǎn)化為以起點(diǎn)和終點(diǎn)確定的 1040 條 具有單一方向的 有向線段 。具體的處理方法如下： a) 對于上行與下行站點(diǎn) 相同 的線路 ，如 圖 1 中 (a)，將上行與下行視為不同的兩條線路，每一條作為一條新的單方向行駛的公交線路 ，即 BA? 及 AB? ； 由于兩個(gè)走向站點(diǎn)相同，因此這兩條線路經(jīng)過的站點(diǎn)集合相同，但是每個(gè)站點(diǎn)在兩條線路中的位置不同，這對衡量從某個(gè)站點(diǎn)出發(fā)乘坐該線路是否可以換乘其他線路，以及換乘哪條線路非常重要（詳細(xì)說明見后續(xù)命題）； b) 對于 上行與下行站點(diǎn)不 同的 線路 ，如圖 1 中 (b)， 將上行方向與下行方向視為兩個(gè)不同的線路 BA? 及 AB? ，這兩條線路經(jīng)過的站點(diǎn)集合不同，從而每個(gè)站點(diǎn)在兩條線路中的站點(diǎn)位置也不同 ； c) 對于環(huán)形線路， 如圖 1 中 (c)，起點(diǎn)與終點(diǎn)為 A 的環(huán)形道路， 從中間某個(gè)站點(diǎn)斷開，作為前一路線的終點(diǎn)以及后一路線的起點(diǎn)，這樣就形成兩條新的線路 。進(jìn)而 我們 可以使用 通過動(dòng)態(tài)規(guī)劃 方法、最短路方法等建模思想構(gòu)造算法、編寫 程序 ， 使問題得到圓滿地解決。 描述公交線路網(wǎng)絡(luò)的一個(gè)簡單方法是以每個(gè)站點(diǎn) 為頂點(diǎn)，以兩個(gè)頂點(diǎn)之間的公交線路信息（需要花費(fèi)的時(shí)間、花費(fèi)的費(fèi)用等）為弧建立賦權(quán)圖，本題中站點(diǎn)個(gè)數(shù)共有 3957個(gè)，這樣得到的矩陣將是 3957階方陣，如此龐大的矩陣在使用計(jì)算機(jī)處理時(shí)，將會(huì)遇到很大的困難，我們所擁有的計(jì)算機(jī)硬件達(dá)不到要求。 有的結(jié)點(diǎn)之間有邊相連 (即在某一條公交線上 ) , 有的結(jié)點(diǎn)之間無邊相連 (即這兩個(gè)結(jié)點(diǎn)不在任何一條公交線上 )。 四、 符號(hào)說明及定義 ： ),( jiLS ： 衡量每條線路在每個(gè)站點(diǎn)是否?？康?0— 1 矩陣； ),( jiLSN ：衡量每條線路 經(jīng)過 的每個(gè)站點(diǎn)是從起點(diǎn)起 算 的第幾站 的矩陣 ； :),(iLSLi ? ：線路 iL 的?？空军c(diǎn)向量 C ：存儲(chǔ) 每條 線路的收費(fèi)信息； )( iSSB ：停靠 iS 的所有公交線路的集合； )( iLLB ： 線路 iL 停靠的所有站點(diǎn)； ),( baiCost ：乘坐 iL 從其第 a 站到第 b （ ab? ）站的費(fèi)用 )(),( abTbaiTim bb ?? ：表示從線路 iL 的第 a 站到第 b 站的時(shí)間函數(shù) bbT ：表示相鄰公汽站平均行駛時(shí)間 ，本題為 3 ),( nm SSTime ? ：從站點(diǎn) mS 經(jīng)過 一系列線路到達(dá) nS 的總時(shí)間 ),( nm SSTCost ? ：從站點(diǎn) mS 經(jīng)過一系列線路到達(dá) nS 的總費(fèi)用 TR ：所有線路的轉(zhuǎn)乘矩陣 ),( jitr ：公交線路 iL ， jL 兩兩 轉(zhuǎn)乘集合 ； V ：為 所 有站點(diǎn) 集合； E ： 有向圖中表示兩個(gè)站點(diǎn)之間最短距離（最少時(shí)間或者最少費(fèi)用）信息 五、 問題一建模與求解 一個(gè)城市所有的公交線路和停車點(diǎn)構(gòu)成了一個(gè)復(fù)雜的網(wǎng)絡(luò)圖 , 這些停車點(diǎn)可以看作該網(wǎng)絡(luò)圖的結(jié)點(diǎn) , 這些結(jié)點(diǎn)由相應(yīng)的公交路線相連 。問題三增加步行信息后，問題變得較為復(fù)雜，因?yàn)槲覀儾⒉恢涝谀男┑胤綄?huì)步行，因此我們采用簡單列舉的方法建立模型。 （ 5） 問題一僅對公共汽車進(jìn)行分析，可以轉(zhuǎn)化為一個(gè)圖論問題，使用動(dòng)態(tài)規(guī)劃方法進(jìn)行算法設(shè)計(jì)與計(jì)算。 （ 4） 在公交線路信息中，與決策目標(biāo)有關(guān)的元素還有每條線路的計(jì)費(fèi)方式 及每 條線路乘坐時(shí)花費(fèi)的時(shí)間。 （ 3） 在給出的線路信息中，我們發(fā)現(xiàn)主要 有三類線路：下行線路與上行線路