公共交通網(wǎng)絡(luò)模型公共交通網(wǎng)絡(luò)模型第一組：劉毅張學(xué)令鄭榕嬌摘要北京申奧的成功，給北京的交通帶來了巨大的影響。本文就公交線路的選擇問題，采用廣度優(yōu)先搜索的理論與方法建立了公共交通網(wǎng)絡(luò)模型，并提出了滿足公交乘客各種不同需求的快速算法，針對實際問題給出了最優(yōu)路徑。對于問題（1），首先根據(jù)公共交通網(wǎng)絡(luò)的特點，把公交網(wǎng)絡(luò)模型映射為一個無向圖來表示公交線路及站點分布情況。結(jié)合圖論中的廣度優(yōu)先搜索方法并對其進(jìn)行改進(jìn)，即從起點和終點同時搜索，找出起點與終點的所有可行路徑（包括直達(dá)、一次換乘、兩次換乘的情況），再分別求出每條路徑的耗時、花費及換乘次數(shù)進(jìn)行比較，選出最優(yōu)路徑。對于問題（2），同時考慮公汽與地鐵線路時，可以將可換乘的地鐵站和公汽站視為對等的，這樣就與第一問相同了，可利用相同的方法來解決。對于問題（3），考慮步行，通過對時間加一個閾值（乘客可以容忍的步行時間），通過Floyd算法求出任意兩站點間的最短步行時間，并與閾值進(jìn)行比較，建議乘客是否應(yīng)該步行。該模型的創(chuàng)新點在于克服了廣度優(yōu)先搜索盲目搜索的缺點，采取從起點和終點同時搜索的方法，大大提高了搜索效率；同時為了更全面的考慮問題，我們分別以行程耗時、花費與換乘次數(shù)為優(yōu)先考慮，找出了最優(yōu)路徑，以滿足公交乘客的各種不同需求；最后結(jié)合乘客都會盡量選擇有座位的公交的實際情況對模型進(jìn)行了改進(jìn)。關(guān)鍵詞：公交網(wǎng)絡(luò)，廣度最優(yōu)搜索，最優(yōu)路徑，F(xiàn)loyd算法，MATLAB1.問題的重述北京申奧的成功，對北京市的交通系統(tǒng)提出了更高的要求。奧運期間交通狀況是否良好，交通管理是否高效，是關(guān)系奧運盛會能否圓滿成功舉辦的重要條件之一。屆時有大量觀眾到現(xiàn)場觀看奧運比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。解決如下問題：1、僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)相關(guān)數(shù)據(jù)，利用模型與算法，求出以下6對起始站一終到站之間的最佳路線（要有清晰的評價說明）。（1）、S3359-S1828 （2）、S1557-S0481 （3）、S0971-S0485（4）、S0008-S0073 （5）、S0148-S0485 （6）、S0087—S36762、 同時考慮公汽與地鐵線路，解決以上問題。3、 假設(shè)又知道所有站點之間的步行時間，給出任意兩站點之間線路選擇問題的數(shù)學(xué)模型。2.模型的假設(shè)與符號說明2.1模型的假設(shè)（1） 乘客到達(dá)站點時可以直接選擇公汽或地鐵班次上車，即不考慮乘客在站點的等待時間。（2） 在實際過程中，對于公交（包括公汽與地鐵）可能要換車2次以上，用戶已無法容忍，視為無法到達(dá)。（因為如果他們之間換乘就使得費用增大了很多，這是人們不愿意看到的，且一般只坐地鐵是無法到達(dá)終點站的，所以還要再換乘其他的工具，換乘次數(shù)太大我們也不再將其納入考慮的范圍）。（3） 相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘。（4） 相鄰公汽站平均行駛時間（包括停站時間）：3分鐘。（5） 公汽換乘公汽平均耗時：5分鐘（其中步行時間2分鐘）。（6） 地鐵換乘地鐵平均耗時：4分鐘（其中步行時間2分鐘）。（7） 地鐵換乘公汽平均耗時：7分鐘（其中步行時間4分鐘）。（8） 公汽換乘地鐵平均耗時：6分鐘（其中步行時間4分鐘）。（9） 公汽票價：分為單一票價與分段計價兩種，標(biāo)記于線路后；其中分段計價票價為：0?20站：1元；21?40站：2元；40站以上：3元。（10） 地鐵票價：3元（無論地鐵線路間是否換乘）。（11） 已知所有站點之間的步行時間。（12） 同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘（無需支付地鐵費）。（13）郊區(qū)和繁華地區(qū)公交車站的間隔大概一致。2.2符號說明G=（V,E）表示公交網(wǎng)絡(luò)無向圖；V=*II<i<n）表示所有節(jié)點即公交站點的集合，n為節(jié)點數(shù)；E二￡.11<j<m如示路段集合，即線路上任意兩站點間的一段，m是路段數(shù)；L={lI1<j<m}表示指定兩站點間運行線路的集合；C={I1<j<m}表示公汽從一指定站點到另一指定站點所經(jīng)過的站點數(shù)；jS表示第k條路段的行程耗時；kS表示從起點到終點的總的行程耗時；M表示第k條路段的行程費用；kM表示從起點到終點的總的行程費用；N表示換乘次數(shù)；A表示鄰接矩陣；V表示起點（Origin）的鄰接站點的集合；OV表示終點（Dstination）的鄰接站點的集合。D3.問題的分析根據(jù)楊新苗等［1］對公交乘客的出行心理的研究表明，對于公交（包括公汽與地鐵）可能要換車2次以上，用戶已無法容忍，所以我們僅考慮換乘次數(shù)在2次以內(nèi)的情況。分別以行程耗時、花費與換乘次數(shù)為優(yōu)先考慮，找出了最優(yōu)路徑，以滿足公交乘客的各種不同需求。對于無特殊要求的乘客，把三個因素視為同等重要，取平均，得出最優(yōu)路徑。針對第一問，我們根據(jù)公共交通網(wǎng)絡(luò)的特點，把公交網(wǎng)絡(luò)模型映射為一個無向圖G=（V,E）來表示公交線路及站點分布情況，其中V表示公交站點的集合，E是邊的集合，即能通車的路段。結(jié)合圖論中的廣度優(yōu)先搜索（BFS）方法⑵并對其進(jìn)行改進(jìn)，從起點（Origin）和終點（Dstination）同時搜索其鄰接站點，分別構(gòu)成集合V和V，通過判斷兩集合中是否存在交集或任意兩點卩和V（VGV,VGV）間是否有邊相連來找出起點與終點的所有可行路徑（包括直達(dá)、一次換乘、兩次換乘的情況），再分別求出該路徑的耗時及花費，進(jìn)行比較，選出最優(yōu)路徑。針對第二問，因為公汽與地鐵之間可以換乘，所以當(dāng)同時考慮公汽與地鐵線路時，可以將可換乘的地鐵站和公汽站視為對等的，這樣就與第一問相同了，可利用相同的方法來解決。最后，考慮步行，通過調(diào)查對時間加一個閾值T(乘客可以容忍的步行時間)。在第二問算法基礎(chǔ)上求出任意兩站點間的最優(yōu)路徑，通過Floyd算法求出路徑上每個路段及從起點到終點的最短步行時間，分別為ti和t，若求出兩點間的最短步行時間tvT時，則選擇步行；若t>T時，為了滿足乘客想轉(zhuǎn)乘次數(shù)少的心理，做進(jìn)一步判斷，若ti<T,建議乘客步行走完該路段；否則，選擇相應(yīng)的交通工具。模型的建立與求解根據(jù)楊新苗等［1］對公交乘客的出行心理的研究表明，對于公交(包括公汽與地鐵)可能要換車2次以上，用戶已無法容忍，所以我們僅考慮換乘次數(shù)在2次以內(nèi)的情況。分別以行程耗時、花費與換乘次數(shù)為優(yōu)先考慮，找出了最優(yōu)路徑，以滿足公交乘客的各種不同需求。對于無特殊要求的乘客，把三個因素視為同等重要，加和取平均，得出最優(yōu)路徑。問題(1)模型的建立與求解模型的建立首先，只考慮公汽的情況時，我們將公汽的上、下行看作不同的線路。對于有n個站點的公交網(wǎng)絡(luò)，根據(jù)公共交通網(wǎng)絡(luò)的特點，把公交網(wǎng)絡(luò)模型映射為一個無向圖G二(V,E)來表示公交線路及站點分布情況，并得出相應(yīng)的n階鄰接矩陣A=(8)，其中：rsnxn［0,表示r,s站點間無法直達(dá)，即沒有邊相連；5 =2rs1,表示r,s站點間可以直達(dá)，有邊相連。然后，利用圖論中的廣度優(yōu)先搜索算法(Breadth-First-Search)，又譯作寬度優(yōu)先搜索，簡稱BFS，是一種圖形搜索算法。簡單的說，BFS是從根節(jié)點開始，沿著樹的寬度遍歷樹的節(jié)點，如果發(fā)現(xiàn)目標(biāo)，則算法終止。如圖1：但由于BFS是一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以尋找結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。搜索效率較低。為了提高搜索效率,我們對廣度優(yōu)先搜索算法進(jìn)行改進(jìn)，采取從起點（Origin）和終點（Dstination）同時搜索，并結(jié)合集合的思想，采用兩個集合之間逐漸逼近的搜索方法，在一個龐大的無向交通網(wǎng)絡(luò)中，尋找可行路徑。如圖2：考慮對于任意起點和終點，可能存在以下四種情況：（1） 起點和終點在同一線路上，不需要換車（即存在直達(dá)路線）；（2） 起點和終點不在同一線路上，需要換車1次；（3） 起點和終點不在同一線路上，需要換車2次；（4） 起點和終點不在同一線路上，需要換車大于2次，視為通過換車無法達(dá)到（見模型假設(shè)2）。分別對前三種情況進(jìn)行搜索。情況1：直接搜索起點和終點有無一條邊直接連接，若有，則說明兩站點間可直達(dá)；否則，無法直達(dá)。情況2：從起點（Origin）和終點（Dstination）同時搜索其鄰接站點，分別構(gòu)成集合V和V，判斷兩集合中是否存在交集，若有交集，則兩站點間可通過OD一次換乘到達(dá)，且交點為一次換乘的中轉(zhuǎn)站點；否則兩站點無法通過一次換乘到達(dá)。如圖2中，V={V,V,V},V={V,V},VV={V}，則表明起點與終O123D14OD1點可通過一次換乘到達(dá)，且V為該一次換乘的中轉(zhuǎn)站點。1情況3：從起點和終點同時搜索其鄰接站點，分別構(gòu)成集合V和V，判斷兩OD集合中任意兩站點V和卩（V^V,VeV）是否有一條邊相連，若有，則說明起ijiOjD點與終點間可通過兩次換乘到達(dá)，且V和V為兩次換乘的先后中轉(zhuǎn)站點；否則,ij兩站點無法通過兩次換乘到達(dá)。如圖3：從圖3中可看出，V與V,V均有邊相連（V,VeV,VeV），說明起點與終4 2 3 2 3O4D點不僅可通過一次換乘到達(dá)，也可通過兩次換乘到達(dá)，中轉(zhuǎn)站先后分別為V和V24或V和V。34考慮到信息的存貯，我們對每一條連接兩站點的邊建立一個鏈表，用于存貯兩鄰接站點間的所有通行線路L=（LII<j<m｝及線路對應(yīng)的路段所經(jīng)過站點j數(shù)C I1<j<m｝。并由題知，相鄰公汽站平均行駛時間（包括停站時間）為3j分鐘，由此，可計算出該路段的行程耗時S，公式如下：jS二（C-1為3 （1）jj計算費用M時，流程圖如下：

