implementasi algoritma palgunadi untuk …eprints.uns.ac.id/17533/1/cover.pdf ·...

perpustakaan.uns.ac.id digilib.uns.ac.id

commit to user

IMPLEMENTASI ALGORITMA PALGUNADI

UNTUK MENYELESAIKAN SINGLE DAN MULTI

PRODUCT VEHICLE ROUTING PROBLEM

SKRIPSI

Diajukan untuk Memenuhi Salah Satu Syarat Mencapai Gelar Strata

Satu Jurusan Informatika

HALAMAN JUDUL

Disusun Oleh :

IKA TOFIKA RINI

M0510028

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

2015


commit to user ii

SKRIPSI

IMPLEMENTASI ALGORITMA UNTUK MENYELESAIKAN

SINGLE DAN MULTI PRODUCT VEHICLE ROUTING PROBLEM

HALAMAN PENGAJUAN

Disusun oleh :

Ika Tofika Rini

M0510028

ditulis dan diajukan untuk memenuhi sebagian persyaratan

memperoleh gelar Strata Satu Jurusan Informatika

JURUSAN INFORMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SEBELAS MARET

SURAKARTA

2015


commit to user iii

SKRIPSI

IMPLEMENTASI ALGORITMA UNTUK MENYELESAIKAN WITH

SINGLE DAN MULTI PRODUCT VEHICLE ROUTING PROBLEM

HALAMAN PERSETUJUAN

Disusun oleh : Ika Tofika Rini

M0510028

Skripsi ini telah disetujui untuk dipertahankan di hadapan dewan penguji,

Pada tanggal: 24 Maret 2015

Pembimbing 1,

Drs. YS. Palgunadi, M.Sc. NIP. 19560407 198303 1 004

Pembimbing 2,

Drs. Bambang Harjito, M.App.Sc., Ph.D. NIP. 19621130 199103 1 002

HA


commit to user iv

NSKRIPSI

IMPLEMENTASI ALGORITMA UNTUK MENYELESAIKAN

VEHICLE ROUTING PROBLEM WITH SINGLE AND MULTI

PRODUCT

HALAMAN PENGESAHAN

Disusun oleh :

Ika Tofika Rini

M0510028

Telah dipertahankan di hadapan Dewan Penguji

pada tanggal: 24 Maret 2015

Susunan Dewan Penguji

1. Drs. Y.S. Palgunadi, M.Sc. ( )

NIP. 19560407 198303 1 004

2. Drs. Bambang Harjito, M.App.Sc., Ph.D. ( ) NIP. 19621130 199103 1 002

3. Abdul Aziz, S.Kom., M.Cs. ( )

NIP. 19810413 200501 1 001

4. Drs. Wiranto, M.Kom., M.Cs. ( )

NIP. 19661230 199302 1 001

Disahkan Oleh

19621130 199103 1 002


commit to user v

HALAMAN PERSEMBA

Skripsi ini penulis persembahkan untuk

kedua orang tuaku,

adikku tercinta,

teman-teman Informatika angkatan 2010.


commit to user vi

KATA PENGANTAR

Segala puji dan syukur penulis ucapkan kepada Allah SWT, yang hanya

karena rahmat dan karunia-Nya, penulis dapat menyelesaikan skripsi dengan judul

Implementasi Algoritma Palgunadi Untuk Menyelesaikan Single and Multi

Product Vehicle Routing Problem

mendapatkan gelar strata satu Informatika Universitas Sebelas Maret Surakarta.

Penulis menyadari keterbatasan yang dimiliki, serta penulis mengucapkan

terima kasih atas bantuan, bimbingan, dan petunjuk selama penulis menyusun

skripsi ini. Semoga Allah membalas kebaikan mereka yang telah membantu penulis

menyelesaikan skripsi ini. Penulis ucapkan terima kasih kepada :

1. Kedua orang tua Penulis, yang selalu mencurahkan kasih sayang, doa, serta

dukungan kepada Penulis.

2. Bapak Drs. YS. Palgunadi, M.Sc., dosen pembimbing I yang penuh

kesabaran membimbing, mengarahkan, dan memberi motivasi kepada

penulis selama proses penyusunan skripsi ini.

3. Bapak Bambang Harjito, M.App.Sc., Ph.D., dosen pembimbing II yang

telah memberikan arahan serta masukan selama proses penyusunan skripsi.

4. Bapak Meiyanto Eko Sulistyo, S.T., M.Eng., dosen Pembimbing Akademik

yang telah memberikan bimbingan dan pengarahan selama Penulis

menempuh studi di Jurusan Informatika.

5. Teman-teman Informatika angkatan 2010 Maman,

Eva, Shofi, Aish, April, Kartika, Dian C, dan Pingky yang selalu

memberikan semangat dan motivasi kapanpun dan dimanapun.

6. Kakak-kakak tingkat Informatika yang senantiasa memotivasi penulis untuk

segera menyelesaikan skripsi ini.

