公交線路選擇

1、公交線路選擇摘要本文解決的是公交線路的選擇問題，由于不同查詢者有不同的需求，故我們提出了 換乘次數(shù)、出行時(shí)間以及乘車費(fèi)用等三個(gè)指標(biāo)建立模型求解，利用多目標(biāo)規(guī)劃中的層次 算法解決了公交換乘問題，建立換乘模型，并用題中6對(duì)起始點(diǎn)加以驗(yàn)證。首先對(duì)汽車線路中環(huán)路信息和原路返回信息進(jìn)行了處理，保證各線路形式上的一 致，便于后面的計(jì)算求解。由文獻(xiàn)【4】中調(diào)查結(jié)果可知，在一般的城市公交網(wǎng)絡(luò)中人們坐公交出行，換乘次 數(shù)（可以忍受的換車次數(shù)）一般不會(huì)大于2次。對(duì)于問題一，只需考慮公汽線路，首先假設(shè)乘客最多換乘兩次并且轉(zhuǎn)乘時(shí)乘客只在 下車站點(diǎn)轉(zhuǎn)車，在上述假設(shè)的前提下，建立了換乘次數(shù)最少、時(shí)間最短、費(fèi)用最小三個(gè) 目

2、標(biāo)函數(shù)，然后利用MATLAB編程進(jìn)行搜索分別求得換乘次數(shù)最少，時(shí)間最短，費(fèi)用 最小和綜合考慮三種情況時(shí)以換乘次數(shù)最少為第一目標(biāo)、以時(shí)間最少為第二目標(biāo)、以費(fèi) 用最少為第三目標(biāo)這四種情況的最優(yōu)解.。綜合考慮三個(gè)目標(biāo)函數(shù)：先考慮換乘次數(shù)、再考慮時(shí)間最后考慮費(fèi)用求得結(jié)果如下： S3359到S1828需要換乘一次，所需要時(shí)間為101分鐘，共有兩條線路可以到達(dá)； S1557到S0481需要換乘兩次，所需時(shí)間為135分鐘，共有兩條路線可以到達(dá)； S0971到S0485需要換乘一次，所需時(shí)間為129分鐘，共有兩條路線可以到達(dá)； S0008到S0073需要換乘一次，所需時(shí)間為84分鐘，共有兩條路線可以到達(dá)； S

3、0148到S0485需要換成兩次，所需時(shí)間為192分鐘，有一條路線可以到達(dá)； S0087到S3676需要換乘一次，所需時(shí)間為66分鐘，共有一條線路可以到達(dá)；對(duì)于問題二，同時(shí)考慮公汽線路和地鐵線路，也假設(shè)最多只有兩次換乘情況，在此 假設(shè)下，確定了同問題一類似的目標(biāo)函數(shù)，在利用MATLAB搜索求解時(shí)，先考慮一次 換乘情況，按題意此時(shí)可能存在地鐵轉(zhuǎn)地鐵，地鐵轉(zhuǎn)公汽，公汽轉(zhuǎn)地鐵和公汽轉(zhuǎn)公汽這 四種情況。但仔細(xì)考慮并結(jié)合題中條件后，我們發(fā)現(xiàn)在兩次換乘時(shí)只可能存在公汽轉(zhuǎn)乘 公汽轉(zhuǎn)乘公汽、公汽轉(zhuǎn)乘地鐵轉(zhuǎn)乘公汽等情況，利用窮舉法可以求得任意兩張點(diǎn)之間滿 足不同查詢者不同需求時(shí)的最佳路線。將問題一中的6組起始站

4、和終點(diǎn)站代入即可求出 滿足不同查詢者不同需求的最佳路線。（結(jié)果見正文）。對(duì)于問題三考慮到了步行時(shí)間即可能存在乘客從一個(gè)站點(diǎn)出發(fā)步行到臨近站點(diǎn)去 轉(zhuǎn)車的情況，在此問中引入了乘客換車步行距離的最大心里承受值w，用來表示當(dāng)乘客 下車后走到其他站點(diǎn)去坐車時(shí)只要所走距離再其最大心里承受值范圍內(nèi)即可。在此前提 下，建立了與問題一類似的目標(biāo)函數(shù)，并對(duì)算法進(jìn)行了描述。關(guān)鍵詞：多目標(biāo)規(guī)劃，搜索法，最大心里承受值，層次分析1、問題重述我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn) 場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱公交，包括公汽、地鐵等） 出行。這些年來，城市的公交系

5、統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上， 使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。針對(duì)市場(chǎng)需求， 某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考 慮，滿足查詢者的各種不同需求。1、1本文需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。 并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對(duì)起始站一終到站之間的最佳路 線（要有清晰的評(píng)價(jià)說明）。（1）、S3359-S1828（2）、S1557-S0481 （3）、S0971-S0485

6、（4）、S0008-S0073（5）、S0148-S0485 （6）、S0087S36762、同時(shí)考慮公汽與地鐵線路，解決以上問題。3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請(qǐng)你給出任意兩站點(diǎn)之間線路選擇問題 的數(shù)學(xué)模型。附錄：基本參數(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à)的

