[發(fā)明專利]一種城市可達(dá)區(qū)域搜索系統(tǒng)及方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010053825.5
• 申請(qǐng)日: 2020-01-17
• 公開（公告）號(hào): CN111222059B
• 公開（公告）日: 2023-03-28
• 發(fā)明（設(shè)計(jì)）人: 孫鶴立;張優(yōu)優(yōu);楊洲;何亮;黃健斌;陳積銀;賈曉琳
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué);西安交通大學(xué)深圳研究院
• 主分類號(hào): G06F16/9537
• 分類號(hào): G06F16/9537;G06Q50/26
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 馬貴香

1.一種城市可達(dá)區(qū)域搜索系統(tǒng)，其特征在于，包括：

數(shù)據(jù)采集模塊，用于獲取地圖網(wǎng)絡(luò)數(shù)據(jù)和軌跡數(shù)據(jù)；

數(shù)據(jù)映射模塊，用于將軌跡數(shù)據(jù)映射到地圖網(wǎng)絡(luò)數(shù)據(jù)的道路網(wǎng)絡(luò)中，得到各條城市道路對(duì)應(yīng)的歷史軌跡；

道路權(quán)重計(jì)算模塊，用于將歷史軌跡按照時(shí)間特征分塊計(jì)算道路段速度的均值與方差；最后利用均值與方差和道路速度分布函數(shù)將搜索輸入的概率映射為相應(yīng)的速度，從而計(jì)算出道路段的時(shí)間權(quán)重；

層級(jí)跳躍表生成模塊，用于根據(jù)預(yù)定時(shí)刻道路段的時(shí)間權(quán)重和道路網(wǎng)絡(luò)數(shù)據(jù)，計(jì)算預(yù)定時(shí)刻預(yù)定間間隔內(nèi)從某一地點(diǎn)可達(dá)的區(qū)域集合，并將多種時(shí)刻與多種時(shí)間粒度的可達(dá)區(qū)域集合同時(shí)進(jìn)行記錄存儲(chǔ)，生成層級(jí)跳躍表；

時(shí)間線段樹索引模塊，用于為層級(jí)跳躍表建立查詢索引，根據(jù)查詢索引獲取道路信息，進(jìn)而得到城市可達(dá)區(qū)域；

可達(dá)區(qū)域搜索模塊，用于根據(jù)用戶輸入的概率、起始位置、起始時(shí)間和時(shí)間間隔，使用時(shí)間線段樹索引在道路網(wǎng)絡(luò)中進(jìn)行迭代搜索，最終輸出可達(dá)區(qū)域集合。

2.根據(jù)權(quán)利要求1所述的一種城市可達(dá)區(qū)域搜索系統(tǒng)，其特征在于，數(shù)據(jù)采集模塊從地圖數(shù)據(jù)庫(kù)和軌跡數(shù)據(jù)庫(kù)中分別獲取地圖網(wǎng)絡(luò)數(shù)據(jù)和軌跡數(shù)據(jù)；所述地圖網(wǎng)絡(luò)數(shù)據(jù)是指城市的路網(wǎng)數(shù)據(jù)，包括代表交叉路口的節(jié)點(diǎn)和代表道路段的邊；所述的軌跡數(shù)據(jù)是由連續(xù)的帶時(shí)間戳的GPS點(diǎn)構(gòu)成，每個(gè)GPS點(diǎn)包含經(jīng)度、維度和時(shí)間戳這三個(gè)維度的數(shù)據(jù)。

3.根據(jù)權(quán)利要求1所述的一種城市可達(dá)區(qū)域搜索系統(tǒng)，其特征在于，層級(jí)跳躍表生成模塊的工作過(guò)程包括：

根據(jù)預(yù)定時(shí)刻道路段的時(shí)間權(quán)重和道路網(wǎng)絡(luò)數(shù)據(jù)，生成帶權(quán)特征圖，然后使用帶早停策略和堆優(yōu)化策略的dijkstra算法分別得到預(yù)設(shè)時(shí)間間隔內(nèi)從某一地點(diǎn)可達(dá)的區(qū)域集合；

