優(yōu)秀論文公交線路優(yōu)化選擇模型及算法肖華勇指導(dǎo)_1709321838

1、<p>　　蚃袁芆蒀蕿袀莈蚅袈衿肈蒈襖袈芀螄螀袇莂薆蚆袆蒅荿羄裊膄薅袀裊芇莈螆羄荿薃螞羃聿莆薈羂膁薁羇羈莃莄袃羀蒆蝕蝿罿膅蒂蚅罿羋蚈薁羈莀蒁衿肇肀蚆螅肆膂葿蟻肅芄蚅薇肄蒆蕆羆肅膆莀袂肅羋薆螈肂莁莈蚄肁肀薄薀膀膃莇衿腿芅薂螅膈莇蒞螁膈膇蟻蚇膇艿蒃羅膆莂蠆袁膅蒄蒂螇膄膄蚇蚃袁芆蒀蕿袀莈蚅袈衿肈蒈襖袈芀螄螀袇莂薆蚆袆蒅荿羄裊膄薅袀裊芇莈螆羄荿薃螞羃聿莆薈羂膁薁羇羈莃莄袃羀蒆蝕蝿罿膅蒂蚅罿羋蚈薁羈莀蒁衿肇肀蚆螅肆膂葿蟻肅芄蚅薇肄蒆蕆羆

2、肅膆莀袂肅羋薆螈肂莁莈蚄肁肀薄薀膀膃莇衿腿芅薂螅膈莇蒞螁膈膇蟻蚇膇艿蒃羅膆莂蠆袁膅蒄蒂螇膄膄蚇蚃袁芆蒀蕿袀莈蚅袈衿肈蒈襖袈芀螄螀袇莂薆蚆袆蒅荿羄裊膄薅袀裊芇莈螆羄荿薃螞羃聿莆薈羂膁薁羇羈莃莄袃羀蒆蝕蝿罿膅蒂蚅罿羋蚈薁羈莀蒁衿肇肀蚆螅肆膂葿蟻肅芄蚅薇肄蒆蕆羆肅膆莀袂肅羋薆螈肂莁莈蚄肁肀薄薀膀膃莇衿腿芅薂螅膈莇蒞螁膈膇蟻蚇膇艿蒃羅膆莂蠆袁膅蒄蒂螇膄膄蚇蚃袁芆蒀蕿袀莈蚅袈衿肈蒈襖袈芀螄螀袇莂薆蚆袆蒅荿羄裊膄薅袀裊芇莈螆羄荿薃螞羃聿莆薈羂膁薁羇

3、羈莃莄袃羀蒆蝕蝿罿膅蒂蚅罿羋蚈薁羈莀蒁衿肇肀蚆螅肆膂葿蟻肅芄蚅薇肄蒆蕆羆肅膆莀袂肅羋薆螈肂莁莈蚄肁肀薄薀膀膃莇衿腿芅薂螅膈莇蒞螁膈膇蟻蚇膇艿蒃</p><p>　　芁蚈肀膁蕿蚇螀羄蒅螆袂腿莁螅羄羂芇螄蚄膇芃螄袆肀薂螃羈芆蒈螂肁聿莄螁螀芄芀螀袃肇蕿衿羅節(jié)蒅袈肇肅莁袈螇芁莇蒄罿膃芃蒃肂荿薁蒂螁膂蕆蒂襖莇莃蒁羆膀艿薀肈羃薈蕿螈膈蒄薈羀羈蒀薇肂芇莆薆螂聿節(jié)薆襖芅薀薅羇肈蒆薄聿芃莂蚃蝿肆羋螞袁芁膄蟻肅肄薃蝕螃莀葿蝕裊膃蒞蠆

4、羈莈芁蚈肀膁蕿蚇螀羄蒅螆袂腿莁螅羄羂芇螄蚄膇芃螄袆肀薂螃羈芆蒈螂肁聿莄螁螀芄芀螀袃肇蕿衿羅節(jié)蒅袈肇肅莁袈螇芁莇蒄罿膃芃蒃肂荿薁蒂螁膂蕆蒂襖莇莃蒁羆膀艿薀肈羃薈蕿螈膈蒄薈羀羈蒀薇肂芇莆薆螂聿節(jié)薆襖芅薀薅羇肈蒆薄聿芃莂蚃蝿肆羋螞袁芁膄蟻肅肄薃蝕螃莀葿蝕裊膃蒞蠆羈莈芁蚈肀膁蕿蚇螀羄蒅螆袂腿莁螅羄羂芇螄蚄膇芃螄袆肀薂螃羈芆蒈螂肁聿莄螁螀芄芀螀袃肇蕿衿羅節(jié)蒅袈肇肅莁袈螇芁莇蒄罿膃芃蒃肂荿薁蒂螁膂蕆蒂襖莇莃蒁羆膀艿薀肈羃薈蕿螈膈蒄薈羀羈蒀薇肂芇莆薆

5、螂聿節(jié)薆襖芅薀薅羇肈蒆薄聿芃莂蚃蝿肆羋螞袁芁膄蟻肅肄薃蝕螃莀葿蝕裊膃蒞蠆羈莈芁蚈肀膁蕿蚇螀羄蒅螆袂腿莁螅羄羂芇螄蚄膇芃螄袆肀薂螃羈芆蒈螂肁聿莄螁螀芄芀螀袃肇蕿衿羅節(jié)蒅袈肇肅莁袈螇芁莇蒄罿膃芃蒃肂荿薁蒂螁膂蕆蒂襖莇莃蒁羆膀艿薀肈羃薈蕿螈膈蒄薈羀羈蒀薇肂芇莆薆螂聿節(jié)薆襖芅薀薅羇肈蒆薄聿芃莂蚃蝿肆羋螞袁芁膄蟻肅肄</p><p>　　公交線路優(yōu)化選擇模型及算法</p><p><b>

6、　　朱英，趙曉凱，王林</b></p><p><b>　　指導(dǎo)教師：肖華勇</b></p><p><b>　　摘要</b></p><p>　　本文主要是針對兩公汽站點(diǎn)之間的最佳公交路線選擇問題而建立模型，對于給定的三種不同的具體情況，我們建立了以總換乘次數(shù)最少，乘車所消耗總時(shí)間最短以及乘車費(fèi)用最少的多目標(biāo)

7、規(guī)劃模型。為建模方便，我們首先設(shè)定由起始站到終到站所經(jīng)過的站點(diǎn)序列，并構(gòu)建了各個(gè)站點(diǎn)換乘情況的0-1決策變量，將所有站點(diǎn)的換乘情況進(jìn)行疊加得到總換乘次數(shù)。乘車所消耗的總時(shí)間和總乘車費(fèi)用，在不同情況下計(jì)算方式不同。</p><p>　　問題一只考慮公汽。由從起點(diǎn)到終點(diǎn)經(jīng)過的站點(diǎn)數(shù)目和換乘次數(shù)可得到總消耗時(shí)間，同時(shí)引入計(jì)價(jià)因子表示公汽計(jì)價(jià)方式計(jì)算乘車費(fèi)用。我們在5.1.5中設(shè)計(jì)了適當(dāng)?shù)乃惴ú⒂肰isual C++編程

8、計(jì)算，得到各個(gè)目標(biāo)值如下：</p><p>　　按照起始站→終到站, 換乘次數(shù), 總時(shí)間, 總票價(jià)的順序?yàn)镾3359→S1828, 1, 101, 3；S1557→S0481, 2, 106, 3；S0971→S0485, 1, 128, 3；S0008→S0073, 1, 83, 2；S0148→S0485, 2, 106, 3；S0087→S3676, 1, 65, 2；</p><p&g

