交通規(guī)劃課程設(shè)計--利用dijkstra算法與floyd算法進行交通分配

1、<p>　　利用Dijkstra算法與Floyd算法進行交通分配</p><p><b>　　比較分配結(jié)果</b></p><p>　　摘要：本文主要內(nèi)容包括對烏魯木齊市五區(qū)的人民進行OD調(diào)查，得到網(wǎng)絡(luò)交通量數(shù)據(jù)，再利用Dijkstra算法與Floyd算法確定交通網(wǎng)絡(luò)圖的最短路徑，運用全有全無的方法進行交通量的分配，最后比較這兩種方法在確定最短路徑時的利弊。

2、</p><p><b>　　關(guān)鍵詞：</b></p><p>　　Using the algorithm of Dijkstra and Floyd to distribute the volume of traffic and compare the result of the traffic assignment</p><p>　　Ab

3、stract: The article takes the main point to use the algorithm of Dijkstra and Floyd to decide the shortest way of traffic network , making use of the method of All-or-none to distribute the volume of traffic. At last,com

4、paring the advantages and disadvantages between the two methods during deciding the shortest way.</p><p><b>　　Key word:</b></p><p><b>　　0．引言：</b></p><p>　　隨著

5、科學(xué)技術(shù)的進步和工業(yè)的發(fā)展，城市中交通量激增，城市道路交通擁堵和環(huán)境污染現(xiàn)象越來越嚴重，對人民的出行和生活帶來了很大的不便和危害，私人交通工具發(fā)展的結(jié)果，給城市交通帶來了一系列的問題，主要是：①交通擁擠和交通阻塞，城市中的平均車速日益下降;②交通事故增加；③噪聲和空氣污染日趨嚴重;④能源消耗量猛增；⑤停放車場地嚴重不足。為了克服這些矛盾，一些工業(yè)發(fā)達的國家，曾致力于道路系統(tǒng)的改善：加寬地面道路，修建高架路和高速路，開辟地下交通。此外，在

6、交通管理、交通控制系統(tǒng)方面采用了計算機等新技術(shù)。這些措施雖然提高了道路通過能力，但是仍解決不了由有增無減的私人交通流所造成的道路阻塞問題。就道路交通擁堵問題，這里運用Dijkstra算法與Floyd算法確定交通網(wǎng)絡(luò)的最短路徑，并用全有全無的方法進行交通量得分配，最后比較這兩種方法在確定最短路徑時的難易程度。</p><p>　　1．規(guī)劃區(qū)社會經(jīng)濟發(fā)展概況</p><p>　　1.1 烏魯木

7、齊是新疆維吾爾自治區(qū)首府，全疆政治、經(jīng)濟、文化中心，也是第二座亞歐大陸橋中國西部橋頭堡和我國向西開放的重要門戶。她地處亞歐大陸中心，天山山脈中段北麓，準噶爾盆地南緣。烏魯木齊經(jīng)濟建設(shè)長足進步。改革開放以來，特別是國家實施西部大開發(fā)戰(zhàn)略以來，烏魯木齊經(jīng)濟建設(shè)取得了前所未有的成就。以國有企業(yè)為中心的各項改革取得顯著成效，建立和完善了社會主義市場經(jīng)濟體制，全方位的開放開發(fā)格局初步形成。經(jīng)濟結(jié)構(gòu)戰(zhàn)略性調(diào)整取得實質(zhì)性進展，經(jīng)濟技術(shù)開發(fā)區(qū)、高新技術(shù)

8、產(chǎn)業(yè)開發(fā)區(qū)和區(qū)級經(jīng)濟成為新的經(jīng)濟增長點，公有制為主體、混合所有制經(jīng)濟共同發(fā)展的格局基本形成。農(nóng)村經(jīng)濟穩(wěn)步發(fā)展，農(nóng)業(yè)結(jié)構(gòu)調(diào)整力度加大。工業(yè)結(jié)構(gòu)調(diào)整繼續(xù)深化，高新技術(shù)產(chǎn)業(yè)產(chǎn)值的比重不斷提高。城市基礎(chǔ)設(shè)施功能不斷完善，建成了以中山路商業(yè)一條街、人民路金融一條街、二道橋民俗一條街和北京路科技一條街為主要代表的、各具特色的城市功能街區(qū)。新疆商貿(mào)城、中國新疆小商品城、新疆國際大巴扎、華凌、友好百盛等一批地方特色市場和大型超市相繼建成，逐步形成了火車

