平面多輪廓加工路徑優化模型及其近似算法

余國興　丁玉成　李滌塵

摘要：應用一種節點可變的廣義旅行商問題，為平面多輪廓加工路徑優化問題建模．針對在分層實體制造中，輪廓加工路徑的優化必須實時進行、優化計算時間必須小于因路徑縮短而節省的加工時間的要求，以及每層加工的輪廓數量通常少于10²每條輪廓的節點數可能為10³的特點，提出一種先用時間復雜度為O(n²)的最近鄰算法，求輪廓原始起點集合的旅行商問題解，然后在O(n)時間內改變每條輪廓的起點，進一步縮短路徑長度的2步優化近似算法，從而兼顧了輪廓加工特點和算法實時性的要求．實驗統計表明，該算法對路徑的優化程度比僅按傳統旅行商問題處理時提高了10％以上，且運行時間不超過0．1s.關鍵詞：輪廓加工；路徑優化；旅行商問題；分層實體制造中圖分類號：TH164；TP301文獻標識碼：A文章編號：0253—987X(2004)01—0039—04