工作者的路徑規(guī)劃問題是空間眾包中一個重要的研究內(nèi)容。當(dāng)前路徑規(guī)劃問題的研究主要集中在離線情形下,然而在線情形下的路徑規(guī)劃更符合現(xiàn)實需求。因此,該文從眾包物流和共享巴士等典型空間眾包平臺中提取出了一個在線路徑規(guī)劃問題——空間眾包中終點固定的在線路徑規(guī)劃問題。首先研究了Euclidean空間上的路徑規(guī)劃問題,提出了基于粒子群的在線粒子群路徑規(guī)劃算法,該算法通過在線追蹤最優(yōu)解來進行路徑規(guī)劃,同時,提出了基于k近鄰的在線局部粒子群路徑規(guī)劃算法。還研究了面向路網(wǎng)的路徑規(guī)劃問題,提出了加權(quán)最短路徑邊界索引和路網(wǎng)上的在線局部粒子群路徑規(guī)劃算法。最后,通過真實數(shù)據(jù)上的大量實驗驗證了上述算法的有效性和高效性,其中在線局部粒子群路徑規(guī)劃算法擁有更好的效果。

【文章頁數(shù)】：11 頁

【部分圖文】：

圖3離線路徑規(guī)劃圖

圖2在線粒子群路徑規(guī)劃算法過程2.2在線局部粒子群路徑規(guī)劃算法

圖4請求r′的k近鄰與孤立點

本文把請求r′的近鄰分為2種類型:一種是不產(chǎn)生孤立點的近鄰集合N,另一種是產(chǎn)生孤立點的近鄰集合Ν～。若請求r′的所有近鄰請求在原路徑p中是連續(xù)的,則稱r′的近鄰是不產(chǎn)生孤立點的近鄰集合N;否則稱r′的近鄰是產(chǎn)生孤立點的近鄰集合Ν～。事實上,孤立點也是一個....

圖6路網(wǎng)索引建立圖

區(qū)域劃分:首先頂點v與其距離至多為δ的鄰居頂點構(gòu)成一個區(qū)域,對路網(wǎng)進行區(qū)域覆蓋,其中頂點v為中心點。為了盡量減少區(qū)域的數(shù)量,將頂點按度排序,以頂點作為中心點開始廣度優(yōu)先遍歷進行區(qū)域劃分。圖6a中的路網(wǎng)可以按δ=5劃分為如圖所示的3個區(qū)域。首先對頂點按度排序得到頂點....

圖10參數(shù)對算法結(jié)果的影響

在4個數(shù)據(jù)集上對算法結(jié)果與執(zhí)行時間進行比較。采取控制變量的方式對參數(shù)進行選擇,其中組合1、組合2、組合3用來比較參數(shù)m不同取值的影響;組合1、組合4、組合5用來比較參數(shù)n不同取值的影響;組合1、組合6、組合7用來比較參數(shù)k不同取值的影響。實驗結(jié)果如圖10和1....

本文編號：3936267