否是?否是否31Ljj單MjC.>20?MjMj否是?否是否31Ljj單MjC.>20?MjMjL,Cj/輸入L/,CCj>40?L:Cjj是M=2—j開始結(jié)束圖4路段費用計算流程圖若從起點到終點，需經(jīng)過換乘N（Nv3）次，則可計算出所有可行路徑的總耗時S與總花費M，公式如下：TOC\o"1-5"\h\z\o"CurrentDocument"S=S+S+…+S+N5X （2）1 2 N+1M二M+M+…+M （3）1 2 N+1再分別從行程耗時（分）、花費（元）與換乘次數(shù)三方面對可行路徑進(jìn)行比較，針對公交乘客的各種不同需求提供合適路線。最后，對三個因素進(jìn)行綜合考慮，取平均，給出最優(yōu)路徑。max先對行程耗時S、花費M與換乘次數(shù)N消除量綱，令：maxS'=SSMM'—N'—NNMmaxmax若乘客無特殊要求，把三個因素視為同等重要，則加和取平均，給出最優(yōu)路徑。Y=S'+M，+N' (5)3Y值越小，路線最好。模型的求解運用上述算法，我們從搜索出的6對起始站一終到站之間的所有可行路徑中分別以行程耗時、花費與換乘次數(shù)為優(yōu)先考慮，找出了最優(yōu)路徑，并從最優(yōu)路徑中隨機選出了兩條線路(若最優(yōu)路徑多于兩條以上)，滿足乘客的不同需求。最后綜合考慮，對三者進(jìn)行加權(quán)，得出最優(yōu)路徑，乘車公交路線如下：表1 S3359-S1828的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S3359-L474S2093L201S1783L041S18287332短S3359-L469S2027L201S1783L041S18287332花費最S3359-L436S1784-L167S182810131少S3359-L436S1784-L217S182810131轉(zhuǎn)乘最S3359-L436S1784-L167S182810131少S3359-L436S1784-L217S182810131綜合考S3359-L436S1784-L167S182810131慮S3359-L436S1784-L217S182810131表2S1557-S0481的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S1557-L084S1919-L189S3186-L460S048110632短S1557-L363S1919-L189S3186-L460S048110632花費最S1557-L084S1919-L189S3186-L460S048110632少S1557-L363S1919-L189S3186-L460S048110632轉(zhuǎn)乘最S1557-L084S1919-L189S3186-L460S048110632少S1557-L363S1919-L189S3186-L460S048110632綜合考S1557-L084S1919-L189S3186-L460S048110632慮S1557-L363S1919-L189S3186-L460S048110632起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0971 -L013 S2517 L296 S2480 -L417 S0485 106 3 2短S0971L094S1609-L140S2654L469S048510632花費最S0971-L013S2184-L417S048512831少轉(zhuǎn)乘最S0971-L013S2184-L417S048512831少綜合考S0971-L013S2184-L417S048512831慮表4S0008-S0073的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0008L198S3766L296S2184L345S00736732短花費最S0008-L159S0291-L058S00738321少S0008-L355S2263L345S00738321轉(zhuǎn)乘最S0008-L463S2083L057S00738321少S0008-L159S0491-L058S00738321綜合考S0008-L355S2263L345S00738321慮S0008-L463S2083L057S00738321表5S0148-S0485的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0148L308S0036L156S2210-L417S048510632短S0148L308S0036L156S3332-L417S048510632花費最S0148L308S0036L156S3351-L417S048510632少S0148L308S0036L156S3332-L417S048510632轉(zhuǎn)乘最S0148L308S0036L156S3332-L417S048510632少S0148L308S0036L156S2210-L417S048510632綜合考S0148L308S0036L156S3351-L417S048510632慮S0148L308S0036L156S2210-L417S048510632表6S0087—S3676的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0087-L021S0088L231S0427L097S36764632短S0087-L454S0088L231S0427-L462S36764632花費最S0087L454S3496-L209S36766521少轉(zhuǎn)乘最S0087L454S3496-L209S36766521少綜合考S0087L454S3496-L209S36766521慮班次前的負(fù)號表示該線路為下行線)系統(tǒng)可根據(jù)公交乘客對換乘次數(shù)、行程耗時與費用的不同要求，并進(jìn)行綜合考慮，提供合適的路徑。該算法的時間復(fù)雜度與鄰接矩陣的稀疏程度有關(guān)，在一般情況下，其時間復(fù)雜度為O(lVI+1EI)。4.2問題(2)模型的建立與求解4.2.1模型的建立因為公汽與地鐵之間可以換乘，所以當(dāng)同時考慮公汽與地鐵線路時，可以將可換乘的地鐵站和公汽站視為對等的，這樣就與第一問相同了，可利用相同的方法來解決。地鐵站對應(yīng)的公汽站與同一地鐵線路上其他地鐵站對應(yīng)的公汽站彼此間是可以直達(dá)的。女如地鐵T1線上的地鐵站D01對應(yīng)公汽站S0567,S0042,S0025,地鐵站D02對應(yīng)公汽站S1487，則我們認(rèn)為S1487與S0567,S0042,S0025分別都是可以直達(dá)的,那么5 =5 =5 =1(S1487,S0567) (S1487,S0042) (S1487,S0025)相應(yīng)的n階鄰接矩陣A=(5)也發(fā)生改變，再利用問題(1)的算法進(jìn)行搜rsnxn索，找出起點與終點的所有可行路徑。此外，此時站點數(shù)分別與費用和行程耗時的關(guān)系發(fā)生了變化，需利用新的算法求解再比較得到最優(yōu)路線，不同的是換乘情況變得更為復(fù)雜。L為中轉(zhuǎn)站的前一線路，L為中轉(zhuǎn)站的后一線路，C在該中轉(zhuǎn)站換乘所需的時間ijij換乘所需時間的算法流程圖如下：

