Skripsi

Implementasi metode Simulated Annealing (SA) pada Vehicle Routing Problem with Simultaneous Deliveries and Pick-ups (VRPSDP) / Amelia Wahyu Noor Aida

Abstrak
ABSTRAK Aida Amelia Wahyu Noor. 2015. Implementasi Metode Simulated Annealing (SA) pada Vehicle Routing Problem With Simultaneous Deliveries and Pick-Ups (VRPSDP). Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I) Mohamad Yasin S.Kom M.Kom (II) Dra. Mimiep Setyowati Madja M.Kom Kata Kunci Metode Simulated Annealing (SA) Vehicle Routing Problem With Simultaneous Deliveries and Pick-Ups (VRPSDP) Vehicle Routing Problem (VRP). Teori graph adalah bahasan dalam matematika yang dapat digunakan untuk menyelesaikan permasalahan optimalisasi. Optimalisasi dalam menentukan sejumlah rute untuk sekumpulan kendaraan yang harus melayani sejumlah konsumen merupakan permasalahan Vehicle Routing Problem (VRP). Vehicle Routing Problem With Simultaneous Deliveries and Pick-Ups (VRPSDP) adalah pengembangan dari VRP dengan penambahan kendala di mana pada saat pengiriman barang ke konsumen disertai pula oleh pengambilan barang dari konsumen. Permasalahan VRPSDP dapat diselesaikan menggunakan modifikasi metode yang digunakan untuk menyelesaikan permasalahan Travelling Salesman Problem (TSP) yaitu metode Simulated Annealing (SA). Tahapan-tahapan metode SA untuk menyelesaikan permasalahan VRPSDP meliputi tahap pertama adalah menentukan kondisi atau jalur awal menggunakan permutasi Josephus. Tahap kedua adalah penentuan rute kendaraan dengan cara menghitung kendala kapasitas kendaraan. Tahap ketiga adalah menentukan kondisi baru menggunakan metode SA. Dari kondisi baru yang diperoleh melakukan tahap keempat dengan cara yang sama seperti pada tahap kedua. Tahap kelima adalah meng-update kondisi sekarang dengan cara membandingkan total jarak kondisi awal dengan kondisi baru. Selanjutnya mengulangi tahap ketiga sampai tahap kelima sebanyak iterasi yang diinginkan. Untuk menyelesaikan permasalahan VRPSDP menggunakan metode SA diperlukan iterasi yang banyak untuk mendapatkan hasil solusi rute yang optimum. Pengerjaan manual akan sangat panjang jika iterasi yang diinginkan sangat banyak. Oleh karena itu untuk mempermudah mendapatkan hasil solusi rute yang optimum metode SA diimplementasikan ke dalam program komputer yang dibuat dengan Borland Delphi. Program yang telah dibuat diuji coba dengan beberapa titik yaitu 7 9 20 50 dan 100 titik. Dua dari kelima uji coba yaitu 7 titik dan 9 titik dibandingkan dengan pengerjaan manual dari metode dan algoritma lain. Dari perbandingan pertama yaitu 7 titik program SA dibandingkan dengan metode Insertion Heuristic yang telah diselesaikan dalam skripsi oleh Diaz Vinancya Ayuandari tahun 2009. Solusi rute yang diperoleh dari program SA menghasilkan total jarak tempuh yang lebih optimum dibanding dengan solusi rute yang diperoleh dari metode Insertion Heuristic. Dari perbandingan kedua yaitu 9 titik program SA dibandingkan dengan metode Insertion Heuristic yang telah diselesaikan dalam skripsi oleh Diaz Vinancya Ayuandari tahun 2009 algoritma Scatter Search yang telah diselesaikan dalam skripsi oleh Muhammad Zakaria tahun 2014 dan algoritma Ant Colony System (ACS) yang telah diselesaikan dalam skripsi oleh Cornelius Bahtiar Cristy tahun 2014. Solusi rute yang diperoleh dari program SA dan algoritma Ant Colony System menghasilkan total jarak tempuh yang sama dan lebih optimum dibanding dengan solusi rute yang diperoleh dari algoritma Scatter Search dan metode Insertion Heuristic. Berdasar solusi rute dan total jarak yang dihasilkan oleh masing-masing pengerjaan program SA mampu menyelesaikan permasalahan VRPSDP dengan hasil paling optimum. Hal ini disebabkan oleh proses random dalam pencarian rute dan iterasi yang diinputkan.

Informasi Detail

DDC

Rs 511.8 AID i

Prodi

Universitas Negeri Malang. Program Studi Pendidikan Matematika, 2015.

Deskripsi Fisik

xi, 103 hlm. : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

03171/KI/15

Edisi

Skripsi (Sarjana)-- Universitas Negeri Malang, 2015

Subjek

1. GRAPH, TEORI
2. GRAPH THEORY

Pembimbing

1. Mohamad Yasin ; 2. Mimiep Setyowati Madja

Lampiran Berkas