[發明專利]加工路徑規劃方法、智能終端以及存儲裝置

有效

• 申請號: 202110784095.0
• 申請日: 2021-07-12
• 公開（公告）號: CN113256035B
• 公開（公告）日: 2021-11-19
• 發明（設計）人: 王秋實;李會江;馮征文;李士才;甘文峰
• 申請（專利權）人: 廣州中望龍騰軟件股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06F30/27;G06F111/06
• 代理公司: 廣州市越秀區哲力專利商標事務所(普通合伙) 44288
• 代理人: 曾令軍

本發明提供一種加工路徑規劃方法、智能終端以及存儲裝置，該加工路徑規劃方法包括：S101：根據初始化策略選擇加工路徑中的節點構建環路；S102：基于環路求解旅行商問題，根據求解結果加載當前最優解，當前最優解為當前最優路徑；S103：修改當前最優路徑中的節點連接方式以形成新的環路；S104：判斷是否達到最大迭代次數，若是，則執行S105，若否，則執行S102；S105：根據當前最優解輸出加工路徑的最優解。本發明能夠通過修改路徑的方式不斷的嘗試求解旅行商問題，不容易陷入局部最優解，且框架結構簡單，降低了計算量和設備的計算能力要求，節省了計算成本，還可以通過不同的初始化策略進一步提高算法的搜索效率的精確度，可擴展性強。

技術領域

本發明涉及加工路徑規劃領域，尤其涉及一種加工路徑規劃方法、智能終端以及存儲裝置。

背景技術

在CAM加工中，一般會采取將整個加工對象進行分區，之后使用刀軌規劃算法規劃每個分區內部的加工方式。但是，如何在不同的加工分區之間進行轉移，這個路徑的設計需要進行規劃計算。將加工區域看做是一個節點，加工區域之間的轉移路徑看做是邊，則加工區域轉移路徑問題就可以看做是如何找到一條最短路徑訪問所有節點，且所有節點只訪問一次，所以整個加工問題可以看做是旅行商問題（TravelingSalesmanProblem，TSP）。

旅行商問題是圖論中著名的問題，問題的表述是“已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉回路”。該問題的解空間規模非常大，假如有N個節點，全部路徑的組合有N!個，在進行路徑規劃時計算量大，對設備的計算能能力要求高，提高了計算成本。而且，一些啟發式求解算法比如蟻群算法、遺傳算法等，非常容易陷入局部最優解，造成求解精度比較低，不能很好地進行路徑規劃。

發明內容

為了克服現有技術的不足，本發明提出一種加工路徑規劃方法、智能終端以及存儲裝置，根據初始化策略選擇節點構建環路，對該環路求解TSP問題得到最優解后，通過修改該最優解的路徑形成新的環路，利用新的環路求解TSP問題的方式跳出當前最優解，能夠通過修改路徑的方式不斷的嘗試求解旅行商問題，不容易陷入局部最優解，且框架結構簡單，降低了計算量和設備的計算能力要求，節省了計算成本，還可以通過不同的初始化策略進一步提高算法的搜索效率的精確度，可擴展性強。

為解決上述問題，本發明采用的一個技術方案為：一種加工路徑規劃方法，所述加工路徑規劃方法包括：S101：根據初始化策略選擇加工路徑中的節點構建環路；S102：基于所述環路求解旅行商問題，根據求解結果加載當前最優解，所述當前最優解為當前最優路徑；S103：修改所述當前最優路徑中的節點連接方式以形成新的環路；S104：判斷是否達到最大迭代次數，若是，則執行S105，若否，則執行S102；S105：根據所述當前最優解輸出所述加工路徑的最優解。

進一步地，所述根據初始化策略選擇加工路徑中的節點構建環路的步驟之前還包括：判斷是否存在兩個節點之間的轉移路徑不對稱；若是，對所述加工路徑中的節點的數據進行預處理；若否，根據初始化策略選擇加工路徑中的節點構建環路。

進一步地，所述對所述加工路徑中的節點的數據進行預處理的步驟具體包括：構建所述加工路徑中節點的替代距離矩陣，其中，D為加工路徑中節點之間的距離矩陣，N為節點數。

進一步地，所述對所述加工路徑中的節點的數據進行預處理的步驟還包括：

對所述加工路徑中每個原始節點添加一個輔助節點，定義所述原始節點以及所述原始節點的輔助節點為相互固定節點，并獲取所述加工路徑中各節點之間的距離。

進一步地，通過距離方程獲取加工路徑中各節點之間的距離，所述距離方程為：

其中，P為所有輔助節點的集合，輔助節點為，Q為所有原始節點集合，原始節點為Node_i≤n，M為所有節點之間距離的最大值。