Aplikasi Kombinatorial pada Vehicle Routing Problem Raden Prana A Jurusan Teknik Informatika ITB, Bandung, email:
[email protected]
Abstract – Makalah ini membahas tentang pengunaan kombinatorial dalam vehicle routing problem. Vehicle routing problem sendri adalah sebuah problem optimalisasi kombinatorial yang bertujuan untuk melayani beberapa pelanggan dengan sejumlah kendaraan. Tujuan utama dari VRP adalah meminimalisasi biaya yang keluar untuk proses pendistribusian barang. Banyak metode yang dapat dipakai untuk mencari solusi yang baik, tetapi untuk lingkup yang lebih besar, fungsi biaya untuk mencari nilai minimum global sangatlah kompleks. Dalam makalah ini, salah satu cara yang dipakai adalah dengan optimalisasi kombinatorial. Optimalisasi kombinatorial adalah cabang dari ilmu optimalisasi dalam aplikasi matematika dan ilmu komputer. Algoritma dari optimalisasi kombinatorial digunakan untuk menyelesaikan masalah yang cukup rumit dan memiliki ruang lingkup yang cukup besar. Algoritma optimalisasi kombinatorial menyelesaikan masalah tersebut dengan mengurangi ukuran efektif dari ruang lingkup yang digunakan dan dengan mengeksplorasi ruang lingkup secara efisien. VRP mempunyai beberapa variasi, antara lain: Capacitated VRP(CVRP), VRP with time windows(VRPTW), Multiple Depot VRP(MDVRP), VRP with Pick-Up and Delivering(VRPPD), Split Delivery VRP(SDVRP), Stochastic VRP(SVRP), dan Periodic VRP(PVRP).
Gambar 1 Masukan untuk VRP
Kata Kunci: VRP,optimalisasi kombinatorial, NPhard problem, aplikasi kombinatorial.
Gambar 2 Salah satu keluaran untuk masukan VRP sebelumnya
1. PENDAHULUAN 1.1 Apa itu VRP? 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 konsumen-konsumen yang tersebar. Tujuan dari VRP adalah mengantarkan barang pada konsumen dengan biaya minimum melalui rute-rute kendaraan yang keluar-masuk depot. Dua gambar berikut menunjukkan masukan yang biasa ada pada VRP dan salah satu kemungkinan keluaran yang ada:
VRP adalah sebuah problem pemrograman integer yang masuk kategori NP-Hard Problem, yang berarti usaha komputasi yang digunakan akan semakin sulit dan banyak seiring dengan meningkatnya ruang lingkup masalah. Untuk masalah-masalah seperti ini, biasanya yang dicari adalah aproksimasi solusi yang terdekat, karena solusi tersebut dapat dicari dengan cepat dan cukup akurat. Biasanya masalah ini terselesaikan dengan menggunakan berbagai variasi dari metode heuristik yang memerlukan sedikit pengamatan pada ruang lingkup masalah. 1.2 Optimalisasi Kombinatorial Optimalisasi kombinatorial adalah cabang dari ilmu optimalisasi dalam aplikasi matematika dan ilmu komputer yang umumnya berhubungan dengan operation research, teori algoritma dan teori kompleksitas komputasional yang berada pada
1
persilangan dengan beberapa ruang ilmu lainnya, seperti intelegensia buatan, matematika dan software engineeering. Algoritma dari optimalisasi kombinatorial digunakan untuk menyelesaikan masalah yang cukup rumit dan memiliki ruang lingkup yang cukup besar. Algoritma optimalisasi kombinatorial menyelesaikan masalah tersebut dengan mengurangi ukuran efektif dari ruang lingkup yang digunakan dan dengan mengeksplorasi ruang lingkup secara efisien. Pembelajaran akan teori kompleksitas komputasional membantu pertumbuhan optimalisasi kombinatroial. Algoritma optimalisasi kombinatorial biasanya ditujukan untuk masalah-maslah yang dianggap NPhard problems. Masalah-masalah tersebut umumnya dianggap tidak dapat dicari solusinya dengan efisien. Namun, beberapa aproksimasi dari teori kompleksitas menemukan bahwa untuk beberapa keadaan ruang lingkup, seperti ruang lingkup yang kecil, masalahmasalah tersebut dapat diselesaikan secara efisien. Penemuan ini terbukti dapat mempunyai kegunaankegunaan praktikal yang penting. 1.2..1 Definisi Informal Domain dari optimalisasi kombinatorial adalah masalah-masalah optimalisasi dimana sejumlah solusi yang ditawarkan adalah solusi yang diskrit atau dapat dijadikan diskrit, dan tujuannya adalah mencari solusi terbaik yang mungkin ada. 1.2.2 Definisi Formal Sebuah ruang dari masalah optimalisasi kombinatorial dapat dideskripsikan secara formal sebagi sebuah tuple (X,P,Y,f,extr) dimana X adalah ruang solusi(di dalamnya f dan P terdefinisi), P adalah predikat kelayakan, Y adalah himpunan dari solusi-solusi yang layak, f adalah fungsi objektif, dan extr adalah nilai ekstrimnya(bisa minimum atau maksimum). 1.3 Hubungan Antara Optimalisasi Kombinatorial dan Vehicle Routing Problem Apa hubungan antara VRP dan optimalisasi kombinatorial? Salah satunya adalah kenyataan bahwa VRP adalah NP-hard problem, dan optimalisasi kombinatorial memberikan cara untuk menyederhanakan NP-hard problems sehingga dapat dicari solusinya dengan efisien.
2. PEMBAHASAN 2.1 Mengenal VRP Lebih Lanjut VRP adalah sebuah problem kombinatorial yang terletak pada irisan dua masalah yang sudah dikenal, yaitu: • Travelling Salesman Problem(TSP) Jika kapasitas dari kendaraan C tak terhingga,
maka kita bisa mendapatkan sebuah keadaan untuk Multiple Travelling Salesman Problem (MTSP). Sebuah keadaan MTSP dapat diubah menjadi keadaan TSP yang ekuivalen dengan cara menyambungkan salinan dari node 0 dari graf k-1 (dengan k adalah jumlah rute) dan ujung-ujung perpotongannya (tidak ada sisi diantara titik-titik depot sejumlah k). • Bin Packing Problem(BPP) Pertanyaannya adalah apakah ada solusi yang mungkin utnuk sebuah keadaan VRP dimisalkan keadaan itu adalah sebuah keadaan BPP. Penyelesaian dari masalah ini sama secara konseptual dengan pemodelan VRP dimana semua biaya pada sisi dianggap nol, sehingga semua solusi memiliki biaya yang sama. Maka, kita bisa menganggap bahwa VRP dpat ditransformasi dengan cara: • Transformasi pertama dengan cara memperluas dasar prinsip pengepakan struktur BPP • Transformasi kedua dengan berlandaskan dasar perutean pada struktur TSP. Sebuah solusi yang ‘layak’ untuk masalah secara keseluruhan adalah sebuah graf TSP (dalam graf yang sudah diperluas) yang juga memenuhi batasan pemuatan (contoh, permintaan total untuk k segmen untuk beberapa depot yang tergabung tidak boleh melebihi C atau kapasitas total). Dikarenakan penggunaan antara dua model yang menjadi dasar (dan keduanya adalah NP-hard problems), VRP dapat menjadi sangat sulit untuk diselesaikan secara praktikal. Penggunaan VRP meningkat sebagai inti masalah dalam bidang transportasi, distribusi dan logistik. Dalam beberapa sektor pasar, transportasi sangat berpengaruh pada harga barang yang ditetapkan. Oleh karena itu, penggunaan metode komputerisasi untuk transportasi umumnya menghaslkan kontribusi yang siginifkan terhadap totla biaya, mulai dari 5% sampai 20%. 2.2 Jenis-jenis VRP Dalam penggunaan VRP untuk dunia nyata, banyak faktor sampingan yang muncul. Faktor-faktor tersebut berpengaruh pada munculnya variasi dari VRP, antara lain: • Capacitated VRP(CVRP) Faktor: Setiap kendaraan punya kapasitas yang terbatas. • VRP with Time Windows(VRPTW) Faktor: Setiap pelanggan harus disuplai dalam jangka waktu tertentu. • Mulitple Depot VRP(MDVRP) Faktor: Distributor memiliki banyak depot untuk menyuplai pelanggan. • VRP with Pick-Up and Delivering(VRPPD)
2
Faktor: Pelanggan mungkin mengembailkan barang pada depot asal. • Split Delivery VRP(SDVRP) Faktor: Pelanggan dilayani dengan kendaraan berbeda. • Stochastic VRP(SVRP) Faktor: Munculnya ‘random values’(seperti jumlah pelanggan, jumalh permintaan, waktu pelayanan atau waktu perjalanan). • Periodic VRP Faktor: Pengantaran hanya dilakukan di hari tertentu. 2.3 Formulasi VRP VRP adalah sebuah problem kombinatorial dengan basisnya adalah sisi dari graf G(V,E). Notasi-notasi yang digunakan: • V = {υ0, υ1,…., υn}(1) Adalah himpunan simpul dimana sebuah depot ada pada υ0 dan V’ = V/{ υ0} adalah himpunan sejumlah kota. • A = {( υi, υj)/ υi, υj Є V}; i ≠ j (2) Adalah sebuah ‘arc set’. • C adalah sebuah matriks dari biaya atau jarak non-negatif Cij antra pelanggan υi dan υj. • d adalah vektor permintaan konsumen • Ri adalah rute untuk kendaraan i. • m adalah jumlah kendaraan. Satu rute untuk tipa kendaraan. Jika Cij = Cji untuk semua υi, υj Є A maka dikatakan simetris dan umumnya A digantikan dengan himpunan sisi : E ={( υi, υj)| υi, υj Є V ; i < j }. Dengan tiap simpul dalam V’ berhubungan dengan jumlah barang yang akan diantar satu kendaraan qi. Agar perhitungan menjadi mudah, dapat didefiniskan sebagai berikut: b(V) =[(∑υiЄVdi/C) (3) untuk menghitung batas minimum jumlah truk yang dibutuhkan untuk melayani pelanggan dalam himpunan V. Kita juga harus memperhitungkan waktu pelayanan(waktu yang dibutuhkan untuk menurunkan semua barang) yang dibutuhkan satu kendaraan untuk menurunkan sejumlah qi pada υi. Diingatkan juga bahwa total waktu untuk rute kendaraan mana pun(waktu perjalanan ditambah waktu pelayanan) jangan sampai melewati batas yang diberikan atau D. Maka, biaya Cij diambil dari waktu perjalanan antar kota. Solusi yang layak terdiri dari: • Partisi R1 ,…, Rm dari V. • Permutasi σi dari Ri U O yang menunjukkan urutan pelanggan di rute i. Sementara itu, biaya untuk rute (Ri = {υo, υ1,…, υm+1}), dimana υi Є V dan υ0 = υm+1 = 0 (0 menunjukkan depot) dihitung dengan rumus: C(Ri) = ∑mi=0 ci,i+1 + ∑mi=1 δi (4) Sebuah rute Ri dianggap layak jika kendaraan berhenti
tepat sekali untuk setiap pelanggan dan total waktu yang dibutuhkan tidak melebihi batas yang sudah ditentukan D atau C(Ri) ≤ D. Terakhir, biaya untuk solusi masalah S adalah: FVRP(S) = ∑mi=1 C(Ri) (5) Perhitungan diatas dapat dipakai untuk VRP secara umum. Tetapi, jika ada faktor-faktor sampingan yang muncul, penyelesaian VRP –nya akan mendapat sedikit perubahan. 2.4 Solusi untuk variasi VRP Telah disebutkan sebelumnya bahwa ada berbagai variasi dari VRP. Masing-masing memiliki faktor pendorong tersendiri dan masalah tersendiri. 2.4.1 Capacitated VRP(CVRP) CVRP atau Capacitated Vehicle Routing Problem adalah sebuah VRP dimana diberikan sejumlah kendaraan dengan kapasitas tersendiri yang harus melayani sejumlah permintaan pelanggan yang telah diketahui untuk satu komoditas dari sebuah depot dengan biaya transit minimum. Oleh karena itu, CVRP sama seperti VRP dengan faktor tambahan yaitu tiap kendaraan punya kapasitas tersendiri untuk satu komoditas. CVRP dapat dijabarkan sebagai berikut: • Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan, dan total permintaan barang untuk tiap rute tidak boleh melebihi kapasitas kendaraan yang melewati rute tersebut. • Kelayakan: Solusi dikatakan ‘layak’ jika jumlah total barang yang diatur untuk tiap rute tidak melebihi kapasitas kendaraan yang melewati rute tersebut. • Perhitungan: Misalkan Q melambangkan kapasitas sebuah kendaraan. Secara matematis, solusi untuk CVRP sama dengan VRP, tapi dengan batasan tambahan total permintaan pelanggan pada rute Ri tidak boleh melebihi kapasitas kendaraan Q, atau ∑mi=1 di ≤ Q 2.4.2 VRP with Time Windows(VRPTW) VRPTW atau Vehicle Routing Problem with Time Window, hampir sama dengan VRP, namun memiliki batas tambahan yaitu sebuah jangka waktu, yang berhubungan dengan setiap pelanggan υ Є V, yang mendefinisikan sebuah jangka waktu [еυ,lυ] dimana sang pelanggan harus disuplai. Interval waktu [е0,l0] di depot disebut sebagai batas penjadwalan. VRPTW dapat dijabarkan sebagai berikut: • Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan dan waktu menunggu yang dibutuhkan untuk menyuplai semua pelanggan pada jam-jam tertentu. • Kelayakan: VRPW dibatasi hal-hal berikut, yaitu: solusi menjadi ‘tidak layak’ jika
3
kiriman pada pelanggan sampai setelah batas atas dari intervak; jika kendaraan sampai sebelum batas bawah interval ,maka waktu menunggu pada rute tersebut menjadi bertambah; Setiap rute harus start dan berhenti dalam jangka waktu yang berkaitan dengan depot; Untuk kasus soft time windows, sebuah pengiriman yang terlambat tidak mempengerahui kelayakan solusi, tapi berpengaruh pada penambahan nilai di fungsi objektif. • Perhitungan: Misalkan bυ melambangkan awal pelayanan pada pelanggan υ. Agar rute Ri = (υ0, υ1,…, υm, υm+1) memiliki solusi b yang mungkin maka solusi harus memenuhi eυi ≤ bυi ≤ lυi, 1 ≤ i ≤m, bυm + δυm + cυm,0 ≤ l0. Jika diberikan bahwa sebuah kendaraan pergi ke pelanggan selanjutnya segera setelah selesai melayani pelanggan sebelumnya, bυi dapat dihitung secara rekursif dengan rumus bυi = max{eυi,bυi-1 + δυi-1 + cυi-1, υi}(6) dengan b0 = e0 dan δ0 = 0. Maka, waktu menunggu wυi = max{0,bυi - bυi-1 – δυi-1 – ci-1,i} (7) dapat berpengaruh ketika mencapai pelanggan υi. Biaya untuk rute i dapat ditentukan dengan rumus CVRPTW(Ri) = ∑mi=0 ci,i+1 + ∑mi=1 δi + ∑mi=0 w0 (8) . Untuk solusi S dengan rute R1,…Rm, biaya dari S ditentukan oleh FVRPTW(S) = ∑mi=1 (CVRPTW(Ri + M) (9) , dimana M adalah sebuah konstanta yang sangat besar. M ditambahkan kedalam perhitungan karena minimalisasi jumlah kendaraan dimasukkan dalam salah satu tujuan VRPTW. Solusi S dibilang layak/mungkin jika semua rute yang ada dalam S layak/mungkin dan semua pelanggan dilayani dalam satu rute. Kita dapat menganggap bahwa semua kendaraan akan meninggalkan depot seawal mungkin e0. Setelah kita mendapatkan solusi dari VRPTW, kita bisa menyesuaikan waktu keberangkatan tiap depot untuk setiap kendaraan untuk menghilangkan waktu menunggu yang tidak penting. Gambar dibawah menunjukkan graf yang menggambarkan keadaan solusi untuk VRPTW. Kotak biru dan putih menggambarkan rentang waktu, area kotak yang diwarnai putih menggambarkan kapan kita bisa melayani pelanggan. Garis merah menunjukkan kapan pengantaran harus dilakukan pada keadaan ini.
Gambar 3 Keadaan solusi untuk VRPTW
2.4.3 Mulitple Depot VRP(MDVRP) Sebuah perusahaan mungkin memiliki lebih dari satu depot. Jika pelanggan-pelanggannya terkumpul di sekitar depot-depot yang ada, maka masalah pendistribusiannya harus dimodelkan menjadi sebuah kumpulan dari VRP-VRP yang independent. Namun, jika pelanggan dan depot-depot yang ada saling bercampur aduk (tidak terkumpul secara teratur, bisa ada satu pelanggan dilayani lebih dari satu depot atau sebaliknya) maka masalahnya menjadi Multi-Depot Vehicle Routing Problem atau MDVRP. Sebuah MDVRP membutuhkan pengaturan para pelanggan ke depot-depot yang ada. Tiap kendaraan pergi dari satu depot, melayani pelanggan-pelanggan yang sudah ditentukan akan dilayani oleh depot tersebut, dan kembali lagi ke depot tersebut. Tujuan utama dari MDVRP adalah untuk melayani semua pelanggan sementara jumlah kendaraan dan jarak perjalanan diminimalisasi. Penjabaran MDVRP sebagai berikut: • Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan dan total permintaan barang yang harus dilakukan dari beberapa depot. • Kelayakan: Solusi dianggap layak jika tiap rute memenuhi batasan standar VRP dan keluar-masuk kendaraan terjadi di depot yang sama. • Perhitungan: Dalam kasus MDVRP, kita mempunyai himpunan simpul V ={υ1,…, υm} U V0, dimana V0 = {υ01,…, υ0d} adalah simpul-simpul yang menggambarkan depotdepot yang ada. Rute i digambarkan dengan Ri = {d, υ1,.., υm,d} dengan d Є V0. Biaya untuk rute ini dihtung dengan cara yang sama untuk VRP biasa. 2.4.4
VRP with Pick-Up and Delivering(VRPPD) Vehicle Routing Problem with Pick-up and Delivering atau VRPPD adalah sebuah VRP dimana ada peluang
4
kejadian pelanggan mengembalikan barang yang sudah diantarkan. Dalam VRPPD kita perlu memperhatikan bahwa barang yang dikembalikan dapat dimasukkan ke dalam kendaraan pengantar. 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 bahwa semua pelanggan hanya diknjungi satu kali. Simplifikasi yang biasa terjadi lainnya adalah dengan memikirkan bahwa tiap kendaraan harus mengantarkan semua barang sebelum mengambil kembali barang dari pelanggan. VRPPD 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 ckup untuk mengambil barang dari pelanggan. • Perhitungan: Biaya untuk satu rute dihitung seperti dalam kasus VRP biasa, dengan batasan tambahan bahwa sebuah rute dianggap ‘layak’ jika dan hanya jika memenuhi syarat ‘layak-antar’, ‘layakambil’, dan ‘layak-isi’. Pertama-tama, misalkan p adalah vector permintaan penagmbilan barang dari pelanggan,maka: ¾ Layak-antar: Keadaan seperti ini artinya total kuantitas barang untuk diantrakan untuk satu rute tidak boleh melebihi kapasitas kendaraan. Misalkan diberikan rute Ri = {υ0, υ1,…, υm+1} dan kendaraan yang ditentukan untuk rute tersebut berkapasitas C, maka batasannya dapat diekspresikan secara matematis oleh : Cd(υk) ≤ C dan Cd(υk+1) > C;dimana Cd(υk) adalah total kuantitas barang yang diantarkan ke semua pelanggan dalam suatu rute yang dimulai dari υ0 (depot) dan berakhir di υk ,atau Cd(υk) = ∑ υiЄP(1, υk) di (10). P(1, υk) melambangkan pelanggan yang dikunjungi sepanjang jalan dari depot sampai υk, termasuk pelanggan υk. ¾ Layak-ambil: Keadaan seperti ini memliki batasan yang memastikan bahwa
kendaraan yang digunakan punya kapasitas yang cukup untuk mengambil barang dari pelanggan di rute tersebut. Cp(υk) ≤ C dan Cp(υk+1) > C; dimana Cp(υk) adalah total kuantitas barang yang diambil sepanjang jalan menuju dan termasuk ‘node’ υk , atau : Cp(υk) = ∑ υiЄP(1, υk) pi (11). ¾ Layak-isi: Keadaan ini disebabkan kemungkinan kapasitas dai kendaraan dilanggar pada suatu titik di dalam rute. Pelanggaran itu bisa berdampak pada beberapa pelanggan selanjutnya, Misalkan L(υk) menggambarkan jumlah isi dari kendaraan setelah meninggalkan pelanggan υk . Andaikan kendaraan meninggalkan depot dengan isi awal L(1) ≤ C. Kemudian isi kendaraan di suatu titik adalah L(υk) = Cp(υk) + L(1) – Cd(ik) (12). Isi kendaraan yang dihitung dengan persamaan (12) dapat melebihi kapasitas kendaraan. Itu berarti rute tersebut menjadi ‘tidak layak’ karena kendaraan terebut tidak bisa melakukan layanan pada pelanggan selanjutnya υk+1 di rute tersebut. Kesimpulannya, sebuah rute dianggap layak jika L(υk) ≤ C dan L(υk+1) > C. 2.4.5 Split Delivery VRP(SDVRP) Split Delivery Vehicle Routing Problem, atau SDVRP adalah perluasan VRP jika tiap pelanggan dapat dilayani dengan kendaraan yang berbeda andaikan biayanya dapat berkurang. Perluasan ini perlu dilakukan jika jumlah permintaan pelanggan sama besar dengan kapasitas dari kendaraan. SDVRP dijabarkan sebagai berikut: • Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan untuk pelayanan. • Kelayakan: Solusi dianggap layak jika tiap rute memenuhi batasan standar VRP Solusi dianggap layak jika memenuhi batasan standar VRP ditambah dengan tiap pelangan bisa dilayani oleh lebih dari satu kendaraan. • Perhitungan: Minimalisasi total biaya untuk semua rute. Cara yang paling mudah untuk mengubah VRP menjadi SDVRP adalah dengan membagi jumlah permintaan pelanggan menjadi sejumlah kecil permintaan. 2.4.6 Stochastic VRP(SVRP) Stochastic Vehicle Routing Problem atau SVRP adalah variasi VRP yang terjadi jika factor sampinga yang muncul bersifat acak. Ada tiga bentuk SVRP, yaitu: o Pelanggan stochastic : Tiap pelanggan υi ada memiliki peluang pi dan tidak ada dengan peluang 1 – pi. o Permintaan stochastic : Jumlah permintaan di
5
untuk tiap pelanggan adalah variabel random. Waktu stochastic : Waktu pelayanan δi dan waktu pelayanan tij adalah variabel random. Dalam SVRP, untuk bisa mendapatkan solusi, masalah harus dibagi menjadi dua tahap. Solusi pertama ditentukan sebelum variabel random diketahui. Pada tahap kedua, pengoreksian dilakukan jika nilai dari variabel random sudah diketahui. SVRP dijabarkan seperti ini: • Tujuan: Minimalisasi jumlah kednaraan dan total waktu perjalanan untuk melayani pelanggan dengan nilai random untuk tiap pengantaran(pelanggan,permintaan,waktu)] • Kelayakan: Jika data-data yang ada bersifat random/acak, kita tidak perlu lagi memenuhi batasan-batasan yang ada untuk semua realisasi variabel random. Maka pencari solusi memerlukan antara tingkat kepuasan batasan tertentu dengan peluang yang diberikan, atau pengoreksian bila ada batasan yang dilanggar. • Perhitungan : Sederhanakan ∑i<j cijxij + Q(x), dimana xij adalah sebuah variabel integer yang nilainya sama dengan jumlah sisi (υi,υj) yang muncul pada tahap pertama, dan jika xij hanya bisa bernilai 1 atau 0, maka i = 1, xij sama dengan 2 jika kendaraan melakukan perjalanan bolak-balik antara depot dan υj;sedangkan Q(x) adalah fungsi untuk tahap kedua. Fungsi ini bergantung pada masalah dan berhubungan dengan pilihan tindakan yang mungkin untuk kasus-kasus tertentu.
tetap. PVRP dapat dilihat sebagai masalah pengaturan sekelompok rute untuk tiap hari sehingga batasan-batasan yang ada terpenuhi dan biaya keseluruhan dapat diminimalisasi. PVRP juga dapat dilhat sebagai ‘multi-level combinatorial optimization problem’: o Pada tahap pertama, tujuannnya adalah untuk menghasilkan sebuah kelompok berisi kombinasi alterntatif-alternatif solusi untuk tiap pelanggan. Contoh, jika rentang perencanaan t = 3 hari atau {d1,d2,d3} maka kombinasi yang mungkin adalah: 0 → 000;1 → 001;2 → 010;3 → 011;4 → 100;5 → 101;6 → 110;dan 7 → 111. Jika pelanggan menghendaki dua kali kunjungan, makan pelanggan akan mendapatkan beberapa alternatif bentuk kunjungan: {d1,d2},{d1,d3},{d2,d3}, atau pilihan 3,5,6 dari tabel dibawah.
o
2.4.7 Periodic VRP Dalam Periodic Vehicle Routing Problem atau PVRP, VRP digeneralisasi dengan memperluas rentang perencanaan pengiriman menjadi M hari, dari semula hanya dalam rentang sehari. PVRP dapat dijabarkan sebagai berikut: • Tujuan: Meminimalisasi jumlah kendaraan dan total waktu perjalanan untuk melayani tiap pelanggan. • Kelayakan: Solusi dianggap layak jika memenuhi batasan standar VRP. Ditambah dengan keadaan bahwa sebuah kendaraan tidak boleh kembali ke depot pada satu hari yang sama. Dalam M hari, tiap pelanggan harus dikunjungi minimal sekali. • Perhitungan: Sederhanakan jumlah biaya untuk semua rute. Tiap pelanggan punya permintaan harian yang telah diketahui yang harus dipenuhi dalam satu kali kunjungan dengan hanya satu kendaraan. Jika rentang perencanaan M = 1, maka PVRP berubah menjadi VRP biasa. Dalam PVRP, tiap pelanggan dikunjungi k kali dimana 1 ≤ k ≤ M. Dalam model klasik dari PVRP, jumlah permintaan harian dari suatu pelanggan selalu
Tabel 1
J. Pelang gan 1 2 3 4 5 o
o
Kemung kinan Kombina si 30 1 3 1,2,4 20 2 3 3,5,6 20 2 3 3,5,6 30 2 3 1,2,4 10 3 1 7 Pada tahap kedua, kita harus memilih satu alternatif untuk setiap pelanggan, sehingga batasan harian terpenuhi. Oleh karena itu, kita gharus memilih pelanggan mana yang akan dikunjungi setiap harinya. Pada tahap ketiga, kita harus menyelesaikan VRP untuk tiap harinya(menggunakan perhitungan dasar VRP) J. Permintaan Harian
J. Kunjung an
J. Kombi nasi
2.5 Penggunaan Kombinatorial Dalam VRP Bentuk kombinatorial yang digunakan dalam VRP adalah optimalisasi kombinatorial. Penggunaaannya lebih ditujukan pada VRP biasa , SDVRP dan CVRP (mengingat cara penghitungannya sama dengan VRP biasa) dan PVRP. Penggunaaan optimalisasi kombinatorial merupakan dasar dari pencarian solusi dari berbagai jenis VRP. Umumnya penggunaan kombinatorial adalah untuk memeriksa kemungkinan prioritas pelayanan pelanggan di suatu rute, sementara untuk perhitungan lainnya(perhitungan kapasitas, waktu, jarak, dll) cukup menggunakan perhitungan aritmatika biasa. Seperti pada Periodic VRP, kombinatorial digunakan untuk mengetahui kombinasi kunjungan pada pelanggan tiap harinya.
6
2.6 Cara Lain Menyelesaikan VRP Sebagian besar bentuk VRP diselesaikan dengan metode-metode berikut ini: ¾ Pendekatan lansung dengan menghitung dengan rumus biasa (hingga 100 node). ¾ Metode-metode heuristic: Pendekatan hierarkis (SDVRP + TSP), Mulit-route Improvement Heuristic. ¾ Metode-metode metaheuristik: Tabu search, constraint programming, granular tabu, ant systems. 3. KESIMPULAN Kesimpulan yang dapat diambil dari pembahasan makalah ini tentang aplikasi kombinatorial dalam Vehicle Routing Problem : ¾ Kombinatorial adalah salah satu cabang ilmu matematika diskrit. Penggunaannya sangat beragam, salah satu contohnya adalah dalam Vehicle Routing Problem. ¾ Penggunaan optimalisasi kombinatorial dalam Vehicle Routing Problem memudahkan pencarian solusi untuk Vehicle Routing Problem , yang dikategorikan ke dalam NP-hard problems. ¾ Vehicle Routing Problem dapat diimplementasikan ke dalam kehidupan sehari-hari, terutama bagi mereka yang berkecimpung dalam bidang distribusi barang,
DAFTAR REFERENSI [1]
IDSIA - Istituto Dalle Molle di Studi sull'Intelligenza Artificiale. (2007). Vehicle Routing Problem. http://www.idsia.ch/. Tanggal akses: 12 Desember 2007 pukul 10.32. [2] Neo.lcc.uma.es. (2007). Capacitated VRP. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/CVRPDesc.html. Tanggal akses: 12 Desember 2007 pukul 09.40.
[3] Neo.lcc.uma.es. (2007). Multiple Depot VRP. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/MDVRPDesc.ht ml. Tanggal akses: 12 Desember 2007 pukul 09.49. [4] Neo.lcc.uma.es. (2007). Periodic VRP. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/PVRPDesc.html. Tanggal akses: 12 Desember 2007 pukul 09.56. [5] Neo.lcc.uma.es. (2007). Split Delivery VRP. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/SDVRPDesc.htm l. Tanggal akses: 12 Desember 2007 pukul 09.59. [6] Neo.lcc.uma.es. (2007). Stochastic VRP. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/SVRPDesc.html. Tanggal akses: 12 Desember 2007 pukul 10.04. [7] Neo.lcc.uma.es. (2007). What is VRP. http://neo.lcc.uma.es/radi-aeb/WebVRP/VRPIntro.html. Tanggal akses: 12 Desember 2007 pukul 09.29. [8] Neo.lcc.uma.es. (2007). VRP Formulation. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/VRPDesc.html. Tanggal akses: 12 Desember 2007 pukul 09.30. [9] Neo.lcc.uma.es. (2007). VRP with Pick-Up and Delivering. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/VRPPDDesc.htm l. Tanggal akses: 12 Desember 2007 pukul 10.11. [10] Neo.lcc.uma.es. (2007). VRP with Time Windows. http://neo.lcc.uma.es/radiaeb/WebVRP/Problem_Descriptions/VRPTWDesc.htm l. Tanggal akses: 12 Desember 2007 pukul 10.14. [11] Schrijver, Alexander. (2007). A Course in Combinatorial Optimization. homepages.cwi.nl/~lex/files/dict.pdf. Tanggal akses: 11 Desember 2007 pukul 16.00 [12] Wikipedia. (2007). Combinatorial Optimization. http://en.wikipedia.org/wiki/Combinatorial_optimizati on. Tanggal akses: 11 Desember 2007 pukul 16.03. [13] Wikipedia. (2007). Vehicle Routing Problem. http://en.wikipedia.org/wiki/Vehicle_routing_problem. Tanggal akses : 11 Desember 2007 pukul 16.18.
7
