Skripsi

Analisis tiga jenis perturbasi pada ILS-RVND untuk permasalahan OVRPTW / Alin Nabilah

Abstrak
tidak kembali lagi ke depot sehingga proses berakhir hingga customer terakhir saja. Selain itu kendala waktu yang terdapat pada depot maupun customer juga berperan penting dalam pencarian rute optimal. Oleh karena itu terbentuklah salah satu varian dari VRP yaitu Open VRP with Time Windows (OVRPTW). Pencarian rute optimal pada permasalahan OVRPTW dilakukan dengan menggunakan algoritma ILS-RVND. Algoritma ILS-RVND terdiri dari empat tahap yaitu penentuan solusi awal local search perturbasi serta penerimaan kriteria. Pencarian solusi awal dilakukan dengan menggunakan algoritma sequential insertion kemudian melakukan perulangan tahap local search-RVND dan perturbasi secara berurutan sebanyak MaxIter. Terakhir tahap penerimaan kriteria untuk memutuskan solusi yang paling optimal. Pada tahap perturbasi akan dilakukan dengan menggunakan 3 jenis yaitu ejection chain double swap dan double bridge. Dari ketiga perturbasi tersebut dilakukan analisis mengenai langkah kerja serta hasil penerapannya. Hasil analisis perbandingan ketiga jenis perturbasi pada ILS-RVND dari 2 contoh yang diberikan didapatkan bahwa penggunaan perturbasi dengan double swap menghasilkan solusi yang lebih baik. Karena dalam sekali percobaannya dilakukan perpindahan sebanyak dua kali sekaligus dan penggunaannya juga fleksibel untuk berbagai jumlah titik. Untuk ejection chain mampu memberikan solusi yang lebih baik namun tidak sebaik solusi dari double swap karena perpindahan yang dilakukan bergantung pada rute sebelumnya. Sedangkan untuk double bridge tidak mampu memberikan solusi yang lebih baik karena customer yang diambil sekaligus dalam jumlah yang besar sehingga tidak dapat menelusuri semua kemungkinan yang ada serta tidak fleksibel terhadap jumlah customer yang sedikit dalam satu rutenya

Informasi Detail

DDC

Rs 518.1 NAB a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2019.

Deskripsi Fisik

xv, 150 lembar: il., tab.; 30 cm

Bahasa

Indonesia

No Reg

03297/KI/19

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2019

Subjek

1. ALGORITMA
2. ALGORITHMS

Pembimbing

1. Sapti Wahyuningsih

Lampiran Berkas