TSP Ant Colony [PDF]

Citation preview

PENENTUAN RUTE TRAVELING SALESMAN PROBLEM MENGGUNAKAN ALGORITME ANT COLONY OPTIMIZATION



NURUL FATHIAH



DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2019



PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penentuan Rute Traveling Salesman Problem Menggunakan Algoritme Ant Colony Optimization adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, November 2019 Nurul Fathiah NIM G54150037



ABSTRAK NURUL FATHIAH. Penentuan Rute Traveling Salesman Problem Menggunakan Algoritme Ant Colony Optimization. Dibimbing oleh PRAPTO TRI SUPRIYO dan BIB PARUHUM SILALAHI. Traveling Salesman Problem (TSP) merupakan salah satu permasalahan yang sering muncul dalam sistem distribusi. Seiring berjalannya waktu, pemecahan masalah TSP berkembang dengan begitu cepat. Para ilmuwan berusaha mencari cara agar dapat menemukan hasil yang semakin baik dengan waktu eksekusi yang semakin cepat. Ada beberapa metode yang dikembangkan untuk permasalahan ini. Pada karya ilmiah ini, digunakan metode eksak Integer Linear Programming (ILP) dan metode meta-heuristic Ant Colony Optimization (ACO) untuk menyelesaikan TSP. Hasil yang diperoleh menunjukkan bahwa waktu eksekusi metode ACO jauh lebih cepat dibandingkan dengan metode eksak. Akan tetapi, ACO masih menghasilkan selisih jarak yang relatif besar dibandingkan ILP. Kata kunci: ant colony optimization, integer linear programming, metode meta-heuristic, traveling salesman problem



ABSTRACT NURUL FATHIAH. Route Determination of Traveling Salesman Problem Using Ant Colony Optimization Algorithm. Supervised by PRAPTO TRI SUPRIYO and BIB PARUHUM SILALAHI. Traveling salesman problem (TSP) is one of the problems that often appear in distribution system. As time goes by, TSP problem solving develops quickly. Scientists are trying to find ways to get better results with faster execution times. There are several methods developed for this problem. In this manuscript, integer linear programming (ILP) as an exact method and ant colony optimization (ACO) as a meta-heuristic method will be used to solve TSP. The results obtained show that the ACO execution time is faster than the exact method. However, ACO still produces a relatively large distance difference compared to ILP. Keywords: ant colony optimization, integer linear programming, meta-heuristic method, traveling salesman problem



PENENTUAN RUTE TRAVELING SALESMAN PROBLEM MENGGUNAKAN ALGORITME ANT COLONY OPTIMIZATION



NURUL FATHIAH



Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika



DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR NURUL2019 FATHIAH



Judul Skripsi: Penentuan Rute Traveling Salesman Problem Menggunakan Algoritrne Ant Colony Optimization. Nama



: Nurul Fathiah



NIM



: G54150037



Disetujui oleh



Drs Prapto Tri Supriyo, MKorn



M.Kom



Pernbirnbing I



--



Tanggal Lulus:



-



0 5 NOV 2019a



PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilaksanakan sejak bulan Februari 2019 ini ialah riset operasi, dengan judul Penentuan Rute Traveling Salesman Problem Menggunakan Algoritme Ant Colony Optimization. Proses penyusunan karya ilmiah ini tidak lepas dari bantuan banyak pihak. Untuk itu ungkapan terima kasih sebesar-besarnya penulis sampaikan kepada: 1. kedua orang tua, abi Syukron Azis dan umi Ermayanti serta adik penulis, A Faqih M untuk seluruh cinta, doa, ridho, dan kesabaran dari umi, abi, dan adik sejak pertama kali penulis menuntut ilmu di IPB, 2. Bapak Drs Prapto Tri Supriyo, MKom selaku dosen Pembimbing I, Bapak Dr Ir Bib Paruhum Silalahi, Mkom selaku dosen Pembimbing II, serta Ibu Hidayatul Mayyani, SSi, MSi selaku dosen penguji yang telah meluangkan waktu, memberikan arahan, motivasi dan ilmu yang bermanfaat kepada penulis selama proses pengerjaan karya ilmiah ini, 3. Ihda, Novfrinka, dan Monica, selaku sahabat yang sangat setia menemani penulis dan bersedia menjadi wadah untuk segala keluh kesah penulis selama ini, 4. PADEPOKAN (Nindia, Ria, dan Meta) yang telah menjadi sahabat serta guru selama penulis menimba ilmu di Departemen Matematika, 5. seluruh pimpinan Gumatika Periode 2017/2018, kalian memberi warna dan pengalaman yang luar biasa untuk penulis, 6. Alifah Fidela selaku teman hidup penulis selama belajar di kampus IPB tercinta, 7. Gumakusi yang selalu setia menjadi tempat penulis untuk meluapkan kejenuhan maupun kebahagiaan selama menjalani perkuliahan sehingga penulis dapat bertahan hingga saat ini, 8. teman-teman Angkatan 52 atas kebersamaannya, kakak-kakak Angkatan 50 dan 51 serta teman-teman Angkatan 53 atas pengalaman dan dukungan yang diberikan, 9. kak Alfien dan Daffa (Ilkom) yang banyak membantu selama proses pengerjaan tugas akhir, 10. pihak-pihak lainnya yang telah banyak membantu penulis yang tidak dapat disebutkan satu per satu. Semoga karya ilmiah ini bermanfaat.



