BAB II TINJAUAN PUSTAKA
II.1. Vehicle Routing Problem II.1.1. Definisi VRP Vehicle routing problem (VRP) adalah istilah umum yang diberikan untuk permasalahan yang melibatkan rute kendaraan dengan berbasis depot yang melayani pelanggan yang tersebar dengan permintaan tertentu. Tujuan umum VRP adalah melayani sekumpulan pelanggan dengan ongkos operasi yang minimum. VRP adalah istilah umum yang dipakai banyak pihak. Beberapa ahli lain menggunakan nama berbeda, dengan permasalahan yang sama. Berikut ini adalah istilah VRP yang lain : vehicle scheduling problem (Clarke and Wright, 1964) dan vehicle dispatching (Dantzig Ramser, 1959). Perbedaan yang nyata antara defenisi routing problem dan scheduling problem diberikan oleh Bodin and Golden(1981) dalam Mahaputra (2006). Routing problem menekankan pada bagaimana membuat urutan mengunjungi pelanggan dengan kendaraan yang berangkat dan berakhir didepot (fasilitas sentral). Bila diberikan tambahan keterangan waktu seperti waktu keberangkatan dan waktu kedatangan maka permasalahan menjadi
scheduling
problems. VRP pertama kali dipelajari oleh Dantzig dan Ramser (1959) dalam bentuk rute dan penjadwalan truk. Clarke dan Wright (1964) kemudian melanjutkan penelitian ini dengan memperkenalkan istilah depot sebagai tempat keberangkatan dan kembalinya kendaraan. Clarke dan Wright mengunakan saving algorithm. Sejak saat itu penelitian VRP terus berkembang karena peran VRP yang penting dalam distribusi dunia industry. Perkembangan VRP meliputi pendekatan pemecahan masalah dan munculnya kendala-kendala baru. VRP dikenal sebagai permasalahan kombinatorial yang termasuk kategori NP-Hard yang berarti effort komputasi akan meningkat secara eksponensial seiring dengan meningkatnya ukuran permasalahan. Dengan demikian, metode yang tepat untuk permasalahan ini adalah algoritma heuristik. Algoritma ini memberikan solusi yang 13
baik dan cepat jika dibandingkan dengan penjelajahan seluruh ruang solusi dengan menggunakan metode enumerasi. VRP yang standar dapat dijelaskan sebagai berikut: terdapat sebuah depot dan beberapa pelanggan dengan lokasi dan permintaan yang diketahui. VRP bertujuan untuk menentukan beberapa rute yang meminimumkan fungsi tujuan dengan tetap memenuhi
seluruh
permintaan
pelanggan.
Sebuah
rute
mencakup
urutan
mengunjungi pelanggan dengan kendaraan yang berangkat dan berakhir di depot. Total permintaan semua pelanggan dalam satu rute tidak boleh melebihi kapasitas kendaraan yang digunakan. Setiap rute ditunjukan oleh satu kendaraan yang mengunjungi pelanggan sebanyak satu kali. Karena terdapat keterbatasan pada kapasitas kendaraan, VRP standar sering disebut dengan capacitated vehicle routing problem (CVRP). Secara umum fungsi tujuan dari permasalahan VRP adalah meminimumkan jumlah kendaraan yang digunakan dana memenimumkan total jarak tempuh kendaraan. Meminimumkan jumlah kendaraan biasanya diletakan sebagai fungsi tujuan yang utama baru kemudian meminimumkan jarak tempuh kendaraan. Fungsi tujun lain yang dapat ditambahkan adalah meminimumkan waktu penyelesaian untuk setiap kendaraan, maupun rentang waktu penyelesaian antar kendaraan, ataupun jenis fungsi tujuan lain sesuai kebutuhan dan karakteristik masing-masing kasus. Ilustrasi dari permasalahan VRP dapat dilihat pada gambar II.1. Misalnya, terdapat satu depot, sepuluh pelanggan, dan tiga kendaraan. Permasalahan yang muncul adalah penentuan rute kendaraan untuk mengunjungi pelanggan dengan memenuhi batasan yang ada (termasuk pemenuhan permintaan pelanggan) dan sekaligus meminimumkan biaya operasi total. Dengan menggunakan metode-metode pemecahan masalah rute kendaraan diperoleh seperti yang terlihat pada gambar II.1. Kendaraan pertama secara berurutan mengunjungi pelanggan 2,1, dan 9, lalu kembali ke depot. Kendaraan kedua secara berurutan mengunjungi pelanggan 3,5, dan 4 lalu kembali ke depot. Kendaraan tiga berangkat dari depot lalu secara berurutan mengunjungi pelanggan 8,10, 7, dan 6 lalu kembali kedepot.
14
Gambar II.1. Ilustrasi VRP II.1.2. Model Matematik VRP Rumus matematik untuk VRP dapat dinyatakan dalam rumusan yang berbasis traveling salesman problem (TSP) dan set partitioning problem (SPP). Rumusan pemrograman matematik ini sesuai untuk ukuran permasalahan yang kecil. Selain kelemahan yang disebutkan sebelumnya, rumusan matematik berbasis TSP memiliki kelemahan dalam menangani pembatas-pembatas tambahan yang biasanya muncul dalam praktek (seperti multiple trip, split delivery, dan sebagainya). Sebaliknya, keunggulan rumusan pemrograman matematik berbasis SPP adalah kemampuan untuk mengakomodasi pembatas-pembatas tambahan yang biasanya muncul dalam praktek. Tetapi, kelemahan rumusan pemrograman berbasis SPP ini terletak pada pembangkitan rute yang layak. Rumusan matematik VRP dasar berbasis TSP Suprayogi dan Yamato (2003) menyederhanakan perumusan VRP dasr berbasis TSP. Diketahui sebuah jaringan G = (N,L) dengan N menunjukan sekumpulan node N = {0,1,…,n} dan L= {(i,j); i,j∈ N, i≠j} menunjukan himpunan arc (link). Node O menunjukan depot dengan terdapat sejumlah NV kendaraan. Matriks jarak D = didefinisikan pada L. Jika dij = dij untuk semua (i,j), maka permasalahan dapat dikatakan simetri dan arc merepresentasikan busur yang tidak berarah (undirected arcs). Permintaan pelanggan i dinyatakan dengan qi dan jumlah permintaan pelanggan dalam satu rute tidak boleh melebihi kapasitas kendaraan Qk. Tujuan dari
15
VRP dasar ini adalah penentuan rute NV kendaraan yang memberikan jarak total minimal dengan setiap kendaraan berangkat dari depot dan kembali lagi ke depot. Formulasi model matematik untuk VRP dasar dapat dinyatakan sebagai berikut :
Min ∑∑∑ dij xijk i
j
(2-1)
k
Dengan pembatas:
∑∑ x i
ijk
= 1, untuk semua j
∑x
ijk
i
− ∑ x pjk = 0, untuk semua p, k
⎛
i
i
⎝
n
∑x
(2-3)
j
∑ q ⎜⎜ ∑ x
j =1
(2-2)
k
0 jk
ijk
j
⎞ ⎟ ≤ Qk , untuk semua k ⎟ ⎠
≤ 1 , untuk semua k
(2-4)
(2-5)
NV
yi − y j + n∑ xijk ≤ n − 1, i ≠ j, i ≠ 0, j ≠ 0
(2-6)
xijk ∈{0,1}, untuk semuai, j, k
(2-7)
y i arbitrary
(2-8)
k =1
Fungsi tujuan yang meminimumkan jarak total ditunjukan pada persamaan (2-1). Pembatas (2-2) menjamin bahwa setiap node hanya dilalui oleh satu kendaraan. Pembatas (2-3) menjamin bahwa kendaraan yang meninggalkan node i telah melayani node i tersebut. Pembatas kapasitas kendaraan dinyatakan dengan pertidaksamaan (2-4). Pembatas (2-5) menjamin bahwa kendaraan yang ditugaskan tidak melebihi NV kendaraan. Pembatas (2-6) berperan sebagai pembatas eliminasi subtur sehingga rute kendaran selalu dimulai dari depot dan berakhir di depot.
16
Rumusan matematik VRP dasar berbasis SPP Balinski dan Quandt (1964) merumuskan pemograman matematis berbasis SPP untuk VRP dasar. Rumusan berbasis SPP dinyatakan sebagai berikut: R menunjukan kumpulan kandidat rute lang layak. N menunjukan himupunan pelanggan yang yang dinyatakan dengan N
=
{1,…,n}. Air adalah konstanta yang bernilai 1 jika rute r
mencakup pelanggan I dan bernilai 0 jika rute r tidak mencakup pelanggan i. Biaya untuk rute r (gabungan dari biaya tetap dan biaya variable) dinyatakan dengan notasi cr dan xr adalah variable biner yang bernilai 1 jika rute r dipilih sebagai solusioptimal.
∑c x
Min
r∈R
r
r
(2-9)
dengan pembatas
∑A r∈R
ir
x r = 1, ∀i ∈ N
x r ∈ {0 ,1}, ∀ r ∈ R
(2-10) (2-11)
Fungsi tujuan (2-9) biaya total yang mencakup biaya tetap kendaraan dan biaya variabel berupa biaya perjalanan kendaraan. Pembatas (2-10) menamin bahwa tiap pelanggan hanya dikunjungi oleh satu kendaraan. pembatas (2-11) menunjukan batasan nilai variabel biner. Solusi yang optimal diperoleh dengan menyelesaikan formulasi SPP ini menggunakan integer programming solver. Himpunan rute yang layak dibangkitkan melalui enumerasi semua rute yang mungkin dari tiap subset himpunan pelanggan. Tiap rute yang dibangkitkan untuk tiap subset diperiksa kelayakannya terhadap pembatas kapasitas. II.1.3. Klasifikasi VRP VRP muncul dengan variasi bentuk yang tergantung pada sejumlah faktor, kendala, dan fungsi tujuan. Jenis VRP ada yang muncul dengan kendala jarak tempuh dan waktu tempuh, ada yang muncul dengan fungsi tujuan berupa total ongkos, waktu, jarak tempuh, ada juga yang muncul dengan kendala ketidaksimetrisan jarak atau
17
waktu tempuh, dan sebagainya. Suprayogi (2003) memberikan beberapa contoh varian dari VRP antara lain: •
Pelanggan punya rentang waktu layanan (VRP Time Windows: VRPTW)
•
Pelanggan dilayani oleh kendaraan berbeda (VRP Split Delivery: VRPSD)
•
Pelanggan terjadi proses pengambilan dan pengantaran produk (VRP PickUp anf Delivery: VRPPD)
•
Depot lebih dari satu (VRP Multiple Depots: VRPMD)
•
Permintaan pelanggan lebih dari satu produk (VRP Multiple Produk: VRPMP)
•
Kendaraan menempuh beberapa rute dengan kembali ke depot dahulu (VRP Mu;tiple Trips: VRPMT)
•
Kendaraan yang digunakan bermacam-macam dengan karakteristik yang berbeda pula (VRP Heterogeneous Fleet of Vehicles: VRPHFV)
•
Pelayanan kepada pelanggan dapat dilakukan dalam beberapa waktu horizon perencanan (Periodic VRP : PVRP)
•
Parameter angka (seperti jumlah pelanggan, permintaan masing-masing pelanggan, dan waktu layanan) bnersifat acak (Stochastic VRP: SVRP)
•
Pelanggan bersifat tidak tetap untuk masing-masing horizon waktu (Dynamic VRP: DVRP)
II.1.4. Fleet Mix Vehicle Routing Problem (FMVRP) II.1.4.1. Definisi FMVRP Fleet mix vehicle routing problem (FMVRP) adalah suatu kasus besar problem optimasi. Pada umumnya armada atau kendaraan yang digunakan untuk distribusi mempunyai ukuran kapasitas yang heterogen. (Montané dan Vianna, 2007) FMVRP merupakan salah satu varian dari vehicle routing problem (VRP) klasik. FMVRP berbeda dari VRP klasik, yang mana FMVRP mempunyai armada atau kendaraan yang heterogen, kapasitas kendaraan yang bervariasi, adanya fixed cost dan variable cost. FMVRP membentuk sekumpulan rute kendaraan, dimana setiap kendaraan mulai dan berakhir di depot, melayani pelanggan yang mempunyai permintaan tertentu dengan kendaraan atau armada yang heterogen. Masing-masing
18
pelanggan di kunjungi hanya sekali, dan total permintaan dari satu rute tidak melebihi kapasitas kendaraan yang ditugaskan. Biaya perajalanan (routing cost) kendaraan adalah jumlah dari fixed cost dan variable cost yang terjadi sebanding dengan jarak yang ditempuh. Tujuannya adalah untuk meminimasi total routing cost. Jumlah kendaraan diasumsikan tidak terbatas (Choi dan Tcha, 2007). Choi dan Tcha (2007) ada tiga versi VRPH yang telah dipelajari, pertama kali diperkenalkan oleh Golden et.al (1984), dimana variable cost adalah uniform untuk semua tipe kendaraan dengan jumlah kendaraan yang tersedia diasumsikan tidak terbatas untuk setiap tipe. Versi ini juga disebut fleet size and mix VRP, Golden et.al (1984) atau fleet size and composition VRP, Gheysen et.al (1986). Versi yang kedua mempertimbangkan variable cost yang tergantung pada tipe kendaraan, yang berbeda dengan versi yang pertama yang tidak mempertimbangkannya. Versi ini dikenal juga sebagai heterogeneous fleet vehicle routing problem (HVRP), Genderau et.al (1999), VFM with variable unit running costs, Salhi S et.al (1992) atau fleet mix VRP, Wassan dan Osman (2002). Versi yang terakhir disebut VRP with heterogeneous fleet of vehicles, Taillard (1996), atau the heterogeneous fixed fleet VRP, Tarantilis et.al (2004) yang merupakan generalisasi dari versi yang kedua dengan jumlah kendaraan untuk masing-masing tipe terbatas. Gambar II.2 berikut ini akan merupakan ilustrasi FMVRP. Misalkan terdapat satu depot, sepuluh pelanggan, dan tiga tipe kendaraan. Permasalahan yang muncul adalah penentuan rute kendaraan untuk masing-masing tipe yang mengunjungi pelanggan dengan memenuhi batasan-batasan yang ada (termasuk pemenuhan pelanggan) dan sekaligus meminimumkan total biaya operasi. Selain tujuan FMVRP untuk meminimumkan total biaya operasi juga tujuan utama lainnya adalah meminimumkan jumlah kendaraan untuk masing-masing tipe. Dengan menggunakan metode-metode pemecahan masalah diperoleh rute kendaraan seperti yang terlihat pada gambar II.2. kendaraan tipe pertama secara berurutan mengunjungi pelanggan 2, 1, 9, dan 8 lalu kembali ke depot. Kendaraan tipe kedua secara berurutan mengunjungi pelanggan 3, 5, dan 4 lalu kembali ke depot. Kendaraan tipe ketiga secara berurutan mengunjungi pelanggan 10, 7 dan 6 lalu kembali ke depot.
19
1
9
1 9 2
5
3 8
8
7
4 10
0
3
5 5 1
6 8
7
4
Gambar II.2. Ilustrasi FMVRP II.1.4.2. Model Matematik FMVRP. Rumusan pemograman matematis FMVRP diambil dari Gheysens et.al (1984) yang mana ada n pelanggan yang terletak pada lokasi yang berbeda-beda yang harus di layani oleh kendaraan dari depot. Depot dinotasikan dengan angka 0 dan lokasi pelanggan dinotasikan dengan i = 1,..., n. masukan berikut diasumsikan tersedia: T = jumlah dari tipe kendaraan Qk = kapasitas dari kendaraan tipe k (Q1 < Q2<...
⎧1 jika kendaraan tipe k melakukan perjalanan dai i ke j xijk = ⎨ ⎩0 otherwise yij = aliran barang dari i ke j sehingga FMVRP dapat dirumuskan sebagai berikut: T
n
k =1
j =1
T
n
n
Min ∑ f k ∑ x0k j + ∑∑∑ cij xijk
(2-12)
k =1 i = 0 j = 0
20
Dengan pembatas : T
n
∑∑ x
=1
k ij
k =1 i = 0 n
n
i =0
l =0
n
n
i =0
l =0
j = 1,..., n
∑ xijk − ∑ xkjl = 0 ∑ yij − ∑ y jl = d j T
y 0 j ≤ ∑ Qk x0k j
(2-13)
j = 0,..., n; k = 1,...,T
(2-14)
j = 1,..., n
(2-15)
j = 1,..., n
(2-16)
k =1
T
yij ≤ M ∑ xijk
i ≠ j = 0,..., n
(2-17)
yij ≥ 0
i ≠ j = 0,..., n
(2-18)
xijk ∈ {0,1}
i ≠ j = 0,..., n; k = 1,..., T
(2-19)
k =1
n
Sebagai catatan
∑x j =1
k 0j
menggambarkan jumlah total kendaraan dari tipe k yang
tercakup dalam armada tersebut. Fixed cost fk terjadi untuk masing-masing kendaraan, berikutnya menunjukan biaya perjalanan (2-12). Pembatas (2) dan (3) memastikan tepat hanya satu kali kendaraan masuk dan meninggalkan pelanggan. Persamaan (2-15) menunjukan pergerakan dari barang diasumsikan untuk semua permintaan konsumen harus tercukupi. Pembatas (2-16) menunjukan total load (muatan) dalam sekali perjalanan (trip) y0j tidak melebihi kapasitas kendaraan untuk masing-masing tipe. Persamaan (2-17) menyatakan tidak ada perjalanan barang dari i ke j jika tidak ada perjalanan kendaraan dari i ke j (yaitu jika x 0k j = 0 untuk semua k). M dalam jumlah yang besar sedemikian sehingga persamaan T
berlebihan jika
∑x k =1
k ij
(2-17) menjadi
= 1 . Sepesifikasi lengkap dari semua variabel xijk secara
simultan memperbaiki komposisi dan struktur rute kendaraan untuk setiap kendaraan dalam armada.
21
II.1.5. Vehicle Routing Problem with Multiple Products and Multiple Compartments VRP with multiple products and multiple compartments terjadi jika produk yang diantarkan terdiri atas lebih dari satu jenis produk yang harus disimpan dalam kendaraan dalam kompartemen yang berbeda (Christofides et.al, 1979). Misalkan terdapat satu set pelanggan X, depot x0, dan satu set kendaraan V. pelanggan xi mempunyai kebutuhan sebagai berikut: 1. Satu set Li, tipe produk yang berbeda yang akan diantarkan menggunakan kendaraan. Dengan tiap tipe produk (i,l), l = 1,...,Li diasosiasikan kuantitas qil dan sebuah label πi. 2. Waktu ui dibutuhkan untuk mengunjungi pelanggan dan untuk membongkar muatan. Kendaraan vk mempunyai karakteristik sebagai berikut: 1. Satu set kompartemen Hk untuk membawa produk. Dengan tiap kompartemen (k,h), h = 1,..., Hk diasosiasikan kapasitas Qkh dan label Πkh. 2. Aturan untuk menentukan apakah r buah
qi1l1,...,qirl r , dengan label
π i l1 ,...,π i l r dapat dimsukan atau tidak kedalam kompartemen dengan 1
r
kapasitas Qkh yang mempunyai label Πkh. r
Aturan ini tidak hanya membutuhkan bahwa
∑q j =1
i jl j
≤ Qkh tapi juga beberapa fungsi
f (π i1l 1 ,..., π ir l r , Π kh ) mempunyai nilai 0. Sebagai contoh, dalam pendistribusian barang yang harus dibekukan / frozen goods (l = 1) dan yang tidak dibekukan / nonfrozen goods (l = 2), dengan kendaraan yang mempunyai refrigerated compartments (h = 1) dan nonrefrigerated compartemens (h = 2), dapat dibuat πi1 = 1, πi2 = 2, ∀i dan = 1 Πk2 = 2, ∀k dengan fungsi
f (π i1l 1 ,..., π ir l r , Π kh ) = 0 jika dan hanya jika π i1l 1 = π i2l 2 = ... = Π kh . Contoh lainnya adalah, pada pendistribusian minyak dengan berbagai tipe, tipe-tipe minyak tersebut jelas tidak bisa dicampur, tapi bisa saja tidak perlu dipedulikan ke kompartemen yang mana tiap tipe tersebut dimasukan.
22
1. Jika kebutuhan/persyaratan pelanggan untuk tipe minyak yang sama dapat dicampur dalam kompartemen yang sama, tentukan π i jl sama dengan tipe j
minyak (ij, lj) dengan fungsi f (π i1l 1 ,..., π ir l r , Π kh ) = 0 jika dan hanya jika
π i l 1 = ... = π i l r . 1
r
2. Jika kebutuhan/persyaratan dari setiap pelanggan untuk setiap tipe minyak harus disimpan dalam kompartemen yang terpisah, tentukan π i jl sama j
dengan bilangan bulat (integer) yang berbeda dengan f (π i1l 1 ,..., π ir l r , Π kh ) = 0 jika dan hanya jika π i1l 1 = ... = π irl r . II.1.6. VRP Multiple Trips (VRPMT) II.1.6.1. Defenisi VRPMT Dalam VRP standar, satu kendaraan hanya dapat melayani satu rute dalam horizon perencanaan.
Vehicle
Routing
Problem
With
Multiple
Trips
(VRPMT)
memungkinkan satu kendaraan memiliki lebih dari satu rute selama horizon pencanaan. Dalam literatur, VRPMT sering disebut juga dengan vehicle routing problem with multiple use of vehicles. Kendaraan dapat berangkat dan pulang ke depot lebih dari satu siklus selama periode perencanaan. Kendala tambahan dapat berupa kendala maksimum total jarak tempuh atau maksimum waktu perjalanan kendaraan. VRPMT ini pernah diteliti oleh Taillard et.al. (1996), Brandao dan Mercer (1997), Zhao et.al. (2002) dalam Mahaputra (2006). Fagerholt (1999) dan Suprayogi et.al. (2001) membahas VRPMT dalam konteks ship routing dengan merumuskan permasalahan dalam bentuk set partitioning problem (SPP). Gambar II.3 berikut ini merupakan ilustrasi VRPMT. Misalnya, terdapat satu depot, sepuluh pelanggan, dan tiga kendaraan. Permasalahan yang muncul adalah penentuan rute kendaraan untuk mengunjungi pelanggan memenuhi batasan-batasan yang ada (termasuk pemenuhan permintaan pelanggan) dan sekaligus meminumumkan total biaya operasi. Selain itu, tujuan utama VRPMT adalah meminimumkan biaya operasi total. Selain itu, tujuan utama VRPMT adalah meminimumkan jumlah kendaraan sehingga satu kendaraan diperbolehkan memiliki lebih dari satu rute. Dengan menggunakan metode-metode pemecahan masalah diperoleh rute kendaraan seperti
23
yang terlihat pada gambar II.3. Kendaraan pertama secara berurutan mengunjungi pelanggan 2,1, dan 9, lalu kembali ke depot. Kendaraan kedua secara berurutan mengunjungi pelanggan 3, 5, dan 4 lalu kembali ke depot. Kendaraan ke tiga berangkat dari depot lalu secara berurutan mengunjungi pelanggan 8 dan 10 lalu kembali ke depot dan mengunjungi lagi pelanggan 7 dan 6 lalu kembali ke depot.
Gambar II.3. Ilustrasi VRPMT. II.1.6.2. Model Matematik VRPMT Rumusan matematik VRPMT berbasis TSP Rumusan matematis berbasis TSP yang diambil dari Zhao et.al (2002) dalam Mahaputra (2006) dapat dinyatakan sebagai berikut: n
n
n
n
n
n
Min ∑∑ x0 jkr + ∑∑∑∑ cij xijkr j =1 i =1
(2-20)
i = 0 j = 0 i =1 r =1
Dengan n = jumlah pelanggan, f = biaya tetap untuk tiap-tiap kendaraan, cij = biaya perjalanan dari pelanggan i ke pelanggan j. xijkr = 1 jika kendaraan k melakukan perjalanan dari pelanggan i ke pelanggan j pada rute r dan dan bernilai 0 jika sebaliknya. Batas atas dari k dan r adalah n. jadi, item pertama pada fungsi tujuan memberikan biaya tetap total dan item selanjutnya memberikan biaya variabel total. Tiap pelanggan hanya di kunjungi satu kali dan tiap kendaraan yang datang ke lokasi juga meninggalkan lokasi, ditunjukan dengan persamaan (2-21) dan (2-22)
24
n
n
n
∑∑∑ x i =0 k =1 r =1
ijkr
n
n
i =0
j =0
= 1 j = 1,..., n
∑ xipkr −∑ x pjkr = 0
(2-21)
p = 1,..., n, k = 1,..., n r = 1,..., n
(2-22)
Sebagai tambahan, muatan yang diangkut/ dibawa dalam satu rute tidak boleh melebihi kapasitas kendaraan dan waktu perjalanan total untuk tiap-tiap kendaraan pada satu tur tidak boleh melebihi durasi kerja yang ditentukan. Hal ini ditunjukan dengan pertidaksamaan (2-23) dan (2-24) n
n
i =0
j =0
∑ qii ∑ xijkr ≤ Q
k = 1,..., n r = 1,..., n
⎛ n n ⎞ ⎜ ∑∑ t ij xijkr ⎟ ≤ H ∑ ⎜ ⎟ i =0 ⎝ i =0 j =0 ⎠ n
(2-23)
k = 1,..., n
(2-24)
Dengan Q menunjukan kapasitas masing-masing kendaraan, qi menunjukan permintaan pelanggan, tij menunjukan waktu perjalanan dari pelanggan I ke pelanggan j (diasumsikan bahwa waktu perjalanan independen dengan jenis kendaraan), dan H adalaha durasi kerja untuk seua kendaraan. Selanjutnya pembatas eliminasi sub tur diberikan pada pertidaksamaan berikut ini: n
n
∑∑ x i∈B j∈B
ijkr
≤ [ B] − 1
B ⊆ N , [ B] ≥ 2
k = 1,..., n r = 1,..., n
(2-25)
Dengan N menunjukan set pelanggan dan |B| menunjukan jumlah pelanggan dalam subset B. Pembatas yang terakhir adalah yang mengacu pada variabel keputusan.
xijkr ∈{0,1} i = 1,..., n
j = 1,..., n k = 1,..., n
r = 1,..., n
(2-26)
Permasalahan yang sangat kompleks ini menunjukan bahwa pendekatan eksak tidak bisa
digunakan
untuk
menyelesaikan
permasalahan
ini
meskipun
ukuran
permasalahan kecil (Zhao et.al., 2002). Rumusan matematik VRPMT berbasis SPP Fagerholt (1999) dan Suprayogi et.al. (2001) merumuskan pemrograman matematis berbasis SPP untuk VRPMT. Rumusan berbasis SPP dinyatakan sebagai berikut: T menunjukan kumpulan kandidat tur yang layak dan mencakup tur dengan rute 25
tunggal dan mejemuk. N menunjukan himpunan pelanggan yang dinyatakan dengan N = {1,…,n}. Aij adalah konstanta yang bernilai 1 jika tur t mencakup pelanggan i dan bernilai 0 jika tur t tidak mencakup pelanggan i. Notasi cr merupakan biaya untuk tur t (gabungan dari biaya tetap dan biaya variabel) dan xr adalah variabel biner yang bernilai 1 jika tur t dipilih sebagai solusi optimal.
Min ∑ ct xt
(2-27)
t∈T
Dengan pembatas
∑A x t∈T
it
t
= 1,
x t ∈ {0 ,1},
∀i ∈ N ∀t ∈ T
(2-28) (2-29)
Fungsi tujuan (2-27) meminimumkan biaya total yang mencakup biaya tetap, kendaraan dan biaya variabel berupa biaya perjalanan kendaraan. Pembatas (2-28) menjamin bahwa setiap pelanggan hanya dikunjungi oleh satu kendaraan (tur). Pembatas (2-29) menunjukan batasan nilai dari variabel biner. Solusi yang optimal dapat diperoleh dengan menyelesaikan formulasi SPP ini menggunakan integer programming solver. Suprayogi et al. (2001) himpunan tur (rute tunggal maupun rute majemuk) yang layak dibangkitkan dengan melalui enumerasi semua tur yang mungkin dari subset himpunan pelanggan. Tiap tur yang dibangkitkan untuk tiap subset diperiksa kelayakannya terhadap pembatas kapasitas dan horizon perencanaan. II.1.7. Split Delivery Vehicle Routing Problem (SDVRP) II.1.7.1. Defenisi SDVRP VRP standar mengasumsikan bahwa tiap pelanggan hanya dilayani oleh satu kendaraan. Dalam split delivery routing, pengantaran kepada satu demand point dapat dibagi (split) oleh beberapa kendaraan. Walaupun terdapat relaksasi ini, masalah yang ada tetap sulit untuk diselesaikan. Dror dan Trudeau (1990) membahas permasalahan SDVRP dengan menganalisis penghematan (savings) yang terjadi dengan memperbolehkan adanya split dekivery pada VRP standar, walaupun dengan begitu akan menambah kompleksitas VRP. 26
Prosedur heuristik yang digunakan adalah k-split interchange (membagi demand pelanggan jika terdapat penghematan jarak) dan route addition (menambah rute untuk menghilangkan split delivery jika terdapat penghematan jarak). Menurut Dror dan Trudeau (1990), jika pelanggan-pelanggan mempunyai demand diatas 10% dari kapasitas kendaraan, penghematan yang signifikan akan didapatkan jika dilakukan split delivery. Ilustrasi SDVRP dapat dilihat pada gambar II.14. Misalkan terdapat satu depot, sepuluh pelanggan, dan tiga kendaraan. Permasalahan yang muncul adalah penentuan rute kendaraan untuk mengunjungi pelanggan dengan memenuhi batasan-batasan yang ada dan sekaligus meminimasi biaya operasi total. Setiap pelanggan tidak harus dikunjungi oleh satu kendaraan saja, dengan kata lain permintaan (demand) setiap pelanggan dapat diantarkan oleh lebih dari satu kendaraan. Dengan menggunakan metode-metode pemecahan masalah seperti metode optimal, heuristik, atau metaheuristik, rute kendaraan diperoleh seperti yang terlihat pada gambar II.4. Kendaraan pertama secara berurutan mengunjungi pelanggan 2, 1, 9, dan 10 lalu kembali ke depot. Kendaraan dua secara berurutan mengunjungi pelanggan 3,5 dan 4 lalu kembali ke depot. Kendaraan tiga berangkat dari depot lalu secara berurutan mengunjugi pelanggan 8, 10, 7, dan 6 lalu kembali ke depot. Terlihat bahwa pelanggan 10 dikunjungi dua kali oleh kendaraan satu dan kendaraan tiga (split delivery dilakukan terhadap demand pelanggan 10). 1
9
1 9 2
2 3 8
8
7
4
8
10
0
3
5
5
2
6 8
7
4
Gambar II.4. Ilustrasi SDVRP 27
II.1.7.2. Rumusan Matematik SDVRP Rumusan pemrograman metematis SDVRP yang diambil dari Dror dan Trudeau (1990) dapat dinyatakan sebagai berikut: Cij
= biaya perjalanan dari pelanggan i ke pelanggan j
di
= demand pelanggan i
Qv
= kapasitas kendaraan v
xvij
= 1 jika kendaraan v melakukan perjalanan dari pelanggan i ke pelanggan j dan bernilai 0 jika sebaliknya.
yij
= proporsi demand pelanggan i yang diantarkan oleh kendaraan v
NV
= jumlah kendaraan
S
= menunjukan himpunan semua siklus pada himpunan N, termasuk depot
(titik 0 menunjukan depot) n
n
NV
Min z s ∑∑∑ C ij xijv
(2-30)
i = 0 j = 0 v =1
Dengan pembatas NV n
∑∑ x v =1 i =0
v ij
≥ 1, untuk j = 0,1,..., n
n
n
i =0
j =0
(2-31)
∑ xipv − ∑ x vpj = 0, untuk p = 0,1,..., n; v = 1,2..., NV NV
∑y v =1
= 1, untuk i = 0,1,..., n;
iv
n
∑d y i =1
i
iv
(2-32)
(2-33)
≤ Qv , untuk v = 0,1,..., NV ;
(2-34)
n
yiv ≤ ∑ x vji , untuk i = 1,2,..., n; v = 1,2,..., NV
(2-35)
X∈S
(2-36)
xijv = 0,1, untuki = 0,1,...,n; j = 0,1,...,n; v = 1,2,..., NV
(2-37)
y iv ≥ 0 ,
(2-38)
j =0
untuk i = 1, 2 ,..., n ;
v = 1, 2 ,..., NV
28
Persamaan (2-30) menunjukan ongkos total yang dikeluarkan oleh armada kendaraan. Pembatas (2-31) memastikan bahwa setiap pelanggan akan mendapatkan setidaknya satu kali pengantaran
(bedakan dengan pembatas (2-2) pada VRP
standar, yang mensyaratkan setiap pelanggan hanya dilalui oleh satu kendaraan). Pembatas (2-32) memastikan bahwa kendaraan yang memasuki node i (termasuk depot) akan meninggalkan node tersebut. Pembatas (2-33) memastikan bahwa setiap pelanggan akan menerima kiriman demand seara penuh. Pembatas (2-34) memastikan bahwa penugasan pengiriman untuk setiap kendaraan tidak melebihi kapasitas kendaraan. Pelanggan i hanya bisa dilayani oleh kendaraan yang melalui pelanggan tersebut, hal ini dipastikan oleh pembatas (2-35). Pembatas (2-36) merupakan pembatas eliminasi subtur yang fungsinya memastikan bahwa rute kendaraan selalu berawal dan variabel xvij. Pembatas (2-38) adalah pembatas non negatif untuk variabel yiv. Berbeda dengan VRP standar, pada SDVRP ini rute kendaraan tidak hanya ditentukan oleh konfigurasi ruangnya saja, melainkan juga oleh kuantitas yang dikirimkan pada setiap node. Hal ini ditunjukan melalui pembatas (2-33) sampai (234). Pada VRP standart, rute hanya ditentukan oleh konfigurasi ruang saja, dikarenakan kuantitas yang dikirimkan pada setiap node ditentukan oleh parameter permasalahan demand tiap pelanggan, di. II.2. Ship Routing and Scheduling Vehicle routing and scheduling problem telah banyak dibahas dalam banyak literatur dan menjadi salah satu success stories dalam bidang management science atau operation research. Christiansen (1998b), ada beberapa alasan ketertarikan yang begitu besar terhadap masalah ini adalah: •
Transaportasi barang dan jasa adalah salah satu komponen biaya utama dalam berbagai sistem distribusi dan transportasi. Sebagai contoh, pengoperasian atau penyewaan kapal laut bisa menghabiskan biaya puluhan ribu US$ sehari, sehingga penentuan rute dan penjadwalan yang tepat dari armada kapal dapat menghasilkan penghematan yang besar.
•
Routing and scheduling problems merupakan masalah yang menarik dilihat dari sudut pandang teori optimasi. Masalah yang mendasarinya secara
29
konseptual sederhana, tetapi kompleks secara matematis dan menantang. Untuk menyelesaikan masalah yang rumit ini, formulasi dari masalah merupakan keperluan yang vital. Biasanya, formulasi masalah dan teknik solusi yang dipilih terkait erat satu sama lain. Christiansen (1998a), penghematan yang signifikan bisa dicapai dengan adanya penentuan rute dan penjadwalan armada kapal yang efisien. Ronen (1983) mengemukakan beberapa alasan mengapa ship routing and scheduling problem hanya mendapat sedikit perhatian. Salah satu alasan yang disebutkan adalah karena industri perkapalan sudah sejak lama sekali menentukan rute armadanya menggunakan cara manual. Industri ini tergolong konservatif dan tidak terbuka terhadap metode-metode baru yang berbasis optimasi. Alasan lain adalah karena penjadwalan
kapal
memiliki
varian
yang
lebih
banyak
dalam
struktur
permasalahannya maupun operating environments-nya dibandingkan penjadwalan kendaraan biasa, sehingga tailor-made systems sering diperlukan sebagai alat pendukung bagi pengambilan keputusan. Dalam merencanakan penjadwalan armadanya, banyak shipping companies yang tidak memakai bantuan computer based decision support system. II.2.1 Infrastuktur Jaringan Transportasi Produk Minyak Iakovou (1996) dalam Komara (2006), jaringan transportasi minyak di perairan laut merupakan sistem yang terdiri dari sekumpulan nodes dan links. Nodes
yang
dimaksud adalah pelabuhan-pelabuhan, import/export points, dan lightering zones. Pelabuhan dan import/export points masing-masing mempunyai supply dan demand dengan jumlah dan tipe produk minyak yang diterima dan dikirimkan berbeda satu sama lain. Hubungan (links) antar nodes merupakan jalur pelayaran tanker, terusan, dan coastal navigation channels. Produk minyak bisa dikategorikan menjadi minyak mentah (crude oil) dan produk petroleum. Produk petroleum yang berasal dari pemrosesan minyak mentah antara lain adalah bensin, minyak tanah (kerosin), distillate, residual fuel oil, lube oil & greases, petroleum jelly & waxes, naptha & solvents, aspal, tar & pitch, petroleum coke, liquid natural gas (LNG) dan non-classified petroleum products lainnya. Pengiriman produk minyak juga dibedakan berdasarkan kategori dan ukuran vessel.
30
Banyak perusahaan mengirimkan produk atau material mereka kepada konsumen, atau distribution center atau fasilitas manufaktur, dalam recurrent basis (berulang). Seringkali pengiriman tidak diinisiasi oleh adanya order dari lokasi penerima, melainkan pengirim harus menjadwalkan pengiriman agar lokasi penerima tidak mengalami kekurangan stok. Ini adalah kasus untuk produk (atau material) yang dikirimkan dalam volume besar (bulk atau semi-bulk), atau dalam kasus perusahaan harus menjaga tingkat persediaan tertentu. Banyak produk dikirimkan dengan cara seperti itu, termasuk produk minyak yang dikirim ke SPBU. Dengan metode pengiriman
seperti
itu,
keputusan
harus
dibuat
tidak
hanya
dengan
mempertimbangkan routing dan penjadwalan dari setiap kendaraan tapi juga mempertimbangkan kapan tiap lokasi pengiriman harus dikunjungi dan berapa banyak yang harus dikirim (Ronen, 2002). Pengangkutan dengan jumlah besar (bulk) dalam armada perdagangan dunia biasanya beroperasi dengan kapal dipenuhi barang antara loading dan discharging port, kemudian kapal tidak mengangkut barang (kapal kosong) hingga mencapai loading port selanjutnya. Biaya pengiriman ini ditetapkan dengan basis supply atau demand dan sangat bervariasi. Oleh karena itu, penjadwalan kapal yang tepat mempunyai potensi yang sangat besar untuk meningkatkan laba perusahaan dan performansi ekonomis pengiriman barang (Kim dan Lee, 1997). Douligeris et.al, (1997) dalam Komara (2006) kategori kapal yang digunakan untuk transportasi produk minyak di laut adalah sebagai berikut: 1. Tanker a. Kecil (kurang dari 19-foot draft) b. Medium (19 sampai 30-foot draft) c. Large (lebih besar daripada 30-foot draft) 2. Tanker barge ( kapal tongkang) a. Kecil (kurang dari 19-foot draft) b. Besar (lebih besar atau sama dengan 19-foot draft) Satu kapal tanker membutuhkan capital investment yang besar. Saat ini, banyak perusahaan minyak lebih suka menyewa tanker dari pada membangun sendiri. Pengadaan tanker membutuhkan biaya yang cukup besar karena spesifikasi tanker
31
harus memenuhi peraturan kelautan tertentu. Biaya pengoperasian satu kapal bisa mencapai ribuan US$ perhari. Oleh karenanya perbaikan dalam penentuan rute dan penjadwalan kapal dapat menghasilkan penghematan yang besar yang pada akhirnya akan memberikan peningkatan profit yang signifikan. Hal ini penting agar bisa bertahan dalam pasar yang semakin kompetitif. Biaya pelayaran terutama terdiri dari biaya bahan bakar yang tergantung pada ukuran kapal, kecepatan kapal, dan banyaknya kargo yang dibawa oleh kapal. Waktu yang dibutuhkan di pelabuhan tergantung pada kuantitas produk yang harus dimuat (loaded) atau di bongkar(discharge), dengan rata-rata memerlukan waktu satu hari. Menurut Ronen (1983) terdapat tiga metode operasi pelayaran yaitu: liner, tramp, dan industrial. Ketiga mode ini tidak didefenisikan secara jelas ataupun mutually exclusive. Satu kapal bisa ditransfer dari satu mode ke mode lainnya dan operator dapat mengoperasikan kapal dalam beberapa mode dalam waktu yang bersamaan. Linear operation menyerupai armada bus yaitu terdapat jadwal keberangkatan dan terjadi persaingan dalam mendapatkan kargo. Jadwal dari liner ships mempengaruhi demand terhadap jasa mereka (kargo yang didapatkan). Liners biasanya beroperasi dalam rute tertutup dan seringkali asal dan tujuan perjalanan tidak dapat didefenisikan karena kapal-kapal dapat memuat dan membongkar kargo di setiap pelabuhan yang dikunjungi dan kapal-kapal tesebut tidak pernah kosong. Tramp operation menyerupai armada taksi. Kapal dikirimkan ke tempat dimana kargo berada dan biasanya kapal tersebut penuh, dengan single origin dan satu atau dua tujuan. Liner dan tramp operation biasanya adalah maksimasi laba per satuan waktu. Industrial
operation
mirip
dengan
operasi
armada
truk.
Pemilik
kargo
mengendalikan armada kapal. Kapal-kapal tersebut bisa merupakan milik perusahaan itu sendiri atau perusahaan menyewa kapal (carter). Tujuan utama dari industrial operation ini adalah untuk menjamin pelayanan transportasi bagi perusahaan dan mereduksi biaya.
32
II.2.1.1. Jenis terminal Komara (2006) pola opeasi kapal, baik sebagai pengangkut minyak mentah maupun produk minyak adalah dari satu terminal loading menuju satu atau beberapa terminal discharging. Disamping itu, terdapat terminal yang difungsikan sebagai terminal transit (transhipment). Ciri pola distribusi minyak mentah adalah kapal bergerak dari sumur minyak (sebagai terminal loading) menuju ke tempat penyulingan minyak (refinery) atau menuju ke terminal transit. Sedangkan pada produk minyak, kapal bergerak dari refenery (terminal loading) menuju depot-depot penerima produk minyak. Untuk membantu distribusi produk minyak, dikenal juga terminal transit, terminal buffer, dan terminal backloading. Terminal buffer adalah terminal yang berfungsi untuk menjaga ketersediaan produk minyak secara nasional dengan cara mengimpor minyak. Sedangkan terminal backloading adalah terminal yang fungsinya sama dengan terminal transit, hanya saja kapasitas suplainya kecil. II.2.1.2. Pola distribusi minyak Komara (2006) ditinjau dari sebaran geografis permintaan minyak yang ada, pola transihipment dalam pendistribusian minyak tidak dapat dihindari. Gambar II.1 berikut ini menggambarkan pola distribusi minyak.
Gambar II.5. Pola Distribusi Minyak. Untuk berproduksi, pusat pengolahan minyak (kilang ) membutuhkan pasokan minyak mentah, sehingga ada aliran minyak mentah dari sumber minyak menuju
33
kilang. Minyak mentah yang telah diolah dari tempat penyulingan kemudian didistribusikan ke terminal transit atau langsung ke depo. Distribusi produk minyak juga dapat melalui buffer sebagai teminal loading menuju terminal transit atau langsung ke depo sebagai terminal discharging. Permintaan produk minyak dari tiap depo dapat juga dilayani dari terminal transit II.2.1.3. Karakteristik pelabuhan Dermaga dapat melayani 1 sampai n kapal bersamaan tergantung pada panjang dermaga, panjang pipa in dan out, panjang kapal, jarak antara pipa in-out satu dengan lainnya, atau dari data yang ada misalnya dermaga g pada pelabuhan h dapat melayani maksimal tiga kapal dengan bobot mati x DWT dan dengan panjang y, (Komara, 2006).
Gambar II.6. Kapal Bersandar pada Dermaga
II.2.1.4. Karakteristik loading dan discharging Pada gambar II.7 sampai dengan gambar II.10, diilustrasikan macam-macam proses loading dan discharging pada dermaga (Komara, 2006)
34
Gambar II.7. Proses Loading dan Discharging 1 Jenis Produk ke/dari r Tangki Kapal
Gambar II.8. Proses Loading dan Discharging 1 Jenis Produk ke/dari 1 Tangki Kapal Dalam Waktu Bersamaan
Gambar II.9. Proses Loading dan Discharging 1..N Jenis Produk ke/dari 1..N Tangki Kapal 35
Gambar II.10. Proses Loading dan Discharging 1..N Jenis Produk ke/dari 1..N Tangki Kapal dengan Pergerakan Kapal dari Satu Dermaga ke Drmaga lainnya Pada Pelabuhan yang Sama. II.2.1.5. Karakteristik Ship Routing Pada gambar II.11 sampai gambar II.14 diilustrasikan macam-macam karakteristik ship routing atau karakteristik distribusi produk minyak menggunakan tanker. Kondisi laden adalah kondisi kapal berlayar dengan mengangkut muatan penuh. Kondisi inballast adalah kondisi kapal berlayar tanpa muatan (Komara, 2006).
Gambar II.11. Perjalanan Kapal dengan Relasi One to One
36
Gambar II.12. Perjalanan Kapal dengan Relasi One to Many
Gambar II.13. Perjalanan Kapal dengan Relasi Many to One
Gambar II.14. Perjalanan Kapal dengan Relasi Many to Many II.2.2. Perbedaan antara standart vehicle routing and scheduling dengan ship routing and scheduling problem.
problem
Ronen (1983) menyebutkan perbedaan utama antara standart vehicle routing and scheduling problem dengan ship routing and scheduling problem yaitu:
37
1. Armada truk seringkali terdiri dari banyak truk yang identik, sedangkan kapal hampir selalu berbeda antara satu dengan yang lain baik itu dalam ukuran, kompartemenisasi, struktur biaya, dan karakteristik lainnya. 2. Marine routing problem seringkali melibatkan beberapa produk yang harus dikirimkan dalam kompartemen yang terpisah dalam satu kapal. Berbadea dengan package products yang dapat disimpan secara bersamaan dalam kompartemen yang sama. 3. Kapal-kapal yang ada mempunyai ukuran yang bervariasi dengan ukuran kompartemen yang berbeda. Ketika pengiriman terdiri lebih dari satu produk yang harus dimuat dalam satu kapal, jumlah produk harus disesuaikan agar sesuai dengan kompartemen yang tersedia. 4. Pelabuhan biasanya hanya mempunyai satu atau sedikit lokasi bongkar muat. 5. Waktu pengiriman biasanya lebih lama (dalam hitungan hari). 6. Permasalahan penjadwalan kapal memiliki tingkat ketidakpastian yang tinggi. Kapal mungkin mengalami keterlambatan karena masalah cuaca, kerusakan mesin, pemogokan di pelabuhan, dsb. Demand juga tidak diketahui dengan pasti. Sebagian informasi baru diketahui seiring berjalan waktu. Kebanyakan masalah penjadwalan diselesaikan menggunakan stattic procedures dan dilakukan rerun ketika terdapat update informasi. 7. Kapal tidak harus ke tempat asalnya. 8. Kapal beroperasi 24 jam, sedangkan truk biasanya tidak beroperasi diwaktu malam. 9. Tujuan kapal dapat berubah sewaktu-waktu ketika berada di laut. II.3. Algoritma Sequential Insertion Untuk membentuk solusi VRP, terdapat dua macam cara, yaitu menggabungkan rute yang ada dengan menggunakan criteria penghematan (saving criterion) dan mencoba secara berurutan memasukan pelanggan dalam rute kendaraan dengan menggunakan criteria biaya penyisipan (cost insertion) Laporte et.al.( 2000) dalam Komara (2006). Metode yang kedua telah terbukti menjadi metode yang popular digunakan untuk menyelesaikan permasalahan rute dan penjadwalan kendaraan (vehicle routing and scheduling problems) (Campbell dan savelsbergh, 2002). Algoritma ini membangun solusi yang layak yaitu sekumpulan rute yang layak dengan cara berulang kali mencoba memasukan pelanggan yang belum masuk dalam rute manapun ke dalam 38
bagian sementara dari rute yang terbentuk saat ini. Isu yang muncul pada algoritma ini adalah pemelihan pelanggan yang belum masuk dalam rute manapun untuk disisipkan dan pemilihan lokasi tempat penyisipan pelanggan. Algoritma heuristic insertion ini sangat terkenal sebab metode ini sangat cepat dalam memberikan solusi, mudah untuk diimplementasikan, dan mudah dikembangkan untuk menangani pembatas-pembatas yang sulit. Beberapa literature pernah menggunakan algoritma ini seperti Solomon (1987) dalam Mahaputra (2006) telah mengembangkan algoritma ini untuk untuk memecahkan VRPTW. Algoritma insertion ini sering dipilih untuk meghasilkan solusi awal yang layak pada LS dan metaheuristik untuk permasalahan rute dan penjadwalan kendaraan (vehicle routing and scheduling problems). Untuk menjelaskan algoritma insertion dasar, notasi-notasi yang digunakan didefenisikan terlebih dahulu. Missal, terdapat n pelanggan dan permintaan pelanggan i dinyatakan dengan qi. Campbell dan Savelsbergh (2002) mengasumsikan bahwa qi tidak melebihi kapasitas kendaraan Q dengan kendaraan memiliki kapasitas yang sama (homogeneous). Waktu perjalanan dari pelanggan i ke pelanggan j dinyatakan dengan tij dan diasumsikan tidak terdapat tambahan waktu pada saat pengiriman ke pelanggan selama waktu perjalanan. Sebuah rute didefenisikan sebagai perjalanan dari depot ke beberapa pelanggan secara berturutan dan kembali lagi ke depot. Sebuah rute dinyatakan dengan (0,1,2,…,j,…,n+1) dengan 0 dan n+1 meyatakan depot dan kendaraan akan melayani pelanggan i yang telah menduduki posisi j pada rute tersebut. Algoritma insertion didefenisikan sebagai metode untuk menyisipkan pelanggan yang belum masuk dalam rute, pelanggan i, diantara pelanggan j-1 dan j pada rute (0,1,2,…,j - 1, j,…, n + 1). Algoritma insertion terdiri dari dua macam yaitu algoritma parallel insertion dan sequential insertion. Algoritma parallel insertion pernah dibahas oleh Potvin dan Rousseau (1992) dalam Mahaputra (2006) untuk menyelesaikan VRPTW dengan beberapa rute dibangun sekaligus dalam waktu yang sama. Prinsip dasar dari algoritma ini adalah pertama-tama membentuk sejumlah rute. Selanjutnya, tiap pelanggan akan disisipkan pada posisi tertentu pada salah satu tur yang memberikan criteria terbaik, jika tidak dimungkinkan lagi terjadi penyisipan maka satu tambahan rute dibangkitkan. Algoritma behenti jika semua pelanggan telah ditugaskan. Potvin
39
dan Rousseau (1992) dalam Mahaputra (2006) rincian algoritma parallel insertion dapat dinyatakan sebagai berikut: N = kumpulan pelanggan yang belum ditugaskan R = satu set rute yang selalu berisi rute kosong. Dengan kata lain R menyatakan banyaknya rute yang ingin dibentuk. While N ≠ { } do P* =-∞ for i ∈ N do for i ∈ R do for (j-1, j) ∈ r do If feasible (i,j) and profit (i,j) > p * Then r* = r i* = i P*= profit (i,j) end if end for end for end for insert (i*,j*) N = N \ j* Update (r*) End while Pada algoritma sequential insertion, setiap rute harus dilengkapi terlebih dahulu sebelum membentuk rute baru. Algoritma ini pernah digunakan oleh Suprayogi dan Yamato (2003) dalam menyelesaikan VRPMTTW. Algoritma ini dikenal juga dengan nama push forward insertion heuristic (PFIH). Prinsip dasar dari algoritma sequential insertion adalah mencoba menyisipkan pelanggan diantara semua busur (edge) yang ada pada rute saat ini. Busur ini didefenisikan sebagai lintasan yang menghubungkan secara langsung satu lokasi dengan satu lokasi yang lain. Pada gambar II.15, pelanggan berikutnya dicoba untuk disisipkan pada busur 1 dan busur 2 yang ada pada rute saat ini
Gambar II.15. Penyisipan Pelanggan pada Rute Saat ini.
40
Kelayakan diperiksa untuk semua pembatas time window dan kapasitas muatan kendaraan. Pelanggan dan busur yang memberikan tambahan “biaya” yang paling kecil dan layak selanjutnya dipilih. Prosedur ini terus berulang hingga semua pelanggan telah ditugaskan. Algoritma sequential insertion memiliki kelebihan dibandingkan dengan parallel insertion (Suprayogi dan Yamato, 2002). Seperti yang pernah dinyatakan oleh Tung dan Pinnoi (2000) dalam Mahaputra (2006) , algoritma sequential insertion akan berusaha untuk menghasilkan jumlah kendaraan (tur) sekecil mungkin dengan memanfaatkan kapasitas kendaraan sebanyak mungkin. Hal ini sesuai dengan tujuan utama dari VRPMT atau VRPMTTW yaitu jumlah kendaraan diusahakan seminimum mungkin. II.4. Genetic Algorithm Dalam penelitiannya, Braysy (2001) menyebutkan bahwa GA pertama kali diperkenalkan oleh John Holland pada tahun 1975 setelah mengamati bahwa proses evolusi dapat dipakai sebagai analogi dari alam untuk persoalan optimasi di bidang teknik. Prinsip dan mekanisme evolusi disusun menjadi suatu algoritma program untuk diterapkan dalam software computer, yang diberinama GA. Goldberg (1989) dalam Mahaputra (2006) menyebutkan bahwa GA merupakan algoritma pencarian terstruktur yang didasarkan pada mekanisme seleksi alami dan informasi genetika alami. Algoritma ini mengkombinasikan struktur string yang paling baik dalam satu generasi dengan struktur yang berasal dari pertukaran informasi secara acak. Pada setiap generasi, suatu kumpulan dari individu disusun dengan menggunakan informasi dari individu unggul pada generasi sebelumnya. Ketika digunakan mekanisme acak, algoritma genetika bukanlah pencarian acak yang sederhana. Algoritma ini secara efisien mengeksploitasi informasi-informasi historis untuk kemudian menentukan titik pencarian solusi berikutnya dengan eksektasi dapat meningkatkan performansi. GA mengadaptasi mekanisme evolusi. Evolusi adalah proses yang bekerja pada kromosom-kromosom suatu mahluk hidup dari generasi ke generasi. Kromosom merupakan sekumpulan molekul besar yang mengkodekan struktur mahluk hidup.
41
Pada mahluk hidup biasanya terdapat lebih dari satu kromosom dan keseluruhan kromosom ini disebut genotip (genotype). Kromosom-kromosom ini menyusun protein asam amino yang ada dalam mahluk hidup yang merupakan pengatur dari segala macam proses kimiawi yang terjadi. Individu-individu yang ada pada saat tertentu dalam suatu populasi merupakan individu yang berhasil bertahan, sedangkan yang lemah akan punah. Individu-individu yang bertahan akan membentuk individu baru sehingga terjadi proses regenerasi. Individu-individu dalam suatu populasi dianalogikan sebagai suatu set solusi yang mungkin dari permasalahan optimasi. Setiap solusi memiliki nilai suaian (fitness) terhadap fungsi tujuan yang hendak dicapai. Semakin tinggi atau rendah nilai suaiannya (tergantung pada permasalahan minimasi atau maksimasi) maka solusi tersebut akan semakin mendekati solusi terbaik. Set solusi baru tersebut dibentuk berdasarkan informasi-informasi genetika yang bermanfaat dari set solusi yang mempunyai suaian tinggi. GA melakukan simulasi evolusi pada populasi kromosom. Seperti evolusi, algoritma ini menyelesaikan masalah pencarian kromosom yang baik dengan memanipulasi bagian yang terdapat dalam kromosom secara acak. Algoritma ini tidak mengetahui tipe permasalahan yang dihadapui. Informasi yang diberikan hanyalah evaluasi nilai suaian setiap kromosom. Informasi ini akan berpengaruh dalam pemilihan kromosom, sehingga kromosom yang mempunyai hasil evaluasi yang paling baik akan direproduksi lebih banyak dibandingkan dengan kromosom yang mempunyai hasil evaluasi yang buruk. Goldberg (1998) dalam Mahaputra (2006) menyebutkan bahwa ada tiga tipe untuk pencarian titik optimal : •
Calculus-based Metode ini berorientasi pada penyelesaian persamaan matematis untuk mencari titik ekstrim local. Ada dua jenis, yaitu metode langsung dan tidak langsung.
Metode
tidak
langsung
mencari
ekstrim
local
dengan
menyelesaikan beberapa pertidaksamaan matematis, sampai terjadi tingkat kemiringan nol untuk semua arah. Metode langsung berharap pada fungsi pertidaksamaan dan menggerakannya ke solusi sekitar yang memungkinkan 42
untuk mencapai optimal local. Kedua metode ini memiliki kelemahan, yaitu kedua metode ini hanya mencapai optimal lokal. Di samping itu, jika suatu nilai optimal lokal telah tercapai, unttuk mencari solusi yang lebih baik, dibutuhkan metode modifikasi solusi ekstrim baik berupa mengadaptasi aspek kerandoman, maupun dengan aturan-aturan tertentu. Permasalahan lainnya adalah metode ini sangat bergantung pada fungsi turunan dari fungsi utama. •
Enumerative Metode ini mencari nilai fungsi obyektif pada setiap poin dalam ruang solusi satu per satu. Algoritma ini cukup sederhana, tetapi kurang efisien terlebih untuk permasalahan riil dengan ruang solusi yang sangat besar.
•
Random Search Metode ini banyak menjadi perhatian akhir-akhir ini sejalan dengan berkembangnya penelitian di bidang algoritma, kecerdasan buatan, dan komputasi evolusioner. Menyadari kelemahan dua metode sebelumnya, berbagai variasi metode random search, baik berupa guided search hingga multiple points solution telah dikemukakan dalam berbagai penelitian yang pada akhirnya berkembang menjadi metode simulated annealing, GA, dan algoritma evolusioner lainnya.
GA memiliki perbedaan mendasar dibandingkan dengan metode pencarian solusi lainnya. Goldberg (1989) dalam Mahaputra (2006) menyebutkan perbedaan mendasar itu : 1. GA tidak bekerja secara langsung, tetapi bekerja dengan hasil kodifikasi solusi. Solusi beranalogi dengan sifat fisik mahluk hidup, sedangkan kodifikasi solusi beranalogi dengan pengkodean sifat fisik mahluk hidup, sedangkan kodifikasi solusi beranalogi dengan pengkodean sifat fisik ke dalam kromosom. Evolusi yang merupakan inti dari algoritma genetika bekerja dengan memanipulasi isi kromosom, dengan tidak memanipulasi sifat fisiknya secara langsung. Hal ini menyebabkan GA tidak dipengaruhi oleh persoalan yang dihadapi secara langsung. 2. GA menggunakan kumpulan solusi dalam melakukan pencarian. Hal ini berbeda dengan metode lainnya yang menggunakan hanya satu solusi untuk
43
melakukan solusi berikutnya untuk dievaluasi. GA mengikuti proses evolusi yang bekerja pada suatu populasi. Informasi genetika yang terkandung dalam populasi itu akan menentukan individu-individu baru dalam generasi selanjutnya. 3. GA bekerja dengan menggunakan informasi yang diperolehdari fungsi tujuan saja. Berbeda sekali dengan banyak metode konvensional yang biasanya menggunakan informasi lain berupa turunan, baik yang dihitung secara analitik ataupun numerik. Hal ini menyebabkan GA dapat diterapkan pada masalah-masalah yang melibatkan fungsi multimodal, non-linier, dan sebagainya. 4. GA menggunakan aturan transisi probabilistic, bukan deterministic. GA menggunakan mekanisme acak untuk mengeksplorasi ruang solusi. Karena perbedaaan yang mendasar tersebut, GA menjadi metode yang robust dan mempunyai kelebihan tersendiri dibanding metode-metode optimasi lainnya. Proses pengerjaan GA terdapat encoding (kodifikasi) dan decoding (dekodifikasi). Dalam melakukan encoding dan decoding tersebut, terdapat dua hal penting yang perlu diperhatikan yaitu : •
Kelayakan Kromosom Merupakan fenomena apakah solusi yang di-dekodifikasi dari sebuah kromosom terletak pada daerah yang layak untuk permasalahan tersebut. Tiap metode optimasi, baik metode konvensional maupun algoritma genetika, harus dapat mengakomodasi adanya kendala untuk tiap variabel, baik berupa persamaan atau pertidaksamaan
•
Legalitas kromosom Merupakan
fenomena
apakah
sebuah
kromosom
benar-benar
merepresantisakan sebuah solusi permasalahan. Kromosom illegal tidak dapat didekodifikasi menjadi solusi, sehingga kromosom tersebut tidak dapat dievaluasi. Teknik perbaikan biasanya digunakan untuk memperbaiki kromosom illegal menjadi legal agar ruang solusi tetap terbuka. Kodifikasi merupakan ciri penting dari GA. Ada beberapa bentuk kodifikasi yang sering digunakan:
44
•
String biner (0 dan 1), paling umum digunakan tetapi cukup sulit diterapkan pada kasus nyata karena kode biner bukanlah kode alami dari persoalan.
•
Bilangan riil (real number coding) untuk masalah optimasi berkendala.
•
Bilangan
bulat
(integer
number
coding)
untuk
masalah
optimasi
kombinatorial. Braysy (2001) dalam penelitiannya disebutkan bahwa walaupun secara teoritis dan secara umum, representasi kromosom jenis bit-string (1-0) cukup mampu mengakomodasi karakteristik GA, tetapi untuk permasalahan yang membahas tentang urutan, seperti permasalahan rute kendaraan (VRP), representasi kromosom integer akan lebih mudah serta lebih masuk akal. Faktor terbesar dalam teori evolusi yang menyebabkan suatu kromosom bertahan hidup, mati, melakukan persilangan, atau mengalami mutasi adalah lingkungan pada GA, faktor lingkungan ini direpresentasikan melalui fungsi tertentu sebagai evaluator. Fungsi tujuan adalah hubungan antara algoritma genetika dengan permasalahan yang akan dioptimasi. Fungsi inilah yang akan digunakan untuk mengevaluasi kromosom pada setiap generasi. Masukan, fungsi obyektif adalah kromosom dan keluarannya adalah suatu bilangan yang disebut fitness. Lebih lanjut dinyatakan bahwa, pada beberapa permasalahan berkendala digunakan fungsi suaian (fitness function) yang merupakan fungsi tujuan yang dimodifikasi sebagai evaluator dari kromosom. Fitness juga dapat digunakan untuk mengakomodasi prosedur penalti dan prosedur penanganan kendali lainnya. Operator yang digunakan dalam penyelesaian masalah dengan menggunakan GA terdiri dari 4 macam yaitu: •
Elitis : berfungsi untuk melakukan pemilihan individu yang akan mati untuk kemudian diganti oleh individu lainnya atau individu yang bertahan untuk kemudian diperbanyak
•
Migration: berperan untuk memindahkan individu-individu generasi sebelumnya dan membentuk subpopulasi baru yang diharapkan menghasilkan individu-individu baru yang lebih baik.
•
Crossover : berfungsi untuk menggabungkan dua string induk yang berbeda menjadi dua string anak yang berbeda dengan string induknya.
•
Mutasi : berperan dalam melakukan perubahan pada setiap kromosom dan gen didalammnya.
45
Algoritma migrasi pembagian populasi dibuat dalam suatu kumpulan subpopulasi dan dengan menentukan interval, membagi informasi diantara subpopulasi. Pei Hong, et.al (2006) memperkenalkan paramater dalam algoritma migrasi yaitu : conection topology (topologi yang dijelaskan dengan hubungan antara subpopulasi), migration policy, migration interval (parameter yang mengontrol seberapa sering migrasi terjadi), migration rate (parameter yang mengontrol berapa jumlah individu yang akan bermigrasi), dan population size (jumlah dari subpopulasi), dan lain-lain. Berikut adalah contoh the multi-population genetic algorithm with fixed migration interval and migration rates: Initialize the parameters; Generate N sub-population P1, P1,..., PN randomly; generation←1; while generation ≤ max_gen do for each sub-population Pi do use a fitness function to evaluate each individual in Pi; perform crossover in Pi; perform mutation in Pi; perform replacement in Pi; endfor generation← generation+1; if (generation % migration-intervall ==0) perform migration at the fixed migration rate; endwhile Pada Goldberg (1989) dalam Mahaputra (2006) disebutkan bahwa algoritma dasar dari GA bekerja sebagai berikut: Bentuk populasi awal (T=1) Evaluasi fitness masing-masing individu dari populasi awal Bentuk generasi berikutnya dengan mekanisme evolusi Mekanisme evolusi: Pilih dua individu dengan mekanisme seleksi. Jika keadaannya memungkinkan, crossover individu tersebut dan menghasilkan dua individu baru. Jika keadaanya memungkinkan, mutasikan kedua individu baru tersebut. Masukan individu baru ke dalam generasi baru. Ulanggi mekanisme evolusi sampai generasi baru terbentuk. Evaluasi generasi baru yang telah terbentuk. Ulangi pembentukan generasi baru sampai kriteria pemberhentian terpenuhi.
46
Gambar II.16 berikut ini menunjukan diagram alir dari GA
Gambar II.16. Diagram Alir GA
47
