IMPLEMENTASI ALGORITMA PARALEL UNTUK TRAVELING SALESPERSON PROBLEM DENGAN MPI.NET PADA VISUAL C#

Abstract

Travelling Salesperson Problem merupakan salah satu persoalan optimasi klasik dengan berbagai teknik
penyelesaiannya, termasuk juga teknik Brute Force. Teknik ini sederhana tetapi memiliki O(n!) dimana n.
Algoritma pada teknik ini memilik potensi untuk adanya eksekusi secara paralel. Pada penelitian ini, dilakukan
paralelisme algoritma Brute Force dengan model Single Program Multiple Data (SPMD). Algoritma
diimplementasikan pada lingkungan C#.NET dengan library Message Passing Interface MPI.NET. Eksekusi
algoritma dilakukan untuk dataset persoalan TSP simetrik, dan dilakukan untuk berbagai n simpul dan m buah
mesin paralel. Untuk eksekusi sekuensial, maksimal simpul yang dapat diekskusi adalah 11 sedangkan untuk
eksekusi paralel, maksimal simpul yang dapat diekekusi adalah 12. Speedup, yaitu perbandingan waktu
eksekusi sekuensial dan paralel, dengan waktu terbaik didapat pada eksekusi dengan 2 buah mesin untuk 11
simpul. Semakin banyak mesin, eksekusi paralel menjadi semakin lama. Hal ini dikarenakan adanya overhead
komunikasi antar proses. Namun demikian, potensi paralelisme pada teknik Brute Force dapat terus
dikembangkan dan menjadi dasar dari model paralel untuk teknik penyelesaian TSP lainnya