Bogor, November 2019 Nurul Fathiah



DAFTAR ISI DAFTAR TABEL



vi



DAFTAR GAMBAR



vi



DAFTAR LAMPIRAN



vi



PENDAHULUAN



1



Latar Belakang



1



Tujuan Penelitian



2



Manfaat Penelitian



2



TINJAUAN PUSTAKA



2



Optimisasi



2



Penyelesaian Masalah Optimisasi



2



Traveling Salesman Problem (TSP)



3



Algoritme Ant Colony Optimization (ACO)



4



Alur dan Langkah Algoritme Ant Colony Optimization (ACO)



5



HASIL DAN PEMBAHASAN



7



Deskripsi Masalah



7



Penyelesaian Menggunakan Integer Linear Programming (ILP)



9



Penyelesaian Menggunakan Algoritme Ant Colony Optimization (ACO)



11



Perbandingan Hasil



15



SIMPULAN DAN SARAN



15



Simpulan



15



Saran



15



DAFTAR PUSTAKA



16



LAMPIRAN



17



RIWAYAT HIDUP



45



DAFTAR TABEL 1 Data kordinat 𝑥 dan 𝑦 masing-masing kasus 2 Perbandingan hasil pada kasus I menggunakan beberapa parameter dan iterasi yang berbeda 3 Perbandingan hasil pada kasus II menggunakan beberapa parameter dan iterasi yang berbeda 4 Perbandingan hasil pada kasus III menggunakan beberapa parameter dan iterasi yang berbeda 5 Perbandingan waktu eksekusi 6 Perbandingan total jarak



8 12 13 14 15 15



DAFTAR GAMBAR 1 2 3 4 5 6 7



Algoritme Ant Colony Optimization Hasil optimum global kasus I Hasil optimum global kasus II Hasil optimum global kasus III Rute pendekatan yang dihasilkan pada kasus I Rute pendekatan yang dihasilkan pada kasus II Rute pendekatan yang dihasilkan pada kasus III



5 10 10 11 12 13 14



DAFTAR LAMPIRAN 1 2 3 4 5



Sintaks model TSP pada software LINGO 11.0 Sintaks ACO menggunakan software MATLAB Matriks jarak pada kasus I Matriks jarak pada kasus II Matriks jarak pada kasus III



17 18 23 29 36



PENDAHULUAN Latar Belakang Salah satu permasalahan dalam sistem distribusi yang sering kali kita temui adalah Traveling Salesman Problem (TSP). TSP merupakan permasalahan dalam mencari jarak minimum untuk mengunjungi seluruh node yang telah ditentukan, dengan aturan setiap node haruslah dikunjungi tepat satu kali dan kembali lagi ke node awal. Artinya, perjalanan dimulai dari suatu node (starting node) kemudian dilanjutkan ke node selanjutnya hingga seluruh node dikunjungi dan kembali lagi ke node awal (finishing node). Salah satu sifat TSP ialah non-deterministic polynomial-time complete (NPC), artinya tidak ada penyelesaian yang paling optimal selain harus mencoba seluruh kemungkinan penyelesaian yang ada (Heizer dan Render 2010). Pengaplikasian TSP dalam dunia nyata sering kali dimanfaatkan untuk kasus pendistribusian barang maupun jasa. Seperti misalnya pada perusahaan pengiriman barang, pendistribusian produk ke seluruh agen, bahkan dalam rute perjalanan pariwisata yang biasa digunakan oleh agen perjalanan. Masalah yang sering dihadapi terkait dengan distribusi antara lain menentukan rute perjalanan yang mampu meminimumkan jarak tempuh, waktu tempuh, atau biaya oprasional (Heizer dan Render 2010). Salah satu metode yang dapat digunakan untuk menyelesaikan TSP adalah metode eksak. Metode eksak merupakan penyelesaian dengan cara perhitungan matematis eksak. Salah satu metode eksak yang dapat digunakan adalah Integer Linear Programming (ILP). ILP adalah masalah pengoptimuman dimana di dalamnya terdapat fungsi objektif linear, fungsi kendala linear dan variabel berupa bilangan bulat. Selain itu juga terdapat kendala-kendala yang dapat diubah sesuai kebutuhan, sehingga penggunaan ILP dianggap lebih fleksibel. ILP merupakan salah satu metode yang akan digunakan dalam karya ilmiah ini. Selain metode eksak, terdapat metode heuristic maupun meta-heuristic yang dapat digunakan untuk menyelesaikan TSP. Pada dasarnya, metode heuristic maupun meta-heuristic merupakan metode pendekatan dalam mencari optimasi. Perbedaannya terletak pada jenis permasalahan. Meta-heuristic merupakan perluasan dari heuristic, dengan kata lain, meta-heuristic dapat menyelesaikan permasalahan yang lebih rumit dibandingkan dengan heuristic. Akan tetapi, kemampuan mengadaptasi metode ini berpengaruh pada kualitas penyelesaian yang dihasilkan. Salah satu metode meta-heuristic yang dapat digunakan untuk menyelesaikan TSP adalah algoritme Ant Colony Optimization (ACO). ACO diadopsi dari perilaku koloni semut yang dikenal sebagai sistem semut (ant system). Semut mampu mencari makan dengan cara yang efektif, yaitu dengan menemukan jarak terpendek antara sumber makanan dengan sarangnya tanpa menggunakan indera penglihatan. ACO banyak digunakan sebagai penyelesaian dalam berbagai masalah optimisasi, salah satunya adalah TSP. Algoritme ini tersusun atas sejumlah m semut yang berkomunikasi secara tidak langsung melalui feromon (Dorigo et al. 2006).



