Application of precedence constrained travelling salesman problem model for tool path optimization in CNC milling machines
In this study, a tool path optimization problem in Computer Numerical Control (CNC) milling machines is considered to increase the operational efficiency rates of a company. In this context, tool path optimization problem of the company is formulated based on the precedence constrained travelling salesman problem (PCTSP), where the general form of the TSP model is extended by taking the precedence of the tool operations into account. The objective of the model is to minimize total idle and unnecessary times of the tools for internal operations. To solve the considered problem, a recent optimization algorithm, called Satin Bowerbird Optimizer (SBO), is used. Since the SBO is first introduced for the global optimization problems, the original version of the SBO is modified for the PCTSP with discretization and local search procedures. In computational studies, first, the performance of the proposed algorithm is tested on a well-known PCTSP benchmark problems by comparing the proposed algorithm against two recently proposed meta-heuristic approaches. Results of the comparisons show that the proposed algorithm outperforms the other two competitive algorithms by finding better results. Then, the proposed algorithm is carried out to optimize the hole drilling processes of three different products produced by the company. For this case, with up to 4.05% improvement on the operational times was provided for the real-life problem of the company. As a consequence, it should be noted that the proposed solution approach for the tool path optimization is capable of providing considerable time reductions on the CNC internal operations for the company.
[1] Bohez, E., Makhanov, S.S., Sonthipaumpoon, K.(2000). Adaptive nonlinear tool path optimization for five-axis machining. International Journal of Production Research, 38(17), 4329-4343.
[2] Makhanov, S.S., Batanov, D., Bohez, E., Sonthipaumpoon, K., Anotai, W. (2002). On the tool-path optimization of a milling robot. Computers and Industrial Engineering, 43(3), 455-472.
[3] Chandrasekaran, M., Muralidhar, M., Murali Krishna, C., Dixit, U.S. (2010). Application of soft computing techniques in machining performance prediction and optimization: A literature review. The International Journal of Advanced Manufacturing Technology, 46(5-8), 445-464.
[4] D’Souza, K., Castelino, R., Wright, P.K. (2003). Tool-path optimization for minimizing airtime during machining. Journal of Manufacturing Systems, 22, 173-180.
[5] Park, K.S., Kim, S.H. (1998). Artificial intelligence approaches to determination of CNC machining parameters in manufacturing: A review. Artificial Intelligence in Engineering, 12(1-2), 127-134.
[6] Lasemi, A., Xue, D., Gu, P. (2010). Recent development in CNC machining of freeform surfaces: A state-of-the-art review. Computer-Aided Design, 42(7), 641-654.
[7] Lazoglu, I., Manav, C., Murtezaoglu, Y. (2009). Tool path optimization for free form surface machining. CIRP Annals, 58(1), 101-104.
[8] Oysu, C., Bingul, Z. (2009). Application of heuristic and hybrid-GASA algorithms to tool-path optimization problem for minimizing airtime during machining. Engineering Applications of Artificial Intelligence, 22(3), 389-396.
[9] Dewil, R., Küçükoğlu, İ ., Luteyn, C., Cattrysse, D.(2018). A critical review of multi-hole drilling path optimization. Achieves of Computational Methods in Engineering, In Press, 1-11.
[10] Abidin, N.W.Z., Ab Rashid, M.F.F., Mohamed, N.M.Z.N. (2017). A review of multi-holes drilling path optimization using soft computing approaches.Achieves of Computational Methods in Engineering,In Press, 1-12.
[11] Narooei, K.D., Ramli, R., Nizam, M., Rahman, A., Iberahim, F., Qudeiri, J.A. (2014). Tool routing path optimization for multi-hole drilling based on ant colony optimization. World Applied Sciences Journal, 32(9), 1894-1898.
[12] Linn, R.J., Liu, J., Kowe, P.S.H (1999). Efficient heuristics for drilling route optimization in printed circuit board manufacturing. Journal of Electronics Manufacturing, 8(2), 127-138.
[13] Kolahan, F., Liang, M. (2000). Optimization of hole- making operations: A tabu search approach.International Journal of Machine Tools andManufacture, 40(12), 1735-1753.
[14] Abbas, A.T., Aly, M.F., Hamza, K. (2011). Optimum drilling path planning for a rectangular matrix of holes using ant colony optimization. International Journal of Production Research, 49(19), 5877-5891.
[15] Montiel-Ross, O., Medina-Rodrı´guez, N., Sepu´lveda, R., Melin, P. (2012). Methodology to optimize manufacturing time for a CNC using a high performance implementation of ACO. International Journal of Advanced Robotic Systems, 9, 1-10.
[16] Zhu, G.-Y., Zhang, W.-B. (2008). Drilling path optimization by the particle swarm optimization algorithm with global convergence characteristics.International Journal of Production Research,46(8), 2299-2311.
[17] Onwubolu, G.C., Clerc, M. (2004). Optimal path for automated drilling operations by a new heuristic approach using particle swarm optimization.International Journal of Production Research,42(3), 473-491.
[18] Dalavi, A.M., Pawar, P.J., Singh T.P. (2016). Optimal sequence of hole-making operations using particle swarm optimisation and shuffled frog leaping algorithm. Engineering Review, 36(2), 187- 196.
[19] Kumar, A., Pachauri, P.P. (2012). Optimization drilling sequence by genetic algorithm. International Journal of Scientific Research Publications, 2(9), 1- 7.
[20] Nabeel,P., Abid, K., Abdulrazzaq, H.F. (2014). Tool path optimization of drilling sequence in CNC machine using genetic algorithm. Innovation System Design and Engineering, 5(1), 15-26.
[21] Khalkar, S., Yadav, D., Singh, A. (2015). Optimization of hole making operations for sequence precedence constraint. International Journal of Innovative and Emerging Research in Engineering, 2(7), 26-31.
[22] Pezer, D. (2016). Efficiency of tool path optimization using genetic algorithm in relation to the optimization achieved with the CAM software. Procedia Engineering, 149, 374-379.
[23] Raja, C.K.B., Saravanan, M. (2017). Genetic algorithm for TSP in optimizing CNC tool path.International Journal of Engineering Technology, Management and Applied Sciences, 5(2), 139-146.
[24] Tamjidy, M. (2015). Biogeography based optimization (BBO) algorithm to minimize non- productive time during hole-making process. International Journal of Production Research, 53(6), 1880-1894.
[25] Kanagaraj, G., Ponnambalam, S.G., Loo, C.K.(2015). Charged system search algorithm for robotic drill path optimization. Proceedings of the 2015 International Conference on Advanced Mechatronic Systems, Beijing, China, 125-130.
[26] Lim, W.C.E., Kanagaraj, G., Ponnambalam, S.G.(2016). A hybrid cuckoo search-genetic algorithm for hole-making sequence optimization, Journal of Intelligent Manufacturing, 27, 417-429.
[27] Zhang, W.-B., Zhu, G.-Y. (2018). Drilling path optimization by optimal foraging algorithm. IEEE Transactions on Industrial Informatics, 14(7), 2847- 2856.
[28] Moosavi, S.H.S., Bardsiri, V.K. (2017). Satin bowerbird optimizer: A new optimization algorithm to optimize ANFIS for software development effort estimation. Engineering Applications of Artificial Intelligence, 60, 1-15.
[29] Kubo, M., Kasugai, H. (1991). The precedence constrained traveling salesman problem. Journal of the Operations Research, 34(2), 152-172.
[30] Miller, C.E., Tucker, A.W., Zemlin, R.A. (1960). Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326- 329.
[31] Bellmore, M., Nemhauser, G.L. (1968). The traveling salesman problem: A Survey. Operations Research, 16(3), 538-558.
[32] Crawford, B., Soto, R., Astorga, G., Garcia, J., Castro, C., Paredes, F. (2017). Putting continuous metaheuristics to work in binary search spaces.Hindawi-Complexity, 2017, 1-17.
[33] Tasgetiren, M.F., Liang, Y.-C., Sevkli, M., Gencyilmaz, G. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European Journal of Operational Research, 177, 1930-1947.
[34] Sung, J., Jeong, B. (2014). An adaptive evolutionary algorithm for travelling salesman problem with precedence constraints. Hindawi-The Scientific World Journal, 2014, 1-11.
[35] Skinderowicz, E. (2017). An improved ant colony system for the sequential ordering problem. Computers and Operations Research, 86, 1-17.