1、. . . . 專業代碼： 070101 學 號： 2008405010 本科畢業論文（設計）題目：經濟開發區公交線路網的優化設計學 院： 理學院 專 業： 數學與應用數學 班 級： 2008級（1）班 學生： 軍 指導教師： 余英（助教）羅永超（教授）2011年12月28日19 / 24目 錄中文摘要、關鍵詞II英文摘要、關鍵詞III 1.引言 1 1.1提出問題 1 1.2文獻綜述 11.2.1公交網絡優化的目的與基本容 21.2.2最短路問題簡介 31.2.3MATALB軟件簡介 3 1.3研究意義 32. 資料收集 33.研究過程 4 3.1資料分析 4 3.2資料處理 4 3.3公交

2、線路網絡研究設計 43.3.1公交起訖點的選擇 43.3.2公交起訖點的確定 5 3.3.3公交起訖點的配對 53.3.4具體公交線路徑的確定 5 4.結果討論 105.結束語 106.參考文獻117.致 118.附件 12 經濟開發區公交線路網的優化設計軍(省學院理學院08級數學與應用數學，市 556000)摘要：長昆鐵路客運專線的修筑工作正在火熱進行，經濟開發區的城市化進程也在一旁快速地推進。公共交通具有運載量大、運輸效率高、能源消耗低、相對污染少、運輸成本低等優點，在城市交通干線上最為明顯，所以在城市規劃中公共交通的規劃非常重要。公交線路網絡的優化是城市公共交通設計的一個重要工作。對于任

3、何一個公交系統，公交線路的設計是決定系統服務質量的主要因素之一。對于正處于規劃建設中的經濟開發區，在城市建設方面也必須考慮其區域的公交線路優化問題。本文主要對經濟開發區主要城區的公交線網的優化設計進行研究。本文用圖論的最短路知識對收集的資料進行處理，然后結合實際情況對實驗所得的成果修改完善，最后給出公交線網優化設計方案。關鍵字：公交網絡；最短路問題；Dijkstra算法；Matlab；Kaili economic development zone of bus network optimization designWuZhongJun(Guizhou Province Carey instit

4、ute college of science 08 levels of Mathematics,city Kaili 556000)Abstract:With the quick construction of the passenger line from Changsha to Kunming, Kaili city also is promoting the urbanization of its Economic Development Zone quickly . Because public transportation owns the merits of heavy carry

5、ing capacity, high efficiency, low energy consumption, less pollution, and low cost, which most obviously appear in the use of urban transportation routes, the public transportation of city planning is very important. The optimization of public bus lines network is a pretty important work of the des

6、ign of urban public transportation. The design of public bus is one of the main factors, which determines the quality of system service. The under construction Economic Development Zone of Kaili city must consider the optimization of its regional public bus lines network. This thesis mainly studies

7、the optimized design of the main city area public bus lines of Kaili Economic Development Zone. The author collects the dada by using the graph theory of the shortest route to process the data, and then revises and improves the experimental result according to the practical situation, lastly, gives

8、the optimized planning design of the public bus lines and network of Kaili Economic and Development Zone.Key words:public transport network; the shortest path problem;Dijkstra algorithm;Matlab；1.引言1.1提出問題 隨著長昆鐵路干線的即將通車，市經濟開發區的城市化進程將不斷的加快。市經濟開發區正處于由一個城鎮向城市的華麗角色變化中，在這個過程中不僅其經濟實力要達到城市的規模，其基礎設施也要達到城市的規模

9、。公共交通是城市必不可少的公共設施，所以在經濟開發區的城市規劃建設過程中，公交線路網的設計是一個必不可少的任務。本文主要就公交系統的一個問題公交線路網進行研究。研究結果能為相關部門的工作帶來一些科學參考，為經濟開發區的公交系統的優化設計提供理論依據。1.2文獻綜述 我國人多地少，可用資源相對貧乏，城市人口集中，盡管與發達國家和發展中國家相比，我國的機動車擁有量要低得多，但很多大城市的交通擁堵問題仍然是相當嚴重。為了改善城市交通狀況，實現城市可持續發展，“中國技術政策藍皮書”明確提出要“大力發展城市公共交通”，當前國許多城市也確立了“優先發展公共交通”這一交通發展的基本戰略，希望搶在大規模小汽車

