[發(fā)明專利]動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610021915.X
• 申請(qǐng)日: 2016-01-14
• 公開（公告）號(hào): CN105571604B
• 公開（公告）日: 2018-08-14
• 發(fā)明（設(shè)計(jì)）人: 胡小兵;廖建勤
• 申請(qǐng)（專利權(quán)）人: 北京師范大學(xué);廖建勤
• 主分類號(hào): G01C21/34
• 分類號(hào): G01C21/34
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法，用以解決在一個(gè)路網(wǎng)環(huán)境的變化規(guī)律是已知的動(dòng)態(tài)路網(wǎng)環(huán)境下，僅僅通過(guò)一次性的優(yōu)化計(jì)算，就能保證從原始起點(diǎn)到終點(diǎn)所實(shí)際走過(guò)路線的理論最優(yōu)性的技術(shù)問(wèn)題，其特征是：在單次路徑優(yōu)化計(jì)算過(guò)程中，路網(wǎng)環(huán)境不是靜態(tài)不變的，而是會(huì)隨著計(jì)算過(guò)程按給定的路網(wǎng)環(huán)境變化規(guī)律而變化，即，在單次優(yōu)化計(jì)算中的路網(wǎng)環(huán)境隨計(jì)算過(guò)程而協(xié)同進(jìn)化；路網(wǎng)環(huán)境協(xié)同進(jìn)化會(huì)造成結(jié)點(diǎn)和鏈接變成暫不可通達(dá)，路徑優(yōu)化計(jì)算過(guò)程中會(huì)考慮運(yùn)動(dòng)體在暫不可通達(dá)結(jié)點(diǎn)和鏈接前的等待行為；考慮了路網(wǎng)環(huán)境協(xié)同進(jìn)化的優(yōu)化計(jì)算過(guò)程能有效保證實(shí)際走過(guò)路徑的最優(yōu)性和計(jì)算的時(shí)效性；所述的方法主要包括以下幾個(gè)步驟：(1)確定描述路網(wǎng)環(huán)境變化的規(guī)律；(2)選定一個(gè)足夠小的時(shí)間單位，以確保能有效描述所給定的路網(wǎng)環(huán)境的變化過(guò)程；(3)初始化在原始起點(diǎn)時(shí)的路網(wǎng)環(huán)境，選定一個(gè)旅行速度常值，并計(jì)算從原始起點(diǎn)出發(fā)沿路網(wǎng)中的鏈接在一個(gè)時(shí)間單位長(zhǎng)度內(nèi)所能到達(dá)的所有位置，將所有這些位置記為當(dāng)前陣面，并將當(dāng)前陣面中所有點(diǎn)的前驅(qū)結(jié)點(diǎn)標(biāo)注為原始起點(diǎn)，即，當(dāng)前陣面中的每個(gè)點(diǎn)都是從原始起點(diǎn)走過(guò)來(lái)的；(4)如果當(dāng)前陣面中包含終點(diǎn)，前往步驟(7),否則，前往步驟(5)；(5)根據(jù)路網(wǎng)環(huán)境變化的規(guī)律，按一個(gè)時(shí)間單位長(zhǎng)度計(jì)算更新路網(wǎng)環(huán)境；(6)基于更新的路網(wǎng)環(huán)境，計(jì)算從當(dāng)前陣面出發(fā)沿路網(wǎng)中的鏈接在一個(gè)時(shí)間單位長(zhǎng)度內(nèi)所能到達(dá)的所有以前不曾到達(dá)過(guò)的位置，記為新的當(dāng)前陣面，并根據(jù)計(jì)算過(guò)程標(biāo)注好新的當(dāng)前陣面中各個(gè)點(diǎn)的前驅(qū)結(jié)點(diǎn)，即，新的當(dāng)前陣面中的某一個(gè)點(diǎn)是從上一個(gè)當(dāng)前陣面中的哪一個(gè)點(diǎn)走過(guò)來(lái)的；如果新的當(dāng)前陣面中的某一個(gè)點(diǎn)可以從上一個(gè)當(dāng)前陣面中的多個(gè)點(diǎn)在當(dāng)前這一個(gè)時(shí)間單位長(zhǎng)度內(nèi)到達(dá)，則該點(diǎn)的前驅(qū)結(jié)點(diǎn)應(yīng)該標(biāo)注為上一個(gè)當(dāng)前陣面中在當(dāng)前這一個(gè)時(shí)間單位長(zhǎng)度內(nèi)最早到達(dá)該點(diǎn)的那一個(gè)點(diǎn)；在計(jì)算新的當(dāng)前陣面時(shí)，需要考慮運(yùn)動(dòng)體在暫不可通達(dá)的結(jié)點(diǎn)和鏈接前的等待行為，即，假如在更新的路網(wǎng)環(huán)境中，上一個(gè)當(dāng)前陣面中的某個(gè)點(diǎn)的前方在當(dāng)前這一個(gè)時(shí)間單位長(zhǎng)度內(nèi)有一個(gè)暫不可通達(dá)的結(jié)點(diǎn)或鏈接，則從該點(diǎn)出發(fā)而形成的新的當(dāng)前陣面中還會(huì)包含該點(diǎn)，即運(yùn)動(dòng)體在該點(diǎn)可以有等待行為；然后返回步驟(4)；(7)從終點(diǎn)開始，按前驅(qū)結(jié)點(diǎn)依次反推直到原始起點(diǎn)，從而確定最優(yōu)路徑，然后優(yōu)化計(jì)算過(guò)程結(jié)束。

2.根據(jù)權(quán)利要求1所述的動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法，其特征是：如果描述路網(wǎng)環(huán)境變化的規(guī)律是固定不變的已知的，則所述的方法僅僅通過(guò)一次性的離線優(yōu)化計(jì)算就可以解決問(wèn)題，而不需要不斷重復(fù)進(jìn)行實(shí)時(shí)的在線優(yōu)化計(jì)算。

3.根據(jù)權(quán)利要求1所述的動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法，其特征是：如果描述路網(wǎng)環(huán)境變化的規(guī)律也是隨時(shí)間變化的，則所述的方法只需要在路網(wǎng)環(huán)境變化規(guī)律發(fā)生變化的各個(gè)時(shí)刻分別進(jìn)行一次性的路徑優(yōu)化計(jì)算。

4.根據(jù)權(quán)利要求1所述的動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法，其特征是：所述的方法可以應(yīng)用于現(xiàn)實(shí)物理網(wǎng)絡(luò)中的路徑優(yōu)化問(wèn)題。

5.根據(jù)權(quán)利要求1所述的動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法，其特征是：所述的方法可以應(yīng)用于抽象虛擬網(wǎng)絡(luò)中的路徑優(yōu)化問(wèn)題。

6.根據(jù)權(quán)利要求1所述的動(dòng)態(tài)路網(wǎng)環(huán)境下的協(xié)同進(jìn)化路徑優(yōu)化方法，其特征是：所述的方法可以采用各種恰當(dāng)?shù)挠布?jì)算設(shè)備和軟件編程技術(shù)來(lái)實(shí)現(xiàn)。