乘公交看奧運大學(xué)生數(shù)學(xué)模型

1、承諾書我們仔細(xì)閱讀了中國人學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明口，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨 詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他公開的資料 （包插網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在止文引川處和參考文獻中 明確列出。我們鄭重承諾，嚴(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é)人（打印并簽名）：fi期： 年 月 fi賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）:賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）:評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）:全國評閱編號（由全國組委會評閱前進行編號）:本文建立了乘公交看奧運最佳線路的選擇模型。在僅就滿足公眾對乘車耗時最少和花費最低的兩種需求，對三個情形：僅考慮公汽 的單一線路，同時考慮公汽與地鐵兩種線路，兼顧步行公汽地鐵 三種線路，分別建立了任意兩站點之間線路選擇問題的數(shù)學(xué)模型，依 托matlab軟

3、件編程給出相應(yīng)的的算法。并利用所建立的模型與算法, 求出給定的6對起始站一終到站之間的最佳路線，并做出了清晰的評 價說明。最后，本文還對模型作出了進一步分析、評價和推廣。針對問題一中僅考慮乘坐公汽，我們在對問題分析的基礎(chǔ)上，運用matlab軟件編程并搜索，就乘客的耗時最少需求，建立了模型i （耗 時最少的線路選擇模型），給出了相應(yīng)的算法步驟及程序框圖，并針 對六組得到如下結(jié)果：s3359s1828,換乘一次有兩條線路，都 經(jīng)過了 32個站點，所花費的時間均為101分鐘；s1557s0481：至少需換乘兩次，線路有兩條，也經(jīng)過32個站點，耗時101分鐘;s0971s0485：換乘一次，通過41站

4、，耗時128分鐘；s0008s0073：換乘一次，有14種不同線路，經(jīng)過26站，耗時83分鐘；s0148s0485：至少需換乘兩次，線路有6條，且都經(jīng)過32個站點，耗時101分鐘；s0087ts3676：換乘一次，經(jīng)過20站,耗時65分鐘。同樣，就乘客的費用最低需求，建立了模型ii （費用最低的線路選擇 模型），給出了相應(yīng)的算法步驟，得到結(jié)果詳見正文第12頁至第13 頁。針對問題二，同時考慮公汽與地鐵兩種線路，我們建立了模型iii （分步規(guī)劃模型），通過設(shè)計算法步驟,再運用matlab編程可求出以上完成，我們可求出以上六組點的結(jié)果，詳見正文第15頁至第18頁。針對問題三，兼顧步行公汽地鐵三種線

5、路，我們建立了模型iv （線路 綜合評價模型），第三題是在前面問題的基礎(chǔ)上，加入了步行這一較 為自主化的“交通工具”，使得原本的選擇最優(yōu)線路模型不再適用，于 是我們這里建立了一個線路綜合評價模型，通過分類討論的方式，提 供適合各種情況的線路選擇方案,從而解決在三種交通工具并行時的 路線選擇問題。本文最后還對這一自主查詢系統(tǒng)進行了推廣，將自主查詢系統(tǒng)推廣到 手機彩信或短信，給出了系統(tǒng)結(jié)構(gòu)設(shè)計和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖；同時，將 這一自主查詢系統(tǒng)應(yīng)用到旅游線路選擇上，并繪制了旅游線路選擇系統(tǒng)結(jié)構(gòu)圖。關(guān)鍵詞：線路選擇；換乘；分步規(guī)劃;自主查詢系統(tǒng)；matlab§1、問題的重述一、問題背景1、看奧運要

6、出行 2008年8月8日至8月24日，我國人民翹首企盼的第29屆奧運會將在北京舉行，屆時將會有大量觀眾從不同地點到達(dá)比賽現(xiàn)場去觀看 奧運盛況，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。2、乘公交需擇線這些年來，隨著科技進步、政府投資及市政部門對城市道路的不斷完 善，我國城市的公交系統(tǒng)有了很大發(fā)展，作為我國首都北京市, 它的公交線路已多達(dá)800條以上，這使得廣大市民的出行更加通暢、 便利。但是，同時也因線路的眾多，為廣大市民的出行帶來一個新的 問題，乘車從一個地方到另一個地方，如果都在同一條公交線路上, 市民則不存在選擇；如果需要換乘，特別是二次以上的換乘，市民則 面臨

7、著多種選擇，可分別從選最短線路、花最少時間、用最少換乘、 節(jié)省票價等各個方面進行決策，以實現(xiàn)出行任務(wù)的完成。3、做系統(tǒng)先建模針對市場需求，某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自 主查詢計算機系統(tǒng)。為了設(shè)計這樣一個系統(tǒng)，其核心是線路選擇的模 型與算法，應(yīng)該從實際情況出發(fā)考慮，滿足查詢者的各種不同需求。二、有關(guān)數(shù)據(jù)1、基本參數(shù)設(shè)定.-ail相鄰公汽站平均行駛時間（包括停站時間）：3分鐘;相鄰地鐵站平均行駛時間（包括停站時間）：2.5分鐘;公汽換乘公汽平均耗時:5分鐘（其中步行時間2分鐘）;地鐵換乘地鐵平均耗時:4分鐘（其中步行時間2分鐘）;地鐵換乘公汽平均耗時：7分鐘（其中步行時間4分鐘）

8、;公汽換乘地鐵平均耗時：6分鐘（其中步行時間4分鐘）;公汽票價：分為單一票價與分段計價兩種，標(biāo)記于線路后；其中分 段計價的票價為：020站：1元；2140站：2元；40站以上：3 元；地鐵票價：3元（無論地鐵線路間是否換乘）。注：以上參數(shù)均為簡化問題而作的假設(shè)，未必與實際數(shù)據(jù)完全吻合。2、公交線路及相關(guān)信息（詳見附件2中文本文檔1、1.1、1.2及2、 21、2.2 ）o三、問題提出1、問題一：僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與 算法，求出以下6對起始站-終到站之間的最佳路線（要有清晰的評 價說明）。 s3359s1828；