9、t;　　詳細(xì)結(jié)果及分析見5.1.6和附錄1；同時(shí)我們還在5.1.7和5.1.8中討論了適當(dāng)增加換乘次數(shù)對乘車時(shí)間和費(fèi)用的影響。</p><p>　　問題二同時(shí)考慮加入地鐵的情況。我們假定只有公汽換乘地鐵和地鐵換乘公汽兩種情況。乘地鐵消耗的時(shí)間類似乘公汽消耗時(shí)間可計(jì)算得出；因換乘消耗的時(shí)間與初始的交通方式相關(guān)，我們引入了起點(diǎn)乘車方式因子。總乘車費(fèi)用類似問題一的情況可得。利用Visual C++編程計(jì)算，我們得到此時(shí)

10、各目標(biāo)值如下：</p><p>　　起始站→終到站, 換乘次數(shù), 總時(shí)間, 總票價(jià), S3359→S1828, 2, 101, 5；S1557→S0481, 2, 117, 5；S0971→S0485, 2, 96, 5, 13, 20；S0008→S0073, 2, 65.5, 5；S0148→S0485, 2, 87.5, 5；S0087→S3676, 0, 33, 3；</p><p&g

11、t;　　詳細(xì)結(jié)果及分析見5.2.6。</p><p>　　問題三中我們基于問題二中所建立的模型，引入了步行因子，其在乘車所消耗總時(shí)間最短以及乘車費(fèi)用最少兩個(gè)目標(biāo)中都得到了體現(xiàn)，得到了任意兩站之間選擇路線的模型，見5.3.5中式（35），（36）。</p><p>　　此外，我們還對模型進(jìn)行了評價(jià)和推廣。</p><p>　　關(guān)鍵字：多目標(biāo)規(guī)劃模型，換乘點(diǎn)，計(jì)價(jià)因子，

12、起點(diǎn)乘車方式因子，步行因子</p><p><b>　　問題重述</b></p><p>　　我國人民翹首企盼的第29屆奧運(yùn)會明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場觀看奧運(yùn)比賽，其中大部分人將會乘坐公共交通工具（簡稱公交，包括公汽、地鐵等）出行。這些年來，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線

13、路的選擇問題。針對市場需求，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。</p><p>　　為了設(shè)計(jì)這樣一個(gè)系統(tǒng)，其核心是線路選擇的模型與算法，應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。請你們解決如下問題：</p><p>　　1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用你們的模型與算法，求出以下6對起始站→

