Optimum drilling path planning for a rectangular matrix of holes using ant colony optimisation

This paper investigates optimum path planning for CNC drilling machines for a special class of products that involve a large number of holes arranged in a rectangular matrix. Examples of such products include boiler plates, drum and trammel screens, connection flanges in steel structures, food-processing separators, as well as certain portions of printed circuit boards. While most commercial CAD software packages include modules that allow for automated generation of the CNC code, the tool path planning generated from the commercial CAD software is often not fully optimised in terms of the tool travel distance, and ultimately, the total machining time. This is mainly due to the fact that minimisation of the tool travel distance is a travelling salesman problem (TSP). The TSP is a hard problem in the discrete programming context with no known general solution that can be obtained in polynomial time. Several heuristic optimisation algorithms have been applied in the literature to the TSP, with varying levels of success. Among the most successful algorithms for TSP is the ant colony optimisation (ACO) algorithm, which mimics the behaviour of ants in nature. The research in this paper applies the ACO algorithm to the path planning of a CNC drilling tool between holes in a rectangular matrix. In order to take advantage of the rectangular layout of the holes, two modifications to the basic ACO algorithm are proposed. Simulation case studies show that the average discovered path via the modified ACO algorithms exhibit significant reduction in the total tool travel distance compared to the basic ACO algorithm or a typical genetic algorithm.     

Optimal air-move path generation based on MMAS algorithm

Air-move paths are executed by machine tools to cut 2D patterns that must retract (or turn off) when travelling from one pattern to the next. These retractions are nonproductive and hence their travelling distances should be minimised. For instance, reducing air-move time can increase the efficiency of cloth cutting in the garment industry. In this paper, a novel algorithm is proposed to solve this problem. In several past works, this problem is formulated as an instance of the generalised travelling salesman problem. We divide this problem into two independent sub-optimal problems (pattern cutting order and entry/exit cutting point) and iteratively solve them using a max–min ant system. This strategy can greatly narrow down the search space. We also perturb the pattern cutting order to avoid dowelling at a local minimum. Experiments show that the proposed algorithm is able to obtain near-optimal solutions, with the results beating the three state-of-the-art algorithms that were used as the benchmarks.     

Tool path optimisation for flank milling ruled surface based on the distance function

This paper deals with optimised tool path generation for five-axis flank milling using signed point-to-surface distance function. The main idea is that the geometrical deviations between the design surface and the machined surface are minimised by fine tuning the cutter locations. Based on the tangency conditions in envelope theory, the analytic representation of the envelope surface of a cutter undergoing five-axis motion is first obtained. Then the geometrical deviations between the envelope surface (i.e. machined surface) and the design surface are calculated. Optimisation of the five-axis tool path is modeled as the fine tuning of the initial cutter locations under the minimum zone criterion recommended by ANSI and ISO, which requires minimisation of the maximum geometrical deviation between the design surface and the envelope surface. Using the signed point-to-surface distance function, tool path optimisation for finish milling is formulated as a constrained optimisation problem. Based on the first-order Taylor approximation of the signed distance function, two sequential approximation algorithms for the Minimax and Least Square optimisations are developed. Numerical examples, in which a conical tool is chosen as a special case of flank machining ruled surface, verify the proposed strategy.     

Model of megalopolises in the tool path optimisation for CNC plate cutting machines

We consider the issues of tool path optimisation under constraints and formulate a mathematical problem of visiting megalopolises. The megalopolises model is the result of the discretisation of the tool path problem for CNC plate cutting machines. The order of visits is subject to precedence constraints. In addition, the cost functions depend on the set of pending tasks. The quality criterion is a variety of the additive criterion. The problem is established within the dynamic programming framework, however, a heuristic is proposed and implemented to solve practical problems of large dimensionality.     

Tool path generation via the multi-criteria optimisation for flat-end milling of sculptured surfaces

