PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN MULTI - DEPOT VEHICLE ROUTING PROBLEM (MDVRP) SKRIPSI

ADLN – Perpustakaan Universitas Airlangga

PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN MULTI - DEPOT VEHICLE ROUTING PROBLEM (MDVRP)

SKRIPSI

FATIMATUS ZAHRO

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

SKRIPSI

PENERAPAN ALGORITMA CAT...

FATIMATUS ZAHRO


PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN MULTI - DEPOT VEHICLE ROUTING PROBLEM (MDVRP)

SKRIPSI

FATIMATUS ZAHRO 081211231114

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

SKRIPSI

i


FATIMATUS ZAHRO


SKRIPSI

ii


FATIMATUS ZAHRO


SKRIPSI

iii


FATIMATUS ZAHRO


PEDOMAN PENGGUNAAN SKRIPSI Skripsi ini tidak dipublikasikan, namun tersedia di perpustakaan dalam lingkungan Universitas Airlangga, diperkenankan untuk dipakai sebagai referensi kepustakaan, tetapi pengutipan harus seizin penulis dan harus menyebutkan sumbernya sesuai kebiasaan ilmiah. Dokumen skripsi ini merupakan hak milik Universitas Airlangga.

SKRIPSI

iv


FATIMATUS ZAHRO


SKRIPSI

v


FATIMATUS ZAHRO


KATA PENGANTAR

Puji syukur Alhamdulillah penulis panjatkan kehadirat Allah SWT, karena atas limpahan rahmat dan hidayah-Nya kepada penulis sehingga skripsi dengan judul

“Penerapan

Algoritma

Cat

Swarm

Optimization

(CSO)

untuk

Menyelesaikan Multi-Depot Vehicle Routing Problem (MDVRP)” dapat diselesaikan tepat pada waktunya. Ucapan terimakasih disampaikan kepada: 1. Universitas Airlangga yang telah memberi kesempatan bagi penulis untuk melanjutkan pendidikan tinggi khususnya program studi Matematika Fakultas Sains dan Teknologi yang telah memberikan banyak ilmu kepada penulis. 2. Bapak Presiden Republik Indonesia dan Direktorat Jendral Pendidikan Tinggi (DIKTI) yang telah mencanangkan program Beasiswa Bidikmisi yang telah memberikan kesempatan kepada penulis sehingga dapat merasakan indahnya bangku perkuliahan di Universitas Airlangga. 3. Badrus Zaman, S.Kom., selaku Ketua Departemen Matematika Fakultas Sains dan Teknologi Universitas Airlangga. 4. Auli Damayanti, S.Si., M.Si., selaku dosen wali dan dosen pembimbing II yang senantiasa penuh kesabaran, ketelitian dan keramahan dalam memberikan bimbingan berupa ilmu, arahan, waktu, serta semangat . 5. Dr. Herry Suprajitno, M.Si., selaku dosen pembimbing I, yang senantiasa penuh kesabaran, ketelitian dan keramahan dalam memberikan bimbingan berupa ilmu, arahan, waktu, semangat, serta masukan berupa kritik dan saran.

SKRIPSI

vi


FATIMATUS ZAHRO


6. Semua Bapak dan Ibu dosen Fakultas Sains dan Teknologi khususnya Prodi S1 Matematika Universitas Airlangga, terima kasih telah memberikan banyak ilmu serta nasehat semasa kuliah. 7. Yang tercinta kedua orang tua, Bapak M.As’ad Riady dan Ibu Nanik Mulyaningsih, serta seluruh keluarga besar penulis yang selalu memberikan dukungan, semangat, doa dan kasih sayangnya. 8. Teman-teman seperjuangan mahasiswa

Matematika 2012

Universitas

Airlangga atas dukungan dan kebersamaannya selama ini. 9.

Serta semua pihak yang tidak dapat disebutkan, yang telah membantu terselesainya skripsi ini. Penulis berharap semoga skripsi ini dapat bermanfaat untuk semua pihak

sebagai bahan pustaka dan penambah informasi khususnya bagi mahasiwa Universitas Airlangga. Tak ada gading yang tak retak, oleh karena itu penulis menyadari bahwa dalam penulisan proposal skripsi ini masih banyak kekurangan, sehingga saran dan kritik yang konstruktif sangat diharapkan agar skripsi ini bisa menjadi lebih baik lagi.

Surabaya, April 2016

Fatimatus Zahro

SKRIPSI

vii


FATIMATUS ZAHRO


