USULAN PENELITIAN TUGAS AKHIR

TOPIK/JUDUL TUGAS AKHIR

PENERAPAN ANT COLONY SYSTEM PADA VEHICLE ROUTING PROBLEM UNTUK

MENENTUKAN RUTE DISTRIBUSI PADA PT. RISKY AGIE

Maksud dan Tujuan Penelitian

Memperoleh rute distribusi yang terpendek sehingga dapat meminimalkan biaya distribusi

menggunakan Algoritma Ant Colony System pada PT. Risky Agie

Oleh:

Yoan Ariesta

063.08.013

Laboratorium:

Sistem dan Simulasi Industri

JURUSAN TEKNIK INDUSTRI

FAKULTAS TEKNOLOGI INDUSTRI

UNIVERSITAS TRISAKTI

2012

Pembimbing utama Paraf Pembimbing

DR. Dra.Pudji Astuti, MT

1. Latar Belakang

Seiring dengan perkembangan zaman di Indonesia maka semakin berkembang

pula teknologi yang digunakan untuk memudahkan kinerja manusia. Sebagai contoh

dalam hal memasak, dulu sekali orang Indonesia memakai kayu bakar. Namun hal ini

sangatlah merepotkan karena mereka harus mencari kayu atau ranting-ranting pohon.

Lalu dengan bertambahnya waktu mucullah kompor minyak. Hal ini dianggap jauh

lebih praktis karena kompor ini hanya menggunakan minyak tanah, sumbu dan api

sebagai bahannya. Karena persediaan cadangan minyak bumi di Indonesia makin

menipis akhirnya pada awal tahun 2007 pemerintah RI mengeluarkan kebijakan

konversi minyak tanah ke gas. Hal ini tentunya berakibat melonjaknya permintaan

gas. Oleh karena itu pendistribusian yang baik dan tepat waktu merupakan salah satu

hal yang penting untuk memenuhi kebutuhan pelanggan.

PT. RISKY AGIE memiliki armada angkut untuk melayani pengiriman gas

elpiji ke sub-sub agen dalam Kota dan setiap armada melayani 4-7 titik sub-sub agen

tersebut. Selama ini pertimbangan pengemudi dalam rute mendistribusikan gas-gas

elpiji ke sub-sub pelanggan hanya berdasarkan instuisi acak pengemudi dan tidak

mempertimbangkan banyaknya barang yang diangkut ke lokasi serta tidak

mempertimbangkan apakah rute yang ditempuh sudah memiliki jarak tempuh yang

efisien atau belum. Oleh sebab itu perlu ditentukan rute pendistribusian yang efisien

sehingga perusahaan dapat memperoleh jarak tempuh yang terpendek sekaligus dapat

meminimasi biaya transportasi. Masalah transportasi ini dimodelkan sebagai

permasalahan Vehicle Routing Problem (VRP). Beberapa metode yang digunakan

untuk menyelesaikan VRP antara lain adalah dengan pendekatan eksak, heuristik dan

metaheuristik. Dibandingkan dengan heuristik klasik, metaheuristik menunjukan

pencarian solusi yang lebih efektif dan teliti. Ant Colony System merupakan metode

terbaik yang dapat diimplementasikan pada VRP dibanding metaheuristik lain.

2. Rumusan Masalah

Permasalahan yang terjadi pada PT. Risky Agie adalah rute pendistribusian

gas elpiji dari PT. Risky Agie ke sub-sub agen yang masih kurang efektif dan

efisien dikarenakan pendistribusian gas elpiji berdasarkan instuisi acak pengemudi

sehingga rute pendistribusian belum optimal atau rute yang yang dilewati masih

belum terpendek. Akibatnya biaya distribusi atau biaya transportasi pun ikut

melonjak dan waktu tempuh untuk mengantarkan gas ke sub-sub agen menjadi lebih

lama.

3. Tujuan Penelitian

Tujuan yang ingin dicapai dalam penelitian ini adalah:

1. Memperoleh rute pendistribusi gas elpiji yang efisien dan optimal,

menggunakan model Vehicle Routing Problem dengan metode

Algoritma Ant Colony.

2. Meminimasi biaya distribusi gas elpiji pada PT. Risky Agie

4. Studi Literatur

4.1 Definisi dan jenis Vehicle Routing Problem

VRP dapat disebut juga Vehicle Schedulling Problem, berhubungan dengan

