4

Algoritma Genetik Untuk Penyelesaian Vehicle Routing Problem

dengan Pemerataan beban

Di PT.Patra Niaga, Anak Perusahaan PT.Pertamina Rewulu, Yogyakarta

Trio Yonathan Teja Kusuma, Taufiq Aji

Program Studi Teknik Industri, Fakultas Sains dan Teknologi

Universitas Islam Negeri Sunan Kalijaga, Yogyakarta

Abstraksi

Patra Niaga adalah sebuah anak perusahaan Pertamina, yang salah satu

tugasnya adalah mendistribusikan Bahan Bakar Minyak (BBM) ke SPBU-SPBU

yang memesan. Pengelolaan rute pendistribusian harus dilakukan untuk meminimasi

biaya. Hal lain yang cukup penting dalam pengelolan rute adalah besarnya

pemerataan beban di setiap driver. Menurut Kritikos (2007) bahwa dengan distribusi

beban yang seimbang dan ditambah dengan jumlah beberapa kali perjalanan yang

setara akan menghindari masalah ketidak puasan pengemudi.

Permasalahan VRP dapat diselesaikan salah satunya dengan menggunakan

metode heuristik. Salah satu metode heuristik yang biasa digunakan adalah metode

Algoritma Genetika.

Pendekatan yang diambil oleh Algoritma ini adalah dengan menggabungkan secara

acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan

generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan

kecocokannya atau lazim disebut fitness.

Hasil dari pengolahan data menggunakan metode Genetic Algoritma

menyatakan bahwa dengan metode ini rute yang terbentuk memiliki nilai biaya dan

pemerataan beban berturut-turut sebesar Rp1.155.740,16 dan 1,2. Bila dibandingkan

dengan rute rancangan perusahaan diliat dari segi biaya rute rancangan Algoritma

Genetik tinggi sebesar Rp 98.904,74, namun bila diliat dari segi pemeratan beban

kerja Rute rancangan Algoritma Genetik lebih rata dengan perbandingan 1:13.

Kata kunci :Algoritma Genetik, minimasi biaya, pemerataan bebankerja.

5

1. PENDAHULUAN

Pendistribusian adalah salah satu kegiatan yang tidak memberikan nilai tambah

namun dibutuhkan untuk mengantarkan produk dari produsen ke konsumen. Dengan

tidak memberikannnya nilai tambah maka sebisa mungkin biaya yang digunakan

minimal. Salah satu cara yang digunakan untuk meminimalkan biaya distribusi

adalah dengan penentuan rute pendistribusian untuk menghasilkan biaya yang minim.

Penentuan rute yang dimaksud adalah rute yang dapat memeratakan beban kerja

dan meminimasi biaya.

2. STUDI KASUS

Patra Niaga adalah sebuah anak perusahaan Pertamina, yang salah satu tugasnya

adalah mendistribusikan Bahan Bakar Minyak (BBM) ke SPBU-SPBU yang

memesan. Dalam pengoperasiannya Patra Niaga harus mendistribusikan BBM

dengan mobil tangki yang tersedia menuju SPBU-SPBU yang letaknya terpencar dan

berjarak jauh dari depot.

Permasalahan yang terjadi adalah belum ada penentuan rute yang sistematis.

Penentuan rute masih menggunakan human (daya ingat manusia), sehingga resiko

akan terjadi kesalahan sangat besar. Faktor-faktor psikologis seperti daya ingat,

kelupaan, beban mental yang dihadapi manusia akan menjadi penghambat dalam

penentuan solusi, sehingga bila dipaksakan maka solusi yang dihasilkan jauh dari

optimal.

Menurut Thot and Vigo (2002) permasalahan rute kendaraan atau disebut vehicle

routing problem ( VRP) termasuk dalam kelas NP-hard problem dalam combinatorial

optimization, sehingga sulit diselesaikan dengan metode eksak yang berlaku secara

6

umum. Menurut Mutakhiroh et.al (2007) permasalahan ini dapat diselesaikan salah

satunya dengan menggunakan metode heuristik. Salah satu metode heuristik yang

biasa digunakan adalah metode Algoritma Genetika.

Algoritma genetik (AG) adalah algoritma pencarian berbasis pada mekanisme

