公交查詢系統(tǒng)最佳路線設(shè)計(jì)

公交查詢系統(tǒng)最佳路線設(shè)計(jì)摘要本文研究的是在三種不同情況下，確定任意兩站點(diǎn)最優(yōu)路線問題。結(jié)合生活實(shí)際，我們定義最優(yōu)路線標(biāo)準(zhǔn)是換乘次數(shù)最少，所用時(shí)間最短，乘車費(fèi)用最低，并將其分別位作為第一、第二、第三目標(biāo)建立多目標(biāo)規(guī)劃模型。利用廣度優(yōu)先遍歷原理編程得到滿意的乘車路線。針對問題一，只考慮公交的情況下，對公交路線進(jìn)行抽象化處理。根據(jù)網(wǎng)上調(diào)查結(jié)果，確定多目標(biāo)規(guī)劃模型，利用matlab編程求解得到依次滿足三個(gè)目標(biāo)的任意兩點(diǎn)的乘車路線。以下為6對起始站一終到站之間的部分可行路線：起始f終到站路線轉(zhuǎn)乘時(shí)間/分費(fèi)用S3359-S1828S3359切36（下）＞S1784l167（下）＞S182811013S1557fS0481S1557l08（下）＞S3389l08。（下）＞S2361—L312（下）＞S048121303S0971fS0485S0971L013（下）＞S2184L417（下）＞S048511283S0008fS0073S0008L15（下）＞S2683l058下）＞S00731832S0148fS0485S0148l02（環(huán)）＞S0345lvkk下）＞S3037—L104（下）＞S048521303S0087fS3676S0087L216（下）＞S0145 L506＞S367611253針對問題二，將地鐵站點(diǎn)與其周圍的公汽站抽象為同一站點(diǎn)。同樣建立以轉(zhuǎn)乘次數(shù)最少的為第一目標(biāo)，所用時(shí)間短和費(fèi)用低分別為第二、三目標(biāo)的多目標(biāo)規(guī)劃模型。利用matlab編程求解，得到滿意的乘車路線。針對問題三，以乘客所在站點(diǎn)為中心，步行時(shí)間上線為半徑的區(qū)域內(nèi)站點(diǎn)均考慮步行。將此區(qū)域內(nèi)站點(diǎn)抽象為同一站點(diǎn)，建立多目標(biāo)規(guī)劃模型，進(jìn)行編程求解，并與問題二結(jié)果進(jìn)行比較。關(guān)鍵字多目標(biāo)規(guī)劃模型廣度優(yōu)先遍歷抽象化關(guān)鍵字多目標(biāo)規(guī)劃模型廣度優(yōu)先遍歷抽象化1、 問題重述1.1背景信息：我國人民翹首企盼的第29屆奧運(yùn)會明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場觀看奧運(yùn)比賽，其中大部分人將會乘坐公共交通工具(簡稱公交，包括公汽、地鐵等)出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。1.2需要解決的問題：1、 僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站一終到站之間的最佳路線(要有清晰的評價(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í)間，請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。2、 模型假設(shè)與符號說明2.1模型假設(shè)假設(shè)1：相鄰站點(diǎn)平均時(shí)間一定；假設(shè)2：公交運(yùn)行不出現(xiàn)交通堵塞，公交準(zhǔn)時(shí)到達(dá)每個(gè)站點(diǎn);假設(shè)3：交通工具票價(jià)穩(wěn)定，不考慮其他因素對票價(jià)的影響;假設(shè)4：所有人的步行速度相等；假設(shè)5：不會出現(xiàn)車輛擁擠或超載而使乘客誤車的情況。2.2符號說明t相鄰公汽站平均行駛時(shí)間t二3分鐘t'相鄰地鐵站平均行駛時(shí)間t'=2.5分鐘t1公汽換乘公汽平均耗時(shí)t=5分鐘1t2公汽換乘地鐵平均耗時(shí)t=6分鐘2t3地鐵換乘地鐵平均耗時(shí)t=4分鐘3t4地鐵換乘公汽平均耗時(shí)t=7分鐘4

T從始發(fā)站到終點(diǎn)站所用總時(shí)間W從始發(fā)站到終點(diǎn)站所花總費(fèi)用y1公汽與公汽的轉(zhuǎn)乘次數(shù)y2公汽轉(zhuǎn)乘地鐵的次數(shù)y3地鐵轉(zhuǎn)乘地鐵的次數(shù)y4地鐵轉(zhuǎn)乘公汽的次數(shù)Y從始發(fā)站到終點(diǎn)站總共轉(zhuǎn)乘次數(shù)x從始發(fā)站到終點(diǎn)站乘坐公交所經(jīng)過的總站點(diǎn)數(shù)（不考慮出發(fā)占）x'從始發(fā)站到終點(diǎn)站乘坐地鐵所經(jīng)過的總站點(diǎn)數(shù)（不考慮出發(fā)占）tpq從站點(diǎn)p到站點(diǎn)q的步行時(shí)間t〃乘客選擇步行的時(shí)間上限3、 問題分析本文主要研究的交通網(wǎng)絡(luò)中的尋優(yōu)問題，要求在三種不同情況下，找出任意兩站點(diǎn)之間最佳路線。聯(lián)系生活實(shí)際，考慮公眾乘坐公交的出行，確定目標(biāo)函數(shù)，找出乘客滿意的乘車路線。對于問題一，在僅考慮公汽線路的情況下，根據(jù)公眾乘坐公交出行的考慮因素，建立以換車次數(shù)最少為第一目標(biāo)，所花時(shí)間和費(fèi)用最少分別為第二、第三目標(biāo)下的多目標(biāo)規(guī)劃模型。通過題中給出數(shù)據(jù)運(yùn)用matlab編程得到任意兩點(diǎn)之間的乘車路線，再結(jié)合目標(biāo)函數(shù)對所得路線進(jìn)行篩選，找出換車次數(shù)最少，所花時(shí)間和費(fèi)用較小的路線作為最佳路線。對于問題二，在同時(shí)考慮地鐵和公交的情況下。根據(jù)問題一中的抽象化方法，將地鐵線路T1抽象為一條單向的公交線路，T2抽象為一條環(huán)形的公交線路；對于地鐵站點(diǎn)，由于地鐵與鄰近公汽站點(diǎn)可換乘，我們認(rèn)為地鐵站點(diǎn)與周圍的公汽站點(diǎn)距離較近，將其抽象化為同一站點(diǎn)，重新構(gòu)造站點(diǎn)間的關(guān)系矩陣。結(jié)合問題一，建立優(yōu)化模型進(jìn)行編程求解。對于問題三，將步行考慮在出行方式中。一般來說，出行者選擇步行的目的是為了減少換乘次數(shù)或花費(fèi)時(shí)間。當(dāng)兩個(gè)站點(diǎn)相鄰近時(shí)，乘客才愿意選擇步行換乘，因此我們需確定一個(gè)鄰近站點(diǎn)的范圍界限。但考慮到本文的目標(biāo)之一是所用時(shí)間最短，為此將鄰近站點(diǎn)的范圍界限轉(zhuǎn)化為時(shí)間界限，即所用步行時(shí)間在某一范圍之內(nèi)時(shí)，乘客才考慮步行。基于這種思想，再結(jié)合問題一，確定多目標(biāo)優(yōu)化模型進(jìn)行編程求解。

4、 數(shù)據(jù)處理4.1對站點(diǎn)數(shù)據(jù)處理利用matlab編程從文本中按行讀取數(shù)據(jù)，將每一行數(shù)據(jù)作為一個(gè)元胞，按行存放在元胞矩陣中，如下圖1示：元胞1□---L001元胞2分段計(jì)價(jià)元胞3|--------S0619-S1914..元胞...［一一…4.2地鐵線路的抽象處理地鐵與鄰近公汽站點(diǎn)可換乘說明地鐵站點(diǎn)及其周圍的公汽站點(diǎn)距離較近，所以考慮將其抽象為新的站點(diǎn)，如下圖2：加靠為一個(gè)站點(diǎn)4.3公交乘客出行心理調(diào)查分析：在研究乘公交出行最優(yōu)算法時(shí)，首先要了解乘客出行時(shí)所要考慮的因素。通過對公交乘客的出行心理、行為的調(diào)查研究來確定模型的優(yōu)化目標(biāo)及約束條件是必要的。根據(jù)網(wǎng)上搜索得到合肥市關(guān)于公交乘客出行需求的調(diào)查結(jié)果，如圖3所示：從圖中可以看出公交乘客在出行時(shí)，考慮最多的是換乘次數(shù)，其次時(shí)間最短（在此將時(shí)間最短和路程最短統(tǒng)一作為時(shí)間最短來考慮）和費(fèi)用最少。所以在換乘次數(shù)已經(jīng)確定的情況下，選擇時(shí)間較短和費(fèi)用較少的路線作為最佳路線。4.4所能接受的最長步行時(shí)間調(diào)查表:

結(jié)合實(shí)際情況，乘客對距離較近的站點(diǎn)會考慮步行換乘，省錢的同時(shí)也可能節(jié)省時(shí)間。當(dāng)步行時(shí)間較短時(shí)，才會選擇步行。以下是通過網(wǎng)上搜索得到的換乘口一S口一S分鐘」S.86%-20^鐘以上」S.S6%^16-20^,7.59%通過觀察發(fā)現(xiàn)，大多數(shù)人所能接受的最長步行時(shí)間是6-10分鐘。所以對于問題三，我們考慮以步行8分鐘為乘客的步行時(shí)間上限。數(shù)據(jù)來源：問卷星unip.Bin 5、 問題一的解答5.1模型建立根據(jù)問題一的分析，建立以換車次數(shù)最少為第一目標(biāo)，所花時(shí)間和費(fèi)用最少分別為第二、第三目標(biāo)下的多目標(biāo)規(guī)劃模型。5.1.1確立目標(biāo)函數(shù)：目標(biāo)一：轉(zhuǎn)乘次數(shù)最少設(shè)從始發(fā)站到終點(diǎn)站總共轉(zhuǎn)乘次數(shù)為r，則轉(zhuǎn)乘次數(shù)最少的目標(biāo)函數(shù)：minY目標(biāo)二：所用總時(shí)間最短總時(shí)間包括轉(zhuǎn)乘時(shí)間和經(jīng)過站點(diǎn)所用時(shí)間，得所用時(shí)間最少的目標(biāo)函數(shù)：minT=tx+1y目標(biāo)三：所花費(fèi)用最少判斷線路/是否為分段計(jì)價(jià)：勺單一票價(jià)七一w分段計(jì)價(jià)在路線i(i<y1+1)(分段計(jì)價(jià))經(jīng)過站數(shù)為X.，則：[1(0<x<20)w.=<2(21<X<40).得出所花費(fèi)用最少的目標(biāo)函數(shù)：minW=罷+'ui=i=15.1.2確定約束條件在分段計(jì)價(jià)路線上經(jīng)過的站不超過A-B經(jīng)過的共站點(diǎn)，即:土<xii=1只考慮換乘次數(shù)不超過兩次的情況下的乘車路線，得：約<2綜上得問題一的多目標(biāo)優(yōu)化模型為：1minY<minTminW罷*1x,<x5.2模型求解：5.2.1求出換乘次數(shù)最少的可行路徑設(shè)S(A)、S(B)分別為經(jīng)過起點(diǎn)A、終點(diǎn)B的所有公汽線路的集合，即S(A)={Ali=1,2,3…a}，S(B)={BIj=1,2,3…b}設(shè)第i條線路A=；A,A，,A…A'其中A,A分別表示第i條線路的起點(diǎn)和終TOC\o"1-5"\h\zI i11213 im i1im點(diǎn)；第j條線路B=〈B「B2,B B)，其中B,B分別表示第j條線路的起點(diǎn)和終點(diǎn)。算法品下："°"" 刀"1、 若S(A)cS(B)^0，即存在i,j使A=B，表示站點(diǎn)A,B間可以通過一次乘車直接到達(dá)，線路如： ijA—a=Bj>B找出經(jīng)過站點(diǎn)最少的路線作為最優(yōu)路線。2、 若S(A)cS(B)=0，則A,B兩站點(diǎn)間沒有直達(dá)路線，需要換乘。模型只考慮換成兩次的情況：一次換乘：經(jīng)過起點(diǎn)站A的某條公汽線路與經(jīng)過終點(diǎn)B的某條公汽線有公共站點(diǎn)A(B)，得出線路如：ipjA-A->A(B)-a->B若可以一次轉(zhuǎn)乘，則計(jì)算出起始站與終點(diǎn)站間經(jīng)過站點(diǎn)最少的路線為最優(yōu)路線。二次換乘：設(shè)S(C)為S(A)中所有能轉(zhuǎn)乘車次的集合S(C)={CIr=1,2,3…c}如果S(C)cS(B)^0，即存在C=B，則找出此交集，并按順序找出這個(gè)交集中的車由哪些車次轉(zhuǎn)來，可知經(jīng)兩次轉(zhuǎn)車可達(dá)到目的站點(diǎn)。路線如下：A—r>a(C)-r>C(B)—>B計(jì)算出A,B之間所經(jīng)站點(diǎn)最少的路線作為最優(yōu)路線。5.2.2算法步驟：首先我們將文本數(shù)據(jù)按行存在一個(gè)元胞矩陣的每一行中，然后從外部輸入要查詢線路的起點(diǎn)與終點(diǎn)。查找線路時(shí)，我們先考慮能否直達(dá)，步驟如下：建立一個(gè)記錄經(jīng)過某一點(diǎn)的所用線路的函數(shù)；然后將輸入的點(diǎn)分別代到上述函數(shù)中，分別得到經(jīng)過起點(diǎn)A和終點(diǎn)B的所有線路S（A），S（B）；判斷兩者是否在S（A）=S（B）。如果存在，將A,B兩之間經(jīng)過的站點(diǎn)數(shù)n記錄下來，與初始A,B間站點(diǎn)數(shù)n0（初始值設(shè)為無窮大）比較。如果n<n0，則記錄次線路，同時(shí)將n0賦值為n；否則舍去此線路；以此循環(huán)，直到找出所有S（A）=S（B）且n最小的情況。考慮轉(zhuǎn)乘一次，步驟如下：先輸入始發(fā)站A，搜索經(jīng)過A的所有線路S（A）；然后在上述線路上分別用A之后的每個(gè)站點(diǎn)搜索經(jīng)過它的所有線路；重復(fù)直達(dá)的情況下的算法步驟。考慮轉(zhuǎn)乘兩次和上面一樣，不同的是在轉(zhuǎn)乘一次的基礎(chǔ)上增加一個(gè)搜索線路。5.2.3模型結(jié)果依照以上的算法步驟，運(yùn)用matlab編程進(jìn)行求解。在路線的選擇時(shí)，首先考慮換乘次數(shù)最少的，其次是經(jīng)過站點(diǎn)最少（所用時(shí)間最少），最后考慮的是費(fèi)用。問題一的具體結(jié)果如下：①從S3359-S1828轉(zhuǎn)乘次數(shù)最少的，經(jīng)過站點(diǎn)較少的選擇路徑，如下表1.1：轉(zhuǎn)乘次數(shù)路線經(jīng)過站點(diǎn)數(shù)所花時(shí)間（分鐘）所用費(fèi)用（元）1S3359切36（下）＞S1784li們（下）＞3359l436（下）＞S1784乙2頃下）＞S1828321013②從S1557-S0481轉(zhuǎn)乘次數(shù)最少的，經(jīng)過站點(diǎn)較少的選擇路徑，如下表1.2：轉(zhuǎn)乘次數(shù)路線經(jīng)過站點(diǎn)數(shù)所花時(shí)間（分鐘）所用費(fèi)用（元）2S1557lo8（下）＞S3389l。8（下）＞S2361—L312（下）＞S04814013032S1557 L084（下）＞S3389l157（上）＞S2361—L312（下）＞S04814013032S1557L084（下）＞S3389l河.下）＞S2361—L312（下）＞S04814013032S1557L084（下）＞S3389%3倒下）＞S2361—L312（下）＞S0481401303③從S0971-S0485轉(zhuǎn)乘次數(shù)最少的，經(jīng)過站點(diǎn)較少的選擇路徑，如下表1.3：轉(zhuǎn)乘次數(shù)路線經(jīng)過站點(diǎn)數(shù)所花時(shí)間（分鐘）所用費(fèi)用（元）

1S0971頃3（下）＞S2184切17（下）＞S0485411283④從S0008-S0073轉(zhuǎn)乘次數(shù)最少的，經(jīng)過站點(diǎn)較少的選擇路徑，如下表1.4：轉(zhuǎn)乘次數(shù)路線經(jīng)過站點(diǎn)數(shù)所花時(shí)間（分鐘）所用費(fèi)用（元）1S0008心（下）＞S2683l058下）＞S0073268321S0008L159（下）＞S0291l058（下）＞S007326832⑤從S0148-S0485轉(zhuǎn)乘次數(shù)最少的，經(jīng)過站點(diǎn)較少的選擇路徑，如下表1.5：轉(zhuǎn)乘次數(shù)路線經(jīng)過站點(diǎn)數(shù)所花時(shí)間（分鐘）所用費(fèi)用（元）2S0148L02（環(huán)）＞S0345lmo（下）＞S3037—L104（下）＞S04854013032S0148L02（環(huán)）＞S1609lm0（下）＞S3037—L104（下）＞S04854013032S0148L308（下）＞S0345%1你下）＞S3037—L104（下）＞S0485401303⑥從S0087-S3676轉(zhuǎn)乘次數(shù)最少的，經(jīng)過站點(diǎn)較少的選擇路徑，如下表1.6：轉(zhuǎn)乘次數(shù)路線經(jīng)過站點(diǎn)數(shù)所花時(shí)間（分鐘）所用費(fèi)用（元）1S0087L21（下）＞S0145L506＞S36764012535.3結(jié)果分析從以上六個(gè)表中的數(shù)據(jù)可以看出，根據(jù)模型求出的任意兩點(diǎn)之間所用時(shí)間和費(fèi)用均相等，乘車路線也無太大差異，所以以上所有路線均可供乘客選擇。6、 問題二的解答6.1模型建立將地鐵與相鄰公交站點(diǎn)抽象為同一站點(diǎn)，結(jié)合問題一，建立以轉(zhuǎn)乘次數(shù)最少為第一目標(biāo)，所用時(shí)間和費(fèi)用最少分別第二、三目標(biāo)的多目標(biāo)優(yōu)化模型。6.1.1確定目標(biāo)函數(shù)目標(biāo)一：換乘次數(shù)最少總換乘次數(shù)為兩種交通工具互轉(zhuǎn)乘次數(shù)的和，得轉(zhuǎn)乘次數(shù)最少的目標(biāo)函數(shù)：miny=miny=￡（y+y+y+y）目標(biāo)二：所花時(shí)間最少12 3 4總時(shí)間包括轉(zhuǎn)乘時(shí)間和經(jīng)過站點(diǎn)所用時(shí)間，其中乘公交所用時(shí)間T1=xt乘地鐵所用時(shí)間T2=xft，則所用總時(shí)間最少的目標(biāo)函數(shù)：minT=T+T+(yt+yt+yt+yt)1 2 11 22 33 44目標(biāo)三：所花費(fèi)用最少總費(fèi)用等于各條路線上所花費(fèi)用之和。判斷線路i是公交線還是地鐵線；若i為公交線，判斷線路i是單一票價(jià)還是分段計(jì)價(jià)'1 公交(單一票價(jià))u=\w公交(分段計(jì)價(jià))'[3i地鐵得總費(fèi)用最少的目標(biāo)函數(shù)：minW=引uii=16.1.2確定約束條件總轉(zhuǎn)乘次數(shù)少于兩次：0<Y<2(YeN)綜上得問題二多目標(biāo)模型為：minY<minT

minWS.t0<Y<2(YeN)6.2模型求解依照問題一的算法步驟，運(yùn)用matlab編程進(jìn)行求解得出題中6對起始站一終到站之間的最佳路線。7、 問題三的解答7.1模型建立：根據(jù)分析，當(dāng)步行時(shí)間在某一范圍之內(nèi)乘客時(shí)才會選擇步行。以乘客所在的站點(diǎn)為中心，以步行時(shí)間上限為半徑，找出在范圍內(nèi)的所有站點(diǎn)(鄰近點(diǎn))。同問題二，將這些點(diǎn)抽象為同一點(diǎn)，如下圖：O\'鄰近站點(diǎn)—-—-——這些站點(diǎn)之間均通過步行到達(dá)。7.1.1確定目標(biāo)函數(shù)

目標(biāo)一：換乘次數(shù)最少minY=￡(y+y+y+y)12 3 4目標(biāo)二：所花時(shí)間最短乘公交所用時(shí)間：乘地鐵所用時(shí)間:步行所花時(shí)間：乘地鐵所用時(shí)間:步行所花時(shí)間：T=xt1T=xftfT=zxfft苴中*_{1站點(diǎn)p,q間步行pq其中X=0站點(diǎn)p,q間不步行得出從始發(fā)站到終點(diǎn)站所用時(shí)間最少的目標(biāo)函數(shù)為：pqminT=T+T+T+(yt+yt+yt+yt)1 2 3 11 22 33 44目標(biāo)三：所花費(fèi)用最少同問題二，總花費(fèi)最少的目標(biāo)函數(shù)：minW=Y+1uii=17.1.2確定約束條件：從站點(diǎn)p到站點(diǎn)q所花時(shí)間不超過乘客步行時(shí)間上限:t<t〃總轉(zhuǎn)乘次數(shù)不超過兩次：0<Y<2(YeN)綜上得問題三的多目標(biāo)優(yōu)化模型：minY<minT

minW{0<Y<2s.tt<t〃pq8、 模型的評價(jià)、改進(jìn)及推廣8.1.1優(yōu)點(diǎn)：1、 模型舍棄了對問題影響不大的因素，只保留換乘次數(shù)，乘車時(shí)間，所花費(fèi)用這幾個(gè)核心目標(biāo)建立模型，使問題簡化清晰。2、 根據(jù)網(wǎng)上搜索的公交乘客出行調(diào)查表的結(jié)果確立目標(biāo)函數(shù)，使模型更貼近實(shí)際情況。3、 模型將距離較近的站點(diǎn)抽象為同一站點(diǎn)，使問題得到簡化。8.1.2缺點(diǎn)1、 在模型中我們只考慮了最多兩次轉(zhuǎn)乘就能夠到達(dá)目的地的情況。如果2次轉(zhuǎn)乘還不能到達(dá)目的地本模型將不能給出答案。2、 本模型沒有考慮到乘客在乘公交時(shí)的其他需求，如沿途觀光旅游等。8.2模型改進(jìn)1、 像觀看奧運(yùn)會這樣的大型賽事，對游客而言，更希望在乘車途中可觀賞到北京的特色景觀及建筑，如奧運(yùn)場館、名勝古跡等?；谶@些因素，我們所設(shè)計(jì)的查詢系統(tǒng)在給出常規(guī)最佳路線的同時(shí)，也應(yīng)提示一條觀光路線供乘客自由選擇。2、 題中給出的是一個(gè)靜態(tài)的交通系統(tǒng)，只要給出始發(fā)站和終點(diǎn)站，我們就可以通過算法求得可行路線。但是在現(xiàn)實(shí)生活中，交通系統(tǒng)隨時(shí)都可能在發(fā)生變化，常見的如：上下班時(shí)候的高峰期，由于交通事故某兩個(gè)站點(diǎn)之間的線路暫時(shí)中斷等，這些在本題中都沒有能夠反應(yīng)出來。所以應(yīng)考慮從實(shí)際出發(fā)，建立動態(tài)系統(tǒng)模型，可以根據(jù)最新的數(shù)據(jù)信息得出最優(yōu)方案。8.3模型推廣本文解決的是最佳路線的設(shè)計(jì)問題，結(jié)合實(shí)際情況建立優(yōu)化目標(biāo)模型。本模型不僅適用于乘車路線的選擇，還可用于觀光旅游及公交站點(diǎn)位置的選擇等。9、 參考文獻(xiàn)【1】鄧化宇李康弟黃建雄，改進(jìn)的Dijkstra矩陣算法在城市公交線路選擇中的應(yīng)用［J］，上海電力學(xué)院學(xué)報(bào)，第25卷第1期；【2】王林曹帥王歡李揚(yáng)，基于廣度優(yōu)先的城市公交出行線路選擇［J］，沈陽化工學(xué)院數(shù)理系，遼寧沈陽，110142；【3】扈震張發(fā)勇劉書良，城市公交換乘數(shù)據(jù)模型研究及算法實(shí)現(xiàn)［J］,中國地質(zhì)大學(xué)信息工程學(xué)院，湖北武漢，430074【4】百度，出行者所期望的地鐵與公交換乘步行時(shí)間和換乘候車時(shí)間問卷調(diào)查表，(/report/222042.aspx)附錄基本參數(shù)設(shè)定相鄰公汽站平均行駛時(shí)間（包括停站時(shí)間）：3分鐘相鄰地鐵站平均行駛時(shí)間（包括停站時(shí)間）：2.5分鐘公汽換乘公汽平均耗時(shí)： 5分鐘（其中步行時(shí)間2分鐘）地鐵換乘地鐵平均耗時(shí)： 4分鐘（其中步行時(shí)間2分鐘）地鐵換乘公汽平均耗時(shí)： 7分鐘（其中步行時(shí)間4分鐘）公汽換乘地鐵平均耗時(shí)： 6分鐘（其中步行時(shí)間4分鐘）公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種，標(biāo)記于線路后；其中分段計(jì)價(jià)的票價(jià)為：0?20站：1元；21?40站：2元；40站以上：3元地鐵票價(jià)：3元問題一的matlab程序%%%functionmainclear;clc;s0=input(,請輸入起點(diǎn)站\n');s1=input(,請輸入終點(diǎn)站\n');%s0='S3359';s1='S1828';n=0;a={};b1={'線路/過站數(shù)’};a1=fopen('d:/我的文檔/桌面/1.1公汽線路信息.txt');whilen<520*4+1t=fgetl(a1);n=n+1;ifischar(t)a=[a;t];endendk1=f(a,s0);k2=f(a,s1);p0=inf;%直達(dá)fori=1:size(k1,1)forj=1:size(k2,1)ifk1(i}(1)==k2(j}(1)||k1(i}(1)+1==k2(j}(1)||k1(i}(1)-1==k2(j}(1)b=[s0];p=g(a,s0,s1);m=k1(i}(1);fori1=1:4m=m-1;ifstrncmp(a{m},'L',1)b=[b,'-',a{m},'-',s1,'',p];ifall(strcmp(b,b1(size(b1,1),:)))||p>p0

b=[];elseb1=[b1;b];p0=p;endendendendendendifsize(b1,1)~=1disp(bl);break;end%轉(zhuǎn)乘一次fori=1:size(k1,1)fori1=k1{i}(2):6:size(a{k1{i}(1)},2)-4k3=f(a,a{k1{i}(1)}(i1:(i1+4)));p1=g(a,s0,a{k1{i}(1)}(i1:(i1+4)));p2=g(a,a{k1{i}(1)}(i1:(i1+4)),s1);fori2=1:size(k3,1)forj=1:size(k2,1)ifk3(i2}(1)==k2(j}(1)||k3(i2}(1)+1==k2(j}(1)||k3(i2}(1)-1==k2(j}(1)b=[s0];p=p1+p2;m1=k1(i}(1);fori3=1:4m1=m1-1;ifstrncmp(a{m1},'L',1)b=[b,'-',a{m1},'-',a{k1{i}(1)}(i1:i1+4)];endendm=k3(i2}(1);fori4=1:4m=m-1;ifstrncmp(a{m},'L',1)b=[b,'-',a{m},'-',s1,'',num2str(p)];ifall(strcmp(b,b1(size(b1,1),:)))||p>p0b=[];elseb1=[b1;b];p0=p;endendendendend

endendendendendifsize(b1,1)~=1disp(bl);break;end%轉(zhuǎn)乘兩次fori=1:size(k1,1)%確定線路fori1=k1{i}(2):6:size(a{k1{i}(1)},2)-4%確定站點(diǎn)k3=f(a,a{k1{i}(1)}(i1:(i1+4)));p1=g(a,s0,a{k1{i}(1)}(i1:(i1+4)));fori2=1:size(k3,1)%再次確定線路fori3=k3{i2}(2):6:size(a{k3{i2}(1)},2)-4%確定站點(diǎn)k4=f(a,a{k3{i2}(1)}(i3:(i3+4)));p2=g(a,a{k1{i}(1)}(i1:(i1+4)),a{k3{i2}(1)}(i3:(i3+4)));p3=g(a,a{k3{i2}(1)}(i3:(i3+4)),s1);fori4=1:size(k4,1)%確定線路forj=1:size(k2,1)%經(jīng)過終點(diǎn)站的線路ifk4(i4}⑴==k2{j}(1)||k4{i4}⑴+1==k2(j}(1)||k4(i4}(1)-1==k2(j}⑴b=[s0];p=p1+p2+p3;m1=k1(i}(1);fori5=1:4m1=m1-1;ifstrncmp(a{m1},'L',1)b=[b,'-',a{m1},'-',a{k1{i}(1)}(i1:i1+4)];endendm2=k3(i2}(1);fori6=1:4m2=m2-1;ifstrncmp(a{m2},'L',1)b=[b,'-',a{m2},'-',a{k3{i2}(1)}(i3:(i3+4))];endendm3=k4(i4}(1);fori7=1:4m3=m3-1;ifstrncmp(a{m3},'L',1)b=[b,，-，,a{m3},，-，,s1,',num2str(p)];ifall(strcmp(b,b1(size(b1,1),:)))||p>p0b=[];elseb1=[b1;b];p0=p;endendendendendendendendendenddisp(b1);%子函數(shù)，搜索經(jīng)過該點(diǎn)的線路%functionk1=f(a,n)%k1={};%fori=1:size(a,1)% k=0;% k=findstr(a{i},n);% ifk~=0% k1=[k1;[i,k]];% end%end%