[發明專利]車輛路徑規劃方法、裝置、設備和存儲介質

有效

• 申請號: 202110012924.3
• 申請日: 2021-01-06
• 公開（公告）號: CN112633609B
• 公開（公告）日: 2022-10-25
• 發明（設計）人: 藍文興;葉梓元;阮沛鈞;劉佳琳;姚新
• 申請（專利權）人: 南方科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08;G06Q50/30
• 代理公司: 北京品源專利代理有限公司 11332
• 代理人: 潘登

本發明實施例公開了一種車輛路徑規劃方法、裝置、設備和計算機存儲介質。該方法具體公開了根據車輛任務信息確定初始路徑S₀，對初始路徑S₀進行進行鄰域交換優化得到第一路徑S₁，基于第一路徑S₁隨機進行交換、插入、逆轉三種優化方式中的一種或多種得到第二路徑S₂，判斷第二路徑S₂與初始路徑S₀相比是否有改進，若有則更新初始路徑S₀為第二路徑S₂，基于初始路徑S₀判斷是否達到預設停止條件，若達到所述預設停止條件，則將所述初始路徑S₀作為規劃結果得到規劃的車輛路徑。本發明實施例通過基于距離信息的鄰域交換優化和隨機優化不斷尋找成本更低的路徑，其優化速度比傳統局部搜索算法更快，效果也更好。

技術領域

本發明實施例涉及路徑規劃領域，尤其涉及一種車輛路徑規劃方法、裝置、設備和存儲介質。

背景技術

帶容量約束的車輛路徑調度場景（Capacitated Vehicle Routing Problems,CVRP），是針對一批運輸設備執行服務任務的調度問題。假定有一批運輸設備，例如卡車，它們要經過城市的多條街道，其中的一些街道上需要載貨，而車輛一旦滿載就必須返回倉庫卸貨，然后才能繼續前往其他街道載貨，而為了使得這批車輛運輸的總開銷最小（每條街道只服務一次、總行駛距離最小等等）。

M3CVRP（英文名：Multi-depot Multi-disposal-facility Multi-tripCapacitated Vehicle Routing Problem，以下全文仍舊簡稱為M3CVRP）是傳統帶容量車輛路徑問題的變種，它擁有更多的約束條件，具體的條件約束還包括：車輛初始從多個停車場出發，并回到對應的停車場，每個車輛的工作時長不能超過最大工作時長限制，其中停車場和倉庫可以是同一位置。

目前局部搜索（英文名：Local Search, 簡稱LS）是用于解決組合優化問題的幾種通用方法之一，它通過對當前解迭代地進行小的局部的修改來不斷地改進當前解，從而達到對解進行優化的目的。

發明內容

本發明實施例提供一種車輛路徑規劃方法、裝置、設備和計算機存儲介質，實現路徑規劃加速求解處理。

第一方面，本發明實施例提供了一種車輛路徑規劃方法，包括：

a、根據車輛任務信息確定初始路徑；

b、基于所述初始路徑進行鄰域交換優化得到第一路徑；

c、基于所述第一路徑進行隨機優化得到第二路徑；

d、判斷所述第二路徑的成本是否低于所述初始路徑的成本，若不是則跳轉至步驟f；

e、若是則更新所述初始路徑為所述第二路徑；

f、基于所述初始路徑判斷是否達到預設停止條件，若未達到所述預設停止條件則跳轉至步驟b；

g、若達到所述預設停止條件，則將所述初始路徑作為規劃結果得到規劃的車輛路徑。

第二方面，本發明實施例還提供了一種車輛路徑規劃裝置，該裝置包括：

初始路徑確定模塊，用于根據車輛任務信息確定初始路徑；

第一路徑確定模塊，用于基于所述初始路徑進行鄰域交換優化得到第一路徑；

第二路徑確定模塊，用于基于所述第一路徑進行隨機優化得到第二路徑；

成本判斷模塊，用于判斷所述第二路徑的成本是否低于所述初始路徑的成本，若不是則跳轉至停止判斷模塊；

路徑調整模塊，用于若是則更新所述初始路徑為所述第二路徑；