是否否是否6CjL,Cj/L地鐵/是否否是否6CjL,Cj/L地鐵/公汽L地鐵/地鐵L,C"jj是C=7i/C=5ij輸入L,LjC=4jLL公汽jj公汽開始結(jié)束模型的求解對于前2對指定的起始站f終到站，加入地鐵后的所有線路，由于需要換乘的次數(shù)較多，行程耗時較長，超過了人們可以承受的限度，且如果采納這樣的路線行駛，會使金錢上的花費巨大，所以不采用這類方案，而直接采用一種交通工具即公汽。那么在這種情況下，它們的最優(yōu)路線并沒有改變，即上面表格統(tǒng)計結(jié)果。針對問題(2),與問題(1)相比，其中第3、4、5、6對起始站f終到站的乘車線路有些變化：起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0971L094S0567T1S0464L104S04859652短S0971-L119S0567T1S0466L051S04859652花費最S0971-L013S2184-L417S048512831少轉(zhuǎn)乘最S0971-L013S2184-L417S048512831少綜合考S0971-L013S2184-L417S048512831慮表8S0008-S0073的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0008-L150S3874T2S0525L103S00735552短S0008-L159S3874T2S0525L103S00735552花費最S0008-L159S0291-L058S00738321少S0008-L355S2263L345S00738321轉(zhuǎn)乘最S0008-L463S2083L057S00738321少S0008-L159S0491-L058S00738321綜合考S0008-L355S2263L345S00738321慮S0008-L463S2083L057S00738321表9S0148-S0485的可行路線起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘時間最S0148-L024S1487T1S0464-L469S048587.552短S0148-L024S1487T1S0466-L450S048587.552花費最S0148L308S0036L156S3351-L417S048510632少S0148L308S0036L156S3332-L417S048510632轉(zhuǎn)乘最S0148-L024S1487T1S0464L104S048587.552少S0148-L024S1487T1S0466L051S048587.552綜合考S0148L308S0036L156S3351-L417S048510632慮S0148L308S0036L156S2210-L417S048510632起點站班次中轉(zhuǎn)站班次中轉(zhuǎn)站班次終點站時間總費用轉(zhuǎn)乘花費最S0087 L454 S3496 -L209 S3676 65 2 1時間最S0087T2短S3676 25 30少轉(zhuǎn)乘最S0087 T2 S3676 25 3 0少綜合考S0087 T2 S3676 25 3 0慮班次T1、T2為地鐵線路）4.3問題（3）模型的建立與求解最后，考慮步行,通過調(diào)查對時間加一個閾值T（乘客可以容忍的步行時間）。在第二問算法基礎(chǔ)上求出任意兩站點間的最優(yōu)路徑，通過Floyd算法求出路徑上每個路段及從起點到終點的最短步行時間，分別為ti和t。若求出兩點間的最短步行時間t<T時，則選擇步行；若t>T時，為了滿足乘客想轉(zhuǎn)乘次數(shù)少的心理，做進(jìn)一步判斷，若ti<T,建議乘客步行走完該路段；否則，選擇相應(yīng)的交通工具。問題補充：若存在兩站點間無法通過兩次及兩次以內(nèi)的換乘到達(dá)，則加入步行作為補充，將步行作為一種線路考慮，那么鄰接矩陣A中元素全為1，再利用第二問的算法進(jìn)行搜索，求出最優(yōu)路徑。模型的優(yōu)缺點評價5.1模型的優(yōu)點（1） 該模型對廣度優(yōu)先搜索算法進(jìn)行改進(jìn)，并結(jié)合集合的思想，不僅提出了一種新的思路，還大大提高了搜索效率。算法簡單合理，運算速度快，容易在計算機上實現(xiàn)。（2） 為了更全面的考慮問題，我們分別以行程耗時、花費與換乘次數(shù)為優(yōu)先考慮，找出了最優(yōu)路徑，以滿足公交乘客的各種不同需求，同時也對三個因素進(jìn)行了綜合考慮。（3） 我們從最優(yōu)路徑中隨機選出了兩條線路提供給乘客，這樣一來，在資源的配置方面更具有可實施性。避免了該地區(qū)的人都采取一樣的方案來實施，那么就會使資源分配不均，造成很多新的現(xiàn)象（如堵車等）來影響這個措施的實施過程，使其達(dá)不到預(yù)期的效果。5.2模型的缺點(1)第三問的補充中，將步行作為一種線路考慮，搜索效率較低。模型的改進(jìn)與推廣考慮實際情況中，乘客都會盡量選擇有座位的公交，即公交起點站離自己所在站點最近的班次。所以我們將其作為一個影響因素加入到模型的算法中，進(jìn)一步選出最優(yōu)路徑。7.參考文獻(xiàn)楊新苗，基于GIS的公交乘客出行路線選擇模型[J],東南大學(xué)學(xué)報,30(11)：87—91,2000.維基百科，廣度優(yōu)先搜索，/zh-cn/BFS，2009.9.2.附錄附錄1(求解直達(dá)矩陣hc的程序huan_cheng_matrix)functionhc=huan_cheng_matrix(data,DTdata,dt)tic;hc=cell(4000);%換乘一階矩陣forI=1:520對%于上行的處理I%debugtime=toclen=data(1+(I-1)*4,2);%disp('$$$$$$$$$$$$$$$$$$$$$$$$$111')%debug%disp(len);forJ=2:len-1forK=J+1:len%disp('$$$$$$$$$$$$$$$$$$$$$$$$$')%debughc{data(3+(I-1)*4,J),data(3+(I-1)*4,K)}=strcat(hc{data(3+(I-1)*4,J),data(3+(I-1)*4,K)},'+S',num2str(data(3+(I-1)*4,J)),'.L',num2str(K-J),'.T',num2str(data(3+(I-1)*4,K)),'.C',num2str(I),'.');endend對%于下行的處理ifdata(3+(I-1)*4,1)==1len=data(1+(I-1)*4,3);forJ=2:lenforK=J+1:lenhc{data(4+(I-1)*4,J),data(4+(I-1)*4,K)}=strcat(hc{data(4+(I-1)*4,J),data(4+(I-1)*4,K)},' + S',num2str(data(4+(I-1)*4,J)),'.L',num2str(K-J),'.T',num2str(data(4+(I-1)*4,K)),'.C',num2str(-I),'.');endendendend%%對地鐵的處理ifdt==0return;endDT{1}=DTdata(1:23,2:6);DT_c{1}=DT{1}(isnan(DT{1})==0);DT_c{3}=DT_c{1}(end:-1:1);DT{3}=DT{1};DT{2}=DTdata(23:41,2:6);DT_c{2}=DT{2}(isnan(DT{2})==0);forI=1:3len=length(DT_c{I});forJ=1:len-1forK=J+1:len[J_r,J_c]=find(DT{I}==DT_c{I}(J));[K_r,K_c]=find(DT{I}==DT_c{I}(K));hc{DT_c{I}(J),DT_c{I}(K)}=strcat(hc{DT_c{I}(J),DT_c{I}(K)},'+S',num2str(DT_c{I}(J)),'.L',num2str(abs(K_r-J_r)),'.T',num2str(DT_c{I}(K)),'.D',num2str(520+I),'.');endendend附錄2(求解鄰接舉證lj的程序lin_jie)functionlj=lin_jie(data,DTdata,dt)tic;lj=zeros(4000);%換乘一階矩陣forI=1:520對%于上行的處理I%debugtime=toclen=data(1+(I-1)*4,2);forJ=2:len-1forK=J+1:lenlj(data(3+(I-1)*4,J),data(3+(I-1)*4,K))=1;endendifdata(3+(I-1)*4,1)==1對%于下行的處理len=data(1+(I-1)*4,3);forJ=2:lenforK=J+1:lenlj(data(4+(I-1)*4,J),data(4+(I-1)*4,K))=1;endendendend%%對地鐵的處理ifdt==0return;endDT{1}=DTdata(1:23,2:6);DT_c{1}=DT{1}(isnan(DT{1})==0);DT_c{3}=DT_c{1}(end:-1:1);DT{3}=DT{1};DT{2}=DTdata(23:41,2:6);DT_c{2}=DT{2}(isnan(DT{2})==0);forI=1:3len=length(DT_c{I});forJ=1:len-1forK=J+1:lenlj(DT_c{I}(J),DT_c{I}(K))=1;endendend附錄3(尋找出發(fā)點s到t的公交或地鐵線路的程序search)function[route_num1route_num2route_num3hub2hub3_1hub3_2routeFrouteSrouteT]=search(lj,data,hc,s,t)%%%第一部分求解出乘車中轉(zhuǎn)方案tic;%debugroute_num1=0;%直達(dá)的乘車方案個數(shù)route_num2=0;%轉(zhuǎn)乘一次的乘車方案個數(shù)hub2=[];%轉(zhuǎn)乘一次的中轉(zhuǎn)站route_num3=0;%轉(zhuǎn)乘二次的乘車方案個數(shù)hub3_1=[];%轉(zhuǎn)乘二次的第一個中轉(zhuǎn)站hub3_2=[];%第二個中轉(zhuǎn)站%直達(dá)方案求解iflj(s,t)==1route_num1=1;%轉(zhuǎn)乘一次方案求解hub2=find(lj(s,:).*lj(:,t)');route_num2=length(hub2);%轉(zhuǎn)乘二次方案求解M=find(lj(s,:)==1);N=find(lj(:,t)==1);%lj_hub=lj(lj(s,:)==1,lj(:,t)==1);lj_hub=lj(M,N);[hub3_1,hub3_2]=find(lj_hub==1);hub3_1=M(hub3_1);hub3_2=N(hub3_2);route_num3=length(hub3_1);routeF=[];routeS=[];routeT=[];%%%%第二部分求解各條路徑的信息%直達(dá)方案的各條路徑信息求解disp('$$$$$$$$$$$$$$$$$11111111111111111111');%debugrouteF_len=0;ifroute_num1==1routeF=string_analysis(hc{s,t},data);elserouteF=[];enddisp('$$$$$$$$$$$$$$$$$22222222222222222222');%debug%轉(zhuǎn)乘一次方案的各條路徑的信息求解routeS_len=0;routeS(100000).StartStation=[];%debugforI=1:route_num2route1=string_analysis(hc{s,hub2(I)},data);route2=string_analysis(hc{hub2(I),t},data);r_1_len=length(route1);r_2_len=length(route2);forJ=1:r_1_lenforK=1:r_2_lenrouteS_len=routeS_len+1;routeS(routeS_len).StartStation=s;routeS(routeS_len).RouteLength=route1(J).RouteLength+route2(K).RouteLength;routeS(routeS_len).HubStation1=hub2(I);routeS(routeS_len).Station=t;routeS(routeS_len).CarNumber1=route1(J).CarNumber;routeS(routeS_len).CarNumber2=route2(K).CarNumber;routeS(routeS_len).Time=route1(J).Time+route2(K).Time+change_bus(route1(J).CarNumber,route2(K).CarNumber);routeS(routeS_len).Money=route1(J).Money+route2(K).Money;endendendrouteS=routeS(1:routeS_len);disp('$$$$$$$$$$$$$$$$$33333333333333333333');%debugrouteT(100000).StartStation=0;%轉(zhuǎn)乘二次方案的各條路徑的信息求解routeT_len=0;forI=1:route_num3route1=string_analysis(hc{s,hub3_1(I)},data);route2=string_analysis(hc{hub3_1(I),hub3_2(I)},data);route3=string_analysis(hc{hub3_2(I),t},data);r_1_len=length(route1);r_2_len=length(route2);r_3_len=length(route3);%disp('$$$$$$$$$$$$$$%%%%%%%%%%%%%%%$$$$$$$$$$$$$$$$$');forJ=1:r_1_lenforK=1:r_2_lenforL=1:r_3_lenrouteT_len=routeT_len+1;routeT(routeT_len).StartStation=s;routeT(routeT_len).RouteLength=route1(J).RouteLength+route2(K).RouteLength+route3(L).RouteLength;routeT(routeT_len).HubStation1=hub3_1(I);routeT(routeT_len).HubStation2=hub3_2(I);routeT(routeT_len).Station=t;routeT(routeT_len).CarNumber1=route1(J).CarNumber;routeT(routeT_len).CarNumber2=route2(K).CarNumber;routeT(routeT_len).CarNumber3=route3(L).CarNumber;routeT(routeT_len).Time=route1(J).Time+route2(K).Time+route3(L).Time+change_bus(route1(J).CarNumber,route2(K).CarNumber)+change_bus(route2(K).CarNumber,route3(L).CarNumber);routeT