Fatimatus Zahro, 2016, Penerapan Algoritma Cat Swarm Optimization (CSO) untuk menyelesaikan Multi-Depot Vehicle Routing Problem (MDVRP). 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 Penulisan skripsi ini bertujuan untuk menyelesaikan masalah Multi-Depot Vehicle Routing Problem dengan menggunakan algoritma Cat Swarm Optimization. Multi-Depot Vehicle Routing Problem (MDVRP) adalah suatu permasalahan dalam pembentukan rute untuk kendaraan yang digunakan melayani pelanggan yang berbasis pada suatu depot tertentu. Tujuan dari permasalahan ini adalah mendesain rute yang dapat meminimumkan jarak tempuh kendaraan untuk melayani pelanggan tanpa melanggar kendala kapasitas kendaraan dan kapasitas depot. Terdapat tiga tahapan dalam penyelesaian MDVRP yaitu grouping, routing, dan scheduling. Pada tahap grouping, pelanggan dikelompokkan tepat ke satu depot terdekat. Pada tahap routing, pelanggan pada masing-masing depot dibentuk kedalam rute pengiriman barang. Kemudian pada tahap scheduling, tahap ini merupakan tahap penjadwalan rute berdasarkan total jarak yang paling minimum. Algoritma CSO merupakan sebuah algoritma yang mengimitasi kebiasaan dari sekumpulan kucing dan model perilakunya untuk menyelesaikan permasalahan optimasi. Dalam algoritma CSO terdapat beberapa parameter yakni, parameter banyaknya kucing (m), seeking memory pool (smp), count dimension to change (cdc), seeking range dimension (srd), mixing ratio (mr), dan konstanta tracing (c). Program penyelesaian MDVRP menggunakan algoritma CSO dibuat dalam bahasa pemrograman C++ serta diimplementasikan pada tiga contoh kasus yaitu data kecil D01 dengan 4 depot dan 50 pelanggan, data sedang D02 dengan 5 depot dan 75 pelanggan, serta data besar D03 dengan 2 depot dan 100 pelanggan. Berdasarkan hasil implementasi didapatkan bahwa semakin besar maksimum iterasi maka solusi dari penyelesaian MDVRP semakin baik yaitu dengan total jarak tempuh minimum.

Kata Kunci : Cat Swarm Optimization, Vehicle Routing Problem (VRP), MultiDepot Vehicle Routing Problem (MDVRP)

SKRIPSI

viii


FATIMATUS ZAHRO


Fatimatus Zahro, 2016, Penerapan Algoritma Cat Swarm Optimization (CSO) untuk menyelesaikan Multi-Depot Vehicle Routing Problem (MDVRP). This final project was supervised by Dr. Herry Suprajitno, M.Si and Auli Damayanti, S.Si., M.Si. Mathhematics Departement, Faculty of Science and Technology, Airlangga University, Surabaya. ABSTRACT This thesis aims to solve the problem of Multi-Depot Vehicle Routing Problem (MDVRP) using Cat Swarm Optimization Algorithm. Multi-Depot Vehicle Routing Problem (MDVRP) is a problem in the formation of the vehicles used to serve customers who are based in a particular depot. The purpose of this problem is to designing route that can minimize the mileage of the vehicle to serve customers without violating vehicle capacity constraints and capacity depot. There are three phases to solve MDVRP i.e. grouping, routing, and scheduling. At the grouping phase, customers are grouped right to a nearest depot. In routing phase, customers at each depot formed into a delivery route. Then the scheduling phase, these scheduling based on the number of minimum distance. CSO is a algorithm which imitates habit of cats and model of behavior to solve the optimization problems. The CSO algorithm have several parameters there are amount of cats, seeking memory pool (smp), count dimension to change (cdc), seeking range dimension (srd), mixing ratio (mr), dan konstanta tracing (c). MDVRP solution program using CSO algorithm was built using C++ programming language and implemented on the three sample cases that is small data D01 with 4 depot and 50 customers, a medium data D02 with 5 depot and 75 customers, and also a big data D03 with 2 depot and 100 customers. Based on the results of the implementation it was obtained the higher maximum iteration result the better MDVRP solution as indicated by minimum travel distances.

Keyword: Cat Swarm Optimization, Vehicle Routing Problem (VRP), MultiDepot Vehicle Routing Problem (MDVRP)

SKRIPSI

ix


FATIMATUS ZAHRO


DAFTAR ISI Halaman LEMBAR JUDUL ..........................................................................................

i

LEMBAR PERNYATAAN ............................................................................

ii

