IMPLEMENTASI ALGORITMA CLARKE AND WRIGHT’S SAVINGS DALAM MENYELESAIKAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
SKRIPSI
DONNA DAMANIK 110803063
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
IMPLEMENTASI ALGORITMA CLARKE AND WRIGHT’S SAVINGS DALAM MENYELESAIKAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
DONNA DAMANIK 110803063
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2015
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: Implementasi Algoritma Clarke And Wright’s Savings Dalam Menyelesaikan Capacitated Vehicle Routing Problem (CVRP) : Skripsi : Donna Damanik : 110803063 : Sarjana (S1) Matematika : Matematika : Matematika Dan Ilmu Pengetahuan Alam (FMIPA) Universitas Sumatera Utara
Diluluskan di Medan, Juli 2015
Komisi Pembimbing: Pembimbing 2,
Pembimbing 1,
Dr. Syahriol Sitorus, M.IT NIP. 19710310 199703 1 004
Dr. Faigiziduhu Bu’ulolo, M.Si NIP. 19531218 1980003 1 003
Disetujui oleh: Departemen Matematika FMIPA USU Ketua,
Prof. Dr. Tulus, M.Si NIP. 19620901 198803 1 002 i Universitas Sumatera Utara
PERNYATAAN
IMPLEMENTASI ALGORITMA CLARKE AND WRIGHT’S SAVINGS DALAM MENYELESAIKAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Juli 2015
Donna Damanik 110803063
ii Universitas Sumatera Utara
PENGHARGAAN
Puji dan syukur penulis panjatkan kepada Allah SWT Yang Maha Pemurah dan Maha Penyayang, dengan limpahan karuniaNya penulis dapat menyelesaikan penyusunan skripsi ini dengan judul Implementasi Algoritma Clarke And Wright’s Savings dalam Menyelesaikan Capacitated Vehicle Routing Problem (CVRP). Terimakasih penulis sampaikan kepada Bapak Dr. Faigiziduhu Bu’ulolo, M.Si selaku dosen pembimbing 1 dan Bapak Dr. Syahriol Sitorus, M.IT selaku dosen pembimbing 2 yang telah meluangkan waktunya selama penulisan skripsi ini. Terimakasih kepada dosen pembanding penulis Bapak Drs. James Piter Marbun, M.Kom dan Bapak Dr. Suyanto, M.Kom atas saran dan kritik yang membangun dalam penulisan skripsi penulis. Terimakasih kepada Bapak Prof. Dr. Tulus, M.Si dan Ibu Dr. Mardiningsih, M.Si selaku Ketua dan Sekretaris Departemen Matematika FMIPA USU. Terimakasih kepada Bapak Dr. Sutarman, M.Sc selaku Dekan FMIPA USU, Pembantu Dekan FMIPA USU, seluruh Staff dan Dosen Matematika FMIPA USU, pegawai FMIPA USU serta rekan-rekan kuliah. Akhirnya tidak terlupakan kepada Ayahanda tercinta Alm Sugondo Damanik, Ibunda tercinta Katijah Purba, serta saudara penulis Zuhari Damanik serta keluarga yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Allah SWT akan membalasnya.
iii Universitas Sumatera Utara
IIMPLEMENTASI ALGORTIMA CLARKE AND WRIGHT’S SAVINGS DALAM MENYELESAIKAN CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
ABSTRAK
Model penentuan rute kendaraan umumnya dikenal sebagai Vehicle Rouitng Problem (VRP). VRP berkaitan dengan penentuan rute optimal untuk permasalahan yang melibatkan lebih dari satu kendaraan dengan kapasitas tertentu untuk melayani sejumlah pelanggan (konsumen) sesuai dengan permintaannya masing-masing. Capacitated vehicle routing problem (CVRP) adalah salah satu bentuk VRP dengan setiap kendaraan mempunyai kapasitas yang terbatas, kendaraan yang akan digunakan dalam permasalahan CVRP ini adalah kendaraan dengan kapasitas yang berbeda. Penentuan solusi menggunakan algoritma Clarke and Wright’s Savings. Algoritma ini memungkinkan diperolehnya suatu rute dengan mempertimbangkan kapasitas kendaraan dan permintaan masing-masing pelanggan. Data yang digunakan adalah jarak antar depot dengan pelanggan, jarak antar pelanggan, jumlah permintaan masing-masing pelanggan, dan kapasitas kendaraan. Pada penelitian ini dilakukan penyelesaian kasus CVRP dengan menggunakan algortima Clarke and Wright’s Savings. Dari hasil penyelesaian dengan menggunakan algortima Clarke and Wright’s Savings tersebut diperoleh 5 rute yang optimal dengan kapasitas kendaraan yang berbeda.
Kata kunci: Vehicle Routing Problem (VRP), Capacitated Vehicle Routing Problem (CVRP), algoritma Clarke and Wright’s Savings
iv Universitas Sumatera Utara
IMPLEMENTATION CLARKE AND WRIGHT’S SAVINGS ALGORITHM TO SOLVE CAPACITATED VEHICLE ROUTING PROBLEM (CVRP)
ABSTRACT
Model to choose vehicle route is known as Vehicle Routing Problem (VRP). VRP is related to optimal routing problem that involve more than one vehicle of each capacity to serve costumer’s demand. Capacitated Vehicle Routing Problem is one of VRP form which each of vehicle has finite capacity. Solution in this research use Clarke and Wright’s Savings Algorithm. This algorithm may get a route depand to vehicle capacity and customer’s demand. Data that use in this research is distance between source and customer, between each customer, customer’s demand and vehicle’s capacity. In this research, the resolution of CVRP by using Clarke and Wright’s Savings Algorithm. From the results of the solution by using Clarke and Wright’s Savings Algorithm obtained 5 optimal route with vehicles of different capacities.
Keyword: Vehicle Routing Problem (VRP), Capacitated Vehicle Routing Problem (CVRP), Clarke and Wright’s Savings Algorithm
v Universitas Sumatera Utara
DAFTAR ISI
Halaman i ii iii iv v vi viii ix x xi
PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR DAFTAR SINGKATAN DAFTAR LAMPIRAN BAB 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Tinjauan Pustaka 1.7 Metodologi Penelitian 1.7.1 Studi Literatur 1.7.2 Pengumpulan data 1.7.3 Pengolahan Data
1 1 2 2 3 3 3 6 6 6 6
BAB 2 LANDASAN TEORI 2.1 Teori Graf 2.1.1 Defenisi graf 2.1.2 Graf Terhubung (Connected Graph) 2.1.3 Graf Berbobot (Weighted Graph) 2.1.4 Graf Berarah (Directed Graph) 2.1.5 Graf Tidak Berarah (Undirected Graph) 2.2 Vehicle Routing Problem 2.3 Capacitated Vehicle Routing Problem (CVRP) 2.4 Algoritma Clarke and Wright’s Savings
7 7 7 7 8 8 9 9 13 14
BAB 3 HASIL DAN PEMBAHASAN 3.1 Contoh Kasus 3.1.1 Perumusan Fungsi Tujuan 3.1.2 Fungsi Kendala 3.1.3 Penyelesaian Contoh Kasus Capacitated Vehicle Routing Problem (CVRP) dengan Menggunakan Algoritma Clarke and Wright’s Savings
19 19 22 22
23
vi Universitas Sumatera Utara
BAB 4 KESIMPULAN DAN SARAN 4.1 Kesimpulan 4.2 Saran
37 37 38
DAFTAR PUSTAKA LAMPIRAN
39 40
vii Universitas Sumatera Utara
DAFTAR TABEL
Nomor
Judul
Halaman
Tabel 2.1
Bentuk Umum Matriks Jarak
15
2.2
Bentuk Umum Matriks Matriks Penghematan
17
3.1
Permintaan Masing-Masing Pengecer Resmi
19
3.2
Matriks Jarak Asal-Tujuan (km)
20
3.3
Matriks Penghematan
23
3.4
Iterasi 1: Pengelompokan Node Berdasarkan Matriks Penghematan
25
3.5
Iterasi 2: Pengelompokan Node Berdasarkan Matriks Penghematan
26
3.6
Iterasi 3: Pengelompokan Node Berdasarkan Matriks Penghematan
26
3.7
Iterasi 4: Pengelompokan Node Berdasarkan Matriks Penghematan
27
3.8
Iterasi 5: Pengelompokan Node Berdasarkan Matriks Penghematan
28
3.9
Iterasi 6: Pengelompokan Node Berdasarkan Matriks Penghematan
29
3.10
Iterasi 7: Pengelompokan Node Berdasarkan Matriks Penghematan
30
3.11
Iterasi 8: Pengelompokan Node Berdasarkan Matriks Penghematan
31
3.12
Iterasi 9: Pengelompokan Node Berdasarkan Matriks Penghematan
32
3.13
Iterasi 10: Pengelompokan Node Berdasarkan Matriks Penghematan
33
viii Universitas Sumatera Utara
DAFTAR GAMBAR
Nomor
Judul
Halaman
Gambar 2.1
Graf G
7
2.2
Graf Terhubung
8
2.3
Graf Berbobot
8
2.4
Graf Berarah
9
2.5
Graf Tidak Berarah
9
2.6
Ilustrasi Konsep Penghematan
16
2.7
Flowchart Pengerjaan Algoritma Clarke and Wright’ Savings
18
3.1
Rute yang Terbentuk Dari Matriks Jarak
20
3.2
Rute yang Terbentuk Dari Matriks Penghematan
24
3.3
Kendaraan Dengan Kapasitas Angkut yang Berbeda
24
3.4
Rute Optimal yang Dihasilkan
34
ix Universitas Sumatera Utara
DAFTAR SINGKATAN
VRP
= Vehicle Routing Problem
CVRP
= Capacitated Vehicle Routing Problem
x Universitas Sumatera Utara
DAFTAR LAMPIRAN
Nomor
Judul
1
Jadwal Penelitian
Halaman 40
xi Universitas Sumatera Utara