10、發展之前確立起公共交通的主導地位。 公共交通網絡優化設計在城市公交發展規劃過程中是最為重要的規劃步驟。對于任何一個城市的公共交通系統，公交網絡布局是決定系統質量的主要因素。公交網絡的優化設計直接影響公交服務水平，并且受到很多條件的限制，一直受到許多學者的關注。 在國，城市公交網絡設計的有代表性的研究有：東南大學王煒教授等出的全網最優的規劃方法、逐條布設優化成網的規劃方法12、結合現狀公交網絡的啟發式逐條優化方法等三種方法。交通大學高自友教授等人提出的連續平衡網絡設計的雙層規劃模型和求解方法3。林柏梁等人在對公交網絡設計的指派問題模型分析基礎上，以所有乘客流的出行時間和實現公交網絡的資金投入為費

11、用目標函數，綜合考慮了起訖點站場的容量限制，同一條道路上的重復線路的數量限制等因素，建立了公交網絡設計非線性0-1規劃模型4。超等人則用圖論方法，以OD分布為基礎依據，給出了城市公共交通網絡最優的圖論模型這些模型和方法為我國公交網絡優化開辟了嶄新的研究思路5。1.2.1 公交網絡優化的目的與基本容公交系統優化設計的目的 （1）為城市居民的出行帶來方便。 （2）引導城市經濟，規劃向著健康、高速、可持續的方向發展。 （3）乘客與公交公司之間出現雙贏的畫面。公交線路優化設計的基本容： （1) 公交線路的優化。 （2) 公交站點優化。 （3）公交調度優化。1.2.1.1公交線路優化目標 （1）最大的直

12、達乘客人數 直達客人數指不需要中途換乘就可以到達目的地的乘客人數，直達乘客人數是一個非常重要的指標，它可以表示一個公交線路的主要方便程度，是較常用的優化目標 （2）最小出行時間 該時間包括候車時間和乘車時間，候車時間與公交發車頻率有關，而乘車時間則與公交線路有關。 （3) 最大公交公司利益 公交公司的最大利益指公交公司投入產出比最大。 (4) 公交線網的服務面積度 保證線網的服務面積率，減少公交盲區。1.2.1.2 影響公交線路規劃的因素 （1）城市客運交通需求 公路沿線的人口分布情況，直接影響到客運量的大小。 （2）道路條件 對于常規公交線路網來說，道路網是公交線路網的基礎，設計公交線路網時

13、首先要考慮到道路的幾何線性、路面條件和容量限制等因素。1.2.2 最短路問題簡介 最短路問題是網絡理論中應用最廣泛的問題之一。許多問題可以使用這個模型，如設備更新、管道鋪設、線路安排、廠區布局等。解決最短路問題主要的算法有：Dijkstra算法，逐次逼近算法和Floyd算法。Dijkstra算法是由Dijkstra于1959年提出，可用于求解指定兩點間的最短路，或從指定點到其余各點的最短路，目前被認為是求無負權網絡最短路問題的最好辦法。 1.2.3MATALB軟件簡介 MATLAB 是MATrix LABoratory（ 矩陣實驗室 ）的縮寫，該軟件是由美國MathWork公司20世紀80年代

14、初開發的一套以矩陣計算為基礎的科學和工程計算軟件。1.3研究意義 國外學者通過研究影響交通網絡設計的因素，主要包括乘客流、資金投入、與道路條件等因素展開自己的研究，達到公交網絡的優化設計。本文主要以經濟開發區的道路規劃圖為基礎，進一步給出其主城區的公交網絡的優化設計，假設研究中的每條公路都滿足公交車運行的相關要求，規劃圖中正在建設的道路和規劃道路全看成已有的道路。研究結果能為經濟開發區的城市規劃與相關課題的研究提供理論依據。2.資料收集 經濟開發區城區建設正在火熱的進行，建設局作為城市的規劃單位，其工作任務重大。通過走訪市經濟開發區建設局相關人士，收集到經濟開發區2009-2030年總歸圖（附