distribusi barang jadi antara depot dengan pengguna akhir (konsumen). Model dan

algoritmanya dapat digunakan secara efektif tidak hanya untuk pengiriman dan

pengambilan barang, tetapi juga dapat diaplikasikan untuk masalah transportasi

sehari-hari.

Vehicle Routing Problem (VRP) adalah suatu metoda yang digunakan untuk

menetukan rute untuk suatu armada kendaraan baik dari single depot ataupun multiple

depot sehingga dapat melayani pelanggan yang tersebar secara geografis.

Distribusi barang meliputi pelayanan sejumlah konsumen, pada waktu tertentu, oleh

jumlah kendaraan, berasal dari 1 atau lebih depot, dikendarai sejumlah

pengemudi/kru, dan pergerakannya menggunakan suatu jaringan jalan (road network).

Salah satu definisi VRP adalah suatu pencarian solusi yang meliputi penentuan

sejumlah rute, masing-masing rute dilalui oleh 1 kendaraan yang berawaal dan

berakhir di depot asal, agar dapat melayani semua konsumennya dengan tetap

memenuhi kendala operasional yang ada, juga dengan meminimumkan biaya

transportasi global (P.toth & D. Vigo, 2002)

VRP pada aplikasinya merupakan salah satu bagian dari permasalahan perutean

(routing problem). Pengembangan dari persoalan di atas menghasilkan beberapa jenis

(variant) VRP, antara lain :

1. Capacitated Vehicle Routing Problem (CVRP), jenis dari VRP dimana setiap unit

kendaraan mempunyai kapasitas angkut barang yang sama. Jumlah permintaan

barang yang dapat dilayani oleh setiap kendaraan tidak boleh melebihi dari

kapasitas angkut barang kendaraan.

2. Vehicle Routing Problem with Time Widows (VRPTW), jenis dari VRP dimana

masing-masing pelanggan dan tempat pemberhentian memiliki interval waktu

tertentu dalam melakukan pengambilan dan pengiriman barang.

3. Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), jenis dari

VRP yang merupakan gabungan dari CVRP dan VRPTW.

4. Multiple Depot Vehicle Routing Problem (MDVRP), jenis dari VRP dengan lebih

dari satu depot.

5. Periodic Vehicle Routing Problem (PVRP), jenis dari VRP dimana pengiriman

barang dapat dilakukan dalam beberapa hari (lebih dari 1 hari).

6. Split Delivery Vehicle Routing Problem (SDVRP), jenis dari VRP dimana satu

pelanggan dapat dilayani oleh lebih dari satu unit kendaraan.

7. Vehicle Routing Problem with Backhauls (VRPB), jenis dari VRP dimana antara

pengambilan barang dan pengiriman barang dapat dilakukan pada setiap tempat

pemberhentian yang diberikan sepanjang rute. Secara khusus, pengambilan barang

tidak dapat dilakukan sampai semua pengiriman selesai dilakukan.

4.2 Definisi Ant Colony

Algoritma Semut diadopsi dari perilaku koloni semut yang dikenal sebagai sisetem

semut (Dorigo, 1996). Secara alamiah koloni semut mampu menemukan rute terpendek

dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni semut dapat

menemukan rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada

lintasan yang telah dilalui. Semakin banyak semut yang melalui suatu lintasan, maka akan

semakin jelas bekas jejak kakinya. Hal ini akan menyebabkan lintasan yang dilalui semut

dalam jumlah sedikit, semakin lama akan semakin ber4kurang kepadatan semut yang

melewatinya, atau bahkan akan tidak dilewati sama sekali. Sebaliknya lintasan yang dilalui

semut dalam jumlah banyak, atau bahkan semua semut akan melalui lintasan tersebut.

Gambar 4.1 Perjalanan semut menemukan sumber makanan

dari gambar 4.1a di atas menujukkan ada dua kelompok semut yang akan

melakukan perjalanan. Satu kelompok bernama L yaitu kelompok yang berangkat dari arah

kiri merupakan sarang semut dan kelompok lain ytang bernama kelompok R yang

berangkat dari kanan yang merupakan sumber makanan. Kedua kelompok semut dari titik

berangkat sedang dalam posisi pengambilan keputusan jalan sebelah mana yang akan

diambil. Kelompok semut L membagi dua kelompok lagi. Sebagian melalui jalan bawah.

