ALGORITMA HEURISTIK UNTUK PENYELESAIAN PERMASALAHAN ASYMMETRICS VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS DELIVERIES AND PICK-UPS (AVRPSDP)

Prosiding Seminar Nasional Manajemen Teknologi VIII Program Studi MMT-ITS, Surabaya 2 Agustus 2008

ALGORITMA HEURISTIK UNTUK PENYELESAIAN PERMASALAHAN ASYMMETRICS VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS DELIVERIES AND PICK-UPS (AVRPSDP) Kristina Nina Eka Tanjung dan Ahmad Rusdiansyah Program Studi Magister Manajemen Teknologi ITS Bidang Keahlian Manajemen Industri Email: [email protected]

ABSTRAK Penelitian ini membahas masalah operasional pendistribusian barang dalam konteks reverse logistics. Secara spesifik, penelitian ini akan membahas mengenai metode heuristic untuk menyesaikan permasalahan Vehicle Routing Problem (VRP) dimana transportasi linehaul untuk mengirimkan produk isi dan transportasi backhaul untuk mengambil kemasan ulang kosong di masing-masing titik kustomer dilaksanakan secara simultan dalam satu perhentian. Dalam literatur, problem ini dikenal dengan nama Vehicle Routing Problem with Simultaneous Deliveries and Pick-Ups (VRPSDP). Problem VRPSDP ini berbeda dengan VRP pada umumnya dimana transportasi linehaul atau backhaul dilakukan secara terpisah dan dilakukan dengan kendaraan yang berbeda. Contoh kasus nyata permasalahan ini adalah permasalahan distribusi air mineral dengan kemasan gallon dan distribusi dari tabung gas LPG dari depot ke pelanggan dan kembali lagi ke depot. Dalam penelitian ini permasalahan VRPSDP dikembangkan menjadi permasalahan dimana jarak antara dua titik pelanggan/depot merupakan tidak simetris. Permasalahan ini kemudian dinamakan Asymmetric Vehicle Routing Problems with Simultaneous Deliveries and Pick-Ups. Untuk menyelesaikan permasalahan AVRPSDP ini dikembangkan metode heuristik yang merupakan pengembangan algoritma heuristik dari Dethloff (2001) untuk menyelesaikan permasalahan VRPSDP. Dalam algoritma ini, suatu rute awal dikembangkan dengan melakukan penyisipan-penyisipan node (node insertions) yang mempertimbangkan tidak hanya faktor jarak terpendek namun juga faktor sisa ruang dalam kendaraan setelah penyisipan. Hal ini dilakukan mengingat pembentukan rute dalam VRPSDP/AVRPSDP lebih kompleks dibandingkan dengan problem klasik VRP. Urutan kunjungan adalah sangat mempengaruhi kelayakan suatu rute dari sudut pandang kapasitas kendaraan. Algoritma yang dikembangkan tersebut kemudian diterjemahkan dalam perangkat lunak spreadsheet Excel dan diujicobakan untuk memecahkan permasalahan nyata distribusi barang di sebuah perusahaan distribusi air mineral. Kata kunci : Reverse logistics, VRP, VRP with Simultanoeus Deliveries and Pickups, Assymetric.

PENDAHULUAN Pada level operasional menurut Ghiani,dkk (2004), problem efisiensi untuk transportasi terletak pada pengaturan rute pada distribusi produk, khususnya pada short haul transportation yang melibatkan banyak pelanggan. Masalah pengaturan rute

ISBN : 978-979-99735-6-6 A-30-1