seleksi alam dan genetik alamiah. Suatu AG sederhana tersusun dari tiga operator:

reproduksi, pertukaran silang (crossover) dan mutasi. Satu hal yang penting AG

menganalisa bagaimana suatu fungsi obyektif (fungsi fitness) mudah atau berat untuk

AG tersebut.

Rumusan masalah yang dituangkan dalam tulisan ini adalah bagaimana rute yang

dihasilkan dari metode Algoritma Genetik yang dibangun?. Dan tulisan ini betujuan

untuk menentukan rute pendistribusian Bahan Bakar Minyak (BBM) yang mampu

meratakan beban kerja dengan minimasi biaya kirim.

3. KAJIAN LITERATUR

Permasalahan rute kendaraan atau vehicle routing problem (VRP) merupakan

permasalah optimasi yang dapat digambarkan sebagai perancangan rute pengiriman

yang optimal dari satu atau beberapa depot ke sejumlah kota atau pelanggan yang

tersebar secara geografis (Laporte, 1991)

VRP adalah sebuah problem pemrograman integer yang masuk kategori

permasalahan non polinomial hard (NP-Hard Problem), yang berarti usaha

komputasi yang digunakan akan semakin sulit dan banyak seiring dengan

meningkatnya ruang lingkup masalah.

Pada VRP armada pengangkut berperan sebagai salesperson yang memiliki

jumlah dan kapasitas tertentu. Variasi- variasi variabel yang terdapat dalam VRP

7

seperti kendala kapasitas angkut, jumlah armada angkut, batasan waktu pengiriman,

kendala kondisi riil rute yang dihadapi, serta variabel yang berkaitan dengan aktifitas

apa saja yang dilakukan saat pengiriman dan lain sebagainya membuat VRP semakin

berkembang menjadi berbagai macam jenis.

Salah satu jenis VRP yang ada adalah Split Delivery Vehicle routing problem

(SDVRP).

SDVRP adalah perluasan VRP jika tiap pelanggan dapat dilayani dengan kendaraan

yang berbeda andaikan biayanya berkurang. Perluasan ini perlu dilakukan jika jumlah

permintaan pelanggan sama besar atau lebih besar dengan kapasitas dari kendaraan

(Archetti et.al, 2001).

Menurut Mutakhiroh et.al (2007) permasalahan VRP dapat diselesaikan salah

satunya dengan menggunakan metode heuristik. Salah satu metode heuristik yang

biasa digunakan adalah metode Algoritma Genetika.

Pendekatan yang diambil oleh Algoritma ini adalah dengan menggabungkan

secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk

mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang

memaksimalkan kecocokannya atau lazim disebut fitness (Nugraha, 2008).

4. Split Delivery Vehicle routing problem (SDVRP)

Dalam VRP diasumsikan bahwa permintaan dari pelanggan kurang dari atau sama

dengan kapasitas kendaraan dan setiap pelanggan harus dilayani tepat satu kendaraan.

Namun jelas bahwa ketika permintaan pelanggan melebihi kapasitas kendaraan maka

dibutuhkan lebih dari sekali kendaraan dalam mengunjungi pelanggan yang sama.

Bahkan hal ini dapat terjadi ketika permintaan kurang dari atau sama dengan

8

kapasitas kendaraan. Ketika beberapa kendaraan harus mengantarkan pesanan

menuju beberapa pelanggan yang ditemukan persimpangan dalam rute pengiriman.

Sedangkan salah satu pelanggan berada di tengah- tengah persimpangan maka

pelanggan dilayani lebih dari satu kendaraan. Hal ini mungkin bermanfaat untuk lebih

meminimalkan biaya kirim. Permasalahan rute kendaraan ini dinamakan Split

Delivery Vehicle routing problem (SDVRP).

Gambar 1. SDVRP

Dalam SDVRP C set pelanggan harus dilayani oleh sejumlah M kendaraan yang

berkapasitas. Setiap kendaraan v ∈ M memiliki kapasitas sebesar Q dan harus

memulai dan mengakhiri perjalanan di depot yang sama. Setiap pelanggan i ∈ C

memiliki permintaan,di, yang bisa kurang dari, sama, atau lebih besar dari kapasitas

