數(shù)學(xué)建模論文公交查詢系統(tǒng)的數(shù)學(xué)模型_第1頁
數(shù)學(xué)建模論文公交查詢系統(tǒng)的數(shù)學(xué)模型_第2頁
數(shù)學(xué)建模論文公交查詢系統(tǒng)的數(shù)學(xué)模型_第3頁
數(shù)學(xué)建模論文公交查詢系統(tǒng)的數(shù)學(xué)模型_第4頁
數(shù)學(xué)建模論文公交查詢系統(tǒng)的數(shù)學(xué)模型_第5頁
已閱讀5頁,還剩26頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、科院6組:魯成、蔡光達(dá)、王奇公交查詢系統(tǒng)的數(shù)學(xué)模型摘要本文針對公交線路選擇問題,建立了多目標(biāo)動態(tài)規(guī)劃模型,運(yùn)用matlab軟件實(shí)現(xiàn)了整個流程和迭代,最終求出全局近似最優(yōu)解,即換乘次數(shù)最少的情況下耗時最短,費(fèi)用最低的乘車路線。并分別提供了轉(zhuǎn)乘次數(shù)最少、耗時最短、費(fèi)用最低三種線路滿足不同需求的乘客。針對問題一,僅考慮公汽線路,對數(shù)據(jù)進(jìn)行初步分析和處理后,考慮到數(shù)據(jù)的復(fù)雜性和數(shù)據(jù)搜索范圍的廣度,將不同公交汽線路抽象化,建立站點(diǎn)間直達(dá)線路信息存儲結(jié)構(gòu)元胞,基于直達(dá)線路數(shù)據(jù)庫構(gòu)造站點(diǎn)間以直達(dá)線路數(shù)目為元素的鄰接矩陣,在鄰接矩陣構(gòu)成的數(shù)據(jù)結(jié)構(gòu)之上,考慮公汽線路不同票價、線路等條件,采用改進(jìn)的鄰接算法分別以

2、轉(zhuǎn)乘次數(shù)最少、耗時最短、費(fèi)用最低為目標(biāo)進(jìn)行全局最佳路線的求解。并分別給出了轉(zhuǎn)乘次數(shù)最少、耗時最短、費(fèi)用最低三種路線來滿足不同需求的乘客。針對問題二,在問題一的基礎(chǔ)上考慮公汽與地鐵混排,將地鐵站點(diǎn)與周圍的公汽站點(diǎn)集抽象為同一新站點(diǎn),把以上公汽線路站點(diǎn)映射為新站點(diǎn),建立新的直達(dá)數(shù)據(jù)庫,結(jié)合地鐵費(fèi)用、地鐵與公汽間的換乘時間以及兩者站間行駛時間等條件,將地鐵與公汽結(jié)合的問題轉(zhuǎn)化為問題一,采用改進(jìn)的鄰接算法得到不同目標(biāo)下的多種優(yōu)化方案。針對問題三,根據(jù)問題一與問題二基于換乘次數(shù)最少逐步分析目標(biāo)選定最佳路線的模型,在知道所有站點(diǎn)之間的步行時間的基礎(chǔ)上,建立以步行代替短距離減少換乘次數(shù)和以步行鄰邊化減少出行

3、用時的優(yōu)化數(shù)學(xué)模型,采用廣度優(yōu)先算法,改進(jìn)公交線路的路線選擇方案。關(guān)鍵詞:多目標(biāo)動態(tài)規(guī)劃;matlab;鄰接矩陣;廣度優(yōu)先算法一、問題重述1.1問題的背景近幾年來,城市的公交系統(tǒng)有了很大的發(fā)展。公交運(yùn)輸?shù)母采w面越來越廣,公交線路也日益增多,公共交通逐漸成為絕大多數(shù)出行人員的首選方式。發(fā)達(dá)的城市公交系統(tǒng)使得公眾的出行更加通暢、便利,同時也給人們出行乘車線路的選擇帶來了一定的困擾。方便、快捷、經(jīng)濟(jì)的公交出行線路方案,不僅可以方便公眾的出行,同時也為城市交通減少了不必要的負(fù)擔(dān),有利于提高城市交通運(yùn)行的效率,展現(xiàn)城市的現(xiàn)代化風(fēng)貌。1.2問題的重述 我國人民翹首企盼的第29屆奧運(yùn)會明年8月將在北京舉行,

