[發(fā)明專利]一種滿足活動(dòng)需求和路徑最優(yōu)的出行導(dǎo)航方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010259794.5
• 申請(qǐng)日: 2010-08-20
• 公開（公告）號(hào): CN101995255A
• 公開（公告）日: 2011-03-30
• 發(fā)明（設(shè)計(jì)）人: 楊敏;王煒;陳學(xué)武;陳景旭;范會(huì)川
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)
• 主分類號(hào): G01C21/26
• 分類號(hào): G01C21/26;G01C21/34
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 黃雪蘭

1.一種滿足活動(dòng)需求和路徑最優(yōu)的出行導(dǎo)航方法，其特征在于：

步驟1：普通個(gè)體出行者根據(jù)自己出行的實(shí)際需要建立初始活動(dòng)安排，列出出行的具體活動(dòng)、活動(dòng)地點(diǎn)限制條件和時(shí)間約束條件，所述的活動(dòng)地點(diǎn)限制條件是出行者根據(jù)自身的實(shí)際需求對(duì)活動(dòng)的地點(diǎn)屬性進(jìn)行的組合，包括(1)活動(dòng)地點(diǎn)的地理位置符合出行者的要求，(2)活動(dòng)地點(diǎn)的等級(jí)和規(guī)模達(dá)到出行者的規(guī)定水平，(3)活動(dòng)地點(diǎn)周圍1km范圍內(nèi)有出行者指定的設(shè)施，所述的時(shí)間約束條件是指出行者根據(jù)自身的實(shí)際需求對(duì)活動(dòng)的時(shí)間屬性進(jìn)行的組合，包括(1)活動(dòng)的起始時(shí)間，(2)活動(dòng)的終止時(shí)間，

步驟2：結(jié)合當(dāng)天的活動(dòng)和地點(diǎn)限制條件，尋找到能夠滿足出行者活動(dòng)需要的活動(dòng)地點(diǎn)，從中提取出可供選擇的活動(dòng)地點(diǎn)集合，

步驟3：確定定點(diǎn)活動(dòng)對(duì)數(shù)目，結(jié)合時(shí)間約束條件，利用啟發(fā)式搜索算法得到每個(gè)定點(diǎn)活動(dòng)對(duì)內(nèi)的最優(yōu)地點(diǎn)，并將所述的最優(yōu)地點(diǎn)作為非定點(diǎn)活動(dòng)地點(diǎn)，同時(shí)得到每個(gè)定點(diǎn)活動(dòng)對(duì)內(nèi)各活動(dòng)對(duì)的最優(yōu)出行路徑，從而確定出行者當(dāng)天所有的活動(dòng)地點(diǎn)和出行路徑，

步驟4：利用地理信息系統(tǒng)GIS作為技術(shù)平臺(tái)，根據(jù)步驟3中得到的最優(yōu)活動(dòng)地點(diǎn)和最優(yōu)出行路徑對(duì)個(gè)體出行者進(jìn)行導(dǎo)航；

可供選擇的活動(dòng)地點(diǎn)集合采用如下方法來(lái)確定：

將出行者活動(dòng)安排的活動(dòng)數(shù)目m作為循環(huán)總次數(shù)，對(duì)出行者當(dāng)天安排的活動(dòng)做時(shí)間排序并標(biāo)號(hào)，用i表示活動(dòng)的序號(hào)，其中1≤i≤m，假定出行起點(diǎn)和終點(diǎn)均為定點(diǎn)，依次對(duì)已做好排序標(biāo)號(hào)的活動(dòng)進(jìn)行活動(dòng)地點(diǎn)的提取，具體措施如下：

步驟A1)選擇出行起始點(diǎn)作為第一個(gè)定點(diǎn)，選取第一個(gè)活動(dòng)，即令i＝1，轉(zhuǎn)入步驟A2)；

步驟A2)判斷活動(dòng)的活動(dòng)地點(diǎn)類型，如果活動(dòng)是定點(diǎn)活動(dòng)，選取下一個(gè)活動(dòng)，即i＝i+1，轉(zhuǎn)入步驟A4)；如果是非定點(diǎn)活動(dòng)，則轉(zhuǎn)入步驟A3)；

步驟A3)用j表示非定點(diǎn)活動(dòng)i的活動(dòng)地點(diǎn)，將出行者規(guī)定的非定點(diǎn)活動(dòng)的活動(dòng)地點(diǎn)提取數(shù)n作為每個(gè)非定點(diǎn)活動(dòng)的循環(huán)總次數(shù)，選取活動(dòng)i的第一個(gè)活動(dòng)地點(diǎn)，即j＝1，判斷是否滿足活動(dòng)的地點(diǎn)限制條件，如果不滿足地點(diǎn)限制條件，則繼續(xù)選擇下一個(gè)活動(dòng)地點(diǎn)，即j＝j(luò)+1；如果滿足地點(diǎn)限制條件，則將活動(dòng)地點(diǎn)j加入活動(dòng)i的可選活動(dòng)地點(diǎn)集合，并繼續(xù)選擇下一個(gè)活動(dòng)地點(diǎn)，即j＝j(luò)+1，當(dāng)活動(dòng)地點(diǎn)數(shù)目達(dá)到了n時(shí)，活動(dòng)i的活動(dòng)地點(diǎn)提取完成，令i＝i+1，轉(zhuǎn)入步驟A4)；