kendaraan Q. Pelanggan mungkin akan dikunjungi lebih dari sekali. Biaya untuk

melakukan perjalanan antara lokasi i dan j adalah cij. Hal ini bertujuan untuk

mememinimasi biaya pengiriman (Archetti et.al, 2001).

5. PEMERATAAN BEBAN

Di jelaskan dalam penelitian yang dilakukan oleh Kritikos (2007) bahwa dengan

distribusi beban yang seimbang dan ditambah dengan jumlah beberapa kali

perjalanan yang setara akan menghindari masalah ketidak puasan pengemudi.

9

Pemerataan beban kerja dapat didekati dengan metode pencarian nilai error pada

forecasting. Menurut Heizer dan Render (2006) kesalahan peramalan (forecast error)

pada periode t dapat didefinisikan sebagai berikut:

e(t) = A(t) – F(t) (1)

dimana: A(t) = harga aktual pada periode t

F(t) = harga peramalan pada periode t

Untuk menguji performansi hasil peramalan, digunakan ukuran kesalahan

peramalan salah satunya adalah Mean Absolute Deviation

Mean Absolute Deviation (MAD)

MAD = ∑

(4)

Dalam pemerataan beban ini pendekatan dapat dilakukan dari rumus-rumus di atas

namun nilai aktual (At) pada pemerataan beban adalah nilai beban kerja (contoh =

jarak) yang dimiliki setiap kendaraan dan nilai Forcesting (Ft) adalah nilai rata-rata

beban kerja sedangkan n adalah jumlah kendaraan yang digunakan.

6. ALGORITMA GENETIK

Terinspirasi dari teori darwin, pada tahun 1975 John Holland dan timnya

menciptakan teori Genetic Algorithm. Ide utama dibalik Genetic Algorithm ini adalah

memodelkan proses evolusi alami menggunakan warisan genetika seperti yang

diumumkan oleh Darwin. Meskipun diperkenalkan oleh John Holland, penggunaan

Genetic Algorithm untuk memecahkan persoalan yang kompleks baru

10

didemonstrasikan kemudian (pada tahun yang sama) oleh De Jong, dan kemudian

oleh Goldberg pada tahun 1989 (Bräysy, 2002).

Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara

acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan

generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan

kecocokannya atau lazim disebut fitness (Nugraha, 2008).

Representasi data yang digunakan pada algoritma genetika untuk masalah vehicle

routing adalah representasi bilangan bulat (integer). Data disajikan dalam bentuk

rangkaian barisan bilangan bulat, dimana dalam satu rangkaian mepresentasiikan

individu yang dikenal dengan sebutan kromosom. Kromosom terdiri dari kumpulan

gen yang berupa bilangan bulat. Gen dalam kromosom tersebut merepresentasikan

customer yang dikunjungi dan posisi gen merepresentasikan posisi kunjungan,

sehingga kromosom tersebut merepresentasikan rute perjalanan yang ditempuh

kendaraan.

7. Pembangunan Algoritma Genetika

Proses pada algoritma genetika diawali dengan menentukan teknik pengkodean

yang digunakan, selanjutnya dilakukan proses pembentukan populasi awal. Populasi

awal terdiri dari kumpulan kromosom yang dibentuk dengan menggunakan Random.

Jumlah kromosom pada populasi awal dibatasi sejumlah titik yang dikunjungi. Tahap

selanjutnya yaitu perhitungan nilai fitness, seleksi, crossover dan mutasi.

1) Teknik Pengkodean

Teknik pengkodean dilakukan dengan bilangan integer (bilangan bulat) yang

merepresetasikan SPBU yang memesan.

11

2) Pembangkitan Populasi Awal

Pembangkitan populasi awal dilakukan dengan metode Vehicle Based

Representation. Metode ini merupakan pengembangan dari metode random

generator. Kromosom yang akan dibuat dengan metode ini adalah kromosom yang

memiliki block-block. Block-block tersebut bertindak sebagai mobil tangki yang

digunakan. Dengan adanya block yang berkapasitas dan genome yang berkapasitas

maka secara otomatis terdapat batasan jumlah muatan (genome) yang bisa