14、終到站之間的最佳路線（要有清晰的評價(jià)說明）。</p><p>　　(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485</p><p>　　(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676</p><p>　　2、同時(shí)考慮公汽與地鐵線路，解決以上問題。<

15、/p><p>　　3、假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間，請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。</p><p><b>　　問題分析</b></p><p>　　隨著2008年北京奧運(yùn)會的來臨，北京的公共交通系統(tǒng)有了飛速的發(fā)展。目前北京有公交線路800條以上。這使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問題。</p>

16、;<p>　　題目中給出了6對起始站與終點(diǎn)站，要求我們求出由這些起始站到終點(diǎn)站的最佳路線。如何理解“最佳路線”體現(xiàn)乘車者不同的出發(fā)點(diǎn)，也是我們解決問題的前提?，F(xiàn)有對于選擇出行最佳路徑的模型多為基于“出行距離最短”或“出行時(shí)耗最少”的最短路模型。而對于公交乘客而言，更多的乘客以“換乘次數(shù)最少”為首要著眼點(diǎn)，“出行距離最短”為第二目標(biāo)[2]。因此，現(xiàn)在的問題是如何在現(xiàn)有的公交網(wǎng)絡(luò)上尋找一條換乘次數(shù)最少、距離最短的線路。目前采用

17、的常用方法是將公交路徑的最短路徑理解成廣義費(fèi)用的最小來考慮。在這里，我們認(rèn)為應(yīng)該考慮換乘次數(shù)盡量少，乘車時(shí)間盡量少和車費(fèi)最少這三個(gè)目標(biāo)。具體討論如下：</p><p>　　汽車換乘會給乘客帶來極大的不便：一方面，北京市的車流輛非常大，在高峰期很容易出現(xiàn)堵車的情況，所以乘客等車的時(shí)間可能遠(yuǎn)大于平均等候時(shí)間5分鐘；另一方面，還可能出現(xiàn)公交車裝載過于飽和的狀況，這時(shí)乘客只能選擇等候下一輛，這也有可能造成等候時(shí)間過長。因

18、此，我們把換乘次數(shù)作為第一目標(biāo)。</p><p>　　人們在出行的時(shí)候，不會希望自己的大部分時(shí)間耽誤在公交車上。因此，乘車過程消耗的時(shí)間也是重要的目標(biāo)。對于不同的方案，這個(gè)時(shí)間的構(gòu)成不盡相同，具體如下：</p><p>　　當(dāng)只考慮公共汽車線路的時(shí)候，即在乘客進(jìn)行換乘的時(shí)候直接在前一輛車的下車站換乘車輛，這時(shí)乘客在由起始站到終點(diǎn)站的過程中花去的總時(shí)間由公汽的行進(jìn)時(shí)間和換乘所花去的時(shí)間兩部分

19、組成。公汽的行進(jìn)時(shí)間由從起點(diǎn)站到終點(diǎn)站所停的站點(diǎn)數(shù)量立即可得，乘客在換乘中花去的時(shí)間可根據(jù)假設(shè)由換乘次數(shù)易得。這樣我們就可以得到公汽換乘公汽時(shí)乘客從起始站到終點(diǎn)站所需要花去的時(shí)間。</p><p>　　當(dāng)同時(shí)考慮公汽與地鐵線路，這里乘客在由起始站到終點(diǎn)站所花去的總時(shí)間就要看成由兩大部分組成，即乘車的時(shí)間和換乘的時(shí)間。乘車的時(shí)間由公汽的行進(jìn)總時(shí)間和地鐵的行進(jìn)總時(shí)間兩部分組成，前面已經(jīng)討論過公汽的總行進(jìn)時(shí)間，這里地鐵

20、的總行進(jìn)時(shí)間可以類似得到。而換乘的時(shí)間較為復(fù)雜，包括了公汽換乘公汽，地鐵換乘地鐵，公汽換乘地鐵以及地鐵換乘地鐵四個(gè)部分，各個(gè)部分可以很類似得到，和前面討論的公汽換乘公汽的計(jì)算方法類似。</p><p>　　由上我們可分別得到在只考慮公汽和同時(shí)考慮公汽和地鐵時(shí)乘客由起始站到終點(diǎn)站所消耗的總時(shí)間，這是第二個(gè)目標(biāo)。</p><p>　　另外，整個(gè)行程所需票價(jià)支出也會被某些乘客列入考慮范圍。只考慮

21、公汽與同時(shí)考慮公汽和地鐵，票價(jià)的計(jì)算方法有所不同，作討論如下：</p><p>　　對于只考慮乘公汽到達(dá)的情況，北京市采用的是分段收費(fèi)。我們可以從0開始編號，在不同范圍內(nèi)的站點(diǎn)數(shù)，收費(fèi)情況不盡相同。首先，我們把收費(fèi)情況考慮為一個(gè)分段函數(shù)。對于特定的起始站→終到站的線路選擇，我們只需要將乘客換乘公汽的站點(diǎn)與所到站點(diǎn)序列進(jìn)行劃段，這里也將起始站和終到站認(rèn)作換乘點(diǎn)。進(jìn)行劃段以后，可以得到相鄰兩換乘站點(diǎn)之間的站點(diǎn)數(shù)，計(jì)算

22、各段的票價(jià)，再將各段票價(jià)疊加后可得整個(gè)乘車過程所需總票價(jià)。</p><p>　　當(dāng)同時(shí)考慮地鐵和公汽時(shí)，我們也需要根據(jù)換乘點(diǎn)將起始站→終到站的站點(diǎn)序列進(jìn)行劃分。所不同的是，若乘坐地鐵，乘客只需要買一張票就可以了，換乘不收費(fèi)，因此，如果在起始站→終到站的站點(diǎn)序列中有地鐵，對于地鐵換地鐵，我們則需要在前面計(jì)算的總票價(jià)上加上地鐵票價(jià)3元即可得到起始站→終到站的總票價(jià)。</p><p>　　因此，

23、我們得到了只考慮公汽和同時(shí)考慮地鐵時(shí)乘客所要花費(fèi)的總票價(jià)的表示方法，作為我們的第三個(gè)目標(biāo)。</p><p>　　綜上，我們首先得到解決該問題的一個(gè)三目標(biāo)規(guī)劃模型。第三問要我們在假設(shè)又知道所有站點(diǎn)之間的步行時(shí)間的情況下，給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。該問是建立在前兩個(gè)問題的基礎(chǔ)上的。對于發(fā)生的情況有很多種，如在將要到的站時(shí)發(fā)生堵車步行以節(jié)約時(shí)間，在下車站點(diǎn)需要走一到兩站路才能到達(dá)目的地或者是換乘下一趟車

24、的站點(diǎn)，在采用分段計(jì)價(jià)方式的情況下，多出一到兩個(gè)站點(diǎn)是為了節(jié)省選擇提前下車等多種情況。這里，根據(jù)1中的基本假設(shè)，我們只考慮，在采用分段計(jì)價(jià)方式的情況下，多出一到兩個(gè)站點(diǎn)時(shí)為了節(jié)約選擇提前下車的情況。</p><p><b>　　基本假設(shè)</b></p><p>　　附錄中給出的數(shù)據(jù)真實(shí)可信，直到2008年8月不進(jìn)行調(diào)整。</p><p>　　附

25、錄中給出的各項(xiàng)假設(shè)真實(shí)可信。</p><p>　　環(huán)線車和地鐵T2均為單環(huán)。</p><p>　　北京市公交路線暢通，不會出現(xiàn)長時(shí)間的堵車。</p><p>　　將要到達(dá)站點(diǎn)只有1至2站時(shí)出現(xiàn)步行的情況。</p><p>　　在地鐵站之間不出現(xiàn)步行的情況，單一票價(jià)制度的公汽不考慮步行的情況。</p><p><b

26、>　　符號說明</b></p><p><b>　　模型建立和求解</b></p><p>　　根據(jù)前面對于該問題的分析，該問題前兩個(gè)問題主要是要我們對給定的6對起始站→終到站在只考慮公汽和同時(shí)考慮公汽和地鐵兩種不同的情況下，建立模型并進(jìn)行求解給出各個(gè)線路的最佳選擇，第三問要求我們在假設(shè)知道所有站點(diǎn)之間的步行時(shí)間的情況下，給出任意兩站點(diǎn)之間線路選擇問

27、題的數(shù)學(xué)模型，各個(gè)問題分別具體討論如下：</p><p>　　只考慮公汽線路的模型以及求解</p><p>　　根據(jù)4中的分析，我們需要首先建立一個(gè)以換乘次數(shù)最少，整個(gè)過程當(dāng)中需要花費(fèi)的總時(shí)間最少以及總票價(jià)最少三者作為目標(biāo)的三目標(biāo)規(guī)劃模型。</p><p>　　由于各條線路的討論情況相同，首先我們需要假設(shè)出由起始站到終點(diǎn)站乘客經(jīng)過的乘車線路序列，這里我們不妨設(shè)由起始

28、站到終點(diǎn)站乘客所經(jīng)過的站點(diǎn)序列為。其中分別為起始站編號、終到站編號、起始站到終到站經(jīng)過的站點(diǎn)總數(shù)，為乘客經(jīng)過的第站的編號。下面對各個(gè)目標(biāo)進(jìn)行分別討論。</p><p><b>　　換乘次數(shù)</b></p><p>　　為了計(jì)算換乘次數(shù)，我們首先設(shè)為經(jīng)過站的公汽編號，其集合記為，表示如下</p><p><b>　　(1)</b&

29、gt;</p><p>　　設(shè)為公汽線路經(jīng)過的站點(diǎn)編號集合。</p><p>　　根據(jù)前面設(shè)定的乘客由起始站到終到站，我們可以通過比較相鄰站點(diǎn)的公汽編號，來判斷是否進(jìn)行了公汽換乘，設(shè)為是否在第站發(fā)生了換乘，為0-1變量，由于起始站和終到站是我們假定的換乘點(diǎn)，取值為0，因此這里只需要考慮中間站的換乘情況，表示如下</p><p><b>　　(2)</

30、b></p><p>　　另設(shè)為換乘站點(diǎn)編號的集合，由于并不是所有的站點(diǎn)都是要進(jìn)行換乘的，因此換乘點(diǎn)的站點(diǎn)編號集合應(yīng)為行程中通過的所有站點(diǎn)的集合的子集，即相當(dāng)于原來有一個(gè)序列為，其下標(biāo)為連續(xù)的，我們從其中抽取出一個(gè)子列，記為。運(yùn)用于該具體問題當(dāng)中，換乘點(diǎn)的序列是由起始站到終到站以及之間所有站點(diǎn)序列的子序列，可表示為</p><p><b>　　(3)</b>&l

31、t;/p><p>　　為了后面方便處理，我們把該集合直接記為</p><p><b>　　(4)</b></p><p><b>　　其基數(shù)為。</b></p><p>　　因此我們可以得到換乘次數(shù)的目標(biāo)函數(shù)，為</p><p><b>　　(5)</b>&

32、lt;/p><p><b>　　行程總時(shí)間</b></p><p>　　根據(jù)4的分析，在我們只考慮公汽的情況下，乘客由起始站→終到站所花費(fèi)的總時(shí)間由經(jīng)過站點(diǎn)數(shù)量和換乘次數(shù)兩部分決定。</p><p>　　前面已經(jīng)假定乘客經(jīng)過的站點(diǎn)序列，根據(jù)題目中的假設(shè)，相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)為3分鐘，可以直接得到公汽的總時(shí)間為。</p>

33、<p>　　對于公汽換乘公汽的換乘過程所花的時(shí)間，題目中已經(jīng)給出公汽換乘公汽平均耗時(shí)為5分鐘(其中步行時(shí)間2分鐘)，而前面5.1.1中我們已經(jīng)給出了換乘次數(shù)的表達(dá)式，因此可以得到換乘過程中所消耗的時(shí)間為。</p><p>　　綜上，可以得到行程總時(shí)間最少作為該問的第二個(gè)目標(biāo)，如下</p><p><b>　　(6)</b></p><

34、p>　　其中為經(jīng)過總站點(diǎn)數(shù)量，為在第站是否發(fā)生公汽換乘公汽的情況。</p><p><b>　　總票價(jià)</b></p><p>　　根據(jù)前面4的分析，在只考慮公汽時(shí)，票價(jià)是以相鄰兩換乘點(diǎn)之間站點(diǎn)數(shù)量來決定的。</p><p>　　設(shè)為換乘點(diǎn)在由起始站到達(dá)終點(diǎn)站站點(diǎn)序列的編號，為的整數(shù)，但不一定連續(xù)，其對應(yīng)換乘點(diǎn)的站點(diǎn)編號為，易得相鄰兩換乘

35、點(diǎn)之間的站點(diǎn)數(shù)為</p><p>　　由于北京的公汽收費(fèi)方式分為單一票制和分段計(jì)價(jià)兩種方式，因此我們首先需要判斷乘坐的公汽的收費(fèi)方式，這由公汽線路本身決定。引入0-1計(jì)價(jià)方式因子來表示采用的收費(fèi)方式，則</p><p><b>　　(7)</b></p><p>　　若收費(fèi)方式為分段計(jì)價(jià)，由題目所給資料得到0～20站：1元；21～40站：2元；

36、40站以上：3元，設(shè)定票價(jià)收費(fèi)分段函數(shù)</p><p><b>　　(8)</b></p><p>　　因此我們可以得到總票價(jià)最少的目標(biāo)，為</p><p><b>　　(9)</b></p><p><b>　　其中為換乘總次數(shù)。</b></p><p&g

37、t;　　這樣我們就對各個(gè)約束條件進(jìn)行了討論，接下來對約束條件進(jìn)行討論。</p><p><b>　　約束條件</b></p><p>　　該問題中主要有三個(gè)約束，都針對換乘站點(diǎn)，即換乘之前乘坐的公汽要到達(dá)該站以，經(jīng)過該站公汽數(shù)量要大于1以及將要換乘的公汽可以到達(dá)序列中的另外一點(diǎn)，分別討論如下</p><p>　　首先在換乘站點(diǎn) 之前所乘坐的公汽

38、編號，其應(yīng)屬于所有經(jīng)過站的公汽編號的集合，換乘站點(diǎn)公汽數(shù)量大于1，設(shè)為經(jīng)過換乘點(diǎn)站的公汽編號的集合，其基數(shù)可表示為，因此得到換乘站點(diǎn)經(jīng)過公汽輛數(shù)大于1的約束為</p><p><b>　　(10)</b></p><p>　　設(shè)下一個(gè)換乘點(diǎn)序號為，對應(yīng)站點(diǎn)編號為，可以得到換乘點(diǎn)的另一個(gè)約束條件，為</p><p><b>　　(11)

39、</b></p><p><b>　　多目標(biāo)模型的建立 </b></p><p>　　綜合5.1.1~5.1.4的分析，我們可以得到如下三目標(biāo)規(guī)劃模型</p><p><b>　　目標(biāo)函數(shù)</b></p><p><b>　　(12)</b></p>

40、<p><b>　　約束條件</b></p><p><b>　　(13)</b></p><p>　　模型求解算法描述與求解</p><p><b>　　算法描述</b></p><p>　　根據(jù)5.1.5的模型，我們首先設(shè)計(jì)算法如下：</p><

41、;p>　　輸入待查詢站點(diǎn)的和。</p><p>　　從站點(diǎn)可直達(dá)的站點(diǎn)集合，可直達(dá)的站點(diǎn)集合，若 , 用表示從的直達(dá)線路，。為可行解集合。如以換乘次數(shù)為目標(biāo)，轉(zhuǎn)7.</p><p>　　若，，則為一個(gè)可行解。如以換乘次數(shù)為目標(biāo)，轉(zhuǎn)7.</p><p>　　，所有可直達(dá)的站點(diǎn)集合為，若，，則</p><p>　　，所有可直達(dá)的站點(diǎn)集合為

42、，若，，則</p><p>　　若，兩次換乘不能得到可行解，需近一步搜索，結(jié)束。</p><p>　　若考慮以時(shí)間最短為目標(biāo)得從可行解集合中得到全局最優(yōu)解，結(jié)束。</p><p><b>　　求解結(jié)果</b></p><p>　　根據(jù)以上算法，我們采用Visual C++進(jìn)行編程求解，在編程過程中將換乘次數(shù)作為第一目標(biāo)

43、進(jìn)行計(jì)算。</p><p>　　由于對于特定的換乘次數(shù)目標(biāo)值，計(jì)算得到的由各對起始站→終到站的乘車方案很多，所以需要根據(jù)第二目標(biāo)來找到里面滿足總時(shí)間最短進(jìn)行篩選，若總時(shí)間相同，只能根據(jù)第三目標(biāo)總票價(jià)來確定出最佳路線。因此，我們采用圖1流程篩選出最佳路線。</p><p>　　圖1最佳路線篩選方案</p><p>　　根據(jù)圖1，可以得到題目中給出的各起始站→終到站之

44、間的以及目標(biāo)值以及最佳乘車路線如下。</p><p>　　表1只考慮公汽時(shí)的各個(gè)目標(biāo)值</p><p>　　同時(shí)可以得到各個(gè)起始站→終到站乘坐公汽的部分最佳路線如下（其余見附錄1）</p><p>　　S3359→S1828的最佳路線為：</p><p>　　乘L436路下行：S3359-S2026-S1132-S2266-S2263-S3

45、917-S2303-S2301-S3233 -S618-S616-S2112-S2110-S2153-S2814-S2813-S3501-S3515-S3500-S756-S492-S903-S1768-S955-S480-S2703-S2800-S2192-S2191-S1829-S3649-S1784-乘L167路下行：S1784-S1828</p><p>　　S1557→S0481的最佳路線為：</

46、p><p>　　乘L84路下行：S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S28- S29-S55-S51-S1919-乘L189路下行：S1919-S2840-S1402-S3186-乘L460路下行：S3186-S3544-S2116-S2119-S1788-S1789-S1770-S2322-S992-S2184-S2954-S3117　-S2424-S11

47、74-S902-S903-S2101-S481</p><p>　　S0971→S0485的最佳路線為：</p><p>　　乘L13路下行：S971-S3832-S3341-S2237-S3565-S3333-S1180-S3494-S1523- S1520-S1988-S1743-S1742-S1181-S1879-S3405-S2517-S3117-S2954-S531-S2184-

48、換乘L417路下行：S2184-S992-S2322-S1770-S1789-S2119-S2116-S3544-S3186- S3409-S2717-S1402-S2840-S643-S2079-S1920-S2480-S2482-S2210-S3332-S3351-S485</p><p>　　S0008→S0073的最佳路線為：</p><p>　　乘L159路下行：S8-S3412

49、-S2743-S3586-S2544-S913-S2953-S3874-S630 -S854-S400-S2633-S3053-S408-S145-S3138-S2684-S2683-S291-換乘L58路下行：S291-S3614-S491-S2559-S990-S3315-S3898-S1855-S0073</p><p>　　S0148→S0485的最佳路線為：</p><p>　　

50、乘L308路上行：S148-S462-S361-S1797-S2221-S302-S2222-S2737-S1716 -S128-S2268-S1308-S1391-S2272-S36-換乘L156路上行：S36-S3233-S618-S617 -S721-S2057-S2361-S608-S399-S2535-S2534-S239-S497-S2090-S2082-S2210-S3332-換乘下行－L417-S3332-S3351-S

51、0485</p><p>　　S0087→S3676的最佳路線為：</p><p>　　乘L454路上行：S87-S857-S630-S1427-S1426-S541-S978-S3389-S1919- S641-S2840-S3496-乘L209路下行：S3496-S1883-S1159-S2699-S2922-S3010　-S583-S1987-S82-S3676</p>

52、<p>　　增加換乘次數(shù)對時(shí)間的影響結(jié)果</p><p>　　為了討論換乘次數(shù)對于換乘時(shí)間的影響，我們將S3359→S1828,S0971→S0485, S0008→S0073 ,S0087→S3676增加一次換乘得到相應(yīng)結(jié)果如下</p><p>　　表2調(diào)整換乘次數(shù)后的各個(gè)目標(biāo)值</p><p>　　同時(shí)，我們可以給出題目中列出的6對起始站→終到站

53、路線時(shí)間最短的最佳路線如下：</p><p>　　S3359→S1828的時(shí)間最短的最佳路線為：</p><p>　　乘坐L324上行：S3359--S2023-S2027-S1746 換乘L027環(huán)線:　S1746-S3697-S3727-S0393-S0391-S3177-S0004-S1967-S3674-S1522-S1520-S2992　-S0903-S1768-S0955-S0

54、480-S2704-S1784 換乘L167下行：S1784-S1828</p><p>　　S0971→S0485的時(shí)間最短的最佳路線為：</p><p>　　乘坐L013上行: S0971-S3571-S1609換乘L140下行,S1609-S3242　-S1481-S3426-S2553-S3903-S1553-S3531-S1967-S0012-S2636-S2113-S2112-

55、S2833　-S0618-S1327-S2303-S2263-S3037-S2654- 換乘L469上行S2654-S1729-S3766　-S1691-S1383-S1381-S1321-S2019-S2017-S2159-S0772-S0485</p><p>　　S0008→S0073的時(shí)間最短的最佳路線：</p><p>　　乘坐L198上行: S0008-S1383-S1691-

56、S3766換乘L296環(huán)線－S3766-S1729-S2654-S3231-S3917-S2303-S1327-S0618-S3100-S2151-S3746-S3501　-S2517-S2184換乘L345上行－S2184-S3162-S2181-S0073</p><p>　　S0087→S3676的時(shí)間最短的最佳路線：</p><p>　　乘坐L021下行－S0087-S0088換乘

57、L231環(huán)線－S0088-S0609-S0483　-S0604-S2650-S3693-S1659-S2962-S0622-S0456-S0427換乘L097上行，S0427-S3676。</p><p><b>　　結(jié)果分析</b></p><p>　　根據(jù)5.1.6和5.1.7中的結(jié)果對比，我們可以將換乘次數(shù)增加1的4對起始站→終到站的個(gè)目標(biāo)值的變化，由于增加換乘

58、自然會影響到總花費(fèi)，但是考慮到公交花費(fèi)占有的比重相對來說很小。因此只考慮乘車站點(diǎn)以及節(jié)約時(shí)間在調(diào)整換乘次數(shù)之間的對比情況，結(jié)合表1和表2的計(jì)算結(jié)果，我們不難得到下表3</p><p>　　表3 調(diào)整換乘次數(shù)前后時(shí)間和站點(diǎn)數(shù)量對比量</p><p>　　從表3可以看出，將換乘次數(shù)增加1，會使乘車所經(jīng)過的站點(diǎn)數(shù)量大大減小，整個(gè)行程中所花費(fèi)的總時(shí)間雖然是由在公汽上消耗的時(shí)間和換乘所消耗的時(shí)間兩

59、部分構(gòu)成。但由于換乘次數(shù)為0~2，相差范圍很小。因此行程中所消耗的總時(shí)間將直接由所經(jīng)過站點(diǎn)數(shù)決定。這樣站點(diǎn)數(shù)量的減少就會直接導(dǎo)致行程的所花去的時(shí)間大大減小。</p><p>　　根據(jù)此分析結(jié)果，我們可以向時(shí)間觀念比較強(qiáng)的乘客提出建議，在考慮乘車過程當(dāng)中適當(dāng)增加換乘次數(shù)，這樣會大大節(jié)約時(shí)間。對題目中所給出的6條起始站→終到站我們的乘車建議見5.1.7，5.1.8以及附錄1。</p><p>

60、　　同時(shí)考慮公汽與地鐵線路</p><p>　　該問題與5.1類似，只是在考慮公汽的同時(shí)加入了地鐵的因素在里面，根據(jù)我們對題目附錄2.1和2.2地分析不難發(fā)現(xiàn)，問題一當(dāng)中給出的6對起始站→終到站的站點(diǎn)中（除題中給出的第6對線路外），沒有地鐵換乘公汽的站點(diǎn)，因此我們可以肯定的是除題中給出的第6對線路外，乘客的起始站和終到站都是公汽站點(diǎn)。對于對應(yīng)各個(gè)目標(biāo)以及約束條件，我們在5.1的基礎(chǔ)上進(jìn)行討論分析如下。</p

61、><p><b>　　換乘次數(shù)</b></p><p>　　在5.1.1中，只需要對公汽換乘公汽進(jìn)行討論，但在這里面需要討論四種換乘情況，為了方便下面的計(jì)算和模型建立，我們?yōu)樗姆N方式進(jìn)行了編號入下表</p><p>　　表4各種方式編號情況表</p><p>　　對于行程序列中的一個(gè)站點(diǎn)來說只會出現(xiàn)發(fā)生和不發(fā)生兩種情況。因

