perpustakaan.uns.ac.id
digilib.uns.ac.id
BAB II TINJAUAN PUSTAKA 2.1 Dasar Teori 2.1.1 Vehicle Routing Problem (VRP) Di dalam VRP setiap rute kendaraan dimulai pada depot, melayani semua pelanggan pada rute tersebut, dan kembali ke depot. Rute ini harus memenuhi semua constraint yang berkaitan dengan masalah: kapasitas kendaraan, time stamp, dll. Hal ini termasuk masalah logistik vehicle routing problem (VRP) yang tujuannya untuk meminimalkan jarak keseluruhan perjalanan dengan kendaraan sementara mampu melayani semua pelanggan (Moolman & Westhuizen, 2010). VRP atau Vehicle Routing Problem adalah sebuah cakupan masalah yang di dalamnya ada sebuah problem dimana ada sejumlah rute untuk sejumlah kendaraan yang berada pada satu atau lebih depot yang harus ditentukan jumlahnya agar tersebar secara geografis supaya bisa melayani konsumenkonsumen yang tersebar. Tujuan dari VRP adalah mengantarkan barang pada konsumen dengan biaya minimum melalui rute-rute kendaraan yang keluar-masuk depot (Moolman & Westhuizen, 2010). Dalam perkembangannya, VRP memiliki beberapa tipe dalam aplikasinya, antara lain: 1. Capacited Vehicle Routing Problem (CVRP), dengan faktor utama yaitu masing-masing kendaraan memiliki kapasitas tertentu. 2. Vehicle Routing Problem with Time Windows (VRPTW), merupakan jenis VRP dengan kendala kapasitas kendaraan dan batasan waktu (time windows) pada setiap pelanggan dan depot. 3. Multiple Depot Vehicle Routing Problem (MDVRP), merupakan jenis VRP yang memiliki banyak depot dalam melakukan pelayanan terhadap pelanggan. 4. Vehicle Routing Problem with Pick-Up and Delivering (VRPPD), dengan faktor utama yaitu pelanggan/customer dimungkin mengembalikan barang
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id 6
kepada agen asal. Penelitian (Montane & Galvao, 2006) menggunakan algoritma Tabu Search dimana VRP-SPD adalah salah satu variasi dari classical VRP. Pengiriman barang disuplai dari satu depot pada titik awal pengiriman, sementara pick-up muatan kemudian diambil untuk dikembalikan ke depot. Karakteristik dari VRP
SPD adalah bahwa
kendaraan yang digunakan pada suatu rute diisi oleh muatan barang yang dikirim dan muatan barang pick-up. 5. Split Delivery Vehicle Routing Problem (SDVRP), merupakan variasi dari capacitated vehicle routing problem (CVRP) dimana pelayanan terhadap pelanggan dilakukan dengan menggunakan kendaraan yang berbeda-beda. 6. Periodic Vehicle Routing Problem (PVRP), dengan faktor utama yaitu pengantaran hanya dilakukan di hari tertentu. Tujuan dari PVRP ini adalah untuk meminimalkan total jarak rute dan menyelesaikan permasalan penentuan jadwal pelayanan customer. Variasi dari semua VRP tersebut dapat digunakan sesuai dengan keadaan atau kondisi dari masalah yang dihadapi nantinya, tentunya dengan tujuan awal yang sama yaitu untuk meminimalkan total jarak tempuh untuk mendapatkan biaya transportasi yang minimum pula. 2.1.2 Vehicle Routing Problem Delivery and Pick-up (VRPDP) Vehicle Routing Problem with Delivery and Pick-up (VRPDP) adalah sebuah VRP dimana ada peluang kejadian pelanggan mengembalikan barang yang sudah diantarkan. Dalam VRPDP kita perlu memperhatikan bahwa barang yang dikembalikan dapat dimasukkan ke dalam kendaraan pengantar (Wassan & Nagy, 2014). Batasan ini membuat perencanaan pengantaran menjadi lebih sulit dan bisa berakibat pada penyalahgunaan kapasitas kendaraan, memperbesar jarak perjalanan atau kendaraan yang diperlukan lebih dari yang seharusnya. Maka, dalam situasi seperti ini biasanya kita harus memikirkan batasan keadaan dimana semua permintaan pengantaran dimulai dari depot dan semua permintaan pengambilan akan dibawa kembali ke depot, sehingga tidak ada pertukaran barang antar pelanggan. Alternatif lainnya adalah dengan memperbesar batasan
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id 7
bahwa semua pelanggan hanya dikunjungi satu kali atau dua kali jika demend dari pelangan melibihi capasitas kendaraan. Simplifikasi yang biasa terjadi lainnya adalah dengan memikirkan bahwa tiap kendaraan harus mengantarkan semua barang sebelum mengambil kembali barang dari pelanggan. VRPDP dapat dijabarkan sebagai berikut: -
Tujuan: Minimalisasi jumlah kednaraan dan total waktu perjalanan dengan
batasan bahwa kendaraan yang digunakan harus punya kapasitas yang cukup untuk mengantarkan barang ke pelanggan dan pengembalian barang ke depot -
Kelayakan: Solusi dibilang layak jika total kuantitas barang yang ditentukan
untuk tiap rute tidak melebihi kapasitas kendaraan yang melalui rute tersebut dan kendaraannya harus punya kapasitas yang cukup untuk mengantar dan mengambil barang dari pelanggan. 2.1.3 Model Matematika VRP Pendekatan umum (Boonkleaw, Arunya, Nanthi, & Srinon, 2009) untuk menyelesaikan VRP dapat dijelaskan ke dalam integer programming (IP), diberikan agen sebagai A= {0,1,2,...,m}, dan kendaraan yang tersedia di depot sebagai n, dan xi,j , menjadi fungsi yang menunjukkan kendaraan vi yang melayani agen j, i.e
dan xi,j , = 1 ketika kendaraan v melayani agen j
dan sebaliknya akan diset sebagai 0. Bahwa xi,j
= 1 berarti kendaraan vi
mengirim produk ke agen j. Di dalam clasical VRP, kita dapat meminimalisir jumlah kendaraan yang digunakan sehingga xi,j akan dimaksimalkan, dengan demikian fungsi dari classical VRP adalah sesuai constraint sebagai berikut :
Adapun syarat yang perlu diperhatikan, yakni syarat pertama adalah tidak ada satupun agen yang dilayani oleh dua atau lebih kendaraan, seperti constraint berikut :
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id 8
Kedua, adalah kendala demand yang harus dipenuhi sesuai dengan constraint berikut: 1. Panjang lintasan maksimum untuk masing-masing kendaraan vi adalah
m (sesuai banyaknya jumlah agen)
2. Total demand maksimum dari agen oleh kendaraan vi adalah Qi
3. Bounding integer variabels yang digunakan untuk menunjukkan bahwa agen dikunjungi atau tidak adalah sesuai dengan constraint berikut:
dimana : A = agen, nilai A = 0, ..., m j = agen tujuan, nilai j = 0, ..., m n = banyaknya kendaraan, nilai n = 1, ... , n = kendaraan i ,=
kendaraan
melayani agen j
= kapasitas maksimum kendaraan = total kendaraan yang akan dipakai = permintaan agen 2.1.4 Algoritma Tabu Search Tabu Search merupakan suatu metode pencarian lokal iteratif yang biasa digunakan dalam optimasi kombinatorial. Konsep Tabu Search yang digunakan dalam penelitian ini diadopsi dari (Glover & Laguna, 1997), yang terdiri atas tiga tahap: pencarian awal (preliminary search), intensifikasi dan diversifikasi. Pada tahap pencarian awal, algoritma Tabu Search menyerupai metode optimasi yang lain, di mana perbedaan utamanya hanyalah bahwa pada Tabu Search sebuah solusi dapat diterima meskipun kualitas dari solusi tersebut tidak lebih baik daripada solusi awal. Pada tahap intensifikasi dilakukan pergerakan
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id 9
atau pencarian solusi di area sekitar solusi yang telah ditemukan pada tahap pencarian awal, sedangkan tahap diversifikasi mencari solusi pada area-area baru (eksplorasi).
terjadinya cycling (kembali ke solusi awal), di mana beberapa pergerakan dinyatakan tabu atau tidak boleh dilakukan selama beberapa iterasi. Gerakangerakan yang tabu ini disimpan dalam daftar tabu atau tabu list. Dengan menggunakan tabu list, solusi yang tidak lebih baik dari solusi awal dapat diterima agar dapat menghindari kondisi terjebak dalam optimal lokal. Akan tetapi, dalam Tabu Search terdapat pula kondisi aspirasi (aspiration condition), di mana jika solusi dari gerakan yang terdapat pada tabu list merupakan solusi yang lebih baik dari semua solusi yang telah ditemukan, maka solusi ini akan diterima dan dibebaskan dari tabu list (Sitorus, Juwono, & Ciputra, 2014). 2.1.5 Algoritma Palgunadi Algoritma Palgunadi merupakan pengembangan dari algoritma Tabu Search. Penggunaan Algoritma Palgunadi sebagai algoritma baru penyelesaian masalah routing dikarenakan Algoritma Tabu Search menjadi tidak optimal apabila pada kasus yang sesungguhnya terdapat banyak customer yang terlibat karena mengakibatkan semakin besar pula ukuran tabu list. Iterasi untuk mencari solusi optimal juga semakin banyak, dan hal ini menyebabkan waktu perhitungan yang lebih lama. Tabu list yang terlalu kecil memungkinkan untuk terjadinya cycling, namun jika terlalu besar, maka Algoritma tidak dapat mengidentifikasi pencarian wilayah optimal lokal sehingga kemungkinan tidak menghasilkan solusi yang benar-benar optimal. Oleh karena itu diusulkan Algoritma Palgunadi sebagai solusi untuk menyelesaikan masalah routing dengan customer dalam jumlah besar (Sarngadi & Putri, 2014). Selain memperbaiki kelemahan Tabu Search dalam penyelesaian masalah
dalam
skala
besar,
diketahui
bahwa
algoritma
palgunadi
menghilangkan proses interchanges (realocate dan exchanges) yang dapat memakan waktu lama. Proses perhitungan Algoritma Palgunadi yang tidak melibatkan proses interchanges seperti pada algoritma Tabu Search ternyata
commit to user
perpustakaan.uns.ac.id
digilib.uns.ac.id 10
tetap dapat menghasilkan rute pengiriman yang optimal. Hal ini dikarenakan pada saat pencarian agen terdekat untuk dimasukkan ke dalam rute kendaraan pertama dan seterusnya, algoritma ini telah melakukan pencocokan dengan demand dan juga time windows dari masing-masing agen (Sarngadi & Putri, 2014). Algoritma Palgunadi dijelaskan dengan code pada Gambar 1.
Function minDemand 2. For i = 1 to n do 2.1 If (0 < di < D) then D = di 3. Return D Function nearestNeighbour (start, remainQ) {calculate the nearest next agent i to be processed} 2. For j = 1 to m do {
j > 0) and (remainQ > dj) and (dij < MinJarak) Then (MinJarak = j); i=j}
3. Return i
Input: number of agent demand agent distanace maximum capacity of vehicle Output:route each vehicle minimum number of vehicle Process: 1. i=1 2. repeat 3. route (i) = Ø 4. minD = minDemand ##dari semua agen yang belum dikunjungi 6. repeat 6.1 remainQ = Qi , start = 0 6.2 k = nearestNeighbour(start, remainQ) 6.3 if k > 0 then { remainQ = remainQ dk, dk = 0 start = k, route (i) = route (i) + k} 6.4 until (remainQ < minD) 7. i = i + 1 9. return (i
1)
Gambar 1. Algoritma Palgunadi
commit to user
2
Ika Ayu Fajarwati & Wiwik Anggraeni
Implementasi Algoritma Palgunadi Sebagai Algoritma Baru Dalam Optimalisasi Vehicle Routing Problem With Time Windows (VRPTW)
Sarngadi, Palgunadi & Putri, Elkagianda LA (2014)
1
Metode
Tujuan
DE menyempurnakan kekurangan dari algoritma evolusi lainnya dengan strategi optimasi sederhana untuk proses optimasi yang cepat (waktu perhitungan cepat dengan iterasi yang sedikit untuk menemukan optimal global solution). Metode ini merupakan evolusi dari Genetic Algorithm (GA) dengan mengganti operator logika dengan operator matematis
Algoritma Palgunadi memperbaiki algoritma Tabu Search, terbukti dapat menghemat total waktu perjalanan dan mengurangi jumlah customer yang pengirimannya mengalami keterlambatan.
Kelebihan
Tabel 1. Tabel Penelitian-Penelitian Terkait
Menggunakan Mengusulkan Algoritma algoritma Palgunadi Palgunadi sebagai algoritma baru untuk menyelesaikan VRPTW Penerapan Algoritma Differential Mengusulkan Differential Evolution algoritma Evolution untuk (DE). Diffential Penyelesaian Evolution (DE) Permasalahan sebagai Vehicle Routing algoritma baru Problem with untuk Delivery and Pick-up menyelesaikan VRPDP
Judul
Nama
No
2.2 Penelitian Terkait
Masih diterapkan untuk single product. Split delivery masih belum diperhatikan.
Masih diterapkan untuk single product. Split delivery masih belum diperhatikan.
Kekurangan
perpustakaan.uns.ac.id digilib.uns.ac.id
commit to user
commit to user
Penerapan Algoritma Tabu Search Vehicle Routing Problem Untuk Menyelesaikan
Fajar Eska Pradhana & Endang Sugiharti, dan Muhammad Kharis
5
Algoritma Tabu Search
Vehicle Routing Integer Linear Problem with Deliveries Programming and Pickups: Modelling (ILP) model Issues and Metaheuristics Solution Approaches
Niaz A. Wassan & Gábor Nagy
4
Algoritma Palgunadi
Metode
Algoritma Palgunadi Untuk Menyelesaikan Single Dan Multi Product Vehicle Routing Problem
Judul
Ika Tofika Rini, Sarngadi Palgunadi & Bambang Harjito
Nama
3
No
Bertujuan untuk menerapkan algoritma Tabu Search pada VRP
Mengusulkan algoritma Palgunadi sebagai algoritma baru untuk menyelesaikan Single and Multiple ProductVRP Menunjukkan model-model yang terdapat dalam VRP Delivery and Pick-Up
Tujuan
Mendapatkan solusi alternative untuk distribusi barang.
Menjelaskan model-model Delivery dan Pick-Up VRP lebih dalam, dengan single, multiple, combined product. Memberikan area baru untuk riset
Algoritma Palgunadi memperbaiki algoritma Tabu Search, terbukti dapat menghemat total jarak dan mengurangi jumlah armada untuk mengantarkan demend dr customer yang multiproduct
Kelebihan
Tabel 2. Tabel Penelitian-Penelitian Terkait (lanjut)
Run time terlalu lama.
Time Windows masih belim diperhatikan.
Time Windows masih belim diperhatikan.
Kekurangan
12
perpustakaan.uns.ac.id digilib.uns.ac.id
perpustakaan.uns.ac.id
2.3
digilib.uns.ac.id
Rencana Penelitian Penelitian ini akan membuat program simulasi penentukan rute distribusi
barang untuk meminimumkan biaya transportasi dengan cara meminimalkan total waktu tempuh dan jumlah kendaraan yang digunakan sebagai sarana pendistribusian pada kasus Vehicle Routing Problem Delivery and PickUp(VRPDP). Data untuk pengujian program adalah data distribusi yang kemudian akan dicocokkan dengan perhitungan manual dari Algoritma yang digunakan. Selain itu, digunakan pula data random untuk menguji sejauh mana Algoritma ini dapat digunakan. Algoritma yang digunakan adalah Algoritma Palgunadi.
commit to user
