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

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

【部分圖文】：

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

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

圖4請(qǐng)求r′的k近鄰與孤立點(diǎn)

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

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

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

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

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

本文編號(hào)：3936267