[發(fā)明專利]遍歷多點(diǎn)歸原的車輛路徑規(guī)劃方法

有效

• 申請?zhí)枺?/td>: 202110263504.2
• 申請日: 2021-03-11
• 公開（公告）號: CN112947467B
• 公開（公告）日: 2021-11-02
• 發(fā)明（設(shè)計(jì)）人: 李斌;駱劍鋒;朱展延;陳逸婷;曾雄;庾文聰
• 申請（專利權(quán)）人: 東莞職業(yè)技術(shù)學(xué)院;駱劍鋒
• 主分類號: G05D1/02
• 分類號: G05D1/02
• 代理公司: 東莞市十方專利代理事務(wù)所(普通合伙) 44391
• 代理人: 黃云

本發(fā)明公開了一種遍歷多點(diǎn)歸原的車輛路徑規(guī)劃方法，涉及計(jì)算機(jī)智能路徑規(guī)劃技術(shù)領(lǐng)域。所述方法包括如下步驟：先知條件；求最小生成樹；取最小生成樹中的各子樹；求最密子樹；在最密子樹中找到最邊沿葉子1；針對最密子樹找最邊沿葉子端點(diǎn)2；在兩個最邊沿葉子端點(diǎn)中，確定一個是最密子樹始點(diǎn)，另外一個是最密子樹終點(diǎn)：以最密子樹根節(jié)點(diǎn)和最密子樹始點(diǎn)和最密子樹終點(diǎn)組成的回路為主線，把最密子樹中的葉子端點(diǎn)合并到主線中；原點(diǎn)與主線合并，形成回路；對剩下的子樹進(jìn)行判斷，點(diǎn)數(shù)超過1的子樹以上部分步驟，讓子樹形成回路；所有的回路合并后，最終的回路就是我們的最終的路徑規(guī)劃結(jié)果。所述方法具有計(jì)算量小，計(jì)算速度快，穩(wěn)定性強(qiáng)等優(yōu)點(diǎn)。

技術(shù)領(lǐng)域

本發(fā)明涉及涉及計(jì)算機(jī)智能路徑規(guī)劃技術(shù)領(lǐng)域，尤其涉及一種圍繞最小生成樹方法的遍歷多點(diǎn)歸原的遍歷多點(diǎn)歸原的車輛路徑規(guī)劃方法。

背景技術(shù)

在現(xiàn)實(shí)應(yīng)用領(lǐng)域，現(xiàn)流行的導(dǎo)航軟件有百度、高德、騰訊等導(dǎo)航APP，它們的主要功能就是根據(jù)用戶的需要和根據(jù)現(xiàn)實(shí)的交通情況，實(shí)現(xiàn)一輛車到一個目的地的不考慮回程的合理的路徑規(guī)劃。而現(xiàn)實(shí)中需要更復(fù)雜的路徑規(guī)劃，比如要合理規(guī)劃出貨車從物流中心出發(fā)，到多個目的地進(jìn)行收貨，收貨完畢后返回物流中心的路徑規(guī)劃，即遍歷多點(diǎn)歸原的路徑規(guī)劃，而這種路徑規(guī)劃在現(xiàn)在的導(dǎo)航APP中是沒有的。

在已有的軟件服務(wù)平臺中，滴滴快車的順風(fēng)車服務(wù)、美團(tuán)外買騎手APP、公交線路規(guī)劃等，都被誤認(rèn)為是我們的路徑規(guī)劃算法的程序?qū)崿F(xiàn)，其實(shí)它們都不是我們前面所說的遍歷多點(diǎn)歸原的路徑規(guī)劃，它們只是兩點(diǎn)路線規(guī)劃在現(xiàn)實(shí)應(yīng)用中的升級改進(jìn)，或是多次兩點(diǎn)路線規(guī)劃的結(jié)果。

在路徑規(guī)劃領(lǐng)域，遍歷多點(diǎn)歸原的最短路徑規(guī)劃算法屬于TSP(TravelingSalesman Problem)問題(可百度搜索TSP問題)，它是一個組合優(yōu)化問題。該問題已經(jīng)被證明具有NPC計(jì)算復(fù)雜性，也就是說，針對大型實(shí)例，不存在高效穩(wěn)定且最佳算法這一猜想。所以，高效穩(wěn)定且接近最佳路徑規(guī)劃方案是眾多人的研究方向。

現(xiàn)在常見的算法有全排列算法及其提速法、近似算法和各種模擬算法，但這三種算法都不能做到高效穩(wěn)定且近似最佳，現(xiàn)分析如下：

全排列算法，它是唯一能解決遍歷多點(diǎn)歸原的路徑規(guī)劃的算法，但它是一種低效的計(jì)算方法，在目的地較多的情況下，計(jì)算效率極低，無法在可接受的時間內(nèi)得到結(jié)果，比如在20個點(diǎn)的情況下，它的計(jì)算次數(shù)為2432902008176640000次，對于一般計(jì)算機(jī)來說，實(shí)在太多了，用戶等待計(jì)算時間過長。所以全排列算法不是高效的算法。

全排列算法的提速法，比如：分界截支算法，它們在一定程序上提高了組合排列算法的效率，但提高后的效率仍然不理想。各種近似算法，這些算法有最近點(diǎn)算法、節(jié)省路程算法、最小生成樹算法(不是多點(diǎn)歸原算法)、隨機(jī)算法等，它們可以做到高效，但不穩(wěn)定，存在多種可能的近似方案，并且經(jīng)常得不到近似結(jié)果。

各種模擬算法：這些算法包括有：人工智能的神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、魚群算法、退火算法、遺傳算法等等，這些算法都站不住腳，現(xiàn)具體分析如下：

1)首先人工智能的神經(jīng)網(wǎng)絡(luò)算法，它的特點(diǎn)是需要人的大量訓(xùn)練后，計(jì)算機(jī)才能擁有相關(guān)的功能，但對于多點(diǎn)路徑規(guī)劃來說，本來憑借人的智力也難在一時三刻找到最佳路徑，更不用說要人對機(jī)器做大量訓(xùn)練了。所以這種命題是偽命題。

2)其次是蟻群算法、魚群算法、退火算法，這類低級智商動物算法更不用與人工智能算法比了。并且在平時觀察可了解蟻群和魚群并不走最短路徑，它們一般走安全路徑，最明顯的是蟻群。其次，這些算法是局部最優(yōu)算法，不穩(wěn)定，每次計(jì)算，結(jié)果可能不一樣，并且一但路徑規(guī)劃失敗，將重新規(guī)劃，耗時絕對不低。

3)遺傳算法，與上面的算法也有相同的缺點(diǎn)，首先它是局部最優(yōu)算法，沒有宏觀調(diào)控，并且這種算法有隨機(jī)性(不穩(wěn)定)，失敗后又要重新計(jì)算，消耗時間變長。

總的來說，現(xiàn)在還沒有一種符合現(xiàn)實(shí)應(yīng)用的高效且穩(wěn)定的接近最佳的算法。

發(fā)明內(nèi)容