Penyelesaian Vehicle Routing Problem with Time Window (VRPTW) Menggunakan Algoritma kelelawar SKRIPSI

SKRIPSI

ADLN - PERPUSTAKAAN UNIVERSITAS AIRLANGGA

Penyelesaian Vehicle Routing Problem with Time Window (VRPTW) Menggunakan Algoritma kelelawar

SKRIPSI

Amalia Ruspita Nabilla

PROGRAM STUDI S-1 MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS AIRLANGGA 2016

PENYELESAIAN VEHICLE ROUTING ...

AMALIA R NABILLA

SKRIPSI


Penyelesaian Vehicle Routing Problem with Time Window (VRPTW) menggunakan Algoritma kelelawar

SKRIPSI

Amalia Ruspita Nabilla 081112077

PROGRAM STUDI S-1 MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS AIRLANGGA 2016

i


AMALIA R NABILLA

SKRIPSI



AMALIA R NABILLA

SKRIPSI



AMALIA R NABILLA

SKRIPSI


PEDOMAN PENGGUNAAN SKRIPSI

Skripsi ini tidak dipublikasikan, namun tersedia

di perpustakaan dalam

lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seijin penulis dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah. Dokumen skripsi ini merupakan hak milik Universitas Airlangga.

iv


AMALIA R NABILLA

SKRIPSI



AMALIA R NABILLA

SKRIPSI


KATA PENGANTAR

AlhamdulillahirAbbilalamiin,

penulis

memanjatkan puji syukur

kehadirat Allah SWT pemilik seluruh alam yang melimpahkan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan skripsi yang berjudul “Penyelesaian Vehicle Routing Problem with Time Window (VRPTW) menggunakan

Algoritma

Kelelawar”.

Sholawat

dan

salam selalu

tercurahkan kepada junjungan kita Rasulullah SAW. Dalam penulisan skripsi ini penulis menyadari akan banyaknya bantuan, bimbingan, dan doa dari berbagai pihak. Secara khusus penulis berterima kasih kepada : 1. Universitas Airlangga yang telah memberikan kesempatan kepada Penulis untuk melanjutkan pendidikan tinggi. 2. Badrus Zaman, S.Kom., M.Cs selaku Ketua Departemen Matematika Fakultas Sains dan Teknologi Universitas Airlangga. 3. Dr. Eridani, M.Si selaku dosen wali selama penulis menuntut ilmu di perkuliahan. 4. Dr. Herry Suprajitno selaku dosen pembimbing I yang telah memberikan banyak waktu,saran dan bimbingan serta ilmu selama perkuliahan

vi


AMALIA R NABILLA

SKRIPSI


5. Auli Damayanti, S.Si,M.Si selaku dosen pembimbing II yang dengan sabar memberikan bimbingan dan pengarahan untuk kesuksesan penulis selama perkuliahan. 6. Bapak/Ibu dosen khususnya dosen Program Studi Matematika Universitas Airlangga atas segala ilmu, nasehat, pengalaman, dan kesabarannya yang telah diberikan selama penulis menuntut ilmu di perkuliahan. 7. Raswagiantoro dan Anik Sutjiati selaku orang tua kandung penulis yang luar biasa tiada henti memberi semangat, kepercayaan, dukungan, dan doa sebagai motivasi. 8. Aulia Ruspita Salsabillah yang selalu memberi semangat dalam tingkahnya yang jahil. 9. Uti dan seluruh keluarga yang selalu memberi dukungan baik secara moril maupun materi. 10. Mas Anang yang selalu menemani dan memberi motivasi untuk terus semangat dalam menyelesaikan skripsi. 11. Mbak Ninggar dan Muhammad Yan ( Cuta ) yang sangat berjasa dalam pembuatan skripsi. 12. Teman – teman seperjuangan saya untuk wisuda di bulan Maret 2016 Fajar (Judika), Hakim (dacil) , Aji (Gembel). 13. Teman-teman Septi, (Almarhuma) Ulfa, Cici, Cista, Ines, Inov, Shofi, Ratna, Asni, Yanti, Lista yang sangat membantu penulis dalam menyelesaikan skripsi.

vii


AMALIA R NABILLA

SKRIPSI


14. Teman-teman keluarga kampus Meiyin, Husnul, Haidar Fajar, Rendy, Brian, Danang, Tina atas bantuan, dukungan dan doa yang selalu diberikan kepada penulis 15. Teman-teman lama yang selalu menemani yaitu Arin, Rinda, Andini, Cepe, Dwiky, Ancha, Reza, Gilang, Rizky, Angga, Mas Iam, dan Pipit atas semua waktu dan banyaknya bantuan serta kesabaran yang diberikan kepada penulis. 16. Teman-teman kantin Mas Jono, Rizal (Ambon), Mas Raiesha, Mas Anto, Mada, Aditya ( Pikacu), Billi, dan teman-teman yang lain yang sering menemani dan mendukung saya dalam pembuatan skrips i 17. Mami dan Cak Priyo yang selalu memberikan tempat untuk menyelesaikan skripsi. 18. Teman-teman kuliah khususnya Matematika 2011 Universitas Airlangga atas semua kesempatan dan kebersamaan. 19. Dan seluruh pihak yang tidak dapat disebutkan satu persatu yang telah membantu menyelesaikan skripsi ini.

