[發明專利]基于數據驅動的群體智能計算的城市車輛路徑優化方法

有效

• 申請號: 202011275358.7
• 申請日: 2020-11-16
• 公開（公告）號: CN112270047B
• 公開（公告）日: 2023-09-29
• 發明（設計）人: 王甲海;張勇鑫;張子臻
• 申請（專利權）人: 中山大學
• 主分類號: G06F30/15
• 分類號: G06F30/15;G06F30/27;G06F111/06
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 林梅繁

本發明屬于車輛路徑優化技術，為基于數據驅動的群體智能計算的城市車輛路徑優化方法，先將多目標車輛路徑優化問題建模成無向圖，倉庫和客戶為圖中的結點；建立多目標函數；設定M個均勻分布的權重向量，使用權重和的方式將多目標函數的向量目標分解為M個單目標子問題；對每個單目標子問題使用強化學習方法訓練一個帶有全面環境信息的圖注意力模型，再將得到的M個神經網絡模型作為初始種群，使用演化學習方法訓練模型種群，最終得到M個模型，從而對多目標車輛路徑優化問題進行求解，獲得一組在兩個優化目標間權衡的解集。本發明求得的解集具有良好的收斂性和多樣性。

技術領域

本發明屬于車輛路徑優化技術，具體為基于數據驅動的群體智能計算的城市車輛路徑優化方法。

背景技術

車輛路徑問題(vehicle?routing?problem，VRP)是一類非常重要的組合優化問題：給定一組車隊和一定數量的客戶，每個客戶有不同數量的貨物需求，配送中心向客戶提供貨物，如何在滿足給定約束條件下來組織送貨車隊的行駛路線使得給定的目標(例如路程、耗時等)最優。VRP問題及其復雜變種在城市中普遍存在，例如郵政投遞、外賣服務、設備調度、智能出行等都可以抽象為VRP問題。在現實環境中，客戶點往往有特定的服務時間窗，因此帶有時間窗約束的VRP問題更符合實際需求。對于城市VRP問題，城市各利益相關方具有不同的利益訴求，形成了各自不同的優化目標，這些目標由于不同的利益考慮，難免相互沖突，形成多目標優化和決策的問題。因此多目標時間窗車輛路徑優化問題(multi-objective?vehicle?routing?problem?with?time?window，MO-VRPTW)可以很好的建模現實中城市車輛路徑優化的情景。多目標優化問題可以形式化描述如下：

多目標優化問題可以形式化描述如下：

Min?F(x)＝(f₁(x),f₂(x),…,f_m(x))^T

s.t.x∈X

其中，上標T表示對矩陣或向量的轉置操作，下文皆同；Min表示取最小值；F(x)表示函數映射包括m個單目標函數f₁(x),f₂(x),…,f_m(x)；s.t.表示subject?to的意思；X是滿足容量和時間窗約束的解空間。因為m個目標往往相互沖突，對于多目標優化問題，并不存在單一的最優解，尋求一組在多個目標中權衡的解集更有意義。記是兩個目標值向量。當且僅當并且稱a支配b，記為b＜a。對于解x^*，若則稱x^*為Pareto最優解。包含所有Pareto最優解的集合稱為Pareto解集。Pareto解集在目標空間中的映射稱為Pareto前沿。

對于MO-VRPTW，前人提出了很多基于迭代的智能優化算法。大致分為兩類：第一類是多目標演化算法，如NSGA-II，MOEA/D；第二類是多目標鄰域搜索算法，如MOGLS。多目標演化算法通過同時演化一組解來搜索Pareto解集，而多目標鄰域搜索算法則通過鄰域搜索算子迭代提升解。這些基于迭代的方法具有強大的搜索能力，但存在三個缺點：第一，在求解過程中需要大量的迭代計算，算法時間復雜度高；第二，當求解的問題僅發生數值上的微小改變或遇到相似的新問題時，整個迭代求解過程需要重新演算；第三，算法中的啟發式規則往往依賴專家知識進行設計。