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

Aida, Amelia Wahyu Noor (2015) Implementasi metode Simulated Annealing (SA) pada Vehicle Routing Problem with Simultaneous Deliveries and Pick-ups (VRPSDP) / Amelia Wahyu Noor Aida. Diploma thesis, Universitas Negeri Malang.

Full text not available from this repository.

Abstract

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.

Item Type: Thesis (Diploma)
Subjects: ?? ??
Divisions: Fakultas Matematika dan IPA (FMIPA) > Jurusan Matematika (MAT) > S1 Pendidikan Matematika
Depositing User: Users 2 not found.
Date Deposited: 02 Jul 2015 04:29
Last Modified: 09 Sep 2015 03:00
URI: http://repository.um.ac.id/id/eprint/15622

Actions (login required)

View Item View Item