dengan keterbatasan kapasitas muatan kendaraan pengangkut dan jumlah kendaraan untuk mengantar ke sejumlah pelanggan dalam literatur dikenal dengan nama vehicle routing problem (VRP). Pada VRP, setiap pelanggan harus dikunjungi sebanyak satu kali dengan tujuan untuk meminimalkan total jarak tempuh yang harus dilalui oleh kendaraan dalam melayani pelanggan. Pada VRP original pengiriman barang dilakukan dari distributor (depot) kepada konsumen (line haul). Berbeda dengan di atas, penelitian ini akan membahas lebih dalam mengenai VRP yang ditujukan untuk Reverse Logistics Transportation. Pada reverse logistic pengiriman produk disertai pula oleh pengambilan kemasan dari pelanggan yang pada awalnya terjadi pada lintasan backhaul dengan menggunakan kendaraan yang sama. Jenis pengembangan dari VRP ini kemudian dikategorikan berdasarkan urutan pengambilan (pick-ups) dan pengiriman (deliveries) produk yang dikenal dengan nama VRP with Pick Ups and Deliveries (VRPPD). Salhi dan Nagy (2004) menggolongkan VRPPD menjadi tiga macam yaitu VRPB, VRPM, dan yang terakhir adalah VRP with Simultaneous Deliveries and PickUps (VRPSDP). Pengiriman terlebih dahulu kemudian mengambil kembali setelah semua order pengiriman selesai dilakukan dengan menggunakan kendaraan pengangkut yang kapasitas muatannya terbatas dikenal dengan nama Vehicle Routing Problem with Backhaul (VRPB). Sedangkan jika deliveries dicampur dengan pick-ups dinamakan Vehicle Routing Problem with Mixed Pick Ups and Deliveries (VRPM). Yang menjadi masalah sehingga VRPSDP tidak terlalu popular dibahas adalah keterbatasan kapasitas kendaraan pengangkut, dan desain dari kendaraan pengangkut dalam hal loading dan unloading dari container kendaraan pengangkut.. Namun dengan modifikasi yang ada dari container kendaraan pengangkut dan maraknya penggunaan kemasan isi ulang maka studi tentang hal ini mulai kembali ramai dibahas. Dalam beberapa kasus, VRPB dan VRPM dianggap tidak efisien karena pengiriman produk dan pengambilan kemasan kosong terpisah antara linehaul dan backhaul. Hal inilah yang kemudian menaikkan kembali issue VRPSDP untuk efisiensi.. VRPSDP sendiri adalah salah satu model derivasi terkini dari VRP, untuk problem dengan pengiriman produk dan pengangkutan kembali kemasan kosong/produk cacat, dilakukan secara simultan pada setiap titik dalam lintasan. Dalam penelitian ini VRPSDP akan dikembangkan untuk kegiatan distribusi di lapangan dengan jarak dan waktu tempuh antara satu titik ke titik lain yang tidak simetris. Hal ini dilihat dari kenyataan di lapangan bahwa: a. Dengan adanya pengaturan jalur lalu lintas dan aliran jalan menyebabkan tidak setiap jalan (arc) dapat dilalui dengan dua arah (asymmetrics), sehingga tidak semua titik pelanggan dapat dijangkau dari titik yang sama b. Waktu tempuh antara titik A ke B berbeda dengan waktu tempuh dari B ke A c. Adanya keterbatasan waktu pelayanan dari kendaraan pengangkut d. Keterbatasan kapasitas dan jumlah kendaraan yang melayani Melihat hal tersebut diatas maka permasalahan tersebut dinamakan Asymmetrics Vehicle Routing Problem with Simultaneous Deliveries and Pick-Ups. Di mana untuk menyelesaikan masalah dikembangkan metode heuristik yang merupakan pengembangan algoritma heuristik dari Dethloff (2001) untuk menyelesaikan permasalahan VRPSDP, berdasarkan total waktu minimal yang dibutuhkan untuk melayani satu group pelanggan.

ISBN : 978-979-99735-6-6 A-30-2


METODA Menurut Amico, Righini, dan Salani (2006) VRPSDP ini dikenal juga dengan nama Vehicle Routing Problem with Simultaneous Distributions and Collections. Problem yang dipunyai adalah bagaimana dengan kapasitas kendaraan terbatas harus mengirim dan mengambil kembali barang dari depot ke kelompok pelanggan yang harus dilakukan oleh kendaraan yang sama dan di setiap pelanggan dilakukan, pendistribusian barang dan setelah itu mengambil kembali (collection) kemasan yang telah kosong untuk dikirimkan ke depot secara simultan. Problem selanjutnya adalah bila pengambilan kembali (pick-ups) lebih besar dari pada deliveries. Dalam jurnalnya Nagy dan Salhi (2004) mengkategorikan VRPSDP sebagai jenis VRPPD. Beberapa metode pendekatan heuristik dilakukan untuk menyelesaikan kasus ini, salah satunya adalah Dethloff (2001) dengan pendekatan insertion-nya. Model Matematika dari VRPSDP Notasi: J : Kelompok dari lokasi konsumen : Kelompok dari konsumen dan depot, Jo = Jo {0} Jo K : Kelompok dari kendaraan Parameters C : Kapasitas dari kendaraan/vehicle Cij

