承諾書我們仔細(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í)顚懲暾娜?參賽隊員（打印并簽名）：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）： 數(shù)模指導(dǎo)組 日期：2011年8月26日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：公交查詢系統(tǒng)的研究與設(shè)計摘要本文旨在設(shè)計一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。問題一，鑒于實際生活中公交路線復(fù)雜多樣，我們將不同公交線路抽象化。把公汽換乘和直達(dá)綜合考慮，模型比較復(fù)雜，所以我們首先建立公汽直達(dá)數(shù)據(jù)庫Q,用戶查詢時，系統(tǒng)首先查詢Q,得到所有直達(dá)車方案。在需要轉(zhuǎn)乘時，針對不同用戶需求，分別以轉(zhuǎn)乘次數(shù)最少、總耗時最短、總費用最少為目標(biāo)，量化不同目標(biāo)為有向賦權(quán)圖的不同權(quán)矩陣，始、終點連通為約束建立0-1整數(shù)線性規(guī)劃模型來設(shè)計最佳路線。為了能提供多種公交線路備選方案，我們首先使用基于Dijkstra的鄰接算法求解，得到不同目標(biāo)下的多種優(yōu)化方案；對于鄰接算法不易求解的多次轉(zhuǎn)乘最優(yōu)方案，我們采用Lingo軟件直接求得全局最優(yōu)解。綜合方案集（見5.1.6模型表1.1-1.6），其中6條線路時間最短目標(biāo)分別為67、102、106、62、105、49（分鐘）。問題二，同時考慮公汽和地鐵系統(tǒng)，首先把各地鐵站點和周圍鄰近的公汽站點集抽象為同一新站點，同時將兩條地鐵線路抽象化，計算公汽地鐵直達(dá)數(shù)據(jù)庫:門，再結(jié)合地鐵的費用與地汽換乘等待時間把地鐵線與公汽線結(jié)合，建立多目標(biāo)0-1整數(shù)線性規(guī)劃模型（見5.2.7模型）；對于轉(zhuǎn)乘次數(shù)以2次為分界分別使用鄰接算法和Lingo軟件求解得出6條線路的全局最優(yōu)解。綜合方案集（見5.2.9模型表2.1-2.6），其中6條線路時間最短目標(biāo)分別為65、102、98、56.5、89.5、30（分鐘）。問題三，將步行考慮在內(nèi)，將此系統(tǒng)抽象為最短路問題下的有向賦權(quán)圖，并在此基礎(chǔ)上以換乘次數(shù)最少為主要約束，以總行程時間最短、費用最低為目標(biāo)，建立多目標(biāo)0-1整數(shù)線性規(guī)劃模型，并給出求解的一般步驟與算法。關(guān)鍵詞：鄰接算法；有向賦權(quán)圖；直達(dá)隊列表；分層序列法；疊加有向賦權(quán)圖問題的重述為了迎接2008年奧運會，北京公交做了充分的準(zhǔn)備，公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時也面臨了多條線路的選擇問題。為方便公眾查詢公交線路，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。這個系統(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ù)學(xué)模型。問題的分析本題主要在三種不同情況下，研究任意兩站點之間的線路選擇問題。問題一，在僅考慮公汽線路的情況下，首先要根據(jù)題目給出的公交線路信息數(shù)據(jù)對每條線路進(jìn)行抽象化處理。然后由于乘坐公交有直達(dá)和轉(zhuǎn)乘兩種情況，為了方便用戶查詢，我們先要運用MATLAB內(nèi)建元胞結(jié)構(gòu)來建立公汽直達(dá)數(shù)據(jù)庫Q,之后再結(jié)合有向賦權(quán)圖建立最短路模型來設(shè)計需要轉(zhuǎn)乘時的路線。問題二，由于地鐵與鄰近站點可換乘，可將每個地鐵站點及其周邊鄰近的所有公交站點抽象成一個點處理。對于兩條地鐵線路可按照與問題一相同的抽象方法處理。在此基礎(chǔ)上按照問題一的思路確定任意兩站點間的最佳方案。問題三，綜合考慮公交和地鐵站點的實際分布情況，人們有時會選擇步行小段距離之后再轉(zhuǎn)車來節(jié)省時間或減少轉(zhuǎn)車次數(shù)，本問研究此種情況下的出行方案。模型的假設(shè)相鄰公汽站平均行駛時間（包括停站時間）：3分鐘。相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘。公汽換乘公汽平均耗時：5分鐘（其中步行時間2分鐘）。地鐵換乘地鐵平均耗時：4分鐘（其中步行時間2分鐘）。地鐵換乘公汽平均耗時：7分鐘（其中步行時間4分鐘）。公汽換乘地鐵平均耗時：6分鐘（其中步行時間4分鐘）。公汽票價：分為單一票價與分段計價兩種；單一票價：1元其中分段計價的票價為：0?20站：1元21?40站：2元40站以上：3元地鐵票價：3元（無論地鐵線路間是否換乘）。假設(shè)同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘，且無需支付地鐵費。假設(shè)各公交車都運行正常，不會發(fā)生堵車現(xiàn)象。假設(shè)公交、列車均到站停車。假設(shè)始發(fā)終點出入地鐵需要步行4分鐘；