9、南站、二道橋、中山路、大西門、鐵路局等各具特色、初具規(guī)模的商業(yè)圈，肯德基、普爾斯瑪特、世紀金花、百盛、家樂</p><p>　　1.2烏魯木齊市人口總數(shù)年統(tǒng)計數(shù)據(jù)分析</p><p>　　1.2.1沙依巴克區(qū)2010年人口預(yù)測</p><p>　　1.2.2天山區(qū)2010年人口預(yù)測</p><p>　　1.2.3水磨溝區(qū)2010年人口預(yù)測&l

10、t;/p><p>　　1.2.4新市區(qū)2010年人口預(yù)測</p><p>　　1.2.5米東新區(qū)2010年人口預(yù)測</p><p>　　1.2.6五區(qū)2010年人口預(yù)測為：</p><p>　　1.3烏魯木齊市國民生產(chǎn)總值年統(tǒng)計數(shù)據(jù)分析</p><p>　　1.3.1沙依巴克區(qū)2010年國民生產(chǎn)總值預(yù)測</p>

11、<p>　　1.3.2天山區(qū)2010年國民生產(chǎn)總值預(yù)測</p><p>　　1.3.3水磨溝區(qū)2010年國民生產(chǎn)總值預(yù)測</p><p>　　1.3.4新市區(qū)2010年國民生產(chǎn)總值預(yù)測</p><p>　　1.3.5米東新區(qū)2010年國民生產(chǎn)總值預(yù)測</p><p>　　1.3.6五區(qū)2010年國民生產(chǎn)總值預(yù)測為：</p&

12、gt;<p>　　1.4 由以上兩個折線圖可以看書，烏魯木齊五區(qū)的人口與國民生產(chǎn)總值在不斷提高，人民生活質(zhì)量日益增加。烏魯木齊居民在食品消費上逐步向營養(yǎng)、科學(xué)、多樣化方向發(fā)展，居民的飲食更多地追求食品的口感、方便和營養(yǎng)，以此也拉動了食品消費的支出，三季度人均月食品支出達到了207.12元，同比增長了9.17％。衣著消費方面，居民所追求的檔次高了，三季度居民家庭人均月衣著支出59.07元，同比增長11.15％。 同時，通信業(yè)

13、的飛速發(fā)展，激發(fā)了人們對高科技信息產(chǎn)品和服務(wù)的需求渴望，引發(fā)消費熱潮，居民用于通訊方面的支出大幅增長。三季度，居民人均月通訊支出達到了39.26元，同比增長15.64％。</p><p><b>　　2 主要方法介紹</b></p><p>　　2.1 OD調(diào)查方法</p><p>　　2.1.1 OD調(diào)查即交通起止點調(diào)查又稱OD交通量調(diào)查，O

14、D交通量就是指起終點間的交通出行量。“O”來源于英文ORIGIN，指出行的出發(fā)地點，“D”來源于英文DESTINATION，指出行的目的地。</p><p>　　2.1.2 OD調(diào)查方法很多。在我國，客流OD調(diào)查多采用家訪調(diào)查，貨流調(diào)查多采用發(fā)收表調(diào)查。家訪調(diào)查是對居住在調(diào)查區(qū)內(nèi)的住戶，進行抽樣家訪。由調(diào)查員當面了解該戶中包括學(xué)齡前兒童在內(nèi)的6年以上（如北京1986年進行的個人出行調(diào)查）全體成員的詳細出行情況，包