: Jarak dari node i ϵ Jo, j ϵ Jo, i ≠ j

Dj

: Jumlah yang harus dikirim ke pelanggan j ϵ J

N

: Banyaknya titik, yaitu: N =

Pj

: Jumlah yang harus diambil dari pelanggan j ϵ Jo

M : Bilangan, contoh M=max Variabel Keputusan : Muatan dari kendaraan v ϵ V ketika akan meninggalkan depot

xijv

: Muatan dari kendaraan setelah melayani pelanggan j ϵJ : Variable yang digunakan untuk menghindari subtours, dapat diartikan sebagai posisi dari node j ϵ J dalam rute : Binary variable yan mengindikasikan apakah kendaraan v ϵ V menempuh perjalanan dari node i ϵ J0 sampai node j ϵ J0(xijv = 1) atau tidak (xijv = 0)

Model (V) Minimize (1) (untuk meminimalkan total jarak tempuh) Subject to

(j ϵ J) (Melayani pelanggan hanya satu kali)

ISBN : 978-979-99735-6-6 A-30-3

(2)


(s ϵ J,k ϵK)

(3) (Tiba dan berangkat dari setiap pelanggan menggunakan kendaraan yang sama)

(k ϵ K)

(4)

(Inisial untuk muatan kendaraan)

(j ϵ J,k ϵ K)

(5)

(Muatan kendaraan setelah pelanggan pertama)

(i ϵ J, j ϵ J,j ≠ i)

(6)

(Muatan Kendaraan setelah rute terakhir)

(k ϵ K) (j ϵ J)

(7) (8)

(kapasitas kendaraan setelah pelanggan pertama dan akhir dari rute) (i ϵ J, j ϵ J, j ≠ i) ( j ϵ J) (i ϵ J0, j ϵ J0, k ϵ K)

(9) (10) (11)

VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian ini pun tidak dapat diselesaikan dari satu arah, seperti pada VRPB ataupun pada VRPM. Rusdiansyah (2005) menjelaskan dua buah tur yang mengandung node/titik yang sama tetapi dengan arah tur yang berbeda akan menyebabkan terjadinya perbedaan pada hasil yang didapat, untuk itu Dethloff (2001) mengatakan kasus VRPSDP harus dilihat dari dua arah dalam melakukan perhitungannya yaitu dari arah deliveries dan dari arah pickups sehingga didapat hasil yang sesuai. Metode Penyisipan Dethloff (2001) Selain ditinjau dari dua arah, penyelesaian VRPSDP in tidak bisa hanya melihat jarak saja karena kapasitas baik pick-ups dan deliveries dari setiap node perlu diperhatikan. Dethloff (2001), berusaha membahas masalah ini dengan pendekatan penyisipan yang menggabungkan beberapa metode penyisipan untuk membuat rute yang dapat digunakan dalam kasus VRPSDP. Pada subbab ini akan dijelaskan dua metode penyisipan yang dibahas oleh Dethloff (2001) untuk menyelesaikan kasus VRSDP. a. Penyisipan Titik berdasarkan Travel Distance (TD) Salah satu cara sederhana dalam metode penyisipan adalah Travel Distance yang dinotasikan menjadi ΨTD. ΨTD adalah jarak tempuh extra yang didapat dengan memasukkan konsumen k di antara 2 konsumen i dan j dan kemudian cari pilih nilai ΨTD terkecil.

ΨTD =

(12) Namun menurut Dethloff cara ini mempunyai dua kekurangan yaitu: 1. Efek dari feasible insertation/penyisipan dalam hubungannya dengan kapasitas, sebagai derajat bebas untuk insertation berikutnya tidak diperhitungkan.

ISBN : 978-979-99735-6-6 A-30-4