符號說明鞘：5:%：Si：Akj:弧〔i’j）是否在該有向賦權(quán)圖上；站點i?j的總乘車時間；站點1fj的乘車費用；站點；站點kfj的直達(dá)路線數(shù)；A=(話如c=(CJ:Yij:Yij:知:珀::直達(dá)線路數(shù)矩陣；最少換乘次數(shù)矩陣；0-1決策變量；弧（i,j）是否在該路徑上；站點ifjfk間是否地鐵換乘地鐵；站點1fj的乘車時間；R；：C:站點ifj的乘車總費用；人為設(shè)定參數(shù)，表示乘客可接受的最多換乘次數(shù);二： 總等待時間，總步行時間;z：=3:i-‘最短直達(dá)為公汽（表示乘始發(fā)坐公汽等待3分鐘），等于2為地鐵。模型的建立與求解問題一的模型建立與求解5.1.1圖論抽象化處理模型實際生活中，公交線路復(fù)雜多樣，不利于問題的求解，于是我們將三種公汽線路進(jìn)行抽象化處理，方法如下：（1）上、下行線原路返回線路這種線路有兩個端點站，在兩個端點之間雙向行車，并且兩個方向上的行車路線相同，經(jīng)過同樣的站點序列。由于線路的方向不同，將上行線和下行線抽象為兩條線路處理。如圖所示：S1S2S3S4V 1 AY AV 1 ■>（2）線路為環(huán)行線實際情況中環(huán)形路線一般是雙環(huán)，即將環(huán)形路線抽象為順時針和逆時針兩條線路如圖所示：3）下行線與上行線經(jīng)過站點不同由于下行線與上行線經(jīng)過站點不同，該種線路顯然可以被抽象為兩條不同線路。如下圖所示：5.1.2公汽直達(dá)數(shù)據(jù)庫Q的建立在現(xiàn)實生活中，乘客在進(jìn)行公交路線選擇時，通常會優(yōu)先選擇直達(dá)車，那么在查詢系統(tǒng)內(nèi)部應(yīng)設(shè)有任意兩站點的直達(dá)線路表，以方便查詢時快速查詢是否有直達(dá)車，若有，則直接輸出所有直達(dá)車輛；若無，再搜索換乘路線。在建立公汽直達(dá)數(shù)據(jù)庫Q的時候，由于本題站點較多，若采用通常方式，占的內(nèi)存較大，所以本文采用MATLAB內(nèi)建元胞結(jié)構(gòu)，當(dāng)元胞內(nèi)隊列不存在時不占用空間。具體元胞結(jié)構(gòu)設(shè)計如下：Cellflj}Cellg}Cell{13}???Cell{14008}???CelI{2Tl}Cell如}CeU{23}???0611(24000}?????????????????????Cell[27Tl}CeU{273}???Cellfa^lOOS]???車號耗時（分鐘）費用（元）L053391??????????????????上圖中Cell{27,1008}代表公汽直達(dá)數(shù)據(jù)庫Q中第27行第1008個元胞（即從站點S0027到站點S1008的直達(dá)公交線路信息），元胞中隊列的每一行代表一輛直達(dá)車信息。5.1.3基于不同目標(biāo)的有向賦權(quán)圖定義_由圖論相關(guān)知識可將題中所提供的公汽網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖迂中的每個頂點為每個不同的站點，如果從三中的頂點「到「有直達(dá)路線，那么這兩點之間就用有向邊相連，記做 ，方向為從i指向'，表示可從i直達(dá)’，相應(yīng)的有一個數(shù)稱為該有向邊的權(quán)，這樣公汽網(wǎng)絡(luò)就抽象為一個有向賦權(quán)圖。在本模型中，賦權(quán)圖中的權(quán)定義如下：時間費用其分量為二=$m碼）站點％到站點m的直達(dá)時間i+8 無直達(dá)線路時間費用其分量為二=‘小="：—._，其分量為氾=典出閑）站點K到站點Y的直達(dá)費用‘小="：—._，其分量為氾=5.1.4最小換乘次數(shù)的確定如果用戶查詢的站點間無直達(dá)車輛，則查詢系統(tǒng)需給出換乘方案，此時，我們需要得知查詢的站點間公交的最小換乘次數(shù)。由公汽直達(dá)數(shù)據(jù)庫;?我們可得任意兩站點的直達(dá)線路數(shù)，由此可構(gòu)造表示兩兩站點間直達(dá)路線數(shù)目的直達(dá)線路數(shù)矩陣，通過矩陣運算可得到任兩站點間換乘線路數(shù)矩陣，進(jìn)而得到任兩站點間的最少換乘次數(shù)矩陣，從而可得任兩站間所需的最少換乘次數(shù)。''直達(dá)線路數(shù)矩陣的建立引入直達(dá)線路數(shù)矩陣 ，N表示所有公汽所經(jīng)過的的站點總數(shù)。矩陣元

