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

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

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

3、軟件編程求解得到相應的 最佳路線。以線路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)多目標整數(shù)規(guī)劃 多目標分層序列法 局部搜索算法1 問題重述1.1問題背景傳承華夏五千年的文明，夢圓十三億華夏兒女的暢想，我國人民翹首企盼的 第29屆奧運會明年8月將在北京舉行!在觀看奧運的眾多方式之

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

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

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

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

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

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

10、將這三種線路進行數(shù)據(jù)處理: 下行線是上行線原路返回這種線路有兩個端點站，在兩個端點之間雙向行車，而且兩個方向上的行車 路線相同，經(jīng)過同樣的站點序列，只是線路的方向不同；上行線與下行線的站點名不完全相同這種線路與下行線是上行線的原路返回不同，下行線與上行線經(jīng)過的站點不 完全相同，但是起始站和終點站相同； 線路為環(huán)形線對環(huán)形線路的站點進行分析，把一個環(huá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建立“公汽直達數(shù)據(jù)庫dm ”從實際出發(fā)，結(jié)合公眾出行心理，公汽線路選擇應優(yōu)先考慮兩站點z間是否 有直達車，那么在查詢系統(tǒng)內(nèi)部應設(shè)有任兩站點的直達線路表，以方便查詢時優(yōu) 先快速查詢是否有直達車，若有，則直接輸出所有直達車輛；若無，再搜索換乘 路線。在數(shù)據(jù)導入的過程中，首先考慮直接從文本文件導入matlab中，但是本題共 有3957個站點，520條公交線路，若每個隊列的每個數(shù)據(jù)都是用雙精度進行存 儲，那么內(nèi)存占用大，實際輸岀時運行時間長，考慮到所存儲的信息

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

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

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

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

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

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

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

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

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

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

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

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

24、7）判斷是否需要兩次換車集合f不是空集，轉(zhuǎn)入8）集合f是空集，不考慮8）基于三種不同的策略，推薦最優(yōu)乘車線路5. 4. 2求解結(jié)果根據(jù)上面的算法思想，可以運用ma1tab軟件進行編程（代碼詳見附錄 二），由于我們釆用的是多目標分層序列整數(shù)規(guī)劃模型，所以根據(jù)確定的三種 不同的策略，可以得到相應策略的最佳路線，表（1）至表（3）分別給出了三種不同 策略下題中要求解的六條線路的最佳路線。表（1）：策略一中六條線路的最佳路線線路換乘次數(shù)時間花費坐車路線距離始發(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ù)、乘午時間、乘午費用的順序進行考慮）表（2）：策略二中六條線路的最佳路線線路時間換乘次數(shù)花費坐車路線距離始發(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ù)、乘車費用的順序進行考慮）表（3）：策略三中六條線路的最佳路線線路換車次數(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ù)、乘車時間、乘車費用的順序進行考慮）5. 5模型一的結(jié)果分析比較表仃）至表（3）的結(jié)果，可以看到策略一和策略三的結(jié)果完全一樣，這主 要是因為乘坐公交的費用變化不顯著，每經(jīng)過20個站點才增加一元錢，這樣一來 在某

28、個范圍內(nèi)，乘坐公交的費用相差不會很遠，所以對路線的選取不會有太大影 響。我們縱向比較三種策略的時間，將三種策略下的時間變化作圖如下：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.問題二的解答問題二同吋考慮公汽與地鐵線路，我們建立了模型二進行求解。6.1問題二的數(shù)據(jù)處理6.1. 1對兩條地鐵線路的處理基于對三種公汽線路路線的抽彖方法，用相同的方法對兩地鐵線路7；,7；進 行抽象化處理。7；：返回時沿原路返回，這種線路有兩個端點站，在兩個端點之間雙向行車，而 r兩個方向上的行車路線相同，經(jīng)過同樣的站點序列，只是線

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

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

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

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

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

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

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

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

38、e 1,3957c. + d < 13969,3975jj0 < min a.- < %fje 1,3957zje395& 39966. 2. 3確定模型二綜上我們確定多fl標整數(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、索算法思想，可 以運用ma1tab軟件進行編程(代碼詳見附錄四)，由于我們采用的是多目標 分層序列整數(shù)規(guī)劃模型，所以根據(jù)確定的三種不同的策略，可以得到相應策略的 最佳路線，表(4)至表(6)分別給出了三種不同策略下題中要求解的六條線路的最 佳路線。表(4)：策略一中六條線路的最佳路線線路換乘次數(shù)時間花費坐車路線距離始發(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ù)、乘車時間、乘車費用的順序進行考慮）表（5）：策略二中六條線路的最佳路線線路時間換乘次數(shù)花費坐車路線距離始發(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ù)、乘午費用的順序進行考慮）表（6）：策略三中六條線路的最佳路線線路換車次數(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ù)、乘車時間、乘車費用的順序進行考慮）6. 4模型二的結(jié)果分析比較表至（6）,對三種策略下的最優(yōu)路線進行分析發(fā)現(xiàn)，對于線路 s3359-s1828和s1557-s0481無論是乘車時間、費用還是擁擠程度都是一樣 的，但是對于有些路線，在不同策略下的相關(guān)信息會有很大的區(qū)別，比如： 線路s0971-s0485,在優(yōu)先考慮乘車次數(shù)的策略下，所需時間為128分鐘， 但是在優(yōu)先考慮時間的策略下，所需時間為85分鐘，相對減少了 43分鐘， 可見對于那些

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

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

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

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

47、jwe 綜上，多目標整數(shù)規(guī)劃目標函數(shù)為：min坊min 0 化;+1) + 5z； + 6z 譬 +7z 爲 + 4z 洛 + kt()min工馬化；+ 1)i.jwe7. 2. 2確定約束條件步行對換乘問題，包括換乘次數(shù)以及換乘方式均沒有影響，所以問題二中的 約束條件均適合問題三。另外我們假設(shè)任意兩個鄰近站點平均步行時間是 =5 分鐘，乂鄰近站點的時間上確界為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確定模型三綜上，我們確定的多目標整數(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ù)少、乘車吋間短、費用少為考慮的先后順序建立的多目 標整數(shù)規(guī)劃模型三，增加考慮步行后，一些

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

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

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

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

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

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

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