7、票價(jià)為：020站：1元；2140站：2元；40站以上：3元地鐵票價(jià)：3元（無論地鐵線路間是否換乘）注：以上參數(shù)均為簡(jiǎn)化問題而作的假設(shè)，未必與實(shí)際數(shù)據(jù)完全吻合。2、模型的假設(shè)與符號(hào)說明2.1模型的假設(shè)假設(shè)一：換乘次數(shù)不能超過兩次。假設(shè)二：忽略乘客在站臺(tái)的等待時(shí)間。假設(shè)三：在單行線中，車行駛到終點(diǎn)時(shí)必須要下車。假設(shè)四：地鐵之間的換乘不需要額外買票。假設(shè)五：模型一中假設(shè)不存在從一個(gè)公汽站下車到其附近公汽站轉(zhuǎn)乘的情況。2.2符號(hào)說明i： 一次出行總的公汽乘車數(shù)；j: 一次出行總的地鐵乘車數(shù)；x :表示乘第i輛公汽所需費(fèi)用；D .:表示乘第j輛地鐵所需的費(fèi)用，且此處D . 3 .P：表示一次出行的總費(fèi)用

8、；T：表示一次出行所需總時(shí)間；m :表示一次出行乘第i輛公汽車經(jīng)過的站點(diǎn)數(shù)；n .:表示一次出行乘第j輛地鐵的經(jīng)過的站點(diǎn)數(shù)；CH :代表?yè)Q乘數(shù)；K :第t次換乘站點(diǎn)；tstart : 所查找路線的起點(diǎn)；end :所查找路線的終點(diǎn)。3、問題分析本文研究的是公交線路選擇問題，在選擇公交線路時(shí)乘客通常會(huì)考慮三方面因素： 換乘次數(shù)、乘車所需時(shí)間、乘車所需費(fèi)用。不同的顧客有不同的偏好，通過查閱南京 市做的一個(gè)公交乘客出行心理調(diào)查統(tǒng)計(jì)（結(jié)果如下圖）可知41.16%的乘客在選擇出行 路徑時(shí)首先考慮的是換乘最少，其次考慮的是時(shí)間最短。而將時(shí)間最短作為出行時(shí)考慮 的首要條件的乘客只占18.60%。綜上：我們以換

9、乘次數(shù)、乘車所需費(fèi)用和乘車所需時(shí)間為評(píng)價(jià)指標(biāo)建立模型選擇最 佳公交線路。在求解過程中本應(yīng)該為了滿足不同顧客的不同需求列出換乘次數(shù)最少，換 成時(shí)間最少，所需費(fèi)用最少和綜合考慮這三個(gè)因素時(shí)，以換乘次數(shù)最少為第一目標(biāo)、換 乘時(shí)間最少為第二目標(biāo)、換乘費(fèi)用最少為第三目標(biāo)和以換乘次數(shù)最少為第一目標(biāo)、換乘 費(fèi)用最少為第二目標(biāo)、換乘時(shí)間最少為第三目標(biāo)等情況，但為了簡(jiǎn)化計(jì)算只考慮了前四 種情況。公交出行乘客心理調(diào)查車費(fèi)最少 時(shí)間最短換車次數(shù)最少其他針對(duì)問題一：僅考慮公汽線路，要求給出任意兩站點(diǎn)之間線路選擇的數(shù)學(xué)模型。通 ?？倳?huì)存在某幾個(gè)站點(diǎn)之間不能直達(dá)而乘客又需要從不能直達(dá)的某一站點(diǎn)到另一站點(diǎn) 到另一站點(diǎn)，這時(shí)

10、就需要考慮換乘問題，但并不是每一次換乘都是一下車就可以上車， 大多數(shù)換乘都需要等待時(shí)間，通常人們都是希望換乘次數(shù)越少越好，費(fèi)用越少越好，所 用時(shí)間越短越好。故以換乘次數(shù)、乘車所需時(shí)間及乘車所需總費(fèi)用為目標(biāo)函數(shù)，建立了多目標(biāo)規(guī)劃模 型，然后利用MATLAB進(jìn)行搜索分別求出換乘次數(shù)最少，時(shí)間最短，費(fèi)用最少和綜合 考慮三種情況時(shí)以換乘次數(shù)最少為第一目標(biāo)、以時(shí)間最少為第二目標(biāo)、以費(fèi)用最少為第 三目標(biāo)這四種情況的可行路徑，并在可行路徑中搜索出最優(yōu)解。針對(duì)問題二：類似于問題一，在問題一的基礎(chǔ)上引入了公汽與地鐵，地鐵與公汽之 間的換乘。我們?cè)诖颂幰仓豢紤]小于三次換乘的情況。在地鐵換乘地鐵的時(shí)候，乘車線 路更

11、換，但費(fèi)用不變。一次換乘情況，此時(shí)可能存在地鐵轉(zhuǎn)地鐵，地鐵轉(zhuǎn)公汽，公汽轉(zhuǎn) 地鐵和公汽轉(zhuǎn)公汽這四種情況。在兩次換乘時(shí)則可能存在公汽轉(zhuǎn)公汽轉(zhuǎn)公汽、公汽轉(zhuǎn)公 汽轉(zhuǎn)地鐵等情況，利用窮舉法可以求得任意兩張點(diǎn)之間滿足不同查詢者不同需求時(shí)的最 佳路線。在計(jì)算問題一中六組起始站到終點(diǎn)站之間的路線時(shí)，通過對(duì)數(shù)據(jù)的分析發(fā)現(xiàn)在一次 換乘時(shí)前五組起始站與終點(diǎn)站之間只可能出現(xiàn)汽車轉(zhuǎn)乘汽車，而第六組則存在汽車轉(zhuǎn)乘 地鐵和汽車轉(zhuǎn)乘汽車情況。并且在汽車轉(zhuǎn)乘汽車時(shí)考慮到了同一地鐵站附近多個(gè)站點(diǎn)的 轉(zhuǎn)乘情況，即可能出現(xiàn)從某一地鐵站附近汽車站下車后到該地鐵站附近另一汽車站轉(zhuǎn)乘 情況。在兩次換乘時(shí)只存在汽車轉(zhuǎn)乘地鐵轉(zhuǎn)乘公汽情況。故此

