Penyelesaian masalah traveling salesman problem dengan menggunakan parallel dynamic programming

Abstract

Traveling salesman problem adalah suatu masalah pencarian sirkuit yang melewati semua simpul dari suatu graf dengan bobot minimum. Saat ini, belum ada algoritma yang dapat menyelesaikan masalah traveling salesman problem dalam polynomial-time, yang berarti waktu yang dibutuhkan untuk menyelesaikan masalah bertambah dengan cepat seiring bertambahnya ukuran masalah. Salah satu cara untuk mengurangi waktu yang digunakan dalam menyelesaikan traveling salesman problem adalah dengan melakukan komputasi dengan menggunakan beberapa processing core dalam waktu yang sama (komputasi paralel).

Algoritma Held-Karp adalah sebuah algoritma yang berdasar pada paradigma dynamic programming, yang mana saat ini merupakan salah satu algoritma tercepat untuk menyelesaikan traveling salesman problem. Algoritma Held-Karp dapat dikombinasikan dengan komputasi paralel untuk mengurangi waktu yang dibutuhkan. Penggunaan komputasi paralel membutuhkan suatu teknik untuk mendistribusikan beban kerja secara efisien kepada processing core yang digunakan. Task decomposition adalah suatu teknik pendistribusian beban kerja yang cocok untuk digunakan pada Algoritma Held-Karp.

Sebuah eksperimen dilakukan untuk mengukur peningkatan kinerja yang dihasilkan dari penggunaan komputasi paralel dalam penyelesaian traveling salesman problem. Eksperimen dilakukan pada 3 graf berbeda, yaitu pada graf dengan 18, 20, dan 25 simpul. Peningkatan kinerja diukur dengan membandingkan penurunan waktu dengan penambahan banyak thread yang digunakan. Banyak thread yang digunakan adalah 1 sampai dengan 6 thread. Penggunaan 2 thread dibanding 1 thread menghasilkan penurunan waktu sebesar 48, 95% sampai dengan 54, 59% sedangkan penggunaan 3 thread dibanding 2 thread menghasilkan penurunan waktu sebesar 14, 62% sampai dengan 23, 85%. Penambahan banyak thread diatas 3 menghasilkan penurunan waktu yang jauh lebih kecil yaitu berkisar antara -1, 55% sampai dengan 5, 68%.