2 Tujuan Penelitian Tujuan dari karya ilmiah ini yaitu : 1. menentukan rute Traveling Salesman Problem (TSP) dengan menggunakan algoritme ACO, 2. melihat kinerja ACO dengan membandingkan waktu eksekusi dan total jarak yang diperoleh antara metode eksak Integer Linear Programming (ILP) dengan metode pendekatan (meta-heuristic) ACO dalam menyelesaikan TSP.



Manfaat Penelitian Penulisan karya ilmiah ini bermanfaat untuk penentuan rute efisien dari suatu tempat menuju tempat-tempat lain yang telah ditentukan untuk berbagai keperluan. Seperti misalnya pada perusahaan pengiriman barang, pendistribusian produk ke seluruh agen, bahkan dalam rute perjalanan pariwisata yang biasa digunakan oleh agen perjalanan.



TINJAUAN PUSTAKA Optimisasi Optimisasi merupakan suatu upaya sistematis untuk memilih elemen terbaik dari suatu kumpulan elemen yang ada. Dalam konteks matematika, optimisasi ini bisa dinyatakan sebagai suatu usaha sistematis untuk mencari nilai minimum atau maksimum dari suatu fungsi. Dengan kata lain, optimisasi merupakan proses mencari nilai terbaik berdasarkan fungsi tujuan dengan daerah asal yang telah didefinisikan. Optimisasi digunakan hampir dalam semua bidang ilmu antara lain bidang teknik, sains, ilmu sosial, ekonomi, dan bisnis. Banyak permasalahan dalam bidang teknik, sains, dan ekonomi yang dapat dinyatakan sebagai permasalahan optimisasi seperti meminimalkan biaya, waktu dan risiko atau memaksimalkan keuntungan dan kualitas. (Mutakhiroh et al. 2007)



Penyelesaian Masalah Optimisasi Salah satu permasalahan optimisasi adalah pencarian rute terpendek yang secara umum dapat dilakukan dengan menggunakan dua metode, yaitu metode eksak dan metode heuristic maupun meta-heuristic. Metode konvensional dihitung dengan perhitungan matematis biasa, sedangkan metode heuristic dihitung dengan menggunakan sistem pendekatan.



3 1. Metode Eksak Metode eksak adalah metode yang menggunakan perhitungan matematika eksak. Ada beberapa metode eksak yang biasa digunakan untuk melakukan pencarian rute terpendek, diantaranya: algoritme Dijkstra, algoritme FloydWarshall, dan algoritme Bellman-Ford. 2. Metode Heuristic Metode heuristic maupun meta-heuristic adalah metode yang menggunakan sistem pendekatan dalam melakukan pencarian dalam optimisasi. Perbedaan utama antara metode heuristic dan meta-heuristic ialah metode heuristic bersifat problem dependent yang artinya bergantung pada permasalahan, jadi metode ini hanya dapat digunakan untuk jenis permasalahan tertentu sedangkan metode meta-heuristic bersifat problem independent yang artinya tidak bergantung pada jenis permasalahan atau dapat digunakan untuk berbagai jenis permasalahan. Contoh dari metode meta-heuristic adalah algoritme genetik (GA), particle swam optimization (PSO), dan ACO. (Mutakhiroh et al. 2007)