62、此我們首先定義各個(gè)方式的0-1變量如下</p><p><b>　　(14)</b></p><p>　　另設(shè)采用第種方式進(jìn)行換乘的換乘站點(diǎn)編號的集合，可表示為</p><p><b>　　(15)</b></p><p><b>　　其基數(shù)為。</b></p>

63、<p>　　因此，我們可以得到換乘次數(shù)最少的目標(biāo)，為</p><p><b>　　(16)</b></p><p><b>　　行程消耗總時(shí)間</b></p><p>　　在5.1.2中，我們只考慮公汽的情況。而在此問中，除了要考慮公汽的情況以外還要考慮地鐵與地鐵之間、地鐵換乘公汽、公汽換乘地鐵三種情況。<

64、/p><p>　　同樣地，在該問題當(dāng)中，行程消耗的總時(shí)間包含兩部分，即在車上的時(shí)間和換乘所花的時(shí)間。</p><p>　　首先刻畫在車上花去的時(shí)間，其包含在公汽和地鐵上兩部分的時(shí)間，由于地鐵換乘公汽和公汽換乘地鐵是成對出現(xiàn)的，先后順序不同，具體討論如下</p><p>　　設(shè)分別為地鐵換乘公汽和公汽換乘地鐵的站點(diǎn)集合中的站點(diǎn)編號元素，設(shè)起始點(diǎn)編號為0。</p>