4、屆時有大量觀眾到現(xiàn)場觀看奧運(yùn)比賽,其中大部分人將會乘坐公共交通工具(簡稱公交,包括公汽、地鐵等)出行。這些年來,城市的公交系統(tǒng)有了很大發(fā)展,北京市的公交線路已達(dá)800條以上,使得公眾的出行更加通暢、便利,但同時也面臨多條線路的選擇問題。針對市場需求,某公司準(zhǔn)備研制開發(fā)一個解決公交線路選擇問題的自主查詢計算機(jī)系統(tǒng)。為了設(shè)計這樣一個系統(tǒng),其核心是線路選擇的模型與算法,應(yīng)該從實(shí)際情況出發(fā)考慮,滿足查詢者的各種不同需求。1.3有待解決的問題1. 僅考慮公汽線路,給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù),利用你們的模型與算法,求出以下6對起始站終到站之間的最佳路線(要有清晰

5、的評價說明)。 (1)、s3359s1828 (2)、s1557s0481 (3)、s0971s0485(4)、s0008s0073 (5)、s0148s0485 (6)、s0087s36762. 同時考慮公汽與地鐵線路,解決以上問題。3. 假設(shè)又知道所有站點(diǎn)之間的步行時間,請你給出任意兩站點(diǎn)之間線路選擇問題的數(shù)學(xué)模型。附:基本參數(shù)設(shè)定相鄰公汽站平均行駛時間(包括停站時間):3分鐘相鄰地鐵站平均行駛時間(包括停站時間):2.5分鐘公汽換乘公汽平均耗時:5分鐘(其中步行時間2分鐘)地鐵換乘地鐵平均耗時:4分鐘(其中步行時間2分鐘)地鐵換乘公汽平均耗時:7分鐘(其中步行時間4分鐘)公汽換乘地鐵平均

6、耗時:6分鐘(其中步行時間4分鐘)公汽票價:分為單一票價與分段計價兩種,標(biāo)記于線路后;其中分段計價的票價為:020站:1元;2140站:2元;40站以上:3元地鐵票價:3元(無論地鐵線路間是否換乘)注:以上參數(shù)均為簡化問題而作的假設(shè),未必與實(shí)際數(shù)據(jù)完全吻合。二、問題分析2.1出行人員乘車需求本文參照了在宜昌市做的一個公交乘客出行心理調(diào)查統(tǒng)計結(jié)果,它主要對三個因素做了調(diào)查:換乘次數(shù)、出行距離、出行耗時。從圖1中可以看到有41.16%的乘客在選擇出行路徑時首先考慮的是換乘最少,其次考慮時間最短,而將路程最短作為出行時考慮的首要條件的乘客只占18.60%,故而我們選擇以轉(zhuǎn)車次數(shù)最少為首要目標(biāo),時間最

7、短、路程最短為次要目標(biāo)。圖1:公交乘客出行心理分析圖2.2公交網(wǎng)絡(luò)的特點(diǎn)根據(jù)題中信息,公汽線路分三種,下面將這三種線路進(jìn)行數(shù)據(jù)處理: 1. 下行線、上行線原路返回 這種線路有兩個端點(diǎn)站,在兩個端點(diǎn)之間雙向行車,而且兩個方向上的行車路線相同,經(jīng)過同樣的站點(diǎn)序列。由于線路的方向不同,因此,下行線和上行線可以抽象成兩條線路處理。如下圖所示:2. 線路為環(huán)行線 實(shí)際中環(huán)形路線一般是雙環(huán),但在對這兩條線路進(jìn)行抽象時,為保證任意兩站點(diǎn)距離最近,把每條線路再抽象成2條。如下圖所示:3. 下行線與上行線經(jīng)過站點(diǎn)不同 由于下行線與上行線經(jīng)過站點(diǎn)不同,顯然,該種線路需要抽象成兩條線路處理。如下圖所示:2.3問題一