LEMBAR PENGESAHAN NASKAH SKRIPSI ............................................ iii LEMBAR PEDOMAN PENGGUNAAN SKRIPSI ........................................ iv SURAT PERNYATAAN TENTANG ORISINALITAS .................................

v

KATA PENGANTAR .................................................................................... vi ABSTRAK ..................................................................................................... viii ABSTRACT ................................................................................................... ix DAFTAR ISI ..................................................................................................

x

DAFTAR GAMBAR ...................................................................................... xiii DAFTAR TABEL .......................................................................................... xv DAFTAR LAMPIRAN ................................................................................... xvii BAB I

BAB II

SKRIPSI

PENDAHULUAN ...........................................................................

1

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

1

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

4

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

4

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

5

1.5 Batasan Masalah ..........................................................................

5

TINJAUAN PUSTAKA ..................................................................

6

2.1 Pemrograman Linier (Linear Programming) .............................

6

2.2 Graph .......................................................................................

8

x


FATIMATUS ZAHRO


2.3 Vehicle Routing Problem (VRP)................................................ 11 2.4 Multi-Depot Vehicle Routing Problem (MDVRP) ..................... 13 2.5 Algoritma .................................................................................. 18 2.6 Pengkodean ............................................................................... 18 2.7 Nilai Fitness .............................................................................. 19 2.8 Seleksi Roulette Wheel .............................................................. 19 2.9 Algoritma Cat Swarm Optimization (CSO)................................ 20 2.9.1 Seeking Mode .................................................................. 22 2.9.2 Tracing Mode .................................................................. 24 2.10 Pemrograman C++ ..................................................................... 25 BAB III METODE PENELITIAN ................................................................ 28 BAB IV

PEMBAHASAN ............................................................................ 34 4.1 Multi-Depot Vehicle Routing Problem (MDVRP) ...................... 34 4.2 Cat Swarm Optimization (CSO) ................................................. 34 4.2.1 Input Data ......................................................................... 36 4.2.2 Inisialisasi Parameter ........................................................ 37 4.2.3 Grouping .......................................................................... 37 4.2.4 Membangkitkan Populasi dan Kecepatan Awal Kucing .... 39 4.2.5 Evaluasi Fungsi Tujuan ..................................................... 42 4.2.6 Menentukan xbest ............................................................. 44 4.2.7 Menentukan Self Position Considering ( ) ......................... 44 4.2.8 Penentuan Bendera (flag) .................................................. 45 4.2.9 Seeking Mode .................................................................... 47

SKRIPSI

xi


FATIMATUS ZAHRO


4.2.10 Tracing Mode.................................................................. 51 4.2.11 Penentuan Solusi Terbaik untuk Setiap Iterasi ................. 55 4.2.12 Menghitung Total Jarak Tempuh ..................................... 57 4.3 Data ........................................................................................... 57 4.4 Penyelesaian Contoh Kasus MDVRP Data D01M Manual ......... 59 4.5 Program ..................................................................................... 90 4.6 Implementasi Program Pada Contoh Kasus Multi-Depot Vehicle Routing Problem (MDVRP) ....................................................... 90 4.6.1 Implementasi Pada Data Berukuran Kecil (D01) ................ 91 4.6.2 Implementasi Pada Data Berukuran Sedang (D02) ............. 93 4.6.3 Implementasi Pada Data Berukuran Besar (D03) ................ 94 BAB V KESIMPULAN DAN SARAN........................................................... 97 5.1 Kesimpulan ............................................................................... 97 5.2 Saran .......................................................................................... 98 DAFTAR PUSTAKA ..................................................................................... 99 LAMPIRAN

SKRIPSI

xii


FATIMATUS ZAHRO


DAFTAR GAMBAR

Gambar

Judul

2.1 Contoh Graph

Halaman 9

2.2

𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣2 adalah walk

9

2.3

𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 adalah path

9

2.4

Cycle 𝑣1 − 𝑣2 − 𝑣3 − 𝑣1

10

2.5

Contoh Digraph

10

2.6

Contoh Graph Lengkap

11

2.7

Contoh Graph Berbobot

11

2.8

Contoh MDVRP dengan 2 depot dan 10 pelanggan

15

2.9

Langkah-langkah menyelesaikan MDVRP

16

4.1

Prosedur CSO untuk Menyelesaikan MDVRP

35

4.2

Prosedur Input Data

36

4.3

Prosedur Inisialisasi Parameter

37

4.4

Prosedur Grouping

38

4.5

Prosedur Membangkitkan Posisi Awal Kucing

39

4.6

Prosedur Membangkitkan Kecepatan Awal Kucing

40

4.7

Prosedur Transformasi Elemen Kucing i depot d