9、s1557s0481；s0971s0485； s0008s0073；s0148s0485；s0087s3676。2、問題二：同時考慮公汽與地鐵線路，解決問題一中兩個問題。3、問題三：假設(shè)又知道所有站點之間的步行時間，請你給出任意兩 站點之間線路選擇問題的數(shù)學(xué)模型。§2、問題的分析一.問題的總體分析與相關(guān)量的明確1、問題的總體分析乘公交看奧運公交線路選擇問題涉及到數(shù)百條公汽線路與兩條地鐵 公交線路、數(shù)千個公汽站點與幾十個地鐵站點、三類不同乘車票價信 息、上行下行單行環(huán)形四種車行方向等多個因素，且出行查詢者的通 常需求分別有選最短線路、花最少時間、用最少換乘以及用最低票價, 當(dāng)然這些需求

10、在小城市道路比較單一時可能是相一致的，但對擁有眾 多車輛及線路且道路如網(wǎng)的首都北京而言，這些需求則不盡然。故問 題這是一類多因素多數(shù)據(jù)計算機查詢信息處理及多目標(biāo)決策問題，核 心是算法。2、幾個重要的量為了便于解決問題，下面我們先明確問題涉及到的幾個重要相關(guān)量。 運用相關(guān)的統(tǒng)計方法，從競賽b題所給的壓縮文本文檔中，我們不 難得到以下幾個量的準(zhǔn)確信息: 公交線路：520條公汽線路，編號：l001l520；兩條地鐵線路t1 與t2。公交站點：3957個公汽站點，編號：s0001s3957；39個地鐵站點，編號：d01d39。公汽線路與站點:文本文檔1.1具體地給出了 520條公汽線路編號, 票價信息

11、，車行線信息（詳見2007年競賽b題壓縮文本文檔l.l）o 地鐵線路與站點：文本文檔1.2具體地給出了北京地鐵線路t1與t2,我們通過上網(wǎng)搜索1很易獲取相關(guān)的地鐵圖片（圖1）與北京地鐵tl、t2線路圖（圖2）。結(jié)合文檔12所給北京地鐵線路t1與t2的信息，我們不難發(fā)現(xiàn)，地鐵t1的23個站與地鐵t2的16個站 相吻合，且圖2中的復(fù)興門為d12與建國門為d18是可以換乘的兩 個站。二、對具體問題的分析1、對問題一的分析問題：僅考慮公汽線路，給出任意兩公汽站點之間線路選擇問題的般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用所給出的模型與算法, 求出6對起始站t終到站之間的最佳路線，且要有清晰的評價說明。分析

12、：要尋找兩站之間的最佳公交線路，就是要滿足不同乘客乘坐 公交的一定要求，比如選最短線路、花最少時間、用最少換乘或花最 低票價等等。為了簡化對問題的解決，我們不妨假定求最佳路線，僅 在乘車耗時最少、花費最低兩種條件下確定最佳公交線路。對于在同一線路上的任意兩個站點，若通過兩個站點的線路僅一條（如圖3左），顯然這一條也就是最佳路線；若通過兩個站點的線路 有兩條及兩條以上的線路，按基本參數(shù)設(shè)定知，最佳路線是中間站 點數(shù)最少的線路，如圖3右圖中藍(lán)色的直線即最佳路線。圖3兩站間通過的線路僅一條與兩站間通過的線路有兩條線路圖 對于不在任何一條公交線路上的兩個站點，即沒有直達(dá)的公交線路, 則要考慮換乘，若通

13、過起始站的所有線路和通過終到站的所有線路有 且僅有一個公共站點，如圖4左可知，則相交站點的線路acb即為 最佳路線;若通過起始站的所有線路和通過終到站的所有線路多于 個公共站點，如圖4右c站和d站均為換乘站點，顯然同樣換乘次 數(shù)時換乘線路所經(jīng)過的站數(shù)較少的acb線要優(yōu)于adb,從而acb線為最佳路線。同樣換乘次數(shù)時多于兩條換乘線的，則換乘線路所經(jīng) 過站數(shù)最少的為最佳路線。圖4兩站間換乘一次線路僅有一條與換乘一次線路有兩條線以上的 線路圖如果對進行一次換乘不能完成出行任務(wù)的，我們要進行兩次換行計劃。類似上述的分析，我們可以得到兩次的換乘情形下的最佳路線。顯然這要比前兩類情形復(fù)雜得多,但運用計算機

14、進行編程一般是可以 實現(xiàn)的。如果對進行兩次換乘仍不能完成出行任務(wù)的，我們要進行三次或三次 以上的換乘。但考慮到換乘三次及三次以上研究的技術(shù)處理和實際操 作太復(fù)雜且實際意義不大，故在最初建模時可不予考慮，在對建模進 行改進時，可酌情考慮。當(dāng)然，對于基于最低價格的最佳模型求解,除了要考慮以上的分析外, 我們還要考慮各類票價信息。首先我們要搜索出所有需要分段計價的 公汽線路，然后根據(jù)題目中的分段計價要求建立一個價格矩陣，再由 前述換乘法求出的結(jié)果進行價格計算，看是否滿足價格最小的條件, 對不滿足的利用排序求出最小價格，并得到相對應(yīng)的線路信息。2、對問題二的分析問題：同時考慮公汽與地鐵線路時，解決問題

