algoritma heuristik untuk penyelesaian …mmt.its.ac.id/download/semnas/semnas viii/mi/30. prosiding...

12
Prosiding Seminar Nasional Manajemen Teknologi VIII Program Studi MMT-ITS, Surabaya 2 Agustus 2008 ISBN : 978-979-99735-6-6 A-30-1 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

Upload: trinhhuong

Post on 30-Mar-2018

233 views

Category:

Documents


3 download

TRANSCRIPT

Page 1: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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

Page 2: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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 Pick-

Ups (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.

Page 3: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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

Jo : Kelompok dari konsumen dan depot, Jo = Jo {0}

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

: Muatan dari kendaraan setelah melayani pelanggan j ϵJ

: Variable yang digunakan untuk menghindari subtours, dapat diartikan sebagai

posisi dari node j ϵ J dalam rute

xijv : 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) (2)

(Melayani pelanggan hanya satu kali)

Page 4: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

(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) (7)

(j ϵ J) (8)

(kapasitas kendaraan setelah pelanggan pertama dan akhir dari rute)

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

( j ϵ J) (10)

(i ϵ J0, j ϵ J0, k ϵ K) (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 pick-

ups 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.

Page 5: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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

l q : 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:

RD(0) = (13)

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

Page 6: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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.

Page 7: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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 Kapasitas

Lintasan aliran lalu lintas menyebabkan

ketidaksimetrisan jarak � dengan asumsi kecepatan

konstan maka waktu tempuh titik ke titik menjadi

tidak simetris

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 AVRPSDP

Parameter T : Total waktu yang tersedia bagi kendaraan untuk

melayani satu lintasan.

vij : kecepatan kendaraan dari node i ϵ Jo, j ϵ Jo, i ≠ j

Variabel

Keputusan

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) (24)

(j ϵ J) (55)

Page 8: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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.

Page 9: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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 (29)

C > ∑ Ps (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:

Page 10: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

Tabel 3. Tabel Model Matematika Kasus di PT X

AVRPSDP

Notasi V : Kelompok dari kendaraan

J : Kelompok dari lokasi konsumen

V = 2

J = 10

Parameter 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

C = 100 gallon

T = 8 jam (480 menit)

vij = 25 km/jam

N ≤ 10

Variabel

Keputusan

tij : Waktu tempuh dari node i ϵ Jo, j

ϵ Jo, i ≠ j

stj : Waktu service yang dibutuhkan

untuk melayani pelanggan j ϵ J

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) (35)

(j ϵ J) (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:

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.

0

1

2

3

4

5

6

7

8

9

10

Senin Selasa Rabu Kamis Jumat

GRAFIK WAKTU TOTAL PELAYANAN SELAMA SATU MINGGU

Kendaraan 1 Kendaraan 2

Page 11: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

Jika dibandingkan dengan rata-rata waktu tempuh pelayanan sehari dengan

menggunakan metode lama didapat data sebagai berikut:

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

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.

0

2

4

6

8

10

12

Senin Selasa Rabu Kamis Jumat

GRAFIK PERBANDINGAN METODE LAMA DAN AVRPSDP DENGAN �RC

Metode Lama AVRPSDP dgn �RC

Hari Metode Lama (jam) AVRPSDP dgn �RC (jam) %Pengurangan Waktu

Senin 9 8.405865714 6.60%

Selasa 8 7.034541905 12.07%

Rabu 9.25 7.888336667 14.72%

Kamis 10.25 8.767862381 14.46%

Jumat 8.75 7.855196667 10.23%

Page 12: ALGORITMA HEURISTIK UNTUK PENYELESAIAN …mmt.its.ac.id/download/SEMNAS/SEMNAS VIII/MI/30. Prosiding Kristina... · VRPSDP penyelesaiannya dilakukan dengan metode heuristic, Penyelesaian

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

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

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.