Semoga skripsi ini dapat memberikan manfaat bagi pembaca umumnya

dan mahasiswa Informatika pada khususnya.

Surakarta, Maret 2015

Penulis


commit to user vii

IMPLEMENTASI ALGORITMA PALGUNADI UNTUK MENYELESAIKAN SINGLE DAN MULTI PRODUCT

VEHICLE ROUTING PROBLEM

IKA TOFIKA RINI Jurusan Informatika, Fakultas Matematika dan Ilmu Pengetahuan Alam,

Universitas Sebelas Maret

ABSTRAK Vehicle Routing Problem dengan single dan multi product merupakan

permasalahan perencanaan routing transportasi distribusi barang dengan satu dan lebih dari satu jenis komoditi barang. Saat ini dalam menentukan rute tidak mempertimbangkan area customer secara keseluruhan dan tidak memaksimalkan kapasitas dari kendaraan yang digunakan. Penelitian ini mengusulkan Algoritma Palgunadi sebagai algortima baru untuk menentukan rute dalam kasus single dan multi product. Tahapan penelitian ini meliputi pengumpulan dan pengolahan data, implementasi algoritma Palgunadi menggunakan Java, tes validasi, dan tes efisiensi. Implementasi algoritma Palgunadi menggunakan bahasa pemrograman Java diperoleh hasil berupa rute dan jumlah kendaraan yang digunakan sesuai dengan perhitungan manual. Algoritma Palgunadi juga dapat digunakan untuk menyelesaikan kasus dalam skala besar dibuktikan dengan running time. Hubungan banyaknya agen yang harus dilayani per running time program menunjukan kondisi kuadratik dan hubungan banyaknya agen per banyaknya kendaraan menunjukkan kondisi linear. Dengan demikian Algoritma Palgunadi ini dapat diajukan sebagai salah satu algoritma alternatif pemecahan masalah penentuan rute kendaraan untuk kasus Vehicle Routing Problem dengan single dan multi product.

Kata Kunci: Vehicle Routing Problem, Algoritma Palgunadi


commit to user viii

THE IMPLEMENTATION OF PALGUNADI ALGORITHM TO SOLVE SINGLE AND MULTI

PRODUCT VEHICLE ROUTING PROBLEM

IKA TOFIKA RINI Department of Informatics, Mathematics and Science Faculty, Sebelas Maret

University

ABSTRACT

Vehicle Routing Problem with Single and Multi Product is routing transportation planning problems with the distribution of goods and more than one type of commodity goods. Currently in determining the route does not take into consideration the customer area as a whole and does not maximize the capacity of the vehicle. This research proposes algorithm Palgunadi as new algorithm to determine the route in case of single and multi-product. Stages of this study consisted of data collectiing and processing, Palgunadi algorithm implementation using Java, test validation, and test efficiency. Palgunadi algorithm is implemented using the Java programming language. The results show the same results with manual calculation. Palgunadi algorithm can also be used to solve large-scale case evidenced by the running time. Relationship number of agents per running time indicates a quadratic condition. Relationship number of agents per number of vehicles indicates a linear condition. This algorithm can also complete infeasible conditions. Thus Palgunadi algorithm can be proposed as one of the alternative algorithms solving the problem of determining the case of vehicles for Vehicle Routing Problem with single and multi product.

Key Words: Vehicle Routing Problem, Palgunadi Algorithm


commit to user ix

DAFTAR ISI

HALAMAN JUDUL ............................................................................................... i

HALAMAN PENGAJUAN .................................................................................... ii

HALAMAN PERSETUJUAN ............................................................................... iii

HALAMAN PENGESAHAN ............................................................................... iv

HALAMAN PERSEMBAHAN .............................................................................. v

KATA PENGANTAR ........................................................................................... vi

ABSTRAK ............................................................................................................ vii

ABSTRACT ......................................................................................................... viii

DAFTAR ISI .......................................................................................................... ix

DAFTAR TABEL .................................................................................................. xi

DAFTAR GAMBAR ............................................................................................ xii

DAFTAR LAMPIRAN ........................................................................................ xiii

PENDAHULUAN ................................................................................................... 1

1.1 Latar Belakang ............................................................................................... 1

1.2 Rumusan Masalah .......................................................................................... 3

1.3 Batasan Masalah ............................................................................................. 3

1.4 Tujuan Penelitian ............................................................................................ 4

1.5 Manfaat Penelitian .......................................................................................... 4

1.6 Sistematika Penulisan ..................................................................................... 4

TINJAUAN PUSTAKA .......................................................................................... 6

2.1 Dasar Teori ..................................................................................................... 6

2.1.1 Vehicle Routing Problem (VRP) .............................................................. 6

2.1.2 Vehicle Routing Problem Single Product ................................................ 8

2.1.3 Vehicle Routing Problem Multi Product ................................................. 9

2.1.4 Model Matematika VRP .......................................................................... 9

2.1.5 Algoritma Tabu Search .......................................................................... 11