15、一的建模、算法和6 條最佳路線。分析：問題二是在問題一只有公共汽車單一交通工具的基礎(chǔ)上，通 過引入地鐵這一交通工具，使得轉(zhuǎn)乘不僅僅是公汽轉(zhuǎn)公汽，還包括公 汽轉(zhuǎn)地鐵，地鐵轉(zhuǎn)地鐵，地鐵轉(zhuǎn)公汽，使得轉(zhuǎn)乘問題復(fù)雜化。為了得 到用時最少的線路，我們可考慮建立了分步規(guī)劃模型進行求解，將總 用時最少這一規(guī)劃問題，分成在每次搭乘都用時最少的分布規(guī)劃問 題。從而在綜合考慮公汽與地鐵的情況下確定了最佳線路。3、對問題三的分析問題：假設(shè)又知道所有站點之間的步行時間，請你給出任意兩站點 之間線路選擇問題的數(shù)學(xué)模型。分析：第三題是在前面兩個問題的基礎(chǔ)上，加入了步行這一較為自 主化的“交通工具”，使得原本的選擇最優(yōu)線路模

16、型不再使用，于是我 們這里建立了一個線路綜合評價模型，通過分類討論的方式，提供適 合各種情況的線路選擇方案，從而解決在三種交通工具并行時的路線 選擇問題。§3.模型的假設(shè)1、為便于研究問題，規(guī)定每條線路起點站的位標(biāo)為1,從起點站至終點站的其余各站的位標(biāo)依次為2、32、由于基本參數(shù)已設(shè)定，不再考慮發(fā)車頻率和乘客到達(dá)時刻及等待時間;3、由于公交線路的交錯復(fù)雜，不考慮公交線路的編排次序和公交站點的編排次序；4、交通狀況良好，無交通阻塞及其它影響交通運營的異常情況發(fā)生;5、作為交通系統(tǒng)比較發(fā)達(dá)和完善的首都北京，聯(lián)通任意兩站間的線路最多換乘兩次，換乘三次及三次以上研究太復(fù)雜且實際意義不大, 故

17、不予考慮。§4、名詞解釋與符號說明一、名詞解釋1、換乘:從一輛車下來轉(zhuǎn)乘另一輛車的過程;2、位標(biāo)：為建模而自行定義的變量，規(guī)定一條線路從始發(fā)站起各站的位標(biāo)依次為1、 2、 3、二、符號說明1. :所有公汽線路數(shù)據(jù)處理后得到的;2. :經(jīng)過起始站s1的所有線路站臺矩陣;3. :經(jīng)過終到站s2的所有線路站臺矩陣;4.,:公汽的起始站點;5. :公汽的終到站點；6. :只考慮公汽情況下起始站與終到站的公共站點；7. :公共站點與起始站在同一線路上的公共站點的列標(biāo)；& :公共站點與終到站在同一線路的公共站點的列標(biāo)；9. :與公共站點在同一條線路上的起始站的列標(biāo)；10. :與公共站點在

18、同一條線路上的終到站的列標(biāo)；12.11:只考慮公汽情況下從起始站到公共站點的站點數(shù)量，即;:只考慮公汽情況下從公共站點與終到站的站點數(shù)量，即；12.:只考慮公汽情況下從起始站到終到站的總的站點數(shù)量，即；13:只考慮公汽情況下耗費時間最少情況下得到的最佳路線的中轉(zhuǎn)14.站;:只考慮公汽情況下乘車費用最低情況下得到的最佳路線的中轉(zhuǎn)15.站;:為使得以一個向量的形式輸出，同時為了循環(huán)的方便而引進的變量，初值為1;16.:乘車所耗費的總時間，包括等待和轉(zhuǎn)乘的時間;17.:所有分段計價線路數(shù)據(jù)組成的矩陣;18.:只考慮公汽情況下從起始站到中轉(zhuǎn)站的票價;19.:只考慮公汽情況下從中轉(zhuǎn)站到終到站的票價;20

19、.:耗時最少的最佳路線的乘車費用，計算得到價格并計算出最低價格;21:乘車費用最低的最佳路線的最低乘車費用;22.:根據(jù)分段計價標(biāo)準(zhǔn)的不同得到的的分段計價價格向量，由數(shù)字1,2,3組成；23dij：地鐵相鄰的公汽站臺矩陣；24. p：矩陣dij與矩陣b的交；25. q：矩陣dij與矩陣c的交；26. :矩陣b與矩陣dij的公共元素；27:矩陣c與矩陣dij的公共元素；28.ti：乘坐交通工具時經(jīng)歷的時間； 2910：交通工具換乘用時平均耗時;30. ni：乘坐交通工具時經(jīng)過的有效站臺數(shù);31. :任意兩站點i、j之間的步行時間。§5.模型的建立與求解從所要解決的問題和對問題所做的假設(shè)

20、出發(fā)，我們對問題一分別建立 了模型i （耗時最少的線路選擇模型）和模型ii （費用最低的線路選 擇模型），我們對問題二建立了模型iu （分步規(guī)劃模型），我們對問題 三建立了模型iv （線路綜合評價模型）。一、問題一的分析與求解1、問題一的分析要尋找兩站之間的最佳公交線路,就是要滿足各類乘客乘坐公交的不同要求，為了簡化對問題解決，我們大體上認(rèn)為最佳路線即是乘車耗時最少、乘車費用最:少兩種情況來對問題一進行求解。為了實現(xiàn)這一目標(biāo)，我們對題目給出的大量數(shù)據(jù)進行了相應(yīng)的處理，發(fā)現(xiàn)對問題中 列出的六組站點，都無法根據(jù)現(xiàn)有的公交線路直達(dá)，于是就要考慮公 交車的換乘問題。在考慮到技術(shù)處理和實際操作的可行性，