12、簡(jiǎn)化了搜索過程求得滿足 不同查詢者不同需求的最佳路線。針對(duì)問題三：該問在前兩問的基礎(chǔ)上引入了任意兩站點(diǎn)之間的步行時(shí)間。引入步行 時(shí)間會(huì)對(duì)環(huán)形線路產(chǎn)生影響。在實(shí)際情況中，乘客為了降低行程換乘的次數(shù)和減少時(shí)間 和費(fèi)用，通常會(huì)選擇在下車的站點(diǎn)出尋找一個(gè)臨近的站點(diǎn)去換乘。但步行時(shí)間必須在一 定范圍內(nèi)，如果超過一定范圍，則要選擇別的方法，故在此問中引入了乘客換車步行距 離的最大心里承受值，即當(dāng)乘客從某一沾點(diǎn)出發(fā)到另一站點(diǎn)去乘車時(shí)，若步行距離小于 乘客換車步行距離的最大心里承受值即可接受?；谝陨戏治鲈诖藛栔薪⒘送谝粏?類似的多目標(biāo)規(guī)劃，并使用層次分析解法，分層次對(duì)尋找線路時(shí)滿足換乘次數(shù)最少，時(shí) 間最

13、短，費(fèi)用最低三種情況分別進(jìn)行線路的搜索。得到最優(yōu)的線路解。4、數(shù)據(jù)的處理4.1公汽線路信息的處理：4.1.1將公汽線路中的上下行線路換為兩條通路，將原路返回的線路如：L003：S0417-S0272-S1973-S3425-S1433-S3476-S2337-S1027-S1065-S2974-S0234-S0521-S3737-S3806-S1682-S1684-S3925-S3897-S2489-S2488處理后即可得到：41727219733425143334762337102710652974234521373738061682和2488248938973925168416823806

14、373752123429741065102723373476兩條線路。將環(huán)路信息轉(zhuǎn)換為兩條一模一樣的環(huán)路：如：L017：S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S2742-S25 33-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483-S0604- S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S0668-S30 81-S3078-S20

15、82-S0683-S2160-S3748轉(zhuǎn)換為兩條這樣的環(huán)路即可：Loop1:S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S27 42-S2533-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483- S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S06 68-S3081-S3078-S2082-S0683-S2160-S3748L

16、oop2:S3748-S2160-S0732-S3078-S2808-S2816-S3028-S1123-S3029-S2764-S2543-S27 42-S2533-S1839-S2751-S2755-S2937-S1929-S1007-S0940-S1907-S2085-S0609-S0483- S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427-S0582-S0577-S1895-S3648-S06 68-S3081-S3078-S2082-S0683-S2160-S37484.2地鐵信息的處理地鐵T1,T2中的各站點(diǎn)去掉其中的D和-然后導(dǎo)入處

17、理即可。4.3地鐵與公汽換乘信息的處理以矩陣的形式導(dǎo)入，不存在站點(diǎn)的地方取0即可5、問題一的解答5.1模型一的建立由于乘客在考慮換乘次數(shù)、乘車費(fèi)用和乘車時(shí)間三個(gè)因素時(shí)換乘次數(shù)占的比重較 高，一般情況下當(dāng)從出發(fā)點(diǎn)到終點(diǎn)所需要換乘的次數(shù)超過2時(shí)，就要考慮另外的交通工 具。實(shí)際情況中，就算是類似上海那樣城市的龐大的公交網(wǎng)中也很少有從起點(diǎn)到終點(diǎn)需 換乘公汽2次以上的。故我們?cè)谶@只考慮換乘次數(shù)小于3次的情況。由此可知i=1,2,3, 4 （i表示一次出行總的乘車數(shù)，即i-1表示換乘次數(shù)）由于公汽票價(jià)分為單一票價(jià)與分段票價(jià)兩種，由附錄中的數(shù)據(jù)可知：1 單一票價(jià)10 m 20，1 221 m 40注：m表示

18、乘坐第i個(gè)公汽時(shí)所經(jīng)過的汽車站點(diǎn)數(shù)。分以下幾種情況考慮：【1】、當(dāng)i=1時(shí)，乘客從出發(fā)點(diǎn)到目的地不需要換乘，故所需總費(fèi)用P= x 1，總時(shí)間T = 3氣【2】、當(dāng)i = 2時(shí)，乘客從出發(fā)點(diǎn)到目的地需要換乘1次，此時(shí)P= X1 + X2,總時(shí)間T = 3 m + 5 + 3 m【3】、當(dāng)i=3時(shí)乘客從出發(fā)點(diǎn)到目的地需要換乘2次，此時(shí)P = X 1 + x之+ X3,總時(shí)間T = 3 m + 5 + 3 m + 5 + 3 m【4】、當(dāng)i=4時(shí)乘客從出發(fā)點(diǎn)到目的地需要換乘3次，此時(shí)P = x 1 + x2 + x3 + x4,總時(shí)間T = 3 m + 5 + 3 m + 5 + 3 m + 5 +

19、 3 m綜上所述，得到問題一的多目標(biāo)最優(yōu)化模型為：最少換乘次數(shù)Min ii最少站數(shù)Min P = Z xkk = 1最少時(shí)間 Min T = 3Z m + 5(i - 1)k=15.2算法5.2.1換乘算法的情景描述：換乘一次、end表示終針對(duì)該問題我們考慮利用搜索算法尋找最有路徑，在此只考慮直達(dá)、 換乘兩次的情況：如下圖(其中S表示第t個(gè)站點(diǎn)，S表示第p個(gè)站點(diǎn),start表示起始站到站，乙表示第q條路線)Start(1)直達(dá)情況5.2.2換乘算法描述如下：1、輸入起點(diǎn)站start和終點(diǎn)站end2、分別搜索起始站start和終點(diǎn)站end所在的線路L1和、，將它們分別存入數(shù)組， 然后再在這兩個(gè)數(shù)