8、的分析 本問題僅考慮公汽線路,因此,只需對不包含地鐵站的1018條行駛路線進(jìn)行分析即可。對于公眾而言,選擇路線時主要考慮以下三個方面:換乘次數(shù)、路途時間和乘車費(fèi)用。因此,本問題是一個多目標(biāo)的規(guī)劃問題。不難發(fā)現(xiàn),換乘次數(shù)的增加必然會引起費(fèi)用的開銷,而且對費(fèi)用的影響很大。費(fèi)用最小時的路線,其對應(yīng)的換乘次數(shù)必然很少。因此,我們把換乘次數(shù)最少作為第一目標(biāo),費(fèi)用最省和時間最短分別作為第二、三目標(biāo)。分別考慮對此三個目標(biāo)的優(yōu)化,按照第一目標(biāo)最優(yōu),第二、三目標(biāo)在第一目標(biāo)最優(yōu)前提下最優(yōu)或者次優(yōu)來求解。2.4問題二的分析對于問題二,對于兩條地鐵線路,依據(jù)問題一中的抽象化方法進(jìn)行抽象化處理;對于地鐵站點(diǎn),由地鐵與鄰

9、近公汽站點(diǎn)可換乘的信息可知地鐵站點(diǎn)及其周圍的公汽站點(diǎn)距離較近,考慮將其抽象化歸一為新的站點(diǎn),減小站點(diǎn)差異性,重新構(gòu)造站點(diǎn)間的鄰接矩陣?;趩栴}一更新數(shù)據(jù),尋找合適的算法組合不同路線及站點(diǎn)分別給出三種目標(biāo)下的最優(yōu)方案。2.5問題三的分析考慮公汽站點(diǎn)與地鐵站點(diǎn)的實(shí)際分布情況,在某些轉(zhuǎn)乘點(diǎn)存在步行小段距離再轉(zhuǎn)車可以節(jié)省時間或減少轉(zhuǎn)車次數(shù)的情況,在求解時需確定線路中該類選擇多樣化的站點(diǎn),然后主要優(yōu)化該類站點(diǎn)后繼線路的選擇方案,達(dá)到以上三個目標(biāo)。三、模型假設(shè)1. 假設(shè)車站站點(diǎn)無重名;2. 假設(shè)相鄰站點(diǎn)間平均行駛時間一定;3. 假設(shè)公交準(zhǔn)點(diǎn)到達(dá),不考慮紅綠燈等待時間;4. 假設(shè)各公交線路公交車發(fā)車頻度相同

10、;5. 假設(shè)公交系統(tǒng)運(yùn)行順暢,不考慮中途發(fā)生故障堵車等意外情況;6. 假設(shè)附錄1所給的基本參數(shù)均為定制,且能較好的反應(yīng)實(shí)際情況;7. 假設(shè)地鐵線路間的換乘不需要付費(fèi),票價為3元不變;8. 假設(shè)坐環(huán)行線經(jīng)過終點(diǎn)站后要重新收費(fèi)。四、符號說明乘車時間對應(yīng)的決策變量站點(diǎn)至站點(diǎn)乘車所需時間站點(diǎn)至站點(diǎn)的直達(dá)費(fèi)用表示站點(diǎn)至站點(diǎn)所經(jīng)過的站數(shù)步行時間對應(yīng)的決策變量站點(diǎn)間是否有地鐵換乘表示第個站點(diǎn)負(fù)載壓力權(quán)總等待時間步行時間五、問題一的解答5.1模型一的建立5.1.1目標(biāo)函數(shù)的確立目標(biāo)一:換乘次數(shù)最少引入0-1決策變量表示弧是否在起點(diǎn)與終點(diǎn)的路上,則:若與之間無直接相連的弧,但可通過中間節(jié)點(diǎn)轉(zhuǎn)跳,表明若vi與vj