A method of generating optimal tool paths for sculptured surface machining with flat-end cutters is presented in this paper. The inclination and tilt angles, as well as the feed directions of the cutter at each cutter contact point on a machining path are optimised as a whole so that the machining width of the tool path can be as large as possible, and concerns such as smooth cutter motion, gouging avoidance, scallop height and machining widths overlap are also considered when calculating a path. A multi-criteria tool path optimisation model is introduced, and it is converted into a single objective optimisation with the weighted sum method. The Differential Evolution (DE) algorithm is suitable for solving this highly non-linear problem. However, the searching process of the DE algorithm may be trapped in local minima due to large number of design variables. Therefore, an algorithm combining the DE algorithm and the sequence linear programming algorithm is developed to solve this optimisation model. The proposed method is applied to two freeform surfaces to illustrate its effectiveness.     

A lower bound for the shortest Hamiltonean path in directed graphs

Summary We present in this paper a Lagrangean relaxation of a particular formulation for the shortest Hamiltonean path problem in a directed graph. The dual problem defined gives a lower bound. This relaxation has not the integrality property. To solve the dual problem we have to find a shortest path (not constrained to be elementary) with a fixed number of arcs, and solve a classical shortest path problem with nonnegative lengths.     

A hybrid particle swarm based method for process planning optimisation

A process planning (PP) problem is defined as to determine a set of operation-methods (machine, tool, and set-up configuration) that can convert the given stock to the designed part. Essentially, the PP problem involves the simultaneous decision making of two tasks: operation-method selection and sequencing. This is a combinatorial optimisation problem and it is difficult to find the best solution in a reasonable amount of time. In this article, an optimisation approach based on particle swarm optimisation (PSO) is proposed to solve the PP problem. Due to the characteristic of discrete process planning solution space and the continuous nature of the original PSO, a novel solution representation scheme is introduced for the application of PSO in solving the PP problem. Moreover, two kinds of local search algorithms are incorporated and interweaved with PSO evolution to improve the best solution in each generation. The numerical experiments and analysis have demonstrated that the proposed algorithm is capable of gaining a good quality solution in an efficient way.     

Non-productive tool path optimisation for four-axis milling using the simulated annealing algorithm

The paper concerns the development of generic computer aided optimisation techniques for the minimisation of residence time of a multi-component pallet in a horizontal machining centre. A general methodology has been established to take a part program for a multi-faced pallet, that involves many components, typically 20–30, and tool changes, segment it to extract the position and machining conditions embedded in it, automatically re-sequence the machining operations to find the optimum total tool path, and regenerate a new part program with the optimised machining sequence. A range of case studies has been used to: validate the software, and to demonstrate its ability to minimise the total pallet residence time. The techniques developed can be used for semi-automatic part programming of the entire pallet with multi-components, and with an auto-selection multi-tool facility. The software is capable of achieving a large reduction in part programming time, as well as reducing the non-machining time. It is shown that the use of the optimisation package with a range of part programs reduces the total pallet residence time by a factor between 9.5 and 36%, and consequently has the potential to achieve considerable economic gains.     

Integrated task sequencing and path planning for robotic remote laser welding

This paper investigates the problem of integrated task sequencing and path planning in Remote Laser Welding (RLW). It is shown that finding the appropriate order of welding tasks is crucial for exploiting the efficiency of this new joining technology, and this can be achieved only if the robot path is considered already at the time of sequencing. For modelling the problem, a novel extension of the well-know Travelling Salesman Problem with neighbourhoods and durative visits, denoted as TSP-ND, is introduced. Basic properties of this problem are formally proven, and a GRASP meta-heuristic algorithm is proposed for solving it. Extensive computational experiments demonstrate that the novel approach solves efficiently industrially relevant problems, and it achieves substantial improvement in cycle time compared to the single earlier approach in the literature dedicated to RLW, as well as compared to a decomposition approach to solving the TSP-ND model.     

假肢接受腔阳模数控加工刀具的运动轨迹规划

应用表面建模方法，建立了假肢接受腔的三维数学模型。针对假肢接受腔的独特外形特征，研制了加工假肢接受腔阳模的三轴联动数控机床，该机床控制系统采用开环系统，可以运行CAD／CAM软件。对加工假肢接受腔阳模的刀具进行了运动轨迹规划，推导出了切削点的计算公式。根据三维刀具半径补偿原理，确定了刀具的刀位点运动轨迹。经过临床实例加工表明：该数控机床和刀具运动轨迹规划算法完全满足实际应用要求。     

Cutter size optimisation and interference-free tool path generation for five-axis flank milling of centrifugal impellers

