公交查詢系統(tǒng)的最佳乘車方案研究與設(shè)計(jì)

1、公交查詢系統(tǒng)的最佳乘車方案研究與設(shè)計(jì)摘要本文要求設(shè)計(jì)一個(gè)公交線路計(jì)算機(jī)自助查詢系統(tǒng)，針對(duì)不同需求的出行者推 薦相應(yīng)的最佳路線。這是一個(gè)多目標(biāo)決策的網(wǎng)絡(luò)優(yōu)化問題，并且隨著問題的深入 逐層遞進(jìn)，我們建立了三個(gè)多目標(biāo)優(yōu)化模型解決此問題。針對(duì)問題一，將三種不同的公汽線路抽象化，建立站點(diǎn)間直達(dá)線路信息存儲(chǔ) 元胞結(jié)構(gòu)。調(diào)查分析得岀，盡管乘客對(duì)公交線路的需求側(cè)重點(diǎn)各有不同，但都包 括乘車次數(shù)少、時(shí)間短、費(fèi)用少和擁擠程度低，以前三個(gè)量為目標(biāo)，擁擠程度為 約束，建立多目標(biāo)整數(shù)規(guī)劃模型，根據(jù)多目標(biāo)分層序列法，出于對(duì)乘客不同需求 的考慮，采用3種對(duì)每個(gè)需求側(cè)重程度不同的策略，利用局部搜索算法，求岀6 條線路在3種不

