[發明專利]適用于大規模交通流仿真的虛擬車輛路由方法

有效

• 申請號: 201110002566.4
• 申請日: 2011-01-07
• 公開（公告）號: CN102054355A
• 公開（公告）日: 2011-05-11
• 發明（設計）人: 蔣昌俊;張棟良;陳閎中;閆春鋼;丁志軍;張亞英
• 申請（專利權）人: 同濟大學
• 主分類號: G08G1/00
• 分類號: G08G1/00;G06F17/50
• 代理公司: 上海光華專利事務所 31219
• 代理人: 王松

技術領域

本發明屬于智能交通技術領域，涉及一種交通仿真方法，尤其涉及一種適用于大規模交通流仿真的虛擬車輛路由方法。

背景技術

在現有的交通仿真系統中仿真車輛往往不遵循最短路徑行駛，或是隨機行駛，或是在交叉口按流量分配進行選擇性轉彎，這些仿真方法中車輛的行駛都不是“理性”的行為，單獨跟蹤一輛仿真車輛，往往會出現車輛在小范圍“轉圈”現象，這對于基于車輛理性行為的仿真試驗非常不利，如考察一個路段受阻情況下交通流的變化情況時無法得到正確結果。因此，仿真系統中的車輛應當以理性方式(最短路徑)行駛。

但是，在大范圍路網內對大量車輛的最短路徑的計算相當耗時，尤其是在系統初始化時，數十萬輛車的行駛路線計算使得用戶陷入長時間等待。針對這種現象，有人提出路徑預存法：事先將一部分具有代表性的路徑存在服務器內形成路徑庫，當車輛要產生是從路徑庫調出，直接賦予車輛，節省計算路徑的時間。但是要形成具有代表性的路徑庫需要大量的存儲空間，因為在上萬個節點的路網上全部的路徑數目要以億計甚至幾十億計，而每一個路徑平局長度有幾百個路段長。在這種情況下即使預存十分之一的路徑存儲上也是不可接受的。

發明內容

本發明所要解決的技術問題是：提供一種適用于大規模交通流仿真的虛擬車輛路由方法，能夠顯著的節省計算時間。

為解決上述技術問題，本發明采用如下技術方案：

一種適用于大規模交通流仿真的虛擬車輛路由方法，所述方法包括：

將路徑以下一跳的標示方法存入每個節點的路由表；

車輛行駛到每個節點時，查詢該節點的路由表；若在該表中可查詢到欲到達目的地的下一跳節點ID，則按此目標移動，從而實現整個路由；否則計算整條路徑，并將路徑分解存儲到各個相關的路由表。

作為本發明的一種優選方案，在路由表的生成與更新使用分布式的求解方式，將路網按處理機數目分割，每臺處理機處理局部路由表，再由多臺處理機交互合成路由表可以加速全局路網路由表的計算。

作為本發明的一種優選方案，如果A節點與B節點之間的道路發生中斷，則分別進行以A節點為源點和以B節點為源點的Dijkstra操作。

作為本發明的一種優選方案，所述Dijkstra操作包括如下步驟：

A1、處理、歸并線路；

A2、確定所有線路的端點ID；

A3、判斷所有線路是否均處理完畢，若是則轉步驟A6；否則轉步驟A4；

A4、提取一條線路；

A5、添加該線路信息至路由表，轉步驟A3；

A6、結束。

本發明的有益效果在于：本發明提出的適用于大規模交通流仿真的虛擬車輛路由方法，利用查表方式，減少重復路徑計算，能夠顯著的節省大量車輛的最短路徑計算時間，其原因是，先計算的路徑結果往往可以被后面的計算所利用。

同時，本發明利用表的動態變化表征動態路況，在動態路網路徑計算方面這種方法也有著很大的優勢；因為在這種路徑查詢模式下，最優路徑的更新完全取決于路由表的定期更新，其更新模式與計算機網絡路由更新機制類似。

附圖說明

圖1為Dijkstra子函數的流程圖。

圖2為一個簡單的最短路徑示意圖。

圖3為在路由表上更新更改的道路兩端節點信息示意圖。

圖4為路網與路由表示意圖。

圖5為50個仿真周期內，每個周期內用于計算路徑的耗時比較示意圖。

具體實施方式

下面結合附圖詳細說明本發明的優選實施例。

實施例一

本發明提出模仿計算機網絡路由模式，將路徑以下一跳的標示方法存入每個節點的路由表。車輛行駛到每個節點時，查詢該節點的路由表，在該表中可查詢到欲到達目的地的下一跳節點ID，從而實現整個路由。如圖1所示。

具體做法是：首先選定一對OD點，察看O點路由表中是否有D點的下一跳信息，如果有按此目標移動，否則計算整條路徑，并將路徑分解存儲到各個相關的路由表。

這種路徑生成算法的最大優點是能夠顯著的節省大量車輛的最短路徑計算時間，其原因是，先計算的路徑結果往往可以被后面的計算所利用。

在動態路網路徑計算方面這種方法也有著很大的優勢。因為在這種路徑查詢模式下，最優路徑的更新完全取決于路由表的定期更新，其更新模式與計算機網絡路由更新機制類似。

此外在路由表的生成與更新上很適合與分布式的求解方式，將路網按處理機數目分割，每臺處理機處理局部路由表，再由多臺處理機交互合成路由表可以加速全局路網路由表的計算。