20、組中進(jìn)行搜索，判斷是否有相同的路線，若有則說明起始站和終點(diǎn)站 之間有直達(dá)路線，此時(shí)換成次數(shù)為0，然后再在所有直達(dá)路線中選出時(shí)間最少的路線即 可，若沒有相同的路線則轉(zhuǎn)入步驟3；3、 分別搜索l和L所經(jīng)過的各站點(diǎn)并比較判斷是否存在L經(jīng)過的某站點(diǎn)S與L經(jīng)q1q2q1tq2 過的某站點(diǎn)S為相同站點(diǎn)的情況，若存在則說明從起始站到終點(diǎn)站換乘一次就可以到達(dá)， 然后再將換乘一次的各個(gè)換成路線存儲(chǔ)起來，從中選出時(shí)間最短的路線，若不存在1經(jīng) 過的某站點(diǎn)S與L 2經(jīng)過的某站點(diǎn)S為相同站點(diǎn)的情況，則轉(zhuǎn)入步驟4；4、起始站所經(jīng)過的各線路記為，終點(diǎn)站經(jīng)過的各線路記為L(zhǎng)，L經(jīng)過的各站點(diǎn)記 q 1q 2q 1為S，L經(jīng)過的各

21、站點(diǎn)記為S，分別搜索S和S所經(jīng)過的各條路線找出相同路線則搜索 tq 2ptp出來的具有相同路線的兩站點(diǎn)S和S即為兩次換乘站點(diǎn)，然后在兩次換乘各路線中選出耗時(shí)最少的路線。綜合比較上述各種情況選出來的路線即為從起始站start出發(fā)到達(dá)終點(diǎn)站end。5.3問題一的求解5.3.1以考慮換成次數(shù)最少為目標(biāo)函數(shù)求得結(jié)果如下：S3359到S1828需要換乘一次，所需要時(shí)間最少為為101分鐘，共有兩條線路可以到達(dá)； S1557到S0481需要換乘兩次，所需時(shí)間最少為135分鐘，共有兩條路線可以到達(dá)； S0971到S0485需要換乘一次，所需時(shí)間最少為129分鐘，共有兩條路線可以到達(dá)； S0008到S0073需

22、要換乘一次，所需時(shí)間最少為為84分鐘，共有兩條路線可以到達(dá)； S0148到S0485需要換成兩次，所需時(shí)間最少為192分鐘，有一條路線可以到達(dá)； S0087到S3676需要換乘一次，所需時(shí)間最少為為66分鐘，共有兩條路線可以到達(dá)。具體結(jié)果見下表:起始站換乘線路中轉(zhuǎn)站換乘線路終點(diǎn)站經(jīng)過站點(diǎn) 總數(shù)時(shí)間 （min）價(jià)格（元）S3359L436S1784L217S1828341012S3359L436S1784L217S1828341012S0791L13S992L417S0485431292S0485L13S2322L417S0485441322S0008L159S2683L58S007328842

23、S0008L159S291L58S007128842S0008L159S3614L58S007128842S0008L159S491L58S007128842S0008L159S2259L58S007128842S0008L159S3315L58S007128842S0008L159S2559L463S007128842S0008L159S400L463S007128842S0008L159S2633L463S007128842S0008L159S3053L463S007128842S0008L355S2263L349S007128842S0008L355S3917L349S007128842

24、起始點(diǎn)起始線路中轉(zhuǎn)站換乘線路中轉(zhuǎn)站終點(diǎn)線路終點(diǎn) 八、經(jīng)過站點(diǎn)數(shù)時(shí) 間價(jià)格換乘次數(shù)S1557L84S1919L402S3068L72S04814513532S1557L84S1919L403S3068L72S04814513532S0148L307S128L276S791L49S04856419232S0008L355S2303L349S007128S0008L463S2083L56S0071S0087L453S0087L453S3496L209S3676S1893L209S36762822248484667222225.3.2以時(shí)間最少為目標(biāo)函數(shù)求得結(jié)果如下：S3359到S1828需要換乘兩次

25、，所需時(shí)間為最少為36分鐘，共有四條路線可以到達(dá);S1557到S0481需要換乘兩次，所需時(shí)間最少為135分鐘，共有兩條路線可以到達(dá)； S0971到S0485需要換成兩次，所需時(shí)間最少為114分鐘，共有兩條路線可以到達(dá)； S0008到S0073需要換成兩次，所需最少時(shí)間為27分鐘，共有兩條路線可以到達(dá)； S0148到S0485需要換成兩次，所需時(shí)間最少為192分鐘，有一條路線可以到達(dá)； S0087到S3676需要換乘兩次，所需時(shí)間最少為54分鐘，有兩條路線可以到達(dá)。具體結(jié)果見下表:起始點(diǎn)起始線路中轉(zhuǎn)站換乘線路中轉(zhuǎn)站終點(diǎn)線路終點(diǎn) 八、經(jīng)過站點(diǎn) 數(shù)時(shí)間費(fèi)用S3359L14S1327L200S178

