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

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

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

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

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

8、產(chǎn)業(yè)開(kāi)發(fā)區(qū)和區(qū)級(jí)經(jīng)濟(jì)成為新的經(jīng)濟(jì)增長(zhǎng)點(diǎn)，公有制為主體、混合所有制經(jīng)濟(jì)共同發(fā)展的格局基本形成。農(nóng)村經(jīng)濟(jì)穩(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)城、中國(guó)新疆小商品城、新疆國(guó)際大巴扎、華凌、友好百盛等一批地方特色市場(chǎng)和大型超市相繼建成，逐步形成了火車(chē)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、始化D[i,j]=j。把各個(gè)頂點(diǎn)插入圖中，比較插點(diǎn)后的距離與原來(lái)的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點(diǎn)之間最短道路的信息，而在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>　　一、方法：家庭訪問(wèn)法</p><p>　　二、定義：對(duì)調(diào)查區(qū)內(nèi)的家庭，按確定的抽樣率進(jìn)行家庭訪問(wèn)，多用于居民出行調(diào)查，調(diào)查員當(dāng)面了解被調(diào)查戶中包括就學(xué)兒童在內(nèi)的家庭成員全天出行情況，家庭訪問(wèn)

25、法是搜集居民出行資料最可靠的方法之一。</p><p>　　三、確定抽樣率：根據(jù)城市規(guī)模、人口和區(qū)域劃分，對(duì)居民進(jìn)行抽樣調(diào)查，、烏魯木齊市人口數(shù)約兩百萬(wàn)人，大于100萬(wàn)人時(shí)按1/25抽樣，即共應(yīng)抽樣8萬(wàn)人進(jìn)行調(diào)查。</p><p><b>　　四、問(wèn)卷設(shè)計(jì)</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萬(wàn)份，收回7萬(wàn)9千6百余份，符合調(diào)查要求。</p><p>