i
PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN BEBERAPA METODE HEURISTIK KONSTRUKTIF
DEIBY TINEKE SALAKI
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
iii
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Juli 2009 Deiby Tineke Salaki NRP G551070031
iv
ABSTRACT
DEIBY TINEKE SALAKI. The Solution of Vehicle Routing Problem Using Some Constructive Heuristic Methods. Under supervision of AMRIL AMAN and FARIDA HANUM. The distribution of commodities or services can be viewed as a combinatorial optimization and application of graph theory named vehicle routing problem (VRP). The VRP, which is generalization of traveling salesman problem, can be described as the problem of designing least cost routes from depot to a set of costumers. The routes must be designed in such a way, that each costumer is visited only once by exactly one vehicle, started and ended at the depot. The VRP can be further complicated by associating time windows on visits, which is called VRP time windows (VRPTW). Because of the high complexity of the VRP and its wide applicability to various circumstances, heuristic method is more powerful to solve the problem than the exact one. The method is capable in performing a solution in a relatively limited running time, although it does not guarantee that the solution will be optimal. Most heuristic methods strategies involve finding an initial feasible solution by constructing a given route and then improving that solution. The aims of this research are (1) formulating model for the distribution of commodities as a VRPTW, (2) implementing the model on the delivery of “Sari Roti” bread to some stores, (3) solving the delivery problem using some heuristic methods, (4) comparing the output of each method based on running time and total of distribution distance. The distribution problem is modeled as VRPTW. The model is solved using heuristic method by means of ILOG Dispatcher software. In finding the solution, route construction method is applied by doing each saving, sweeping, nearest-to-depot, nearest addition, and insertion methods; and simultaneously performing route improvement using 2-opt, Or-opt, relocate, exchange and cross methods. Comparison of these methods, which is based on running time and distance on delivery of “Sari Roti” bread, shows that, the least route distance is given by the output of insertion method, the fastest running time is given by saving method. In contrast, the saving method yields the biggest route distance and the nearest-todepot produces the longest running time. Keywords: graph, combinatorial optimization, traveling salesman problem, vehicle routing problem, heuristic method
v
RINGKASAN
DEIBY TINEKE SALAKI. Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif. Dibimbing oleh AMRIL AMAN dan FARIDA HANUM. Pendistribusian barang atau jasa merupakan salah satu bagian penting dari kegiatan sebuah instansi pemerintah ataupun perusahaan tertentu, yang sering mengadakan pengambilan keputusan mengenai rute yang dapat mengoptimalkan biaya, waktu dan sumberdaya lain yang tersedia. Masalah ini dapat diformulasikan secara matematis sebagai sebuah Vehicle Routing Problem (VRP). VRP merupakan salah satu aplikasi dari teori graf dan optimasi kombinatorial yang mencakup penentuan sejumlah rute angkutan yang diawali dan diakhiri di suatu tempat yang disebut depot untuk mengantarkan barang kepada sekumpulan pelanggan sesuai permintaannya masing-masing. Rute yang terbentuk harus mengunjungi setiap pelanggan tepat satu kali dan menghabiskan biaya atau jarak tempuh seminimal mungkin. Salah satu variasi dari VRP adalah VRP time windows (VRPTW) yang menambahkan kendala batasan selang waktu tertentu (time windows) dalam melayani pelanggan. Selain dengan metode eksak, penyelesaian VRP, terutama yang berukuran besar dapat dilakukan dengan metode heuristik yang menentukan solusi secara cepat dari segi waktu komputasi meskipun solusi yang diperoleh belum tentu optimal. Metode heuristik dapat dibagi dalam tiga kelompok yaitu metode heuristik konstruktif (constructive heuristic), metode dua fase, dan metode perbaikan (improvement). Pada umumnya metode heuristik konstruktif dan metode perbaikan dilakukan secara bersamaan. Pada penelitian ini dilakukan formulasi masalah pendistribusian barang dalam bentuk VRPTW dan diimplementasikan pada masalah distribusi roti “Sari Roti”. Masalah tersebut selanjutnya diselesaikan dengan beberapa metode heuristik konstruktif. Rute yang diperoleh pada tahap konstruksi diperbaiki dengan metode perbaikan. Hasil masing-masing rute setelah perbaikan, selanjutnya dibandingkan berdasarkan waktu tempuh dan total jarak tempuh. Penelitian ini menggunakan software ILOG . Tahapan-tahapan metode heuristik yang digunakan adalah (1) penentuan rute fisibel awal dengan menggunakan 5 metode konstruksi yaitu saving, sweeping, nearest-to-depot, nearest addition, dan insertion, (2) memperbaiki rute yang diperoleh dari setiap metode konstruksi dengan menerapkan secara simultan 5 metode perbaikan rute yaitu metode 2-opt, metode Or-opt, metode relocate, metode exchange dan metode cross, (3) membandingkan hasil akhir perbaikan rute dari kelima metode berdasarkan total jarak tempuh dan waktu eksekusi. Hasil perbandingan lima metode heuristik konstruktif yang diterapkan pada data distribusi roti “Sari Roti” menunjukkan bahwa, jarak terkecil dari kegiatan distribusi diperoleh dari metode insertion dan jarak terbesar diperoleh dari metode saving, sebaliknya waktu eksekusi tercepat diperoleh dari metode saving dan paling lama pada metode nearest-to-depot.
vi
Total jarak tempuh distribusi dapat menjadi masukan bagi PT NIC (produsen “Sari Roti”) untuk memilih rute kendaraan guna meningkatkan efisiensi perusahaan sedangkan waktu eksekusi dapat menjadi masukan bagi pengembangan metode heuristik untuk masalah yang berukuran besar. Kata Kunci : graf, optimasi kombinatorial, traveling salesman problem, vehicle routing problem, metode heuristik
vii
@ Hak Cipta milik IPB, tahun 2009 Hak Cipta dilindungi Undang-Undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah. b. Pengutipan tidak merugikan kepentingan yang wajar IPB 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apa pun tanpa izin IPB.
viii
PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN BEBERAPA METODE HEURISTIK KONSTRUKTIF
DEIBY TINEKE SALAKI
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Departemen Matematika
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
ix
Judul Tesis Nama NRP
: Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif : Deiby Tineke Salaki : G551070031
Disetujui Komisi Pembimbing
Dra. Farida Hanum, M.Si.
Dr. Ir. Amril Aman, M.Sc. Ketua
Anggota
Diketahui Ketua Program Studi
Dekan Sekolah Pascasarjana
Matematika Terapan
Dr. Ir. Endar H. Nugrahani, M.S.
Prof. Dr. Ir. Khairil A. Notodiputro, M.S.
Tanggal Ujian: 6 Juli 2009
Tanggal Lulus:
x
Penguji Luar Komisi pada Ujian Tesis: Drs. Prapto Tri Supriyo, M.Kom.
xi
PRAKATA
Eben Haezer. Ya, (lagi dan lagi) sampai di sini, Tuhan menolong saya melewati satu tahapan penting dalam perjuangan hidup. Thanks God, for showing me Thy way and teaching me how to walk aright, more by faith and less by sight. Diawali dengan pemilihan topik pada bulan Januari 2009 sampai penyelesaian tesis ini yang diberi judul “Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif”, saya sangat didukung oleh sejumlah pihak. Bapak Amril Aman, Ph.D dan Ibu Farida Hanum, M.Si., pembimbing saya; serta Bapak Prapto Tri Supriyo, M.Kom. selaku penguji, terima kasih atas semua arahan, masukan, dan pengertiannya yang tak ternilai. Segenap civitas akademika Departemen Matematika IPB di almamater saya yang tak pernah terlupakan, terima kasih atas semua ilmu, teladan dan keramahannya. Terima kasih kepada teman-teman kuliah, kak Asmara teman seperjuangan, kepada Aji Raditya yang bersedia ‘meminjamkan’ datanya dan bersama Fariz yang memberi banyak masukan kepada saya; kepada ‘keluarga’ saya di Bogor: teman-teman kost (Deli, Yona, dan Alina) dan keluarga besar Bapak Rahmat di RM Palem Merah. Kepada GKI Pengadilan Bogor yang selalu menjadi ‘rumah’ bagi saya untuk ‘pulang’, terimakasih atas persekutuannya. Ucapan terimakasih juga disampaikan kepada pimpinan dan staf Yayasan Toyota & Astra atas kepercayaannya memberikan beasiswa. Last but not least, terima kasih kepada harta saya yang paling berharga: suami tercinta, Obrin Sualang atas pengertian, kasih sayang dan dukungannya; anakanak tersayang, Riemann, Ednayra dan my future daughter, yang selalu menyemangati saya dalam berjuang; orang tua dan keluarga besar di Pakuure dan Wioi yang selalu mendoakan saya. Terima kasih untuk semua pihak yang selama ini mendukung saya yang tidak dapat disebutkan satu per satu. Saya menerima segala kritik dan saran dari pembaca, karena saya sangat menyadari tulisan ini masih banyak kekurangan. Semoga tulisan ini bermanfaat dan menjadi inspirasi untuk penelitian selanjutnya. Bogor, Juli 2009 Deiby Tineke Salaki
xii
RIWAYAT HIDUP
Deiby Tineke Salaki, dilahirkan sebagai anak bungsu dari dua bersaudara di Amurang, Minahasa Selatan, Sulawesi Utara pada tanggal 17 Desember 1972 dari pasangan Liem Hou Ing dan Altje Fredika Wowor. Lulusan SMA Katolik Aquino Amurang tahun 1991 ini, diterima pada tahun yang sama di Program Studi Ilmu Kelautan, Fakultas Perikanan Unsrat Manado. Setahun kemudian penulis mendapat tugas belajar dari Universitas Sam Ratulangi Manado di Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam IPB dengan beasiswa EIUDP-CIDA dan TID dan lulus pada tahun 1998. Pada tahun 2007, diterima di Program Studi Matematika pada Sekolah Pascasarjana IPB. Selama menempuh jenjang S2, penulis menerima beasiswa dari Yayasan Toyota & Astra Indonesia dan bantuan penelitian dari Lembaga Penelitian Unsrat Manado. Penulis merupakan dosen pada Jurusan Matematika, FMIPA Universitas Sam Ratulangi Manado sejak tahun 2000 sampai sekarang. Pada tahun 2001, penulis menikah dengan Obrin Sualang dan dikaruniai seorang putra Riemann Janson Sualang (6 tahun), seorang putri Ednayra Marqliem Sualang (3 tahun) dan seorang calon bayi.
xiii
DAFTAR ISI
Halaman DAFTAR TABEL .....................................................................................
xv
DAFTAR GAMBAR ................................................................................
xvi
DAFTAR LAMPIRAN .............................................................................
xvii
1
2
3
4
PENDAHULUAN 1.1 Latar Belakang .............................................................................. 1.2 Tujuan Penelitian ........................................................................... 1.3 Manfaat Penelitian .........................................................................
1 3 3
TINJAUAN PUSTAKA 2.1 Graf ............................................................................................... 2.2 Optimasi Kombinatorial ................................................................ 2.3 Traveling Salesman Problem ......................................................... 2.4 Vehicle Routing Problem ............................................................... 2.5 Vehicle Routing Problem with Time Windows ................................
4 4 5 6 9
METODE HEURISTIK UNTUK VRPTW 3.1 Metode Heuristik ........................................................................... 3.2 Metode Heuristik Konstruktif ......................................................... 3.2.1 Metode Saving ................................................................... 3.2.2 Metode Sweeping ............................................................... 3.2.3 Metode Nearest-to-depot .................................................... 3.2.4 Metode Nearest Addition .................................................... 3.2.5 Metode Insertion ................................................................ 3.3 Metode Perbaikan .......................................................................... 3.3.1 Perbaikan dalam Rute ........................................................ 3.3.1.1 Metode 2-opt ................................................................ 3.3.1.2 Metode Or-opt ............................................................. 3.3.2 Perbaikan Antarrute ........................................................... 3.3.2.1 Metode Relocate ........................................................... 3.3.2.2 Metode Exchange ......................................................... 3.3.2.3 Metode Cross ...............................................................
12 12 12 14 15 16 18 19 19 19 20 21 21 22 22
PENYELESAIAN MASALAH DISTRIBUSI ROTI “SARI ROTI” 4.1 Data ............................................................................................... 4.2 Deskripsi Masalah ......................................................................... 4.3 Formulasi Masalah ........................................................................ 4.4 Hasil dan Pembahasan ................................................................... 4.4.1 Rute Kendaraan dengan Metode Saving .............................. 4.4.2 Rute Kendaraan dengan Metode Sweeping ......................... 4.4.3 Rute Kendaraan dengan Metode Nearest-to-depot ..............
24 24 26 28 29 31 32
xiv
4.4.4 Rute Kendaraan dengan Metode Nearest Addition .............. 4.4.5 Rute Kendaraan dengan Metode Insertion .......................... 4.4.6 Pembandingan Kelima Metode Heuristik Konstruktif..........
34 35 37
SIMPULAN DAN SARAN 5.1 Simpulan ....................................................................................... 5.2 Saran .............................................................................................
39 39
DAFTAR PUSTAKA ................................................................................
40
LAMPIRAN .............................................................................................
42
5
xv
DAFTAR TABEL
Halaman 1
Data pelanggan PT NIC .........................................................................
25
2
Rute kendaraan dengan metode saving ..................................................
29
3
Rute kendaraan dengan metode sweeping ..............................................
31
4
Rute kendaraan dengan metode nearest-to-depot ...................................
32
5
Rute kendaraan dengan metode nearest addition ...................................
34
6
Rute kendaraan dengan metode insertion ...............................................
35
7
Perbandingan hasil kelima metode konstruksi ........................................
37
8
Perbandingan jarak dan waktu eksekusi kelima metode konstruksi ........
37
xvi
DAFTAR GAMBAR Halaman 2.1
Contoh penyelesaian TSP ....................................................................
6
2.2
Contoh penyelesaian VRP 3 rute .........................................................
7
3.1
Contoh metode saving ..........................................................................
13
3.2
Contoh metode sweeping......................................................................
15
3.3
Contoh metode nearest-to-depot .........................................................
16
3.4
Contoh metode nearest addition ..........................................................
18
3.5
Contoh metode insertion .....................................................................
19
3.6
Contoh metode 2-opt ...........................................................................
20
3.7
Contoh metode Or-opt ........................................................................
21
3.8
Contoh metode relocate ......................................................................
22
3.9
Contoh metode exchange ....................................................................
22
3.10 Contoh metode cross ...........................................................................
23
4.1
Rute kendaraan dengan metode saving ................................................
30
4.2
Rute kendaraan dengan metode sweeping ............................................
32
4.3
Rute kendaraan dengan metode nearest-to-depot .................................
33
4.4
Rute kendaraan dengan metode nearest addition .................................
35
4.5
Rute kendaraan dengan metode insertion ............................................
36
4.6
Perbandingan waktu eksekusi dan total jarak tempuh kelima metode konstruksi ...........................................................................................
38
xvii
DAFTAR LAMPIRAN
Halaman 1
Matriks jarak antarlokasi .....................................................................
2
Program penentuan rute dengan metode saving menggunakan software
43
ILOG ..................................................................................................
44
3
Hasil penentuan rute dengan metode saving .........................................
47
4
Program penentuan rute dengan metode sweeping menggunakan software ILOG ..................................................................................................
49
5
Hasil penentuan rute dengan metode sweeping .....................................
52
6
Program penentuan rute dengan metode nearest-to-depot menggunakan software ILOG ....................................................................................
54
7
Hasil penentuan rute dengan metode nearest-to-depot ..........................
57
8
Program penentuan rute dengan metode nearest addition menggunakan software ILOG ....................................................................................
59
9
Hasil penentuan rute dengan metode nearest addition ..........................
62
10
Program penentuan rute dengan metode insertion menggunakan software
11
ILOG ..................................................................................................
64
Hasil penentuan rute dengan metode insertion......................................
67
