Skripsi

Permasalahan Dynamic Travelling Salesman Problem (D-TSP) dan implementasi programnya / Rizki Dinar Palupi

Abstrak
ABSTRAK Palupi Rizki Dinar. 2013. Permasalahan Dynamic Travelling Salesman Problem (D-TSP) dan Implementasi Programnya. Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I). Dra. Sapti Wahyuningsih MSi (II). Lucky Tri Oktoviana S.Si M.Kom. Kata Kunci graph Dynamic Travelling Salesman Problem (D-TSP) Algoritma Nearest Neighbor Heuristic. Nearest Insertion Heuristic Dynamic Traveling Salesman Problem (D-TSP) merupakan masalah kombinatorial yang kompleks dalam masalah optimal. Pada dasarnya D-TSP adalah pengembangan dari Traveling Salesman Problem (TSP). Bedanya adalah dalam TSP hanya mencari jarak titik tujuan sudah ditentukan dan tetap D-TSP mencari jarak dan waktu yang sudah ditentukan kemudian titik tujuan tidak tetap sehingga terjadi penambahan titik tujuan maupun pengurangan titik tujuan. Pendeskripsian D-TSP adalah bagaimana cara menemukan penggunaan lintasan minimum dari suatu proses pengiriman barang di mana titik tujuan tersebut dapat berubah sewaktu-waktu. Setiap pelanggan harus dilayani tepat satu setiap pengiriman barang. Diperlukan suatu metode yang lebih baik dari algoritma heuristik untuk menemukan rute minimum suatu graph. Salah satunya adalah Algoritma Nearest Insertion Heuristic dan Nearest Neighbor Heuristic. Langkah pertama pada Algoritma nearest neighbor heuristic pada D-TSP adalah mencari titik awal kemudian cari titik lainnya yang terhubung langsung. Pada pertengahan langkah terdapat penambahan dan pengurangan titik. Pada akhir langkah ini didapat hasil minimum. Algoritma nearest insertion heuristic pada D-TSP adalah mencari titik awal kemudian cari titik lainnya kemudian terdapat penyisipan titik antara titik yang terhubung langsung tersebut. Pada pertengahan langkah terdapat penambahan dan pengurangan titik. Pada akhir langkah ini didapat hasil sikel minimum. Kedua algoritma di atas bila dibandingkan dalam D-TSP yaitu proses penambahan dan pengurangan titik sedangkan TSP tidak terdapat penambahan dan pengurangan titik pada tengah proses. Untuk menyelesaikan masalah D-TSP dalam proses analisa hasil iterasi yang berbeda dibuatlah program yang menggunakan software Delphi 7. Berdasarkan perhitungan dengan menggunakan Algoritma Nearest Insertion Heuristic dan Nearest Neighbor Heuristic yang dilakukan 50 60 70 titik melalui implementasi program diperoleh hasil yang berbeda.

Informasi Detail

DDC

Rs 519.703 PAL p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

ix, 79 lembar : il. , tab. ; 30 cm

Bahasa

Indonesia

No Reg

02024/KI/15

Edisi

Skripsi (Sarjana). Universitas Negeri Malang, 2013

Subjek

1. PEMOGRAMAN (MATEMATIKA)
2. TRAVELING SALESMAN PROBLEM

Pembimbing

1. Sapti Wahyuningsih ; 2. Lucky Tri Oktoviana

Lampiran Berkas