ditampung dalam satu block. Proses pengisian genome kedalam kromosom tetap

menggunakan bilangan acak namun berbeda dari random

generator yang pengisiannya tidak memperhitungkan kapasitas. Dalam metode

ini pengisian genome kedalam kromosom dengan memperhitungkan kapasitas

Block. Jadi kromosom hasil pengolahan dengan metode ini adalah kromosom yang

memiliki N buah block yang didalam satu block terdapat N buah genome.

Block 1 Block 2

Gen 1 Gen 2 Gen 3 Gen 4

Gambar 3. Kromosom hasil Vehicle Based Representation

3) Perhitungan Nilai Fitnes

Proses ini dilakukan dengan menghitung jarak dari setiap solusi (kromosom) yang

terbentuk. Dari jarak tersebut selanjutnya dicari biaya distribusi serta pemerataan

beban.

12

a) Perhitungan biaya distribusi

Dilakukan dengan persamaan sebagai berikut :

Biaya Variabel = S + P + B + Gs + Gk

S = Tj x Sk x J ( 6 )

P = Tj x Pk ( 7 )

B = Tj / Jl x L ( 8 )

Gs = Tj – 60 x Gsk ( 9 )

Gk = Tj – 60 x Gkk (10)

Pengiriman lebih dari satu SPBU

Tj = Jda +Jab + Jdb (11)

Pengiriman satu SPBU

TJ = Jda x 2 (12)

Dimana :

S = Biaya Sewa Ban

P = Biaya Pakai Pelumas

B = Biaya Bahan Bakar

Gs = Gaji Sopir

Gk = Gaji Kondektur

Tj = Total Jarak tempuh

Sk = Biaya Sewa Ban/1 km

J = Jumlah Ban Mobil Tangki

Pk = Biaya Pelumas untuk 1 km Perjalanan

13

Jl = Jarak yang Ditempuh dengan 1 Liter Solar

L =

Biaya 1 Liter

Solar

Gsk = Gaji Sopir Untuk 1 Km Perjalanan

Gkk = Gaji kondektur untuk 1 Km Perjalanan

Jda = Jarak Depot dengan SPBU Pertama

Jab = Jarak SPBU Satu dengan SPBU lanjut

Jdb = Jarak Depot dengan SPBU terakhir

b) Pemerataan beban kerja

Perhitungan dilakukan dengan rumus MAD.

MAD = ∑

(13)

Dimana : Vd = jarak tempuh tiap kendaraan

Ad = rata-rata jarak tempuh dari semua kendaraan yang beroperasi.

c) Fitness gabungan

Fitness ini adalah penjumlahan dari fitness biaya distribusi dengan fitness

pemerataan beban. Untuk menjumlahkannya dibutuhkan faktor perkalian

unutk pemerataan beban agar satuan antar keduanya sama. Faktor perkalian ini

didapat dari perbandingan antara nilai pemerataan beban (MAD) tertinggi

dibagi dengan nilai biaya distribusi tertinggi.

Faktor Perkalian = MAD max

Biaya Distribusi max

14

Sehingga rumus yang digunakan adalah

Total Fitness = C + B*Fp

Dimana :

C = Fitnes minimasi biaya

B = Fitness pemerataan Beban

Fp = Faktor perkalian

Dengan menggunakan fitness gabungan akan terjadi konflik antara dua fungsi

tujuan tersebut. Konflik yang terjadi biasanya hubungan perbandingan

terbalik. Dimana bila salah satu fungsi bernilai tinggi maka fungsi yang lain

akan bernilai rendah begitu pula sebaliknya.

4) Seleksi

Proses seleksi dilakukan dengan metode elitisme. Cara kerja yang dilakukan

adalah dengan meranking nilai fitness yang didapat. Kemudian beberapa persen

dari kromosom yang memiliki nilai fitness yang dianggap tinggi diambil dan

sisanya diambil dari kromosom yang memilki nilai fitness yang dianggap rendah.

Gambar 4. Seleksi Elitisme

15

5) Crossover

Proses crossover dijalankan dengan metode Block Crossover. Metode ini adalah

pengembangan dari metode Order Crossover. Pada metode Order Crosssover

pemindahan genome dari kromosom lawan ke kromosom yang dicrosover