11、之間無直接相連的弧,但可通過中間節(jié)點(diǎn)轉(zhuǎn)跳,表明由站點(diǎn)i到j(luò)之間不可直達(dá),但可通過轉(zhuǎn)乘到達(dá),則由到之間換乘次數(shù)為經(jīng)過的總弧數(shù)減 1,即換乘次數(shù)最小可表示為:目標(biāo)二:行程總時間最短:目標(biāo)三:行程總費(fèi)用最少:5.1.2確定約束條件1. 換乘次數(shù)約束基于對目標(biāo)一的分析,以c表示換乘次數(shù):注:為自然數(shù)其中,參數(shù)為人為設(shè)定值,根據(jù)實(shí)際情況,考慮以下三種情況:2. 行程總費(fèi)用最少設(shè)表示車輛屬性:設(shè)表示所經(jīng)過的站數(shù):5.1.3綜上所述,得到問題一的最優(yōu)化模型5.2模型一的求解運(yùn)用matlab軟件求解,得:表1:問題一結(jié)果路線第1目標(biāo)換乘次數(shù)時間(分)費(fèi)用(元)s3359s1828換乘次數(shù)11043時間2673

12、費(fèi)用2673s1557s0481換乘次數(shù)21093時間31024費(fèi)用21093s0971s0485換乘次數(shù)11313時間21063費(fèi)用21063s0008s0073換乘次數(shù)1862時間4625費(fèi)用1862s0148s0485換乘次數(shù)21093時間31054費(fèi)用21093s0087s3676換乘次數(shù)1682時間2493費(fèi)用16825.3模型一的結(jié)果分析分析結(jié)果,得:1.幾乎所有換乘3次的線路都可以以較短時間、較低的費(fèi)用到達(dá)目的站點(diǎn),說明選擇三次作為換乘次數(shù)的上限是可行的。2.考慮查詢系統(tǒng)的時效性,給出matlab程序運(yùn)行時間。由運(yùn)行時間:查詢換乘次數(shù)小于1次含1次的線路,程序運(yùn)行時間遠(yuǎn)小于1秒;

13、查詢換乘2次程序耗時不超過5秒;查詢換乘3次程序所需時間200秒左右。在實(shí)際情況中,乘客在乘車點(diǎn)等車時進(jìn)行路線查詢,以上查詢時間是可以被乘客接受的。以上所述程序運(yùn)行時間說明在本文描述的數(shù)據(jù)存儲結(jié)構(gòu)下,改進(jìn)的鄰接算法的可行性與較低的時間復(fù)雜度。綜述,模型i求解的線路方案集使用于不同需求下的所有用戶,具有較強(qiáng)的實(shí)用價值,很大程度上滿足了乘客乘車線路多樣化的需求。六、問題二的解答6.1模型二的建立6.1.1確定目標(biāo)函數(shù)目標(biāo)一:換乘次數(shù)最少引入0-1決策變量表示弧是否在起點(diǎn)與終點(diǎn)的路上,則:若與之間無直接相連的弧,但可通過中間節(jié)點(diǎn)轉(zhuǎn)跳,表明由站點(diǎn)i到j(luò)之間不可直達(dá),但可通過轉(zhuǎn)乘到達(dá),則由到之間換乘次數(shù)

14、為經(jīng)過的總弧數(shù)減 去1,即換乘次數(shù)最小可表示為:目標(biāo)二:行程總時間最短:(1)乘車時間(為各站點(diǎn)最快直達(dá)時間,基于,包括地鐵在內(nèi)):(2)總等待時間:設(shè)表示ij 最短直達(dá)為公汽,表示最短直達(dá)為地鐵,總等待時間表示為:(3)總步行時間: 將相同車型換乘、不同車型換乘的步行時間,一同視為2 分鐘 不同車型換乘多步行的4 分鐘表示為:地鐵轉(zhuǎn)地鐵是不同車型換乘的特例,且只可能在d12 與d18 轉(zhuǎn)乘,出現(xiàn)這種情況在基礎(chǔ)上減少步行時間4 分鐘。表示為:在地鐵直達(dá)時,需要另外加上4 分鐘出站步行時間:若始發(fā)乘坐地鐵轉(zhuǎn)公交到達(dá)終點(diǎn),需要增加步行時間2 分鐘:若始發(fā)乘坐公交轉(zhuǎn)地鐵到達(dá)終點(diǎn),也需要增加步行時間2