Hal ini juga berlaku pada kelompok semut R. Gambar 4.1b dan gambar 4.1c menunjukkan

bahwa kelompok semut berjalan pada kecepatan yang sama dengan meninggalkan feromon

atau jejak kaki di jalan yang telah dilalui. Feromon yang ditinggalkan oleh kumpulan semut

yang melalui jalan atas telah mengalami banyak penguapan karena semut yang melalui

jalan atas berjumlah lebih sedikit daripada jalan yang di bawah. Hal ini dikarenakan jarak

yang ditempuh lebih panjang daripada jalan bawah. Sedangkan feromon yang berada di

jalan bawah, penguapannya cenederung lebih lama. Karena semut yang melalui jalan

bawah lebih banyak daripada semut yang melaui jalan atas. Gambar 4.1d menunjukkan

bahwa semut-semut yang lain pada akhirnya memutuskan untuk melewati jalan bawah

karena feromon yang ditinggalkan masih banyak. Sedangkan feromon pada jalan atas

sudah banyak menguap sehingga semut-semut tidak memilih jalan atas tersebut. Semakin

banyak semut yang melalui jalan bawah maka semakin banyak semut yang mengikutinya.

Demikian juga dengan jalan atas, semakin sedikit semut yang melalui jalan atas,

maka feromon yang ditinggalkan semakin berkurang bahkan hilang. Dari sinilah kemudian

terpilihlah jalur terpendek antara sarang dan sumber makanan.

Dalam algoritma semut, diperlukan beberapa variabel dan langkahlangkah untuk

menentukan jalur terpendek, yaitu:

Langkah 1 :

a. Inisialisasi harga parameter-parameter algoritma.

Parameter-parameter yang di inisialisasikan adalah :

1. Intensitas jejak semut antar kota dan perubahannya (τij)

2. Banyak kota (n) termasuk koordinat (x,y) atau jarak antar kota (dij)

3. Kota berangkat dan kota tujuan

4. Tetapan siklus-semut (Q)

5. Tetapan pengendali intensitas jejak semut (α), nilai α ≥ 0

6. Tetapan pengendali visibilitas (β), nilai β ≥ 0

7. Visibilitas antar kota = 1/dij (ηij)

8. Banyak semut (m)

9. Tetapan penguapan jejak semut (ρ) , nilai ρ harus > 0 dan < 1 untuk

mencegah jejak pheromone yang tak terhingga

10.Jumlah siklus maksimum (NCmax) bersifat tetap seloama algoritma

dijalankan, sedangkan τij akan selalu diperbaharui harganya pada setiap

siklus algoritma mulai dari siklus pertama (NC=1) sampai tercapai jumlah

siklus maksimum (NC= NCmax) atau sampai terjadi konvergasi.

b. Inisialisasi kota pertama setiap semut.

Setelah inisialisasi τij dilakukan, kemudian m semut ditempatkan pada kota

pertama tertentu secara acak.

Langkah 2 :

Pengisian kota pertama ke dalam tabu list. Hasil inisialisasi kota pertama setiap

semut dalam langkah 1 harus diisikan sebagai elemen pertama tabu list. Hasil dari langkah

ini adalah terisinya elemen pertama tabu list setiap semut dengan indeks kota tertentu, yang

berarti bahwa setiap tabuk(1) bisa berisi indeks kota antara 1 sampai n sebagaimana hasil

inisialisasi pada langkah 1.

Langkah 3 :

Penyusunan rute kunjungan setiap semut ke setiap kota. Koloni semut yang sudah

terdistribusi ke sejumlah atau setiap kota, akan mulai melakukan perjalanan dari kota

pertama masing masing sebagai kota asal dan salah satu kotakota lainnya sebagai kota

tujuan. Kemudian dari kota kedua masing-masing, koloni semut akan melanjutkan

perjalanan dengan memilih salah satu dari kotakota yang tidak terdapat pada tabuk sebagai

kota tujuan selanjutnya. Perjalanan

koloni semut berlangsung terus menerus sampai semua kota satu persatu dikunjungi atau

telah menempati tabuk. Jika s menyatakan indeks urutan kunjungan, kota asal dinyatakan

sebagai tabuk(s) dan kota-kota lainnya dinyatakan sebagai {N-tabuk}, maka untuk

menentukan kota tujuan digunakan persamaan probabilitas kota untuk dikunjungi sebagai