素汀表示第i個站點到第'個站點直達(dá)線路數(shù)匚，其中，當(dāng)i=，時為無效路徑，設(shè)定值為0,即：_fa{i#j)%lo0=j)最少換乘線路數(shù)矩陣的建立以尸表示方陣上的匚次幕，込.為站點久亠的直達(dá)路線數(shù)，貝I」：A?i=^A?k1-Akjk=l其中，元素蘭為通過 次換乘從站點i的線路數(shù)。如三［=二表示從站點2到站點3有1條2次換乘路線，其換乘站點可通過運算參數(shù)記錄得到。匚e[1嚴(yán)),匚e[1嚴(yán)),即：引入矩陣三=:：-.；，其矩陣元素〉.為使得蘭=二的匚的最小值,則 表示從站點i 必要的最少換乘次數(shù)，以矩陣:=(7:.\表示最少換乘次數(shù)矩陣，貝U：C=E—1其中，元素J表示從站點i必要的最少換乘次數(shù)。基于最少換乘次數(shù)矩陣二，每對起始站f終到站的最少換乘次數(shù)如下:表2.0最小換乘次數(shù)表：線路編號123456起始站S3359S1557S0971S0008S0148S0087終到站S1828S0481S0485S0073S0485S3676最少換乘1211215.1.5最短路模型目標(biāo)函數(shù)的建立(1)換乘次數(shù)最少基于5.1.3建立的有向賦權(quán)圖，引入0T決策變量二.表示弧JJ是否在起點與終點的路徑上，則=$弧(i,0在站點叫到站點M的路徑上XJ=I0 其他情祝若與 可通過轉(zhuǎn)乘到達(dá)，則由站點「到站點「之間換乘次數(shù)為經(jīng)過的總弧數(shù)減1，即換乘次數(shù)最小可表示為：2)行程總時間最短基于5.1.3基于5.1.3建立的有向賦權(quán)圖，行程總時間最短表示為：3)行程總費用最少設(shè)肅表示車輛票價屬性，則表示單一票制1元：2 分段計價設(shè)二.表示■所過站數(shù)，那么—■直達(dá)費用權(quán)十f…表示為:%=1Pii=Mij=占旳EPii=Qij=2,ss)E[21,40]Qii=2円jE[41,-Foo]行程總費用最少可表示為：約束條件的建立換乘次數(shù)約束基于對換乘次數(shù)最少這一目標(biāo)的分析，可得在有向賦權(quán)圖中換乘次數(shù)表達(dá)式，以匚表示乘客所能接受的最大換乘次數(shù)，則換乘次數(shù)約束可表示為：xxij-1cc￡[0,+眄,且為整數(shù)在實際應(yīng)用中，查詢系統(tǒng)中的:值可由查詢用戶自己設(shè)定。(2)最短路起止點約束(i=e)(i圭s,e)(i=e)(i圭s,e)乙鞘—乙嚀j=i j=i(Lj)eE (ij)EE模型的建立基于以上部分，建立多目標(biāo)最短路模型0-1規(guī)劃表達(dá)式如下(s為起點，e為終點):》鞘-gCifDEE鞘E{04} （M）EE5.1.6最短路模型的求解模型的算法及評價方法一基于數(shù)據(jù)庫Q與Dijkstra算法的“鄰接算法”求解步驟1：輸入乘車始點i終點■',（注： 為最少換乘次數(shù)矩陣）若ch=0則有直達(dá)線路，輸出公汽直達(dá)數(shù)據(jù)庫Q中所有直達(dá)信息，結(jié)束程序，若】則有轉(zhuǎn)乘1次線路，轉(zhuǎn)步驟2,若=2則有轉(zhuǎn)乘2次線路，轉(zhuǎn)步驟4,若 則存在轉(zhuǎn)乘-次線路，但全局計算時間復(fù)雜度較高，終止鄰接算法，采用Lingo求解。步驟2：求線路心的直達(dá)站點 ，及線路口:的直達(dá)站點m。步驟3：若存在 ，線路屮）、可能為一次轉(zhuǎn)車的線路，保存隊列L二，轉(zhuǎn)步驟6。步驟4：求經(jīng)過三:啲線路「壬：以及求線路「壬：的站點 。步驟5：若存在 ，線路匚①、二二、讓小可能為兩次轉(zhuǎn)車的線路，保存隊列U2,轉(zhuǎn)步驟6。步驟6：修改隊列匸、口中的成員，按其屬性（路過的站點數(shù)，乘坐的車輛）根據(jù)不同目標(biāo)計算總行程時間、費用等。評價說明：這種算法的優(yōu)點是把較優(yōu)方案都記錄在匚八LV中，方案豐富，這對用戶多需求是吻合的。缺點是對于轉(zhuǎn)乘次數(shù)大于2次時，本方法無法在有限時間內(nèi)求解。方法二使用Lingo軟件求解無轉(zhuǎn)乘次數(shù)限制的方案本方法運用Lingo軟件，通過稀疏矩陣實現(xiàn)編程實現(xiàn)。評價說明：這種算法可以彌補鄰接算法的缺陷，在需要轉(zhuǎn)乘次數(shù)大于2時，只要開始迭代計算后，由于目標(biāo)與約束線性，Lingo只需要幾秒即可求解出全局最優(yōu)解。模型的結(jié)果表1.1一線S3359-S1828部分出行方案列表：求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo/鄰接1104S1784一L436L167一3鄰接1104S1784一L436L217一3鄰接1140S2364一L469L217一3鄰接1143S0519一L469L167一4Lingo/鄰接267S3697S1784L484L485L1673

