Application of precedence constrained travelling salesman problem model for tool path optimization in CNC milling machines
DOI:
https://doi.org/10.11121/ijocta.01.2019.00662Keywords:
Tool path optimization, mathematical modelling, travelling salesman problem, combinatorial optimizationAbstract
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.
Downloads
References
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.
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.
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.
D’Souza, K., Castelino, R., Wright, P.K. (2003). Tool-path optimization for minimizing airtime during machining. Journal of Manufacturing Systems, 22, 173-180.
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.
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.
Lazoglu, I., Manav, C., Murtezaoglu, Y. (2009). Tool path optimization for free form surface machining. CIRP Annals, 58(1), 101-104.
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.
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.
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.
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.
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.
Kolahan, F., Liang, M. (2000). Optimization of hole-making operations: A tabu search approach. International Journal of Machine Tools and Manufacture, 40(12), 1735-1753.
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.
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.
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.
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.
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.
Kumar, A., Pachauri, P.P. (2012). Optimization drilling sequence by genetic algorithm. International Journal of Scientific Research Publications, 2(9), 1-7.
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.
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.
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.
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.
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.
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.
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.
Zhang, W.-B., Zhu, G.-Y. (2018). Drilling path optimization by optimal foraging algorithm. IEEE Transactions on Industrial Informatics, 14(7), 2847-2856.
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.
Kubo, M., Kasugai, H. (1991). The precedence constrained traveling salesman problem. Journal of the Operations Research, 34(2), 152-172.
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.
Bellmore, M., Nemhauser, G.L. (1968). The traveling salesman problem: A Survey. Operations Research, 16(3), 538-558.
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.
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.
Sung, J., Jeong, B. (2014). An adaptive evolutionary algorithm for travelling salesman problem with precedence constraints. Hindawi-The Scientific World Journal, 2014, 1-11.
Skinderowicz, E. (2017). An improved ant colony system for the sequential ordering problem. Computers and Operations Research, 86, 1-17.
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