berikut :

dan

dengan i sebagai indeks kota asal dan j sebagai indeks kota tujuan.

Langkah 4 :

a. Perhitungan panjang rute setiap semut.

Perhitungan panjang rute tertutup (length closed tour) atau Lk setiap

semutdilakukan setelah satu siklus diselesaikan oleh semua semut. Perhitungan ini

dilakukan berdasarkan tabuk masing-masing dengan persamaan berikut :

dengan dij adalah jarak antara kota i ke kota j yang dihitung berdasarkan

persamaan :

b. Pencarian rute terpendek

Setelah Lk setiap semut dihitung, akan didapat harga minimal panjang rute tertutup

setiap siklus atau LminNC dan harga minimal panjang rute tertutup secara

keseluruhan adalah atau Lmin.

c. Perhitungan perubahan harga intensitas jejak kaki semut antar kota.

Koloni semut akan meninggalkan jejak-jejak kaki pada lintasan antar kota yang

dilaluinya. Adanya penguapan dan perbedaan jumlah semut yang lewat,

menyebabkan kemungkinan terjadinya perubahan harga intensitas jejak kaki semut

antar kota. Persamaan perubahan ini adalah :

dengan k Δτij adalah perubahan harga intensitas jejak kaki semut antar kota setiap

semut yang dihitung berdasarkan persamaan:

untuk (i,j) ∈ kota asal dan kota tujuan dalam tabuk Δτij = , untuk (i,j) lainnya.

Langkah 5 :

a. Perhitungan harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya. Harga

intensitas jejak kaki semut antar kota pada semua lintasan antar kota ada kemungkinan

berubah karena adanya penguapan dan perbedaan jumlah semut yang melewati. Untuk

siklus selanjutnya, semut yang akan melewati lintasan tersebut harga intensitasnya telah

berubah. Harga intensitas jejak kaki semut antar kota untuk siklus selanjutnya dihitung

dengan persamaan :

τij = ρ τij + Δτi⋅

b. Atur ulang harga perubahan intensitas jejak kaki semut antar kota.

Untuk siklus selanjutnya perubahan harga intensitas jejak semut antar kota perlu diatur

kembali agar memiliki nilai sama dengan nol.

Langkah 6 :

Pengosongan tabu list, dan ulangi langkah 2 jika diperlukan. Tabu list perlu dikosongkan

untuk diisi lagi dengan urutan kota yang baru pada siklus selanjutnya, jika jumlah siklus

maksimum belum tercapai atau belum terjadi konvergensi. Algoritma diulang lagi dari

langkah 2 dengan harga parameter intensitas jejak kaki semut antar kota yang sudah

diperbaharui.

5. Pembatasan Masalah

Pembatasan masalah dari penelitian ini digunakan agar masalah yang diteliti

lebih terarah dan terfokus sehingga penelitian dapat dilakukan sesuai dengan apa

yang direncanakan dan memberikan hasil yang optimal. Batasan masalah yang

digunakan pada penelitian ini adalah sebagai berikut:

1. Penelitian dilakukan di PT. Risky Agie yang berlokasi di Jalan Kapin

Raya Nomor 6A RT 09 RW 004 Kelurahan Jatibening Bekasi

2. Pendistribusian gas dikirim ke Dalam Kota meliputi Jakarta, Bekasi

3. Dalam hal kemacetan, waktu dianggap linear dengan jarak.

4. Permintaan outlet yang tidak dapat dilayani pada satu rute dan pada satu

hari makan akan didistribusikan pada hari berikutnya.

5. Kondisi armada dianggap sama untuk semua dan jumlahnya tetap untuk

satu periode

6. Perancangan model pendistribusian menggunakan Alogoritma Ant

Colony System

6. Metodologi Penelitian

1. Penelitian Pendahuluan

Penelitian pendahuluan adalah langkah awal sebelum melanjutkan ke

tahapan-tahapan selanjutnya. Penelitian pendahuluan dilakukan agar kita mengerti

apa maksud penelitian yang dilakukan, dan apa/siapa yang mengarahkan

penelitian. Penelitian ini dilakukan pada di PT. Risky Agie yang berlokasi di Jalan

Kapin Raya Nomor 6A RT 09 RW 004 Kelurahan Jatibening Bekasi

2. Identifikasi Masalah

Identifikasi masalah memuat rincian pernyataan tentang cakupan atau topic-