Strategies for cutter size optimisation and interference-free tool path generation are proposed for five-axis flank milling of centrifugal impellers. To increase the material removal rate and provide a stronger tool shank during flank milling, the cutter size is first maximised under a set of geometric constraints. The tool path is then globally optimised in accordance with the minimum zone criterion for the determined optimal cutter size. Aside from the local interference of the cutter with the design surface, the global interferences with the hub surface and the adjacent blade surface are also considered in the optimisation models. Interference is indicated by the signed distance from the sampled point on the blade surface to the tool envelope surface. This distance is calculated without constructing the envelope surface. On the basis of the differential property of the distance function, we choose a sequential linear programming method in implementing the optimisations. This approach applies to generic rotary cutters, such as cylindrical and conical tools. Simulations are conducted to obtain the optimal cutter size and generate an interference-free tool path for a practical impeller. Simultaneously, a software module that can generate tool envelope surfaces and verify geometric errors is used to validate the proposed method.     

Large neighbourhood search based on mixed integer programming and ant colony optimisation for car sequencing

We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requiring the same options need to be distributed far enough apart. The desired separation is not always feasible, leading to an optimisation problem that minimises the violation of the ideal separation requirements. In order to solve the problem, we use a large neighbourhood search (LNS) based on mixed integer programming (MIP). The search is implemented as a sliding window, by selecting overlapping subsequences of manageable sizes, which can be solved efficiently. Our experiments show that, with LNS, substantial improvements in solution quality can be found.     

Applying ant colony system algorithm in the navigation process for plastic injection mould manufacturing scheduling optimisation

Under the computer-aided design (CAD) software architecture, this study aims to develop navigation processes for plastic injection mould manufacturing scheduling optimisation. Mould manufacturing is a job-shop scheduling problem, with components processing sequence under limited conditions. This study uses the search capabilities of the ant colony system (ACS) to determine a set of optimal schedules, under the condition of not violating the processing sequences, in order to minimise the total processing time and realise makespan minimisation. As the test results suggest, it can save up to 52% of manufacturing time, and also substantially shorten the processing time of the production plan. This study completes the algorithm steps and manufacturing process time estimation by operations on the navigation interface, and uses mould manufacturing scheduling to make optimised arrangements of finished components. The method can comply with the on-site manufacturing processes, improve scheduling prediction accuracy and consistently and efficiently integrate the optimisation scheduling system and mould manufacturing system. Visualised information of the scheduling results can be provided, thus allowing production management personnel to ensure smooth scheduling.     

Ant colony optimisation algorithm for distribution-allocation problem in a two-stage supply chain with a fixed transportation charge

In a fixed charge transportation problem, each route is associated with a fixed charge (or a fixed cost) and a transportation cost per unit transported. The presence of the fixed cost makes the problem difficult to solve, thereby requiring the use of heuristic methods. In this paper, an algorithm based on ant colony optimisation is proposed to solve the distribution-allocation problem in a two-stage supply chain with a fixed transportation cost for a route. A numerical study on benchmark problem instances has been carried out. The results obtained for the proposed algorithm have been compared with that for the genetic algorithm-based heuristic currently available in the literature. It is statistically confirmed that the proposed algorithm provides significantly better solutions.     

Solving a time constrained two-crane routing problem for material handling with an ant colony optimisation approach: an application in the roof-tile industry

This paper presents an ant colony optimisation (ACO)-based solution approach for a real-world two-crane routing problem, where a number of different load carriers must be moved within a given cycle time by two gantry cranes in a continuous production process for roof tiles. The cranes have to transport the roof-tile batches and to return the load carriers and intermediate pads for subsequent batches. A feasible solution has to observe workflow-, space-, collision-, and machine-cycle constraints. The objective is to find a feasible schedule that minimises the working time for both cranes. The authors compare different solution approaches in terms of learning – and visibility strategies based on ACO in extensive numerical studies. A visibility concept is used to both partition and balance workload between the cranes.     

一种新型包装码垛机器人路径规划方法