2、同策略下的最優(yōu)線路(最佳線路見表(1)至(3)o針對(duì)問題二，同時(shí)考慮公汽與地鐵線路，將地鐵站點(diǎn)與鄰接的公汽站點(diǎn)抽象 為同一新站點(diǎn)，重新建立站點(diǎn)間直達(dá)線路信息存儲(chǔ)元胞結(jié)構(gòu)。在問題一的基礎(chǔ)上 增加考慮地鐵站對(duì)費(fèi)用、換乘時(shí)間和行駛時(shí)間的影響，仍然以乘客對(duì)線路的三種 主要需求為目標(biāo)，以擁擠程度為約束，建立多目標(biāo)整數(shù)規(guī)劃模型，利用matlab 軟件編程求解得到3種不同策略下的最優(yōu)路線(最佳線路見表(4)至(6)o針對(duì)問題三，增加考慮步行的出行方式，在公汽站點(diǎn)間當(dāng)站點(diǎn)數(shù)目不超過2 時(shí)，可以以步行代替，從而減少換乘次數(shù)。在此基礎(chǔ)上，按換乘次數(shù)少、時(shí)間短、 費(fèi)用少的順尋建立多目標(biāo)整數(shù)規(guī)劃模型，利用matlab

3、軟件編程求解得到相應(yīng)的 最佳路線。以線路s1557->s0481和s0148->s0485為例，最佳路線分別為： s1557-步行 2 站f s2143-l084-s1919-l043-s3077-l273,需 3 元,92 分鐘; s0148->步行 1 站s3182-l308-s36-l157-s0722-步行 1 站->s0485,需 2 元，69分鐘。關(guān)鍵字 元胞結(jié)構(gòu)多目標(biāo)整數(shù)規(guī)劃 多目標(biāo)分層序列法 局部搜索算法1 問題重述1.1問題背景傳承華夏五千年的文明，夢(mèng)圓十三億華夏兒女的暢想，我國(guó)人民翹首企盼的 第29屆奧運(yùn)會(huì)明年8月將在北京舉行!在觀看奧運(yùn)的眾多方式之

4、中，現(xiàn)場(chǎng)觀看無 疑是最激動(dòng)人心的。屆吋有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘 坐公共交通工具(簡(jiǎn)稱公交，包括公汽、地鐵等)出行。為了迎接2008年奧運(yùn) 會(huì)，北京公交做了充分的準(zhǔn)備，首都的公交車大都煥然一新，增強(qiáng)了交通的安全 性和舒適性，公交線路己達(dá)800條以上，使得公眾的出行更加通暢、便利。但同 時(shí)也面臨多條線路的選擇問題。為滿足公眾查詢公交線路的選擇問題，某公司準(zhǔn) 備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。12待解決的問題這個(gè)系統(tǒng)的核心是線路選擇的模型與算法，另外還應(yīng)該從實(shí)際情況出發(fā)考 慮，滿足查詢者的各種不同需求。需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽

5、站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與 算法。并根據(jù)附錄數(shù)據(jù)，利用模型與算法，求出以下6對(duì)起始站到終到站最佳路 線(要有清晰的評(píng)價(jià)說明)。(1)、s3359-s1828(2)、s1557->s0481(3)、s0971-s0485(4)、s0008-s0073(5)、s0148->s0485(6)、s0087->s36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問 題的數(shù)學(xué)模型。2 問題假設(shè)假設(shè)一：各路線公交車發(fā)車頻度相同；假設(shè)二：相鄰站點(diǎn)間平均行駛吋間一定；假設(shè)三：公交運(yùn)行順暢：無交通阻塞、無車輛故障、無道

6、路交通事故等意外情況;假設(shè)四：公交準(zhǔn)點(diǎn)到達(dá)，不考慮紅綠燈等待時(shí)間；假設(shè)五：乘客在起始站時(shí)不考慮擁擠程度，只在轉(zhuǎn)乘時(shí)考慮擁擠程度；假設(shè)六：乘客到起始站乘車時(shí)，不考慮等車時(shí)間；假設(shè)七：同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘，在此換乘 過程中不考慮換乘時(shí)間和費(fèi)用。3. 符號(hào)說明4站點(diǎn)z間的最小換乘次數(shù)嶺實(shí)際換車次數(shù)從站點(diǎn)j到站點(diǎn)丿的費(fèi)用坊表示站點(diǎn)2到站點(diǎn)經(jīng)過的站點(diǎn)數(shù)目叫j表示從起始站startp到終點(diǎn)站endp的站點(diǎn)數(shù)au表示從站點(diǎn)z上車時(shí)站點(diǎn)i距離startp的站點(diǎn)數(shù)表示從起始站i到終點(diǎn)站j公汽換乘公汽的次數(shù)4表示從起始站2到終點(diǎn)站丿公汽換乘地鐵的次數(shù)z：表示從起始站i到終點(diǎn)站j地鐵

7、換乘公汽的次數(shù)表示從起始站7到終點(diǎn)站丿地鐵換乘地鐵的次數(shù)站點(diǎn)i到站點(diǎn)丿的步行時(shí)間t鄰近站點(diǎn)的時(shí)間上確界任意兩個(gè)鄰近站點(diǎn)平均步行時(shí)間t表示鄰接公汽站點(diǎn)間的步行時(shí)間4. 問題分析這是一個(gè)多目標(biāo)決策的網(wǎng)絡(luò)優(yōu)化問題。公交查詢系統(tǒng)需要滿足查詢者各種不 同需求，給出最優(yōu)方案，這是我們建立模型的根木出發(fā)點(diǎn)，有關(guān)問題的求解隨著 規(guī)模擴(kuò)大將逐層深入。對(duì)于問題一，題目給出的公汽線路主要分為上下行線、原路折回線及環(huán)行 線，線路不同，選擇不同，故對(duì)每種線路需要進(jìn)行抽象化處理。站點(diǎn)較多，信息 量較多，需要選擇合適的存儲(chǔ)方法存儲(chǔ)數(shù)據(jù)，存儲(chǔ)題中的線路名、車號(hào)和時(shí)間。 解決這些問題后，就要對(duì)乘客的出行需求進(jìn)行調(diào)查，看看乘客出

8、行時(shí)主要考慮哪 些因素，根據(jù)調(diào)查結(jié)果可以選定主要的需求建立多目標(biāo)規(guī)劃模型。本題數(shù)據(jù)量較 多，一般的算法可能不能處理，所以要探索合適的算法，然后用matlab軟件編 程求解，可以求岀不同需求的岀行者相應(yīng)的公交路線。對(duì)于問題二，在問題一的基礎(chǔ)上更進(jìn)一步探討同時(shí)考慮公汽和地鐵線路的 情況。我們同樣需要對(duì)地鐵線路進(jìn)行抽象化處理，基于假設(shè)七，同一地鐵站與鄰 接的公汽站可以進(jìn)行歸一化處理，因?yàn)檫@些站點(diǎn)間的換成無需支付地鐵費(fèi)并且時(shí) 間可以忽略不計(jì)，還要將地鐵站相關(guān)信息和公交站相關(guān)信息合理存儲(chǔ)。根據(jù)問題 一屮的乘客需求，同樣建立多冃標(biāo)規(guī)劃模型，但由于有了地鐵這種出行方式，在 乘車費(fèi)用與車輛換乘方面有所不同。設(shè)

9、計(jì)合適的算法，編程求解得到不同需求的 乘客相應(yīng)的最優(yōu)路線。對(duì)于問題三，該問在問題二的基礎(chǔ)上增加考慮步行對(duì)最優(yōu)路線選取帶來的 影響，可以把步行作為另一種交通工具進(jìn)行考慮。根據(jù)實(shí)際情況對(duì)步行相關(guān)信息 做出合理的假設(shè)，由于步行這種出行方式不花費(fèi)時(shí)間，對(duì)換乘次數(shù)以及換乘方式 都沒有影響，只改變出行時(shí)間。所以在問題三中，我們對(duì)出行時(shí)間優(yōu)先考慮，再 考慮換乘次數(shù)和乘車費(fèi)用，同樣建立多目標(biāo)優(yōu)化模型，運(yùn)用matlab編程求解得 到任意站點(diǎn)間的最佳路線。5 問題一的解答問題一僅考慮公汽線路，我們建立了模型一進(jìn)行求解。5.1問題一的數(shù)據(jù)處理 5.1. 1三種公汽線路的處理根據(jù)題屮信息，我們知道公汽線路分三種，下面

10、將這三種線路進(jìn)行數(shù)據(jù)處理: 下行線是上行線原路返回這種線路有兩個(gè)端點(diǎn)站，在兩個(gè)端點(diǎn)之間雙向行車，而且兩個(gè)方向上的行車 路線相同，經(jīng)過同樣的站點(diǎn)序列，只是線路的方向不同；上行線與下行線的站點(diǎn)名不完全相同這種線路與下行線是上行線的原路返回不同，下行線與上行線經(jīng)過的站點(diǎn)不 完全相同，但是起始站和終點(diǎn)站相同； 線路為環(huán)形線對(duì)環(huán)形線路的站點(diǎn)進(jìn)行分析，把一個(gè)環(huán)形拉成一條直線，以該直線的終 點(diǎn)為對(duì)稱點(diǎn)進(jìn)行翻折，將終點(diǎn)左邊的直線對(duì)稱到右邊，形成該直線的延長(zhǎng) 線，如下：這種環(huán)形線原有的路線包括：12, 13, 14, 23, 24, 34, 21, 31, 41, 32, 42, 43,抽象成直線后的路線有：1

11、2, 13, 14, 23, 24, 34, 43, 42, 41, 32, 31, 21,與 原路線相同，所以這種抽象方法是合理的。5.1.2建立“公汽直達(dá)數(shù)據(jù)庫dm ”從實(shí)際出發(fā)，結(jié)合公眾出行心理，公汽線路選擇應(yīng)優(yōu)先考慮兩站點(diǎn)z間是否 有直達(dá)車，那么在查詢系統(tǒng)內(nèi)部應(yīng)設(shè)有任兩站點(diǎn)的直達(dá)線路表，以方便查詢時(shí)優(yōu) 先快速查詢是否有直達(dá)車，若有，則直接輸出所有直達(dá)車輛；若無，再搜索換乘 路線。在數(shù)據(jù)導(dǎo)入的過程中，首先考慮直接從文本文件導(dǎo)入matlab中，但是本題共 有3957個(gè)站點(diǎn)，520條公交線路，若每個(gè)隊(duì)列的每個(gè)數(shù)據(jù)都是用雙精度進(jìn)行存 儲(chǔ)，那么內(nèi)存占用大，實(shí)際輸岀時(shí)運(yùn)行時(shí)間長(zhǎng)，考慮到所存儲(chǔ)的信息

12、量包括公汽 號(hào)、公交站點(diǎn)、乘車時(shí)間以及乘車費(fèi)用等多個(gè)因素，所以采用matlab中的元胞數(shù) 組建立公汽直達(dá)數(shù)據(jù)庫dm進(jìn)行存儲(chǔ)（建立數(shù)據(jù)庫dm的代碼詳見附錄一）,節(jié) 省存儲(chǔ)空間。5. 2模型一的準(zhǔn)備5. 2. 1公交乘客的出行需求公交線網(wǎng)優(yōu)化的最終目的是盡最大可能滿足乘客的出行需求。建立合理的線 網(wǎng)優(yōu)化模型，重要的一點(diǎn)是通過對(duì)居民出行心理、行為進(jìn)行調(diào)查研究，以確定模 型的優(yōu)化目標(biāo)和約束條件。居民公交出行需求，是居民對(duì)公交服務(wù)的期望。由于我們?cè)O(shè)計(jì)出來的系統(tǒng)需要滿足查詢者不同的需求，要建立合適的出行路 線選擇模型，必須對(duì)公交乘客選擇出行路徑時(shí)需要考慮的因素進(jìn)行調(diào)查分析。我 們對(duì)隨州市居民的出行需求進(jìn)行

13、調(diào)查結(jié)果，用excel畫出居民對(duì)出行時(shí)的費(fèi)用、 乘車時(shí)間、乘換次數(shù)、步行時(shí)間以及擁擠程度的統(tǒng)計(jì)結(jié)果如下圖（1）:系列1圖（1）:居民出行需求結(jié)果的統(tǒng)計(jì)我們可以看到，出行者對(duì)不同因素的看重比例是不同的，該市居民出行需求 對(duì)于北京這樣的大城市也同樣適用。由于一般情況下路程長(zhǎng)短和所用時(shí)間是密切 聯(lián)系的，乘客關(guān)注路程也是為了節(jié)約時(shí)間，所以問題中已經(jīng)將路程的相關(guān)信息轉(zhuǎn) 化成為吋間了，即只需考慮時(shí)間最短。因此我們的模型中對(duì)公交網(wǎng)絡(luò)的優(yōu)化需要 考慮四個(gè)主要優(yōu)化目標(biāo)：換乘次數(shù)最少，時(shí)間最短，費(fèi)用最少，擁擠程度最低。5. 2. 2換乘次數(shù)的抽象根據(jù)公交線路的設(shè)計(jì)，盡管起始站和終點(diǎn)站位置相同，也可能有多種乘車方

