Skripsi

Algoritma Variable Nighborhood Descent (VND) pada Vehicle Routing Problem with Time Windows (VRPTW) dan implementasinya / Vivi Ratnasari

Abstrak
Ratnasari Vivi. 2018. AlgoritmaVariable Neighborhood Descent (VND) pada Vehicle Routing Problem with Time Windows (VRPTW) dan Implementasinya Skripsi JurusanMatematika FakultasMatematika dan IlmuPengetahuanAlam Universitas Negeri Malang. Pembimbing (I) Dra. SaptiWahyuningsih M.Si. (II) DarmawanSatyananda S.T M.T. Kata Kunci distribusi graph vehicle routing problem with time windows (VRPTW) variable neighborhood descent (VND). Pemilihanrutemerupakan salah satuaspekpentingdalambidangpendistribusian. Permasalahanpenentuanruteyang ditempuh oleh kendaraandistribusi dalamteori graph dikenaldenganVehicle Routing Problem(VRP). Salah satuvarian VRP dengantambahankendalatime windowsuntuksetiapcustomeradalah VRPTW. Permasalahan VRPTW dapatdiselesaikandenganmenggunakanalgoritmaVariable Neighborhood Descent (VND). Teknik yang digunakanalgoritmaVND untuk menyelesaikan permasalahan VRPTW adalahdenganmemberikan himpunan struktur neighborhood untuk suatu solusi awal kemudian memeriksa keoptimalan dari solusi awal menggunakan struktur neighborhoodtersebut.Langkahpertamadalamalgoritma VND adalahmembentuksolusiawalmenggunakanalgoritmaNearest Neighbor. Langkahkeduaadalahmengujikeoptimumansolusiawaldengancaramelakukanpertukaranposisicustomer darisolusiawalmenggunakanenamstrukturneighborhood diantaranyaswap (1-1) swap (2-1) swap (2-2) insertion exchangedan 2-optsecaraberurutan.Solusidariproses pertukarandibandingkandengansolusiawaluntukmengetahuisolusi mana yang memberikanhasil yang lebihbaik. Langkahkeduatersebutdilakukansecaraberulangsampaidiperolehkondisi optimum.Kondisi optimum tercapaisaatsemuastrukturneighborhood telahdilewati dan menghasilkansolusi-solusi yang konvergenkesuatunilai yang minimum. Implementasialgoritma VND untuk VRPTW dirancangdalambahasapemrogramanBorland Delphi 7.0. Berdasarkancontohpermasalahan yang telahdibahas penyelesaian VRPTW menggunakanalgoritma VND menghasilkansolusi yang lebihbaikdengantotal waktutempuhyang lebihpendekdibandingkandenganalgoritmaMultiple Ant Colony System (MACS) dan algoritmaModified Saving with Exchange Local Search (MS-ELS).Berdasarkan uji coba program yang telahdilakukanmenggunakan data titik yang sama diperolehhasilbahwaaplikasi VND-VRPTW menghasilkanrutedengan total waktulebihpendeksecaraberturut-turutadalah 3 58% 26 4% 12 15% 10 1% dan 6 75% dibandingkanrute yang dihasilkan oleh aplikasi TSP-VRP. Aplikasi VND-VRPTW juga menghasilkanrutedengan total waktulebihpendeksecaraberturut-turutadalah 21 29% 1 85% 11 53% 22 71% dan 7 31% dibandingkanrute yang dihasilkan oleh aplikasi MACS-MDVRPTW.

Informasi Detail

DDC

Rs 518.1 RAT a

Prodi

Universita Negeri Malang. Program Studi Matematika, 2018.

Deskripsi Fisik

xiv, 179 Lembar :il.,tab.,30cm

Bahasa

Indonesia

No Reg

05007/KI/18

Edisi

Skripsi(Sarjana). Universitas Negeri Malang. 2018

Subjek

1. ALGORITMA
2. DISTRIBUSI (MATEMATIKA)
3. ALGORITHM

Pembimbing

1. Sapti Wahyuningsih ; 2. Darmawan Satyananda

Lampiran Berkas