41

4.8

Prosedur Pembentukan Rute Awal Depot d

42

4.9

Prosedur Menghitung Fungsi Tujuan Kucing k Depot d

43

4.10 Prosedur Menentukan xbest Depot d

44

4.11 Prosedur Menentukan SPC Tiap Kucing

45

SKRIPSI

xiii


FATIMATUS ZAHRO


DAFTAR GAMBAR

Gambar

Judul

Halaman

4.12 Prosedur Penentuan flag Setiap Kucing Pada Depot d

46

4.13 Prosedur Seeking Mode

47

4.14

Prosedur Modifikasi Pada j-Tiruan Kucing Depot d

48

4.15 Prosedur Menghitung Probabilitas Terpilih (Pi)

49

4.16 Prosedur Roulette Wheel

50

4.17 Prosedur Menyimpan Solusi Terbaik Dari Seeking Mode

51

4.18 Memperbarui Kecepatan Pada Tracing Mode Depot d

52

4.19 Prosedur Memperbarui Posisi Pada Tracing Mode Depot d

53

4.20 Prosedur Perbandingan Fungsi Tujuan Baru dan Fungsi Tujuan Awal

54

4.21 Prosedur Menyimpan Solusi Terbaik Dari Tracing Mode

55

4.22 Prosedur Penentuan Solusi Terbaik untuk Setiap Iterasi

56

4.23 Prosedur Menghitung Total Jarak Tempuh

57

SKRIPSI

xiv


FATIMATUS ZAHRO


DAFTAR TABEL

Tabel

Judul

Halaman

4.1 Pengelompokan Pelanggan

61

4.2 Posisi Awal Kucing Depot 0

63

4.3 Kecepatan Awal Kucing Depot 0

63

4.4 Pengurutan Bilangan Acak Posisi Awal Kucing Depot 0

64

4.5 Pembentukan Rute dan Perhitungan Jarak Depot 0

66

4.6 Nilai Fungsi Tujuan Posisi Awal Kucing

67

4.7 SPC Populasi Awal

67

4.8 Random Bilangan Real Sebanyak Kucing

68

4.9 Pengurutan Bilangan Hasil Random

69

4.10 Penempatan Flag

69

4.11 Proses Pengcopyan Individu 3 Sebanyak smp-1 Kali

70

4.12 Penentuan Dimensi untuk Modifikasi Kucing 3 Copy 1

71

4.13 Hasil Modifikasi Kucing 3

73

4.14 Pengurutan Bilangan Hasil Modifikasi Kucing Tiruan 3

73

4.15 Pembentukan Rute dan Perhitungan Jarak (X3)

74

4.16 Nilai Fitness Kucing Tiruan 3

75

4.17 Probabilitas Terpilih dan Probabilitas Relatif Kucing Tiruan 3

75

4.18 Probabilitas Kumulatif Kucing Tiruan 3

76

4.19 Hasil Modifikasi Kucing Tiruan 4

78

SKRIPSI

xv


FATIMATUS ZAHRO


DAFTAR TABEL

Tabel

Judul

Halaman


78


79

4.22 Hasil Modifikasi Kucing Tiruan 1

80


81


82

4.25 Hasil Update Kecepatan dan Update Posisi

85

4.26 Pembentukan Rute dan Perhitungan Jarak X2 New

86

4.27 Pembentukan Rute dan Perhitungan Jarak X5 New

87

4.28 Hasil Running Program Pada Data D01

91

4.29 Solusi Terbaik Penyelesaian D01

92


93

4.31 Solusi Terbaik Penyelesaian D02

94


95

4.33

96

SKRIPSI

Solusi Terbaik Penyelesaian D03

xvi


FATIMATUS ZAHRO


DAFTAR LAMPIRAN

Tabel 1.

Judul Lampiran Flowchart Penerapan Algoritma Cat Swarm Optimization (CSO) Pada Multi-Depot Vehicle Routing Problem (MDVRP)

2.

Flowchart Grouping

3.

Data D01M (Data Manual)

4.

Data D01 (Data Kecil)

5.

Data D02 (Data Sedang)

6.

Data D03 (Data Besar)

7.

Source Code Program

8.

Output Program Penyelesaian D01

9.


10.


11.

User Interface Program

SKRIPSI

xvii


FATIMATUS ZAHRO

PENERAPAN ALGORITMA CAT SWARM OPTIMIZATION (CSO) UNTUK MENYELESAIKAN MULTI - DEPOT VEHICLE ROUTING PROBLEM (MDVRP) SKRIPSI

Recommend Documents