15、括出發(fā)地、出發(fā)時間、目的地、到達目的地的時間、交通工具、出行目的、換乘情況、上車前后的步行時間等。這種調(diào)查方法數(shù)據(jù)可靠，而且還可同時得到出行者的個人屬性及社會經(jīng)濟特征資料。發(fā)收表調(diào)查是將調(diào)查表格發(fā)到卡車駕駛員處，由駕駛員逐項填寫。主要包括發(fā)時、抵時、貨種、載重、起止點路段名和單位名，經(jīng)過主要路口、里程等。事實證明，這兩種調(diào)查方法的調(diào)查效果都很好。此外還有路邊詢問調(diào)查、明信片調(diào)查、工作出行調(diào)查、車輛牌照調(diào)查、運輸集散點調(diào)查、公交線路乘客調(diào)

16、查、電話詢問調(diào)查等。每種方法都各有優(yōu)缺點，可根據(jù)實際情況加以選用，也可以同時采用幾種方法，以互補不足或互相校對。</p><p>　　2.2 Dijkstra算法</p><p>　　2.2.1Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法是很有代表性的最短

17、路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運籌學(xué)等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權(quán)邊。</p><p>　　2.2.2 Dijkstra算法思想為：設(shè)G=(V,E)是一個帶權(quán)有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S

18、表示，初始時S中只有一個源點，以后每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了），第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S

19、中的頂點為中間頂點的當前最短路徑長度。 　　</p><p>　　2.2.3 算法具體步驟　 　　</p><p>　?。?）初始時，S只包含源點，即S＝，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權(quán)（若v與u有邊）或 ）（若u不是v的出邊鄰接點）。 　?。?）從U中選取一個距離v最小的頂點k，把k，加入S中（該選定的距離就是v到k的最短路徑長度）。 　　</p&g

20、t;<p>　?。?）以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u（u U）的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。 　　</p><p>　　（4）重復(fù)步驟（2）和（3）直到所有頂點都包含在S中。</p><p>　　2.3 Floyd算法</p><p>　

21、　2.3.1 Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法。</p><p>　　2.3.2核心思路：通過一個圖的權(quán)值矩陣求出它的每兩點間的最短路徑矩陣。 　　從圖的帶權(quán)鄰接矩陣A=[a(i,j)] n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-

22、1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節(jié)點矩陣方向來記錄兩點間的最短路徑。</p><p>　　2.3.3 算法過程：把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=空值。 　　定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經(jīng)過的點，初

23、始化D[i,j]=j。把各個頂點插入圖中，比較插點后的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。 </p><p><b>　　3 分析模型建立　</b></p><p>　　3.1 OD調(diào)查方案<

24、;/p><p><b>　　居民出行調(diào)查</b></p><p><b>　　生活區(qū)</b></p><p>　　一、方法：家庭訪問法</p><p>　　二、定義：對調(diào)查區(qū)內(nèi)的家庭，按確定的抽樣率進行家庭訪問，多用于居民出行調(diào)查，調(diào)查員當面了解被調(diào)查戶中包括就學(xué)兒童在內(nèi)的家庭成員全天出行情況，家庭訪問

25、法是搜集居民出行資料最可靠的方法之一。</p><p>　　三、確定抽樣率：根據(jù)城市規(guī)模、人口和區(qū)域劃分，對居民進行抽樣調(diào)查，、烏魯木齊市人口數(shù)約兩百萬人，大于100萬人時按1/25抽樣，即共應(yīng)抽樣8萬人進行調(diào)查。</p><p><b>　　四、問卷設(shè)計</b></p><p>　　居民出行調(diào)查表（正面）</p><p&g

26、t;　　居民出行調(diào)查表（背面）</p><p>　　五、數(shù)據(jù)匯總（OD匯總表）</p><p>　　3.2繪圖及數(shù)據(jù)匯總處理</p><p>　　A代表沙依巴克區(qū)；B代表天山區(qū)；C代表水磨溝區(qū)；D代表新市區(qū)；E代表米東新區(qū)</p><p>　　調(diào)查表格發(fā)放8萬份，收回7萬9千6百余份，符合調(diào)查要求。</p><p>