PENERAPAN PROGRAM DINAMIK PADA TRAVELING SALESMAN PROBLEM (TSP)

Masalah Traveling Salesman Problem (TSP) merupakan persoalan kombinatorial yang tidak sederhana sehingga diperlukan suatu algoritma atau metode yang dapat menyelesaikannya. Metode dan algoritma yang telah ditemukan untuk menyelesaikan permasalahan ini diantaranya Linear Programing (LP), Genetic Algorithm (GA), Nearest Neighbourhood Heuristics (NNH),Cheapest Insertion Heuristic Algorithm, Ant Algorithm (Algoritma Semut) dan lain-lain akan tetapi metode-metode tersebut masih memiliki kekurangan yaitu banyaknya komputasi yang harus dilakukan. Dynamic Programming (Program Dinamik) adalah salah satu metode yang menggunakan sedikit komputasi dan mengandalkan memori. Pada program dinamik, penyelesaian masalah harus memenuhi karakteristik-karakteristik yang ada di dalamnya. Secara umum, dalam program dinamik ada tiga unsur dasar yang diperlukan untuk mendapatkan solusi permasalahan, yaitu tahap (stage), keadaan (state) dan alternatif variabel keputusan. Jika masalah optimasi memenuhi ketiga unsur tersebut maka masalah ini dapat diselesaikan dengan program dinamik. Masalah TSP memenuhi ketiga unsur tersebut yaitu TSP dibagi menjadi tahapan,keadaaan, dan alternatif variabel keputusan yang berupa alternatif jalur yang dilewati sehingga dapat diselesaikan dengan program dinamik. Dari hasil pembahasan, karakteristik-karakteristik program dinamik pada TSP antara lain: masalah TSP dapat dibagi menjadi beberapa tahap dengan setiap tahap diperlukan suatu keputusan, setiap tahap pada TSP memiliki sejumlah ketetapan, pada TSP keputusan pada tahap sekarang akan menjadi masukan pada tahap berikutnya, pada TSP keputusan optimal untuk setiap tahap yang tersisa tidak tergantung pada keputusan yang dipilih sebelumnya, prosedur penyelesaian masalah TSP dimulai dengan mendapatkan keputusan terbaik untuk setiap ketetapan dari tahap awal, pada TSP adanya suatu hubungan rekursif yang mengidentifikasi keputusan terbaik untuk setiap ketetapan antara Tahap n dengan Tahap (n +1) dan prosedur penyelesaian masalah TSP bergerak mundur atau maju tahap demi tahap. Penyelesaian TSP dimulai dengan merepresentasikan TSP dalam graf, membagi dalam beberapa tahap, dan menyelesaikannya dengan mengggunakan karakteristik-karakteristik program dinamik pada TSP maka diperoleh penyelesaian dari masalah TSP tersebut. Masalah TSP dengan kasus khusus yaitu adanya lokasi yang tidak terhubung dengan lokasi yang lain dapat diselesaikan dengan program dinamik dengan menambahkan rusuk semu pada graf yang merepresentasikan masalah TSP tersebut. TSP simetris, TSP asimetris dan TSP dengan kasus khusus dapat diselesaikan dengan program dinamik