Skip to main content Skip to main navigation menu Skip to site footer

Dynamic Programming dalam Penyelesaian Masalah Penjadwalan

Authors
  • Fikri Akbar L Jl. Bahagia, Padang Bulan, Kota Medan 20155, Indonesia
  • Rosnani Ginting Kampus USU, Jl. Almamater, Padang Bulan, Kota Medan 20155, Indonesia
Issue       Vol 2 No 3 (2019): Talenta Conference Series: Energy and Engineering (EE)
Section       Articles
Galley      
DOI: https://doi.org/10.32734/ee.v2i3.751
Keywords: Cheapest Insertion Heuristics Greedy Dynamic Programming Travelling Salesman Problem
Published 2019-12-19

Abstract

Traveling Salesman Problem adalah salah satu masalah untuk menemukan rute terpendek dari bepergian seorang salesman dari kota pertama dan kemudian ke kota tujuan dan akhirnya kembali ke kota pertama, tetapi satu kota hanya sekali dikunjungi. Ada beberapa algoritma untuk menyelesaikan masalah salesman keliling, seperti Greedy Algorithm, Artificial Bee Colony Algorithm, Algoritma Heuristics Insertion Termurah, Algoritma Genetika dan banyak lagi. Dalam tulisan ini, hanya dibahas algoritma serakah, algoritma heuristik penyisipan termurah, dan pemrograman dinamis. Setelah dibandingkan menggunakan contoh kasus dengan 5 kota dan diselesaikan dengan algoritma ketiga, rute terpendek sama tetapi cara penyelesaiannya berbeda. Mereka memiliki kelebihan dan kekurangan masing-masing, dan memiliki karakteristik masing-masing. Algoritma serakah lebih cocok bila digunakan untuk sejumlah kota yang tidak terlalu banyak karena prosesnya lebih sederhana, tetapi algoritma heuristik penyisipan termurah lebih cocok untuk kasus dengan lebih banyak kota yang prosesnya lebih rumit daripada algoritma serakah. Menghitung dalam pemrograman dinamis harus benar karena akan berpengaruh untuk hasil penghitungan berikutnya.