[發明專利]一種協商機制下多車輛平臺的任務規劃系統

有效

• 申請號: 201811473388.1
• 申請日: 2018-12-04
• 公開（公告）號: CN109636023B
• 公開（公告）日: 2022-12-06
• 發明（設計）人: 靳鵬;崔勇;胡笑旋;馬華偉;夏忠;姚靖宇;任送蓮;張凱
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08
• 代理公司: 北京潤平知識產權代理有限公司 11283
• 代理人: 劉兵;肖冰濱

本發明實施方式提供一種協商機制下多車輛平臺的任務規劃系統，屬于物流資源的配送調度技術領域。任務規劃系統包括管控平臺和車輛平臺；管控平臺對接收到的任務集進行預處理以生成第一公告信息，第一公告信息包括每個任務的編號、對應的位置信息、對應的任務集合的編號、完成任務所在的任務集合內所有任務的最短路徑和對應的容量需求；管控平臺從第一公告信息中隨機選取一個未被選取的任務，將被選取的任務發送至每個車輛平臺，其中，每個車輛平臺包括至少一輛運輸車；每個車輛平臺接收被選取的任務，能夠執行被選取的任務的車輛平臺計算執行被選取的任務的執行成本，執行成本包括由于執行任務所減少的剩余里程值以及剩余容量值。

技術領域

本發明涉及物流資源的配送調度技術領域，具體地涉及一種協商機制下多車輛平臺的任務規劃系統。

背景技術

傳統VRP問題(車輛路徑問題)已經被證明是個NP-hard問題，當車輛路徑必須返回原點，即路線閉合時可總結為一類CVRP問題；當客戶的需求可拆分時可總結為一類SDVRP問題；當車輛的路線可以開放時可總結為一類OVRP問題，國內外學者已經從多個角度對上述VRP延伸問題進行建模，通過對文獻閱讀綜合分析，一般可以將問題求解模型分為：建立整數規劃、圖論以及其他形式的表達模型等三類。同時學者們運用精確算法(如：拉格朗日松弛法、列生成算法、動態規劃等)、啟發式算法(節約法、掃描法等)、元啟發式算法(如模擬退火算法、遺傳算法、蟻群算法等)等多種多類型算法，對上述各類VRP問題的模型進行了求解。上述闡述的事實說明，即便學者們針對VRP問題做出了大量的研究，但由于應用背景的變化，導致各個約束條件的變化，由此不斷的產生新型的VRP的衍生問題，依然有著重要的研究價值。

傳統商業模式下，物流主要指以大批貨物為主的運輸和倉儲。這樣物流環境下的調度運輸，用于對運輸車輛進行調度的方法也相對簡單。近年物流包裹小包裝、多頻次、碎片化的特征逐漸明顯，用于傳統物流的調度方法也逐漸難以滿足現有的物流條件。如何解決物流過程末端的由于“碎片化”導致的數量規模龐大的包裹配送問題，已成為物流企業所面臨的重要挑戰。

發明內容

本發明實施方式的目的是提供一種協商機制下多車輛平臺的任務規劃系統，該任務規劃系統能夠滿足現有的物流環境條件，提高大規模任務規劃的效率。

為了實現上述目的，本發明實施方式提供一種協商機制下多車輛平臺的任務規劃系統，所述任務規劃系統包括管控平臺和車輛平臺，其中，每個所述車輛平臺包括至少一輛運輸車；

管控平臺對接收到的任務集進行預處理以生成第一公告信息，所述第一公告信息包括每個任務的編號、對應的位置信息、對應的任務集合的編號、完成每個任務所在的任務集合內所有任務的最短路徑和對應的容量需求；

所述管控平臺從所述第一公告信息中隨機選取一個未被選取的任務，將被選取的任務發送至每個車輛平臺；

每個所述車輛平臺接收被選取的任務，能夠執行選取的任務的所述車輛平臺計算執行被選取的任務的執行成本，所述執行成本包括由于執行選取的任務所減少的剩余里程值以及剩余容量值，并進一步將執行成本和所述車輛平臺在執行完已被分配的任務的剩余能力發送至所述管控平臺，其中所述剩余能力包括所述車輛平臺在執行完已被分配的任務后的剩余里程值和剩余容量值；

所述管控平臺根據每個所述執行成本和所述剩余能力對被選取的任務進行分配；

判斷所述第一公告信息中是否存在未被選取的任務；

在判斷所述第一公告信息中存在未被選取的任務的情況下，再次從所述第一公告信息中隨機選取一個未被選取的任務，執行所述任務規劃方法的相應步驟直到所述第一公告信息中不存在未被選取的任務；

在判斷所述第一公告信息中不存在未被選取的任務的情況下，生成并發送第二公告信息，其中，所述第二公告信息包括任務和任務被分配給的所述車輛平臺的對應關系；

每個車輛平臺分別從所述第二公告信息中獲取被分配的任務；