dilakukan dengan memindahkan genome yang belum ada pada kromosom tanpa

memperhatikan kapasitas mobil tangki. Dengan pemindahan seperti ini maka akan

terjadi muatan yang melebihi kapasitas mobil tangki dalam pengiriman. Untuk itu

penulis membuat cara lain dalam proses crossover, yaitu metode Block Crossover.

Proses metode ini adalah sebagai berikut, setelah diketahui probabilitas crossover

dan diketahui mulai genome ke berapa yang akan dipindah silangkan (random),

pemindahan genome dilakukan secara sekumpulan (dalam satu block) tidak per-

genome. Dan proses persilangan dilakukan dengan block yang memiliki kapasitas

sama pada kromosom lawan.

Proses pertama yang dilakukan adalah menentukan probabilitas crossover (pc).

Probabilitas crossover ini menentukan seberapa banyak kromosom yang akan

dicrossover. Disini pc ditentukan sebesar 0,5 dimana nantinya setengah dari

jumlah populasi akan mengalami crossover. Selanjutnya dilakukan proses random

untuk menentukan mulai gen keberapa dalam kromosom yang akan dipindah

silangkan. Setelah semuanya telah ditentukan maka masuk proses crossover.

16

Gambar 5. Proses Crossover

Gen-gen yang hilang selanjutnya disisipkan pada block yang kapasitasnya

mencukupi.

6) Mutasi

Proses mutasi ini digunakan sebagai langkah untuk mengacak posisi genome yang

ada pada kromosom dan bertujuan agar solusi tidak terjebak pada daerah optimum

lokal. Proses mutasi ini adalah pengembangan dari metode Insertion Mutasi.

Dimana pada insertion mutasi pemilihan genome yang akan dimutasi dilakukan

secara acak pada kromosom yang memiliki genome lengkap dan penyisipan

genome yang terpilih pun dilakukan secara random.

Dalam penelitian ini bila proses penyisipan dilakukan secara random akan terjadi

muatan mobil tangki melebihi kapasitasnya. Untuk itu maka dalam penelitian ini

terdapat proses pencarian block yang memiliki kapasitas mencukupi sebelum

Genome yang termutasi disisipkan. Dengan metode tersebut maka tidak terjadi

17

muatan yang melebihi kapasitas kendaraaan. Metode ini dinamakan Constrained

Insertion Mutation. Langkah proses mutasi ini berjalan seperti pada gambar 6.

Probabilitas mutasi sebesar 0.01. Artinya sebanyak 0.01 dari total gen pada tiap

kromosom yang dicrossover akan termutasi.

Contoh:

gen yang termutasi = (2,4,6)

Gambar 6. Proses penyisipan gen yang hilang

(pada block yang mencukupi kapasitasnya)

7) Pelestarian Kromosom Terbaik

Proses ini bertujuan untuk mempertahankan kromosom yang memiliki fitness

terbaik agar tidak hilang jika kromosom hasil crossover memiliki nilai lebih

buruk. Proses ini berjalan dengan cara mengurutkan kromosom dari nilai fitnes

terbaik (terkecil) hingga nilai fitness terburuk (terbesar). Selanjutnya kromosom

pada urutan teratas diduplicat dan kromosom hasil duplicat tersebut digunakan

untuk mengganti kromosom pada urutan terbawah.

cukup cukup

18

8) Evolusi

Proses evolusi berjalan dengan mengulang-ngulang proses seleksi, crossover,

mutasi, pelestarian kromosom terbaik. Proses ini berjalan hingga jumlah

generasi yang ditentukan.

9) Tampilan sistem yang dibangun

Gambar 9. Tampilan sistem

8. EKSPERIMENTASI

1) Jalannya sistem GA

Eksperimentasi dilakukan dengan menggunakan 20 data buatan (permintaan

SPBU), dengan jumlah kromosom awal sebanyak 100 kromosom, probabilitas

crossover sebanyak 0,5.

19

Grafik 1. Fitnes tiap generasi

Dari grafik 1 dapat dapat diketahui bahwa dengan metode gentik algoritma

yang dibangun dapat menghasilkan nilai fitnes yang semakin menurun pada