2. Konsumen mungkin akan diletakkan di state terakhir dari prosedur sebagai akibat dari tidak dipilihnya lokasi konsumen berdasarkan extra jarak yang didapat dari hasil perhitungan. b. Penyisipan Titik Berdasarkan Residual Capacity Penyisipan kapasitas ini dilakukan dari dua arah yaitu dari arah delivery (RD) dan dari arah pick-up (RP). Dengan adanya penyisipan dari dua arah ini maka akan dapat diketahui bahwa semakin besar residual capacity untuk deliveries dan pick-ups maka akan semakin besar pula derajat kebebasan untuk penyisipan selanjutnya. Notasi: J : Kelompok dari lokasi konsumen J0 : Kelompok dari konsumen dan depot, J0 = J0 {0} K : Kelompok dari kendaraan C : Kapasitas dari kendaraan/vehicle Cij

: Jarak dari node i ϵ Jo, j ϵ Jo, i ≠ j

CD(SUI(s)) : Jumlahan jarak yang harus ditempuh untuk delivery sampai konsumen s CP(SUI(s)) : Jumlahan jarak yang harus ditempuh untuk pick-up dark komsumen s Ds

: Jumlah dari pengiriman ke konsumen s

Ps

: Jumlah pengambilan dari konsumen s

lq

: Jumlahan kapasitas yang digunakan sampai dengan sampai dengan tingkatan q

PRI(q)

: notasi untuk delivery/pick-up sampai dengan tingkatan (q-1)

Rumusan untuk residual deliveries dan pick-ups dirumuskan seperti pada rumus di bawah ini: (13)

RD(0) = RD(q) = min

(qϵT)

(14)

RP(PRI(0)) =

(15)

RP(q) = min

(sϵT\PRI(0)

{0})

(16)

Residual capacity akan semakin tinggi pada saat jumlah delivery besar dan jumlah pick-up kecil disisipkan di awal sedangkan jumlah delivery kecil dan pick-up besar disisipkan setelah node yang ditentukan. Setiap residual tersebut akan semakin berguna jika dapat dipakai sebagai bagian dari rute yang panjang. Hal ini juga sejalan dengan asumsi yang digunakan oleh Rusdiansyah (2005) dalam disertasinya mengenai Periodic Inventory Routing Problem with Simultaneous Deliveries and Pickups (PIRPSDP) Setelah mengetahui residual capacity untuk setiap node, maka rata-rata dari keseluruhan RD dan RP adalah dengan menambahkan semua RD dan RP untuk semua ISBN : 978-979-99735-6-6 A-30-5


node dan membagi dengan jumlah jarak yang harus ditempuh untuk mencapai node tertentu.

RDT =

(17)

RPT =

(18)

Semakin besar RDT dan RPT maka derajat kebebasan untuk melakukan future instertion akan semakin besar. Selanjutnya untuk menguji apakah dapat dilakukan penyisipan untuk titik selanjutnya (future insertion) maka dilakukan penyisipan yang diambil dari node yang belum dimasukkan ke rute (unrouted node). TC =

(19)

Dari penyisipan node selanjutnya akan didapat total consumption capacity (TC). Hasil dari TC selanjutnya dikonversikan ke dalam jarak untuk mendapatkan ΨRC, yang didapat dengan melakukan penggabungan dengan hasil penyisipan dari Travel Distance untuk mendapatkan kriteria penyisipian dari travel distance maupun dari residualnya. ΨRC= ΨTD + λTC(2Cmax-Cmin)

(20)