65、;<p>　　若起始乘坐的是地鐵，那么首先出現(xiàn)的二者換乘方式必然為地鐵換公汽，可以得到二者交叉換乘序列示意圖如下</p><p>　　圖2起始點(diǎn)乘地鐵示意圖</p><p>　　此時(shí)在公汽上消耗的時(shí)間可表示為</p><p>　　若起始乘坐的是公汽，那么首先出現(xiàn)的二者換乘方式必然為公汽換地鐵，可以得到二者交叉換乘序列示意圖為</p>&

66、lt;p>　　圖3起始點(diǎn)乘公汽示意圖</p><p>　　此時(shí)在公汽上消耗的時(shí)間可表示為</p><p><b>　　(17)</b></p><p>　　為了將兩種不同情況進(jìn)行融合，我們引入起始因子來刻畫起始站乘坐車輛的情況</p><p><b>　　(18)</b></p>

67、<p>　　因此可以在公汽上花去的時(shí)間，設(shè)為，為</p><p><b>　　(19)</b></p><p>　　類似地，可以得到在地鐵上花費(fèi)的總時(shí)間，設(shè)為，為</p><p><b>　　(20)</b></p><p>　　再討論在換乘過程中所消耗的時(shí)間，在一個(gè)站點(diǎn)，若換乘，則只

