[發(fā)明專(zhuān)利]導(dǎo)航路線生成方法、裝置、電子設(shè)備及存儲(chǔ)介質(zhì)

在審

• 申請(qǐng)?zhí)枺?/td>: 202310344742.5
• 申請(qǐng)日: 2023-03-28
• 公開(kāi)（公告）號(hào): CN116429139A
• 公開(kāi)（公告）日: 2023-07-14
• 發(fā)明（設(shè)計(jì)）人: 劉人杰
• 申請(qǐng)（專(zhuān)利權(quán)）人: 阿里巴巴（中國(guó)）有限公司
• 主分類(lèi)號(hào): G01C21/34
• 分類(lèi)號(hào): G01C21/34
• 代理公司: 廣州鑄智知識(shí)產(chǎn)權(quán)代理有限公司 44886
• 代理人: 郗名悅;徐瑞紅

1.一種導(dǎo)航路線生成方法，其特征在于，所述方法包括：

響應(yīng)于由起點(diǎn)至終點(diǎn)的導(dǎo)航請(qǐng)求，獲取地圖中的初始端點(diǎn)路段，所述初始端點(diǎn)路段包括起點(diǎn)路段和終點(diǎn)路段；

若所述起點(diǎn)和終點(diǎn)中的任一點(diǎn)為封閉路段與非封閉路段的分界點(diǎn)，在地圖中從所述初始端點(diǎn)路段中與所述分界點(diǎn)相關(guān)的路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充端點(diǎn)路段；

將所述初始端點(diǎn)路段與補(bǔ)充端點(diǎn)路段合并得到候選集合；

根據(jù)所述候選集合中的起點(diǎn)路段和終點(diǎn)路段計(jì)算出導(dǎo)航路線；

其中，路段為地圖中代表真實(shí)道路的最小單元，起點(diǎn)路段為駛出起點(diǎn)的第一個(gè)路段，終點(diǎn)路段為駛?cè)虢K點(diǎn)的最后一個(gè)路段，符合條件的路段是指存在駛?cè)牖蝰偝鲈撀范蔚挠行范巍?/p>

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述在地圖中從所述初始端點(diǎn)路段中與所述分界點(diǎn)相關(guān)的路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充端點(diǎn)路段，包括：

在地圖中從所述初始端點(diǎn)路段中與所述分界點(diǎn)相關(guān)的路段開(kāi)始，采用圖搜索算法進(jìn)行迭代搜索，并在每次迭代中對(duì)搜索路徑上的當(dāng)前路段進(jìn)行判斷：

判斷是否存在關(guān)聯(lián)當(dāng)前路段并在搜索路徑外的有效路段；

如果是，則確定當(dāng)前路段為補(bǔ)充端點(diǎn)路段，并終止當(dāng)前迭代分支的搜索；

否則，繼續(xù)搜索直至搜索路徑末尾或搜索深度大于第一閾值時(shí)終止搜索；

其中，所述有效路段為具備正常通行能力的非封閉公共路段且不是斷頭路段，所述搜索深度為已搜索路段對(duì)應(yīng)真實(shí)道路的總長(zhǎng)度；與所述分界點(diǎn)相關(guān)的路段若為起點(diǎn)路段，所述關(guān)聯(lián)為駛出；與所述分界點(diǎn)相關(guān)的路段若為終點(diǎn)路段，所述關(guān)聯(lián)為駛?cè)搿?/p>

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述斷頭路段通過(guò)以下方式判斷：

對(duì)待判斷路段額外執(zhí)行一次搜索；

若搜索深度大于第二閾值且未至搜索路徑末尾，則確定待判斷路段非斷頭路段并終止搜索；

若至搜索路徑末尾時(shí)搜索深度未達(dá)到所述第二閾值，則確定待判斷路段為斷頭路段。

4.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述有效路段為除橋梁、隧道、收費(fèi)路段、高速路段、匝道、封閉路段或在建路段以外的公共路段。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述根據(jù)所述候選集合中的起點(diǎn)路段和終點(diǎn)路段計(jì)算出導(dǎo)航路線，包括：

根據(jù)所述候選集合中的起點(diǎn)路段和終點(diǎn)路段，計(jì)算出由起點(diǎn)路段至終點(diǎn)路段的路徑中代價(jià)最小的路徑作為導(dǎo)航路線。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述若所述起點(diǎn)和終點(diǎn)中的任一點(diǎn)為封閉路段與非封閉路段的分界點(diǎn)，在地圖中從所述初始端點(diǎn)路段中與所述分界點(diǎn)相關(guān)的路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充端點(diǎn)路段，包括：

若所述起點(diǎn)為分界點(diǎn)且所述初始端點(diǎn)路段中的起點(diǎn)路段為指定路段，在地圖中從所述指定路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充起點(diǎn)路段；

若所述終點(diǎn)為分界點(diǎn)且所述初始端點(diǎn)路段中的終點(diǎn)路段為指定路段，在地圖中從所述指定路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充終點(diǎn)路段；

其中，所述分界點(diǎn)為封閉路段與非封閉路段的分界點(diǎn)，所述指定路段為單向高速封閉路段或單向匝道。

7.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述若所述起點(diǎn)和終點(diǎn)中的任一點(diǎn)為封閉路段與非封閉路段的分界點(diǎn)，在地圖中從所述初始端點(diǎn)路段中與所述分界點(diǎn)相關(guān)的路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充端點(diǎn)路段，包括：

若所述起點(diǎn)和終點(diǎn)中的任一點(diǎn)為封閉路段與非封閉路段的分界點(diǎn)，且車(chē)輛屬性符合指定條件，在地圖中從所述初始端點(diǎn)路段中與所述分界點(diǎn)相關(guān)的路段開(kāi)始，搜索符合條件的路段得到補(bǔ)充端點(diǎn)路段；

其中，所述車(chē)輛屬性包括車(chē)輛類(lèi)型和使用性質(zhì)中的至少一種。

8.根據(jù)權(quán)利要求1所述的方法，其特征在于，還包括：

在計(jì)算出的多條導(dǎo)航路線中確定首選路線和備選路線；

若首選路線中的端點(diǎn)路段為封閉路段，則優(yōu)先推薦端點(diǎn)路段為非封閉路段的備選路線；

若首條路線中的端點(diǎn)路段為非封閉路段，則優(yōu)先推薦端點(diǎn)路段為封閉路段的備選路線。