鄰接267S3697S1784L484L485L2173鄰接267S2027S1784L324L485L1673鄰接267S2027S1784L324L485L2173鄰接267S2903S1784L015L485L1673鄰接267S2903S1784L015L485L2173表1.2二線S1557-S0481部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo3102S1919,S3186,S0903L084,L189,L091,L2394Lingo/鄰接2109S1919S3186L084L189L4603鄰接2109S1919S3186L363L189L4603鄰接2115S1919S2424L084L417L2543鄰接2115S1919S2424L084L417L3123鄰接2118S1919S0992L084L417L4603鄰接2118S1919S0992L363L417L4603鄰接2130S1919S0417L084L497L4604鄰接2130S1919S0417L363L497L4604鄰接2133S3389S1427L084L454L4474表1.3三線S0971-S0485部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用鄰接1131S2184一L013L417一3鄰接1146S2119一L013L395一3鄰接1152S1739一L119L417一3Lingo/鄰接2106S2517S2159L013L290L4693鄰接2109S1609S2654L013L140L4693鄰接2109S1609S2654L024L140L4693鄰接2124S2324S2482L013L132L4174鄰接2124S2324S2482L013L242L4174鄰接2124S2324S2480L013L132L4174鄰接2124S1520S2265L119L008L4693表1.4四線S0008-S0073部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo462S3766,S2085,S0483,S0525L19&L476,L17,L32&L1035鄰接186S2263一L355L345一2

