[發明專利]一種車輛分配方法及裝置

有效

• 申請號: 201710526954.X
• 申請日: 2017-06-30
• 公開（公告）號: CN107392358B
• 公開（公告）日: 2021-07-23
• 發明（設計）人: 金忠孝
• 申請（專利權）人: 上海汽車集團股份有限公司;上海汽車工業（集團）總公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 北京信遠達知識產權代理有限公司 11304
• 代理人: 魏曉波

本發明提供一種車輛分配方法及裝置，該方法包括為各個原始訂單分配車次并生成初始車次分配信息，所述初始車次分配信息包含有車次及其對應的全部原始訂單；優化初始車次分配信息中各個車次的車次載重里程，得到優化后的車次分配信息，所述優化后的車次分配信息包含有車次及其對應的優化后的全部原始訂單；優化車次分配信息中各個車次的車輛總里程，得到車輛分配信息，所述車輛分配信息包含有車輛標識及其對應的車輛路徑。本發明憑借優化車次和車輛的策略，合理并高效地實現了關于原始訂單的車輛分配計劃，從而更加適應業務需求的變化以及業務規模的增長。

技術領域

本發明涉及汽車技術領域，更具體地說，涉及一種車輛分配方法及裝置。

背景技術

VRP問題(Vehicle routing problem，車輛路徑問題)，它是指一定數量的客戶，各自有不同的訂單，配送中心向客戶提供訂單貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。由于旅行商問題(TSP)是VRP問題的一種約化，而Gaery已證明TSP問題是NPC(Non-deterministic Polynomial complete problem，NP完全問題)難題，因此，VRP問題也屬于NPC難題。

由于無法找出一個在常規多項式時間內得出最優解的算法，因此一般的做法是找出一個近似最優解。目前主要采用全局隨機尋優的模擬退火算法，但是這種隨機類別的算法初始搜索空間過大，隨機尋優的時間代價過高，因此無法靈活適應業務需求的變化和增長。

發明內容

有鑒于此，本發明提供一種車輛分配方法及裝置，以解決目前采用全局隨機尋優的模擬退火算法由于初始搜索空間過大、隨機尋優的時間代價過高，因此無法靈活適應業務需求的變化和增長的問題。技術方案如下：

一種車輛分配方法，包括：

為各個原始訂單分配車次并生成初始車次分配信息，所述初始車次分配信息包含有車次及其對應的全部所述原始訂單；

優化所述初始車次分配信息中各個所述車次的車次載重里程，得到優化后的車次分配信息，所述優化后的車次分配信息包含有車次及其對應的優化后的全部所述原始訂單；

優化所述車次分配信息中各個所述車次的車輛總里程，得到車輛分配信息，所述車輛分配信息包含有車輛標識及其對應的車輛路徑。

優選的，所述為各個原始訂單分配車次，包括：

按照節點信息對全部原始訂單進行分類，得到至少一個原始訂單組，所述原始訂單組中各個所述原始訂單的節點信息相同；

對于各個所述原始訂單組，根據車次約束條件對該原始訂單組中各個所述原始訂單進行車次預分配，并將未分配有車次的全部所述原始訂單打包為訂單捆；

根據節點信息以及車次約束條件對全部所述訂單捆中的全部所述原始訂單進行車次再分配。

優選的，所述優化所述初始車次分配信息中各個所述車次的車次載重里程，得到優化后的車次分配信息，包括：

對于所述初始車次分配信息各個所述車次，根據該車次對應的全部所述原始訂單的節點信息，計算該車次的車次載重里程；

將各個所述車次的車次載重里程之和確定為當前車次載重總里程；

根據模擬退火算法對各個所述車次進行訂單尋優迭代處理，并計算此次迭代后的車次載重總里程；

判斷此次迭代后的車次載重總里程和所述當前車次載重總里程差值的絕對值是否大于載重里程閾值；

若是，生成此次迭代后車次分配信息；