setiap generasinya. Fitness menurun karena fungsi tujuan adalah minimasi yaitu

minimasi jarak (pemerataan beban) dan minimasi biaya kirim. Sehingga

semakin kecil nilai fitness maka semakin baik.

2) Perbandingan dengan rute rancangan perusahaan

Eksperimentasi dilakukan dengan membandingkan rute hasil rancangan sistem

dengan rute hasil rancangan perusahaan. Data yang digunakan adalah data

permintaan bahan bakar minyak (BBM) jenis premium pada tanggal 3 Mei

2011.

0

1000000

2000000

3000000

1

18

35

52

69

86

10

3

12

0

13

7

15

4

17

1

18

8

tota

l fi

tnes

Nilai Fitnes Hasil Genetik Algoritma

Fitnes terbaik pada setiap generasi

20

Tabel 1. Data permintaan BBM tanggal 3 Mei 2011

21

Gambar 10. Proses eksperimentasi sistem

Tabel 2. Perbandingan rute rancangan sistem dengan rute rancangan perusahaan

22

Tabel 3. Perbandingan jumlah error dan biaya dari rute rancangan sistem dengan

rute rancangan perusahaan

Pada tabel 3 pemerataan beban ditunjukkan dengan jumlah error. Semakin kecil

error maka semakin rata (pemerataan semakin baik). Dari tabel 3 dapat diketahui

bahwa rute rancangan sistem memiliki tingkat error yang jauh lebih kecil dari pada

rute rancangan perusahaan. Namun biaya pengiriman menjadi lebih tinggi dari

pada rute rancangan perusahaan. Dari hasil ini dapat dikatakan bahwa pemerataan

beban kerja dengan minimasi biaya adalah berbanding terbalik. Dimana semakin

rata beban kerja maka biaya semakin mahal.

9. KESIMPULAN

Dari pengolahan data dan analisa disimpulkan bahwa rute hasil rancangan sistem

dapat memeratakan beban kerja dengan minimasi biaya. Minimasi biaya yang

dimaksud adalah biaya yang minimal dari pemerataan beban yang dihasilkan.

10. DAFTAR PUSTAKA

Archetti, C., Salvelsbergh, M, W, P., Speranza, M, G. 2001. Worst-Case Analysis for

Split Delivery Vehicle Routing Problems. Transportation Science, (13) : 226-228

Bräysy,O., Gendreau,M. 2005.Vehicle Routing Problem with Time Windows, Part II:

Metaheuristics. Transportation Science,(1) :119-124

Jumlah

Error

(AG) Biaya (AG)

jumlah

error

Biaya

Perusahaan

1,2 Rp1.155.740,16 14,72 Rp1.056.835,42

23

Faradian, M,I.2007. Perbandingan Penggunaan Algoritma Genetika dengan

Algoritma Konvensional pada Traveling Salesman Problem. Teknik Informatika,

Institut Teknologi Bandung, (5) : 3-10

Heizer,J.,Render, B. 2006. Operation Management. Salemba Empat, (14): 177

Kritikos, M, N., Loannou, G.2007. The balanced cargo vehicle routing problem with

time windows. Int. J. Production Economics,(9) :42-44

Kusumadewi, S., dan Purnomo, H.2005.Penyelesaian Masalah Optimasi dengan

Teknik-teknik Heuristik. Graha Ilmu, (6) :231-247

Laporte, G. 1991. The Vehicle Routing Problem: An overview of exact and

approximate algorithms. European Journal of Operational Research, (11) : 345-

347

Mutakhiroh,I.,Saptono,F.,Hasanah,N.,Wiryadinata,R. 2007. Pemanfaatan Metode

Heuristik dalam Pencarian Jalur Terpendek dengan Algoritma Semut dan

Algoritma Genetika. Seminar Nasional Aplikasi Teknologi Informasi 2007, (3) :

34-39

Nugraha, I. 2008. APLIKASI ALGORITMA GENETIK UNTUK OPTIMASI

PENJADWALAN KEGIATAN BELAJAR MENGAJAR. Teknik Informatika

ITB, (18) : 1-6

Thot,P.,Vigo,D.2002. Vehicle Routing Problem. Society for Industrial and Applied

Mathematics,(2) : 1-10