26、381S182812363S3359L14S1327L201S178381S182812363S3359L122S2247L435S1784434S182812363S3359L122S2247L436S1784434S182812363S1557L84S1919L402S3068144S0481451353S1557L84S1919L403S3068144S0481451353S0971L118S2648L301S1729208S0485381143S0971L118S2648L302S1729208S0485381143S0008L259S2743L158S3315116S00739273

27、S0008L259S2743L159S3315116S00739273S0148L307S128L276S79199S0485641923S0087L28S2361L442S1159418S367618543S0087L28S2361L443S1159418S3676185435.3.3以費(fèi)用最少為目標(biāo)函數(shù)求得結(jié)果與換乘次數(shù)最少一致5.3.4綜合考慮三個(gè)目標(biāo)函數(shù)：先考慮換乘次數(shù)、再考慮時(shí)間最后考慮費(fèi)用求得結(jié)果如下：S3359到S1828需要換乘一次，所需要時(shí)間為101分鐘，共有兩條線路可以到達(dá);S1557到S0481需要換乘兩次，所需時(shí)間為135分鐘，共有兩條路線可以到達(dá);S0971到S048

28、5需要換乘一次，所需時(shí)間為129分鐘，共有兩條路線可以到達(dá);S0008到S0073需要換乘一次，所需時(shí)間為84分鐘，共有兩條路線可以到達(dá)；S0148到S0485需要換成兩次，所需時(shí)間為192分鐘，有一條路線可以到達(dá)；S0087到S3676需要換乘一次，所需時(shí)間為66分鐘，共有一條線路可以到達(dá)。6、問題二的解答6.1模型的建立對(duì)于該問題，我們建立多目標(biāo)規(guī)劃模型，并使用分層次求解。在該問題中，需要考 慮公汽與地鐵線路之間的混合路線。在這我們?nèi)匀豢紤]在乘客選擇時(shí)從換乘次數(shù)，乘車 時(shí)間，乘車費(fèi)用三個(gè)因素去分析，建立目標(biāo)表達(dá)式。由于之前已經(jīng)分析到，在乘客選擇 線路的心理調(diào)查中換乘次數(shù)的比重占的較多，因此

29、我們把換乘次數(shù)作為首選目標(biāo)。6.1.1目標(biāo)一：換乘次數(shù)的考慮我們已經(jīng)定義i表示乘車過程中乘坐總的乘公汽次數(shù)。j表示總的乘坐地鐵的次數(shù)，根據(jù)假設(shè)有 i+ j 3，則此處換乘的次數(shù)CH= i + j - 1。則最小換乘次數(shù)為：CH = min i+j-16.1.2目標(biāo)二：對(duì)乘車時(shí)間的考慮：通過分析，我們使用窮舉法對(duì)不同的換乘次數(shù)的情況考慮，首先考慮直達(dá)的情況，在該情況下：總的時(shí)間為：3x m 乘坐公汽2.5 xn 乘坐地鐵【1】當(dāng)換乘次數(shù)CH = 1時(shí)，此時(shí)有公汽與地鐵之間的換乘情況有四種:公汽換乘公汽，公汽換 乘地鐵，地鐵換乘地鐵，地鐵換乘公汽在該情況中總的行駛時(shí)間為：T = 3 x m + 3

30、 x m + 5【2】當(dāng)換乘次數(shù)CH = 2時(shí)，針對(duì)公汽和地鐵的同時(shí)換乘，總共有A 2 = 6，其中包括公3汽換乘地鐵換乘公汽，公汽換乘地鐵換乘地鐵等在該換乘情況下，總的使用時(shí)間為：T = 3 x m + 6 + 2.5 x n + 7 + 3 x m綜合考慮，總的時(shí)間的目標(biāo)表達(dá)式為：12T = min &xm +Z 2.5 x n +Z t）其中t .為第i+j次換乘的平均耗時(shí)，且4 地鐵換乘地鐵；5 公汽換乘公汽； t = i +頂6 公汽換乘公汽；、7地鐵換乘公汽；在該換乘情況下，必須滿足i + j 3，即總的換乘次數(shù)不能超過三，如果超過則要考慮別的 交通工具。6.1.3目標(biāo)三：對(duì)乘車費(fèi)

31、用的考慮在針對(duì)乘車費(fèi)用而考慮線路的選擇時(shí)，前提條件也是總的換乘次數(shù)不能超過三次，我們 同樣適用窮舉法，最后得到總的費(fèi)用為：P = min Z m +Z D 同樣，i + j 3。綜上所述：我們的到多目標(biāo)規(guī)劃的目標(biāo)函數(shù)為：min CH ;m i 1T;min P ;其中i + j 3。6.2換乘算法的描述：此問中我們也假設(shè)最多出現(xiàn)最多出現(xiàn)兩次換成情況，經(jīng)分析發(fā)現(xiàn)起始6組起始站點(diǎn)都 不在在地鐵站附近，故不可能出現(xiàn)從地鐵站出發(fā)的情況，同理對(duì)終點(diǎn)站進(jìn)行分析發(fā)現(xiàn)只 有最后一組即S3676在D36地鐵站附近，故只有最后一組可能出現(xiàn)通過乘坐地鐵到達(dá)目 的地的情況。根據(jù)以上分析采取如下算法：1、先考慮一次換乘