14、式，這些乘車方式中可能是育達(dá)的，也可能要轉(zhuǎn)乘一次，也可能需轉(zhuǎn)乘兩次，或 三次及三次以上，以startp表示起始站,endp表示終點(diǎn)站，那么某乘客從startp到勁dp的兒種乘車方式如下:直達(dá)的示意圖startp換乘一次的示意圖如果公交線路設(shè)計(jì)合理的話，那么幾乎所有的站點(diǎn)均可以在轉(zhuǎn)成兩次以內(nèi)達(dá) fi的地，而且乘換次數(shù)過多，容易使乘客產(chǎn)生煩躁情緒，需要更長(zhǎng)的時(shí)間和更多 的費(fèi)用；因此在設(shè)計(jì)算法時(shí)，只搜索直達(dá)、換乘一次和換乘2次的乘車方案。5. 2. 3計(jì)算機(jī)系統(tǒng)自主查詢路線的流程通過上述調(diào)查顯示的統(tǒng)計(jì)結(jié)果得知，乘客乘車都會(huì)考慮換乘次數(shù)，時(shí)間，費(fèi) 用以及擁擠程度的問題，但是不同的乘客對(duì)這些需求考慮的先

15、后次序不同，比如: 度假的乘客，一般會(huì)首先考慮乘車時(shí)間；所帶行李較多的乘客，一般會(huì)首先考慮 擁擠程度和換乘次數(shù)等。一般情況下，人們往往會(huì)選擇直達(dá)，也就說如果兩站點(diǎn)之間有直達(dá)車 輛，乘客會(huì)選擇肓達(dá)。由于肓達(dá)的車輛不止一輛，可以根據(jù)不同乘客的需 求，選擇相應(yīng)的最優(yōu)方案。當(dāng)沒有直達(dá)車輛吋，乘客可以根據(jù)自己不同的 需求，選擇屬于自己的最優(yōu)路線。根據(jù)上述分析，我們構(gòu)建的公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)應(yīng)該考 慮不同乘客對(duì)不同需求的重視程度，根據(jù)上述分析，公交線路自主查詢系統(tǒng)的流 程如下圖(2)：換乘次數(shù)最短 時(shí)間最短 花費(fèi)最少圖(2):公交線路自主查詢系統(tǒng)的流程圖53模型一的建立我們要建立如圖(2)

16、所示的公交線路自主查詢系統(tǒng)，就要對(duì)不同行程需求的 乘客推薦相應(yīng)的最佳路線，根據(jù)實(shí)際情況可以確定三個(gè)目標(biāo)，分別為：換乘次數(shù), 乘車時(shí)間，乘車費(fèi)用。結(jié)合數(shù)據(jù)處理中的實(shí)際情況，不同的乘客對(duì)不同需求的重視程度不同，所以 對(duì)于不同的乘客，我們要給出相應(yīng)的最佳路線，從三個(gè)方面綜合考慮，分別給出 優(yōu)先考慮乘換次數(shù)以及優(yōu)先考慮乘車時(shí)間的最優(yōu)推薦路線。我們考慮運(yùn)用多冃標(biāo) 優(yōu)化設(shè)計(jì)的分層序列法建立模型，進(jìn)行求解，在此引入多目標(biāo)分層序列法。多目標(biāo)分層序列法：將鳥個(gè)目標(biāo)函數(shù)按重要程度排序g也,其中広的 優(yōu)先級(jí)最高，應(yīng)該首先得到滿足，其次是心，直到得出滿足所有的目標(biāo)函數(shù)的解, 或是此吋的解只有一個(gè)。根據(jù)實(shí)際情況，可以根

17、據(jù)多目標(biāo)優(yōu)化設(shè)計(jì)的分層序列法對(duì)我們建立的三個(gè)目 標(biāo)函數(shù)的順序進(jìn)行調(diào)整，得到不同乘客所對(duì)應(yīng)的不同的最佳路線。當(dāng)滿足這些冃 標(biāo)的路線不止一條時(shí)，我們選取離始發(fā)站最近的解，因?yàn)殡x始發(fā)站越近，公交的 擁擠程度相對(duì)越小。當(dāng)以某個(gè)目標(biāo)函數(shù)作為第燈個(gè)目標(biāo)函數(shù)，即決策變量時(shí)，只需將該目標(biāo)函數(shù) 的順序進(jìn)行調(diào)整，使之成為第人個(gè)目標(biāo)函數(shù)。當(dāng)目標(biāo)函數(shù)有三個(gè)時(shí)，排序后共有 六種可能的情形，但不是每種情形都要考慮。根據(jù)調(diào)查結(jié)果，我們確定了乘客出 行時(shí)考慮較多的三種類型，在此分別稱為策略一、策略二和策略三。策略一：按換乘次數(shù)最少、策略二按乘車時(shí)間最短、策略三：按換乘次數(shù)最小、乘車時(shí)間最短、 換乘次數(shù)最少、 乘車費(fèi)用最少、乘

18、車費(fèi)用最少的順序考慮; 乘車費(fèi)用最小的順序考慮; 乘車吋間最短的順序考慮。5. 3.1確定目標(biāo)函數(shù)在建立的公汽直達(dá)數(shù)據(jù)庫dm的基礎(chǔ)上，分別確定三個(gè)冃標(biāo)函數(shù)。target one :乘換次數(shù)最少設(shè)厶“表示站點(diǎn)之間的換乘次數(shù)，根據(jù)公交線路的設(shè)計(jì)，盡管起始站和終點(diǎn) 站位置相同，也可能有多種乘車方式，這些乘車方式中可能是直達(dá)的，也可能要 換乘一次，也可能需換乘兩次。將換乘次數(shù)作為第/個(gè)目標(biāo)，希望在滿足該要求 的基礎(chǔ)上再考慮其它方案，即在建立的公汽直達(dá)數(shù)據(jù)庫dm中進(jìn)行搜索，如果有直 達(dá)方案，僅在直達(dá)方案屮推薦滿足其它fi標(biāo)函數(shù)的最佳路線。那么冃標(biāo)一要求厶“ 最小，即min lj otarget two

19、:乘車時(shí)間最少通過分析我們知道，乘車中的時(shí)間包扌4行駛時(shí)間和換乘時(shí)間?；诩僭O(shè)六, 乘客到起始站乘車時(shí)，不考慮等車時(shí)間。而車輛換乘的過程實(shí)際上包括換乘時(shí)間 和等車時(shí)間。公汽換公汽時(shí)間固定是5分鐘，則換乘吋間(包括換乘過程中的等 車時(shí)間)為：5a.設(shè)實(shí)際換車次數(shù)為嶺，那么實(shí)際乘車的數(shù)量為嶺+ 1,所以行駛總時(shí)間為： 工譏嶺+ 1)，其中九 “廬2ijee那么乘車時(shí)間為：工© (嶺+1) + 5九ijee即第二個(gè)目標(biāo)函數(shù)為： min為譏嶺+1) + 5九ijeetarget three :乘車費(fèi)用最少乘車費(fèi)用分為單一票價(jià)與分段計(jì)價(jià)兩種方式，用傷表示從站點(diǎn)，到站點(diǎn) 丿的計(jì)費(fèi)方式，那么如=；