Dari ΨRC akan didapatkan rute hasil penggabungan antara ΨTD dan TC, di mana peranan dari kapasitas akan menempati λ [0,1], di mana RC terkecil akan dipilih sebagai rute yang akan dilewati. Langkah ini akan diulangi sehingga kapasitas terpenuhi atau semua titik masuk ke dalam rute. Asymmetric Vehicle Routing Problem with Simultaneous Deliveries and Pick-Ups Metode heuristik yang dikembangkan oleh Dethloff (2001) adalah metode insertion. Metode ini digunakan untuk mengatasi permasalahan untuk VRPSPD, di mana setiap titik dapat berhubungan dan jarak antar titik-titiknya adalah simetris. Sedangkan pada kasus ini adanya tata kota menyebabkan tidak semua titik-titik tersebut bisa dijangkau dari semua tempat, dan dengan adanya aliran arus kendaraan, setiap kendaraan bergerak mengikuti peraturan untuk mencapai tempat yang harus dituju, hal itu menyebabkan waktu tempuh dari titik A ke titik B kadang berbeda dengan titik tempuh dari B ke A. Menurut Toth & Vigo (2002) salah satu ciri dari Asymmetric Vehicle Routing Problem adalah pada setiap nonnegative cost cij arc (i,j) ϵ A yang menandakan jarak yang harus ditempuh dari vertex i ke vertex j dalam matriks cij tidak simetris, di mana A adalah kelompok dari directed arc, yang menghubungkan titik-titik di dalam matriks cij. Sama seperti VRPSDP secara umum kondisi pada Asymmetric Vehicle Routing Problem mempunyai beberapa ciri, antara lain: a. Menggunakan lebih dari 1 kendaraan yang homogen. b. Satu alat angkutan untuk melayani satu rute. c. Pada setiap pelanggan akan dilakukan dua jenis service, yaitu pendistribusian produk (deliveries) dan pengambilan kemasan isi ulang (pick-ups). d. Setiap pelanggan akan disinggahi sebanyak satu kali.

ISBN : 978-979-99735-6-6 A-30-6


Jika pada VRPSDP penentuan rute didasarkan pada dua hal yaitu jarak dan kapasitas dari kendaraan yang akan digunakan. Maka pada kasus AVRPSDP juga mempunyai sifat serupa, namun untuk kasus ini akan digunakan turunan dari jarak yang dikonversikan menjadi waktu dengan menggunakan kecepatan yang diasumsikan konstan. Dan dengan adanya perubahan ini menyebabkan terjadi pula penambahan batasan dalam pengambilan keputusan dalam penentuan rute, antara lain: Tabel 1 Kriteria pada Assymetric Vehicle Routing Problem Jarak Waktu Lintasan aliran lalu lintas menyebabkan ketidaksimetrisan jarak dengan asumsi kecepatan konstan maka waktu tempuh titik ke titik menjadi tidak simetris

Kapasitas Banyaknya muatan yang akan dikirim dan diambil

Penambahan variable yaitu: a. Waktu tempuh (tij) b.Waktu service(stij)

Jumlah kendaraan yang homogen

Penambahan batasan waktu, yaitu (tij)+ st(i)

Kapasitas Kendaraan

Dengan adanya perubahan pada variable dan batasan waktu maka akan ada beberapa penyesuaian pada model matematika dan algoritma dari VRPSPD. Model Matematika dari AVRPSDP Pada model matematika dari AVRPSDP terdapat beberapa penambahan pada parameter dan variable keputusan dari model matematika pada VRPSDP. Di samping penambahan terdapat pula perbedaan pada fungsi tujuan. Tabel 2 Tabel Perbedaan dan Penambahan VRPSDP menjadi AVRPSDP VRPSDP Parameter

Variabel Keputusan

AVRPSDP T : Total waktu yang tersedia bagi kendaraan untuk melayani satu lintasan. vij : kecepatan kendaraan dari node i ϵ Jo, j ϵ Jo, i ≠ j tij : Waktu tempuh dari node i ϵ Jo, j ϵ Jo, i ≠ j stj : Waktu service yang dibutuhkan untuk melayani pelanggan j ϵ J

Fungsi Tujuan

(untuk meminimalkan total waktu tempuh)

(21) (untuk meminimalkan total waktu tempuh)

(i ϵ J, j ϵ J,j ≠ i) (22) st j = ((st(d) x Dj ) + (st(p) x Pj ))/60 (23) di mana: stj : waktu pelayanan di pelanggan j st(d) : waktu unloading produk dari kendaraan st(p) : waktu loading kemasan kosong ke kendaraan (i ϵ J, j ϵ J,j ≠ i) (j ϵ J)

ISBN : 978-979-99735-6-6 A-30-7

(24) (55)


