Uzma, Agni Faizatul (2025) Evaluasi Penggunaan Master-Slave Genetic Algorithm Dengan Klasterisasi K-Means Dalam Menyelesaikan Open Arc Routing Problem: Studi Kasus Mesin CNC Batik Tulis. Other thesis, Institut Teknologi Sepuluh Nopember.
![[thumbnail of 5010211004-Undergraduate_Thesis.pdf]](http://repository.its.ac.id/style/images/fileicons/text.png) |
Text
5010211004-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (6MB) | Request a copy |
Abstract
Open Arc Routing Problem (OARP) merupakan permasalahan optimasi kombinatorial berjenis NP-hard yang memiliki tingkat kompleksitas cukup tinggi dalam penyelesaiannya. Sehingga dibutuhkan pendekatan secara metaheuristik, salah satunya dengan menggunakan Master-Slave Genetic Algorithm (MS-GA) untuk menemukan solusi yang efisien. Pada studi kasus mesin CNC batik tulis, terdapat dua penelitian yang menggunakan MS-GA untuk mengoptimalkan rute pembatikan dalam bentuk OARP. Namun, algoritma yang digunakan masih memiliki beberapa kelemahan berupa waktu komputasi yang cukup lama, tidak mempertimbangkan linkage, dan belum menerapkan sensitivity analysis. Oleh karena itu, penelitian ini mengusulkan pengembangan algoritma optimasi yang mampu meningkatkan performa dalam menyelesaikan OARP untuk memperoleh urutan rute yang efisien. Penelitian menggunakan data sekunder berupa hasil digitalisasi motif Batik Megamendung yang terdiri dari 466 segmen. Metode yang digunakan mencakup klasterisasi K-Means, Single-Linkage, Master-Slave Genetic Algorithm, serta Design of Experiment melalui pendekatan Sensitivity Analysis dan Full Factorial Design. Berdasarkan hasil pengujian, algoritma usulan mampu memberikan hasil yang lebih optimal dibandingkan penelitian sebelumnya dengan waktu keseluruhan proses sebesar 28.36 menit dan total jarak perpindahan alat sebesar 24,529.08 mm yang diperoleh dari rata-rata hasil replikasi. Nilai tersebut sudah menunjukkan hasil yang konsisten berdasarkan perhitungan confidence interval. Dengan demikian, penelitian ini terbukti mampu meningkatkan performa algoritma dalam menyelesaikan OARP.
======================================================================================================================================
The Open Arc Routing Problem (OARP) is a combinatorial optimization problem classified as NP-hard that has a high level of complexity in its solution process. To address this issue, a metaheuristic approach is required, one of which is the Master-Slave Genetic Algorithm (MS-GA) to find efficient solutions. In the case study of a CNC hand-drawn batik machine, two previous studies have applied MS-GA to optimize the batik routing process in the form of OARP. However, the algorithms used still have several limitations, including long computational time, the lack of consideration for linkage, and has not implemented sensitivity analysis. Therefore, this study proposes the development of an optimization algorithm to improve performance in solving OARP to generate an efficient routing sequence. The research uses secondary data from the digitization of a Megamendung Batik motif consisting of 466 segments. The proposed method integrates K-Means clustering, Single-Linkage, Master-Slave Genetic Algorithm, and Design of Experiment through Sensitivity Analysis and a Full Factorial Design approach. Based on the experimental results, the proposed algorithm was able to provide more optimal results than the previous studies with an overall process time of 28.36 minutes and a total tool displacement distance of 24,529.08 mm, derived from the average of the replication results. These results indicate a consistent outcome based on the calculation of the confidence interval. Thus, the proposed approach has proven effective in enhancing the performance of algorithms for solving OARP.
Actions (login required)
 |
View Item |