Minimization of Airtime in Cutting and Welding Applications

This paper evaluates the feasibility of applying the Lin-Kernighan algorithm to the problem of optimizing cutting and welding paths. A methodology was developed to solve this problem that is based on modifying the coordinate data presented to the Lin-Kernighan algorithm and to interpret the results of this optimization to ensure the problem constraints are followed. The efficiency of the method is tested on several sample problems with very promising results. In all cases, the method is able to find at least a near-optimal tour and was able to reduce the total cutting and air distance of an industrial problem by more than 12%. The solution is applicable to any problem that needs to determine the shortest path between individual shapes on a sheet.