21、我們不妨 假設(shè)最多換乘兩次就可以到達(dá)任意站點，否則，乘客可以根據(jù)車行方向隨機地選擇車路，然后到一定車站后再行查詢，或通過步行到能夠附近站點。對于基于乘車費用最少的模型求解，我們首先搜索出所有需要分段計價的公汽線路,然后根據(jù)題目中的分段計價要求建立一個價格矩陣，首先對由模型i求出的結(jié)果進行價格計算，看是否滿足價格最小的條件，對不滿足的利用排序求出最小價格，并得到相對應(yīng)的線路信息。2、建模的思想建立數(shù)據(jù)庫 為了確定公汽線路的最佳路線選擇，首先把附錄2中的文本文檔“11 公汽線路信息txt”進行處理，并轉(zhuǎn)換到excel軟件中，形成以第一列 線路為公汽線路編號，第二列為價格信息，第三列為車行性質(zhì)，第四

22、 列為各線路上所有車站點的大型數(shù)據(jù)庫（詳見附錄3）,以此為基礎(chǔ),f面進一步研究。搜索起始站和終到站所經(jīng)過的線路 通過對數(shù)據(jù)庫的搜索，查詢起始站和終到站是否有相同的車經(jīng)過，如 果有且僅有一條，即為最佳乘車線路；如果有且多于一條，則只要計 算從起始站到終到站的總站數(shù)，通過比較可以得到戰(zhàn)數(shù)最少的公交線 路，推薦給乘客。我們可用vb語言編程建立計算機循環(huán)查詢系統(tǒng)。運用此系統(tǒng)產(chǎn)生的對話框進行查詢起始站和終到站是否有相同的車 經(jīng)述 我們只要輸入起始站的站名（比如s0001）,然后再輸入終到 站的站名（比如s0158）,則在打開的excel文件前的對話框里產(chǎn)生一 串語句，比如有，則在回答“直達(dá)3且緊跟“直達(dá)

23、，啲后面給出了起始 站到終到站的站數(shù)，結(jié)束；如果沒有，則回答“不能直達(dá)”，下面再轉(zhuǎn) 入下一步研究。尋找一次換乘的線路 分別從數(shù)據(jù)庫中搜索通過起始站的所有線路和通過終到站的所有線 路，并將線路放到一起進行比較，如果存在公共的交點，則說明進行一次換乘即可完成出行計劃。如果一次換乘的線路為一條，則是最佳 乘車線路；如果一次換乘的線路多于一條，再通過計算通過的站點數(shù) 進行比較，從而可找出站點數(shù)最小的最佳乘車線路。如果不存在公共 的交點，則要進行兩次或兩次以上的換乘。尋找兩次換乘的線路對上一步完成對數(shù)據(jù)庫搜索后，若通過起始站的線路和通過終到站的線路不存在公共的站點，則對通過起始站線路的所有站點和對通過終

24、 到站線路的所有站點再進行第步的搜索，若存在存在公共的線路, 則說明進行二次換乘即可完成出行計劃。否則，我們考慮作為交通系 統(tǒng)比較發(fā)達(dá)和完善的首都北京，聯(lián)通任意兩站間的線路最多換乘兩 次，換乘三次及三次以上研究太復(fù)雜且意義不大，故不予考慮。3、模型i耗時最少的線路選擇模型模型的準(zhǔn)備 在尋找最佳線路之前，我們要給公汽線路信息給出的大量數(shù)據(jù)進行處 理，即對上下行站點完全相同的數(shù)據(jù)補出它的下行數(shù)據(jù)；同時為處理 簡便起見，對環(huán)行線路我們以相同的線路寫出它的下行路線，并對所 有空白數(shù)據(jù)均補“0”。經(jīng)過處理，得到一個1040行86列的的大矩陣a1040x86o下面我們以站點s3359s1828為例來說明公

25、汽站點的最佳路線選擇問題，其具體處理步驟如下： 查找通過起始站與終到站的線路數(shù)利用數(shù)據(jù)庫，我們運用軟件|1編程，可查找出通過起始站s3359和通過終到站s1828的線路數(shù)和具體線路數(shù)。a. 通過起始站s3359的線路有26條（包括上、下行）：l015（上下行）、l123（上下行）、l132（上下行）.l291（上下行）、l324（上 下行）、l352（上下行）、l366（上下行）、l378（上下行）、l436（上下行）、 l469（±下行）、l473（上下行）、l474（上下行）、l484（上下行）。b. 通過終到站s1828的線路有10條（包括上、下行人l041（上下行）、l167

26、（上下行）、l182（上下行）、l217（上下行）、l238（上下行） 因此，可以得到一個以通過s3359的線路為行、每行所有站點為列的 的矩陣，同理得到一個以通過s1828的線路為行、每行所有站點為 列的的矩陣。 確定公共點的位標(biāo) 為方便建模及其算法，下面定義一個新的名詞。定義：規(guī)定一條公交線路從始發(fā)站起到終點站止各站的編號為位標(biāo),位標(biāo)的大小依次為1、2、3、 no通過分析，我們了解到題目給出我們要求計算的起始站與終到站之間 沒有直達(dá)的情況，于是我們要考慮換乘車的問題。首先從換乘一次車 的情況入手，我們利用的查找命令求出起始站s3359與終到站s1828 所有線路上的公共站點組成了集合，以及

