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

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

2、同策略下的最優(yōu)線路(最佳線路見表(1)至(3)o針對問題二，同時考慮公汽與地鐵線路，將地鐵站點(diǎn)與鄰接的公汽站點(diǎn)抽象 為同一新站點(diǎn)，重新建立站點(diǎn)間直達(dá)線路信息存儲元胞結(jié)構(gòu)。在問題一的基礎(chǔ)上 增加考慮地鐵站對費(fèi)用、換乘時間和行駛時間的影響，仍然以乘客對線路的三種 主要需求為目標(biāo)，以擁擠程度為約束，建立多目標(biāo)整數(shù)規(guī)劃模型，利用matlab 軟件編程求解得到3種不同策略下的最優(yōu)路線(最佳線路見表(4)至(6)o針對問題三，增加考慮步行的出行方式，在公汽站點(diǎn)間當(dāng)站點(diǎn)數(shù)目不超過2 時，可以以步行代替，從而減少換乘次數(shù)。在此基礎(chǔ)上，按換乘次數(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問題背景傳承華夏五千年的文明，夢圓十三億華夏兒女的暢想，我國人民翹首企盼的 第29屆奧運(yùn)會明年8月將在北京舉行!在觀看奧運(yùn)的眾多方式之

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

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

6、路交通事故等意外情況;假設(shè)四：公交準(zhǔn)點(diǎn)到達(dá)，不考慮紅綠燈等待時間；假設(shè)五：乘客在起始站時不考慮擁擠程度，只在轉(zhuǎn)乘時考慮擁擠程度；假設(shè)六：乘客到起始站乘車時，不考慮等車時間；假設(shè)七：同一地鐵站對應(yīng)的任意兩個公汽站之間可以通過地鐵站換乘，在此換乘 過程中不考慮換乘時間和費(fèi)用。3. 符號說明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上車時站點(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)丿的步行時間t鄰近站點(diǎn)的時間上確界任意兩個鄰近站點(diǎn)平均步行時間t表示鄰接公汽站點(diǎn)間的步行時間4. 問題分析這是一個多目標(biāo)決策的網(wǎng)絡(luò)優(yōu)化問題。公交查詢系統(tǒng)需要滿足查詢者各種不 同需求，給出最優(yōu)方案，這是我們建立模型的根木出發(fā)點(diǎn)，有關(guān)問題的求解隨著 規(guī)模擴(kuò)大將逐層深入。對于問題一，題目給出的公汽線路主要分為上下行線、原路折回線及環(huán)行 線，線路不同，選擇不同，故對每種線路需要進(jìn)行抽象化處理。站點(diǎn)較多，信息 量較多，需要選擇合適的存儲方法存儲數(shù)據(jù)，存儲題中的線路名、車號和時間。 解決這些問題后，就要對乘客的出行需求進(jìn)行調(diào)查，看看乘客出

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

9、計(jì)合適的算法，編程求解得到不同需求的 乘客相應(yīng)的最優(yōu)路線。對于問題三，該問在問題二的基礎(chǔ)上增加考慮步行對最優(yōu)路線選取帶來的 影響，可以把步行作為另一種交通工具進(jìn)行考慮。根據(jù)實(shí)際情況對步行相關(guān)信息 做出合理的假設(shè)，由于步行這種出行方式不花費(fèi)時間，對換乘次數(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ù)處理: 下行線是上行線原路返回這種線路有兩個端點(diǎn)站，在兩個端點(diǎn)之間雙向行車，而且兩個方向上的行車 路線相同，經(jīng)過同樣的站點(diǎn)序列，只是線路的方向不同；上行線與下行線的站點(diǎn)名不完全相同這種線路與下行線是上行線的原路返回不同，下行線與上行線經(jīng)過的站點(diǎn)不 完全相同，但是起始站和終點(diǎn)站相同； 線路為環(huán)形線對環(huán)形線路的站點(diǎn)進(jìn)行分析，把一個環(huán)形拉成一條直線，以該直線的終 點(diǎn)為對稱點(diǎn)進(jìn)行翻折，將終點(diǎn)左邊的直線對稱到右邊，形成該直線的延長 線，如下：這種環(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á)線路表，以方便查詢時優(yōu) 先快速查詢是否有直達(dá)車，若有，則直接輸出所有直達(dá)車輛；若無，再搜索換乘 路線。在數(shù)據(jù)導(dǎo)入的過程中，首先考慮直接從文本文件導(dǎo)入matlab中，但是本題共 有3957個站點(diǎn)，520條公交線路，若每個隊(duì)列的每個數(shù)據(jù)都是用雙精度進(jìn)行存 儲，那么內(nèi)存占用大，實(shí)際輸岀時運(yùn)行時間長，考慮到所存儲的信息

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

13、調(diào)查結(jié)果，用excel畫出居民對出行時的費(fèi)用、 乘車時間、乘換次數(shù)、步行時間以及擁擠程度的統(tǒng)計(jì)結(jié)果如下圖（1）:系列1圖（1）:居民出行需求結(jié)果的統(tǒng)計(jì)我們可以看到，出行者對不同因素的看重比例是不同的，該市居民出行需求 對于北京這樣的大城市也同樣適用。由于一般情況下路程長短和所用時間是密切 聯(lián)系的，乘客關(guān)注路程也是為了節(jié)約時間，所以問題中已經(jīng)將路程的相關(guān)信息轉(zhuǎn) 化成為吋間了，即只需考慮時間最短。因此我們的模型中對公交網(wǎng)絡(luò)的優(yōu)化需要 考慮四個主要優(yōu)化目標(biāo)：換乘次數(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)生煩躁情緒，需要更長的時間和更多 的費(fèi)用；因此在設(shè)計(jì)算法時，只搜索直達(dá)、換乘一次和換乘2次的乘車方案。5. 2. 3計(jì)算機(jī)系統(tǒng)自主查詢路線的流程通過上述調(diào)查顯示的統(tǒng)計(jì)結(jié)果得知，乘客乘車都會考慮換乘次數(shù)，時間，費(fèi) 用以及擁擠程度的問題，但是不同的乘客對這些需求考慮的先

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

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

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

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

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

20、，其中1表示單一票價，2表示分段計(jì)費(fèi)；又由于分 段計(jì)價的票價為：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從而得到第三個目標(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ù)、乘車 時間和乘車費(fèi)用相同時，考慮以擁擠程度的高低來確定最終的最佳路線。擁擠程度：實(shí)際生活中，當(dāng)離起始站點(diǎn)越近時，車上的乘客越少。設(shè)©表 示從起始站startp到終點(diǎn)站endp的站點(diǎn)數(shù)0 , aif表示從站點(diǎn)2上車時站點(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)，采用 局部搜索思想，對三種不同的策略進(jìn)行分類，在每種策略屮求出最優(yōu)解。首先根 據(jù)乘客輸入的起始點(diǎn)和終點(diǎn)，分別對存儲的數(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ù)時間花費(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ù)、乘午時間、乘午費(fèi)用的順序進(jìn)行考慮）表（2）：策略二中六條線路的最佳路線線路時間換乘次數(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ù)、乘車費(fèi)用的順序進(jìn)行考慮）表（3）：策略三中六條線路的最佳路線線路換車次數(shù)花費(fèi)時間坐車路線距離始發(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ù)、乘車時間、乘車費(fèi)用的順序進(jìn)行考慮）5. 5模型一的結(jié)果分析比較表仃）至表（3）的結(jié)果，可以看到策略一和策略三的結(jié)果完全一樣，這主 要是因?yàn)槌俗坏馁M(fèi)用變化不顯著，每經(jīng)過20個站點(diǎn)才增加一元錢，這樣一來 在某

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

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

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

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

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

33、汽、地鐵直達(dá)數(shù)據(jù)庫dat的基礎(chǔ)上，分別確定三個目標(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è)六，到起始站等車的時間忽略不計(jì)，那么乘車時間包括行駛時間和 換車吋間。設(shè)石是各站最快直達(dá)時間，匕;是實(shí)際轉(zhuǎn)車次數(shù)，則行駛時間為化;+ 1）在起始站點(diǎn)i

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

35、中1表示單一3票價，2表示分段計(jì)費(fèi)，3表示地鐵票價；可設(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從而得到第三個目標(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時，1表示在公汽站點(diǎn)丿換乘公汽，0表示在公汽站點(diǎn)丿不換乘公汽；當(dāng)/c = b,；g 1,3957時，1表示在公汽站點(diǎn)/換乘地鐵，0表示在公汽站點(diǎn)j不換乘地鐵；當(dāng)k = cj"3958,3996時, 1表示在地鐵站j換乘公汽，0表示在地鐵站丿不換乘公汽；當(dāng)k = d時，1表示 在地鐵站丿換乘地鐵，0表示在地鐵站丿不換乘地鐵，而地鐵換乘地鐵只有當(dāng)兩 條地鐵線路經(jīng)過的站點(diǎn)相同吋，才可以換乘，由題中給出的地鐵門線換乘公汽 信息與地鐵卩2線換乘公汽信息可知：地鐵線門，丁2只同時經(jīng)過d12和d18。此 時丿分別等于3969, 3975o討論乘客是否換乘的約束條件，乘客在公汽站

37、吋有三種不同的選擇，分別為 不換乘公汽、換乘公汽和轉(zhuǎn)乘地鐵，三種選擇不能同時進(jìn)行，那么相應(yīng)的約束條 件為：aj + b. < 1 丿 “1,3957乘客在地鐵站d12和d18也相應(yīng)的有三種不同的選擇：不換乘地鐵、換乘公汽和換乘地鐵，三種選擇不能同時進(jìn)行，所以相應(yīng)的約束條件為：cj + q/517 g 3969,3975實(shí)際生活中，當(dāng)離起始站點(diǎn)越近時，車上的乘客越少。甸的最小值越接近© 表示擁擠程度越高，©的最小值越接近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ù)時間花費(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ù)、乘車時間、乘車費(fèi)用的順序進(jìn)行考慮）表（5）：策略二中六條線路的最佳路線線路時間換乘次數(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ù)、乘午費(fèi)用的順序進(jìn)行考慮）表（6）：策略三中六條線路的最佳路線線路換車次數(shù)花費(fèi)時間坐車路線距離始發(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ù)、乘車時間、乘車費(fèi)用的順序進(jìn)行考慮）6. 4模型二的結(jié)果分析比較表至（6）,對三種策略下的最優(yōu)路線進(jìn)行分析發(fā)現(xiàn)，對于線路 s3359-s1828和s1557-s0481無論是乘車時間、費(fèi)用還是擁擠程度都是一樣 的，但是對于有些路線，在不同策略下的相關(guān)信息會有很大的區(qū)別，比如： 線路s0971-s0485,在優(yōu)先考慮乘車次數(shù)的策略下，所需時間為128分鐘， 但是在優(yōu)先考慮時間的策略下，所需時間為85分鐘，相對減少了 43分鐘， 可見對于那些

43、比較重視時間的乘客來說，優(yōu)先考慮時間的策略要更優(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)）的步行時間為若t ,則稱站點(diǎn)i與站點(diǎn)丿互稱為鄰 近站點(diǎn)，7是鄰近站點(diǎn)的口寸間上確界，即乘客所能忍受的最長步行吋間，可令 t = 12分鐘，規(guī)定步行后換乘車次只能在鄰近站點(diǎn)或同一站點(diǎn)。1）所有站點(diǎn)之間的步行時間固定不變，并且不受外界其他因素的干擾；2）只有公汽站點(diǎn)間可以步行，地鐵站點(diǎn)間不能步行；3）任意兩個鄰近站點(diǎn)平均步行吋間是心=5分鐘。7.

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

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

46、直達(dá)時間，是實(shí)際轉(zhuǎn)車次數(shù)，則行駛時間為：石(+1)換乘時間同問題二,為:5zf+6z+7z”4zf設(shè)/表示鄰接公汽站點(diǎn)間的步行時間，為乘車需要乘客步行的站數(shù)可能不止 一站，也有可能不步行，可令r表示乘客步行經(jīng)過的站點(diǎn)數(shù)，則鄰接公汽站點(diǎn)間 的步行時間為：t = kt.所以乘車時間為r (% +1) + 5 z； + 6 zf + 7 z； + 4 zf +仏從而得到第一個目標(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確定約束條件步行對換乘問題，包括換乘次數(shù)以及換乘方式均沒有影響，所以問題二中的 約束條件均適合問題三。另外我們假設(shè)任意兩個鄰近站點(diǎn)平均步行時間是 =5 分鐘，乂鄰近站點(diǎn)的時間上確界為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)先考慮乘車時間的最 佳路線如下表(7):表(7):問題三中的最佳路線線路最優(yōu)路線換 乘時 間花 費(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)間 不能步行；所以步行這種出行方式的增加只會對公汽之間的換乘產(chǎn)生影響，所以 可以將模型三中的結(jié)果與模型一策略一中的結(jié)果對比，模型一中線路 s1

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

52、價優(yōu)點(diǎn)：1、通過實(shí)際調(diào)查，確定了乘客對乘車的不同需求，以乘車時間、換乘次數(shù)、乘 車花費(fèi)為目標(biāo)建立多目標(biāo)優(yōu)化模型，使問題更加清晰，得岀的線路更全面合 理；2、將復(fù)雜的公交網(wǎng)轉(zhuǎn)化為圖論問題，在圖論基礎(chǔ)上求解出轉(zhuǎn)乘次數(shù)不超過兩次 時的所有可行方案，根據(jù)乘客的不同需求，給出最佳路線方案，模型實(shí)用性 較強(qiáng)；3、利用matlab元胞數(shù)組存儲數(shù)據(jù)信息，縮小信息存儲空間，并選用適當(dāng)?shù)乃阉?算法，縮短運(yùn)算時間，有較強(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)車時間是非現(xiàn)實(shí)的，所以使得本模 型的應(yīng)用于現(xiàn)實(shí)時存在偏差。模型的改進(jìn)由于公交網(wǎng)木身就是一個復(fù)雜的連通圖，數(shù)據(jù)信息量大，而我們所建立的模 型只考慮了乘客對乘車吋間，轉(zhuǎn)乘次數(shù)，乘車費(fèi)用以及擁擠程度的需求，可以適 當(dāng)?shù)目紤]其他的需求，如：乘車途中的觀光路線，線路屮經(jīng)過的標(biāo)志性建筑等因 素。從人性化的角度考慮，述可以把車輛的負(fù)載量，舒適度考慮進(jìn)去。另外，本文是一個靜態(tài)的交通系統(tǒng)，所有的信息都己經(jīng)給定。通過本題的數(shù) 學(xué)模型，只要給出起始點(diǎn)和目的地，我們就可以通過算法求得應(yīng)該走的路線，所 花的吋間以及乘車費(fèi)用。但是在現(xiàn)實(shí)生活中，交通系統(tǒng)隨吋都可能在發(fā)生變化, 如：上下班時候的某些線路運(yùn)力不足，由

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

55、，同時又耍考慮節(jié)約運(yùn)費(fèi)等。9.參考文獻(xiàn)1湖北大學(xué)生數(shù)學(xué)競賽專家組，數(shù)學(xué)建模（本科冊），華屮科技大學(xué)出版社, 2006. 2. 王沫然matlab與科學(xué)計(jì)算（第二版）電子工業(yè)出版社2005. 12.3沈雷張鑫馬福誠一種公共交通的最優(yōu)路徑算法海洋測繪第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