15、 分鐘:總步行時間表示為:則行程總時間最短表示為(總等待時間+總步行時間+乘車時間):目標(biāo)三:行程總費(fèi)用最少:6.1.2確定約束條件(1) 換乘次數(shù)約束基于對目標(biāo)一的分析,以c表示換乘次數(shù):(2) 最短路起訖點(diǎn)約束(3) 地鐵間換乘約束站點(diǎn)間是否有地鐵換乘,使用表示,則與走的路徑需滿足:有地鐵線路可知,地鐵轉(zhuǎn)地鐵只可能在d12與d18轉(zhuǎn)乘,故轉(zhuǎn)乘總次數(shù)不大于2:6.1.3綜上所述,得到問題二的最優(yōu)化模型6.2模型二的求解運(yùn)用matlab軟件求解,得:表2:問題二結(jié)果路線第1目標(biāo)換乘次數(shù)時間(分)費(fèi)用(元)s3359s1828換乘次數(shù)11043時間2673費(fèi)用2673s1557s0481換乘次數(shù)

16、21093時間31024費(fèi)用21093s0971s0485換乘次數(shù)11313時間4105.57費(fèi)用21063s0008s0073換乘次數(shù)1862時間356.55費(fèi)用1862s0148s0485換乘次數(shù)21093290.55時間389.56費(fèi)用21093s0087s3676換乘次數(shù)0303時間0303費(fèi)用16826.3問題二的結(jié)果分析分析結(jié)果,得:1.幾乎所有換乘3次的線路都可以以較短時間、較低的費(fèi)用到達(dá)目的站點(diǎn),說明選擇三次作為換乘次數(shù)的上限是可行的。2.考慮查詢系統(tǒng)的時效性,給出matlab程序運(yùn)行時間。由運(yùn)行時間:查詢換乘次數(shù)小于1次含1次的線路,程序運(yùn)行時間遠(yuǎn)小于1秒;查詢換乘2次程序耗

17、時不超過5秒;查詢換乘3次程序所需時間200秒左右。在實(shí)際情況中,乘客在乘車點(diǎn)等車時進(jìn)行路線查詢,以上查詢時間是可以被乘客接受的。以上所述程序運(yùn)行時間說明在本文描述的數(shù)據(jù)存儲結(jié)構(gòu)下,改進(jìn)的鄰接算法的可行性與較低的時間復(fù)雜度。綜述,模型二求解的線路方案集使用于不同需求下的所有用戶,具有較強(qiáng)的實(shí)用價值,很大程度上滿足了乘客乘車線路多樣化的需求。七、問題三的解答7.1模型三的建立7.1.1確定目標(biāo)函數(shù)基于前面問題的分析,本模型主要以出行總時間最省為主要目標(biāo),同時考慮轉(zhuǎn)乘次數(shù)盡量少,行程費(fèi)用最少,轉(zhuǎn)乘點(diǎn)始發(fā)站最多,站點(diǎn)負(fù)載壓力最小,所以建立以下目標(biāo)函數(shù):目標(biāo)一:行程總時間最短(1)時間權(quán)值(2)引入0

18、-1決策變量表示乘車時弧是否在起點(diǎn)與終點(diǎn)的路上,則:(3)引入0-1決策變量表示步行十弧是否在起點(diǎn)與終點(diǎn)的路上,則:則目標(biāo)函數(shù)為:目標(biāo)二:行程總費(fèi)用最少乘車費(fèi)用權(quán),則目標(biāo)函數(shù)為:目標(biāo)三:站點(diǎn)負(fù)載壓力最小 以表示第個站點(diǎn)負(fù)載壓力權(quán),則目標(biāo)函數(shù)為:7.1.2確定約束條件(1)最短路約束由于行走路線中任意兩點(diǎn)之間只會選擇一種出行方式,即:我們還知道決策變量必須滿足最短路問題中的主要現(xiàn)在條件,如下所示:(2)換乘次數(shù)約束,以表示乘客所能承受的最大換乘次數(shù),則(3)地鐵間換乘約束 站點(diǎn)間是否有地鐵換乘,使用表示,則與走的路徑需滿足:有地鐵線路可知,地鐵轉(zhuǎn)地鐵只可能在d12與d18轉(zhuǎn)乘,故轉(zhuǎn)乘總次數(shù)不大于