27、這些公共站點與起始站s3359在同一線路的位標(biāo)、這些公共站點與終到站s1828在同一線路的位標(biāo)。 求換乘一次的總站點數(shù) 通過索引，我們可以求出與對應(yīng)公共站點在同一條線路上的起始站的 位標(biāo) 和這個公共站點在同一條線路上的終到站的位標(biāo)，再利用公共 站點與起始站在同一線路中列標(biāo)的差額以及公共站點與終到站在同 一線路中列標(biāo)的差值就可以得到從起始站到公共站點的站點數(shù)量和 公共站點與終到站的站點數(shù)量，即，?？紤]到公汽的行駛順序一定、無法反向行駛等實際意義，我們只對的 數(shù)據(jù)進行計算，然后把得到的相加就可以得到總的站點數(shù)量，即。 確定目標(biāo)函數(shù) 由于題目中給出了相鄰公汽站平均行駛時間相等（均為3分鐘）的設(shè) 定，

28、所以要達(dá)到耗時最少，我們規(guī)定使得所經(jīng)過的站點最少即可，于 是我們利用上述步驟求得不同路線經(jīng)過的最少站點數(shù)量就可以得到 耗時最少情況下的最佳線路，即可得到對應(yīng)的最佳線路的中轉(zhuǎn)站。此時得到的花費時間為，其中包括了公汽換乘公汽平均耗時5分鐘。模型的建立 通過上述分析，我們得到如下的耗時最少的線路選擇模型: 目標(biāo)函數(shù) 約束條件 算法步驟 設(shè)起始站為，終到站為，具體的算法可按以下五個步驟來實現(xiàn): 搜索求出與站點的數(shù)據(jù)在矩陣中的位置，并構(gòu)造成矩陣; 在的情況下利用查找矩陣的公共元素; 搜索出中第 行的數(shù)據(jù)等于以及中第 行的數(shù)據(jù)等于的數(shù)據(jù)所 在列，只考慮和的情況； 在循環(huán)外層引進變量，并賦初值，計算從起始站

29、到終到站所經(jīng) 過的所有站點數(shù)，其中，并得到與其對應(yīng)的的值，將的數(shù)據(jù)以向 量的形式顯示出來; 求出的最小值，并輸出對應(yīng)最小值所在的線路以及中轉(zhuǎn)站。程序框圖（如圖5所示，程序見附錄） 圖5算法流程圖 模型的結(jié)果 對問題一的第二小問，根據(jù)附錄數(shù)據(jù)，利用上面的模型與算法，求出6對起始站-終到站之間的耗時最少的線路選擇及耗時如下:s3359s1828的最佳路線：首先在l436路車下行路線從s3359s2026ts1132ts2266ts2263ts3917s2303ts2301ts3233ts0 618ts0616ts2112ts2110s2153ts2814ts2813ts3501ts351 5-&g

30、t;s3500ts0756->s0492s0903->s1768ts0955->s0480ts2703s2800s2192ts2191s1829s3649s1784,然后在 s1784 站 點換乘l217路車下行路線，下站即為s1828站；或者在s1784站點 轉(zhuǎn)乘l167路下行路線，下站也是s1828站。因此，得到=31, 兩種換乘方式都經(jīng)過了 32個站點。所花費的時間為分鐘。s1557s0481的最佳路線：線路1：首先在l363路車下行路線從s1557站開始乘車，途經(jīng)s3158ts2628s3408ts2044s1985ts2563ts2682ts2735ts0029ts

31、0055ts0051ts1919,然后在s1919站點換乘l189路車下行路線，途經(jīng)s1919s2840->s1402->s3186,之后在s3186站點換乘l460 路 車 下 行 路 線， 途 經(jīng)s3186fs3544->s2116->s2119ts1788->s1789ts1770fs2322ts0992ts2184ts2954ts3117ts2424ts1174ts0902ts903ts2101s0481。此種轉(zhuǎn)乘方式經(jīng)過了 s1919. s3186站點的共兩次換乘,共經(jīng)過了 32站，所花費的時間為分鐘;線路2：首先在l084路車下行路線從s1557站開始

32、乘車，途經(jīng)s3158fs2628->s3408fs2044->s1985fs2563->s2682->s0028->s0029ts0055s0051s1919,然后在s1919站點換乘l189路車下行 路線，途經(jīng)s1919s2840ts1402ts3186,之后在s3186站點換乘l460 路 車 下 行 路 線， 途 經(jīng)s3186ts3544ts2116ts2119ts1788ts1789s1770ts2322ts0992->s2184s2954->s3117->s2424s1174s0902->s903s2101 s0481。此種轉(zhuǎn)乘方

33、式經(jīng)過了 s1919、s3186站點的共兩次換乘，共經(jīng)過了 32站，所花費的時間為分鐘。s0971s0485的最佳路線：首先在l013路車下行路線從s0971站 開 始 乘 車，途 經(jīng)s3832ts3341->s2237ts3565->s3333ts1180s3494->s1523->s1 520ts1988ts1743ts1742ts1181ts1879ts3405ts2517s3117s2954ts0531ts2184,然后在s2184站點換乘l417路車下行路線， 途 中 經(jīng) 過 以 下 站ts3186ts3409ts2717ts1402ts2840ts0643s

34、2079ts1920ts2480s2482ts221 0s3332ts3351 s0485此種換乘方式經(jīng)過了 41站。所花費的時間為分鐘。s0008s0073的最佳路線：首先在l463路車下行路線從s0008站 開 始 乘 車，途 經(jīng)s0008ts1383ts1688ts3459s2532ts3474ts0369ts1776ts2855ts0338ts2849ts2782ts0935ts2084ts2083,然后在 s2083站點換乘l057路車上行路線，途中經(jīng)過以下站點：s2083ts1538ts3547ts0609ts0483ts0604ts2650ts3470ts2 619s2340ts

