Pengembangan Algoritma Hybrid Metaheuristic Untuk Menyelesaikan Permasalahan Combinatorial Optimization

Adhi, Antono (2022) Pengembangan Algoritma Hybrid Metaheuristic Untuk Menyelesaikan Permasalahan Combinatorial Optimization. Doctoral thesis, Institut Teknologi Sepuluh Nopember.

Text 02411560010001_Disertasi.pdf Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Permasalahan combinatorial optimization adalah permasalahan diskrit yang paling banyak timbul dalam masyarakat maupun dunia industri seperti penjadwalan produksi, pencarian rute terbaik dalam manajemen logistic, ataupun bidang lainnya. Permasalahan ini adalah mencari kombinasi yang terbaik dari elemen-elemen yang memberikan nilai optimum atau mendekati optimum sehingga biaya, waktu, jarak, atau kombinasi dari ketiganya dapat dicapai sekecil mungkin. Permasalahan akan menjadi sangat kompleks saat tidak dapat diselesaikan dengan persamaan matematika secara langsung dan jumlah elemen yang diperhitungkan berjumlah banyak. Akibatnya penyelesaian combinatorial problem akan membutuhkan waktu yang lama. Metode yang biasa digunakan untuk menyelesaikan permasalahan combinatorial optimization adalah dengan metode metaheuristik. Metode ini memang tidak selalu menjanjikan hasil yang optimum global tetapi waktu yang digunakan untuk mencari penyelesaiannya masih dapat diterima. Banyak jenis metode metaheuristik yang telah dikembangkan untuk menyelesaikan permasalahan combinatorial optimization. Penelitian terbaru adalah melakukan perbaikan-perbaikan pada metode metaheuristik dengan mengombinasikannya dengan metode metaheuristik lain atau metode jenis lainnya untuk memperoleh hasil yang lebih efektif. Aktivitas pengombinasian ini disebut hibrid metaheuristik. Penelitian dalam disertasi ini ditujukan untuk mengembangkan hibrid metaheuristik untuk memperoleh hasil yang lebih efektif daripada metode aslinya. Metode hibrid dikembangkan dari metode Nahwaz-Enscore-Ham (NEH), 3-Opt, dan Particle Swarm Optimization (PSO) (NEH3PSO). Jenis permasalahan yang diteliti dan diujicoba dari permasalahan combinatorial optimization di disertasi ini adalah Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), dan Inventory Routing Problem (IRP). Pada perbandingan dengan data TSP library, NEH3PSO memberikan deviasi sebesar 0.3% dibandingkan dengan hasil terbaik. Dari delapan data library, empat data dapat diselesaikan dengan optimum (50%). Pada penyelesaian VRP, NEH3PSO memberikan hasil 0.99% lebih baik daripada metode Genetic Algorithm. Pada penyelesaian IRP, NEH3PSO memberikan hasil 0.75% lebih baik daripada metode Hybid Genetic Algoritma yang dihibridisasi sama dengan NEH3PSO.
=========================================================================================================================
Combinatorial optimization problems are discrete problems that most often appear in society and industry world, such as production scheduling, finding the best route in logistics management, or other problems. This problem is to find the best combination of elements that give the optimum value or close to the optimum so that the cost, time, distance, or a combination of the three can be achieved as small as possible. The problems will become very complex when they cannot be solved by mathematical equations directly and the number of elements that are calculated is big. As a result, solving the combinatorial problem will take a long time. The method commonly used to solve combinatorial optimization problems is the metaheuristic method. This method does not always promise global optimum results but the time taken to find a solution is still acceptable. Many types of metaheuristic methods have been developed to solve combinatorial optimization problems. The latest research is to make improvements to the metaheuristic method by combining it with other metaheuristic methods or other types of methods to obtain better effective result. This combining activity is called hybrid metaheuristic. The research in this dissertation is aimed at developing metaheuristic hybrids to obtain more effective results than the original method. The hybrid method was developed from the Nahwaz-Enscore-Ham (NEH), 3-Opt, and Particle Swarm Optimization (PSO) (NEH3PSO) methods. The types of problems studied and tested from combinatorial optimization problems in this dissertation are the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), and Inventory Routing Problem (IRP). At the comparison of the TSP library data, NEH3PSO gives a deviation of 0.3% compared to the best results. It gives optimum solution of four out of eight library data. At the completion of the VRP, NEH3PSO gave 0.99% better results than the Genetic Algorithm method. At the completion of the IRP, NEH3PSO gave 0.75% better results than the Hybid Genetic Algorithm method which was hybridized the same with NEH3PSO.

Item Type:	Thesis (Doctoral)
Uncontrolled Keywords:	hybrid metaheuristic, combinatorial optimization, Traveling Salesman Problem, Vehicle Routing Problem, Inventory Routing Problem
Subjects:	H Social Sciences > HD Industries. Land use. Labor > HD55 Inventory control
Divisions:	Faculty of Industrial Technology and Systems Engineering (INDSYS) > Industrial Engineering > 26001-(S3) PhD Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	21 Jan 2026 03:16
Last Modified:	21 Jan 2026 03:16
URI:	http://repository.its.ac.id/id/eprint/129924

Actions (login required)

View Item