32、情況，對(duì)于前面五組起始站到終點(diǎn)站只存在公車轉(zhuǎn)公車的情況，但 對(duì)于最后一組則存在公車轉(zhuǎn)汽車和公車轉(zhuǎn)地鐵兩種情況。先考慮公車轉(zhuǎn)公車情況，利用搜索法先搜索出含有起始站的各路線乙,然后再搜索乙路線上在地鐵站 d I附近的站點(diǎn) s ，則乘客可以在此站點(diǎn)下車，接著再搜索出含終點(diǎn)站的各路線 . I，再搜索在.路線上且在地鐵站 D I （注：從終點(diǎn)站出發(fā)搜索的地鐵 站與從起始點(diǎn)出發(fā)搜索的地鐵站相同）附近的站點(diǎn)，則乘客可以從此站點(diǎn)上車，由 此可以搜索出汽車換乘汽車的路線，然后再在搜索出的路線中進(jìn)行篩選。2、對(duì)于最后一組的汽車換乘地鐵情況，首先同上述1步中一樣先搜索出含有起始站的各路線 L ，然后再搜索 L 路線

33、上在地鐵站q 附近的站點(diǎn) s , iiii并且要求地鐵站q在T2路線上并且在D36之前，由此即可以搜索出S0087到S3676汽車轉(zhuǎn)乘地鐵的路線然后再利用時(shí)間和費(fèi)用進(jìn)行篩選即可得到最優(yōu)路線。3、考慮到二次換乘情況只有可能是汽車換乘地鐵再換乘汽車這種情況，同一次轉(zhuǎn)乘中 汽車轉(zhuǎn)乘汽車類似，不同的是從終點(diǎn)站出發(fā)搜索的地鐵站與從起始站出發(fā)搜索的地 鐵站不需要相同。同樣也是從終點(diǎn)站和起始站兩方向同時(shí)考慮：利用搜索法先搜索 出含有起始站的各路線乙,然后再搜索乙路線上在地鐵站 q 附近的站點(diǎn)s ,則乘客可以在此站點(diǎn)下車，接著再搜索出含終點(diǎn)站的各路線 . ，再搜索在l 路線上且在地鐵站q （注q與q在同一地鐵

34、線路t上）附近的站點(diǎn)s， jji jkj則乘客可以在q上地鐵q下地鐵，然后再在公汽站S上車即可到達(dá)目的地，由此可以 搜索出汽車換乘地鐵換乘汽車的路線，然后再在搜索出的路線中進(jìn)行篩選。6.3問題二的求解6.3.1以換乘次數(shù)最少為目標(biāo)函數(shù)求得結(jié)果如下：S3359到S1828需要轉(zhuǎn)乘兩次，時(shí)間最短為64分鐘，最短時(shí)間下的路徑有一條；S1557到S0481需要轉(zhuǎn)乘兩次，時(shí)間最短為112分鐘，最短時(shí)間下的路徑只有一條；S0971到S0485需要轉(zhuǎn)乘兩次，時(shí)間最短為89分鐘，最短時(shí)間下的路徑有十條；S0008到S0073需要轉(zhuǎn)乘一次，時(shí)間最短為81分鐘，最短時(shí)間下的路徑有一條；S0148到S0483需要轉(zhuǎn)

35、成兩次，時(shí)間最短為83分鐘，最短時(shí)間下的路徑有五條；S0087到S3676需要轉(zhuǎn)成一次，時(shí)間最短為23.5分鐘，最短時(shí)間下的路徑有一條。具體結(jié)果如下表：公汽換地鐵換公汽起點(diǎn)起始路線第一次下 車站點(diǎn)第二次上車站點(diǎn)八、轉(zhuǎn)乘線路第二次下車站 點(diǎn)八、第三次上工汽 點(diǎn)八、終止線路終點(diǎn) ”、八、時(shí) 間S3359L473S856D28T2D34S578L167S182864S1557L84S978D32T2D24S537L5S0481112S0971L93S567D1T1D21S466L50S048589S0971L93S567D1T1D21S464L103S048589S0971L93S567D1T1D2

36、1S464L395S048589S0971L93S567D1T1D21S466L450S048589公汽換公汽:起點(diǎn)起始路 線第一次下車站 點(diǎn)八、第二次上車 站點(diǎn)終止路線終點(diǎn) 八、站點(diǎn)數(shù)時(shí) 間S0008L159S4002633947S00732781公汽換地鐵：起始第一次下車轉(zhuǎn)乘地鐵換乘線起點(diǎn)路線站點(diǎn)站點(diǎn)路終點(diǎn)”、八、時(shí)間S0087L20S630D29T2S367623.5S0971 L93S567 D1 T1 D21S464L469 S0485 89S0971 L119S567 D1 T1 D21S466L50 S0485 89S0971 L119S567 D1 T1 D21S464L103

37、 S0485 89S0971 L119S567 D1 T1D21S464L395 S0485 89S0971 L119S567D1 T1D21S466L450 S0485 89S0971 L119S567D1 T1D21S464L469 S0485 896.3.2以時(shí)間最少為目標(biāo)函數(shù)求得結(jié)果如下：S3359 到 S1828,S1557 到 S0481, S0971 到 S0485, S0148 到 S0483 與 S0087 到 S3676 與以換乘次數(shù)為目標(biāo)結(jié)果相同。S0008到S0073需換乘兩次，時(shí)間最短為76分鐘，最短時(shí)間下的路徑有兩條。6.3.3以費(fèi)用最少為目標(biāo)函數(shù)求得結(jié)果與以換乘次

