[發(fā)明專利]車輛路徑規(guī)劃方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 202011056281.4
• 申請(qǐng)日: 2020-09-29
• 公開（公告）號(hào): CN114330800A
• 公開（公告）日: 2022-04-12
• 發(fā)明（設(shè)計(jì)）人: 李勇;王翰森;宗澤方;羅蜀鈺;鄭萌;耿璐
• 申請(qǐng)（專利權(quán)）人: 株式會(huì)社日立制作所;清華大學(xué)
• 主分類號(hào): G06Q10/04
• 分類號(hào): G06Q10/04;G06N3/04;G06N3/08
• 代理公司: 北京銀龍知識(shí)產(chǎn)權(quán)代理有限公司 11243
• 代理人: 黃燦;姜精斌

本發(fā)明提供了一種車輛路徑規(guī)劃方法及裝置，其中，所述方法包括：數(shù)據(jù)獲取步驟、初始計(jì)算步驟、重分區(qū)步驟、迭代計(jì)算步驟、更新處理步驟和迭代停止判斷步驟，其中，在初始計(jì)算步驟中，根據(jù)所述輸入數(shù)據(jù)中的多個(gè)客戶站點(diǎn)的地理位置，對(duì)客戶站點(diǎn)進(jìn)行聚類分區(qū)，得到多個(gè)分區(qū)，以及，計(jì)算得到每個(gè)分區(qū)的局部?jī)?yōu)化路線和局部路線成本；在所述重分區(qū)步驟中，利用預(yù)先訓(xùn)練得到的分區(qū)調(diào)整網(wǎng)絡(luò)，對(duì)所述多個(gè)分區(qū)中的兩個(gè)分區(qū)進(jìn)行融合和重分區(qū)，得到兩個(gè)新分區(qū)。本發(fā)明提供的車輛路徑規(guī)劃方法及裝置，通過將多個(gè)客戶站點(diǎn)劃分為多個(gè)分區(qū)，在每個(gè)分區(qū)下分別進(jìn)行VRP求解，避免對(duì)大量客戶站點(diǎn)進(jìn)行直接求解，可以提高大規(guī)模VRP求解的性能和效率。

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

本發(fā)明涉及車輛路徑問題(Vehicle Routing Problem，VRP)技術(shù)領(lǐng)域，具體而言，本發(fā)明涉及一種車輛路徑規(guī)劃方法及裝置。

背景技術(shù)

大規(guī)模車輛路徑規(guī)劃問題(VRP)在現(xiàn)實(shí)中有廣泛的應(yīng)用，比如公交車規(guī)劃、貨物運(yùn)輸?shù)取?duì)于該問題，現(xiàn)有技術(shù)的解決方案主要包括傳統(tǒng)方法和基于強(qiáng)化學(xué)習(xí)的方法兩種。

其中，傳統(tǒng)方法又具體包括精確算法和啟發(fā)式方法，精確算法效率低、不具備實(shí)用價(jià)值；啟發(fā)式方法的性能依賴精細(xì)的人工設(shè)計(jì)，效率也不夠高。

基于強(qiáng)化學(xué)習(xí)的方法也可以分為“直接生成解”和“先生成再不斷改進(jìn)解”兩大類。前者由于模型難以擴(kuò)展、性能隨規(guī)模增大而大幅下降等原因難以適用于大規(guī)模車VRP問題；后者由于每次改進(jìn)幅度較小、耗時(shí)長(zhǎng)，在大規(guī)模VRP問題上具有訓(xùn)練時(shí)間指數(shù)增長(zhǎng)、訓(xùn)練過程難以收斂等特點(diǎn)，實(shí)用性低。

例如，一篇中國(guó)專利申請(qǐng)(CN110147901A)中使用指針網(wǎng)絡(luò)(Pointer Network)來直接生成VRP問題的解，當(dāng)VRP規(guī)模增大時(shí)，由于狀態(tài)數(shù)目、動(dòng)作空間數(shù)目以及模型規(guī)模的大幅增大，該模型會(huì)出現(xiàn)難以訓(xùn)練、性能大幅下降等問題，因此難以適用于大規(guī)模VRP問題。

又例如，另一篇中國(guó)專利申請(qǐng)(CN106251009A)中使用蟻群優(yōu)化算法來解決VRP問題并生成解，但是在大規(guī)模的數(shù)據(jù)分布上存在著生成速度緩慢，不具有實(shí)時(shí)響應(yīng)能力等缺陷。

另外，現(xiàn)有技術(shù)的專利申請(qǐng)?jiān)谲囕v路徑規(guī)劃問題上大多是進(jìn)行避障控制，與VRP問題中的車輛調(diào)度無(wú)關(guān)，也不能處理帶容量的車輛的接客調(diào)度問題。

因此，亟需一種能夠同時(shí)兼顧高性能和高效率的VRP方法，來解決大規(guī)模車輛路徑規(guī)劃問題。

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

本發(fā)明實(shí)施例要解決的技術(shù)問題是提供一種車輛路徑規(guī)劃方法及裝置，能夠在大規(guī)模車輛路徑規(guī)劃中提高路徑規(guī)劃的性能和效率。

為解決上述技術(shù)問題，本發(fā)明實(shí)施例提供的一種車輛路徑規(guī)劃方法，包括：

數(shù)據(jù)獲取步驟，獲取待進(jìn)行路徑規(guī)劃的始發(fā)站點(diǎn)、配送車輛的最大裝載量、多個(gè)客戶站點(diǎn)的地理位置以及每個(gè)客戶站點(diǎn)的配送需求信息，作為輸入數(shù)據(jù)；

初始計(jì)算步驟，根據(jù)所述輸入數(shù)據(jù)中的多個(gè)客戶站點(diǎn)的地理位置，對(duì)客戶站點(diǎn)進(jìn)行聚類分區(qū)，得到多個(gè)分區(qū)；根據(jù)所述輸入數(shù)據(jù)中的始發(fā)站點(diǎn)、配送車輛的最大裝載量、客戶站點(diǎn)的地理位置以及客戶站點(diǎn)的配送需求信息，計(jì)算得到每個(gè)分區(qū)的局部?jī)?yōu)化路線和局部路線成本，并得到所有客戶站點(diǎn)的全局優(yōu)化路線和路線總成本，以及，根據(jù)所述全局優(yōu)化路線和路線總成本，更新最優(yōu)優(yōu)化路線和最優(yōu)路線總成本；

重分區(qū)步驟，利用預(yù)先訓(xùn)練得到的分區(qū)調(diào)整網(wǎng)絡(luò)，對(duì)所述多個(gè)分區(qū)中的兩個(gè)分區(qū)進(jìn)行融合和重分區(qū)，得到兩個(gè)新分區(qū)；

迭代計(jì)算步驟，計(jì)算所述兩個(gè)新分區(qū)的局部?jī)?yōu)化路線，并更新所述全局優(yōu)化路線和路線總成本；

更新處理步驟，判斷更新后的路線總成本是否低于所述最優(yōu)路線總成本，若是，則根據(jù)更新后的所述全局優(yōu)化路線和路線總成本，更新所述最優(yōu)優(yōu)化路線和最優(yōu)路線總成本，并返回所述重分區(qū)步驟；否則，進(jìn)入迭代停止判斷步驟；