20、，其中1表示單一票價(jià)，2表示分段計(jì)費(fèi)；又由于分 段計(jì)價(jià)的票價(jià)為：020站：1元；2140站：2元40站以上：3元，可設(shè)吊 表示站點(diǎn)i到站點(diǎn)/經(jīng)過的站點(diǎn)數(shù)目，那么從站點(diǎn)i到站點(diǎn)/的費(fèi)用坊為：1， 仏=1)_ 1,(,=2,l<s,<20)坊 _2,仏=2,20 vs產(chǎn) 40)3,(<7,7 =2,5. >40)那么行程總費(fèi)用為：工坊(嶺+1)ijee從而得到第三個(gè)目標(biāo)函數(shù)為：跡工坊何+1)ijee綜上我們建立的多口標(biāo)整數(shù)規(guī)劃口標(biāo)函數(shù)為：min 址min工譏嶺+ l) + 5ijeemin工肌嶺+ 1)ijee5. 3. 2確定約束條件模型屮我們僅考慮換乘2次的路線，所以實(shí)

21、際換車次數(shù)嶺應(yīng)該大于換車次 數(shù)的最小值，但是小于2,即q 5vjj 52；當(dāng)確定的最佳路線的換乘次數(shù)、乘車 時(shí)間和乘車費(fèi)用相同時(shí)，考慮以擁擠程度的高低來確定最終的最佳路線。擁擠程度：實(shí)際生活中，當(dāng)離起始站點(diǎn)越近時(shí)，車上的乘客越少。設(shè)©表 示從起始站startp到終點(diǎn)站endp的站點(diǎn)數(shù)0 , aif表示從站點(diǎn)2上車時(shí)站點(diǎn)i距離 s九切的站點(diǎn)數(shù)，那么知的最小值越接近州表示擁擠程度越高，知的最小值越 接近0表示擁擠程度越低。所以owm加6/. < /?,. o 所以模型一的約束條件為：0 < min ai <5十2ijee5. 3. 3確定模型一綜上所述，可以確定多目標(biāo)整

22、數(shù)規(guī)劃模型為：min limin工譏嶺+1) + 5九hjeemin工坨(嶺+ 1)ijee0 < min au < nijjst九5嶺s2、i,jw e5. 4模型一的求解5. 4. 1算法設(shè)計(jì)基于局部搜索和優(yōu)化枚舉的算法，我們充分利用公交網(wǎng)絡(luò)自身的特點(diǎn)，采用 局部搜索思想，對(duì)三種不同的策略進(jìn)行分類，在每種策略屮求出最優(yōu)解。首先根 據(jù)乘客輸入的起始點(diǎn)和終點(diǎn)，分別對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行搜索，篩選出可行的線路； 然后根據(jù)三種不同的策略在選出的可行路線中，選出每種策略的最優(yōu)方案。具體 算法實(shí)現(xiàn)過程如下：1) 輸入起始點(diǎn)i,終點(diǎn)丿以及選擇的策略種類4 "1,2,3；2）搜索從站點(diǎn)7可

23、乘坐公交線路的集合/?（：）,在終點(diǎn)可乘坐公交線路的集合r（j）；3）判斷是否直達(dá)； /?或/?（刀是空集，說明兩站之間沒有線路可以到達(dá) r（i）cr（j） = o,說明兩站之間不能直達(dá)，轉(zhuǎn)入4） rcr（j"o,說明兩站之間可以直達(dá)，轉(zhuǎn)入8）4）以起始點(diǎn)搜索直達(dá)下有站點(diǎn)的集合m ,以終點(diǎn)搜索直達(dá)上游站點(diǎn)集合5）判斷是否是一次換車 mcnho,存在一次換車就可到達(dá)，轉(zhuǎn)入8） m cn = 0,不存在一次換車就可到達(dá)，轉(zhuǎn)入6）（注：mcn*0中，可能包含直達(dá)路線，要篩選剔出）6）掃描是否vmen ,若存在（m,z?）,則可以直達(dá)，若不存在，則將點(diǎn)力加入集合f ,集合f表示需要換車兩次；

24、7）判斷是否需要兩次換車集合f不是空集，轉(zhuǎn)入8）集合f是空集，不考慮8）基于三種不同的策略，推薦最優(yōu)乘車線路5. 4. 2求解結(jié)果根據(jù)上面的算法思想，可以運(yùn)用ma1tab軟件進(jìn)行編程（代碼詳見附錄 二），由于我們釆用的是多目標(biāo)分層序列整數(shù)規(guī)劃模型，所以根據(jù)確定的三種 不同的策略，可以得到相應(yīng)策略的最佳路線，表（1）至表（3）分別給出了三種不同 策略下題中要求解的六條線路的最佳路線。表（1）：策略一中六條線路的最佳路線線路換乘次數(shù)時(shí)間花費(fèi)坐車路線距離始發(fā)站s3359-s182811013l436-s1784-l21717s1557-s04812763l084-s1919-l043-s3077-l

25、2732& 20s0971-s048511283l013-s2184-l41714s0008-s00731832l355-s2263-l34511s0148-s04852733l024-s1234-l505-s516- l10416, 23s0087-s36761652l454-s3496-l2096（注：策略一按換乘次數(shù)、乘午時(shí)間、乘午費(fèi)用的順序進(jìn)行考慮）表（2）：策略二中六條線路的最佳路線線路時(shí)間換乘次數(shù)花費(fèi)坐車路線距離始發(fā)站s3359-s18287323l324-s2027-l201-s458 -l0417, 10s1557-s04817623l084-s1919-l043-s3

26、077-l27328, 20s0971-s04856423l013-s345-l505-s516-l10417, 23s0008-s00733723l150-s1381-l290-s3645-l02031, 17s0148-s04857323l024-s1234-l505-s516- l10416,23s0087-s36764623l021-s88-l231-s427- l09714, 3（注：策略二按乘車時(shí)間.換乘次數(shù)、乘車費(fèi)用的順序進(jìn)行考慮）表（3）：策略三中六條線路的最佳路線線路換車次數(shù)花費(fèi)時(shí)間坐車路線距離始發(fā)站s3359-s182813101l436-s1784-l21717s1557

27、-s04812376l084-s1919-l043-s3077-l27328,20s0971-s048513128l013-s2184-l41714s0008-s00731283l355-s2263-l34511s0148-s04852373l024-s1234-l505-s516- l10416, 23s0087-s36761265l454-s3496-l2096（注：策略三按換乘次數(shù)、乘車時(shí)間、乘車費(fèi)用的順序進(jìn)行考慮）5. 5模型一的結(jié)果分析比較表仃）至表（3）的結(jié)果，可以看到策略一和策略三的結(jié)果完全一樣，這主 要是因?yàn)槌俗坏馁M(fèi)用變化不顯著，每經(jīng)過20個(gè)站點(diǎn)才增加一元錢，這樣一來 在某