鄰接189S2302一L355L057一2鄰接1113S3415一L463L118一2鄰接1131S3915一L463L118一2Lingo/鄰接270S1691S2184L198L290L3453鄰接270S1383S2184L043L290L3453鄰接279S0630S1659L159L231L4593鄰接279S0630S1659L159L381L4593鄰接279S0854S1659L159L231L4593表1.5五線S0148-S0485部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo3105S3604,S2361,S2210L30&L81,L156,L4174Lingo/鄰接2109S0036S2210L308L156L4173鄰接2112S0036S2482L308L157L4173鄰接2118S3604S1381L308L129L4693鄰接2118S3604S2026L308L123L4693鄰接2118S3604S1383L308L129L4693鄰接2121S3604S2840L308L454L4173鄰接2121S0302S2027L308L427L4693鄰接2121S3604S1321L308L129L4693鄰接2124S3604S2079L308L206L4173表1.6六線S0087-S3676部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo/鄰接168S3496一L454L209一2Lingo/鄰接249S0088S0427L021L231L0973鄰接249S0088S0427L206L231L0973鄰接249S0088S0427L454L231L0973鄰接252S0630S0427L021L381L0973鄰接252S0854S0427L293L231L0973鄰接252S1427S0427L021L381L0973鄰接255S0541S2336L454L120L4623鄰接261S3874S0280L021L068L4623鄰接273S3874S0274L021L068L4623問題二的模型建立與求解5.2.1抽象化處理模型

（1）可互換站點抽象化因為地鐵與公汽互換的時間較短而且比較容易換乘，故將這些站點看作緊鄰站點，將這些可互換的緊鄰站點在整個交通網(wǎng)絡(luò)中抽象為一個站點，使問題得到簡化。（2） 地鐵線路抽象化基于5.1.1的抽象方法對兩地鐵線路Tl、T2進(jìn)行抽象處理如下：T1：為雙向線路，根據(jù)方向不同將其抽象為兩條單向行駛線路。T2：為環(huán)行線路，環(huán)形路線一般是對開，故抽象成兩條線處理。5.2.2公汽地鐵直達(dá)數(shù)據(jù)庫8的建立將緊鄰站點抽象為一個新站點，此時建立的公汽地鐵直達(dá)數(shù)據(jù)庫二二實質(zhì)上是新站點與新站點間的直達(dá)路線集。當(dāng)用戶使用查詢系統(tǒng)時，系統(tǒng)首先查找這兩點所屬的新站點，然后查找新站點間可直達(dá)的線路，給出系統(tǒng)設(shè)計的多種路線方案，供用戶按照自己的目標(biāo)選擇。采用與5.1.2相同的思路及方法，把已知公汽線路到達(dá)久「：都映射到汽，得出新直達(dá)數(shù)據(jù)庫:&，再結(jié)合地鐵的費用與地汽換乘等待時間就可以把地鐵線與公汽線結(jié)合。具體元胞結(jié)構(gòu)設(shè)計圖如下：CeU{l,2}???Cell{lf1008}???Cell[血1}Cell{2,2}Cell{2,3}???Cell{24008}?????????????????????Cell[2Al}GeU{27,2]CeU{27,3}???Cell{274003}???車號耗時（分鐘）費用（元）L053391??????????????????上圖中Cell{27,1008}代表公汽直達(dá)數(shù)據(jù)庫Q中第27行第1008個元胞（即從站點S0027到站點S1008的直達(dá)公交線路信息），元胞中隊列的每一行代表一輛直達(dá)車信息。5.2.3公汽地鐵混合網(wǎng)絡(luò)圖的賦權(quán)根據(jù)5.±1的簡化，結(jié)合圖論相關(guān)知識，將第二問公汽、地鐵混合網(wǎng)絡(luò)抽象成一個有向賦權(quán)圖，乏中的每個頂點為每個不同的站點，如果從壬中的頂點廠到「有直達(dá)路線，那么這兩點之間就用有向邊相連，記做，賦權(quán)圖中的權(quán)可根據(jù)不同的目標(biāo)進(jìn)行定義：時間：費用：V肥“時間：費用：V肥“其分量為斗j=其分量為pjj=3站點vi至可的直達(dá)時間,+8 無直達(dá)線路pfvi環(huán)站點vi至VJ的直達(dá)費用、+8 無直達(dá)線路5.2.4最少換乘次數(shù)的確定采用與5.1.4相同的思路及方法，由公汽地鐵直達(dá)數(shù)據(jù)庫：；二可得任意兩站點的直達(dá)線路數(shù)。由此可構(gòu)造直達(dá)線路數(shù)矩陣二，確定換乘線路數(shù)矩陣：》Aikn1xAkjk=l其中，元素丄「為通過（n-1）次換乘從站點ifj的線路數(shù)。其換乘站點可通過運算參數(shù)記錄得到。進(jìn)而確定最少換乘次數(shù)矩陣：