Algoritma pada Penyisipan Waktu (ψTT) Waktu dalam kasus ini mempunyai peranan penting, karena dalam kasus ini waktu menjadi batasan dalam melayani pelanggan. Waktu dibagi menjadi tiga bagian besar, yaitu: a. Waktu pelayanan (st), waktu yang dibutuhkan untuk melakukan pelayanan di tempat pelanggan, yatu waktu unloading produk dan loading kemasan kosong. b. Waktu tempuh (tij), adalah waktu yang dibutuhkan untuk menempuh perjalanan dari titik i ke tititk j. c. Batasan Waktu (T), adalah waktu yang ditentukan oleh distributor dalam melayani pelanggannya. Waktu tempuh dalam kasus asymmetric di kasus ini sangat ditentukan oleh aliran dan panjang jarak, karena: a. Tidak semua titik berhubungan satu sama lain secara langsung terutama dengan depot, b. Jarak antara titik lokasi satu ke lokasi lainnya tidak semua saling berhubungan satu sama lain. c. Waktu sesungguhnya didapat dari jarak dibagi dengan kecepatan. Oleh karena itu maka dalam matriks ditetapkan xij=1 untuk titik-titik yang berhubungan (direct arc) dan xij=0 untuk jarak yang menghubungkan titik-titik yang tidak berhubungan. Oleh karena data yang kita dapat adalah data jarak, maka jarak antara titik-titik yang tidak berhubungan/ undirected arc adalah 1000, sedangkan dari titik tersebut kembali ke titik tersebut kembali adalah sangat tak terhingga jalannya (contohnya depot) sehingga jaraknya adalah 1000. Arc(i,j) = 1000, di mana i dan j tidak berhubungan langsung (26) Arc(i,i) =1000 (77) Dengan mengetahui jarak yang ada maka dengan asumsi kecepatan adalah konstan, maka akan didapatkan matriks waktu tempuh (tij) di mana waktu tempuh ini merupakan turunan dari jarak yang ada, tij adalah waktu tempuh yang dibutuhkan oleh kendaraan dari titik i ke titik j, di mana waktu tempuh i ke j tidak sama dengan waktu yang ditempuh dari j ke i. Dengan semakin kecil waktu yang dihasilkan dari selisih penyisipan antara dua titik, maka akan semakin cepat waktu tempuh yang harus ditempuh dari dua titik tersebut ke titik sisipan berikutnya. Oleh sebab itu, untuk menentukan lokasi mana yang menghasilkan rute terdekat sesuai dengan tujuan utama VRP, maka diambil residual waktu tempuh terkecil ψTT yang didapat dengan memasukkan penyisipan lokasi baru (k) terhadap lokasi-lokasi yang sudah ditentukan sebelumnya. a. Dalam asymmetric jarak antara titik A ke titik B belum tentu sama dengan titik B ke titik A oleh karena itu harus dihitung semua kemungkinan yang terjadi, Arc(i,j) ≠ Arc(j,i), untuk dua titik yang berhubungan. ΨTT = tik + tkj – tij (28) b. Jarak dua titik yang tidak berhubungan langsung (undirected arc) adalah ∞ (tak terhingga besarnya) sehingga tidak boleh diperhitungkan dalam pengolahan data.

ISBN : 978-979-99735-6-6 A-30-8


Algoritma pada Penyisipan berdasarkan residual Kapasitas Pada bagian ini penentuan rute berdasarkan penyisipan node yang didapat dari residual kapasitas, di mana data jumlah muatan yang akan diterima dan yang akan dikirim ke konsumen s harus lebih kecil dari kapasitas total (C) dari masing-masing kendaraan pengangkut, dan jumlah keseluruhan muatan tidak boleh melebihi kapasitas kendaraan yang digunakan.

C > ∑ Ds C > ∑ Ps

(29) (30)