28、個(gè)范圍內(nèi)，乘坐公交的費(fèi)用相差不會(huì)很遠(yuǎn)，所以對(duì)路線的選取不會(huì)有太大影 響。我們縱向比較三種策略的時(shí)間，將三種策略下的時(shí)間變化作圖如下：13012011010090807060504030策略一六條線路時(shí)間的變化f/策略三六條線路時(shí)間的變化/一/. /x/- /策略二六條線路時(shí)間的變化1 1三條11.522.533.544.555.56六條線路圖（3）：三種策略的時(shí)間比較由圖可以看出，優(yōu)先考慮時(shí)間和優(yōu)先考慮換乘次數(shù)時(shí)，推薦的最優(yōu)路線在乘 車時(shí)間上的波動(dòng)很大，說明我們的策略分配是合理的。對(duì)于比較重視時(shí)間的乘客, 優(yōu)先考慮時(shí)間，就會(huì)節(jié)約很多時(shí)間；對(duì)于不趕時(shí)間，覺得換乘麻煩而重視換乘次 數(shù)的乘客，相對(duì)來

29、說所需時(shí)間要多。以第三條線路s0971-s0485為例，優(yōu)先考 慮乘車時(shí)間時(shí)，需要37分鐘，而優(yōu)先考慮乘換次數(shù)時(shí)，需要128分鐘，即優(yōu) 先考慮時(shí)間比優(yōu)先考慮乘換次數(shù)在這條線路上可以節(jié)約91分鐘。所以針對(duì) 不同的乘車需求，我們確定了不同的乘車策略是非常有必要的。6.問題二的解答問題二同吋考慮公汽與地鐵線路，我們建立了模型二進(jìn)行求解。6.1問題二的數(shù)據(jù)處理6.1. 1對(duì)兩條地鐵線路的處理基于對(duì)三種公汽線路路線的抽彖方法，用相同的方法對(duì)兩地鐵線路7；,7；進(jìn) 行抽象化處理。7；：返回時(shí)沿原路返回，這種線路有兩個(gè)端點(diǎn)站，在兩個(gè)端點(diǎn)之間雙向行車，而 r兩個(gè)方向上的行車路線相同，經(jīng)過同樣的站點(diǎn)序列，只是線

30、路的方向不同； t2 :環(huán)行線路，根據(jù)對(duì)公汽線路中環(huán)形線路的抽象方法把地鐵線路中的環(huán)形線路 拉成1條直線。6. 1. 2歸一化處理由地鐵換乘公汽信息數(shù)據(jù)文件可知，同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間 可以通過地鐵站換乘(無需支付地鐵費(fèi))，從而可以認(rèn)為在實(shí)際情況中，同一地鐵 站點(diǎn)與對(duì)應(yīng)的公汽站點(diǎn)之間距離很近，為了簡(jiǎn)化該問題，可以將這些站點(diǎn)作為一 個(gè)站點(diǎn)進(jìn)行考慮。我們將其抽象化處理如下圖(4)：基于這種思想，在整個(gè)交通網(wǎng)絡(luò)中將同一地鐵站點(diǎn)及其緊鄰站點(diǎn)分別做歸一 站點(diǎn)處理，可以認(rèn)為在新站點(diǎn)所代表的站點(diǎn)集中的任意站點(diǎn)間的距離可以忽略不 計(jì)，從而時(shí)間也可忽略不計(jì)。6.1.3建立“公汽、地鐵直達(dá)數(shù)據(jù)庫dm&

31、#39;"原公交站點(diǎn)有3957個(gè)，考慮地鐵站點(diǎn)后，站點(diǎn)總數(shù)增加至3996個(gè)，如果按 照建立數(shù)據(jù)庫dm的方法存儲(chǔ)數(shù)據(jù)，那么數(shù)據(jù)更新的過程所需時(shí)間很長(zhǎng)，不太實(shí) 際。所以采用將歸一化處理后的站點(diǎn)以txt （詳見附錄三）的形式存儲(chǔ)，把39個(gè) 地鐵站加入到原來的dm數(shù)據(jù)庫中，把歸一化處理的新站點(diǎn)以函數(shù)的形式導(dǎo)入到 數(shù)據(jù)庫，形成一個(gè)新的數(shù)據(jù)庫dm地鐵費(fèi)用和地鐵換乘公汽的等待時(shí)間均被 填充到元胞內(nèi)，將新數(shù)據(jù)庫中的站點(diǎn)稱為新站點(diǎn)。那么建立dm'的實(shí)質(zhì)是新站 點(diǎn)與新站點(diǎn)間的直達(dá)線路信息集。用戶輸入起點(diǎn)和終點(diǎn)后，系統(tǒng)內(nèi)部先自動(dòng)查找 兩點(diǎn)所屈的新站點(diǎn)，然后查找新站點(diǎn)間可直達(dá)的線路，并給出起點(diǎn)及其附

32、近站點(diǎn) 直達(dá)終點(diǎn)及其附近站點(diǎn)的最佳乘車線路。6. 2模型二的建立按換乘次數(shù)最少、 按乘車時(shí)間最短、 按換乘次數(shù)最小、乘車時(shí)間最短、乘車費(fèi)用最少的順序考慮; 換乘次數(shù)最少、乘車費(fèi)用最小的順序考慮; 乘車費(fèi)用最少、乘車吋間最短的順序考慮。問題二同時(shí)考慮公汽與地鐵線路，乘客的需求分析與問題一中相同，要建立 公汽、地鐵線路計(jì)算機(jī)自主查詢系統(tǒng)，對(duì)不同行程需求的乘客推薦相應(yīng)的最佳路 線，仍然采用多目標(biāo)分層序列法，確定三個(gè)目標(biāo)，分別為：換乘次數(shù)，乘車吋間, 乘車費(fèi)用。根據(jù)調(diào)查結(jié)果，我們考慮乘客出行時(shí)考慮較多的三種類型，在此分別 稱為策略一、策略二和策略三。策略一策略二策略三6. 2.1確定目標(biāo)函數(shù)在建立的公

33、汽、地鐵直達(dá)數(shù)據(jù)庫dat的基礎(chǔ)上，分別確定三個(gè)目標(biāo)函數(shù)。 target one :乘換次數(shù)最少設(shè)坊表示站點(diǎn)之間的換乘次數(shù)，根據(jù)公交線路的設(shè)計(jì)，盡管起始站和終點(diǎn) 站位置相同，也可能有多種乘車方式，這些乘車方式屮可能是直達(dá)的，也可能要 換乘一次，也可能需換乘兩次。在建立的公汽、地鐵直達(dá)數(shù)據(jù)庫dvt屮進(jìn)行搜 索，如果有直達(dá)方案，僅在直達(dá)方案中推薦滿足其它fi標(biāo)函數(shù)的最佳路線。那么 要求覽最小，即m加l；jo target two :乘車時(shí)間最少基于假設(shè)六，到起始站等車的時(shí)間忽略不計(jì)，那么乘車時(shí)間包括行駛時(shí)間和 換車吋間。設(shè)石是各站最快直達(dá)時(shí)間，匕;是實(shí)際轉(zhuǎn)車次數(shù)，則行駛時(shí)間為化;+ 1）在起始站點(diǎn)i