Traveling Salesman Problem (TSP) TSP adalah masalah penentuan rute ketika seseorang akan mengunjungi seluruh tempat yang telah ditentukan. Diawali dari tempat pertama dan kemudian mengunjungi setiap tempat yang telah ditentukan tepat satu kali. Setelah itu kembali ke tempat pertama, sehingga total jarak perjalanannya minimum (Nemhauser dan Wolsey 1999). TSP dapat diformulasikan sebagai berikut: Misalkan: 𝑛 : banyaknya node yang akan dikunjungi, 𝑐𝑖𝑗 : jarak node 𝑖 ke node 𝑗, 𝑢𝑖 : variabel tambahan saat mengunjungi node 𝑖. Variabel keputusan: 𝑥𝑖𝑗 = {



1, Jika ada perjalanan dari node 𝑖 ke node 𝑗 0, selainnya



Fungsi objektif TSP ialah meminimumkan total jarak tempuh kendaraan, yaitu min 𝑍 = ∑𝑛𝑖=1 ∑𝑛j=1 𝑐𝑖𝑗 𝑥𝑖𝑗 . Kendala-kendala: 1. Setiap node harus dikunjungi tepat satu kali ∑𝑛𝑖=1 𝑥𝑖𝑗 = 1,



∀𝑗 = 1,2, … , 𝑛



4 ∑𝑛𝑗=1 𝑥𝑖𝑗 = 1,



∀𝑖 = 1,2, … , 𝑛



2. Tidak ada subtur yang terbentuk pada rute perjalanan, sehingga hanya ada satu tur rute perjalanan berupa cycle 𝑢𝑖 − 𝑢𝑗 + 𝑛𝑥𝑖𝑗 ≤ 𝑛 − 1, 𝑖 ≠ 𝑗, ∀𝑖 = 2, 3, … , 𝑛; ∀𝑗 = 2, 3, … , 𝑛; 𝑢𝑗 ≥ 0. 3. Kendala biner 𝑥𝑖𝑗 ∈ {0,1}, ∀𝑖 = 1,2, … , 𝑛; ∀𝑗 = 1,2, … , 𝑛 (Winston 2004)



Algoritme Ant Colony Optimization (ACO) ACO merupakan salah satu metode meta-heuristic yang digunakan untuk menyelesaikan masalah optimisasi kombinatorial yang cukup sulit. Algortime ACO direpresentasikan dari perilaku semut dalam dunia nyata untuk membangun jalur terpendek antara sumber makanan dan sarangnya. Setiap semut memulai turnya melalui sebuah titik yang dipilih secara acak (setiap semut memiliki titik awal yang berbeda). Secara berulang kali, satu persatu titik yang ada dikunjungi oleh semut dengan tujuan untuk menghasilkan sebuah tur. Pemilihan titik-titik yang akan dilaluinya didasarkan pada suatu fungsi probabilitas, dengan nama aturan transisi status (state transition rule), dengan mempertimbangkan visibility (invers dari jarak) titik tersebut, dan jumlah feromon yang terdapat pada ruas yang menghubungkan titik tersebut. Semut lebih suka untuk bergerak menuju ruas yang memiliki tingkat feromon yang tinggi (Dorigo dan Gambardella 1997). Setiap semut memiliki sebuah memori (tabulist), yang berisi semua titik yang telah dikunjunginya pada setiap tur. Tabulist ini mencegah semut untuk mengunjungi titik-titik yang sebelumnya telah dikunjungi selama tur tersebut berlangsung, sehingga menyebabkan solusinya mendekati optimal. Setelah semua semut menyelesaikan turnya dan tabulist menjadi penuh, sebuah aturan pembaruan feromon global (global pheromone updating rule) diterapkan pada setiap semut. Penguapan feromon pada semua ruas dilakukan, kemudian setiap semut menghitung panjang tur yang telah mereka lakukan lalu meninggalkan sejumlah feromon pada edge-edge yang merupakan bagian dari tur yang sebanding dengan kualitas dari solusi yang dihasilkan. Semakin pendek sebuah tur yang dihasilkan oleh setiap semut, jumlah feromon yang ditinggalkan pada edge-edge yang dilaluinya pun semakin besar. Dengan kata lain, edge-edge yang merupakan bagian dari tur-tur terpendek adalah edge-edge yang menerima jumlah feromon yang lebih besar. Hal ini menyebabkan edge-edge yang diberi feromon lebih banyak akan lebih diminati pada tur-tur selanjutnya, dan sebaliknya edge-edge yang memiliki sedikit feromon menjadi kurang diminati. Rute terpendek yang ditemukan oleh semut disimpan dan semua tabulist yang ada dikosongkan kembali. Peranan utama dari penguapan feromon adalah untuk mencegah stagnasi, yaitu situasi ketika semua semut berakhir dengan melakukan tur yang sama. Proses di atas kemudian diulangi sampai tur-tur yang dilakukan mencapai jumlah maksimum (Liu et al. 2009).



5 Alur dan Langkah Algoritme Ant Colony Optimization (ACO) Berikut adalah alur dan langkah algoritme ACO secara sederhana



Inisialisasi parameter ACO



Membangun rute dengan menggunakan fungsi probabilitas



Tidak Apakah setiap semut sudah mengunjungi semua node?



Ya Menghitung panjang perjalanan setiap semut



Penguapan feromon (update pheromone)



Tidak



Apakah kriteria pemberhentian sudah terpenuhi?



Ya



Gambar 1 Algoritme Ant Colony Optimization



Tampilkan hasil



6 1. Data awal yang disajikan hanya berupa titik koordinat 𝑥 dan 𝑦, sehingga perlu dihitung jarak antar node dengan menggunakan rumus Euclidian 𝑑𝑖𝑗 = √(𝑥𝑖 − 𝑥𝑗 )2 + (𝑦𝑖 − 𝑦𝑗 )2 dengan: 𝑑𝑖𝑗 : jarak node 𝑖 ke node 𝑗 𝑥𝑖 : titik koordinat 𝑥 node 𝑖 𝑥𝑗 : titik koordinat 𝑥 node 𝑗 𝑦𝑖 : titik koordinat 𝑦 node 𝑖 𝑦𝑗 : titik koordinat 𝑦 node 𝑗 2. Menentukan node selanjutnya yang akan dilalui semut dengan menghitung probabilitas menggunakan rumus: 𝛼



𝑃𝑖𝑗𝑘 (𝑡)



=



𝛽



[𝜏𝑖𝑗 (𝑡)] ∙ [𝜂𝑖𝑗 (𝑡)] 𝛼



∑𝑗 𝜖 𝑁𝑘[𝜏𝑖𝑗 (𝑡)] ∙ [𝜂𝑖𝑗 (𝑡)]



𝛽



, jika 𝑗 𝜖 𝑁𝑖𝑘



𝑖



dengan: 𝑃𝑖𝑗𝑘 (𝑡) 𝜏𝑖𝑗 (𝑡) 𝜂𝑖𝑗 (𝑡)



: probabilitas semut ke- 𝑘 yang berjalan dari node 𝑖 ke node 𝑗 pada waktu 𝑡, : banyaknya jejak semut (feromon) dari node 𝑖 ke node 𝑗 pada waktu 𝑡, : invers jarak antara node 𝑖 dan node 𝑗 pada waktu 𝑡,



𝑁𝑖𝑘



: himpunan titik yang akan dikunjungi oleh semut 𝑘 yang sedang berada pada titik 𝑖, 𝛼 : parameter pengendali jejak semut (feromon), 𝛽 : parameter pengendali jarak, dan dalam membentuk rute, kriteria pemilihan node selanjutnya menggunakan algoritme Roulette Wheel Selection, dengan langkah-langkah sebagai berikut: a. menentukan satu nilai random antara 0 sampai 1, b. menghitung nilai peluang kumulatif 𝑃𝑖𝑗𝑘 (𝑡), c. membandingkan nilai random pada langkah a dengan masing-masing nilai peluang kumulatif 𝑃𝑖𝑗𝑘 (𝑡) pada langkah b,



3. 4. 5. 6.



d. jika didapatkan nilai peluang kumulatif 𝑃𝑖𝑗𝑘 (𝑡) yang lebih besar dari nilai random, maka akan dipilih sebagai node selanjutnya. Ulangi langkah 2 untuk setiap semut hingga semua node terpilih dan membentuk suatu rute. Menghitung total jarak dari tiap node yang dilalui oleh masing-masing semut. Memilih rute terbaik dari semua rute yang dihasilkan, yaitu rute dengan total jarak paling minimum yang didapat pada langkah 4. Melakukan update pheromone dengan rumus berikut:



7 𝜏𝑖𝑗 (𝑡) = (1 − 𝜌)𝜏𝑖𝑗 (𝑡) + Δ𝜏𝑖𝑗 (𝑡) dengan 1 , Δ𝜏𝑖𝑗 (𝑡) = {𝐿𝑘 0, dengan:



jika semut ke − 𝑘 berjalan dari node 𝑖 ke node 𝑗 selainnya



𝜏𝑖𝑗 (𝑡)



: banyaknya jejak semut (feromon) dari node 𝑖 ke node 𝑗 pada waktu 𝑡, Δ𝜏𝑖𝑗 (𝑡) : perubahan nilai feromon pada node (𝑖, 𝑗) yang dilakukan oleh semut ke- 𝑘, 𝐿𝑘 : panjang perjalanan semut ke- 𝑘, 𝜌 : parameter penguapan (evaporasi) feromon global dengan 0 < 𝜌 ≤ 1, update pheromone dilakukan dengan tujuan memperbarui jumlah feromon yang ditinggalkan semut sebagai dampak dari penguapan. Jumlah feromon yang telah diperbarui akan digunakan sebagai informasi untuk semut pada iterasi selanjutnya. 7. Algoritme ini diberhentikan jika kriteria pemberhentian sudah tercapai, yaitu ketika jumlah iterasi sudah terpenuhi. 8. Kembali ke langkah 2 jika kriteria pemberhentian belum tercapai. (Dorigo dan Socha 2007).



HASIL DAN PEMBAHASAN Deskripsi Masalah Pada karya ilmiah ini, akan dilakukan penyelesaian terhadap tiga kasus TSP menggunakan metode ILP dan metode ACO. Ketiga kasus tersebut terdiri dari kasus I 30 node, kasus II 35 node, dan kasus III 38 node. Selanjutnya, hasil dari kedua metode akan dibandingkan khususnya dalam aspek waktu eksekusi dan total jarak perjalanan. Kedua metode dieksekusi menggunakan bantuan laptop dengan spesifikasi ASUS A 455LD i5 RAM 8GB. Data yang digunakan adalah data koordinat 𝑥 dan 𝑦 yang menunjukan letak node dalam koordinat kartesius dan data tersebut merupakan data hipotetik yang diambil dari fungsi random, disajikan pada tabel dibawah ini:



8 Tabel 1 Data kordinat 𝑥 dan 𝑦 masing-masing kasus 𝑥 81.91



Kasus I 𝑦 37.47



𝑥 81.91



Kasus II 𝑦 37.47



Kasus III 𝑥 𝑦 81.91 37.47



83.16



49.92



83.16



49.92



83.16



49.92



84.76



40.37



84.76



40.37



84.76



40.37



75.27



63.61



75.27



63.61



75.27



63.61



38.10



28.80



38.10



28.80



38.10



28.80



23.28



95.00



23.28



95.00



23.28



95.00



77.49



15.56



77.49



15.56



77.49



15.56



39.22



22.32



39.22



22.32



39.22



22.32



62.88



32.60



62.88



32.60



62.88



32.60



36.63



65.29



36.63



65.29



36.63



65.29



17.02



41.47



17.02



41.47



17.02



41.47



89.50



30.82



89.50



30.82



89.50



30.82



17.02



52.23



17.02



52.23



17.02



52.23



13.25



100.12



13.25



100.12



13.25



100.12



73.20



52.75



73.20



52.75



73.20



52.75



34.08



89.16



34.08



89.16



34.08



89.16



55.29



90.36



55.29



90.36



55.29



90.36



41.42



25.66



41.42



25.66



41.42



25.66



53.31



90.58



53.31



90.58



53.31



90.58



42.66



31.08



42.66



31.08



42.66



31.08



54.49



56.85



54.49



56.85



54.49



56.85



99.85



60.28



99.85



60.28



99.85



60.28



63.39



100.56



63.39



100.56



63.39



100.56



9



𝑥 21.86



Kasus I 𝑦 77.04



𝑥 21.86



Kasus II 𝑦 77.04



Kasus III 𝑥 𝑦 21.86 77.04



35.09



36.91



35.09



36.91



35.09



36.91



56.86



61.57



56.86



61.57



56.86



61.57



83.89



52.24



83.89



52.24



83.89



52.24



53.04



56.22



53.04



56.22



53.04



56.22



34.06



37.48



34.06



37.48



34.06



37.48



66.57



25.84



66.57



25.84



66.57



25.84



34.56



20.48



34.56



20.48



63.63



63.48



63.63



63.48



56.74



22.22



56.74



22.22



15.90



62.84



15.90



62.84



88.86



79.06



88.86



79.06



73.48



82.00



85.58



55.79



90.92



54.49



Dari data di atas, dicari jarak antar node dengan menggunakan rumus Euclidian sehingga menghasilkan matriks jarak seperti pada Lampiran 3 untuk kasus I, Lampiran 4 untuk kasus II, dan Lampiran 5 untuk kasus III. Penyelesaian Menggunakan Integer Linear Programming (ILP) Penyelesaian menggunakan ILP dilakukan dengan bantuan software LINGO 11.0. Pada karya ilmiah ini akan digunakan sintaks seperti pada Lampiran 1 sehingga diperoleh hasil untuk masing-masing kasus. Kasus I Hasil yang diperoleh adalah sebagai berikut:



10



Gambar 2 Hasil optimum global kasus I Gambar 2 memperlihatkan hasil eksekusi menggunakan ILP untuk kasus 30 node dibutuhkan waktu eksekusi 1 menit 34 detik dengan jumlah iterasi 436.649 dan diperoleh hasil total jarak perjalanan minimum sebesar 388.371 km. Kasus II Hasil yang diperoleh adalah sebagai berikut:



Gambar 3 Hasil optimum global kasus II



11 Gambar 3 memperlihatkan hasil eksekusi menggunakan ILP untuk kasus 35 node dibutuhkan waktu eksekusi 11 menit 04 detik dengan jumlah iterasi 3.351.017 dan diperoleh hasil total jarak perjalanan minimum sebesar 427.584 km. Kasus III Hasil yang diperoleh adalah sebagai berikut:



Gambar 4 Hasil optimum global kasus III Gambar 4 memperlihatkan hasil eksekusi menggunakan ILP untuk kasus 38 node dibutuhkan waktu eksekusi 6 jam 38 menit 14 detik dengan jumlah iterasi 142.214.825 dan diperoleh hasil total jarak perjalanan minimum sebesar 430.251 km.



Penyelesaian Menggunakan Algoritme Ant Colony Optimization (ACO) Pada karya ilmiah ini, digunakan software MATLAB R2015a untuk mencari penyelesaian TSP menggunakan algoritme ACO. Setiap kasus menggunakan nilai parameter 𝛼 , 𝛽, dan 𝑚 (jumlah semut) yang berbeda dengan nilai 𝛼 berada pada selang 0 < 𝛼 ≤ 1 serta nilai 𝛽 > 0 dan nilai 𝑚 > 0 (Dorigo dan Socha 2007). Disajikan nilai 𝛼 , 𝛽 , dan 𝑚 yang dapat menghasilkan total jarak pendekatan terkecil. Akan digunakan sintaks seperti pada Lampiran 2 sehingga diperoleh hasil untuk masing-masing kasus.



12



Kasus I Pada kasus I akan dilakukan percobaan menggunakan parameter dengan nilai sebagai berikut: Tabel 2 Perbandingan hasil pada kasus I menggunakan beberapa parameter dan iterasi yang berbeda Jumlah Iterasi



𝛼



𝛽



𝑚



Total Jarak (dalam km)



300 350 400 450 500 500



1 1 1 1 0.9 1



5 5 5 5 5 5



50 50 50 50 50 50



425.1656 417.1519 407.1231 399.8285 420.6379 392.8014



Setelah melakukan beberapa kali percobaan, diperoleh total jarak pendekatan terkecil sebesar 392.8014 km dengan waktu eksekusi 11.836 s dalam 500 iterasi. Rute yang diperoleh adalah sebagai berikut:



Gambar 5 Rute pendekatan yang dihasilkan pada kasus I



13 Kasus II Pada kasus II akan dilakukan percobaan menggunakan parameter dengan nilai sebagai berikut: Tabel 3 Perbandingan hasil pada kasus II menggunakan beberapa parameter dan iterasi yang berbeda Jumlah Iterasi



𝛼



𝛽



𝑚



Total Jarak (dalam km)



300 300 400 500 600 700



0.7 1 1 1 1 1



1 5 5 5 5 5



50 50 50 50 50 50



535.0748 497.4685 481.1290 472.6510 470.1542 463.4509



Setelah melakukan beberapa kali percobaan, diperoleh total jarak pendekatan terkecil sebesar 463.4509 km dengan waktu eksekusi 21.340 s dalam 700 iterasi. Rute yang diperoleh adalah sebagai berikut :



Gambar 6 Rute pendekatan yang dihasilkan pada kasus II



14 Kasus III Pada kasus II akan dilakukan percobaan menggunakan parameter dengan nilai sebagai berikut: Tabel 4 Perbandingan hasil pada kasus III menggunakan beberapa parameter dan iterasi yang berbeda Jumlah Iterasi



𝛼



𝛽



𝑚



Total Jarak (dalam km)



400 400 500 600 700 800



0.9 0.9 0.9 1 0.9 0.9



5 5 5 5 5 5



50 70 70 70 70 70



543.4537 494.852 487.6729 488.1252 481.1320 464.7083



Setelah melakukan beberapa kali percobaan, diperoleh total jarak pendekatan terkecil sebesar 464.7083 km dengan waktu eksekusi 38.00 s dalam 800 iterasi. Rute yang diperoleh adalah sebagai berikut :



Gambar 7 Rute pendekatan yang dihasilkan pada kasus III



15 Perbandingan Hasil Tabel 5 Perbandingan waktu eksekusi Waktu Eksekusi (jam:menit:detik) ILP ACO 0:01:34 0:0:11.836 0:11:04 0:0:21.340 6:38:14 0:0:38.000



Kasus I II III



Berdasarkan Tabel 5 dapat dilihat bahwa waktu eksekusi ACO jauh lebih cepat dibandingkan dengan waktu eksekusi ILP. Untuk Kasus I, waktu eksekusi ACO delapan kali lebih cepat dibandingan ILP. Pada Kasus II, waktu eksekusi ACO 31 kali lebih cepat dibandingan dengan waktu eksekusi ILP. Waktu eksekusi ACO untuk Kasus III lebih cepat 629 kali dibandingkan dengan ILP. Tabel 6 Perbandingan total jarak Kasus I II III



Total Jarak (dalam km) ILP ACO 388.371 392.8014 427.584 463.4509 430.251 464.7083



Tabel 6 memperlihatkan total jarak yang dihasilkan oleh masing-masing metode. Metode ILP menghasilkan nilai yang optimal. Sedangkan ACO menghasilkan nilai pendekatan. Pada Kasus I terdapat persentase selisih jarak sebesar 1%. Sedangkan Kasus II dan Kasus III memiliki persentase selisih jarak sebesar 8%.



SIMPULAN DAN SARAN Simpulan Berdasarkan hasil penelitian ini dapat dilihat bahwa semakin besar kasus yang harus diselesaikan, waktu eksekusi yang dibutuhkan semakin lama. Dapat dilihat pula bahwa waktu eksekusi yang dihasilkan ACO jauh lebih cepat dibandingkan waktu eksekusi metode eksak. Dari tiga kasus yang ada, terlihat bahwa selisih jarak yang dihasilkan ACO terhadap ILP untuk kasus I dengan 30 node berselisih 1%, kasus II dengan 35 node berselisih 8%, dan kasus III dengan 38 node berselisih 8%. Saran Selisih jarak yang dihasilkan pada penelitian ini sebesar 8% masih relatif besar. Oleh karena itu, untuk penelitian selanjutnya diharapkan lebih mengeksplorasi metode pendekatan lain yang dapat menghasilkan selisih jarak yang lebih kecil.



16



DAFTAR PUSTAKA Dorigo M, Birattari M, Stützle T. 2006. Ant Colony Optimization – Artificial Ants as a Computational Intelligence Technique. IEEE Computational Intelligence Magazine. 1(4):28-39. doi: 10.1109/CI-M.2006.248054. Dorigo M, Gambardella L. 1997. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation. 1(1): 53-66. doi: 10.1109/4235.585892. Dorigo M, Socha K. 2007. An Introduction to Ant Colony Optimization. Belgia (BE): IRIDIA. Heizer J, Render B. 2010. Operations Management. Ed ke-9. Jakarta (ID): Salemba Empat. Liu W, Li S, Zhao F, Zheng A.2009. An Ant Colony Optimization Algorithm for The Multiple Traveling Salesmen Problem. IEEE Conference on Industrial Electronics and Applications. doi: 10.1109/ICIEA.2009.5138451. Mutakhiroh I, Saptono F, Hasanah N, dan Wiryadinata R,. 2007. Pemanfaatan Metode Heuristic Dalam Pencarian Jalur Terpendek Dengan Algoritme Semut dan Algoritme Genetik. Seminar Nasional Aplikasi Teknologi Informasi. ISSN: 1907-5022. Yogyakarta. Nemhauser G, Wolsey L. 1999. Integer and Combinatorial Optimization. New York (US): A Wiley-Interscience. Winston WL. 2004. Operations Research: Applications and Algorithms 4thed. California (US): Duxbury.



17



LAMPIRAN Lampiran 1 Sintaks model TSP pada software LINGO 11.0 MODEL: SETS: CITY/1..30/:U; LINK(CITY,CITY):DIST, X; ENDSETS DATA: DIST = @OLE('F:\NURUL FATHIAH\SKRIPSI\SKRIPSI\SKRIPSI\KODINGAN\data.xlsx','cobalagi'); @OLE('F:\NURUL FATHIAH\SKRIPSI\SKRIPSI\SKRIPSI\KODINGAN\data.xlsx','H') = X; ENDDATA



N=@SIZE(CITY); MIN=@SUM(LINK:DIST*X); @FOR(CITY(K):@SUM(CITY(I):X(I,K))=1;); @FOR(CITY(K):@SUM(CITY(J):X(K,J))=1;); @FOR(CITY(K):@FOR(CITY(J)|J#GT#1#AND#K#GT#1:U(J)-U(K)+N*X(J,K)