38、數(shù)為目標(biāo)結(jié)果相同。6.3.4綜合考慮以上三個(gè)目標(biāo)函數(shù)，先考慮換乘次數(shù)在考慮時(shí)間最后考慮費(fèi)用求得結(jié)果 與以換乘次數(shù)為目標(biāo)求得結(jié)果相同。7、問題三的求解7.1模型的建立在該問中，假設(shè)已經(jīng)知道任意兩站點(diǎn)之間的步行時(shí)間。在實(shí)際情況中，當(dāng)某個(gè)乘客 從某個(gè)站點(diǎn)出發(fā)時(shí)，并不是就是在下車的那個(gè)站點(diǎn)換車而是先步行一段路程后，在下車 站點(diǎn)的臨近站點(diǎn)去換車。這樣就增加了乘客選擇路線的方案。而且會(huì)減少換乘的次數(shù)， 當(dāng)然步行到附近的站點(diǎn)要看緊臨站點(diǎn)的分布情況。同時(shí)我們考慮到乘客在換乘時(shí)的步行 距離不可能走很遠(yuǎn)，在此處我們定義巧為乘客換車步行距離的最大心里承受值。同上述問題，我們同樣對(duì)該問題建立多目標(biāo)分層求解的問題規(guī)劃：

39、假設(shè)任意兩站點(diǎn)之間s，s的步行行走時(shí)間為T，整個(gè)過程公汽經(jīng)過的總的站點(diǎn)ij數(shù)為m，地鐵經(jīng)過的總的站點(diǎn)數(shù)為n。其中m為第i次公汽換乘經(jīng)過的站點(diǎn)數(shù)，n為第i次換乘地鐵的站點(diǎn)數(shù)。DG為地鐵換乘公汽的次數(shù)，GD為公汽換乘地鐵的次數(shù)， GG為公汽換乘公汽的次數(shù)，DD為地鐵換乘地鐵的次數(shù)?？紤]到在整個(gè)路線選擇過程 中，換乘次數(shù)的影響占的比重較大，所以對(duì)換乘次數(shù)的考慮應(yīng)放在第一位.目標(biāo)一：對(duì)換乘次數(shù)的考慮：總的換乘次數(shù)為：min CH = GD + DG + GG + DD且必須滿足：GD + DG + GG + DD 3。目標(biāo)二：對(duì)乘車時(shí)間的考慮：總的乘車時(shí)間為：min T = (2 3 x m + 2

40、2.5 x n + 5 x GG + 4 x DD + 7 x DG + 6 x GD + E T 由于考慮到乘客步行時(shí)間要滿足要滿足換乘步行距離的最大心理承受度，假設(shè)d(s ,s )表示任意兩個(gè)站點(diǎn)之間的步行距離，即此處必須要滿足d (s , s ) “。我們以 i ji jT .表示任意兩站點(diǎn)的步行時(shí)間，為了和實(shí)際情況相符合，我們定義T e0,10 。即步 行時(shí)間在10分鐘之內(nèi)。在對(duì)時(shí)間的考慮的同時(shí)，也需要滿足對(duì)換乘次數(shù)的考慮，即也 必須滿足GD + DG + GG + DD 1；20D =3,考慮到地鐵費(fèi)用時(shí)，有一種情況就是當(dāng)?shù)罔F換乘地鐵時(shí)，不需要額外買票。 i總的乘車費(fèi)用為：min P

41、= 2 X +2 D 綜上所述，總的目標(biāo)為:min CH;min T;min P;7.2模型的求解在基于上述關(guān)于換乘次數(shù)，時(shí)間，費(fèi)用的基礎(chǔ)上我們得到路線的選擇方案為：輸入起始點(diǎn)start和終點(diǎn)end;(直達(dá)的情況)判斷起點(diǎn)和終點(diǎn)是否在同一條線路上，如果在則說明線路尋找 成功。如果沒有，則轉(zhuǎn)入下一步；(換乘一次的情況)尋找包含起始站點(diǎn)的線路集e(/)和包含終止站點(diǎn)的線路集 上的相同站點(diǎn)，如果有，則尋找成功，如果沒有，則轉(zhuǎn)入下一步；假設(shè)尋找得到包含起點(diǎn)start的線路集合e(I)和包含終止站點(diǎn)的線路集合s(J)， 在所有線路上的某一個(gè)站點(diǎn)E (I, U )處附近找一緊臨的點(diǎn)V，并且滿足d (U ,

42、 V) w， 如果V e s (J)，則尋找成功，如果不滿足，轉(zhuǎn)入下一步；尋找滿足d (U , V ) w的點(diǎn)V的所有線路集R (K)，在R (K)上找一點(diǎn)K，如果滿 足K e S (J)，則K就是第二次換乘點(diǎn)。如果不滿足，則轉(zhuǎn)入下一步；在K點(diǎn)附近找一緊臨的站點(diǎn)L，并且滿足d(K, L) W，并找出站點(diǎn)L上所有的 線路集合L(r)，在L(r)上尋找一點(diǎn)Q，如果Q e S (J)，則尋找成功，如果沒有，則 跳出，查找失敗。8、模型的優(yōu)缺點(diǎn)8.1模型的優(yōu)點(diǎn)：1、在問題求解過程中綜合考慮了不同顧客的不同需求2、在問題二求解過程中計(jì)算汽車轉(zhuǎn)乘汽車時(shí)，考慮了地鐵站附近多個(gè)汽車站點(diǎn)的轉(zhuǎn) 乘情況3、求解結(jié)果

43、比較準(zhǔn)確8.2模型的缺點(diǎn)：1、問題一算法時(shí)間復(fù)雜度較高，在數(shù)據(jù)很多的情況下不利于計(jì)算2、在問題一和問題二中都只考慮了兩次換乘情況3、在模型建立時(shí)，沒有綜合考慮對(duì)不同查詢者的三種情況所占比重要求不同情況下 的線路查詢。比如，某些個(gè)別查詢者可能要求以費(fèi)用最小為最重要目標(biāo)，但同時(shí)也 要竟可能滿足換乘次數(shù)最少和費(fèi)用最低的情況。9、模型的改進(jìn)1、在求解過程中用該將滿足不同查詢者不同需求的各種情況都列舉出來并進(jìn)行求解便 于乘客進(jìn)行查詢。2、還可以根據(jù)通過調(diào)查判斷哪些站點(diǎn)離比較受顧客歡迎的地方較近可以考慮在這些站 點(diǎn)顧客比較愿意在這些站點(diǎn)下車并且此時(shí)顧客換乘的最大心里承受值是比較大的也 即顧客在這些站點(diǎn)下車