19、2:7.1.3綜上所述,得到問題三的最優(yōu)化模型7.2模型三程序設(shè)計流程圖八、模型的評價與推廣8.1模型的優(yōu)點(diǎn)1. 通過假設(shè)舍棄了對問題影響不大的因素,只保留乘車時間,換乘次數(shù),乘車花費(fèi)這幾個核心目標(biāo),使問題更加清晰,得出的線路更全面合理;2. 建立在圖論基礎(chǔ)上能夠求解出轉(zhuǎn)乘次數(shù)不超過三次時的所有可行方案,并可根據(jù)公眾的不同需求,給出最佳路線方案,模型實(shí)用性較強(qiáng);3. 模型的現(xiàn)實(shí)意義強(qiáng),具有很好的實(shí)用性和擴(kuò)展性。8.2模型的不足1. 在轉(zhuǎn)乘次數(shù)超過3次的情況下,運(yùn)用本模型求解計算過程復(fù)雜,計算量過大,故本模型存在一定的局限性。2. 由于在計算過程中題目給的平均行駛及轉(zhuǎn)車時間是非現(xiàn)實(shí)的,所以使得本

20、模型的應(yīng)用于現(xiàn)實(shí)時存在偏差。8.3模型的推廣解讀題目不難發(fā)現(xiàn)這是運(yùn)籌學(xué)中的最短路問題,仔細(xì)分析建立的模型:模型不僅適用于乘公交,即最短路和最低費(fèi)用的問題,通過不同的權(quán)值變化,這類問題可歸結(jié)為最短路問題,而最短路問題作為圖論或運(yùn)籌學(xué)中的重要分支,在工商業(yè)、交通運(yùn)輸、工程技術(shù)、行政管理等領(lǐng)域有著廣泛的應(yīng)用,由此可知本模型實(shí)用性較強(qiáng),易于推廣。參考文獻(xiàn)1 姜啟源,數(shù)學(xué)建模第三版,北京:高等教育出版社,2006年2 徐多勇、李志蜀、梅林,基于gsm短信息的公交查詢系統(tǒng)的最優(yōu)化轉(zhuǎn)乘方案研究與設(shè)計,計算機(jī)應(yīng)用,27卷:2007年6月。3 王莉,李文權(quán),公共交通系統(tǒng)最佳路徑算法,東南大學(xué)學(xué)報,第34卷:第3