15、件4）。3.研究過程3.1資料數據分析對附件4分析，整理得到統計資料附見1。3.2資料處理將附件4中的圖結合附件1作以下處理： （1）用線段表示公路。 （2）道路長除500取整（小數部分四舍五入）記為道路的權。 （3）給道路交點標上記號為A01、A02.A25。經上面處理，附件4可以用圖1表示（主要研究其主城區的交通，所以有些道路未畫出）。3.3公交線路網絡研究設計3.3.1公交起訖點的選擇 對于公交起訖點的選擇，我們通常會考慮三個因素： (1)公交客流量。公交客流的發生量或者吸引量比較大的地點，需要設立起訖點。 (2)實際的需要。特殊的地點，如車站、碼頭、風景區、居民區、學校等應該選作為起訖

16、點。 （3)人口分布發展走向。以規劃待發展的區域應該設置起訖點，使該區域人口增加。3.3.2 公交起訖點的確定 由于公交車是往返行駛，所以我們選擇的始發點同時也是終點。考慮到上面的三個因素和實際情況，圖1中能夠被選作為起訖點的地點有： （1）學院編號A16 （2）南站編號A20 （3）桃花村與銅鼓村的十字路口編號A09 （4）規劃路與320國道的十字路口編號A01 （5）紅巖村與320國道十字路口編號A053.3.3公交起訖點的配對 結合實際情況、將來的發展趨勢和前面確定的起訖點，設置以下幾條公交線： 1路：下司 南站方向 2路：桃花村 南站方向 3路：環城南路 南站方向 4路：學院 南站方向

17、 5路：紅巖村 環城南路方向 6路：南站環線3.3.4具體公交線路徑的確定 參照公交線網絡優化目標、市經濟開發區的實際情況，本文重點以公交路徑的最短原則來確定公交線路徑（公交環線除外）。對于求最短路徑本文主要采用Dijkstra算法求解。 3.3.4.1 Dijkstra程序收集整理 Dijkstra算法由Dijkstra于1959年提出，可用于求解指定兩點間的最短路，或者從指定點到其余各點的最短路，目前被認為是求解無負權網絡的最短路問題的最好方法。算法的基本思想基于以下原理：若序列As,A1，A2，A3，.，An-1，An是從As到An的最短路，則序列As,A1，A2，A3，.，An-1必為

18、從Vs到Vn的最短路。下面給出dijkstra算法的基本步驟，采用標號法。可用兩種標號：T標號和P標號，T標號為了試探性的標號，P標號為了永久性標號，給Vi點到一個T標號時，是從Vs到Vi點的最短路權的上界，是一種臨時標號，凡沒有得到P標號的點都沒有T標號。算法每一步都把某一點的T標號改為P標號，當然點Vt得到P標號時，全部計算結束。對于有n個頂點的圖，最多進過n-1步驟就可以得到從始點到終點的最短路。步驟：（1）給Vs以P標號，P（s）=0,其余各點均給T標號，T（Vi）=+inf。 （2）若Vi點剛得到P標號的點，考慮這樣的點Vj：（Vi，Vj）屬于E，且Vj為T標號。但對于Vj的T標號進

19、行如下修改：T（Vj）=minT(Vj),P(vi)+Lij。 （3）比較所有具有T標號的點把最小者改為P標號，即：P（Vs')=minT（Vi）當存在兩個以上最小者時，可同時改為P標號。如全部點均為P標號則停止。否則用Vi'代Vi轉后（2）。6 結合所求目標，參照相關理論知識，網上收集資料整理得dijkstra算法程序見附件3。.3.3.4.2 Dijkstra程序MATLAB的實現 （1）根據附件2、圖1，對附件1的數據進行處理得到節點鄰接矩陣見附表3。 （2）依據附件2，將Dijkstra程序放入matlab安裝目錄的work文件夾。 （3）在MATLAB軟件的命令窗口輸