步驟A4)當(dāng)活動(dòng)i的序號(hào)值達(dá)到了出行者活動(dòng)安排的活動(dòng)數(shù)目m時(shí)，循環(huán)結(jié)束，表示整個(gè)可供選擇的活動(dòng)地點(diǎn)集合提取完畢；否則，返回步驟A2)；

確定最優(yōu)活動(dòng)地點(diǎn)和出行路徑采用如下方法：

將出行者活動(dòng)安排的活動(dòng)數(shù)目m作為循環(huán)總次數(shù)，對(duì)出行者當(dāng)天安排的活動(dòng)做時(shí)間排序并標(biāo)號(hào)，用i表示活動(dòng)的序號(hào)，其中1≤i≤m，假定出行起點(diǎn)和終點(diǎn)均為定點(diǎn)，將相鄰兩個(gè)活動(dòng)組成活動(dòng)對(duì)，并將出行起點(diǎn)和第一個(gè)活動(dòng)作為活動(dòng)對(duì)處理，將相鄰兩個(gè)定點(diǎn)活動(dòng)組成至少包括一個(gè)活動(dòng)對(duì)的定點(diǎn)活動(dòng)對(duì)，用f(k)表示定點(diǎn)活動(dòng)對(duì)的最小出行時(shí)間，其中k為定點(diǎn)活動(dòng)對(duì)中的后一個(gè)活動(dòng)的標(biāo)號(hào)，用F表示定點(diǎn)活動(dòng)對(duì)中后一個(gè)活動(dòng)k之前的所有定點(diǎn)活動(dòng)對(duì)的最小出行時(shí)間的總和，具體措施如下：

步驟B1)令F初始值為0，選擇出行起點(diǎn)，將出行起點(diǎn)作為第一個(gè)定點(diǎn)，判斷第一個(gè)活動(dòng)是否為定點(diǎn)活動(dòng)，即i＝1。如果是定點(diǎn)活動(dòng)，則轉(zhuǎn)入步驟B3)；如果是非定點(diǎn)活動(dòng)，將該非定點(diǎn)活動(dòng)與第一個(gè)定點(diǎn)當(dāng)作活動(dòng)對(duì)，確定該非定點(diǎn)活動(dòng)的可選活動(dòng)地點(diǎn)集合中的地點(diǎn)與出行起點(diǎn)間的出行時(shí)間，轉(zhuǎn)入步驟B5)，

步驟B2)如果當(dāng)前活動(dòng)對(duì)中的后一個(gè)活動(dòng)是定點(diǎn)活動(dòng)，則轉(zhuǎn)入步驟B3)；如果當(dāng)前活動(dòng)對(duì)中的后一個(gè)活動(dòng)是非定點(diǎn)活動(dòng)，確定該非定點(diǎn)活動(dòng)與前一個(gè)活動(dòng)組成的活動(dòng)對(duì)中各活動(dòng)地點(diǎn)間的出行時(shí)間，轉(zhuǎn)入步驟B5)，

步驟B3)結(jié)合活動(dòng)的時(shí)間約束條件，利用啟發(fā)式搜索算法得到這個(gè)定點(diǎn)活動(dòng)與前面最近的一個(gè)定點(diǎn)間的最優(yōu)出行路徑，此時(shí)f(k)為最小值，在F值中加入f(k)的值，轉(zhuǎn)入步驟B4)，

步驟B4)如果當(dāng)前活動(dòng)i是出行終點(diǎn)，則循環(huán)結(jié)束，得到當(dāng)前出行路徑最優(yōu)的一組活動(dòng)地點(diǎn)，此時(shí)的F值為最優(yōu)出行路徑對(duì)應(yīng)的出行時(shí)間；如果當(dāng)前活動(dòng)i不是出行終點(diǎn)，轉(zhuǎn)入步驟B5)，

步驟B5)將當(dāng)前活動(dòng)作為下一個(gè)活動(dòng)對(duì)的前一個(gè)活動(dòng)，令i＝i+1，轉(zhuǎn)入步驟B2)。

2.根據(jù)權(quán)利要求1所述的滿足活動(dòng)需求和路徑最優(yōu)的出行導(dǎo)航方法，其特征在于，步驟B3)所述的啟發(fā)式搜索算法的具體實(shí)現(xiàn)過程如下：

步驟B3.1)建立兩個(gè)表，Open表用于存放非定點(diǎn)活動(dòng)地點(diǎn)和當(dāng)前定點(diǎn)活動(dòng)對(duì)的后一個(gè)定點(diǎn)活動(dòng)地點(diǎn)，Close表用于存放當(dāng)前定點(diǎn)活動(dòng)對(duì)的前一個(gè)定點(diǎn)活動(dòng)地點(diǎn)，

