Skripsi

Algoritma general variable neighborhood search (gvns) pada vehicle routing problem with simultaneous delivery and pick-up (vrpsdp) dan implementasinya / Dyah Ayu Retno Widiari Lintang Manggali Putri

Abstrak
Matematika merupakan salah satu ilmu pengetahuan yang penerapannya dapat digunakan untuk menyelesaikan permasalahan dalam kehidupan sehari-hari seperti menentukan rute pendistribusian. Permasalahan tersebut termasuk dapat diselesaikan dengan salah satu cabang ilmu matematika yaitu teori graf khususnya pada materi Vehicle Routing Problem (VRP). Vehicle Routing Problem with Simultaneous Delivery and Pickup (VRPSDP) merupakan perluasan dari VRP yang memiliki kendala khusus yaitu permintaan dan pengembalian dilakukan secara bersamaan. Pada penelitian ini Algoritma yang digunakan dalam menyelesaikan VRPSDP adalah Algoritma General Variable Neighborhood Search (GVNS) yang terdiri dari beberapa tahapan yaitu pembentukan solusi awal dengan Algoritma Insertion Heuristic tahap perturbasi dan tahapan perbaikan solusi dengan Algoritma RVND. Implementasi dari algoritma tersebut telah dibuat dengan menggunakan aplikasi Borland Delphi 7 sebagai alat bantu perhitungan. Program tersebut telah diujicobakan dengan menggunakan 6 customer 10 customer 30 customer 75 customer 100 customer serta 4 dataset. Output yang dihasilkan program adalah berupa rute yang terbentuk beserta jarak tempuhnya dan visualisasi dari rute tersebut. Hasil yang diperoleh dari permasalahan 6 customer adalah sebesar 266 km yang kemudian dibandingkan dengan Algoritma Reactive Greedy Randomized Adaptive Search (RGRASP) yang menghasilkan solusi 361 km. Hal tersebut menyatakan bahwa Algoritma GVNS menghasilkan solusi yang lebih baik dibandingkan dengan Algoritma RGRASP. Kemudian berdasarkan hasil uji coba dataset menggunakan perbandingan antara Algoritma GVNS dengan Algoritma Tabu Search diketahui bahwa dataset c101 yang diselesaikan dengan menggunakan Algoritma GVNS memiliki solusi 1296 126 dengan nilai gap yaitu 0 029% dari solusi Algoritma Tabu Search untuk uji coba dataset r101 menghasilkan solusi 1090 529 dengan nilai gap yaitu 0 046%. Begitu juga dengan dataset c1_2_1 yang diselesaikan dengan Algoritma GVNS menghasilkan solusi 4060 651 memiliki gap 0 70% dan dataset r1_2_1 yang menghasilkan solusi 3715 843 dengan nilai gap yaitu 0 078%. Sehingga berdasarkan data tersebut dapat diketahui bahwa solusi yang dihasilkan dataset melalui uji coba dengan Algoritma GVNS memiliki solusi total jarak yang sedikit lebih jauh jika dibandingkan dengan Algoritma Tabu Search dan nilai rata-rata gap dari kedua algoritma adalah 0 05%. Artinya selisih hasil yang dihasilkan Algoritma GVNS sangat kompetitif dengan rentang nilai persentase gap antara 0 029% sampai 0 078%.

Informasi Detail

DDC

Rs 518.1 PUT a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2021.

Deskripsi Fisik

vi, 21 lembar : il. ; 30 cm.

Bahasa

Indonesia

No Reg

00992/KI/22

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2021

Subjek

1. ALGORITMA - GENERAL VARIABLE NEIGH BORHOOD SEARCH
2. ALGORITHM - GENERAL VARIABLE NEIGH BORHOOD SEARCH

Pembimbing

1. Hj. Sapti Wahyuningsih ; 2. Mahmuddin Yunus

Lampiran Berkas