利用預(yù)設(shè)時(shí)間間隔內(nèi)從某一地點(diǎn)可達(dá)的區(qū)域集合，分別預(yù)設(shè)的不同的時(shí)間間隔參數(shù)下計(jì)算可達(dá)區(qū)域集合，并將計(jì)算結(jié)果連接為層級(jí)跳躍表。

4.根據(jù)權(quán)利要求3所述的一種城市可達(dá)區(qū)域搜索系統(tǒng)，其特征在于，所述早停策略為在帶權(quán)特征圖中進(jìn)行預(yù)設(shè)時(shí)間間隔的可達(dá)區(qū)域集合計(jì)算過(guò)程中，使用該預(yù)設(shè)時(shí)間間隔作為區(qū)域擴(kuò)張的額外約束，加快可達(dá)區(qū)域集合計(jì)算的速度。

5.根據(jù)權(quán)利要求1所述的一種城市可達(dá)區(qū)域搜索系統(tǒng)，其特征在于，時(shí)間線段樹索引模塊包括時(shí)間線段樹的建立模塊和時(shí)間線段樹的查詢模塊：

時(shí)間線段樹的建立模塊用于根據(jù)生成的層級(jí)跳躍表建立時(shí)間線段樹索引結(jié)構(gòu)；

時(shí)間線段樹的查詢模塊根據(jù)用戶輸入的時(shí)間間隔在時(shí)間線段樹中查詢對(duì)應(yīng)的樹中節(jié)點(diǎn)所存儲(chǔ)的道路信息，獲取城市可達(dá)區(qū)域。

6.一種城市可達(dá)區(qū)域搜索方法，其特征在于，包括如下步驟：

S1，獲取地圖網(wǎng)絡(luò)數(shù)據(jù)和軌跡數(shù)據(jù)；

S2，將軌跡數(shù)據(jù)映射到地圖網(wǎng)絡(luò)數(shù)據(jù)的道路網(wǎng)絡(luò)中，得到各條城市道路對(duì)應(yīng)的歷史軌跡；

S3，將歷史軌跡按照時(shí)間特征分塊計(jì)算道路段速度的均值與方差；最后利用均值與方差和道路速度分布函數(shù)將搜索輸入的概率映射為相應(yīng)的速度，從而計(jì)算出道路段的時(shí)間權(quán)重；

S4，根據(jù)預(yù)定時(shí)刻道路段的時(shí)間權(quán)重和道路網(wǎng)絡(luò)數(shù)據(jù)，計(jì)算預(yù)定時(shí)刻預(yù)定間間隔內(nèi)從某一地點(diǎn)可達(dá)的區(qū)域集合，并將多種時(shí)刻與多種時(shí)間粒度的可達(dá)區(qū)域集合同時(shí)進(jìn)行記錄存儲(chǔ)，生成層級(jí)跳躍表；

S5，為層級(jí)跳躍表建立查詢索引，根據(jù)查詢索引獲取道路信息，進(jìn)而得到城市可達(dá)區(qū)域；

S6，根據(jù)用戶輸入的概率、起始位置、起始時(shí)間和時(shí)間間隔，使用時(shí)間線段樹索引在道路網(wǎng)絡(luò)中進(jìn)行迭代搜索，最終輸出可達(dá)區(qū)域集合。

7.根據(jù)權(quán)利要求6所述的一種城市可達(dá)區(qū)域搜索方法，其特征在于，S1中，從地圖數(shù)據(jù)庫(kù)和軌跡數(shù)據(jù)庫(kù)中分別獲取地圖網(wǎng)絡(luò)數(shù)據(jù)和軌跡數(shù)據(jù)；所述地圖網(wǎng)絡(luò)數(shù)據(jù)是指城市的路網(wǎng)數(shù)據(jù)，包括代表交叉路口的節(jié)點(diǎn)和代表道路段的邊；所述的軌跡數(shù)據(jù)是由連續(xù)的帶時(shí)間戳的GPS點(diǎn)構(gòu)成，每個(gè)GPS點(diǎn)包含經(jīng)度、維度和時(shí)間戳這三個(gè)維度的數(shù)據(jù)。