20、入“costmat=0 2.;tolcost,path = dijkstra2(costmat,1,25)”結果如下：（注：tolcost表示最短路權長，path表示最短路徑。) 1路：（下司 南站方向） tolcost = 11 path = 1 2 3 4 5 6 14 19 25 即：該公交線經過以下路段A1A2,A2A3,A3A4,A4A5，A5A6，A6A14，A14A19，A19A25，后面的path均這樣理解。 (4)把輸入命令改成“costmat=0 2.;tolcost,path = dijkstra2(costmat,9,25)結果顯示如下： 2路：（桃花村 南站方向） t

21、olcost = 14 path = 9 10 11 12 13 14 19 25 (5)同理可得到： 3路：（環城南路 南站方向） tolcost = 13 path = 20 21 22 23 24 19 25 4路：（學院 南站方向） tolcost = 3 path = 16 25 5路：（紅巖村 環城南路方向） tolcost = 10 path = 20 21 22 17 18 13 5 6路：（南站環線） 對于比較特殊6路公交線，我們單獨討論。參照附件1我們作出圖2如下圖2 是中國的一個優秀旅游城市，免不了有很多旅游者想游覽一下經濟開發區的面貌，考慮到這個情況。結合圖2對6路公交

22、線作如下設計： Path= 25 16 15 14 13 12 4 3 2 1 9 10 11 21 22 23 24 19 25這樣設計能為旅游者提供便宜的觀光交通工具，同時也能為沿線居民的出行提供方便。 對于上面的4路車，理論得出的行駛路徑過于精簡，根據實際客流情況、道路條件（A16點是一個大轉盤）與公共交通線路設計的一些原則，修改其行駛路徑為： Path= 16 8 7 14 15 16 25 這樣設計能減少公交盲區的面積，提高公交網絡的服務面積。3.3.4.3給出經濟開發區公交線網圖根據3.3.4.2的數據和圖1，描繪出經濟開發區公交線網圖3如下：圖34. 結果討論本文靈活采用圖論的知

23、識解決提出的問題，設計出的成果具有科學性，同時也結合凱利經濟開發區的實際情況，對計算出的理論結論進行了修正，更接近與實際情況。不足之處在于收集到得數據不夠全面，對于其中涉與到得一些條件，假設過于理想化，使得計算結果與現實條件有出入。該研究還很淺顯，公交系統是一個復雜的系統，其中包含很多子系統，以后我們可以進一步完善其每個子系統。如可在本文結論的基礎上研究每條公交線的公交站點的具體位置、可以根據以后客流量的數據對公交車的調度時間進一步確定，以與公交車輛的型號進行科學的選擇等等，最終達到一個完整科學的公交系統。5.結束語 公共交通系統是城市交通的發展趨勢，許多城市都有公交線路多達上百條，公交站點幾

24、百個以上。可見優先發展公共交通是解決城市交通問題的根本途徑，是城市交通可持續發展的必然選擇。公交網路布局規劃優化設計是一個系統過程，它包括公交線網優化、公交換乘優化、車輛配置優化、車輛調度優化和人員調度優化。本文主要利用圖論中最短路問題理論，以公交車在兩個目的地之間行駛路徑最短為目標，優化設計公交線網圖。為了使該公交線網更接近實際，將來經濟開發區公交車正式運營后，我們還必須采集相關數據，如每條道路的路面條件、每條公路的寬、以與每個起訖點的客流人數等，使假設的一些條件參數化，進步對所設計的公交線網圖進行修正。為公交網路的設計提供理論依據。有了相關數據后我們還可以對本文未完成的優化容進一步研究，使

