For Libraries For Publication Open Access Downloads About Us Contact Us
Paper Titles
Investigation on Mechanical Properties of Blend Virgin and Recycled Acrylonitrile-Butadiene-Styrene (ABS) in Injection Molding
p.8
Cooling Rate Observation in Quenching Process Using Carbon Nanofluids for S45C Carbon Steel
p.13
Sustainable Turning of Biocompatible Materials Using Eco Nano-Mist Technique
p.18
Enhancement of Impact Toughness in Mild Steel Weldments under Low Temperature Applications
p.23
Solving the Laser Cutting Path Problem Using Population-Based Simulated Annealing with Adaptive Large Neighborhood Search
p.29
Multi-Response Optimization of Dissimilar Al-Ti Alloy FSW Using Taguchi - Grey Relational Analysis
p.35
Designs and Evaluations of a Gas Atomizer to Fabricate Stainless Steel Metal Powder to Be Applied at a Metal Injection Molding
p.40
A Comparative Study of EDD and PM-EDD in Producing Holes in Inconel 718 Alloy
p.48
Effect of Pressure on the Gas Atomizer to Fabricate Stainless Steel Metal Powder
p.54

Solving the Laser Cutting Path Problem Using Population-Based Simulated Annealing with Adaptive Large Neighborhood Search

Article Preview

Abstract:

This paper presents an alternative algorithm for solving the laser cutting path problem which was modeled as Generalized Traveling Salesman Problem (GTSP). The objective is to minimize the traveling distance of laser cutting of all profiles in a given layout, where a laser beam makes a single visit and then does the complete cut of individual profile in an optimum sequence. This study proposed a hybrid method combining population-based simulated annealing (SA) with an adaptive large neighborhood search (ALNS) algorithm to solve the cutting path problem. Recombination procedures were executed alternately using swap, reversion, insertion and removal-insertion through a fitness proportionate selection mechanism. In order to reduce the computing time and maintain the solution quality, the 35% proportion of population were executed in each iteration using the cultural algorithm selection method. The results revealed that the algorithm can solve several ranges of problem size with an acceptable percentage of error compared to the best known solution.

You might also be interested in these eBooks
Material and Manufacturing Technology X View Preview

Info:

Periodical:

Key Engineering Materials (Volume 833)

Pages:

29-34

DOI:

https://doi.org/10.4028/www.scientific.net/KEM.833.29

Citation:

Cite this paper

Online since:

March 2020

Authors:

Makbul Hajad*, Viboon Saetang, Chaiya Dumkum, Chorkaew Jaturanonda

Keywords:

ALNS, Cultural Algorithm, GTSP, Laser Cutting Path, Simulated Annealing

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2020 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

* - Corresponding Author

References

[1] F.Imeson and S.L. Smith, Multi-Robot Task Planning and Sequencing using the SAT-TSP Language, IEEE International Conference on Robotics and Automation (ICRA) (2015) 5397-5402.

DOI: 10.1109/icra.2015.7139953

Google Scholar

[2] R. Dewil, P. Vansteenwegen and D. Cattrysse, A review of cutting path algorithms for laser cutters, The International Journal of Advanced Manufacturing Technology 87 (2016) 1865–1884.

DOI: 10.1007/s00170-016-8609-1

Google Scholar

[3] G. Laporte, A. Asef-Vaziri and C. Sriskandarajah, Some Applications of the Generalized Travelling Salesman Problem, Journal of the Operational Research Society 47 (1996) 1461-1467.

DOI: 10.1057/jors.1996.190

Google Scholar

[4] J. Yang, X. Shi, M. Marchese and Y. Liang, An ant colony optimization method for generalized TSP problem, Progress in Natural Science 18 (2008) 1417-1422.

DOI: 10.1016/j.pnsc.2008.03.028

Google Scholar

[5] G. Laporte and H. Mercure, Generalized Traveling Salesman Problem Through n Sets of Nodes, the Asymmetrical case, Discrete Applied Mathematics 18 (1987) 185-197.

DOI: 10.1016/0166-218x(87)90020-5

Google Scholar

[6] M. Fischetti, J.J.S. Gonzales and P. Toth, A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem, Operations Research 45 (1997) 378-394.

DOI: 10.1287/opre.45.3.378

Google Scholar

[7] C.E. Noon and J.C. Bean, An Efficient Transformation Of The Generalized Traveling Salesman Problem, INFOR: Information Systems and Operational Research 31 (1993) 39-44.

DOI: 10.1080/03155986.1993.11732212

Google Scholar

[8] K. Helsgaun, An efective implementation of the Lin-Kernighan traveling salesman heuristic, European Journal of Operational Research 126 (2000) 106-130.

DOI: 10.1016/s0377-2217(99)00284-2

Google Scholar

[9] N. Garg, G. Konjevod, and R. Ravi, A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem, Journal of Algorithms 37 (2000) 66-84.

DOI: 10.1006/jagm.2000.1096

Google Scholar

[10] G. Gutin and D. Karapetyan, A Memetic Algorithm for the Generalized Traveling Salesman Problem, Natural Computer 9 (2010) 47-60.

DOI: 10.1007/s11047-009-9111-6

Google Scholar

[11] Information on http://www.cs.nott.ac.uk/~pszdk/gtsp.html.

Google Scholar

[12] D. Karapetyan and G. Gutin, Lin-Kernighan Heuritic Adaptation for the Generalized Traveling Salesman Problem, European Journal of Operational Research 208 (2011) 221-232.

DOI: 10.1016/j.ejor.2010.08.011

Google Scholar

[13] S. Lin and B.W. Kernighan, An Effective Heuritic Algorithm for the Traveling Salesman Problem, Operations Research 21 (1971) 498-516.

DOI: 10.1287/opre.21.2.498

Google Scholar

[14] K. Hesgaun, Solving the Equality Generalized Traveling Salesman Problem using the Lin-Kernighan-Helsgaun Algorithm, Mathematical Programming Computation 7 (2015) 269–287.

DOI: 10.1007/s12532-015-0080-8

Google Scholar

[15] M. Reihaneh and D. Karapetyan, An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem, Algorithmic Operations Research 7 (2012) 22-29.

Google Scholar

[16] S.L. Smith and F. Imeson, GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem, Computers and Operations Research 8 (2017) 1-19.

DOI: 10.1016/j.cor.2017.05.010

Google Scholar

[17] E.-G. Talbi, Metaheuritics: From Design to Implementation, John Wiley & Sons, inc, (2009).

Google Scholar

[18] G.-c. Han and S.-j. Na, Global Torch Path Generation for 2-D Laser Cutting Process using Simulated Annealing, Intelligent Automation & Soft Computing 4 (1998) 97-108.

DOI: 10.1080/10798587.1998.10750725

Google Scholar

© 2025 Trans Tech Publications Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies. For open access content, terms of the Creative Commons licensing CC-BY are applied.
Scientific.Net is a registered trademark of Trans Tech Publications Ltd.