68、可能出現(xiàn)換乘一次另一個(gè)交通工具的情況。設(shè)換乘矩陣為，對應(yīng)換乘矩陣中各分量表示的換乘方式平均耗時(shí)矩陣為</p><p><b>　　，</b></p><p>　　其中至多一個(gè)等于1，因此對于第站換乘所花的時(shí)間為。所有站點(diǎn)換乘所花的總時(shí)間，設(shè)為，為</p><p><b>　　(21)</b></p><

69、p>　　綜上可以得到行程消耗的總時(shí)間最少的目標(biāo)為</p><p><b>　　(22)</b></p><p><b>　　行程花費(fèi)的總費(fèi)用</b></p><p>　　由于加入換乘地鐵主要是為了防止出現(xiàn)多次公汽換公汽的情況，因此我們不妨認(rèn)為不出現(xiàn)公汽換乘公汽的情況，只需要計(jì)算乘坐各段公汽需要支付的票價(jià)和乘坐地鐵所要

70、花費(fèi)的票價(jià)，下面一一進(jìn)行討論。</p><p>　　根據(jù)5.1.3，直接得到各段公汽需要支付的總票價(jià)為</p><p><b>　　(23)</b></p><p>　　其中為地鐵換乘公汽的總次數(shù)。</p><p>　　對于乘坐地鐵所要花費(fèi)的票價(jià)，題目中告訴我們地鐵與地鐵之間換乘是不收費(fèi)的，只有在地鐵換乘公交的時(shí)候會收取

71、3元的費(fèi)用，因此可以得到乘坐地鐵需要花費(fèi)的費(fèi)用為。</p><p>　　綜上可以得到行程花費(fèi)最小的目標(biāo)函數(shù)為</p><p><b>　　(23)</b></p><p><b>　　約束條件</b></p><p>　　在一個(gè)特定的站點(diǎn)，若換乘，則只可能出現(xiàn)換乘一次另一個(gè)交通工具的情況，為<

72、/p><p><b>　　(24)</b></p><p>　　從另一方面來說，在地鐵換乘公汽和公汽換乘地鐵的時(shí)候，對應(yīng)的換乘點(diǎn)應(yīng)該有相應(yīng)的公汽和地鐵站。為了表示這一約束，我們設(shè)地鐵站所達(dá)到的公交站點(diǎn)的集合，這可以由題目所給附錄2.1和2.2中得到。</p><p>　　因此我們只需要約束地鐵換乘公汽的集合中的元素在換乘站有公汽站與該地鐵站對應(yīng)。設(shè)

73、為一包含站點(diǎn)公汽站點(diǎn)的集合，這些元素為同一地鐵站可換乘的公汽站點(diǎn)。由此得到地鐵換乘公汽的條件為</p><p><b>　　(25)</b></p><p>　　對于公汽換乘地鐵的情況，前面已經(jīng)設(shè)定該種換乘方式對應(yīng)的換乘點(diǎn)集合為，二者能夠換乘的條件為集合中的元素屬于所有地鐵站點(diǎn)公汽站點(diǎn)的集合即可，為</p><p><b>　　(26

74、)</b></p><p>　　同時(shí)考慮公汽和地鐵的多目標(biāo)模型建立</p><p>　　根據(jù)5.2.1~5.2.4的分析，我們可以得到同時(shí)考慮公汽和地鐵的三目標(biāo)規(guī)劃數(shù)學(xué)模型，如下</p><p><b>　　目標(biāo)函數(shù)</b></p><p><b>　　(27)</b></p>

75、;<p><b>　　約束條件</b></p><p><b>　　(28)</b></p><p><b>　　模型求解算法及結(jié)果</b></p><p><b>　　算法描述</b></p><p>　　輸入待查詢站點(diǎn)的和。</p&

76、gt;<p>　　可從地鐵換乘的公交站點(diǎn)集合，若，，則最優(yōu)方案 , 表乘地鐵從的最優(yōu)線路，為可行解集合。轉(zhuǎn)5.</p><p><b>　　，若，則，，則</b></p><p>　　則可行解的集合就可以表示為： ，其中表示從站點(diǎn)到的直達(dá)線路，表示從站點(diǎn)到的直達(dá)線路。</p><p>　　考慮以時(shí)間最短為目標(biāo)得從可行解集合中得到

77、全局最優(yōu)解。</p><p><b>　　求解結(jié)果</b></p><p>　　根據(jù)算法，我們采用Visual C++進(jìn)行編程計(jì)算可得到如下結(jié)果</p><p>　　表5同時(shí)考慮公汽和地鐵時(shí)的各個(gè)目標(biāo)值</p><p>　　同時(shí)可以得到各個(gè)起始站→終到站的最佳路徑分別如下</p><p>　　S

78、3359→S1828的最佳路線為：</p><p>　　乘L015上行-S3359-S2266-S3917-S2303-S1327-S3068(D08)-換乘地鐵T1-D08- D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-換乘地鐵T2-D33-D34(S0578)-換乘L167下行S0578-S3095-S0096-S0095-S1193-S0105-S1194-S1189-S

79、2801 -S0590 -S1240 -S1241-S1784-S1828</p><p>　　S1557→S0481的最佳路線為：</p><p>　　乘L084下行S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S28-S29 -S0055-S0051-S1919(D20)-換乘地鐵T2-D20-D19-D18-換乘T2-D18-D3

80、3 -D34-D35-D36-D37-D38-D39-D24(S0537)-換乘L516上行-S0537-S2651-S3013 -S1808-S1173-S0910-S3517-S0453-S2424-S1174-S0902- S0903-S2101-S0481 </p><p>　　乘L363下行S1557-S3158-S2628-S3408-S2044-S1985-S2563-S2682-S2735-S2

81、9 -S0055-S0051-S1919-換乘地鐵T2-D20-D19-D18-換乘T2-D18-D33-D34 -D35 -D36-D37-D38-D39-D24(S0537)-換乘L516上行-S0537-S2651-S3013-S1808 -S1173-S0910-S3517-S0453-S2424-S1174-S0902-S0903 -S2101-S0481 </p><p>　　S0971→S04

82、85的最佳路線：</p><p>　　乘L094上行（或L119下行）S971-S3571-S1609-S0345-S1419-S2389　-S0567(D01)-換乘地鐵T1-D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11　-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21(S0466)換乘L051上行（或L450下行）-S0466-S318

83、9-S2810-S2385-S0071-S0485 </p><p>　　乘L094上行（或L119下行）S971-S3571-S1609-S0345-S1419-S2389-　S0567(D01)-換乘地鐵T1-D01　-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11　-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21(S0464)換乘L104上行

84、（或L395下行）-S0464-S964-S3189-S2810-S2385-S0485</p><p>　　S0008→S0073的最佳路線：</p><p>　　S0008-S3412-S2743-S2544-S2953-S0778-S2534(D15)換乘T1-D15-D14-D13 -D12(S0609)-換乘L057上行-S0609-S0483-S0604-S2650-S3470