25、該公交系統能更好地服務于經濟開發區。6.參考文獻 1 王煒，數學規劃方法在公交網絡優化中的應用J,數系統工程，1990.3,8 （3）：42-49。 2 王煒，一種簡便實用的公交網絡優化方法J，交通與計算機， 1990.3,40-47。 3 高自友、蔡金，求解城市交通連續平衡網絡設計問題的混合法J,北方交 通大學學報，2002.4,26（2），71-76。 4 林伯梁、富社、鵬，基于出行費用最小化的公交網絡優化模型J, 中國公路學報，1999.1,12（1），79-83。 5 超、彬，城市公共交通線網優化的圖論模型與算法J, 同濟大學學報：自然科學版，1998,26（3），294-298。6

26、胡運權、郭耀煌 運籌學教程（第三版）250-251。7.致 經過一段時間的奮斗，我的論文終于順利完成。首先衷心感我的指導老師余英和羅永超老師，他們從我的論文選題、理論分析以與論文撰寫等每個過程中都給我指導，論文的整個研究過程無不傾注著他們的心血和汗水，兩位老師利用課余時間，不辭辛勞，為我逐字修改論文，在此對兩位老師說一聲：老師，您辛苦了。 其次要感市經濟開發區建設局對我在論文資料收集時的大力幫助，你們提供的資料。 最后感在我論文寫作過程中，對我提供幫助的各位老師、同學和朋友，你們是我學習生涯中最美好的回憶，也是我人生中最寶貴的財富。8附件：(1)經濟開發區道路相關數據統計表。經濟開發區道路相關

27、數據統計道路名稱道路長（單位：米）沿線事業單位、公司等個數備注（道路長除500，然后小數部分四 舍五入）金匯路東A25-A161513163金匯路中段A12-A1788012金匯路中段A17-A2265201金匯路西A11-A21156163金匯路北A08-A1681232紅巖村路A7-A865621320國道A01-A02120022320國道A02-A0376512320國道A03-A0474061320國道A04-A0583512320國道A05-A0623020320國道A06-A0767011開司大道A09-A10156753開司大道A10-A11113052開司大道A11-A128

28、8852開司大道A12-A1397632開司大道A13-A1486752開司大道A14-A1580692開司大道A15-A16128993開司大道A16-學院1695143春暉路A06-A1463231春暉路A14-A19978142春暉路A19-A2556531高新路A08-A1542131高新路A15-A1978492高新路A19-A24193844第二園區干道A5-A1369521第二園區干道A13-A18104882第二園區干道A18-A2386912擺仰路A04-12101132銅新路A02-A10161013銅新路A10-A20249715環城西路A20-A21124902環城西路

29、A21-A22112402環城西路A22-A2372201環城西路A23-A24132503規劃路A01-A09152403未命名A07-A1443331未命名A17-A18654O1擺馬大道A03-A11152303附件2 dijkstra算法程序function tolcost,path = dijkstra2(costmat, s, f)% costmat為節點與節點所形成的臨接矩陣% s為起點% f為終點% tolcost為最短路徑長度% path為最短路徑m,n = size(costmat);if m = n error('Costmatrix must be a squa

30、re matrix.')end if any(diag(costmat)for i = 1:n costmat(i,i) = 0;end warning('Self connecting nodes are not allowed, ignoring the diagonal of Costmatrix.')endif nargin<3 f = 1:n;if nargin<2 s = 1:n;if nargin<1 error('Give a Costmatrix.')endendend if (length(s)=1 &&am

31、p; length(f)=1); ls = length(s); lf = length(f); tolcost = zeros(ls,lf);path = cell(ls,lf);for si = 1:lsfor fi = 1:lf tolcost(si,fi),pathsi,fi = dijkstra(costmat,s(si),f(fi);endendreturnendvisited = false(n,1);dist = inf(1,n);dist(s) = 0;prev = zeros(n,1);for i = 1:(n-1) temp = inf;for h = 1:nif visited(h) && dist(h)<temp temp = dist(h); u = h;endend visited(u) = true; % mark it as visited;for v = 1:n temp = costmat(u,v) + dist(u);if temp < dist(v) dist(v) = temp; % update the shortest dist