viii


AMALIA R NABILLA

SKRIPSI


Penulis menyadari bahwa skripsi ini masih terdapat kekurangan sehingga saran serta kritik yang membangun dari pembaca amat diharapkan oleh penulis demi penyempurnaan skripsi ini. Akhir kata, penulis berharap semoga skripsi ini dapat bermanfaat menambah informasi bagi pembaca pada umumnya serta khususnya bagi mahasiswa Program Studi Matematika Universitas Airlangga.

Surabaya, Januari 2016 Penulis,

Amalia Ruspita Nabilla

ix


AMALIA R NABILLA

SKRIPSI


Amalia Ruspita Nabilla, 2016, Penyelesaian Vehicle Routing Problem with Time Window (VRPTW) menggunakan Algoritma Kelelawar. Skripsi ini dibawah bimbingan Dr. Herry Suprajitno, M.Si dan Auli Damayanti, S.Si, M.Si. Departemen Matematika, Fakultas Sains dan Teknologi, Universitas Airlangga, Surabaya.

Abstrak Vehicle Routing Problem (VRP) adalah salah satu jenis masalah penentuan rute distribusi dimana terdapat sejumlah pelanggan yang dilayani oleh satu depot, rute pengiriman harus dimulai dan berakhir di depot, dan pengiriman dilakukan dengan beberapa kendaraan yang memiliki kapasitas tertentu. Semua permintaan pelanggan harus terpenuhi dan setiap pelanggan dilayani oleh satu kendaraan tepat satu kali. Vehicle Routing Problem with Time Window (VRPTW) adalah perluasan permasalahan dari VRP dengan tambahan time window di setiap pelanggan. Banyak sekali metode yang dapat diaplikasikan untuk mengerjakan VRPTW, demikian pula untuk skripsi ini, algoritma kelelawar digunakan untuk menyelesaikan vehicle routing problem with time window . Algoritma kelelawar adalah algoritma metaheuristik yang diinspirasi dari perilaku kelelawar yang memancarkan sonar ( gelombang suara ultrasonik) untuk mencari tau lokasi dan mangsa yang disebut ekolokasi. Algoritma kelelawar mempunyai dua parameter penting diantaranya pulse rate dan loudness pada setiap kelelawar. Jika pulse rate kurang dari hasil bilangan asli acak antara [0,1], itu akan mengakibatkan proses pencarian solusi lokal dipersekitaran solusi terbaik yang terpilih. Jika kebisingan lebih dari hasil bilangan asli acak antara [0,1] dan fungsi tujuan terbaru tidak lebih baik dari sebelumnya, itu akan menurunkan loudness dan menaikkan pulse rate. Program yang digunakan untuk menyelesaikan VRPTW dengan algoritma kelelawar adalah NetBeans dan diimplementasi menggunakan 3 contoh kasus, data kecil dengan 25 pelanggan dengan 25 kendaraan, data sedang 50 pelanggan dengan 25 dan 50 kendaraan dan data besar 100 pelanggan dengan 50 dan 100 kendaraan. Proses komputasi, memperoleh solusi terbaik dari setiap kasus. Kata Kunci : Algoritma Kelelawar, Vehicle Routing Problem (VRP), Vehicle Routing Problem with Time Window (VRPTW)

x PENYELESAIAN VEHICLE ROUTING ...

AMALIA R NABILLA

SKRIPSI


Amalia Ruspita Nabilla, 2016, Resolve Vehicle Routing Problem with Time Window (VRPTW) Use Of Bat Algorithm (BA). This final project was supervised by . Dr. Herry Suprajitno, M.Si dan Auli Damayanti, S.Si, M.Si. Mathematics Department, Faculty of Science and Technology, Airlangga University, Surabaya