44、愿意走較長(zhǎng)的路徑到換乘站點(diǎn)。10、參考文獻(xiàn)【1】薛定宇、陳陽(yáng)泉等著，高等應(yīng)用數(shù)學(xué)問題的MATLAB求解，清華大學(xué)出版社【2】彭祖贈(zèng)等主編，數(shù)學(xué)模型與建模算法，大連海事大學(xué)出版社【3】王莉、李文權(quán)，公共交通系統(tǒng)最佳路徑算法，東南大學(xué)學(xué)報(bào)，第34卷，第3期， 2004年3月【4】王健林，基于換乘次數(shù)最小的城市公交網(wǎng)絡(luò)最優(yōu)化算法，經(jīng)濟(jì)地理，第25卷第5 期，2005年9月11、附錄附錄一：數(shù)據(jù)處理源代碼：clear;clc;fid=fopen(a.txt,rt);b=fscanf(fid,%s);n=size(b,2);i=1;l=0;while(i=n)if (b(i)= L)l=l+1;i=i+

45、4;if (b(i)= ,O)c(l)=0;i=i+5;elseif (b(i)=p)c(l)=1;i=i+7;endw=1;n1(1,l)=1;if (b(i)= El)i=i+3;elseif (b(i)=)i=i+3;h(l)=l;y(l)=0;elsey(l)=l;h(l)=0;endwhile(b(i)=L)for j=1:4;a(j)=eval(b(i + 1);i=i+1;ends(w,n1(w,l),l)=a(1)*1000+a(2)*100+a(3)*10+a(4);i=i+1;if(b(i)= -)n1(w,l)=n1(w,l)+1;i=i+1;elseif (b(i)=I

46、A)w=2;i=i+3;n1(w,l)=1;elseif (b(i)=E)break;elseif(w=1)if(h(l)=0)for k=1:n1(w,l)s(2,k,l)=s(1,k,l);endelsefor k=1:n1(w,l)n1(2,l)=n1(1,l);s(2,k,l)=s(1,n1(w,l)-k+1,l);endendendendelsei=i+1;end end y(l)=0;h(l)=0;t=1;m=1;for i=1:lfor j=1:2if(j=1)x(t,1)=i;if (c(i)=0)c1(t)=2;elsec1(t)=1;endif (y(i)=0)l1(t)=

47、3;elseif (h(i)=0)l1(t)=2;elsel1(t)=1;endelsec1(t)=0;l1(t)=0;endx(t,2:87)=s(j,1:86,i);n2(t)=n1(j,i);t=t+1;endendfor i=1:2*lfor j=1:87if(x(i,j)=0)x(i,j)=inf;endendendc1=c1;l1=l1;n2=n2;附錄二：?jiǎn)栴}一源代碼：判斷是否存在地鐵線為起始路線或地鐵線為終止路線的情況:Function K(start1,end1)a=data(1:1040,:);k=1;t=1;for i=1:1040for j=1:86if a(i,j)=

48、start1b1(k)=i;b2(k)=j;k=k+1;else if a(i,j)=end1c1(t)=i;c2(t)=j;t=t+1;endendendendq=1;for i=1:k-1for j=1:t-1n1=b1(i);n2=c1(j);n3=b2(i);n4=c2(j);for r=1:86for p=1:86if a(n1,r)=0&a(n2,p)=0if a(n1,r)=a(n2,p)&n3p d1(q)=a(n1,r);d2(q)=n1;d3(q)=n2;d4(q)=r-n3+1+n4-p+1;q=q+1;endendendendendendfunction A(start

49、1,end1)a=data(1:1040,:);k=1;t=1;for i=1:1040for j=1:86if a(i,j)=start1b1(k)=i;b2(k)=j;k=k+1;else if a(i,j)=end1c1(t)=i;c2(t)=j;t=t+1;endendendendm=1;for i=1:k-1for j=1:t-1if b1(i)=c1(j)c3(m)=b1(i);m=m+1;endendendq=1;for i=1:k-1for j=1:t-1n1=b1(i);n2=c1(j);n3=b2(i);n4=c2(j);for r=1:86for p=1:86if a(n

50、1,r)=0&a(n2,p)=0if a(n1,r)=a(n2,p)&n3p d1(q)=a(n1,r);d2(q)=n1;d3(q)=n2;d4(q)=r-n3+1+n4-p+1;q=q+1;endendendendendq1 = 1;for i=1:k-1n3=b1(i);n5=b2(i);for j=1:86for p1=1:1040for p2=1:86if p1=iif a(n3,j)=0&a(p1,p2)=0if a(n3,j)=a(p1,p2)&jn5 e1(q1)=a(p1,p2); e2(q1)=p1; e3(q1)=n3; e7(q1)=j-n5+1; q1=q1+1;endendendendendendendq2 = 1;for i1=1:t-1n4=c1(i1);n6=c2(i1);for j1=1:86for p3=1:1040for p4=1:86if p3=i1if a(n4,j1)=0&a(p3,p4)=0&j1i2f1(q3)=e2(i2);f2(q3)=e1(i2);f