Skripsi

Algoritma Variable Neighborhood Descent (VND) pada Multiple Trip Vehicle Routing Problem (MTVRP) dan implementasinya / Pratiwi Ratih Dewi

Abstrak
ABSTRAK Dewi Pratiwi Ratih. 2017. Algoritma VariableNeigborhoodDescent(VND) pada Multiple Trip VehicleRouting Problem (MTVRP) dan Implementasinya Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (1) Dra. SaptiWahyuningsih M.Si. (II) DarmawanSatyananda S.T M.T. Kata Kunci graph vehicle routing problem (VRP) Multiple Trip VehicleRouting Problem (MTVRP) SequentialInsertion VariableNeighborhoodDescent(VND) localsearch distribusi. Proses pendistribusian berkaitan erat dengan pemilihan rute distribusi sehingga diperoleh rute yang optimum dengan biaya pendistribusian minimum. Model pendistribusian bervariasi sesuai dengan batasan yang harus dipenuhi salah satunya adalah batas waktu operasi. Varian VehicleRouting Problem (VRP) yang dibatasi oleh waktu operasi adalah Multiple Trip VehicleRouting Problem (MTVRP) dimana kendaraan dapat menempuh beberapa rute selama periode waktu tertentu. Pencarian rute terpendek pada MTVRP melibatkan solusi awal yang kemudian diperbaikan dengan localsearch. VariableNeighborhoodDescent(VND) merupakan varian paling sederhana dari VariableNeighborhoodSearch(VNS) yang menampilkan beberapa turunan dengan neighborhoodberbeda. Langkah pertama algoritma VND yaitu membentuk solusi awal menggunakan algoritma SequentialInsertion. Langkah keduaadalah tahap perbaikan localsearchmenggunakan prosedur VND dengan enam struktur neighborhoodyang dilakukan secara berurutan (1-insertion intraroute (N_1) 1-insertion inter-route(N_2) 1-1 swap(N_3) 2-0 shift(N_4) 2-2 swap(N_5) 2-1 swap(N_6)) dari neighborhood1 sampai neighborhood6 hingga diperoleh kondisi optimum. Kondisi optimum tercapai saat struktur neighborhoodtelah dilewati semua dan tidak dapat dilakukan perbaikan lagi. Secara umum solusi awal yang diperoleh dari algoritma SequentialInsertionsetelah diperbaiki dengan VND menghasilkan solusi baru yang lebih baik yaitu waktu tempuh yang lebih pendek dari waktu tempuh awal.Implementasi dari algoritma VND untuk MTVRP dalam bahasa pemrograman Borland Delphi 7.0 berhasil dirancang secara terstruktur. Aplikasi diuji coba untuk kasus 10 titik 13 titik 21 titik dan 31 titik.

Informasi Detail

DDC

Rs 518.1 DEW a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2017.

Deskripsi Fisik

xii, 131 lembar : il. , tab. ; 30 cm

Bahasa

Indonesia

No Reg

05517/KI/17

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2017

Subjek

1. ALGORITMA
2. ALGORITHMS

Pembimbing

1. Sapti Wahyuningsih ; 2. Darmawan Satyananda

Lampiran Berkas