21、 期,2004年 3月4 duane hanselman、bruce littlefield 著,朱仁峰譯,matlab 7,北京:清華大學(xué)出版社,2006年5月第一版附錄附錄一:clc,clear%1第一問數(shù)據(jù)處理clc;clear allfid = fopen(1.1 公汽線路信息.txt,r); i=1; while 1 tline = fgetl(fid); if ischar(tline) break; end if strcmp(tline,) continue end if strcmp(tline(1),l) str=tline continue elseif strcmp(t

22、line,end) break end if strcmp(tline,單一票制1元。) p=1; continue elseif strcmp(tline,分段計價。) p=2; continue end if strcmp(tline(1:2),上行) li,1=str; li,2=p; li,3=上行; li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),下行) li,1=str; li,2=p; li,3=下行; li,4=tline(4:end); i=i+1; continue elseif strcmp(tlin

23、e(1:2),環(huán)行) li,1=str; li,2=p; li,3=環(huán)行1; li,4=strcat(tline(4:end),tline(10:end); i=i+1; %計算來回 li,1=str; li,2=p; li,3=環(huán)行2; li,4=strcat(tline(4:end),tline(10:end); i=i+1; continue elseif strcmp(tline(1),s) li,1=str; li,2=p; li,3=來回1; li,4=tline; i=i+1; %計算來回 li,1=str; li,2=p; li,3=來回2; li,4=tline; i=i+1

24、; continue end endfclose(fid);%建立鄰接矩陣for i=1:size(l,1) tline=li,4; t=findstr(tline,s); temp=zeros(1,length(t); if strcmp(li,3,來回2) | strcmp(li,3,環(huán)行2) for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4); end else for j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4); end end

25、l2i,1=temp; end for i=1:3957 if floor(i/10)=0 citi=strcat(s000,num2str(i); elseif floor(i/100)=0 citi=strcat(s00,num2str(i); elseif floor(i/1000)=0 citi=strcat(s0,num2str(i); else citi=strcat(s,num2str(i); end end cit3958=d01:s0567,s0042,s0025; cit3959=d02:s1487; cit3960=d03:s0303,s0302; cit3961=d04

26、:s0566; cit3962=d05:s0436,s0438,s0437,s0435; cit3963=d06:s0392,s0394,s0393,s0391; cit3964=d07:s0386,s0388,s0387,s0385; cit3965=d08:s3068,s0617,s0619,s0618,s0616; cit3966=d09:s1279; cit3967=d10:s2057,s0721,s0722,s0720; cit3968=d11:s0070,s2361,s3721; cit3969=d12:s0609,s0608; cit3970=d13:s2633,s0399,s0

27、401,s0400; cit3971=d14:s3321,s2535,s2464; cit3972=d15:s3329,s2534; cit3973=d16:s3506,s0167,s0168; cit3974=d17:s0237,s0239,s0238,s0236,s0540; cit3975=d18:s0668; cit3976=d19:s0180,s0181; cit3977=d20:s2079,s2933,s1919,s1921,s1920; cit3978=d21:s0465,s0467,s0466,s0464; cit3979=d22:s3457; cit3980=d23:s251

28、2; cit3981=d24:s0537,s3580; cit3982=d25:s0526,s0528,s0527,s0525; cit3983=d26:s3045,s0605,s0607; cit3984=d27:s0087,s0088,s0086; cit3985=d28:s0855,s0856,s0854,s0857; cit3986=d29:s0631,s0632,s0630; cit3987=d30:s3874,s1426,s1427; cit3988=d31:s0211,s0539,s0541,s0540; cit3989=d32:s0978,s0497,s0498; cit399

29、0=d33:s1894,s1896,s1895; cit3991=d34:s1104,s0576,s0578,s0577; cit3992=d35:s3010,s0583,s0582; cit3993=d36:s3676,s0427,s0061,s0060; cit3994=d37:s1961,s2817,s0455,s0456; cit3995=d38:s3262,s0622; cit3996=d39:s1956,s0289,s0291;%2排序% t_sort( a ,n , p ) % a 根據(jù)第n行排序 % p=1升序 ,2 降 % powered_by_* syms psize=si

30、ze(l); if p=1 xx,idx=sort(l(n,:); for i=1:size(1) l(i,:)=l(i,idx); end elseif p=2 xx,idx=sort(l(n,:),descend); for i=1:size(1) l(i,:)=l(i,idx); end end %3直達(dá)列表建立s(1:3957,1:3957)=zeros(1,1,uint16); for i=1:1040 t=l2i,1; for j=1:length(t)-1 for k=j+1:length(t) temp=st(j),t(k); %每條路線任意兩點(diǎn) str=li,1; %l中的第

31、一列 n,m=size(temp); if n=1 & temp(1,1)=0 temp(n,1)=str2double(str(2:end); if li,2=2 if (k-j)40 temp(n,2)=3; elseif (k-j)20 temp(n,2)=2; else temp(n,2)=1; end else temp(n,2)=1; end temp(n,3)=k-j; else temp(n+1,1)=str2double(str(2:end); if li,2=2 if (k-j)40 temp(n+1,2)=3; elseif (k-j)20 temp(n+1,2)=2;

32、else temp(n+1,2)=1; end else temp(n+1,2)=1; end temp(n+1,3)=k-j; end st(j),t(k)=temp; end end end for i=1:3957 for j=1:3957 if length(si,j)=1 si,j=t_sort(si,j,3,1); end end end time=zeros(3957,3957,uint8); for i=1:3957 for j=1:3957 if length(si,j)=1 time(i,j)=size(si,j,1); end end end tt=zeros(3957,

33、3957,uint8); for i=1:3957 for j=1:3957 temp=si,j; if temp(1,1)=0 tt(i,j)=temp(1,3); end end end %4鄰接搜索程序段問題一求解 n=971; m=485; % 直達(dá) if time(n,m)=0 temp=sn,m; for i=1:size(temp,1) disp(strcat(直達(dá)車為:l,num2str(temp(i,1) end return end clear u u2 % 一次轉(zhuǎn)車 t=1:3957; t2=time(n,:).*time(:,m); if sum(t2)=0 x=1;

34、t=t(t2=0); for i=1:length(t) t1=sn,t(i); t2=st(i),m; t1=double(t1); t2=double(t2); for j=1:size(t1,1) for k=1:size(t2,1) u(x,1)=1;%轉(zhuǎn)站次數(shù) u(x,2)=(t1(j,3)+t2(k,3)*3+5+3;%總時間 u(x,3)=t(i);%轉(zhuǎn)站點(diǎn) u(x,4:5)=t1(j,1) t2(k,1);%車輛 %是否始發(fā)站 temp=0; for k1=1:1040 if str2double(lk1,1(2:end)=u(x,5) if l2k1,1(1,1)=t(i)

35、temp=1; break end end end u(x,6)=temp; u(x,7)=t1(j,2)+t2(k,2);%費(fèi)用 x=x+1; end end end return end f=u(1,2); for j=2:length(u(:,2) if u(j,2)=f; f=u(j,2); index=j; endend%二次轉(zhuǎn)車 t=1:3957; x=1; for i=1:3957 if time(n,i)=0 for j=1:3957 if time(j,m)=0 & time(i,j)=0 t1=sn,i; t2=si,j; t3=sj,m; t1=double(t1); t

36、2=double(t2); t3=double(t3); for k1=1:size(t1,1) for k2=1:size(t2,1) for k3=1:size(t3,1) u2(x,1)=2;%轉(zhuǎn)站次數(shù) %總時間 u2(x,2)=(t1(k1,3)+t2(k2,3)+t3(k3,3)*3+10+3; u2(x,3)=t(i);%轉(zhuǎn)站點(diǎn) u2(x,4)=t(j);%轉(zhuǎn)站點(diǎn) u2(x,5:6)=t1(k1,1) t2(k2,1);%車輛1,2 %是否始發(fā) temp=0; for kk=1:1040 if str2double(lkk,1(2:end)=u2(x,6) if l2kk,1(1,

37、1)=t(i) temp=1; break end end end u2(x,7)=t3(k3,1);%車輛3 %始發(fā)站數(shù) for kk=1:1040 if str2double(lkk,1(2:end)=u2(x,7) if l2kk,1(1,1)=t(j) temp=temp+1; break end end end u2(x,8)=temp; %費(fèi)用 u2(x,9)=t1(k1,2)+t2(k2,2)+t3(k3,2); x=x+1; end end end end end end end f2=u2(1,2);for j=2:length(u2(:,2) if u2(j,2)=f2;

38、f2=u2(j,2); index2=j; endend附錄二:clc,clear%1第一問數(shù)據(jù)處理clc;clear allfid = fopen(1.1 公汽線路信息.txt,r); i=1; while 1 tline = fgetl(fid); if ischar(tline) break; end if strcmp(tline,) continue end if strcmp(tline(1),l) str=tline continue elseif strcmp(tline,end) break end if strcmp(tline,單一票制1元。) p=1; continue

39、 elseif strcmp(tline,分段計價。) p=2; continue end if strcmp(tline(1:2),上行) li,1=str; li,2=p; li,3=上行; li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),下行) li,1=str; li,2=p; li,3=下行; li,4=tline(4:end); i=i+1; continue elseif strcmp(tline(1:2),環(huán)行) li,1=str; li,2=p; li,3=環(huán)行1; li,4=strcat(tline(4

40、:end),tline(10:end); i=i+1; %計算來回 li,1=str; li,2=p; li,3=環(huán)行2; li,4=strcat(tline(4:end),tline(10:end); i=i+1; continue elseif strcmp(tline(1),s) li,1=str; li,2=p; li,3=來回1; li,4=tline; i=i+1; %計算來回 li,1=str; li,2=p; li,3=來回2; li,4=tline; i=i+1; continue end endfclose(fid);%建立鄰接矩陣for i=1:size(l,1) tli

41、ne=li,4; t=findstr(tline,s); temp=zeros(1,length(t); if strcmp(li,3,來回2) | strcmp(li,3,環(huán)行2) for j=length(t):-1:1 temp(length(t)-j+1)=str2double(tline(t(j)+1:t(j)+4); end else for j=1:length(t) temp(j)=str2double(tline(t(j)+1:t(j)+4); end end l2i,1=temp; end for i=1:3957 if floor(i/10)=0 citi=strcat(s000,num2str(i); elseif floor(i/100)=0 citi=strcat(s00,num2s

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論