85、-S2619-S2340 -S3162-S2181-S0073 </p><p>　　S0148→S0485的最佳路線：</p><p>　　乘L024下行：S0148-S0927-S2830-S2070-S1487(D2)換乘T1-D2-D3-D4-D5 -D6-D7-D8-D9-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21(S466)

86、換乘L051上行(或L450下行)S466-S3189-S2810-S2385-S0071-S0485 </p><p>　　S0087→S3676的最佳路線：</p><p>　　乘地鐵T2-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36</p><p><b>　　結(jié)果分析</b></p>

87、;<p>　　這里進(jìn)行分析比較的時(shí)候，由于乘坐公交消費(fèi)在乘客考慮選擇線路時(shí)所占有的比重很小，因此這里只對換乘次數(shù)和行程總時(shí)間進(jìn)行比較分析，并根據(jù)分析結(jié)果給出我們的建議。</p><p>　　根據(jù)5.1.6，5.1.7，5.2.6的求解結(jié)果，我們在下表6中做出如下比較</p><p>　　表6同時(shí)考慮公汽和地鐵與只考慮公汽各目標(biāo)值對比情況表</p><p

88、>　　注：同時(shí)考慮公汽和地鐵換乘的情況中站點(diǎn)數(shù)一欄表示的“公汽總站點(diǎn)數(shù)+地鐵站點(diǎn)數(shù)”，如“20+12”即為整個(gè)行程過程中所經(jīng)過的公汽站總數(shù)為20，地鐵站的總數(shù)為12.</p><p>　　從表6我們可以看出：</p><p>　　六條線路中S0971→S0485，S0008→S0073，S0148→S0485，S0087→S3676四條線路在同時(shí)考慮公汽和地鐵換乘的情況下，經(jīng)過的站點(diǎn)

89、數(shù)量和總時(shí)間都得到了大大的減少。</p><p>　　同時(shí)考慮公汽和地鐵換乘的情況下，S0087→S3676線路可以直接通過地鐵到達(dá)目的地。同時(shí)整個(gè)行程消耗的總時(shí)間比起只考慮公汽換乘1次和2次分別減少了32分鐘，13分鐘。因此，對于這樣的線路來說，選用地鐵作為交通工具是最為省時(shí)，省力的途徑。</p><p>　　另外，我們不難看出在同時(shí)考慮公汽和地鐵換乘的情況下，線路S3359→S1828

90、，S1557→S0481的總時(shí)間和總站點(diǎn)數(shù)比起只考慮公汽時(shí)反而有所增加。所以，對于有些線路來說，采用地鐵并不一定是最省時(shí)間的交通方式。我們建議，乘客盡量考慮自己的線路情況來選擇公交工具。</p><p>　　任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型</p><p>　　本問要求我們在前兩問的基礎(chǔ)上，加入步行的情況在內(nèi)，給出任意兩個(gè)站點(diǎn)的路徑選擇問題。</p><p>　

91、　這里就要考慮三種交通方式，即公汽，地鐵以及步行，還有其間的換乘轉(zhuǎn)化關(guān)系。對于公汽和地鐵及二者之間的換乘的情況，我們在5.1和5.2當(dāng)中已經(jīng)進(jìn)行了詳細(xì)的討論，下面主要對步行進(jìn)行討論。</p><p>　　發(fā)生步行的情況，主要考慮到在發(fā)生在換乘點(diǎn)前后，若換乘前乘坐的是分段計(jì)的公汽，為了節(jié)約起見，乘客就要根據(jù)自己所要經(jīng)過的站點(diǎn)數(shù)進(jìn)行考慮。從前面我們知道北京分段計(jì)價(jià)的公汽的計(jì)價(jià)規(guī)則為：0～20站：1元；21～40站：2

92、元；40站以上：3元。因此當(dāng)乘客乘坐經(jīng)過的站點(diǎn)數(shù)量為21，22，41，42的時(shí)候，乘客就會考慮只乘坐20，40個(gè)站以降低票價(jià)。</p><p>　　乘客選擇步行的概率與20和40個(gè)站點(diǎn)有密切關(guān)系，我們不妨認(rèn)為，當(dāng)乘客所乘坐的站點(diǎn)數(shù)為21，22，41，42時(shí)，乘客會選擇在第20站和40站下車進(jìn)行步行1~2個(gè)站點(diǎn)來到達(dá)目的地，發(fā)生點(diǎn)在換乘點(diǎn)之前。</p><p>　　首先引入步行因子來描述換乘

93、點(diǎn)前一段公汽所經(jīng)過的站點(diǎn)數(shù)目</p><p><b>　　(29)</b></p><p><b>　　換乘次數(shù)</b></p><p>　　和5.2.1一樣，我們只考慮了地鐵換乘公交與公交換乘地鐵兩種換乘情況，因此加入步行的因素在里面，換乘總次數(shù)不會受到影響。刻畫換乘次數(shù)最少的目標(biāo)也和5.2.1一樣。</p>

94、<p><b>　　行程消耗總時(shí)間</b></p><p>　　加入步行的成分在里面，必將影響這個(gè)行程的總時(shí)間。這時(shí)整個(gè)行程所消耗的時(shí)間由三部分組成：公交車上消耗的時(shí)間，換乘消耗的時(shí)間以及步行所消耗的時(shí)間。</p><p>　　根據(jù)我們的討論分析發(fā)現(xiàn)，步行時(shí)間僅發(fā)生在公汽換乘地鐵之前，由所乘公汽所經(jīng)過的站點(diǎn)數(shù)量或。對于站點(diǎn)數(shù)量不滿足21，22，41，42

95、的部分，可以直接采用5.2.2中的方法進(jìn)行計(jì)算，為</p><p><b>　　(30)</b></p><p>　　但是很顯然，上式包含了站點(diǎn)數(shù)量滿足21，22，41，42的情況，需要借助步行因子來除去這些情況所消耗的時(shí)間，只需要乘以即可，其只有在步行因子，即不發(fā)生步行的情況下為1，因此得到在公汽換乘地鐵時(shí)不發(fā)生步行的情況所消耗的時(shí)間為</p><

96、;p><b>　　(31)</b></p><p>　　接下來需要單獨(dú)計(jì)算在換乘點(diǎn)之前發(fā)生步行時(shí)，換乘之前所消耗的時(shí)間，這個(gè)事件有兩部分構(gòu)成，一部分是在公汽上的時(shí)間，另一部分是步行的時(shí)間。在公汽上消耗的時(shí)間相當(dāng)于是經(jīng)過20和40個(gè)站所消耗的時(shí)間，結(jié)合步行因子，可以很容易得到在公汽上消耗的時(shí)間，為。</p><p>　　對于步行時(shí)間，由于題目中沒有具體給出北京市的

97、公交站分布情況圖，但可以知道兩個(gè)相鄰站點(diǎn)之間的距離是一定的，因此這里我們不妨假設(shè)平均兩相鄰站點(diǎn)之間的步行時(shí)間為，另外我們可以直接由公汽換乘地鐵的換乘點(diǎn)與前以換乘點(diǎn)之間所經(jīng)過的站點(diǎn)數(shù)量得到需要步行的站點(diǎn)數(shù)量。結(jié)合步行因子，我們可以將步行時(shí)間表示為</p><p><b>　　(32)</b></p><p>　　另外，由于加入步行的成分，對于換乘點(diǎn)的數(shù)量沒有影響，換乘時(shí)

