[發明專利]組合優化問題的處理方法和裝置

在審

• 申請號: 201810344893.X
• 申請日: 2018-04-17
• 公開（公告）號: CN110390413A
• 公開（公告）日: 2019-10-29
• 發明（設計）人: 胡浩源;陳昱潔;韓坤鵬;王龍飛
• 申請（專利權）人: 菜鳥智能物流控股有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08
• 代理公司: 北京潤澤恒知識產權代理有限公司 11319
• 代理人: 冀曉愷

本申請公開了一種組合優化問題的處理方法和組合優化問題的處理裝置。所述組合優化問題的處理方法包括：在未滿足計算終止條件時，分別向多個計算單元提供計算任務對應的初始解；接收多個計算單元依據初始解執行所述計算任務獲得的解；針對所述解進行聚類，獲取聚類后的解集群；在確定滿足計算終止條件之后，從所述聚類后的解集群中確定最終解。本發明實施例提出的組合優化問題的處理方法可以針對同一個組合優化問題，利用多種搜索策略并行地進行搜索，充分發揮了不同搜索策略對于某一類型問題的求解優勢，從而能夠快速地獲得更好的解。

技術領域

本申請涉及計算機信息處理領域，特別是涉及一種組合優化問題的處理方法和組合優化問題的處理裝置。

背景技術

在目前的信息處理領域中，組合優化問題是最優化領域中的一類典型問題，即從組合問題的可行解集(一個整數，一個集合，一個排列，或者一個圖)中找出最優解。可定義為：

Θ為有限集合，f為Θ到實數集R上的映射，即f：Θ→R。求θ^*∈Θ，使得對于任意的θ′∈Θ，有f(θ^*)≤f(θ′)，即求解

經典的組合優化問題包括車輛路徑優化問題、裝箱問題、設施選址問題、計劃排程問題等。例如，在車輛路徑規劃問題中，車輛運輸成本是物流系統中配送成本的主要組成部分之一，所以車輛路徑規劃問題一直是物流業界和學術界的研究熱點之一。強大的路徑規劃算法能夠幫助物流企業大幅降低配送成本、提高配送效率。

結合圖1所示，車輛路徑規劃問題中，物流網絡中有若干個配送點a1、a2、a3、a4，每個配送點有不同數量的貨物需求，需要車輛從倉庫W取貨并配送到這些配送點，所需要優化的方案為如何將配送任務分配到不同的車輛上，以及安排車輛的配送路線，從而獲得最小化使用車輛數、最少的車輛總行駛距離等，減少車輛運輸成本。

在解決車輛路徑規劃問題時，搜索過程中的最優解例如可以包括三個方面，即：需要用車輛的數目n、每輛車應服務哪些配送點(例如一些車輛服務a1、a2配送點、另一些車輛服務a3、a4配送點)，以及從倉庫出發之后每輛車服務配送點的順序(例如某一車輛的配送順序為先a4，再a3，最后a1等)。即，最優解包括上述三個維度，滿足最小化使用車輛數、最少的車輛總行駛距離等要求。

在其他組合優化問題的領域中同樣存在著上述問題。為了避免大量的計算，業界提出了各種處理方法以解決這一問題。例如基于分解-并行遺傳算法的約束優化算法。這一算法首先將所需要優化的原問題分解為多個子問題和一個常規問題，然后對子問題進行迭代進化，從子問題中選擇滿足約束條件的染色體按照順序組成多條染色體，作為常規種群的初始種群，然后對常規問題和子問題進行并行遺傳算法迭代。此算法的缺點包括：需要對原問題進行合理精心的分解、僅使用單一算法、需要重復搜索才能獲得最優解等，造成了計算資源浪費、搜索過程冗長、搜索結果不夠優良。

發明內容

鑒于上述問題，本發明一實施例提出一種組合優化問題的處理方法和組合優化問題的處理裝置，以解決現有技術存在的問題。

為了解決上述問題，本申請一實施例公開一種組合優化問題的處理方法，包括：

在未滿足計算終止條件時，分別向多個計算單元提供計算任務對應的初始解；

接收多個計算單元依據初始解執行所述計算任務獲得的解；

針對所述解進行聚類，獲取聚類后的解集群；

在確定滿足計算終止條件之后，從所述聚類后的解集群中確定最終解。

為了解決上述問題，本申請一實施例還公開一種電子裝置，該電子裝置包括：

存儲器，用于存儲計算機可讀程序；

處理器，當所述處理器讀取所述存儲器中的計算機可讀程序時，所述電子裝置執行如下操作：