35、3162ts2181ts0073此種換乘方式共經(jīng)過了 26站。所花費的時間為分鐘。（本問有14種不同的換乘最佳方案，其他13種換乘方案詳見附錄） s0148s0485的最佳路線: 首先在l308路車上行路線從s0148站開始乘車，途經(jīng)s0462ts0361s1797ts2221ts0302ts2222ts2737ts1716ts0128->s2268s1308->s1391f s2272s0036 然后在 s0036 站點換乘ts 路 車 上 行 路 線， 途 經(jīng)s0036ts3233->s0618ts0617->s0721ts2057->s2361->s0

36、608->s0399ts2535ts2534ts0239ts0497ts2090ts2082s2210 ,之后 在s2210站點換乘l417路車下行路線，途經(jīng) s2210s3332->s3351f s0485。此種轉(zhuǎn)乘方式經(jīng)過了 s0036、s2210站點的共兩次換乘，共經(jīng)過了 33站，所花費的時間為分鐘。（本問有3種不同的換乘最佳方案，其他2種換乘方案詳見附錄1-2） s0087s3676的最佳路線：首先在l454路車上行線路從s0087乘 車，途 經(jīng)s0857ts0630ts1427ts1426ts0541ts0978ts3389ts1919ts0641s2840ts3496,

37、然后在s3496站點換乘l209路車下行路線，途中經(jīng)過以下站點：s3496ts1883ts1159ts2699ts2922ts3010ts0583ts1987ts0082->s3676此種換乘方式共經(jīng)過了 20站。所花費的時間為分鐘。4、模型ii費用最低的線路選擇模型模型的準(zhǔn)備 我們?nèi)砸詮钠鹗颊緎3359到終到站s1828的線路為例進行說明。 首先對題目給出的分段計價的信息進行數(shù)據(jù)處理，通過搜索找到所 有的分段線路，然后根據(jù)分段計價對乘坐站數(shù)不同而制定的具體計價 要求（020站：1元；2140站：2元；40站以上：3元）建立一 個價格向量，又由于共有86列的數(shù)據(jù)，于是我們得到一個前20列

38、為1, 21到40列為2, 41到86列為3的向量則即為在分段計價情況下從起始站到中轉(zhuǎn)站的公汽票價，為分段計 價情況下從中轉(zhuǎn)站到終到站的票價（、為整數(shù)，且）。 在模型i方法的基礎(chǔ)上，得到通過在中轉(zhuǎn)站的轉(zhuǎn)乘所計算出來的從 起始站s3359到終到站s1828所經(jīng)過的站點總數(shù),然后判斷得到的各個方案所經(jīng)過的路線是分段計價還是單一票制。因此，對從起始站到中轉(zhuǎn)站的票價和從中轉(zhuǎn)站到終到站的票價要進行分段討論： 在模型i結(jié)果的基礎(chǔ)上，為了達(dá)到在所用時間最少的同時乘車費用 盡可能少的要求和便于大量數(shù)據(jù)進行比較處理以及在多種消耗時間 最少的最佳線路中進行篩選，我們在模型i計算出的最佳線路的基礎(chǔ) 上計算出一個費用

39、并與實際乘車的最低費用 進行比較，看其是否相 等。如果，說明我們第一問中的最佳線路不僅滿足了所消耗時間最 少的目標(biāo)，而且還使得其所花費的乘車成本最低，這樣可以達(dá)到一舉 兩得的效果；如果，說明我們在所消耗時間條件下的乘車費用不一 定最低，于是我們再通過排序得到最小結(jié)果以及其所對應(yīng)的行進線路 和中轉(zhuǎn)站。模型的建立由以上分析，我們可以得到目標(biāo)函數(shù)：由于我們在求解時考慮了耗時最少情況下能否同時達(dá)到乘車費用最 少，因此我們目標(biāo)函數(shù)的求解需要分兩步進行求解。首先，我們要對 模型i做出的耗時最少的最佳線路計算其費用，如果與通過排序得到 的最低費用相同，就可以同時達(dá)到耗時最少、費用最低的雙目標(biāo)，如 果大于最低

40、費用，我們就要利用下面的約束條件來計算出最低費用情 況下的具體線路及中轉(zhuǎn)站，可以得出約束條件。結(jié)合目標(biāo)函數(shù)有模目標(biāo)函數(shù)：約束條件為:算法步驟 設(shè)起始站為，終到站為，具體的算法實現(xiàn)如下: 對矩陣搜索得到分段計價線路矩陣，并構(gòu)造分段價格向量; 搜索求出與站點的數(shù)據(jù)在矩陣中的位置，并構(gòu)造成矩陣; 在的情況下查找矩陣的公共元素，即; 搜索出中第 行的數(shù)據(jù)等于以及中第 行的數(shù)據(jù)等于的數(shù)據(jù)所 在列，只考慮和的情況; 在模型i計算出的的最小值的基礎(chǔ)上,計算得到價格并計算出最 若，則得到最佳線路結(jié)果；若，輸出最低費用情況下的線路及中 轉(zhuǎn)站點。模型結(jié)果利用編程實現(xiàn)可得到結(jié)果（程序詳見附錄）: s3359s182

41、8的最佳路線：首先在l436路車下行路線從s3359站 開 始 乘 車，途 經(jīng)s2026ts1132ts2266ts2263ts3917s2303ts2301ts3233ts0 618ts0616ts2112ts2110ts2153ts2814ts2813ts3501t s3515ts3500ts0756ts0492ts0903ts1768ts0955ts0480ts2703s2800ts2192ts2191ts1829ts3649ts1784,然后在 si784 站點換乘l217路車下行路線，下站即為s1828站；或者在s1784站點轉(zhuǎn)乘l167路下行路線，下站也是s1828站。因此，得到=

