JURNAL OPTIMASI
SISTEM INDUSTRI
PENERAPAN ALGORITMA SIMULATED ANNEALING PADA PENJADWALAN DISTRIBUSI PRODUK Eri Wirdianto1, Jonrinaldi2, Betris Surya3 1) 2) 3)
Laboratorium POSI Jurusan Teknik Industri Fakultas Teknik Universitas Andalas Laboratorium Sistem Produksi Jurusan Teknik Industri Fakultas Teknik Universitas Andalas Studio TLFP Jurusan Teknik Industri Fakultas Teknik Universitas Andalas
Abstract A good logistics system can be achieved by performing various logistic activities efficiently. One of the most affected logistic components is transportation problem. The reason is that the expense of transportation can range from one-third to two-third of total logistic costs. Therefore, various ways in decreasing the expenses of transportation are needed; by optimizing the resources. The optimization of these resources can be done through efficiencies the amount of vehicles allocation and determination the route so that the minimum of total vehicles allocated and travelling distance are obtained. The distribution route at PT. PDR was unscheduled and only focused on location in the same area, so that vehicles capacities were not exploited maximally. Determination of the route represents problem of VRP (Vehicle Routing Problems). In this research, the method used to determine early solution is 2-Opt method. But solution yielded by this method is not optimal because 2-Opt method is one of heuristic method. Therefore, 2-Opt method solution is then improved by using metaheuristic method which is Simulated Annealing (SA) to get the nearly optimal route solution. SA is conducted by large amount of iterations, so that in this research java programming language is used to facilitate the achievement of the result. This research obtains total reduction of travel distance for 65,82 km and reduction of vehicles allocation by 1 unit for six-wheel vehicle and 1 unit for four-wheel vehicle with average of the vehicles capacities used is 87,75% and mean of distribution time is 5,8 hours. Keywords : Transportation, Vehicle Routing Problems, Metaheuristic, Simulated Annealing 1. Pendahuluan PT. PDR merupakan perusahaan distributor produk “W” untuk daerah pemasaran Sumatera Barat dengan depot yang terletak di kota Bukittinggi dan Padang. Daerah pemasaran untuk depot Bukittinggi meliputi daerah Bukittinggi, Payakumbuh, Padangpanjang, Batusangkar, dan sebagian daerah Pasaman. Sedangkan untuk daerah lainnya di Sumatera Barat ditangani oleh depot Padang. Perusahaan ini memasarkan produk multi item dengan sistem pesan terlebih dahulu (taking order) dan kanvas. Sistem kanvas digunakan untuk mendistribusikan barang ke retailer yang tersebar. Untuk daerah Padang, perusahaan mengalokasikan sebuah truk roda 4 untuk kanvas. Sedangkan untuk sistem taking order, sales akan mencatat semua pesanan pelanggan dalam sales order dan kemudian dilakukan input data pesanan ke komputer. Keluaran dari komputer berupa DO yang berisikan nama pelanggan, list pesanan, dan volume keseluruhan kemudian di kirim ke bagian ekspedisi untuk dikelompokkan berdasarkan area pemasarannya. Dalam melaksanakan pekerjaannya, tim ekspedisi ini bekerja hanya berdasarkan perkiraan saja dan lebih terfokus kepada
pengalokasian kendaraan untuk pelanggan pada area yang sama sehingga sering terjadi kapasitas kendaraan berlebih karena tidak adanya standar dalam melakukan pengelompokkan. Padahal seharusnya kapasitas yang berlebih ini dapat dimanfaatkan untuk mensuplai daerah yang tidak hanya berada pada satu area saja. Selain itu, pengelompokkan area ini tidak menghasilkan solusi rute. Rute yang akan ditempuh hanya ditentukan oleh sopir secara trial dan error. Namun banyaknya jumlah titik distribusi yang tersebar menyulitkan sopir dalam menentukan urutan rute yang akan ditempuh. Salah satu akibatnya adalah jarak yang ditempuh menjadi lebih panjang. Jika hal ini terus berlanjut maka biaya yang dikeluarkan perusahaan untuk mendistribusikan barang menjadi besar. Secara umum, gambaran sistem pendistribusian perusahaan ini dapat dilihat pada Gambar 1. Untuk itu perlu dilakukan penentuan rute dan penjadwalan pengiriman produk yang dapat mengatasi permasalahan diatas dengan mengoptimalkan seluruh sumber daya yang dimiliki sehingga diperoleh solusi rute yang dapat meminimasi total ongkos transportasi.
Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
7
JURNAL OPTIMASI
SISTEM INDUSTRI
ada, dan juga dengan meminimumkan biaya transportasi.
Kapasitas Kendaraan WaktuPelayanan 4unit R4
Area1
Pelanggan Salesman
Sales Order Nama Pelanggan Jenis Produk Jumlah Permintaan
Gambar 2 di bawah menunjukan dimana ada satu depot yang harus melaksanakan distribusi barang ke konsumen. Pada Gambar 2 terlihat ada 12 konsumen yang tersebar dengan jarak dan titik koordinat yang berbeda. Sedangkan pada Gambar 3 dapat melihat bahwa ada garis yang menghubungkan antara konsumen atau depot dengan konsumen yang disebut dengan rute kendaraan. Dari Gambar 3 dapat terlihat bagaimana dalam melakukan distribusi kendaraan membentuk rute tertentu, yaitu 12 konsumen dicapai dengan cara mengirimkan produk berdasarkan rute yang telah ditetapkan.
2unit R6 Delivery Order NamaPelanggan Jenis Produk Jumlah Permintaan Total volume prdukuntuk setiappelanggan
Area2
Area3
Pengelompokkanarea
TimEkspedisi
Area4
Area5
TIDAKTERDAPATURUTAN RUTEPENGIRIMAN EFISIENSI PEMANFAATAN VOLUMETRUKRENDAH
Gambar 1. Gambaran Sistem Pendistribusian PT. PDR untuk Wilayah Padang
2. Tinjauan Pustaka Menurut Council of Logistic Management (CLM) di dalam Ballou (1998) logistik merupakan suatu proses perancangan, implementasi dan pengendalian efisiensi, aliran biaya dan penyimpanan bahan baku, penyimpanan barang dalam proses, produk jadi dan informasi-informasi lain yang berhubungan dengan titik awal sampai titik akhir dari suatu proses produksi untuk memenuhi kebutuhan konsumen. Dalam sistem logistik tingkat performansi tertentu yang ingin dicapai yaitu keseimbangan antara kualitas pelayanan yang diharapkan oleh pelanggan dengan biaya-biaya yang dikeluarkan untuk mencapai tujuan perusahaan. Dua faktor utama yang terkait dengan performansi sistem logistik adalah faktor pelayanan yang menyangkut tingkat pelayanan yang diberikan kepada pelanggan, dan faktor biaya yang menyangkut besarnya biaya yang dikeluarkan perusahaan sehubungan dengan tingkat pelayanan yang diberikan kepada pelanggan. Salah satu faktor yang paling berpengaruh dalam peningkatan pelayanan kepada pelanggan adalah ketepatan waktu pengiriman. Dalam hal ini berkaitan dengan sistem distribusi perusahaan. Vehicle Routing Problems (VRP) Vehicle Routing Problem (VRP) adalah suatu pencarian solusi yang meliputi penentuan sejumlah rute, masing-masing rute dilalui oleh satu kendaraan yang berawal dan berakhir di depot asalnya, agar dapat melayani semua konsumennya dengan tetap memenuhi kendala operasional yang
8
K eterang an : D epot K onsum en
Gambar 2. Contoh Masukan VRP
K ete ran g an : Depot K o n su m e n R u te k en d araa n
Gambar 3. Contoh Keluaran VRP
Tujuan utama dari VRP adalah pencapaian solusi yang optimal. Untuk sebuah permasalahan VRP berskala besar dimana terdapat banyak konsumen yang harus dilayani, maka upaya pencarian solusi yang optimal akan memakan waktu yang sangat lama. Hal ini dikarenakan VRP merupakan NP-hard problems, dimana waktu yang dibutuhkan untuk mencari solusi permasalahan bergerak secara ekponensial seiring dengan bertambahnya konsumen. Sehingga berkembanglah berbagai macam pendekatan heuristik yang mampu menghasilkan solusi yang mendekati optimal dan dengan waktu yang relatif lebih singkat. Pendekatan heuristik ini terus berkembang
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20
JURNAL OPTIMASI
SISTEM INDUSTRI
dengan dibuatnya pendekatan kedalam prosedur yang terkomputerisasi, sehingga menjadi sangat aplikatif dan mudah digunakan. Penggunaan prosedur yang terkomputerisasi ini didalam perencanaan proses pendistribusian telah mampu menghasilkan penghematan yang cukup signifikan, yaitu berkisar antara 5-20% biaya transportasi.
S
R
S S
R
R
R
S
R
S
R R
R
R S
S
S
R R
R S
S
Depot
(a) Pengelompokan yang kurang baik (rute bersilangan)
scheduling
Depot
(b) Pengelompokan yang baik
3. Dalam pembuatan rute dimulai dari titik pemberhentian terjauh dari depot agar mendapatkan rute yang efisien. Rute yang efisien dapat dikembangkan dengan dimulai dari titik pemberhentian yang paling jauh dari depot sampai ke titik yang paling dekat. Saat titik pemberhentian terjauh dari depot teridentifikasi, kapasitas yang tersisa dari kendaraan yang telah ditugaskan sebaiknya diisi dengan memilih sekelompok titik pemberhentian yang berdekatan dengan titik pemberhentian tersebut. Setelah kendaraan ditugaskan untuk volume titik-titik pemberhentian tersebut, mulailah membuat rute dengan kendaraan lain dan identifikasi titik pemberhentian terjauh dari sisa titik-titik pemberhentian yang belum ditugaskan pada kendaraan. Terus lakukan prosedur ini sampai seluruh titik pemberhentian telah ditugaskan pada kendaraan.
1. Mengisi truk sebanyak volume pemberhentian yang akan didatangi, dimana titik-titik pemberhentian tersebut letaknya berdekatan satu sama lain. Pengelompokan titik pemberhentian yang baik dan buruk dapat dilihat pada Gambar 4.
Depot
R
Gambar 5. Pengelompokan Titik Pemberhentian Berdasarkan Hari Pengiriman
Prinsip-prinsip dalam pembuatan routing and scheduling yang baik adalah sebagai berikut [Ballou, 1998, hlm.199] :
D epot K onsum en
(a) Pengelompokan konsum en yang kurang baik
S
S
Vehicle Routing and Shedulling Vehicle routing and merupakan perluasan dari VRP.
R
S S
(b) Pengelom pokan konsum en yang baik
4. Urutan pemberhentian pada sebuah rute sebaiknya membentuk pola air mata (teardrop pattern).
Gambar 4. Pengelompokkan Titik Pemberhentian untuk Penugasan Volume Pemberhentian pada Kendaraan
Hal ini ditujukan agar tidak ada jalur yang bersilangan. Batasan time windows dan pemberlakuan aturan pengambilan barang setelah seluruh pengiriman barang dilakukan, dapat mengakibatkan jalur rute yang bersilangan. Pembuatan urutan pemberhentian yang baik dan buruk dapat dilihat pada Gambar 6.
2. Titik-titik pemberhentian yang memiliki hari pengiriman yang berbeda-beda, sebaiknya diatur untuk memperoleh pengelompokan yang lebih dekat. Titik-titik pemberhentian yang memiliki hari pengiriman yang berbeda-beda, harus dipisahkan untuk routing dan scheduling tiap harinya. Pembuatan rute dan penjadwalan harian juga harus menghindari pengelompokkan yang tumpang tindih (overlapping clusters). Hal ini akan membantu meminimalkan jumlah truk yang dibutuhkan untuk melayani seluruh titik pemberhentian. Ilustrasinya dapat dilihat pada Gambar 5.
5. Rute yang paling efisien dibangun dengan menggunakan kendaraan dengan kapasitas terbesar.
Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
Idealnya, penggunaan truk berkapasitas besar untuk melayani banyak titik pemberhentian dalam satu rute akan meminimalkan jarak tempuh kendaraan. Sehingga, truk dengan kapasitas terbesar harus dialokasikan terlebih dahulu.
9
JURNAL OPTIMASI
SISTEM INDUSTRI
metaheuristik annealing.
yaitu
algoritma
simulated
Konsumen
1. Metode Nearest Neighbour
Depot
(a) Routing yang buruk terdapat jalur yang bersilangan
Nearest neighbour adalah metode yang pertama digunakan untuk mendapatkan solusi vehicle routing problem. Metode ini sangat mudah dan cepat untuk diimplementasikan. Caranya adalah pertama kita pilih satu titik konsumen sebagai titik awal lalu bergerak ke kota berikutnya yang terdekat. Diagram alir penyelesaian permasalahan dengan menggunakan metode ini dapat dilihat pada Gambar 7.
Depot
(b) Routing yang baik - tidak ada jalur yang bersilangan (pola air mata)
Gambar 6. Contoh Penentuan Urutan Pemberhentian 6. Pengambilan barang (pickup) sebaiknya digabungkan dengan rute pengiriman barang (delivery), ketimbang pengambilan barang baru dilakukan setelah semua pengiriman dilakukan. Hal ini guna meminimalkan jalur yang bersilangan, yang dapat terjadi bila pengambilan dilakukan setelah seluruh pengiriman dilakukan. 7. Titik pemberhentian yang terpisah dari pengelompokan rute adalah kandidat terbaik untuk penggunaan alat transportasi lain. Titik pemberhentian yang terpisah dari pengelompokkan, terutama titik pemberhentian dengan volume yang kecil, dilayani dengan waktu dan biaya yang relatif besar. Untuk itu digunakan kendaraan berkapasitas kecil untuk melayani titik pemberhentian tersebut sehingga lebih ekonomis. 8. Batasan time windows titik pemberhentian yang berdekatan harus dihindari. Batasan time windows yang sangat dekat diantara pemberhentian, dapat memaksa pembentukan urutan pemberhentian jauh dari pola ideal. Oleh karena time windows tidak bersifat absolut, maka sebaiknya dilakukan negosiasi terhadap titik pemberhentian yang dipaksa untuk dilayani sesuai dengan pola routing yang diinginkan.
Metode Penyelesaian VRP Metode-metode dalam penyelesaian permasalahan VRP dapat digabungkan antara suatu metode dengan metode yang lain. Dalam penelitian ini, metode yang digunakan adalah metode heuristik yaitu nearest neighbour, k-opt, dan k-insert dikombinasikan dengan metode
10
Mulai
Pilih salah satu titik awal konsumen
Tentukan Titik Konsumen terdekat dari titik awal
Ulangi langkah 2 hingga semua titik konsumen telah dikunjungi dan memenuhi kapasitas yang ada
Hitung semua rute yang didapat
Selesai
Gambar 7. Diagram Alir Metode Nearest Neighbour 2. Metode N-Insert N-insert heuristik adalah memindahkan konsumen dari rute yang satu ke rute yang lain. Pemilihan konsumen berdasarkan informasi jarak, waktu tempuh dan time window konsumen. N-insert dapat diterima apabila dapat memberikan solusi yang lebih baik dari solusi awal seperti pada Gambar 8. 3. Metode N-Opt N-Opt yang digunakan dalam pengolahan data adalah algoritma 2-Opt. Algoritma 2-Opt adalah pertukaran yang menghilangkan 2 titik dan mengantikannya dengan hanya pasangan yang mungkin dari dua titik yang baru yang tidak memecah rute ke dalam dua siklus yang tidak bersama-sama. Algoritma 2-Opt dimulai dengan melakukan pertukaran dan berakhir ketika tidak ada lagi petukaran yang menghasilkan perbaikan. Ilustrasi mengenai 2-Opt ini dapat dilihat pada Gambar 9 dan Gambar 10.
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20
JURNAL OPTIMASI
SISTEM INDUSTRI
4. Metode Saving
Mulai
Tujuan metode saving adalah minimasi total jarak perjalanan semua kendaraan dan untuk meminimalkan secara tidak langsung jumlah kendaraan yang dibutuhkan untuk melayani semua titik pemberhentian. Asumsi awal yang digunakan pada metode ini yaitu setiap kendaraan yang berbeda berangkat dari depot untuk mengantar produk ke lokasi tertentu dan kembali lagi ke depot.
Dapatkan rute berdasarkan solusi awal
Mencari konsumen yang akan dimasukan kedalam rute yang berlainan
Tidak Feasible
5. Metode Sweep Ya
Metode sweep merupakan metode sederhana untuk menentukan rute kendaraan bahkan untuk masalah dalam skala besar. Pada beragam permasalahan, keakuratan metode ini menghasilkan ratarata error kira-kira 10%. Kerugian metode ini yaitu dalam hal cara menghasilkan rute. Proses pembentukan rute pada metode ini dibagi menjadi dua tahap dengan pemberhentian ditetapkan terlebih dahulu pada kendaraan. Kemudian ditentukan urutan rute yang akan ditempuh kendaraan. Karena proses dua tahap ini, maka masalah waktu seperti total waktu serta time windows tidak dapat diatasi dengan baik.
Hitung fungsi tujuan
Stop
Gambar 8. Diagram Alir Metode N-Insert
6. Metode Tabu Search
Gambar 9. Iustrasi Pergerakan 2-Opt
Tabu search adalah suatu strategi pencarian yang bekerja pada satu solusi pada waktu tertentu. Tabu search bekerja dengan memelihara daftar dari langkah (move) yang baru dilakukannya dan mencoba untuk tidak mengulangi langkah tersebut, terutama jika langkah tersebut tidak ada gunanya. Pada masing-masing langkah pencarian, dilakukan evaluasi semua langkah dari suatu daftar calon, dan biasanya menerima satu-satunya yang terbaik dari yang tersedia. Jika tidak ada langkah improving non tabu, algoritma dapat mengambil langkah tabu. Jika tidak ada lagi langkah yang bisa meningkatkan solusi, algoritma bisa mengambil langkah unimproving. Pada setiap langkah, algoritma mengevaluasi daftar calon move dan menggolongkan mereka ke dalam pilihan berikut:
Mulai
Tentukan 2 titik rute yang akan ditukar dengan 2 titik rute yang lain Tukarkan 2 titik rute tersebut antara satu rute dengan rute lainnya
feasible Tidak ya
Hitung fungsi tujuan
Selesai
Gambar 10. Diagram Alir Penyelesaian dengan Menggunakan 2-Opt
best improving, non tabu best improving, tabu
7. Algoritma Genetika
least-worst improving, non-tabu
Algoritma genetika (GA) adalah algoritma pencarian metaheuristik yang didasarkan atas mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah
least-worst improving, tabu
Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
11
JURNAL OPTIMASI
SISTEM INDUSTRI
variasi dari kromosom antar individu organisme. Variasi kromosom ini akan mempengaruhi laju reproduksi dan tingkat kemampuan organisme untuk tetap hidup Pada algoritma ini, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang mungkin yang dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi disebut dengan istilah kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan istilah generasi. Pada setiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang disebut dengan fungsi fitness. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (offspring) terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromosom dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari kromosom induk (parent) dan nilai fitness dari kromosom anak (offspring), serta menolak kromosomkromosom yang lainnya sehingga ukuran populasi (jumlah kromosom dalam suatu populasi) konstan. Setelah melalui beberapa generasi, maka algoritma ini akan kovergen ke kromosom terbaik.
8. Simulated Annealing (SA) Algoritma SA merupakan algoritma metaheuristik dengan konsep awal pada proses fisika. Suatu benda padat dipanaskan hingga mencair pada tingkat temperatur tertentu. Pada temperatur ini, setiap atom dapat bergerak dengan bebas. Dengan melakukan perpindahan, atom-atom ini akan memiliki banyak alternatif kombinasi struktur yang akan terbentuk apabila temperatur diturunkan. Penurunan temperatur ini harus dilakukan secara perlahan yang disebut dengan proses annealing. Hal ini bertujuan agar pada setiap tingkatan temperatur terjadi perubahan sistem hingga tercapai keseimbangan termal. Dengan proses annealing ini maka susunan atom yang terbentuk akan memiliki nilai energi yang rendah. Jika tidak demikian, keadaan akhir dari benda padat
12
tersebut akan memiliki banyak cacat karena terbentuknya struktur yang optimal secara lokal. Penurunan temperatur ini terus dilakukan hingga mencapai nilai temperatur akhir 0,010C. Pada temperatur akhir ini semua atom sudah membentuk suatu struktur kristal dan tidak terdapat lagi perpindahan atom. Pada penyelesaian permasalahan sistem distibusi, rute-rute yang akan disusun diananlogikan seperti atom-atom yang bergerak bebas. Dengan menganalogikan nilai temperatur sebagai tingkatan dari iterasi yang akan dilakukan,maka rute-rute ini akan memiliki alternatif kombinasi rute apabila dilakukan penurunan temperatur. Penurunan ini dilakukan secara perlahan sehingga alternatif yang diperoleh akan semakin banyak karena ietrasi yang dilakukan juga banyak. Pada setiap tingkatan temperatur, dilakukan pertukaran secara acak antara 2 titik rute. Hasil rute setelah pertukaran ini deisebut dengan neighbourhood atau solusi tetangga. Neighbourhood ini akan memiliki nilai solusi yang dianalogikan sebagai nilai energi yang berbeda-beda. Kemudian dipilih satu rute yang memiliki nilai solusi terendah dan dievaluasi. Apabila rute Untuk menghasilkan solusi yang dapat menyelesaikan permasalahan distribusi dengan lebih akurat dan sesuai dengan kondisi riil, sebaiknya dirancang sebuah program yang dapat mengatasi terjadinya penambahan jumlah pelanggan, keterbatasan stock gudang, penambahan jumlah produk, dan hal-hal lainnya.e hasil pertukaran ini lebih baik dari rute awal, maka langkah (move) yang diambil berwsifat memperbaiki dan rute inilah yang akan digunakan sebagai rute awal pada penurunan tingkatan iterasi selanjutnya. Konsep mekanika statistik diringkaskan dan dibandingkan dengan optimasi dapat dilihat pada Tabel 1. Tabel 1. Analogi SA dalam Sistem Termodinamika dan Pencarian Solusi di Berbagai Bidang Sistem termodinamik
Optimasi
Keadaaan Sistem
Solusi
Energi Sistem
Biaya Solusi
Perubahan Sistem
Solusi Neighbour
Min. Energi
Min. Biaya
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20
JURNAL OPTIMASI
SISTEM INDUSTRI
Langkah algoritma SA secara umum adalah [Heragu, 1997] : Langkah 1 Munculkan sebuah solusi awal S Langkah 2 Pilih sebuah nilai temperatur awal, To > 0 Langkah 3 Ulangi sebanyak N kali Munculkan sebuah S’ dari S Bandingkan S’ dengan S Cek suhu ≤ 0.01 Langkah 4 Jika suhu ≤ 0.01 penghentian telah dicapai, stop. Bila tidak turunkan suhu dan set F(T) T + 1, ulangi langkah 3 Efektifitas Simulated Annealing bergantung pada desain neighbourhood dan juga bagaimana pencarian dilakukan di dalam neighbourhood. Jika neighbourhood didesain sedemikian rupa sehingga memfasilitasi move ke solusi lebih baik dan keluar dari minimal lokal, maka prosedur SA akan memiliki kinerja yang baik. Algoritma SA ini merupakan algoritma yang cukup sederhana sehingga mudah diterapkan untuk berbagai permasalahan khususnya permasalahan distribusi. Selain itu, algoritma ini tidak memerlukan pengacakan rute secara keseluruhan untuk memperoleh alternatif kombinasi rute sehingga nilai solusi akhir dengan mudah didapatkan.
3. Metodologi Penelitian Tahapan dalam penelitian Gambar 11.
penyelesaian masalah ini dapat dilihat pada
Mulai
Penelitian Pendahuluan
Studi Literatur
- Kebijakan Distribusi saat ini pada PT. Padang Distribusindo Raya - Data awal berupa data pelanggan dan produk
- Manajemen Logistik - Transportasi - Vehicle Routing and schedulling - Nearest neighbour - 2-opt -Simulated Annealing
A
Perumusan Masalah
bagaimana menentukan rute dan jadwal pengiriman produk dengan tujuan meminimasi ongkos distribusi.
Tujuan Penelitian
menghasilkan rute dan jadwal pengiriman produk dengan memaksimalkan pemanfaatan kapasitas kendaraan dan minimasi total jarak tempuh.
Formulasi Model -Menggambarkan sistem Pendistibusian -Menentukan Ukuran Performansi -Pengumpulan Data
Penyelesaian Permasalahan Distribusi : -Penentuan Kuantiti Maksimum kendaraan - penentuan rata-rata waktu loading dan unloading -Penentuan Persentase kebutuhan volume kendaraan untuk setiap pelanggan -Algoritma Simulated Annealing
Validasi Program dan Pembahasan
Validasi Program
- Perhitungan kuantiti muat maksimum kendaraan - Perhitungan kebutuhan volume kendaraan untuk setiap pelanggan - Perhitungan Waktu Disribusi - Menentukan solusi awal dengan metode nearest neighbour - Pemotongan rute berdasarkan kapasitas dan waktu - Menggunakan metode Simulated Annealing dengan 2-opt - Hasil pemograman komputer
Pembahasan Menganalisis hasil validasi program dan solusi program
Penutup
Identifikasi Masalah
Membuat kesimpulan dan saran berdasarkan hasil penelitian yang telah dilakukan
Kapasaitas kendaraan sering berlebih dan rute tidak terjadwal dengan baik
Selesai
A
Gambar 11. Skema Metodologi Penelitian (lanjutan)
Gambar 11. Skema Metodologi Penelitian
Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
13
JURNAL OPTIMASI
SISTEM INDUSTRI
pelanggan tetap. Data jarak pelanggan dari depot dan data jarak antar pelanggan diperoleh dengan melakukan pengukuran menggunakan peta kota Padang.
4. Formulasi Model A. Ukuran Performansi Performansi rute pengiriman produk ditunjukkan dengan menggunakan fungsi objektif yang dirancang secara tepat. Dalam penelitian ini, fungsi objektif yang digunakan sebagai ukuran performansi rute pengiriman adalah total ongkos transportasi yang didefinisikan oleh total jarak tempuh kendaraan dengan pembatas jumlah kendaraan, persentase volume kendaraan, dan total waktu distribusi. Formulasi matematis dari fungsi objektif ini adalah [Carter, 2003, hlm 2] : P
P
i =0 j=0
P = jumlah pelanggan Xij = jarak dari daerah i ke daerah j
C. Penyelesaian Permasalahan Distribusi
1. Penentuan Kendaraan
B. Pengumpulan Data dalam
1. Jenis produk Data jenis produk diperlukan untuk mengetahui jenis produk yang didistribusikan oleh PT.PDR. Berdasarkan data yang diperoleh, terdapat 685 jenis produk yang didistribusikan. 2. Data volume produk Data volume produk merupakan data volume dari masing-masing produk yang diukur langsung oleh perusahaan dengan memberikan kelonggaran untuk setiap produknya. Data ini diperlukan untuk mengetahui kapasitas ruang yang terpakai dalam kendaraan. 3. Data permintaan pelanggan. Data permintaan pelanggan diperoleh dari data pemesanan yang terdapat pada masing-masing sales. Data ini akan digunakan untuk mengetahui permintaan harian pelanggan terhadap produk. 4. Data lokasi dan data jarak. Data lokasi pelanggan diperoleh dari supervisor. Data lokasi pelanggan yang digunakan hanya pelanggan yang berada dalam area Padang saja. Data ini akan digunakan untuk menentukan jarak lokasi pelanggan dari depot dan jarak antar pelanggan. Berdasarkan data yang diperoleh, perusahaan ini memiliki 250
14
Jumlah kendaraan yang dimiliki oleh PT.PDR untuk area Padang adalah sebanyak 4 unit kendaraan roda empat dan 2 unit kendaraan roda enam.
Penyelesaian Permasalaan Distribusi dengan menggunakan algoritma SA dimulai dengan menentukan kuantiti muat maksimum kendaraan, perhitungan persentase kebutuhan volume kendaraan, perhitungan waktu loading dan unloading, dan tahap algoritma SA.
min∑∑ x ij
Data yang dikumpulkan penelitian ini adalah :
5. Data jumlah dan jenis kendaraan
Kuantiti
Muat
Maksimum
Penentuan kuantiti maksimum kendaraan dilakukan untuk mengetahui jumlah maksimum suatu jenis produk dapat dimuat ke dalam kendaraan. Dalam perhitungannya, yang menjadi ukuran adalah volume produk dan volume box kendaraan. Volume produk yang digunakan adalah dalam bentuk karton kemasan karena permintaan pelanggan lebih sering dalam ukuran karton, bukan dalam pieces produk. Asumsi yang digunakan pada tahap ini adalah berat produk dapat diabaikan. Sedangkan notasi yang digunakan adalah sebagai berikut: Notasi
Keterangan
Satuan
Vp :
Volume produk
cm3/karton
Vk :
Volume kendaraan
cm3
K
Kuantiti muat maksimum kendaraan
karton
:
Kuantiti muat maksimum kendaraan didapatkan dengan membandingkan besarnya volume kendaraan dengan volume produk per karton. Secara matematis dapat dinyatakan dalam persamaan berikut ini.
[Kuantiti Muat Maksimum
kendaraan/ karton ] =
Vk Vp
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20
JURNAL OPTIMASI
2. Penentuan Rata-rata Waktu Loading dan Unloading Kendaraan Data waktu loading dan unloading kendaraan digunakan untuk menghitung waktu distribusi. Data ini merupakan suatu konstanta yang diperoleh dari rata-rata waktu yang dibutuhkan dalam melakukan loading dan unloading. Asumsi yang digunakan pada tahap ini adalah waktu loading merupak suatu nilai yang konstan dan tidak dipengaruhi oleh kondisi pelanggan. Sedangkan notasi yang digunakan adalah sebagai berikut: Notasi :
SISTEM INDUSTRI
a.
Temperatur Awal, To
Temperatur awal dianalogikan sebagai suatu kondisi awal untuk memulai iterasi. Semakin tinggi nilai temperatur awal yang diberikan maka alternatif solusi juga akan semakin banyak. Nilai yang terlalu tinggi akan menyebabkan alternatif solusi terlalu banyak tanpa memberikan perubahan yang cukup berarti. Sebaliknya temperatur awal yang terlalu rendah menyebabkan sistem tidak dapat keluar dari optimal lokal karena alternatif solusi terlalu sedikit. Dalam penelitian ini digunakan nilai temperatur 100°C dan 200°C. Solusi rute yang diperoleh dari kedua nilai temperatur ini kemudian dibandingkan dan ditentukan nilai yang memberikan solusi yang lebih stabil.
L :
Waktu Loading (jam)
b.
U :
Waktu Unloading (jam)
Wl :
Waktu Loading Kendaraan
Dalam sistem distibusi, fungsi laju pendinginan dianalogikan seberapa cepat pencapaian solusi akhir dilakukan. Laju pendinginan yang terlalu lambat menyebabkan lamanya solusi akhir diperoleh sedangkan laju pendinginan yang terlalu cepat mengakibatkan solusi yang diperoleh adalah solusi optimal lokal karena sedikitnya tingkatan iterasi yang terjadi. Dalam penelitian ini nilai α yang digunakan adalah 0,9 dan 0,95. Nilai ini digunakan karena umumnya literatur yang ada merekomendasikan kedua nilai ini sebagai nilai α.
(jam/% permintaan) WU :
Waktu UnLoading Kendaraan (jam/% permintaan)
Waktu loading dan unloading didapatkan dengan membandingkan waktu loading dengan kapasitas kendaraan. Secara matematis dapat dinyatakan dalam persamaan berikut ini.
[Waktu Loading Kendaraan ] =
Waktu Loading (jam) Kapasitas Kendaraan (%)
[Waktu UnLoading Kendaraan] = Waktu UnLoading (jam) Kapasitas Kendaraan (%) 3. Penentuan Persentase Kebutuhan Volume Kendaraan untuk Setiap Pelanggan Dari perhitungan ini dapat diketahui besarnya volume kendaraan yang digunakan berdasarkan besarnya jumlah permintaan pada hari tersebut. Dalam perhitungannya, depot sebagai titik awal akan diberi kode P000 dan setiap titik distribusi diberi urutan kode P001, P002, P003 dan seterusnya, sedangkan kapasitas kendaraan diberi kode R4 untuk kendaraan roda 4 dan R6 untuk kendaraan roda 6.
4. Algoritma Simulated Annealing Parameter yang digunakan dalam algoritma SA adalah :
c.
Laju pendinginan, α
Jumlah iterasi pada setiap tingkatan temperatur, N
Iterasi yang dilakukan pada setiap tingkatan temperatur adalah dengan cara melakukan pertukaran 2 titik secara acak sebanyak 5 kali. Dan setelah itu ditampilkan solusi yang terbaik dari kelima iterasi ini. Nilai solusi terbaik ini akan digunakan sebagai solusi awal pada penurunan temperatur selanjutnya. d.
Temperatur akhir, Tt
Nilai temperatur akhir merupakan suatu titik dimana iterasi dihentikan. Pada tahap ini dimunculkan nilai solusi akir yang merupakan solusi terbaik. Nilai temperatur akhir yang digunakan dalam penelitian adalah 0,01°C. Jadi apabila penurunan suhu telah mencapai nilai 0,01 maka iterasi dihentikan.
Secara umum, aplikasi algoritma SA terdiri dari beberapa tahap, yaitu:
Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
15
JURNAL OPTIMASI
1.
SISTEM INDUSTRI
3.
Menentukan solusi awal
Solusi awal diperoleh dengan menggunakan metode nearest neighbour. Lokasi awal sebagai lokasi dimulainya perjalanan adalah gudang, kemudian dicari daerah yang terdekat dengan gudang, setelah ditentukan daerah yang terdekat dengan gudang, kemudian ditentukan daerah-daerah lain yang terdekat. Hasil dari metode ini adalah berupa rute panjang dengan kriteria jarak terpendek. Rute ini selanjutnya dipotong dan dibentuk rute-rute kecil yang sesuai dengan kapasitas angkut kendaraan dan waktu distribusi kendaraan. Formulasi matematis untuk pemotongan rute dengan mempertimbangkan persentase kebutuhan volume kendaraan adalah [Gen dan Cheng, 1997, hlm 345] : P
max ∑ D i i =1
D = Permintaan pelanggan P = Jumlah Pelanggan Sedangkan formulasi matematis untuk pemotongan rute dengan mempertimbangkan waktu distribusi kendaraan adalah:
Pengecekan solusi secara keseluruhan
Solusi tahap kedua masih perlu dilakukan pengecekan. Pengecekan pertama adalah apakah solusi pada kedua tahap ini lebih baik dari solusi pada tahap pertama. Jika tidak lebih baik maka pencarian tahap kedua masih terus dilanjutkan. Jika solusi pada kedua tahap ini lebih baik dilakukan pengecekan tahap akhir untuk semua solusi yag dihasilkan yaitu melihat apakah suhu yang diturunkan sudah mencapai batas pencarian solusi (T akhir). Jika pencarian solusi belum mencapai T akhir maka pencarian solusi masih terus dilanjutkan. Proses pembentukan algoritma dapat dirangkum pada Gambar 12. Mulai A
Data Jarak Data Volume Produk Data Jumlah Permintaan Data Jumlah Pelanggan Data Waktu Loading dan Unloading Jenis dan kapasitas kendaraan Parameter SA
Simpan Data
Solusi Tetangga = 5
Penentuan Kuantiti Muat MaksimumKendaraan
Tentukan kuantiti muat maksimumkendaraan
Perhitungan persentase Kebutuhan Volume Kendaraan
Tentukan Persentase Kebutuhan Volume Kendaraan
waktu tempuh =
+
Ya Pilih solusi tetangga terbaik
Lebih baik dari solusi awal? ya
Hitung waktu Loading dan Unloading
Perhitungan Waktu Loading dan Unloading
Solusi awal = solusi tetangga terbaik Cari urutan solusi dengan metode jarak terdekat
Menentukan Solusi Awal
Min ∑ (L + X/V + U) Min ∑ (waktu loading tempuh + waktu unloading)
tidak
t < Takhir
Potong menjadi rute sesuai kapasitas
waktu
jarak kecepatan kendaraan
RandomSolusi
tidak ya
Hitung Jarak Tempuh
Tampilkan solusi terbaik
Hitung Waktu Distribusi
Selesai
tidak
Feasible? Pemotongan rute berdasarkan kapasitas dan waktu
2.
Menentukan solusi tetangga
Tahap selanjutnya adalah mencari solusi tetangga dari solusi yang terbaik yang dihasilkan pada tahap sebelumnya. Metode yang digunakan dalam tahap ini adalah metode 2 –opt. Solusi tetangga pada tahap ini juga akan diuji, apakah rute yang dihasilkan sesuai dengan jarak dan kapasitas. Selanjutnya pada tahap ini juga akan terdapat beberapa solusi, oleh karena itu harus dipilih salah satunya untuk menjadi solusi terbaik. Solusi terbaik pada tahap ini selanjutnya akan dibandingkan dengan solusi yang dihasilkan pada tahap satu.
16
ya Simpan sebagai solusi awal
Menggunakan Metode SA dengan 2-Opt
Kemudian lakukan uji fisibilitas yang berhubungan dengan waktu distribusi, persentase kebutuhan volume kendaraan, dan jumlah kendaraan yang digunakan terhadap rute yang dipotong.
Cari solusi tetangga menggunakan metode 2-opt
t=aT
Randomsolusi Potong menjadi rute sesuai kapasitas
hitung jarak Tempuh
hitung waktu Distribusi
Tidak
Feasible?
Ya Simpan solusi tetangga
A
Gambar 12. Diagram Alir Algoritma Pemecahan Masalah Distribusi
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20
JURNAL OPTIMASI
5. Validasi Program Untuk menghasilkan hasil rute distribusii yang mendekati optimal, maka pada algoritma ini dibutuhkan jumlah iterasi yang sangat besar. Untuk itu dirancang sebuah program dengan menggunakan bahasa pemrograman Java untuk mempermudah proses pencarian hasil. Program yang dibuat kemudian di validasi untuk mengetahui apakah sesuai dengan yang diharapkan dan dapat diaplikasikan pada sistem distribusi perusahaan. Validasi ini dilakukan dengan cara membandingkan antara perhitungan manual dengan output program. Apabila output perhitungan manual sama dengan output program, maka diasumsikan program yang dirancang telah sesuai dengan yang diharapkan. Akan tetapi apabila output perhitungan manual dan output program berbeda, maka program yang dirancang belum sesuai dengan yang diharapkan, dan perlu dilakukan koreksi kembali terhadap program yang dirancang.
Penentuan Kendaraan
Kuantiti
Muat
Maksimum
Pada penelitian di PT. PDR diasumsikan kendaraan yang digunakan dapat diisi dengan muatan penuh 100% dengan nilai kelonggaran 10%. Nilai 100% ini diberikan karena pekerja sudah ahli dalam menyusun produk dalam box kendaraan sehingga semua ruang dalam box dapat dimanfaatkan. Sedangkan nilai kelonggaran yang diberikan berdasarkan kepada adanya kemungkinan ruang tersisa pada susunan karton dengan jenis yang berbeda. Berikut ini contoh perhitungan untuk produk B024 pada kendaraan roda 4.
SISTEM INDUSTRI
Jadi untuk produk B024, jumlah maksimal yang dapat dimuat ke dalam kendaraan adalah 380 karton.
Penentuan Kebutuhan Volume Kendaraan untuk setiap Pelanggan Setelah ditentukan kuantiti muat maksimum kendaraan selanjutnya dilakukan perhitungan besarnya kebutuhan volume kendaraan untuk setiap pelanggan. Berikut ini contoh perhitungan kebutuhan volume kendaraan roda 4 untuk jenis produk B024 pada lokasi P001.
Kapasitas box roda 4
= 380 karton
Permintaan produk
= 2 karton
Persentase permintaan = 2/308 * 100% = 0,53% Berarti produk B024 untuk permintaan lokasi P001 hanya menempati 0,53% dari 90% ruang box kendaraan roda 4 yang tersedia.
Penentuan Rata-rata Waktu dan Unloading Kendaraan
Loading
Data waktu loading dan unloading kendaraan digunakan untuk menghitung waktu distribusi. Nilai ini diambil berdasarkan rata-rata waktu yang dibutuhkan pekerja untuk kegiatan loading dan unloading. Untuk kendaraan roda empat, rata-rata waktu yang dibutuhkan untuk loading adalah 0,022 jam/persen permintaan dan 0,033 jam/persen permintaan untuk unloading. Sedangkan untuk kendaraan roda enam, waktu yang dibutuhkan untuk loading adalah 0,033 jam/persen permintaan dan 0,044 jam/persen permintaan untuk unloading.
Volume produk = 23177 cm3/karton Menentukan Solusi Awal Metode Nearest Neighbour
Volume Kendaraan = Panjang box*Lebar box*Tinggi box = 3200*1800*1700 = 9792000 cm3 Dengan memberikan nilai kelonggaran 10%, maka: Vk = 0,9*9792000 = 8812800 cm3
Kuantiti Muat Maksimum Kendaraan =
8812800 = 380karton 23177
Dengan
Solusi awal didapatkan dengan menggunakan metode Nearest Neighbour yaitu memilih satu titik konsumen sebagai titik awal lalu bergerak ke kota berikutnya yang terdekat. Dari data jarak maka didapatkan solusi awal dari rute terpendek yaitu :
P0 - P201 - P190 - P129 - P130 - P125 P158 - P157 - P249 - P250 - P178 - P183 P184 - P186 - P179 - P180 - P073 - P072 -
Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
17
JURNAL OPTIMASI
P068 P056 P041 P026 P036
- P067 - P064 - P069 - P062 - P043 - P046 - P049 - P050 - P040 - P039 - P030 - P029 - P31- P033 - P035 - P024 - P037 - P038 - P216 - P0
Pemotongan Rute Kapasitas dan Waktu
P061 P051 P027 P023
SISTEM INDUSTRI
-
Berdasarkan
penurunan temperatur ini gunanya untuk menentukan berapa iterasi yang akan dilalui dari pencarian solusi, dimana :
T awal = 100°C
T akhir = 0,01 °C
Faktor T = 0,9
Dimana temperatur = Tawal * Faktor T
Berdasarkan solusi awal maka rute tersebut dipotong berdasarkan kapasitas kendaraan dan waktu yang tersedia. Kapasitas kendaraan diasumsikan 90% dan waktu distribusi tidak boleh melebihi jam kerja karyawan pukul 17:00. Maka didapatkan rute-rute sebagai berikut : Rute 1 : P0 - P201 - P190 - P129 - P130 - P125 - P158 - P157 - P249 - P250 - P0 Jarak = 3,08+3,17+2,71+0,02+0,74+2,26 +3,44+2,53+0,05+10,46 = 28,45 km
= 100 °C * 0,9 = 90 °C Pada temperatur 90°C akan dimunculkan bilangan random, bilangan random yang muncul adalah antara 1-45 berdasarkan jumlah titik distibusi pada hari tersebut, misalkan bilangan random yang muncul adalah 1 dan 5 maka indeks urutan lokasi 5 ditukar dengan indeks urutan lokasi 1 dari solusi awal nearest neigbour yaitu sebagai berikut :
Persentase permintaan = 46,37%
Rute sebelum pertukaran :
Rata-rata waktu loading = 0,022 jam/persen permintaan
P0 P158 P184 P068 P056 P041 P026 P036
Rata-rata waktu unloading jam/persen permintaan
=
0,033
Jumlah titik disribusi = 9 titik. Kecepatan rata-rata = 40 km/jam waktu distribusi =
P201 - P190 - P129 - P130 - P125 - P157 - P249 - P250 - P178 - P183 - P186 - P179 - P180 - P073 - P072 - P067 - P064 - P069 - P062 - P061 - P043 - P046 - P049 - P050 - P051 - P040 - P039 - P030 - P029 - P027 - P31- P033 - P035 - P024 - P023 - P037 - P038 - P216 - P0
-
Indeks urutan lokasi 5 adalah titik distribusi P125 dan indeks urutan 1 adalah titik distribusi P201.
jarak (waktu loading * permintaan ) + + kecepatan kendaraan
(waktu unloading * permintaan ) = (0,022*46,37)+
Rute setelah pertukaran :
28,45km 40 km / jam
+ (0,033*46,37) = 1,02 + 0,71 + 1,53 = 3,26 jam Perhitungan waktu ini feasible karena tidak melebihi jumlah jam kerja karyawan.
Menggunakan Algoritma Annealing dengan 2-opt
Simulated
Pada tahap ini metode yang digunakan adalah 2-opt yaitu pertukaran 2 titik dan menggantikannya dengan pasangan yang mungkin dari 2 titik yang baru yang tidak memecah rute berdasarkan urutan pilihan bilangan random. Solusi yang dihasilkan dengan metode 2-opt ini akan dijadikan sebagai solusi tetangga. Konsep dari Simulated Annealing penurunan temperatur secara perlahan-lahan,
18
P0 P158 P184 P068 P056 P041 P026 P036
P125 - P190 - P129 - P130 - P201 - P157 - P249 - P250 - P178 - P183 - P186 - P179 - P180 - P073 - P072 - P067 - P064 - P069 - P062 - P061 - P043 - P046 - P049 - P050 - P051 - P040 - P039 - P030 - P029 - P027 - P31- P033 - P035 - P024 - P023 - P037 - P038 - P216 - P0
-
Kemudian dilakukan pemotongan rute berdasarkan kapasitas dan batasan waktu, yaitu sebagai berikut : Rute 1 : P0 - P125 - P190 - P129 - P130 P201 - P158 - P157 - P249 - P250 - P0 Jarak = 6,81+3,55+2,71+0,02+5,99+9,89 +3,44+2,53+0,05+10,46 = 45,42 km Persentase permintaan = 46,37%
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20
JURNAL OPTIMASI
Rata-rata waktu loading = 0,022 jam/persen permintaan Rata-rata waktu unloading jam/persen permintaan
=
0,033
Jumlah titik distribusi = 9 titik.
SISTEM INDUSTRI
pencarian solusi dengan menggunakan algoritma ini maka digunakanlah bahasa pemograman Java. Tampilan awal program untuk perintah input jumlah data permintaan dapat dilihat pada Gambar 13.
Kecepatan rata-rata = 40 km/jam Waktu distribusi =
(waktu loading * permintaan ) +
jarak + kecepatan kendaraan
(waktu unloading * permintaan ) = (0,022*46,37) +
45,42km 40 km / jam
+ (0,033*46,37) = 1,02 + 1,14 + 1,53 = 3,69 jam Rute-rute ini disimpan sebagai solusi yang baru. Kemudian iterasi dilakukan kembali dengan memunculkan bilangan random yang lain. Iterasi ini terus dillakukan sampai jumlah solusi pada setiap tingkatan temperatur adalah 5 iterasi. Kemudian solusi terbaik dari 5 iterasi ini disimpan dan dilakukan kembali penurunan temperatur, dimana yang menjadi T awal adalah T akhir dari tahap sebelumnya dikali dengan faktor penurunan temperatur. Solusi awal dari temperatur ini adalah rute terbaik yang diperoleh dari temperatur sebelumnya. Namun, apabila pada temperatur sebelumnya tidak terjadi perbaikan solusi maka yang menjadi solusi awal adalah solusi awal yang diperoleh dari metode jarak terdekat.
Gambar 13. Tampilan Perintah Input Jumlah Data Tampilan program untuk perintah input data permintaan dapat dilihat pada Gambar 14.
Gambar 14. Tampilan Perintah Input Data Tampilan hasil running program berupa solusi rute yang mendekati optimal dapat dilihat pada Gambar 15.
Dimana temperatur = T awal * Faktor T = 90 °C * 0,9 = 81°C Pada temperatur 81°C ini akan dimunculkan lagi bilangan random seperti langkah yang sebelumnya dimana bilangan random yang muncul dijadikan indeks dari urutan lokasi yang akan dipertukarkan berdasarkan dari solusi awal, sehingga didapatkan lagi rute baru. Untuk cara selanjutnya sama dengan tahap sebelumnya sampai dilakukan penurunan temperatur mencapai temperatur akhir yaitu 0,01 °C. Setelah tercapainya temperatur akhir maka ditampilkan rute terbaik dengan jumlah kendaraan terkecil dan jarak terpendek. Pada Simulated Annealing ini akan dilakukan searching sesuai dengan penurunan temperatur sehingga terdapat sejumlah besar iterasi. Untuk mempermudah Penerapan Algoritma Simulated Annealing…………. (Eri Wirdianto)
Gambar 15. Hasil Running Program
19
JURNAL OPTIMASI
SISTEM INDUSTRI
6. Kesimpulan dan Saran Berdasarkan hasil penelitian penentuan rute distribusi produk dengan menggunakan algoritma simulated annealing dengan bantuan bahasa pemrograman JAVA dihasilkan rute kendaraan efisien yang dapat meminimasi ongkos distribusi. Hasil rute perhitungan pada running program ke-5 dengan tingkat temperatur 200oC dan faktor penurunan suhu 0,95 adalah: Rute I (Roda 4): P0-P216-P0129-P072-P0178-P0125-P0158P0250-P0249-P0157-P0190-P0
algoritma simulated annealing lebih akurat dalam membentuk rute kendaraan karena algoritma ini telah mempertimbangkan jarak tempuh sesuai dengan data yang ada. -
Jumlah alokasi kendaraan
Algoritma simulated annealing memberikan pengurangan jumlah alokasi kendaraan sebesar 1 unit kendaraan roda 4 dan 1 unit kendaraan roda 6. Sehingga kendaraan yang digunakan untuk mendistribusikan produk hanya 3 unit kendaraan roda 4 saja.
7. Daftar Pustaka
Rute II (Roda 4): Adi, A.H.B, Wirdianto, E., dan Agustina, B.Y., 2005, Analisis dan Penjadwalan Ulang Kegiatan Delivery di CV. "Y" Padang, Jurnal Sains dan Teknologi (ISSN 1412-5455), Vol. 5, No. 2, pp. 145-160.
P0-P186-P184-P183-P179-P180-P41-P40P68-P67-P64-P69-P62-P61-P56-P43-P51P50-P49-P46-P0 Rute III (Roda 4): P0-P201-P130-P39-P30-P29-P27-P26-P31P33-P35-P24-P23-P36-P37-P38-P73-P0
Ballou,
Rata-rata pemanfaatan kapasitas kendaraan adalah 87,75% dan rata-rata waktu distribusi adalah 5,8 jam. Hasil ini feasible karena kapasitas maksimum kendaraan yang dapat digunakan adalah 90% dari volume keseluruhan dan jam kerja karyawan adalah 8 jam. Perbandingan solusi yang diperoleh dengan menggunakan algoritma simulated annealing dan metode perusahaan adalah sebagai berikut: -
Jarak tempuh
Jarak tempuh yang dihasilkan metode perusahaan sebesar 182,59 km sedangkan jarak tempuh yang dihasilkan algoritma simulated annealing sebesar 116,77 km. Jadi, Algoritma simulated annealing memberikan hasil yang lebih baik dari metode perusahaan dengan pengurangan jarak tempuh sebesar 65,82 km. -
Waktu Distribusi
Waktu distribusi yang tersedia dapat dimanfaatkan lebih baik karena jarak tempuh yang lebih pendek. -
Waktu Pembentukan Rute
Algoritma simulated annealing terbukti memberikan waktu pembentukan rute yang lebih cepat dibandingkan dengan menggunakan metode perusahaan saat ini. Algoritma ini hanya membutuhkan waktu 9 menit untuk waktu komputasi. Selain itu
20
R.H., Business Logistics Management: Planning, Organizing and Controlling The Supply Chain, Fourth Edition, Prentice Hall, Inc. New Jersey, 1998.
Busetti, F., Simulated Annealing Overview. http:// www. geocities. com /francorbusetti /saweb. pdf. accesed July 2007 Carter, A., Design and Application of Genetic Algorithms for the Multiple Traveling Salesperson Assignment Problem. Blacksburg, Virginia, 2003. Cordeau, J.F., et.al., 2002, A guide to vehicle routing heuristic, Journal of Operational Research Society, Vol 53, pp. 512-522. Diaz,
B.D., What is VRP?, 2004,
last updated Jan 2004, accesed Mar 2004)
Gen, M., and Cheng, R., Genetic Algorithm and Engineering Design, John Wiley & Sons, Inc., Canada, 1997. Heragu, S., Facilities Design. PWS Publishing Company, Boston, 1997. Larusic, J., A Heuristic for Solving the Bottleneck Traveling Salesman http://www.cs.unb.ca/ Problem, undergrad/html/documents/JhonLaRus icThesis.pdf., accesed July 2007
Optimasi Sistem Industri, Vol. 7 No. 1, Oktober 2007: 7 – 20