열린 윤곽선 부재로 이루어진 판재의 절단가공경로 최적화를 위한 혼합형 유전알고리즘
A Hybrid Genetic Algorithm for Optimizing Torch Paths to Cut Stock Plates Nested with Open Contours
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper considers a problem of optimizing torch paths to cut stock plates nested with open contours. For each contour, one of the two ending points is to be selected as a starting point of cutting with the other being the exit point. A torch path is composed of a single depot and a series of starting and ending points of contours to be cut. The torch path optimization problem is shown to be formulated as an extended version of the standard travelling salesman problem. To solve the problem, a hybrid genetic algorithm with the local search of torch paths is proposed. The genetic algorithm is tested for hypothetical problems whose optimal solutions are known in advance due to the special structure of them. The computational results show that the algorithm generates very near optimal solutions for most cases of the test problems, which verifies the validity of the algorithms.
Abstract
This paper considers a problem of optimizing torch paths to cut stock plates nested with open contours. For each contour, one of the two ending points is to be selected as a starting point of cutting with the other being the exit point. A torch path is composed of a single depot and a series of starting and ending points of contours to be cut. The torch path optimization problem is shown to be formulated as an extended version of the standard travelling salesman problem. To solve the problem, a hybrid genetic algorithm with the local search of torch paths is proposed. The genetic algorithm is tested for hypothetical problems whose optimal solutions are known in advance due to the special structure of them. The computational results show that the algorithm generates very near optimal solutions for most cases of the test problems, which verifies the validity of the algorithms.
참고문헌 (19)
- Bentley,J.L, "Fast Algorithms for Geometric Traveling Salesman Problems", ORSA Journal on Computing, 4(4), pp.387~411 (1992)
- Castelino,K, "Toolpath Optimization for Minimizing Airtime during Machining", Journal of Manufacturing Systems, 22(3), pp.173~180 (2002)
- Chen,J.C, "A Hybrid-coded Genetic Algorithm based Optimization of Non-productive Paths in CNC Machining", Int.J.of Advanced Manufacturing Technology, 20, pp.163~168 (2002)
- Davis,L, "Applying Adaptive Algorithms to Epistatic Domains", Proceedings of the International Joint Conference on Artificial Intelligence, pp.162~164 (1985)
- Freisleben,B, "A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems", Proceedings of IEEE Int'l Conference on Evolutionary Computation, pp.616~621 (1996)
- Gen, M, "Genetic Algorithms and Engineering Optimization" (2000), John Wiley and Sons
- Han,G.C, "Global Torch Generation for 2-D Laser Cutting Process using Simulated Annealing", Intelligent Automation for Soft Computing, 4(2), pp.97~108 (1998)
- Jackson,S.D, "Automatic Generation of 2-axis Laser Cutter NC Machine Program and Path Planning from CAD", Computers in Industry, 21, pp.223~231 (1993)
- Jang,C.D, "An Approach to Efficient Nesting and Cutting Path Optimization of Irregular Shapes", Journal of Ship Production, 15(3), pp.129~135 (1999)
- Khan,W.A, "Determination of Optimal Path under Approach and Exit Constraints", European Journal of Operational Research, 117, pp.310~325 (1999)
- Kim,Y, "Global Cuttingpath Optimization Considering the Minimum Heat Effect with Microgenetic Algorithm", Journal of Marine Science and Technology, 9, pp.70~79 (2004)
- Lee,M.-K, "Cutting Path Optimization in CNC Cutting Processes Using a Two-step Genetic Algorithm", International Journal of Production Research, 44(24), pp.5307~5326 (2006)
- Lin,S, "Computer Solutions of the Traveling Salesman Problem", Bell systems Technical Journal, 44, pp.2245~2269 (1965)
- Liu,T.K, "Optimization of Short-haul Aircraft Schedule Recovery Problems Using a Hybrid Multiobjective Genetic Algorithm", Expert Systems with Applications, 37(3), pp.2307~2315 (2010)
- Manber,U, "Pierce Point Minimization and Optimal Torch Path Determination in Flame Cutting", J.of Manufacturing Systems, 3(1), pp.81~99 (1984)
- Mutty, K, "Linear and Combinatorial Programming" (1976), John Wiley and Sons
- Oysu,C, "Application of Heuristic and Hybrid-GASA Algorithms to Tool-Path Optimization Problem for Minimizing Airtime during Machining", Engineering Applications of Artificial Intelligence, 22, pp.389~396 (2009)
- Raggenbass,A, "Stamping-laser Combination in Sheet Processing", Annals of the CIRP, 38(1), pp.291~294 (1989)
- Wah,P.K, "Tool Path Optimization in Layered Manufacturing", IIE Transactions, 34, pp.335~347 (2002)