34、到終點(diǎn)站丿的過程中，設(shè)zf表示在此過程中從公汽站換乘公汽 站的次數(shù)，此時(shí)zje 1,39571，z#表示從公汽站換乘地鐵站的次數(shù)，z學(xué)表示從 地鐵站換乘公汽次數(shù)，z器表示從地鐵站換乘地鐵的次數(shù)，此時(shí)7jw |3958,3996| o 那么換乘時(shí)間為：5z：+6z： + 7z/+4z洛所以總的乘車吋間為：$化;+ 1） + 5z；+6z； + 7z扌+4zj即第二個(gè)目標(biāo)函 數(shù)為：min 0（v； + l）+5zf+6zf+7z+4zftarget three :乘車費(fèi)用最少問題一屮乘車費(fèi)用分為兩個(gè)部分，在問題二屮增加了地鐵費(fèi)用，用爲(wèi)表示從站點(diǎn)i到站點(diǎn)./的計(jì)費(fèi)方式，那么爲(wèi)有三種取值，即4= 2其

35、中1表示單一3票價(jià)，2表示分段計(jì)費(fèi)，3表示地鐵票價(jià)；可設(shè)表示站點(diǎn)，到站點(diǎn)丿經(jīng)過的站 點(diǎn)數(shù)目，那么從站點(diǎn)i到站點(diǎn)丿的費(fèi)用磅為：t7；.=2,l<s.<20=2,20<s. <40qij = 2, s- > 404 = 3（4 < v； < 2）其中表示實(shí)際換乘次數(shù)。min工咖+ 1）11233 那么行程總費(fèi)用為：工打（ + 1）i、jwe從而得到第三個(gè)目標(biāo)函數(shù)為： 綜上我們建立的多口標(biāo)整數(shù)規(guī)劃口標(biāo)函數(shù)為：/；（ + l） + 5z；+6z；+7z：+4zf 工耽+ 1）ijeeminminmin6. 2. 2確定約束條件k = （a,b,c,d）,當(dāng)=

36、aye 1,3957時(shí)，1表示在公汽站點(diǎn)丿換乘公汽，0表示在公汽站點(diǎn)丿不換乘公汽；當(dāng)/c = b,；g 1,3957時(shí)，1表示在公汽站點(diǎn)/換乘地鐵，0表示在公汽站點(diǎn)j不換乘地鐵；當(dāng)k = cj"3958,3996時(shí), 1表示在地鐵站j換乘公汽，0表示在地鐵站丿不換乘公汽；當(dāng)k = d時(shí)，1表示 在地鐵站丿換乘地鐵，0表示在地鐵站丿不換乘地鐵，而地鐵換乘地鐵只有當(dāng)兩 條地鐵線路經(jīng)過的站點(diǎn)相同吋，才可以換乘，由題中給出的地鐵門線換乘公汽 信息與地鐵卩2線換乘公汽信息可知：地鐵線門，丁2只同時(shí)經(jīng)過d12和d18。此 時(shí)丿分別等于3969, 3975o討論乘客是否換乘的約束條件，乘客在公汽站

37、吋有三種不同的選擇，分別為 不換乘公汽、換乘公汽和轉(zhuǎn)乘地鐵，三種選擇不能同時(shí)進(jìn)行，那么相應(yīng)的約束條 件為：aj + b. < 1 丿 “1,3957乘客在地鐵站d12和d18也相應(yīng)的有三種不同的選擇：不換乘地鐵、換乘公汽和換乘地鐵，三種選擇不能同時(shí)進(jìn)行，所以相應(yīng)的約束條件為：cj + q/517 g 3969,3975實(shí)際生活中，當(dāng)離起始站點(diǎn)越近時(shí)，車上的乘客越少。甸的最小值越接近© 表示擁擠程度越高，©的最小值越接近0表示擁擠程度越低，貝a宀j 另外也要考慮實(shí)際乘車次數(shù)的限制，在模型中我們僅考慮兩次換乘以內(nèi)的情形，所以綜上約束條件為:a, + b. < 1 j

38、e 1,3957c. + d < 13969,3975jj0 < min a.- < %fje 1,3957zje395& 39966. 2. 3確定模型二綜上我們確定多fl標(biāo)整數(shù)規(guī)劃模型為：min 覽min 石( + l) + 5z；+6z#+7z+4z#min工仔必+ 1)ijee舛 + bjvlj g 1,3957ci + dj < 1 j g 39693975 0 < min q < n s.t <坊5匕;52z, j g 1,39577, ye 395&39966. 3模型二的求解模型二中的算法跟模型一中的算法一樣，根據(jù)局部搜

39、索算法思想，可 以運(yùn)用ma1tab軟件進(jìn)行編程(代碼詳見附錄四)，由于我們采用的是多目標(biāo) 分層序列整數(shù)規(guī)劃模型，所以根據(jù)確定的三種不同的策略，可以得到相應(yīng)策略的 最佳路線，表(4)至表(6)分別給出了三種不同策略下題中要求解的六條線路的最 佳路線。表(4)：策略一中六條線路的最佳路線線路換乘次數(shù)時(shí)間花費(fèi)坐車路線距離始發(fā)站s3359-s182811013l436-s1784-l21717s1557-s04812763l084-s1919-l043-s3077-l2732& 20s0971-s048511283l013-s2184-l41714s0008-s00731832l355-s22

40、63-l34511s0148-s04852733l024-s1234-l505-s516- l10416,23s0087-s36760253d27-d365（注：策略一按換乘次數(shù)、乘車時(shí)間、乘車費(fèi)用的順序進(jìn)行考慮）表（5）：策略二中六條線路的最佳路線線路時(shí)間換乘次數(shù)花費(fèi)坐車路線距離始發(fā)站s3359-s182810113l436-s1784-l21717s1557-s04817623l084-s1919-l043-s3077-l2732& 20s0971-s04858523l084-s1919-l259-s211-l27323, 14s0008-s00736725l150-s1426-t

41、2-s528-l103& 2s0148-s04857323l024-s1234-l505-s516- l10416, 23s0087-s36762503d27-d365（注：策略二按乘午時(shí)間、換乘次數(shù)、乘午費(fèi)用的順序進(jìn)行考慮）表（6）：策略三中六條線路的最佳路線線路換車次數(shù)花費(fèi)時(shí)間坐車路線距離始發(fā)站s3359-s182813101l436-s1784-l21717s1557-s04812376l084-s1919-l043-s3077-l27328, 20s0971-s048513128l013-s2184-l41714s0008-s00731283l355-s2263-l34511s

42、0148-s04852373l024-s1234-l505-s516- l10416,23s0087-s36760325d27-d365（注：策略三按換乘次數(shù)、乘車時(shí)間、乘車費(fèi)用的順序進(jìn)行考慮）6. 4模型二的結(jié)果分析比較表至（6）,對(duì)三種策略下的最優(yōu)路線進(jìn)行分析發(fā)現(xiàn)，對(duì)于線路 s3359-s1828和s1557-s0481無論是乘車時(shí)間、費(fèi)用還是擁擠程度都是一樣 的，但是對(duì)于有些路線，在不同策略下的相關(guān)信息會(huì)有很大的區(qū)別，比如： 線路s0971-s0485,在優(yōu)先考慮乘車次數(shù)的策略下，所需時(shí)間為128分鐘， 但是在優(yōu)先考慮時(shí)間的策略下，所需時(shí)間為85分鐘，相對(duì)減少了 43分鐘， 可見對(duì)于那些

