[發(fā)明專利]考慮雙程的多途經(jīng)點(diǎn)的快速路徑規(guī)劃方法

有效

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

本發(fā)明公開了一種考慮雙程的多途經(jīng)點(diǎn)的快速路徑規(guī)劃方法，涉及計算機(jī)智能路徑規(guī)劃技術(shù)領(lǐng)域，所述方法包括如下步驟：設(shè)置先知條件；建立新的坐標(biāo)體系，重新計算各個點(diǎn)的坐標(biāo)：對途經(jīng)點(diǎn)進(jìn)行分類，分為去程點(diǎn)集合及返程點(diǎn)集合；在去程點(diǎn)集合中，根據(jù)x坐標(biāo)值，對點(diǎn)進(jìn)行排序，計算出去程路徑規(guī)劃；在返程點(diǎn)集合中，根據(jù)x坐標(biāo)值，對點(diǎn)進(jìn)行排序，計算出返程路徑規(guī)劃；以目的地為轉(zhuǎn)折點(diǎn)，合并去程與返程；路徑規(guī)劃結(jié)束最后處理。本申請所述方法在途經(jīng)點(diǎn)的點(diǎn)數(shù)超過10個的情況下，計算次數(shù)要比全排列算法至小快1000倍，并且方法穩(wěn)定且唯一，規(guī)劃后的路程最短，具有高效且穩(wěn)定等優(yōu)點(diǎn)。

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

本發(fā)明涉及計算機(jī)智能路徑規(guī)劃技術(shù)領(lǐng)域，尤其涉及一種雙程多途經(jīng)點(diǎn)考慮雙程的多途經(jīng)點(diǎn)的快速路徑規(guī)劃方法。

背景技術(shù)

在現(xiàn)實應(yīng)用領(lǐng)域，現(xiàn)流行的導(dǎo)航軟件有百度、高德、騰訊等導(dǎo)航APP，它們的主要功能就是根據(jù)用戶的需要和根據(jù)現(xiàn)實的交通情況，實現(xiàn)一輛車到一個目的地的不考慮回程的合理的路徑規(guī)劃。而現(xiàn)實中需要更復(fù)雜的路徑規(guī)劃，比如在物流中就需要這樣的路徑規(guī)劃方法：規(guī)劃出一條在去程和返程都經(jīng)過多途經(jīng)點(diǎn)的最短路徑，而這種路徑規(guī)劃就是我們的雙程多途經(jīng)點(diǎn)路徑規(guī)劃方法。

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

還有百度、高德、騰訊等導(dǎo)航APP中具有的多途經(jīng)點(diǎn)規(guī)劃，不是最短路徑規(guī)劃，它們只是根據(jù)用戶輸入地點(diǎn)先后順序的路徑規(guī)劃，并且點(diǎn)數(shù)是有限制的，也不考慮返程的路徑規(guī)劃。

在路徑規(guī)劃算法領(lǐng)域，雙程多途經(jīng)點(diǎn)路徑規(guī)劃方法是哈密爾頓回路中的一個特殊例子，而哈密爾頓回路屬于TSP(Traveling Salesman Problem)問題(同樣，我們的方法也是)，它是一個組合優(yōu)化問題。該問題已經(jīng)被證明具有NPC計算復(fù)雜性，也就是說，針對大型實例，不存在高效穩(wěn)定且最佳算法這一猜想。所以，高效穩(wěn)定且接近最佳路徑規(guī)劃方案是眾多人的研究方向。

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

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

全排列算法的提速法，比如：分界截支算法，它們在一定程度上提高了全排列算法的效率，但提高后的效率仍然不理想。

各種近似算法，這些算法有最近點(diǎn)算法、節(jié)省路程算法、最小生成樹算法、隨機(jī)算法等，它們可以做到高效，但不穩(wěn)定，存在多種可能的近似方案，并且經(jīng)常得不到近似結(jié)果。

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

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

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

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