min{n禺11 0,nE[1,c?]}Cf=Br-1其中，矩陣「中元素匚.表示從站點i-j必要的最少換乘次數(shù)。基于最少換乘次數(shù)矩陣c'，每對起始站一終點站的最少換乘次數(shù)如下:表2.0最小換乘次數(shù)表：線路編號123456起始站S3359S1557S0971S0008S0148S0087終到站S1828S0481S0485S0073S0485S3676最少換乘1211205.2.5最短路模型目標(biāo)函數(shù)的建立引入0-1決策變量—表示弧::jJ引入0-1決策變量—表示弧::jJ是否在該路徑上:弧（i,j）位于頂點％到*的路徑上其他基于對混合網(wǎng)絡(luò)的抽象,0若與 可通過轉(zhuǎn)乘到達(dá)，則由站點「到站點「之間換乘次數(shù)為經(jīng)過的總弧數(shù)減1，即換乘次數(shù)最小可表示為：2）行程總時間最短乘車時間：其中，二為各站點最快直達(dá)時間，基于"，包括地鐵在內(nèi)。總等待時間：設(shè) 表示i~j最短直達(dá)為公汽（也表示乘始發(fā)坐公汽等待2分鐘），則總等待時間可表示為：Tl=》YijZij總步行時間：將相同車型換乘、不同車型換乘的步行時間，均視為2分鐘：不同車型換乘多步行的4分鐘：Tb=工4*y，iCi,j）EEfZi]=2地鐵轉(zhuǎn)地鐵是不同車型換乘的特例，且只可能在D12與D18轉(zhuǎn)乘，出現(xiàn)這種情況在