42、31,兩種換乘方式都經(jīng)過了 32個站點。乘車費用均為3元，與實際的最低費用相等。 s1557s0481的最佳路線： s0971s0485的最佳路線：首先在l013路車下行路線從s0971站 開 始 乘 車，途 經(jīng)s3832ts3341s2237ts3565ts3333ts1180ts3494ts1523ts1 520ts1988ts1743ts1742ts1181ts1879s3405ts2517ts311 7ts2954s0531ts2184,然后在s2184站點換乘l417路車下行路線， 途 中 經(jīng) 過 以 下 站點 ：s2184ts0992ts2322ts1770ts1789ts2119

43、ts2116ts3544ts3186ts3409ts2717ts1402s2840ts0643ts2079ts1920ts2480ts2482ts2210ts3332s3351ts0485此種換乘方式經(jīng)過了 41站。乘車費用均為3元，與實際的最低費用相等。s0008s0073的最佳路線：首先在l463路車下行路線從s0008站 開 始 乘 車，途 經(jīng)s0008ts1383s1688ts3459s2532ts3474ts0369ts1776ts2855ts0338ts2849ts2782ts0935ts2084ts2083,然后在 s2083站點換乘l057路車上行路線，途中經(jīng)過以下站點：s20

44、83ts1538ts3547ts0609ts0483ts0604ts2650ts3470ts2 619s2340ts3162ts2181ts0073用相等。（本問有14種不同的換乘最佳方案，其他13種換乘方案詳見附錄1-1）s0148s0485的最佳路線：首先在l308路車上行路線從s0148站開始乘車，途經(jīng)s0462ts0361s1797ts2221ts0302ts2222ts2737ts1716ts0128->s2268s1308->s1391->s2272->s0036 然后在 s0036 站點換乘-s 路 車 上 行 路 線， 途 經(jīng)s0036fs3233-&g

45、t;s0618fs0617->s0721fs2057->s2361->s0608->s0 399s2535fs2534ts0239ts0497ts2090s2082s2210,之后在s2210站點換乘l417路車下行路線，途經(jīng)s2210ts3332->s3351ts0485。此種轉(zhuǎn)乘方式經(jīng)過了 s0036、s2210站點的共兩次換乘，共經(jīng)過了 33站，所花費的時間為 分鐘。（本問有3種不同的換乘最佳方案，其他2種換乘方案詳見附錄1-2） s0087s3676的最佳路線：首先在l454路車上行線路從s0087s0857ts0630ts1427ts1426s0541t

46、s0978ts3389ts1919ts0641s2840ts3496,然后在s3496站點換乘l209路車下行路線， 途 中 經(jīng) 過 以 下 站 點：s3496ts1883ts1159ts2699ts2922ts3010ts0583ts1987ts0082s3676用相等。最少的乘車路線。二、問題二的分析與求解1、模型iii分步線性規(guī)劃模型模型的準(zhǔn)備我們在模型i中只以公共汽車為交通工具的基礎(chǔ)上，引進地鐵這一快 捷方便的搭乘工具,重新建立一套新的公交和地鐵最佳線路選擇問題 的自主查詢系統(tǒng)，使得這一系統(tǒng)能夠自主的提供一個公交和地鐵交替 使用的用時最少的線路，從而為趕時間的乘客提供更加人性化的建 議

47、。這里共給出tl、t2兩條地鐵線路和地鐵站臺相鄰的若干個公汽站, 且兩條線路可以相互換乘，換乘只能在d12和d18兩個站點。因此 我們認(rèn)為兩個地鐵是相通的，可以任意換乘，且可以在從一個地鐵站 到達(dá)其他任意一個地鐵站。這里我們將tl. t2兩條地鐵線路看成一 條地鐵。建立地鐵站臺相鄰公汽矩陣:tl, t2地鐵站臺相鄰公汽矩陣分別為,:由于我們將tl、t2兩條地鐵線路視為一條地鐵線路，因此可以得到 所有地鐵站臺相鄰公汽矩陣: 模型的算法 在所有地鐵站臺相鄰公汽矩陣中搜索，是否有所要的起始站與終 到站，如果有則可以通過地鐵從起始站直達(dá)終到站; 當(dāng)在中沒有搜索到起始站與終到站時，這說明地鐵只能作為整

48、個線路中的中間搭乘工具,前后都必須通過搭乘公共汽車來連通起始 站，如圖6圖6公汽、地鐵換乘示意圖 這里就涉及到在該在哪一站搭乘地鐵和在哪一站下地鐵這一問題。為 解決這一問題，我們將矩陣中所有元素進行迭代搜索，這一步驟分 成兩步完成：先搜索經(jīng)過起始站的所有線路矩陣b與矩陣的公共 元素，其中；再搜索經(jīng)過終到站的所有線路矩陣c與矩陣的公 共元素，其中。 這里我們依據(jù)時間t最小為目標(biāo)，選取所有線路中的最短路線。這 里t是由四部分組成，分別為乘坐公共汽車l1的時間tl、乘坐地鐵t的時間12、乘坐公共汽車l2的時間t3、交通工具換乘用時to,其中交通工具換乘用時to包括：換乘地鐵平均耗時t01=4分鐘（其

49、中步 行時間2分鐘）；地鐵換乘公汽平均耗時t02=7分鐘（其中步行時間4.tiii分鐘）；公汽換乘地鐵平均耗時t03=6分鐘（其中步行時間4分鐘）；因 此總用時t為: 其中tl、t2、t3是由經(jīng)過的站數(shù)決定的，設(shè)li. l2> t經(jīng)過的站點數(shù)依次為：nl、n2、n3,貝!j：由于中我們是分兩步來進行的，因此要分兩步求最優(yōu)線路，即兩段都是最短線路時得到最優(yōu)線路。 在中存在tl、t2兩條地鐵線路的轉(zhuǎn)乘問題，這就涉及如何計算n2的問題。由于地鐵轉(zhuǎn)乘只能在d12、d18里兩個站臺，需要對于不同的上下地鐵的站臺進行分類討論，計算出有效站臺數(shù)h2。我們 通過if語句將各種可能會出現(xiàn)的情況，分別進行了