Abstract Vehicle Routing Problem (VRP) is a problem in determination of vehicle’s route that employed to serve clients by utilising more than one vehicle to obtain a route with minimum possible distance without violating its capacity constraints. Vehicle Routing Problem with Time Window (VRPTW) is expansion from VRP with additional time window. Numerous methods have been applied to overcome VRPTW, and similarly in this undergraduate thesis, Bat Algorithm (BA) used to resolve vehicle routing problem with time window. BA is a metaheuristic algorithm inspired by behaviour of bat on emitting sonar (ultrasonic sound waves) to find out locations and prey called echolocation. BA has two important parameters including pulse rate and loudness on each bat. If the pulse rate below the value of real number [0,1] which obtained from randomization, it will process local search around the best chosen solution (personal best solution). If the loudness exceeding the value of real number [0,1] which obtained from randomization and the newest destination function is not better than previous one, it will lowering loudness and increasing pulse rate. VRPTW’s solution program using BA was built using NetBeans programming language and implemented on the two sample cases, a small data with 25 clients and 25 vehicles, a middle data with 50 clients and 25 and 50 vehicles and also a big data 100 clients and 50 and 100 vehicles. The computation processes obtain the best solution for each case are. Keywords : Bat Algorithm (BA), Vehicle Routing Problem (VRP), Vehicle Routing Problem with Time Window (VRPTW)

xi


AMALIA R NABILLA

SKRIPSI


DAFTAR ISI

Halaman LEMBAR JUDUL ................................................................................

i

LEMBAR PERNYATAAN…………………………………………..

ii

LEMBAR PENGESAHAN NASKAH SKRIPSI.................................

iii

LEMBAR PEDOMAN PENGGUNAAN SKRIPSI …………………

iv

SURAT PERNYATAAN ORISINALITAS …………………………

v

KATA PENGANTAR………………………………………………...

vi

ABSTRAK…………………………………………………………….

x

ABSTRACT…………………………………………………………...

xi

DAFTAR ISI…………………………………………………………..

xii

DAFTAR GAMBAR………………………………………………….

xv

DAFTAR TABEL …………………………………………………….

xvi

DAFTAR LAMPIRAN………………………………………………..

xviii

BAB I PENDAHULUAN 1.1 Latar Belakang .................................................................

1

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

4

1.3 Tujuan ...............................................................................

4

1.4 Manfaat .............................................................................

5

BAB II TINJAUAN PUSTAKA 2.1 Vehicle Routing Problem.................……………….........

6

2.2 Vehicle Routing Problem with Time Window...................

8

xii


AMALIA R NABILLA

SKRIPSI


2.3 Algoritma Kelelawar.........................................................

11

2.3.1 Ekolokasi.................................................................

12

2.3.2 Pergerakan Kelelawar (Movement of Bats).............

13

2.3.3 Pencarian Solusi Lokal ( Local Search ).................

14

2.3.4 Perubahan Kebisingan (Loudness) dan Pulse Rate.

14

2.3.5 Proses Algoritma Kelelawar....................................

16

BAB III METODE PENELITIAN .......................................................

17

BAB IV PEMBAHASAN ....................................................................

20

4.1 Vehicle Routing Problem with Time Window……………...

20

4.2 Algoritma Kelelawar Untuk Penyelesaian Vehicle Routing Problem with Time Window……………………….

21

4.2.1 Inisialisasi Parameter……………………………..

22

4.2.2 Input Data…………………………………………

23

4.2.3 Membangkitkan Solusi Awal……………………..

25

4.2.4 Menghitung Jarak Terpendek……………………..

27

4.2.5 Movement ………………………………………………

27

4.2.6 Local Search……………………………………………

29

4.2.7 Membandingkan Solusi, Mengupdate kebisingan dan pulse rate…………………………………………..

29

4.2.8 Menyimpan Solusi Terbaik……………………….

30

4.3 Data………………………………………………………

30

4.4 Penyelesaian Manual Contoh VRPTW dengan Algoritma Kelelawar………………………………………………...

31

xiii


AMALIA R NABILLA

SKRIPSI


4.5 Program…………………………………………………..

50

4.6 Implementasi Program Pada Contoh VRPTW…………..

51

4.6.1 Data 8 Pelanggan………………………………….

51

4.6.2 Data 25 Pelanggan ………………………………..

52

4.6.3 Data 50 Pelanggan ………………………………..

53

4.6.4 Data 100 Pelanggan ………………………………

55

BAB V KESIMPULAN DAN SARAN………………………...........

59

5.1 Kesimpulan……………………………………………….

59

5.2 Saran……………………………………………………...

60

DAFTAR PUSTAKA…………………………………………………

61

xiv PENYELESAIAN VEHICLE ROUTING ...

AMALIA R NABILLA

SKRIPSI


DAFTAR GAMBAR

Halaman Gambar 2.1. Ilustrasi dari VRPTW.......................................................

9

Gambar 4.1. Algoritma Kelelawar untuk VRPTW…………………...

22

Gambar 4.2. Inisialisasi Prameter…………………………………...

23

Gambar 4.3. Input Data Jarak……………………………………….

23

Gambar 4.4. Input Data Permintaan Pelanggan……………………....

24

Gambar 4.5. Input Data Waktu Pelayanan Pelanggan………………..

24

