徐建明，林示麟，董　輝，俞　立
浙江工業大學信息工程學院，浙江杭州

摘　　　要：考慮一類輪廓切割順序受限的加工路徑優化問題。遵循由內到外的輪廓切割約束條件，以遍歷所有待切割輪廓且刀頭在輪廓間移動的空行程距離較短為優化目標，把約束條件轉化到遺傳算法編碼問題。采用啟發式搜索技術以加快遺傳算法的爬山速度，并且能自適應調整交叉和變異概率。實際應用結果表明所提算法能有效縮短空行程。

關　鍵　詞：路徑優化；遺傳算法；啟發式搜索；輪廓切割

１　引　言
在服裝、鞋、箱包的面料裁割過程中，刀頭沿輪廓切割時間相對固定，通過路徑優化，可以縮短刀頭在輪廓間移動的空行程距離，以節省加工時間。輪廓加工順序的不同以及加工起點的不一樣都影響著加工路徑的長度；因而不改變加工起點的優化是不充分的［１�玻玻荩�不改變輪廓順序的優化也不充分［３］。因而，需要在一定裁割順序限制下，對輪廓裁割順序和裁割起點進行優化選擇，以縮短面料裁割加工時間。面料裁割加工路徑的優化問題是一類廣義旅行商問題（ＧＴＳＰ），當優化規模較大時，將ＧＴＳＰ轉化為ＴＳＰ問題或采用數學規劃直接求取方法往往難以處理［４］；而基于隨機值的遺傳算法［５］對ＧＴＳＰ問題求解卻無法解決路徑順序受限問題。本文在輪廓切割順序受限的情況下，采用分層法將輪廓分層構成染色體，把約束條件轉化到染色體編碼問題中，使得染色體解碼后的路徑切割順序都是可行的，從而大大縮小搜索空間，排除產生不可行路徑的可能。算法計算過程中結合了啟發式搜索技術并采用了自適應調整交叉變異概率，加強了遺傳算法的尋優能力并能根據實際情況適時退出遺傳算法，達到優化效果與優化時間的折中。

登錄網站后可下載文件