傳統(tǒng)的路線規(guī)劃者通常專注于尋找路網上兩點之間距離最短的路線或花費時間最短的路線。然而,在實際情況下,特別是在智能城市的時代,許多與交通相關的數據可以被容易獲得,近幾年人們對基于不同標準進行路線規(guī)劃的需求不斷增加,例如在不超過給定的旅行時間預算(成本)的前提下,尋找一條累積風景值(效益值)最高的路線,這種問題可以看作弧定向問題(AOP)的變體,眾所周知,這是一個NP難問題。本文針對一個更為實際的AOP問題展開研究,其中,路網中各路段的效益值和通過路段的行駛時間具有時間依賴性,這個問題被定義為雙重時間依賴的弧定向問題(2TD-AOP)。在本文中,針對2TD-AOP展開了深入的研究,提出了兩個解決方案。首先,本文提出使用模因算法來解決2TD-AOP,具體而言,給定旅行時間預算,規(guī)劃了一條累積風景值(效益值)高的路線。這個過程大致分為兩個階段:初始化階段和局部搜索階段。在初始化階段,通過搜索區(qū)域縮減、染色體編碼和染色體解碼操作產生種群中的個體;在局部搜索階段,通過染色體選擇、交叉和變異操作提高了種群中個體的質量。通過種群的迭代使種群中優(yōu)秀個體所占的比例不斷提高,最終在不超過時間預算的前提下,選...

【文章頁數】：64 頁

【學位級別】：碩士

【部分圖文】：

圖2.2搜索區(qū)域縮減示例

重慶大學碩士學位論文2基于模因算法的雙重時間依賴的風景行車路線規(guī)劃方法11t0時刻車輛的平均速度。圓區(qū)域中包含的路段是從起點出發(fā)在時間預算內可達的路段，如圖2.2中所示左邊的圓。使用同樣的方式我們以終點為中心畫一個相同大小的圓，得到在t0時刻從在終點出發(fā)在時間預算內可達的路段。因....

圖2.3初始種群的生成Fig.2.3Thegenerationoftheinitialpopulation

重慶大學碩士學位論文2基于模因算法的雙重時間依賴的風景行車路線規(guī)劃方法11t0時刻車輛的平均速度。圓區(qū)域中包含的路段是從起點出發(fā)在時間預算內可達的路段，如圖2.2中所示左邊的圓。使用同樣的方式我們以終點為中心畫一個相同大小的圓，得到在t0時刻從在終點出發(fā)在時間預算內可達的路段。因....

圖2.4染色體編碼示例

重慶大學碩士學位論文2基于模因算法的雙重時間依賴的風景行車路線規(guī)劃方法13為了更好的理解每條染色體的編碼過程，我們給出了一個例子，如圖2.4所示，在初始化階段有效區(qū)域中有7條有效的風景路段（a,b,c,d,e,f,g），如圖2.4（a）所示，隨著染色體不斷的編碼，有效風景路段的數....

圖2.5染色體交叉Fig.2.5Chromosomecrossover

重慶大學碩士學位論文2基于模因算法的雙重時間依賴的風景行車路線規(guī)劃方法15個參數控制，即Pc和ρc，其中Pc是用戶指定的常數，通常稱作交叉概率；ρc是在[0,1]范圍內隨機生成的值，當Pc>ρc時，對選中的染色體執(zhí)行交叉操作。圖2.5染色體交叉Fig.2.5Chromosomec....

本文編號：3989700