43、比較重視時(shí)間的乘客來說，優(yōu)先考慮時(shí)間的策略要更優(yōu)，所 以我們從乘客不同需求進(jìn)行考慮，給出相應(yīng)的最佳出行路線是合理的。7問題三的解答問題三將步行作為一種交通方式進(jìn)行考慮，建立了模型三進(jìn)行求解。7.1問題三的數(shù)據(jù)處理7. 1. 1關(guān)于步行的假設(shè)設(shè)站點(diǎn)i到站點(diǎn)）的步行時(shí)間為若t ,則稱站點(diǎn)i與站點(diǎn)丿互稱為鄰 近站點(diǎn)，7是鄰近站點(diǎn)的口寸間上確界，即乘客所能忍受的最長(zhǎng)步行吋間，可令 t = 12分鐘，規(guī)定步行后換乘車次只能在鄰近站點(diǎn)或同一站點(diǎn)。1）所有站點(diǎn)之間的步行時(shí)間固定不變，并且不受外界其他因素的干擾；2）只有公汽站點(diǎn)間可以步行，地鐵站點(diǎn)間不能步行；3）任意兩個(gè)鄰近站點(diǎn)平均步行吋間是心=5分鐘。7.

44、1.2步行鄰邊化假設(shè)站點(diǎn)i到站點(diǎn)/的平均步行時(shí)間為彳門），定義以乘客所在的起始點(diǎn)為圓 心，以最長(zhǎng)步行時(shí)間t對(duì)應(yīng)的距離為半徑的圓形區(qū)域稱為起始點(diǎn)$加"的鄰接圓 域。由假設(shè)知，鄰接圓域內(nèi)任意公汽站點(diǎn)b都與妣切相鄰接，且b與也切的鄰 接耗時(shí)為tstartp,b）q將鄰接圓域抽象為下圖：72模型三的建立問題三在問題二的基礎(chǔ)上增加考慮了步行對(duì)最優(yōu)路線選取的影響，我們把步 行作為一種花費(fèi)為0,只需計(jì)算時(shí)間的交通工具。在僅考慮公汽或考慮公汽及地 鐵的時(shí)候，我們都對(duì)有不同需求的乘客推薦相應(yīng)的最佳路線，即考慮了三個(gè)策略。 但對(duì)于該問，步行并沒有增加出行的花費(fèi)，每個(gè)站點(diǎn)間平均步行時(shí)間為5分鐘， 就算乘公

45、汽或地鐵也要分別花費(fèi)3分鐘或2. 5分釗所以考慮步行對(duì)出行時(shí)間和 乘車費(fèi)用的影響不大，但是步行一站或兩站很可能會(huì)導(dǎo)致?lián)Q乘次數(shù)的變化和換乘 站點(diǎn)的變化，所以我們只考慮以換乘次數(shù)作為第k個(gè)目標(biāo)函數(shù)的多目標(biāo)規(guī)劃， 在優(yōu)先考慮換乘次數(shù)的基礎(chǔ)上，再考慮乘車時(shí)間次數(shù)和乘車費(fèi)用，即前兩問中的 策略一。7. 2.1確定目標(biāo)函數(shù)target one :乘換次數(shù)最少把步行作為一種交通工具考慮后，對(duì)換乘次數(shù)并沒有什么影響，所以換乘次 數(shù)同問題二，該目標(biāo)函數(shù)為：min坊target two：乘車時(shí)間最短問題三跟問題二中乘車時(shí)間不同的是要考慮步行的時(shí)間，即包括行駛時(shí)間、 換乘時(shí)間和鄰接公汽站點(diǎn)間的步行時(shí)間。4是各站最快

46、直達(dá)時(shí)間，是實(shí)際轉(zhuǎn)車次數(shù)，則行駛時(shí)間為：石(+1)換乘時(shí)間同問題二,為:5zf+6z+7z”4zf設(shè)/表示鄰接公汽站點(diǎn)間的步行時(shí)間，為乘車需要乘客步行的站數(shù)可能不止 一站，也有可能不步行，可令r表示乘客步行經(jīng)過的站點(diǎn)數(shù)，則鄰接公汽站點(diǎn)間 的步行時(shí)間為：t = kt.所以乘車時(shí)間為r (% +1) + 5 z； + 6 zf + 7 z； + 4 zf +仏從而得到第一個(gè)目標(biāo)函數(shù)為：min %(% + l) + 5z；+6z#+7z點(diǎn)+4z,+m° target three :乘車費(fèi)用最少步行并不能增加乘車費(fèi)用，所以乘車費(fèi)用的目標(biāo)函數(shù)也跟問題二中相同，即 min 工馬 w + 1)i,

47、jwe 綜上，多目標(biāo)整數(shù)規(guī)劃目標(biāo)函數(shù)為：min坊min 0 化;+1) + 5z； + 6z 譬 +7z 爲(wèi) + 4z 洛 + kt()min工馬化；+ 1)i.jwe7. 2. 2確定約束條件步行對(duì)換乘問題，包括換乘次數(shù)以及換乘方式均沒有影響，所以問題二中的 約束條件均適合問題三。另外我們假設(shè)任意兩個(gè)鄰近站點(diǎn)平均步行時(shí)間是 =5 分鐘，乂鄰近站點(diǎn)的時(shí)間上確界為7 = 12,即kt.<t,得到展0,1,2。所以約 朿條件為：a. + b,. <1 jg 1,3957 cj + d. < 1 jg 3969,3975 打石皿2zjg 1,3957f,./g 1395&

48、3996 kt0<t 0,1,27. 2. 3確定模型三綜上，我們確定的多目標(biāo)整數(shù)規(guī)劃模型為：min tf(j (+1) + 5z + 6z + 7z + 4z + ktqmin坊伽工坊必+ 1)ijee舛+ bjwlj g 1,3957c +d <1 je 3969,3975jj0 < min 珀 < %subject to << v/ < 2zje 1,39577 j “3958,3996kt<t z: e 0,1,27. 3模型三的求解模型三中以換乘次數(shù)少、乘車吋間短、費(fèi)用少為考慮的先后順序建立的多目 標(biāo)整數(shù)規(guī)劃模型三，增加考慮步行后，一些

49、相隔2站以內(nèi)的站點(diǎn)可以通過步行到 達(dá)。以題中給出的六條線路中的s1557-s0481, s0148-s0485為例,起始點(diǎn)s1557與 s3158, s0645, s0646相隔僅一站,與s2628, s2143, s3135相隔2站可以步行,終 點(diǎn) s0481 與 s0872,s2101,s3919 相隔僅 一站， 與 s0492,s0903 , s1179, s0871,s3667, s3919相隔2站也可以步行。線路s0148-s0485也可以按照同 樣的方法進(jìn)行分析，在此分析的基礎(chǔ)上可以運(yùn)用matlab軟件編程進(jìn)行求解(代碼 詳見附錄五)，以線路s1557-s0481, s0148-s