Setelah semua Ds dan Ps memenuhi batasan kapasitas, maka ditentukan berapa residual di setiap konsumen s , sehingga dapat diketahui apakah dalam perjalanan untuk memenuhi satu lintasan terdapat muatan yang melebihi kapasitas atau tidak dengan menggunakan rumus 13 sampai 16. Setelah mengetahui berapa residual di setiap titik yang dilewati, maka perlu dihitung rata-rata residual untuk setiap titik sebagai tahap selanjutnya dalam melakukan penyisipan residual kapasitas. (Rumus 17 dan 18) Untuk menentukan unroted node yang mempunyai Delivery Oder (DU) dan Pick-Up Order (PU) dan untuk mengetahui berapa banyak derajat kebebasan untuk node pada fase berikutnya. Dan kemudian dihitung total Residual yang diperoleh dari pembobotan factor λ berdasarkan ψTD dan TC-nya (Rumus 19) Sebelumnya, karena kasus ini merupakan kasus assymetric maka dalam penentuan node mana dari unrouted node yang dapat disisipkan terlebih dahulu node tersebut diuji secara penyisipan waktu dan tentu saja berdasarkan kapasitas. Pengujian berdasarkan kapasitas untuk unrouted node untuk fase berikutnya adalah: a. Ds dan Ps dalam setiap pengiriman diurutkan berdasarkan jumlah muatan Ds dan

Ps pada setiap konsumen, di mana Ds > Ps diletakkan sebelum titik yang ditentukan dalam routed node. b. Kapasitas total yang akan terisi (Ds dan Ps) dari unrouted node sampai dengan t (fase) tertentu harus lebih kecil dari C

∑sϵtDs dan ∑sϵtPs < C (31) Karena letak unrouted node sudah ditentukan ketika akan masuk ke dalam lintasan, maka nilai total dari residual adalah ψTT ditambah dengan TC (total residual kapasitas) yang dikalikan dengan faktor pembobotan λ sehingga menjadi akan menjadi ΨRC= ΨTT+ λTC (2Cmax –Cmin) (32) HASIL Untuk menguji pengembangan metode insertion dan algoritma untuk AVRPSDP maka diadakan percobaan numerik di PT X yang merupakan distributor air minum dalam kemasan gallon “F”. Adapun PT X setiap harinya harus mengantar ke 10 pelanggan dengan menggunakan batasan jam kerja 8 jam sehari dengan lokasi kota Surabaya dan sekitarnya. Untuk kasus di PT X maka pemodelan matematika dari AVRPSDP-nya adalah sebagai berikut:

ISBN : 978-979-99735-6-6 A-30-9


Tabel 3. Tabel Model Matematika Kasus di PT X AVRPSDP V : Kelompok dari kendaraan J : Kelompok dari lokasi konsumen C : Kapasitas total kendaraan T : Total waktu yang tersedia bagi kendaraan untuk melayani satu lintasan. vij : kecepatan kendaraan dari node i ϵ Jo, j ϵ Jo, i ≠ j N : Banyaknya titik pelanggan

Notasi Parameter

V=2 J = 10 C = 100 gallon T = 8 jam (480 menit)

vij = 25 km/jam N ≤ 10

tij : Waktu tempuh dari node i ϵ Jo, j ϵ Jo, i ≠ j stj : Waktu service yang dibutuhkan untuk melayani pelanggan j ϵ J

Variabel Keputusan

st (d) j = 3 menit st (p) j = 1 menit

Fungsi Tujuan (33) (untuk meminimalkan total waktu tempuh)

(i ϵ J, j ϵ J,j ≠ i)

(34)

(i ϵ J, j ϵ J,j ≠ i) (j ϵ J)

(35) (36)

Percobaan numerik dilakukan dengan membuat rancang bangun aplikasi menggunakan spreadsheet Microsoft Excel dan hasilnya dapat dilihat dalam bentuk grafik batang dapat dilihat, jika jam kerja normal perhari adalah 8 jam (07.00 – 16.00) dengan asumsi istirahat selama satu jam, maka total waktu yang dibutuhkan untuk melayani setiap hari selama satu minggu adalah: GRAFIK WAKTU TOTAL PELAYANAN SELAMA SATU MINGGU 10 9 8 7 6 5 4 3 2 1 0 Senin

Selasa

Rabu Kendaraan 1

Kamis

Jumat

Kendaraan 2

Gambar 1. Grafik Waktu Total Pelayanan Selama Satu Mingu

Dari gambar 1 didapat bahwa dalam total penggunaan dua kendaraan perhari, terdapat dua hari di mana kendaraan membutuhkan waktu pelayanan total lebih dari T = 8 jam.

ISBN : 978-979-99735-6-6 A-30-10