Gambar 4.6. Input Data Time Window Pelanggan……………………

24

Gambar 4.7. Membangkitkan Solusi Awal…………………………...

25

Gambar 4.8. Prosedur Transformasi Pengkodean Nilai ke Pengkodean Permutasi………………………………….

26

Gambar 4.9. Transformasi Urutan Pelanggan pada Rute…………….

27

Gambar 4.10. Prosedur Mencari Global Best…………………………

28

Gambar 4.11. Proses Movement……………………………………...

29

Gambar 4.12. Menyimpan Solusi Terbaik……………………………

30

xv


AMALIA R NABILLA

SKRIPSI


DAFTAR TABEL

Halaman Tabel 4.1. Posisi Awal……………………………………………......

32

Tabel 4.2. Kecepatan Awal…………………………………………...

32

Tabel 4.3. Pulse Rate dan Loudness…………………………………..

33

Tabel 4.4. Calon Rute ………………………...……………………....

33

Tabel 4.5. Rute Kelelawar 1…………………………………………..

36

Tabel 4.6. Rute Kelelawar 2…………………………………………..

36

Tabel 4.7. Rute Kelelawar 3……………...…………………………...

36

Tabel 4.8. Total Jarak dan Waktu tiap Kelelawar…………………….

37

Tabel 4.9. Nilai Beta…………………………………….…………….

38

Tabel 4.10. Nilai Frekuensi………………...…………………………

39

Tabel 4.11. Kecepatan Movement Kelelawar………………………...

40

Tabel 4.12. Posisi Movement Kelelawar ……………………………..

41

Tabel 4.13. Urutan Calon Rute Pelanggan dari Posisi Movement……

41

Tabel 4.14. Rute dan Posisi Movement Kelelawar 1…………………

42


42


42

Tabel 4.17. Nilai Acak i………………………………………………

43

Tabel 4.18. Nilai Epsilon……………………………………………...

44

Tabel 4.19. Posisi Local Search Kelelawar 1…………………………

45

Tabel 4.20. Posisi Baru………………………………………………..

46

xvi PENYELESAIAN VEHICLE ROUTING ...

AMALIA R NABILLA

SKRIPSI


Tabel 4.21. Calon Rute………………………………………………

46

Tabel 4.22. Rute Kelelawar 1…………………………………………

47


47


47

Tabel 4.25. Total Jarak dan Waktu Setiap Kelelawar………………...

48

Tabel 4.26. Solusi Update…………………………………………….

49

Tabel 4.27. Rute Terpendek…………………………………………..

50

Tabel 4.28. Jarak Terpendek 8 Pelanggan…………………………….

51

Tabel 4.29. Rute Terpendek 8 Pelanggan……………………………..

52

Tabel 4.30. Jarak Terpendek 25 Pelanggan…………………………

52

Tabel 4.31. Rute Terpendek 25 Pelanggan…………………………..

53

Tabel 4.32. Jarak Terpendek 50 Pelanggan………………………….

54

Tabel 4.33. Rute Terpendek 50 Pelanggan…………………………..

55

Tabel 4.34. Jarak Terpendek 100 Pelanggan…………..…………….

56

Tabel 4.35. Rute Terpendek 100 Pelanggan…………………………

57

xvii


AMALIA R NABILLA

SKRIPSI


DAFTAR LAMPIRAN

Halaman Lampiran 1 Flowchart…………………………………………………....

Lampiran 1

Lampiran 2 Prosedur Menghitung Jarak Terpendek………………..

Lampiran 2

Lampiran 3 Prosedur Local Search……………………………………..

Lampiran 3

Lampiran 4 Prosedur Membandingkan Solusi, Mengupdate Kebisingan dan Loudness………………………………….

Lampiran 4

Lampiran 5 Data 8 Pelanggan………………………………………

Lampiran 5

Lampiran 6 Data 25 Pelanggan……………………………………..

Lampiran 6

Lampiran 7 Data 50 Pelanggan……………………………………..

Lampiran 7

Lampiran 8 Data 100 Pelanggan……………………………………

Lampiran 8

Lampiran 9 Source Code Penyelesaian VRPTW menggunakan Algoritma Kelelawar…………………………………..

Lampiran 9

Lampiran 10 Output Program Fungsi Tujuan 8 Pelanggan…………

Lampiran 10

Lampiran 11 Output Program Fungsi Tujuan 25 Pelanggan………

Lampiran 11

Lampiran 12 Output Program Fungsi Tujuan 50 Pelangga n………

Lampiran 12

Lampiran 13 Output Program Fungsi Tujuan 100 Pelanggan………

Lampiran 13

xviii


AMALIA R NABILLA

Penyelesaian Vehicle Routing Problem with Time Window (VRPTW) Menggunakan Algoritma kelelawar SKRIPSI

Recommend Documents