98、間的計(jì)算與5.2.2種計(jì)算方法相同，為。</p><p>　　由于地鐵是統(tǒng)一計(jì)費(fèi)3元，所以沒有必要考慮地鐵站之間的步行，計(jì)算時(shí)間的方法與5.2.2相同。</p><p>　　綜上，我們可得到加入步行情況時(shí)，使整個(gè)路程所花的總時(shí)間最少的目標(biāo)為</p><p><b>　　(33)</b></p><p><b>

99、　　行程中的乘車費(fèi)用</b></p><p>　　這里需要綜合5.2.3和5.3.2的思想，分析如下。</p><p>　　首先考慮在換乘點(diǎn)之前不進(jìn)行步行部分的花費(fèi)費(fèi)用，為</p><p><b>　　(33)</b></p><p>　　其中，為起點(diǎn)因子，為票價(jià)因子。</p><p>

100、;　　換乘點(diǎn)之前進(jìn)行步行的情況所花費(fèi)的費(fèi)用只需要按照經(jīng)過站點(diǎn)20站或者40站的票價(jià)進(jìn)行支付即可，即要支付的票價(jià)與步行因子相同，由于乘坐地鐵部分是按照統(tǒng)一計(jì)價(jià)3元，所以這里沒有必要在地鐵站點(diǎn)之間考慮換乘的情況，因此乘坐地鐵所花費(fèi)的費(fèi)用和5.2.3一樣，為。</p><p>　　綜上，我們得到了考慮步行情況的任意兩個(gè)站點(diǎn)之間所花費(fèi)的總費(fèi)用目標(biāo)函數(shù)為</p><p><b>　　(34

101、)</b></p><p><b>　　關(guān)于約束條件</b></p><p>　　這里約束條件和前面5.2.4一樣，并未發(fā)生改變。</p><p>　　任意兩站點(diǎn)之間的路線選擇模型</p><p>　　綜合5.3.1~5.3.4種的分析，我們可以得到任意兩站點(diǎn)之間的路線選擇模型，具體如下</p>

102、<p><b>　　(35)</b></p><p><b>　　約束條件</b></p><p><b>　　(36)</b></p><p><b>　　模型評價(jià)和推廣</b></p><p><b>　　模型優(yōu)缺點(diǎn)評價(jià)</

103、b></p><p><b>　　優(yōu)點(diǎn)</b></p><p>　　本題中的模型建立完全是基于組內(nèi)成員討論，結(jié)合問題進(jìn)行分析建立的，體現(xiàn)了一定的新穎性和原創(chuàng)性。</p><p>　　根據(jù)有關(guān)資料中提供的信息，分析出該問題中需要考慮的幾個(gè)問題的幾個(gè)主要目標(biāo)，并確定將各個(gè)目標(biāo)的重要程度，為模型求解帶來了極大的方便。</p>&l

104、t;p>　　巧妙地根據(jù)模型的特點(diǎn)設(shè)計(jì)出簡單易行的算法。</p><p><b>　　算法優(yōu)點(diǎn)：</b></p><p>　　基于生成樹思想的截尾深度優(yōu)先搜索，算法簡單易行，所有結(jié)果均可在數(shù)秒內(nèi)得出。</p><p>　　針對換乘次數(shù)和耗費(fèi)時(shí)間分別為目標(biāo)的檢索，得到的為全局最優(yōu)解，結(jié)果的可靠性強(qiáng)。</p><p>&

105、lt;b>　　缺點(diǎn)</b></p><p>　　由于比賽的時(shí)間有限，我們對該問題進(jìn)行了一些簡化，應(yīng)該需要更加深入地思考這個(gè)問題，做出更為符合實(shí)際情況的結(jié)果以及模型。</p><p><b>　　模型推廣</b></p><p>　　該問題中的模型可以運(yùn)用于多路徑的選擇問題和指派問題。</p><p>&

106、lt;b>　　參考文獻(xiàn)</b></p><p>　　[1]張永梅，韓焱，陳立潮，城市公交查詢系統(tǒng)的研究與設(shè)計(jì)，計(jì)算機(jī)應(yīng)用，第25卷第2期，2005年 2月。</p><p>　　[2]向萬里，劉洪升，城市公交網(wǎng)絡(luò)出行路徑選擇的計(jì)算機(jī)算法研究，蘭州交通大學(xué)學(xué)報(bào)(自然科學(xué)版)，第25卷第1期，2006年 2月。</p><p>　　[3]胡霍真，

107、戴光明，李穎，公交車網(wǎng)絡(luò)的最短路徑算法及實(shí)現(xiàn)，微機(jī)發(fā)展，第l5卷第9期，2005年9月。</p><p>　　[4]姜啟源，數(shù)學(xué)模型（第三版），北京，高等教育出版社，2003年8月。</p><p>　　[5]譚浩強(qiáng)，C語言程序設(shè)計(jì)(第二版)，北京，清華大學(xué)出版社，2002年12月</p><p><b>　　附錄</b></p>

108、<p>　　附錄１以換乘次數(shù)作為第一目標(biāo)，只考慮乘坐公汽時(shí)，各起始站→終到站的最佳路線</p><p>　　S3359→S1828的最佳路線為：</p><p>　　乘L436路下行：S3359-S2026-S1132-S2266-S2263-S3917-S2303-S2301-S3233 -S618-S616-S2112-S2110-S2153-S2814-S2813-S

109、3501-S3515-S3500-S756-S492-S903-S1768-S955-S480-S2703-S2800-S2192-S2191-S1829-S3649-S1784-乘L167路下行：S1784-S1828</p><p>　　S1557→S0481的最佳路線為：</p><p>　　乘L84路下行：S1557-S3158-S2628-S3408-S2044-S1985-S2

110、563-S2682-S28- S29-S55-S51-S1919-乘L189路下行：S1919-S2840-S1402-S3186-乘L460路下行：S3186-S3544-S2116-S2119-S1788-S1789-S1770-S2322-S992-S2184-S2954-S3117　-S2424-S1174-S902-S903-S2101-S481</p><p>　　乘L363路下行：S1557-S31

111、58-S2628-S3408-S2044-S1985-S2563-S2682　-S2735- S29-S55-S51-S1919-乘L189路下行－S1919-S2840-S1402-S3186-乘L460路下行：S3186-S3544-S2116-S2119-S1788-S1789-S1770-S2322-S992-S2184　-S2954-S3117-S2424-S1174-S902-S903-S2101-S481</p>

112、;<p>　　S0971→S0485的最佳路線為：</p><p>　　乘L13路下行：S971-S3832-S3341-S2237-S3565-S3333-S1180-S3494-S1523- S1520-S1988-S1743-S1742-S1181-S1879-S3405-S2517-S3117-S2954-S531-S2184-換乘L417路下行：S2184-S992-S2322-S1770

113、-S1789-S2119-S2116-S3544-S3186- S3409-S2717-S1402-S2840-S643-S2079-S1920-S2480-S2482-S2210-S3332-S3351-S485</p><p>　　S0008→S0073的最佳路線為：</p><p>　　乘L159路下行：S8-S3412-S2743-S3586-S2544-S913-S2953-S3

114、874-S630 -S854-S400-S2633-S3053-S408-S145-S3138-S2684-S2683-S291-換乘L58路下行：S291-S3614-S491-S2559-S990-S3315-S3898-S1855-S0073</p><p>　　乘L159路下行：S8-S3412-S2743-S3586-S2544-S913-S2953-S3874-S630 -S854-S400-S263