2.1.6 Algoritma Palgunadi .............................................................................. 12

2.2 Penelitian Terkait ......................................................................................... 14

2.3 Rencana Penelitian ....................................................................................... 15

METODOLOGI ..................................................................................................... 16


commit to user x

3.1 Pengumpulan dan pemodelan data ............................................................... 16

3.2 Implementasi algoritma Palgunadi menggunakan Java ............................... 17

3.3 Tes validasi algoritma Palgunadi ................................................................. 19

3.4 Tes efisiensi algoritma Palgunadi ................................................................ 19

PEMBAHASAN .................................................................................................... 20

4.1 Tes validasi algoritma Palgunadi ................................................................. 21

4.1.1 Perhitungan manual VRP single product ............................................ 21

4.1.2 Perhitungan manual VRP multi product .............................................. 21

4.2 Tes efisiensi algoritma Palgunadi ................................................................ 24

4.2.1 Efisiensi VRP single product .............................................................. 24

4.2.2 Efisiensi VRP dua produk ................................................................... 26

4.2.3 Efisiensi VRP tiga produk ................................................................... 28

4.2.4 Efisiensi VRP infeasible condition single product .............................. 29

4.2.5 Efisiensi VRP infeasible condition dua produk ................................... 32

4.2.6 Efisiensi VRP infeasible condition tiga produk .................................. 35

4.3 Analisis kompleksitas waktu algoritma Palgunadi ....................................... 37

PENUTUP ............................................................................................................. 40

5.1 Kesimpulan ................................................................................................... 40

5.2 Saran ............................................................................................................. 40

DAFTAR PUSTAKA ............................................................................................ 41

Lampiran ............................................................................................................. 44

Lampiran 2. Hasil perhitungan manual VRP multi product .................................. 46

Lampiran 3. Hasil perhitungan aplikasi VRP single product ................................ 49

Lampiran 4. Hasil perhitungan aplikasi VRP multi product .................................. 58


commit to user xi

DAFTAR TABEL

Tabel 1. Keterangan demand masing-masing agen .............................................. 20 Tabel 2. Matriks jarak antar agen.......................................................................... 20 Tabel 3. Hasil perhitungan single product ............................................................ 25 Tabel 4. Hasil perhitungan dua produk ................................................................ 26 Tabel 5. Hasil perhitungan tiga produk ............................................................... 28 Tabel 6. Hasil perhitungan n agen dan running time kondisi infeasible satu produk ..... 29 Tabel 7. Hasil perhitungan n agen dan n vehicle kondisi infeasible satu produk ........... 31 Tabel 8. Hasil perhitungan n agen dan running time kondisi infeasible dua produk ..... 32 Tabel 9. Hasil perhitungan n agen dan vehicle kondisi infeasible dua produk .............. 34 Tabel 10. Hasil perhitungan n agen dan running time kondisi infeasible tiga produk ... 35 Tabel 11. Hasil perhitungan n agen dan vehicle kondisi infeasible tiga produk ............ 36


commit to user xii

DAFTAR GAMBAR

Gambar 1. Algoritma Palgunadi .......................................................................... 13 Gambar 2. Metodologi penelitian ......................................................................... 16 Gambar 3. Flowchart Algoritma Palgunadi ......................................................... 18 Gambar 4. Tampilan output awal aplikasi ........................................................... 22 Gambar 5. Output perhitungan VRP single product ............................................ 23 Gambar 6. Output perhitungan VRP multi product ............................................. 24 Gambar 7. Grafik hubungan n agen per running time .......................................... 25 Gambar 8. Grafik hubungan n agen per n vehicle ................................................ 26 Gambar 9. Grafik hubungan n agen per running time .......................................... 27 Gambar 10. Grafik hubungan n agen per n vehicle............................................... 27 Gambar 11. Grafik hubungan n agen per running time ....................................... 28 Gambar 12. Grafik hubungan n agen per n vehicle............................................... 29 Gambar 13. Grafik hubungan n agen per running time ....................................... 30 Gambar 14. Grafik hubungan n agen per n vehicle............................................... 32 Gambar 15. Grafik hubungan n agen per running time kondisi infeasible dua produk . 33 Gambar 16. Grafik hubungan n agen n vehicle kondisi infeasible dua produk ............. 34 Gambar 17. Grafik hubungan n agen per running time kondisi infeasible tiga produk . 36 Gambar 18. Grafik hubungan n agen per n vehicle kondisi infeasible tiga produk ....... 37


commit to user xiii

DAFTAR LAMPIRAN

Lampiran 1. Hasil perhitungan manual VRP single product ................................ 44 Lampiran 2. Hasil perhitungan manual VRP multi product ................................ 46 Lampiran 3. Hasil perhitungan aplikasi VRP single product .............................. 47 Lampiran 4. Hasil perhitungan aplikasi VRP multi product ................................ 58

implementasi algoritma palgunadi untuk …eprints.uns.ac.id/17533/1/cover.pdf ·...

Documents