50、0485為例，得到優(yōu)先考慮乘車時(shí)間的最 佳路線如下表(7):表(7):問題三中的最佳路線線路最優(yōu)路線換 乘時(shí) 間花 費(fèi)s1557-s0481從s1557步行2站到s2143-l084-s1919-l043-s3077-l2731923s0148-s0485從 s0148 步行 1 站到 s3182-l308-s36-l157-s0722 再步 行一站到s0485169274模型三的結(jié)果分析基于問題三數(shù)據(jù)處理中的假設(shè)(2),只有公汽站點(diǎn)間可以步行，地鐵站點(diǎn)間 不能步行；所以步行這種出行方式的增加只會(huì)對(duì)公汽之間的換乘產(chǎn)生影響，所以 可以將模型三中的結(jié)果與模型一策略一中的結(jié)果對(duì)比，模型一中線路 s1

51、557-s0481, s0148-s0485相應(yīng)的路線、乘車吋間、換乘次數(shù)如下表(8)：表(8):模型一中相應(yīng)路線的結(jié)果線路最優(yōu)路線換乘次數(shù)時(shí)間花費(fèi)s1557-s10481l084-s1919-l043-s3077-l2732763s0148-s0485l024-s1234-l505-s516- l1042733將表與表(8)對(duì)比可以看出對(duì)于線路s1557-s0481,當(dāng)轉(zhuǎn)乘次數(shù)減小時(shí)， 總的岀行吋間變長(zhǎng)，費(fèi)用不變；但是對(duì)于路線s0148-s0485,當(dāng)轉(zhuǎn)乘次數(shù)減少吋, 不僅出行時(shí)間減少4分鐘，而且費(fèi)用也減少了一元。所以出行時(shí)，適當(dāng)?shù)倪x擇步 行是一種很好的方式。8模型的評(píng)價(jià)、改進(jìn)和推廣模型的評(píng)

52、價(jià)優(yōu)點(diǎn)：1、通過實(shí)際調(diào)查，確定了乘客對(duì)乘車的不同需求，以乘車時(shí)間、換乘次數(shù)、乘 車花費(fèi)為目標(biāo)建立多目標(biāo)優(yōu)化模型，使問題更加清晰，得岀的線路更全面合 理；2、將復(fù)雜的公交網(wǎng)轉(zhuǎn)化為圖論問題，在圖論基礎(chǔ)上求解出轉(zhuǎn)乘次數(shù)不超過兩次 時(shí)的所有可行方案，根據(jù)乘客的不同需求，給出最佳路線方案，模型實(shí)用性 較強(qiáng)；3、利用matlab元胞數(shù)組存儲(chǔ)數(shù)據(jù)信息，縮小信息存儲(chǔ)空間，并選用適當(dāng)?shù)乃阉?算法，縮短運(yùn)算時(shí)間，有較強(qiáng)的實(shí)用性；4、模型的現(xiàn)實(shí)意義強(qiáng)，具有很好的實(shí)用性和擴(kuò)展性。缺點(diǎn)：1、在轉(zhuǎn)乘次數(shù)超過2次的情況下，運(yùn)用所建立的模型求解計(jì)算過程復(fù)雜，計(jì)算量 過大；故模型存在一定的局限性。2、由于在計(jì)算過程中題目給的平

53、均行駛及轉(zhuǎn)車時(shí)間是非現(xiàn)實(shí)的，所以使得本模 型的應(yīng)用于現(xiàn)實(shí)時(shí)存在偏差。模型的改進(jìn)由于公交網(wǎng)木身就是一個(gè)復(fù)雜的連通圖，數(shù)據(jù)信息量大，而我們所建立的模 型只考慮了乘客對(duì)乘車吋間，轉(zhuǎn)乘次數(shù)，乘車費(fèi)用以及擁擠程度的需求，可以適 當(dāng)?shù)目紤]其他的需求，如：乘車途中的觀光路線，線路屮經(jīng)過的標(biāo)志性建筑等因 素。從人性化的角度考慮，述可以把車輛的負(fù)載量，舒適度考慮進(jìn)去。另外，本文是一個(gè)靜態(tài)的交通系統(tǒng)，所有的信息都己經(jīng)給定。通過本題的數(shù) 學(xué)模型，只要給出起始點(diǎn)和目的地，我們就可以通過算法求得應(yīng)該走的路線，所 花的吋間以及乘車費(fèi)用。但是在現(xiàn)實(shí)生活中，交通系統(tǒng)隨吋都可能在發(fā)生變化, 如：上下班時(shí)候的某些線路運(yùn)力不足，由

54、于交通事故某兩個(gè)站點(diǎn)z間的線路暫時(shí) 中斷，但是這些在本題中都沒有能夠反應(yīng)出來，這樣我們的路徑推薦模型就可能 將用戶帶到已經(jīng)中斷或者是非常擁擠的線路中。所以從實(shí)際出發(fā)，應(yīng)該建立動(dòng)態(tài) 系統(tǒng)，將交通系統(tǒng)查詢計(jì)算機(jī)網(wǎng)絡(luò)化，每一個(gè)查詢終端類比為一個(gè)路由器，同時(shí) 采用類似于路由算法的實(shí)吋更新算法。這樣才能夠根據(jù)最新的數(shù)據(jù)信息判斷出最 優(yōu)方案。模型的推廣木文采用多目標(biāo)規(guī)劃模型確定北京的公交線路，多目標(biāo)規(guī)劃模型不僅可以應(yīng) 用于公交線路的查詢還可以運(yùn)用到其他方面，比如：國(guó)防部門設(shè)計(jì)某種導(dǎo)彈吋， 一般都要求導(dǎo)彈的射程要遠(yuǎn)，精度要高，重量要最輕以及消耗燃料要最省等；在 物資調(diào)運(yùn)過程中，既要考慮在運(yùn)輸過程中少走冤枉路

55、，同時(shí)又耍考慮節(jié)約運(yùn)費(fèi)等。9.參考文獻(xiàn)1湖北大學(xué)生數(shù)學(xué)競(jìng)賽專家組，數(shù)學(xué)建模（本科冊(cè)），華屮科技大學(xué)出版社, 2006. 2. 王沫然matlab與科學(xué)計(jì)算（第二版）電子工業(yè)出版社2005. 12.3沈雷張?chǎng)务R福誠(chéng)一種公共交通的最優(yōu)路徑算法海洋測(cè)繪第25卷第6期 2005. 11,41-434姜啟源謝金星葉俊數(shù)學(xué)模型（第三版）m北京：高等教育出版社200310.附錄附錄一：directmatrix.m%生成直達(dá)數(shù)據(jù)庫dmclear all;clc%生成3996*3996的空直達(dá)矩陣dm=cell(3996/3996);%數(shù)據(jù)導(dǎo)入file=fopen('d :我的文檔桌面1.1公汽線路信息.txt'/r1);icou nt=o;while 1fprintf('己導(dǎo)入d 彳亍n'jcount);icou nt 二 icou nt+l;tline=fgetl(file);if s