Jika dibandingkan dengan rata-rata waktu tempuh pelayanan sehari dengan menggunakan metode lama didapat data sebagai berikut: GRAFIK PERBANDINGAN METODE LAMA DAN AVRPSDP DENGAN

RC

12 10 8 6 4 2 0 Senin

Selasa

Rabu

Metode Lama

AVRPSDP dgn

Kamis

Jumat

RC

Gambar 2. Grafik Perbandingan Metode Lama dan AVRPSDP dengan ΨRC

Penurunan waktu tempuh yang didapat perhari selama satu minggu dalam prosentase adalah sebagai berikut: Tabel 4. Tabel Prosentase Pengurangan Waktu Hari Senin Selasa Rabu Kamis Jumat

Metode Lama (jam) 9 8 9.25 10.25 8.75

AVRPSDP dgn RC (jam) 8.405865714 7.034541905 7.888336667 8.767862381 7.855196667

%Pengurangan Waktu 6.60% 12.07% 14.72% 14.46% 10.23%

KESIMPULAN Penelitian ini membahas mengenai mengenai problem pengambilan keputusan untuk level operasional. Pada level ini, penentuan rute mempunyai dampak besar bagi efisiensi untuk biaya transportasi. Secara lebih spesifik penentuan rute membahas mengenai problem yang ada pada Asymmetric Vehicle Routing Problem with Simultaneous Deliveries and Pick – Ups. Untuk menyelesaikan masalah ini digunakan Metode heuristik yang dikembangkan berdasarkan algorithma dari Dethloff (2001), yang menggunakan pertimbangan residual waktu terpendek dan residual kapasitas ruang yang ada pada kendaraan pengangkut. Di mana dari hal ini akan diketahui pentingnya pengurutan lokasi dalam penentuan sebuah rute. Dari pengembangan algoritma yang sudah dibuat maka diperlukan suatu aplikasi yang menunjang algoritma AVRPSDP. Oleh sebab itu maka dikembangkan rancang bangun aplikasi komputer berbasis spreadsheet dari Microsoft Office Excel. Rancang bangun system ini dibuat sebagai penunjang untuk menguji algoritma tersebut. Setelah algoritma dikembangkan dan rancang bangun aplikasi sebagai sarana pengujian sudah dibuat; maka sebagai studi kasus dibuatlah percobaan numerik dengan mengambil kasus sistem pendistribusian pada perusahaan distributor air mineral dalam kemasan gallon di PT X dan hasilnya lebih baik dibanding dengan yang digunakan saat ini.

ISBN : 978-979-99735-6-6 A-30-11


Saran Dengan menggunakan metode ini untuk penyelesaian AVRPSDP, data yang dapat diolah tidak hanya terbatas pada sepuluh data perhari saja. Karena itu ke depan diperlukan suatu perangkat lunak sebagai penunjang, di mana di dalamnya dapat menampung lebih dari jumlah data yang ada saat ini dan proses pengerjaannya dapat lebih cepat lagi, sehingga dapat membantu menyelesaikan masalah AVRPSDP yang ada di dunia transportasi saat ini. DAFTAR PUSTAKA Dethloff, Jan (2001), Vehicle Routing and Reverse Logistic: The Vehicle Routing Problem with Simultaneous Delivery and Pick-up, European Journal of Operational Research 35, hal 137 – 145. Gianpaolo, Ghiani; Laporte,Gilbert; and Musmanno, Robert (2003), Introduction to Logistics Systems Planning and Control, John Wiley and Sons Inc, USA. Nagy, Gabor, Salhi (2005), Heuristic Algorithms for Single and Multiple Depot Vehicle Routing Problems with Pickups and Deliveries, European Journal of Operational Research 162, hal 126 – 141. Rusdiansyah, Ahmad (2005), ‘Modeling and Solving Periodic Inventory Routing Problems’, Unpublished Desertation, Department of Industrial Engineering, Tokyo Institute Technology.

ISBN : 978-979-99735-6-6 A-30-12

ALGORITMA HEURISTIK UNTUK PENYELESAIAN PERMASALAHAN ASYMMETRICS VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS DELIVERIES AND PICK-UPS (AVRPSDP)

Recommend Documents