「，基礎(chǔ)上減少步行時間4分鐘:t產(chǎn)工滬「，基礎(chǔ)上減少步行時間4分鐘:ziiuZjk-2PD12.D1B在地鐵直達(dá)時，需要另外加上4分鐘出站步行時間:T日=知s%啟）=2若始發(fā)乘坐地鐵轉(zhuǎn)公交到達(dá)終點，需要增加步行時間2分鐘：L=Bj^B；Zjj=Z若始發(fā)乘坐公交轉(zhuǎn)地鐵到達(dá)終點，也需要增加步行時間2分鐘:Tf=2》YiiLi^j=e;Zt]=2總步行時間表示為:二=二一乙—二—二-二-二MinT1-FT2-FCtDeEfMinT1-FT2-FCtDeEf3）行程總費用最少設(shè)S表示i―的車輛票價屬性，貝I」：（1表示單一票制一元碣={ 2表示分段計價（3表不地鐵線路設(shè)二.表示i—'設(shè)二.表示i—'所過站數(shù)，那么if?'直達(dá)費用權(quán)皿=：.齊；,，..表示為行程總費用最少可表示為（正常票價-地鐵換乘免費）：4-q]'k=I1=1312^約束條件的建立（1）換乘次數(shù)約束基于對換乘次數(shù)最少這一目標(biāo)的分析，可得在有向賦權(quán)圖中換乘次數(shù)的表達(dá)式，以表示乘客所能接受的最大換乘次數(shù)，貝換乘次數(shù)約束可表示為：ce[0嚴(yán))且為整數(shù)從實際出發(fā)，查詢系統(tǒng)中的c值可由查詢用戶自己設(shè)定，當(dāng)最小換乘次數(shù)小于二?時，輸出無解。最短路起止點約束由于壬為有向圖，則其中頂點分為“起點”、“中間點”、“終點”三類。對有向圖而言，若求頂點 的最短路徑，以二?表示進(jìn)入第個頂點的邊，以二:表示出第個頂點的邊，貝U 中的三類點約束可表示為：I丹廠Xy^=H『二j=i j=i (0 (1Hs7ej地鐵間換乘約束站點i一'一間是否地鐵換乘地鐵，使用:心表示，那么與走的路徑-需要滿足：Yij+Yjk三2Yijk(i」k)EE'；Zi?Z|k=2地鐵轉(zhuǎn)地鐵情況只可能在D12與D18轉(zhuǎn)乘，故換乘總次數(shù)不能夠大于2：LY哽蘭2ZiPZik=2Cifjk)GEf0-1規(guī)劃模型的建立由和可得該模型的表達(dá)式：Min乙-1MinT1-FT2-FA A ( 1 0=s)/Yij-/Yji=\-1(i=e)j=i j=i (0 (i# 気可(Lj}eE' (Lj)eEr(iJ,k)eErzii^zjk(iJ,k)eErzii^zjk=2zij^zjk=2也j)￡tiJ.kJeE1'zjk=2Yjk三Yi]k》Yijk<2ySje{04}模型說明：換乘次數(shù)約束,表示轉(zhuǎn)乘次數(shù)應(yīng)在乘客所能接受的最多轉(zhuǎn)乘次數(shù)。最短路規(guī)劃中的起點，終點約束，其中三為起點，三為終點。5.2.6最短路模型的求解模型的評價方法一、基于數(shù)據(jù)庫;？與Dijkstra算法的“鄰接算法”求解此模型能夠求解出轉(zhuǎn)乘次數(shù)不超過兩次的所有可行方案，設(shè)計方案的速度較快，人們可依據(jù)自己的不同需求選擇出行方案，故模型實用性較強；但本模型還存在一定的局限性，一般不用于轉(zhuǎn)乘次數(shù)超過兩次的情況。方法二、使用Lingo軟件求解無轉(zhuǎn)乘次數(shù)限制的方案（針對不同目標(biāo)分別求解）上述最優(yōu)化模型規(guī)模較大，但是通過模型分析章節(jié)抽象，模型所有約束與目標(biāo)都已經(jīng)線性化，所以可采用Lingo軟件嚴(yán)格按照0-1模型求解。此方法在不限制最小轉(zhuǎn)乘數(shù)時可以求得全局最優(yōu)解。模型的結(jié)果表2.1一線S3359-S1828部分出行方案列表：求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo/鄰接1104S1784—L436L167—3鄰接1104S1784—L436L217—3鄰接1110S1241—L436L167—3鄰接1140S2364—L469L217—3Lingo465S2903,D12,D37,L15,L201,T02,7S1671L428,L41鄰接267S3697S1784L484L485L1673鄰接267S3697S1784L484L485L2173鄰接267S2027S1784L324L485L1673鄰接273D06S1784L484L485L1673

鄰接279S1842S1671L123L475L0413表2.2二線S1557-S0481部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo31021919,3186,903L84,L189,L91,L2394鄰接2109D20S3186L084L189L4603鄰接2109D20S3186L363L189L4603鄰接2112D20S3186L084L189L4603鄰接2112D20S3186L363L189L4603鄰接2112D20S2424L084L417L2543鄰接2112D20S2424L084L417L3123鄰接2112D20S2424L084L417L4473鄰接2121D20S1402L084L030L4603鄰接2121D20S1402L363L030L4603表2.3三線S0971-S0485部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用鄰接1131S2184一L013L417一3鄰接1146S2119一L013L395一3Lingo398D01,D15,3351L094,T001,L156,L4176Lingo/鄰接299D01D21L094T001L0515鄰接299D01D21L094T001L1045鄰接299D01D21L094T001L3955鄰接299D01D21L094T001L4505鄰接2124S2324S2482L013L132L4174鄰接2124S2324S2482L013L242L4174鄰接2127S3405S2515L013L079L4174表2.4四線S0008-S0073部分出行方案列表:求解方法轉(zhuǎn)乘時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo356.5D15,D12,D25L200,T001,T002,L1035鄰接183D13L159L4742鄰接186S3614L159L0582鄰接186S2083L463L0572鄰接186S3315L159L0583鄰接186S2303L355L3452鄰接258D30D25L150T002L1035

鄰接258D30D25L159T002L1035鄰接263.5D30D24L150T002L1035鄰接263.5D30D24L259T002L1035表2.5五線S0148-S0485部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo389.5D02,D15,3351L024,T001,L156,L4176Lingo/鄰接290.5D02D21L024T001L0515鄰接290.5D02D21L024T001L1045鄰接290.5D02D21L024T001L3955鄰接290.5D02D21L024T001L4505鄰接290.5D02D21L024T001L4695鄰接2109S0036S2210L308L156L4173鄰接2112S0036D20L308L157L4173鄰接2124S0036S1406L308L157L0453鄰接2124S0036S2082L308L156L0453表2.6六線S0087-S3676部分出行方案列表:求解方法轉(zhuǎn)乘總時間轉(zhuǎn)站點1轉(zhuǎn)站點2車輛1車輛2車輛3總費用Lingo030一一T002一一3鄰接033一一L231一一1鄰接042一一L381一一1問題三的模型建立與求解基于前面的分析公眾出行時除了出行時間最短外，需要考慮的因素還包括轉(zhuǎn)乘次數(shù)和行程費用。再依據(jù)分層序列法，建立最短路問題的0-1整數(shù)規(guī)劃模型。建立本模型首先要創(chuàng)建鄰接點矩陣E,需要考慮的兩個賦權(quán)值為乘車時間和步行時間，即賦權(quán)圖中任意兩點之間的權(quán)值有兩個，即乘車時間和步行時間＜：■，且都為已知量。令乘車時間對應(yīng)的決策變量為二.（0-1變量），步行時間對應(yīng)的決策變量為匚（0-1變量）。5.3.1目標(biāo)函數(shù)的建立：（1） 行程總時間最短Min（2） 行程總費用最少MinA昭j+ 工叫Min(詡詐" ]=012^10(ijJchE’5.3.2約束條件的建立(1)最短路約束由于行走路線中任意兩點間只會選擇一種出行方式，因此：xij+Yi,<1同時，決策變量還應(yīng)滿足最短路問題中的主要限制條件，如下:A A (1(i~)〉■(呵+yj—)仗ii+y』#_10=e)j=i j=i (o(1S,e)(2)換乘次數(shù)約束公眾在考慮出行時間盡量短的同時，也會考慮到換乘次數(shù)給出行帶來的不便。以：表示乘客所能接受的最大換乘次數(shù)，根據(jù)乘車次數(shù)確定換乘次數(shù)約束可表示為：地鐵間換乘約束站點. 間是否地鐵換乘地鐵，使用:心表示，那么節(jié):匸與走的路徑.需要滿足：yii+yjk三2Yijk(ijKkE'ZipZjk=2

地鐵轉(zhuǎn)地鐵情況只可能在D12與D18轉(zhuǎn)乘，故換乘總次數(shù)不能夠大于2：LY孫蘭2 禺呂*=2tiP>k)cBr5.3.3模型的建立根據(jù)問題分析中的目標(biāo)分析和主要約束分析可建立多目標(biāo)最短路模型，0-1規(guī)劃表達(dá)式(s為起點，e為終點)：

n n>（呵+%）-〉（號+均）=j=iCijltE*爼ij蘭Yijkj=in n>（呵+%）-〉（號+均）=j=iCijltE*爼ij蘭Yijkj=i1-10s.t<^jk三Yijk（iJ.k^eE"zij^zjk=2L04k）EBrSij+羯蘭1xLje{04}YijkE{0,1}Oj）占?j）占（iJ,k）eEr耳”現(xiàn)=25.3.4模型的求解在公交和地鐵交通網(wǎng)絡(luò)系統(tǒng)對應(yīng)的最短路權(quán)值確定的情況下，本模型線性可以考慮運用Lingo軟件編程求解，針對不同目標(biāo)分別求解可能比較容易。另外，針對本模型我們給出一種近似求解的算法。在所有站點之間的步行時間確定的情況下，公眾出行時可以考慮步行小段距離再換乘車次比較符合實際。基于這種思想，可以考慮將位置比較接近的站點抽象為一個點。此時可以根據(jù)問題二站點的抽象方法，將這種點抽象為一個點處理。為方便描述，將公交和地鐵整個系統(tǒng)描述為公交，算法思想如下：步驟1：輸入起始站點A和目的站點B；根據(jù)輸入的站點進(jìn)行優(yōu)化，映射入緊鄰站點集A=D：= E=二?'.c：o步驟2：查詢直達(dá)隊列表是否有A到B的乘車方案，若有則直接輸出結(jié)果；若無，繼續(xù)。步驟3：在公交站點數(shù)據(jù)庫中查出過站點上及緊鄰站點 的站點，及經(jīng)過站點B及緊鄰站點〉上U的公交線路；步驟4：判斷是否有 ，若有一條線路滿足要求，則該公交線路即為最優(yōu)線路輸出結(jié)果；若沒有，繼續(xù)。步驟5：從公交線路數(shù)據(jù)庫中查出經(jīng)過站點上的公