步驟B3.2)將出行起點(diǎn)和第一個(gè)活動(dòng)作為活動(dòng)對(duì)處理，如果第一個(gè)活動(dòng)是定點(diǎn)活動(dòng)，則轉(zhuǎn)入步驟B3.4)；如果第一個(gè)活動(dòng)是非定點(diǎn)活動(dòng)，則對(duì)第一個(gè)活動(dòng)中各個(gè)可選活動(dòng)地點(diǎn)做標(biāo)記，標(biāo)記值為各個(gè)活動(dòng)地點(diǎn)與出行起點(diǎn)間的出行時(shí)間，標(biāo)記完成后，將第一個(gè)活動(dòng)的活動(dòng)地點(diǎn)從Open表放入Close表中，并將第一個(gè)活動(dòng)作為下一個(gè)活動(dòng)對(duì)的前一個(gè)非定點(diǎn)活動(dòng)，并找出下一個(gè)活動(dòng)對(duì)的后一個(gè)活動(dòng)，如果后一個(gè)活動(dòng)是定點(diǎn)活動(dòng)，則轉(zhuǎn)入步驟B3.4)；如果后一個(gè)活動(dòng)是非定點(diǎn)活動(dòng)，則將后一個(gè)活動(dòng)作為當(dāng)前非定點(diǎn)活動(dòng)，轉(zhuǎn)入步驟B3.3a)，

步驟B3.3a)從當(dāng)前非定點(diǎn)活動(dòng)的可選活動(dòng)地點(diǎn)集合中任選一個(gè)地點(diǎn)作為當(dāng)前活動(dòng)地點(diǎn)并對(duì)當(dāng)前活動(dòng)地點(diǎn)進(jìn)行標(biāo)記，再?gòu)那耙粋€(gè)非定點(diǎn)活動(dòng)的可選活動(dòng)地點(diǎn)集合中任選一個(gè)活動(dòng)地點(diǎn)作為前一活動(dòng)地點(diǎn)，將當(dāng)前活動(dòng)地點(diǎn)與前一活動(dòng)地點(diǎn)之間的出行時(shí)間與前一活動(dòng)地點(diǎn)的標(biāo)記值的和作為當(dāng)前活動(dòng)地點(diǎn)的一個(gè)候選標(biāo)記值，

步驟B3.3b)重復(fù)步驟B3.3a)，得到當(dāng)前活動(dòng)地點(diǎn)的第二個(gè)候選標(biāo)記值、第三個(gè)候選標(biāo)記值、……，直到得到當(dāng)前活動(dòng)地點(diǎn)的所有候選標(biāo)記值，再?gòu)乃泻蜻x標(biāo)記值選擇出最小的候選標(biāo)記值，并將所選的最小的候選標(biāo)記值作為當(dāng)前活動(dòng)地點(diǎn)的標(biāo)記值，將所選的最小的候選標(biāo)記值所對(duì)應(yīng)的活動(dòng)地點(diǎn)的前一個(gè)活動(dòng)標(biāo)記為最優(yōu)地點(diǎn)，標(biāo)記完成后，將當(dāng)前非定點(diǎn)活動(dòng)的可選活動(dòng)集合的地點(diǎn)從Open表放入Close表中，并將當(dāng)前非定點(diǎn)活動(dòng)轉(zhuǎn)化為前一個(gè)非定點(diǎn)活動(dòng)，同時(shí)也作為下一個(gè)活動(dòng)對(duì)的前一個(gè)活動(dòng)，并找出下一個(gè)活動(dòng)對(duì)的后一個(gè)活動(dòng)，如果后一個(gè)活動(dòng)是定點(diǎn)活動(dòng)，則轉(zhuǎn)入步驟B3.4)；如果后一個(gè)活動(dòng)是非定點(diǎn)活動(dòng)，則將后一個(gè)活動(dòng)作為當(dāng)前非定點(diǎn)活動(dòng)，轉(zhuǎn)入步驟B3.3a)，

步驟B3.4)將定點(diǎn)活動(dòng)對(duì)的后一個(gè)定點(diǎn)活動(dòng)的標(biāo)記值定為定點(diǎn)活動(dòng)對(duì)的出行時(shí)間的最小值，并將定點(diǎn)活動(dòng)對(duì)的后一個(gè)定點(diǎn)活動(dòng)的前面一個(gè)活動(dòng)中所有候選標(biāo)記值里取最小值的地點(diǎn)作為最優(yōu)地點(diǎn)，將定點(diǎn)活動(dòng)從Open表放入Close表中，此時(shí)，Open表為空，標(biāo)記全部完成。從定點(diǎn)活動(dòng)對(duì)的后一個(gè)活動(dòng)反向追蹤定點(diǎn)活動(dòng)對(duì)中的前一定點(diǎn)活動(dòng)與后一定點(diǎn)活動(dòng)之間的每一個(gè)非定點(diǎn)活動(dòng)的最優(yōu)地點(diǎn)，最優(yōu)地點(diǎn)間取出行時(shí)間最短的路徑作為最優(yōu)出行路徑。