目的为了提高码垛机器人的工作效率,减小能量损耗,优化机器人末端抓手的工作轨迹。方法建立机器人路径规划的数学模型,在此基础上对传统的蚁群算法进行改进,将环境中局部的机器人路径信息引入蚁群信息素的初始化和路径选择概率中,提高蚁群算法的收敛速度,并防止算法早熟,避免算法陷入局部最优。结果仿真结果表明,改进后的蚁群算法收敛速度更快,能够在较短时间内规划出最佳路径。结论所提方法能够明显提高码垛机器人最佳路径搜索能力,对于提升机器人运行效率具有重要指导意义。     

基于Dijkstra-蚁群算法的泊车系统路径规划研究

针对智能停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,提出了一种基于Dijkstra-蚁群算法(Dijkstra-ACO)的泊车系统路径规划方法.首先利用链接可视图法建立环境模型,并在此环境模型下,采用Dijkstra算法规划出AGV的初始路径;其次,通过引入节点随机选择机制、调整信息素更新方式和限定信息素阈值策略等对基本蚁群算法进行优化改进;最后,选用改进的蚁群算法对初始路径进行优化.结果显示:Dijkstra算法和混合算法均能使AGV有效避开障碍物,然后搜索到一条从起点到终点的无碰优化路径;与Dijkstra算法相比,混合算法能有效提高路径搜索效率,缩短搜索路径长度,改善搜索路径质量,表明该算法正确、可行及有效,且具有较强的全局搜索能力和较好的收敛性能,能够满足AGV存取车路径规划的要求.     

A new approach for rebalancing of U-lines with stochastic task times using ant colony optimisation algorithm

In real world, line balancing involves existing lines in existing factories and the line typically needs to be rebalanced rather than balanced. Rebalancing of a U-line can be defined as a changeover process from its initial configuration to a new configuration for a while due to the reasons such as demand variations, changes in product design and changes in task times, etc. This study defines U-line rebalancing problem with stochastic task times and proposes a solution procedure based on ant colony optimisation. The objective of the proposed algorithm is to minimise total cost of rebalancing which is the sum of task transposition costs, workstation opening/closing costs and operating costs of workstations for a particular planning horizon. A comprehensive experiment is conducted to generate problem instances and to compare rebalancing costs of U-lines by means of several factors. A total of 6600 rebalancing solutions are obtained and several comparisons are performed.     

Using the global optimisation methods to minimise the machining path length of the free-form surfaces in three-axis milling

During the machining of free-form surfaces using three-axis numerically controlled machine (NC), several parameters are chosen arbitrary and one of the most important is the feed motion direction. The main objective of this study is to minimise the machining time of complex surfaces while respecting a scallop height criteria. The analytical expression of the machining time is not known and by hypothesis, it is assumed to be proportional to the path length crossed by the cutting tool. This path length depends on the feed direction. To have an optimal feed direction at any point, the surface is divided into zones with low variation of the steepest slope direction. The optimization problem was formulated aiming at minimizing the global path length. Furthermore, a penalty reflecting the time loss due to the movement of the tool from one zone to another one is taken into account. Several heuristics are used to resolve this problem: Clarke and Wrights, Greedy randomized adaptive search procedure, Tabu search and Nearest neighbour search. An example illustrates our work by applying the different heuristics on a test surface. After simulations, the results obtained present a significant saving of paths length of 24% compared to the machining in one zone.     

Tool path generation for five-axis machining of blisks with barrel cutters

A barrel cutter has a cutting segment with a large radius on its profile, and this arc segment allows the cutter to tilt away from the part surface, avoiding the collisions of the tool with the part. Therefore, barrel cutters are suitable for five-axis blisk machining. However, the barrel cutters are more challenging for CAM software to generate paths. A method of generating collision-free and large-machining width flank milling paths with smooth axes movements for blisk machining with barrel cutters is proposed. Local gouge between the tool flute surface and the blade to be machined is considered, and the collisions of the blisk with the non-cutting parts of the tool, i.e. tool shank and holder, are also detected. The machined part geometry is the complement of the cutter’s swept envelope from the stock. Accordingly, the swept profile of the cutter at each cutter contact point is employed to evaluate the machining width naturally. Thereafter, a multi-criteria tool path generation model is established, and it is converted into a single-objective optimization with the weighted sum method. An algorithm based on the Differential Evolution algorithm is developed to solve this model. The numerical example illustrates the effectiveness of the proposed method.