50、討論，這樣就能保證得到的是有效站臺數(shù)n2,即符合地鐵行駛和轉(zhuǎn)乘實際。模型建立：根據(jù)上述算法可建立規(guī)劃問題,目標(biāo)函數(shù)為:,根據(jù)的敘述建立分步線性規(guī)劃模型，并通過matlab編程實現(xiàn): 約束條件: 約束條件：模型的結(jié)果 s3359s1828：從起始站 s3359 乘坐 l015 上行，途經(jīng)s3359ts2266->s3917ts2303->s1327ts3068；在 s3068 下車，從d08 轉(zhuǎn) 乘 地 鐵 t1 上 行， 途 經(jīng)d08td09td10td11td12td13td14td15d16td17td18；從 d18 下地鐵 t1,轉(zhuǎn)乘 t2,途經(jīng) d18-d33-d34-d

51、35-d36-d37-d38；從 d38下地鐵t2 ,從s3262轉(zhuǎn)乘l041上行，途經(jīng)s3262-s1772-s0259-s0258-s1781-s1790-s0458-s1792-s1783-s1671-s 1828；即到達(dá)終到站s1828o用時94分鐘，與模型i用時101分餅相比，節(jié)省時間7分鐘，但比模型ii多花去3元錢。 s1557s0481：線路1 ：從起始站s1557乘坐l363下行，途經(jīng)-s1985-s1557-s3158-s2628-s3408-s2044s2563-s2682-s2735-s0029-s0055-s0051-s1919；在 s1919 下車，從d20轉(zhuǎn)乘地鐵t

52、1下行，途經(jīng)d20->d19->018；從d18下地鐵t1,轉(zhuǎn)乘 t2,途經(jīng) d18-d33-d34-d35-d36-d37-d38-d39-d24；從 d24下地鐵 t2 ,從 s0537 轉(zhuǎn)乘 l516 上行，途經(jīng)s0537-s2651-s3013-s1808-s1173-s0910-s3517-s0453-s2424-s1174-s0902 -s0903-s2101-s0481；即到達(dá)終到站 s0481。線路2 :從起始站s1557乘坐l084下行，途經(jīng)s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s0028-s0029-s0

53、055-s0051-s1919；在 s1919 下車，從 d20 轉(zhuǎn) 乘地鐵t1下行，途經(jīng)d20->d19d18；從d18下地鐵t1,轉(zhuǎn)乘t2,途經(jīng) di8-d33-d34-d35-d36-d37-d38-d39-d24；從 d24 下地鐵t2 , 從 s0537 轉(zhuǎn)乘 l516 上行， 途經(jīng)s0537-s2651-s3013-s1808-s1173-s0910-s3517-s0453-s2424 -s1174-s0902 -s0903-s2101-s0481；即到達(dá)終到站 s0481。線路1和線路2用時均為117分鐘，與模型i用時分鐘相比，節(jié)省時間分鐘，但多花去2元錢；與模型ii s0

54、971s0485線路1： 從起始站 s0971 乘坐 l094 上行，途經(jīng)s0971-s3571-s1609-s0345-s1419-s2389 -s0567；在 s0567 下車，從d01 轉(zhuǎn)乘地鐵 t1 上行，途經(jīng) doi -d02-d03-d04-d05-d06 -d07-d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20- d21；從d21下地鐵t1,從s0464轉(zhuǎn)乘l469下行，途經(jīng) s0464-s0964-s3189-s2810-s2385-s0485；即到達(dá)終到站 s0485。線路2：從起始站 s0971 乘坐 l094 上行途

55、經(jīng)s0971-s3571-s1609-s0345-s1419-s2389-s0567；在 s0567 下車，從d01 轉(zhuǎn)乘地鐵 t1 上行，途經(jīng) d01-d02-d03-d04-d05-d06-d07-d08- d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21 ； 從d21下地鐵 t1 ,從s0466轉(zhuǎn)乘 l051上行，途經(jīng) s0466-s3189-s2810-s2385-s0071-s0485；即到達(dá)終到站 s0485。線路3：從起始站 s0971 乘坐 l094 上行，途經(jīng) s0971-s3571-s1609-s0345- s1419-

56、s2389 -s0567；在s0567下車，從d01轉(zhuǎn)乘地鐵t1上行，途 經(jīng) d01-d02-d03-d04-d05-d06-d07 d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21；從 d21 下地鐵 t1,從 s0464 轉(zhuǎn)乘 l104 上行，途經(jīng) s0464-s0964-s3189-s2810-s2385-s0485； 即到達(dá)終到站s0485o線路4：從起始站s0971乘坐l094上行，途經(jīng)s0971-s3571-s1609- s0345-s1419 -s2389-s0567；在 s0567 下車，從 d01 轉(zhuǎn)乘地鐵 t1 上 行，途經(jīng)d01-d02-d03-d04-d05-d06-d07-d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19 d20-d21；從d21下地鐵t1,從s0464轉(zhuǎn)乘l395下行，途經(jīng)s0464-s0964-s3189-s2810-s2385-s0485；即到達(dá)終到站 s0485。線路5：從起始站s0971乘坐l094上行，途經(jīng)s0971-s3571-s1609-s0345-s1419 -s2389-s0567；在