topik pokok yang akan diungkap/digali dalam penelitian ini. Identifikasi diajukan

unutk mengetahui gambaran apa yang akan diungkapkan di lapangan. Setelah

mengamati langsung dan mewawancarai pemilik PT. Risky Agie maka diketahui

bila masalah yang ada di PT. Risky Agie adalah pendistribusian gas ke sub-sub

agen agar sampai tempat waktu dengan rute terpendek dan biaya transportasi yang

minimum.

3. Studi Pustaka/Studi Literatur

Studi pustaka yaitu mengadakan penelitian dengan cara mempelajari dan

membaca literature-literatur yang ada hubungannya dengan permasalahan yang

menjadi objek penelitian yaitu menelusuri teori-teori yang berkaitan dengan system

distribusi, penjadwalan dan penyusunan rute distribusi dari internet, buku dan

jurnal.

4. Tujuan Penelitian

Sasaran hasil yang ingin dicapai dalam penelitian ini yaitu menemukan

memperoleh rute distribusi yang optimal dengan metode Ant Colony System dan

meminimalkan biaya pendistribusian gas.

5. Pengumpulan Data

Pengumpulan data dilakukan untuk memperoleh informasi yang dibutuhkan

dalam rangka mencapai tujuan penelitian. Adapun metode pengumpulan data yang

digunakan adalah wawancara dengan pihak terkait, melakukan pengamatan

langsung pada PT. Rizky Agie dan data-data yang ada pada PT. Risky Agie.

Adapun data-data yang dikumpulkan pada penelitian kali ini adalah:

1. Data umum perusahaan

Sejarah perusahaan

Visi dan misi perusahaan

Struktur organisasi perusahaan

Jumlah tenaga kerja

Pengaturan jam kerja

2. Data pendistribusian produk

Lokasi PT. Risky Agie

Lokasi sub-sub agen

Data pengiriman barang

Data jarak PT. Risky Agie ke sub-sub agen

Data jarak antar sub-sub agen

Data jumlah armada

3. Data waktu tempuh kendaraan

6. Pengolahan Data

Pengolahan data dilakukan apabila seluruh data-data Pendukung telah

terkumpul. Adapun tahap-tahap dalam pengolahan data ini adaalah

mengumpulakjn wilayah-wilayah pengiriman dan perhitungan dengan

menggunakan Algoritma Ant Colony.

7. Analisa

Pada bagian analisis data diuraikan proses pelacakan dan pengaturan secara

sistematis data-data dari wawancara, observasi dan data-data dari PT. Risky Agie.

Lalu dari hasil pengolahan data yang ada dilakukan analisa hasil apakah rute

usulan dengan menggunakan Ant Colony System lebih baik dari rute yang

digunakan sebelumnya yang berdasarkan intuisi acak pengemudi.

8. Kesimpulan dan Saran

Kesimpulan merupakan bagian akhir dari penelitian ini dan merupakan

jawaban dari tujuan penelitian serta merupakan ringkasan dari penelitian.

Penulispun memberikan saran atau usulan dari penelitian untuk perusahaan agar

menjadi perusahaan yang lebih baik lagi.

Gambar 6.1 Flowchart Metodologi Penelitian

Gambar 6.1 Flowchart Pencarian Rute Distribusi dengan Ant Colony System

VII. Rencana Penelitian

UraianStudi PenelitianPemilihan PembimbingIdentifikasi VariabelWawancara PerusahaanPengumpulan DataPenulisan laporan (Bab 1-3)Pengolahan DataAnalisisPengumpulan DataPengolahan DataPeng Data dan ImplementasiPenulisan laporan (Bab 4-5)KesimpulanPerbaikan secara keseluruhanPengesahan

AgustusMaret April Mei Juni Juli

VII. Daftar Pustaka

1. P. Toth D. Vigo. An Overview OF Vehicle Routing Problems, 2002.

2. Dorigo M., V. Maniezzo & A. Colorni The Ant System: Optimization by a

colony of cooperating agents, IEE transactions on Systems, Man, and

Cybernectics-Part B, Vol. 26 No.1 , 1996.

3. Dorigo, M & Gambardella, L.M. Ant Colony System: A Cooperative Learning

Approach to The Travelling Salesman Problem. 1996.

1. http://edvinramadhan.blogspot.com/2010/10/sekilas-tentang-algoritma-semut-

antnet.html