[發(fā)明專利]車輛路徑規(guī)劃方法及裝置、計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)、終端

有效

• 申請(qǐng)?zhí)枺?/td>: 202010151343.3
• 申請(qǐng)日: 2020-03-06
• 公開（公告）號(hào): CN111461403B
• 公開（公告）日: 2023-09-29
• 發(fā)明（設(shè)計(jì)）人: 鄭仁;項(xiàng)黨
• 申請(qǐng)（專利權(quán)）人: 上海汽車集團(tuán)股份有限公司;上海汽車工業(yè)（集團(tuán)）總公司
• 主分類號(hào): G06Q10/047
• 分類號(hào): G06Q10/047;G01C21/34;G06N3/044;G06N3/045;G06N3/08
• 代理公司: 北京信遠(yuǎn)達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11304
• 代理人: 趙興華

本發(fā)明提供了一種車輛路徑規(guī)劃方法及裝置、計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)、終端，通過(guò)對(duì)指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)進(jìn)行訓(xùn)練得到路徑規(guī)劃模型，將編碼得到的待規(guī)劃的訪問(wèn)站點(diǎn)的名稱序列和距離序列輸入至路徑規(guī)劃模型中，由路徑規(guī)劃模型基于距離序列對(duì)名稱序列進(jìn)行重新排序并輸出能夠使訪問(wèn)訪問(wèn)站點(diǎn)的規(guī)劃路徑距離最短的新名稱序列，從而獲得新名稱序列對(duì)應(yīng)的規(guī)劃路徑。基于本發(fā)明，可以以深度網(wǎng)絡(luò)塑造路徑規(guī)劃策略，從而實(shí)現(xiàn)不經(jīng)過(guò)搜索即可直接計(jì)算出車輛路徑規(guī)劃問(wèn)題的優(yōu)化結(jié)果。

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

本發(fā)明涉及物流技術(shù)領(lǐng)域，更具體地說(shuō)，涉及一種車輛路徑規(guī)劃方法及裝置、計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)、終端。

背景技術(shù)

車輛路徑規(guī)劃問(wèn)題(VRP)是一個(gè)組合優(yōu)化問(wèn)題，該問(wèn)題已被證明是一個(gè)NP-hard問(wèn)題，除非窮舉所有的組合可能，否則無(wú)法確定該問(wèn)題的最優(yōu)解。而實(shí)際物流運(yùn)輸、車輛調(diào)度、路線規(guī)劃等常見場(chǎng)景中，經(jīng)常遇到車輛路徑規(guī)劃問(wèn)題的求解需求。

現(xiàn)階段，解決該類問(wèn)題的常見優(yōu)化方法是啟發(fā)式算法，比如遺傳算法、蟻群算法、粒子群算法、模擬退火、禁忌搜索等。在問(wèn)題的計(jì)算規(guī)模不大時(shí)，也可以用動(dòng)態(tài)規(guī)劃算法求解出最優(yōu)路徑，動(dòng)態(tài)規(guī)劃求解該問(wèn)題所需的時(shí)間復(fù)雜度和空間復(fù)雜度都較高，一般訪問(wèn)站點(diǎn)超過(guò)20個(gè)，其計(jì)算速度就已經(jīng)十分緩慢了。然而，該類問(wèn)題通常沒有特定的優(yōu)化規(guī)律，啟發(fā)式算法本質(zhì)上是以隨機(jī)搜索的方式逐漸找到性能更優(yōu)的解，這樣無(wú)疑需要消耗時(shí)間等待其不停地隨機(jī)搜索。也就是說(shuō)，搜索的可能性越多，就可能越接近最優(yōu)解。

但是，考慮到實(shí)際場(chǎng)景對(duì)該問(wèn)題的求解時(shí)間是有限制的，因此如何在解的性能和計(jì)算損耗時(shí)間之間做出平衡，成為亟需解決的問(wèn)題。

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

有鑒于此，為解決上述問(wèn)題，本發(fā)明提供一種車輛路徑規(guī)劃方法及裝置、計(jì)算機(jī)可讀存儲(chǔ)介質(zhì)、終端。技術(shù)方案如下：

一種車輛路徑規(guī)劃方法，所述方法包括：

編碼待規(guī)劃的訪問(wèn)站點(diǎn)的名稱序列和距離序列，所述名稱序列包含所述訪問(wèn)站點(diǎn)中每個(gè)站點(diǎn)的名稱編碼值，所述距離序列包含所述訪問(wèn)站點(diǎn)中兩兩站點(diǎn)間的距離值；

將所述名稱序列和所述距離序列輸入至預(yù)先訓(xùn)練的路徑規(guī)劃模型中，以使所述路徑規(guī)劃模型基于所述距離序列對(duì)所述名稱序列進(jìn)行重新排序并輸出新名稱序列，所述新名稱序列能夠使訪問(wèn)所述訪問(wèn)站點(diǎn)的規(guī)劃路徑距離最短，所述路徑規(guī)劃模型是預(yù)先對(duì)指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)進(jìn)行訓(xùn)練得到的；

獲取所述新名稱序列對(duì)應(yīng)的規(guī)劃路徑。

優(yōu)選的，預(yù)先對(duì)指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)進(jìn)行訓(xùn)練得到所述路徑規(guī)劃模型的過(guò)程，包括：

獲取訓(xùn)練樣本，所述訓(xùn)練樣本包含多組訓(xùn)練用訪問(wèn)站點(diǎn)的名稱序列樣本和距離序列樣本，一組名稱序列樣本對(duì)應(yīng)一個(gè)訓(xùn)練用規(guī)劃路徑、對(duì)應(yīng)一個(gè)距離序列樣本；

從所述訓(xùn)練樣本中抽取一組本次訓(xùn)練用的名稱序列樣本，將該組名稱序列樣本和對(duì)應(yīng)的距離序列樣本輸入至所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)中，以使所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)基于所輸入的所述距離序列樣本輸出該組名稱序列樣本中能夠使對(duì)應(yīng)的訓(xùn)練用規(guī)劃路徑距離收斂的一個(gè)目標(biāo)名稱序列樣本，所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)的初始值是預(yù)先設(shè)置的；

通過(guò)計(jì)算所述目標(biāo)名稱序列樣本對(duì)應(yīng)的訓(xùn)練用規(guī)劃路徑的距離調(diào)整所述網(wǎng)絡(luò)參數(shù)，以使所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)重新執(zhí)行所述基于所輸入的所述距離序列樣本輸出該組名稱序列樣本中能夠使對(duì)應(yīng)的訓(xùn)練用規(guī)劃路徑距離收斂的一個(gè)目標(biāo)名稱序列樣本到滿足本次訓(xùn)練的結(jié)束條件時(shí)結(jié)束本次訓(xùn)練，并對(duì)本次訓(xùn)練結(jié)束時(shí)所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)所輸出的最終目標(biāo)名稱序列樣本設(shè)置指針，所述指針是再次訓(xùn)練所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)的基礎(chǔ)或依據(jù)；

將多次訓(xùn)練后的所述指針網(wǎng)絡(luò)類型的深度網(wǎng)絡(luò)作為所述路徑規(guī)劃模型。

優(yōu)選的，所述通過(guò)計(jì)算所述目標(biāo)名稱序列樣本對(duì)應(yīng)的訓(xùn)練用規(guī)劃路徑的距離調(diào)整所述網(wǎng)絡(luò)參數(shù)，包括：