JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7
1
Penjadwalan dan Penentuan Rute Kendaraan pada Industri Bahan Kimia Menggunakan Kombinasi Algoritma Genetika dan Algoritma Pencarian Tabu Maya Sagita Walalangi, Arif Djunaidy Jurusan Sistem Informasi, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected]
Abstrak— Distribusi produk yang dihasilkan oleh sebuah perusahaan memerlukan penjadwalan dan penentuan rute kendaraan yang tepat agar produk tersebut dapat disebarkan dan dipasarkan kepada konsumen akhir sesuai dengan yang diinginkan. Salah satu masalah yang sulit diselesaikan dalam penjadwalan kendaraan untuk proses distribusi produk adalah penentuan ketersedian dan kesiapan kendaraan yang sesuai dengan batasan yang telah ditentukan. Dalam tugas akhir ini dikembangkan sebuah aplikasi untuk membantu sebuah industri bahan kimia dalam melakukan penentuan rute dan penjadwalan kendaraan sesuai dengan batasan-batasan yang ditentukan oleh perusahaan dengan menggunakan kombinasi algoritma genetika dan algoritma pencarian tabu. Algoritma genetika digunakan untuk menghasilkan jadwal dan rute kendaraan secara umum. Sedang algoritma pencarian tabu digunakan untuk mengoptimumkan jadwal dan rute yang dibentuk oleh algoritma genetika. Kombinasi dari kedua algoritma diharapkan mampu mengoptimumkan penggunaan kendaraan, meminimumkan biaya pengiriman, dan mengupayakan ketepatan waktu pengiriman. Hasil uji coba aplikasi yang menggunakan kombinasi algoritma genetika dan algoritma pencarian tabu mampu memenuhi batasan-batasan yang ditentukan oleh perusahaan. Penjadwalan dan penentuan rute kendaraan yang melibatkan algoritma kombinasi memberikan hasil biaya yang lebih minimum dibandingkan dengan yang dihasilkan oleh salah satu algoritma yang dikombinasikan. Namun demikian, dari aspek waktu komputasi yang diperlukan, algoritma pencarian tabu membutuhkan waktu komputasi yang tercepat. Kata Kunci—Penjadwalan dan penentuan rute kendaraan, algoritma genetika, algoritma pencarian tabu, kombinasi algoritma genetika dan algoritma pencarian tabu.
I. PENDAHULUAN
D
ISTRIBUSI merupakan kegiatan yang tidak lepas kaitannya dengan aktifitas memindahkan suatu barang atau material dari perusahaan terkait hingga sampai ke pihak pelanggan akhir[17]. Distribusi merupakan suatu aktivitas penting bagi perusahaan, karena dengan adanya proses ini, produk yang dihasilkan oleh perusahaan dapat disebarkan dan
dipasarkan sampai ke konsumen akhir. Untuk memuaskan konsumen, salah satu hal yang dilakukan oleh perusahaan yaitu berusaha mengirimkan produk atau permintaan konsumen dengan tepat. Oleh karena itu proses distribusi juga menjadi proses yang penting bagi perusahaan. Proses distribusi yang dilakukan dibagi-bagi dalam kelompok-kelompok kendaraan yang akan mengirimkan produk ke pelanggan melalui rute yang ditentukan oleh perusahaan. Agar proses distribusi berjalan lancar maka dibutuhkan suatu perencanaan untuk dapat menentukan jadwal distribusi dan rute kendaraan yang tepat dan sesuai. Beberapa masalah yang terjadi karena penjadwalan dan penentuan rute kendaraan yang kurang tepat yaitu terjadinya keterlambatan dan muncul waktu tunggu karena estimasi waktu layanan mulai kendaraan berangkat sampai bongkar muatan di konsumen tidak sesuai. Keterlambatan di satu konsumen akan mempengaruhi waktu layanan pada konsumen yang selanjutnya jika dalam satu rute pengiriman yang dilalui kendaraan pengangkut terdapat lebih dari satu konsumen. Jika terjadi keterlambatan maka yang akan dirugikan nantinya adalah konsumen. Selain itu hal penting yang patut dipikirkan adalah berkenaan dengan utilitas kendaraan yang merupakan tingkat penggunaan kendaraan pada saat proses pengiriman produk berlangsung. Utilitas kendaraan erat kaitannya dengan penjadwalan dan penentuan rute karena dalam proses ini ditentukan kendaraan mana saja yang harus digunakan untuk pengiriman barang yang disesuaikan dengan jumlah produk yang akan dikirimkan pada tiap harinya agar dapat memenuhi permintaan pelanggan. Ada kalanya saat kendaraan telah dijadwalkan, masih ditemukan masalah. Faktanya, kendaraan yang telah dijadwalkan tiap harinya belum tentu berada pada kondisi yang bagus karena ada beberapa kendaraan yang seharusnya dilakukan perawatan atau diperbaiki. Terkadang perawatan tidak bisa dilakukan karena kendaraan harus digunakan untuk memenuhi permintaan. Hal ini dapat membahayakan pekerja karena kondisi kendaraan yang buruk saat digunakan. Permasalahan ini tentu berdampak pada perusahaan. Dampak dari masalah tersebut dapat dirasakan tidak hanya oleh perusahaan namun pelanggan juga ikut merasakan dampak dari masalah yang terjadi. Dampak yang terjadi dapat berpengaruh pada waktu pengiriman dan biaya. Waktu pengiriman menjadi tidak efektif karena banyak waktu yang dibuang karena adanya keterlambatan dan waktu tunggu baik
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7 di jalan maupun saat menunggu antrian di konsumen. Selain itu, dampak juga berpengaruh pada biaya karena kerugiankerugian yang dapat dialami perusahaan. Penggunaan sumber daya yang tidak efektif dapat mengakibatkan peningkatan biaya untuk proses distribusi. Dari permasalahan tersebut, dibutuhkan suatu perhitungan yang sistematis untuk melakukan penjadwalan dan penentuan rute distribusi produk pada perusahaan. Oleh karena itu, pada penelitian ini dilakukan penyelesaian masalah menggunakan gabungan dari Algoritma Genetika dan Algoritma Pencarian Tabu. Gabungan kedua metode ini cukup banyak digunakan dalam menyelesaikan masalah penjadwalan dan penentuan rute kendaraan untuk kegiatan distribusi. II. TAHAPAN PENELITIAN A. Pengumpulan Data dan Identifikasi Masalah Pada tahap ini dilakukan pengumpulan data dan informasi yang dibutuhkan dalam pelaksanaan tugas akhir yang berkenaan dengan proses distribusi pada perusahaan terkait dengan data pelanggan meliputi informasi-informasi terkait dengan pelanggan aktif , data kendaraan meliputi informasiinformasi terkait dengan kendaraan yang dimiliki oleh perusahaan, dan data permintaan pengiriman terkait dengan informasi permintaan pengiriman produk dari pelanggan. Setelah dilakukan pengumpulan informasi dan data, dilakukan identifikasi permasalahan terkait dengan informasi yang didapatkan. B. Perancangan dan Pemodelan Pada bagian ini, semua batasan dan parameter yang dibutuhkan dalam proses analisis dibentuk ke dalam suatu model matematika. Dengan dibentuk ke dalam model matematika agar memudahkan proses perhitungan dengan algoritma yang digunakan. Setelah itu proses perhitungan menggunakan metode atau algoritma yang digunakan dilakukan dengan memanfaatkan model matematika yang telah dibuat sebelumnya. C. Pembuatan Program Pada tahap ini dilakukan pembuatan program penjadwalan dan penentuan rute menggunakan kedua algoritma yang digunakan dan memanfaatkan model matematika yang dibuat pada proses sebelumnya. Berikut ini spesifikasi yang digunakan untuk pembuatan program penjadwalan dan penentuan rute kendaraan : i. Bahasa Pemrograman : Java ii. Database Management System : MySQL D. Uji Coba dan Evaluasi Program Pada tahap ini, program penjadwalan dan penentuan rute dilakukan pengujian untuk mengetahui untuk mengevaluasi kinerja dari program dan algoritma yang digunakan dengan menyajikan pengujian acak untuk jumlah konsumen yang meningkat. III. PENJADWALAN DAN PENENTUAN RUTE MENGGUNAKAN KOMBINASI ALGORITMA Pada penjadwalan dan penentuan rute kendaraan pada kasus
2 ini bertutjuan untuk meminimalkan biaya yang terkait jarak dan waktu transportasi sekaligus untuk mengupayakan ketepatan waktu pengiriman kepada pelanggan. Berikut ini adalah formulasi dari fungsi tujuan yang digunakan. =
(1)
Fungsi tujuan (1) adalah biaya yang memperhitungkan jarak dan waktu perjalanan kendaraan ke pelanggan. Selaing fungsi (1), fungsi lain yang digunakan pada kasus ini adalah sebagai berikut. ⎧ ⎪0 → (, )
=
(, )=
(, )=
)
(2)
⎨ ⎪1 → ⎩
(, )=
( = 1, 2, … ,
≠
( = 1, 2, … ,
)
⎧0 → ⎪
≤
( = 1, 2, … ,
)
⎨ ⎪1 → ⎩
>
( = 1, 2, … ,
)
0 → 1 → 0 → 1 →
(3)
≤ >
(4)
≥ <
(5)
Fungsi (2), (3), (4), dan (5) adalah fungsi batasan yang digunakan dalam kasus ini. Fungsi (2) adalah fungsi batasan yang menentukan apakah semua pelanggan telah terjadwal semuanya pada saat jadwal ditentukan. Fungsi (3) adalah batasan kapasitas dimana muatan kendaraan tidak boleh melebihi kapasitas kendaraan. Fungsi (4) adalah batasan waktu kedatangan dimana waktu kedatangan kendaraan ke pelanggan tidak boleh melebihi batas waktu yang ditentukan. Fungsi (2), (3), dan (4) adalah hard constraint, sedangkan fungsi (5) yang merupakan fungsi yang menunjukkan apakah kendaraan datang lebih dahulu dari waktu awal yang ditentukan merupakan soft constraint yang boleh dilanggar. A. Pemodelan Kromosom Kromosom pada kasus ini berbentuk matrik yang tiap barisnya merepresentasikan jenis produk. Perlu digarisbawahi bahwa tidak boleh ada percampuran muatan antara produk satu dengan produk yang lain. Hal ini karena produk yang dimuat adalah produk kimia. Dalam kasus terdapat 4 jenis produk sehingga banyak baris pada kromosom adalah 4 baris yang tiap barisnya merupakan armada yang ditugaskan pada tiap-tiap produk. Pada contoh kode kromosom pada Gambar 1, T1 sampai dengan T16 adalah Trip Object yang merupakan objek yang menjadi gen dari kromosom yang dibentuk. Keterangan Trip Object ini dapat dilihat pada Tabel 1.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7
3 batasan dimana kesalahan yang terjadi akibat menyalahi batasan dijumlah kemudian diberikan nilai pinalti. ( )=
= Gambar. 1. Contoh pengkodean kromosom yang digunakan Tabel 1 Komponen-Komponen pada Struktur Trip Object Trip Object (T) Waktu kirim ID Pelanggan Waktu Awal kirim (menit) Jumlah permintaan (kg) Waktu Akhir kirim (menit) Waktu kirim Jenis produk ID Armada ID Kendaraan Kapasitas Kendaraan (ton)
B. Pembentukan Populasi Pada kasus ini menggunakan teknik random untuk membentuk individu-individu sebagai calon. Proses random diberlakukan pada Trip Object dimana komponen yang diacak adalah pelanggan dan kendaraan yang akan melakukan pengiriman. Berikut ini tahapan yang dilakukan pada teknik random untuk menghasilkan rute. Tahap 1 : Urutkan tiap node pelanggan berdasarkan waktu awal dan waktu akhir memulai layanan pada pelanggan untuk tiap armada. Tahap 2 : Untuk masing-masing armada, isi Trip Object dengan node pelanggan secara acak berturut-turut mulai dari kunjungan pertama sampai kunjungan ke-n. Kombinasi yang dihasilkan tidak boleh memungkinkan adanya pelanggan yang sama muncul dua kali dalam kunjungan. Satu kunjungan hanya diisi oleh satu pelanggan. Terus lakukan proses random jika ada pelanggan yang belum didaftarkan. Tahap 3 : Setelah tiap-tiap kunjungan telah diisi oleh pelanggan, lakukan proses random kembali terhadap kendaraan. Proses random pada kendaraan harus berkisar pada sejumlah kendaraan yang ditugaskan untuk tiap-tiap armada. Untuk kendaraan, kombinasi yang dihasilkan boleh memungkinkan kendaraan yang sama muncul lebih dari satu kali, namun harus diingat bahwa sebisa mungkin semua kendaraan dapat muncul dalam proses random. Tahap 4 : Setelah Trip Object terisi dengan pelanggan dan kendaraan, masukkan komponen-komponen yang terkait dengan pelanggan dan kendaraan dalam objek. Tahap 5 : Ulangi tahap 2 sampai dengan 4, jika masih ada armada yang belum terisi oleh objek. Setelah terbentuk individu, semua individu yang dihasilkan dihitung nilai fitness untuk tiap-tiap individu. Individu yang memiliki nilai fitness yang baik yang akan dimasukkan ke dalam populasi.Urutan penomoran C. Fungsi Fitness Pada kasus ini, fungsi fitness yang digunakan adalah fungsi tujuan yang bertujuan untuk meminimumkan jarak dan waktu dan fungsi tambahan yang didapatkan dari perhitungan fungsi
1 ×( + )
+ =
+ ′
(6) +
(7)
(8)
=
′′
(9)
=
′′′
(10)
=
′′′′
(11)
C merupakan fungsi tujuan, sedangkan E merupakan fungsi eveluasi yang dibentuk berdasarkan pembobotan dari kesalahan yang dimiliki individu atau kromosom karena menyalahi batasan. Pada fungsi fitness di atas diberikan konstanta e, dimana e merupakan bilangan kecil yang ditentukan untuk menghindari pembagi nol atau jika E bernilai nol. Error1 sampai error4 adalah fungsi yang memberikan bobot pada kesalahan yang terjadi akibat menyalahi empat batasan yang disebutkan sebelumnya. Sedangkan W1 dan W2 merupakan bobot atau nilai pinalti yang diberikan. W1 diberikan pada batasan-batasan yang bersifat hard constraint sedangkan W2 diberikan batasan yang bersifat soft constraint. W1 = jumlah permintaan terbesar dalam hari tersebut dan W2 = 1/jumlah pelanggan. D. Rekombinasi dan Mutasi Proses rekombinasi dan mutasi merupakan proses untuk meningkatkan kualitas individu pada populasi. Sebelum kedua proses ini dilakukan, individu yang akan dikenakan prosesproses ini harus diseleksi terlebih dahulu. Pada kasus ini dilakukan proses seleksi menggunakan metode Roulette Wheel dengan memilih berdasarkan dua angka acak yang dihasilkan disesuaikan dengan persentase nilai fitness masing-masing individu. Proses rekombinasi yang dilakukan adalah menggunakan metode Order Crossover(OX)( Davis, 1985). Order Crossover dipilih karena metode ini menghasilkan jumlah anak yang sama banyaknya dengan jumlah induk yang diseleksi dari populasi. Gen-gen anak yang dihasilkan dimasukkan secara berurutan dan terstruktur sehingga memudahkan proses rekombinasi walaupun bentuk kromosom berbentuk matrik. Operator rekombinasi ini dipilih karena disesuaikan dengan bentuk kromosom pada kasus ini dimana bentuk kromosom adalah matrik yang tiap barisnya mewakili jenis produk atau armada yang berbeda. Mekanisme Order Crossover dapat dilihat pada Gambar 2. Operasi selanjutnya pada Algoritma genetika adalah mutasi.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7 Proses mutasi merupakan proses penukaran gen dari 1 menjadi 0 pada titik tertentu yang didapatkan secara acak [20].Pada kasus ini digunakan salah satu proses mutasi yang sederhana yaitu Swap Mutation yaitu suatu pertukaran dua buah gen dalam satu kromosom dimana gen-gen yang ditukarkan dapat dihasilkan dengan cara acak. Kromosom yang ditukarkan adalah kromosom sebaris, dimana baris dipilih secara acak kemudian dilakukan pertukaran. Mekanisme proses mutasi ini dapat dilihat pada Gambar 3.
4 namun hanya induk kedua saja yang dioptimalkan. Hal ini dilakukan agar tetap menjaga kualitas induk pertama yang memiliki nilai dari fungsi fitness yang paling baik. Sedangkan kombinasi yang kedua adalah melakukan optimasi menggunakan pencarian tabu setelah populasi dikenakan operasi pada algoritma genetika agar dapat menghasilkan individu baru dengan kualitas yang baik. Alur proses gabungan antara algoritma genetika dan algoritma pencarian tabu yang diadaptasi dari penelitian Yu et. al. dan Thamilselvan dan Balasubramanie dan disesuaikan dengan kebutuhan pada kasus dapat dilihat pada Gambar 4.
Gambar. 2. Mekanisme proses rekombinasi menggunakan metode Order Crossover
Gambar 3. Mekanisme proses mutasi menggunakan metode Swap Mutation
E. Terminasi Terminasi adalah suatu kondisi dimana suatu iterasi atau suatu proses dalam menghasilkan solusi mengalami pemberhentian karena syarat atau kondisi tertentu. Pada kasus ini juga menerapkan terminasi dimana proses pencarian solusi menggunakan algoritma genetika akan berhenti jika dalam kondisi di bawah ini : a) Jika jumlah generasi yang dihasilkan telah mencapai angka maksimum generasi yang ditentukan. b) Solusi terbaik dalam populasi atau solusi terbaik dari individu baru terhadap solusi terbaik dari populasi sebelumnya tidak mengalami peningkatan sebanyak 1000 kali iterasi atau mengalami penurunan pada jumlah generasi tertentu. c) Solusi terbaik dari individu baru dibandingkan solusi terbaik dari populasi generasi sebelumnya memiliki persentase kurang dari error rate yang ditentukan. F. Alur Kombinasi Algoritma Genetika dan Algoritma Pencarian Tabu Bagian ini menjelaskan mengenai alur proses pencarian solusi menggunakan kombinasi antara Algoritma Genetika dan Pencarian Tabu. Proses yang dibuat didalamnya diadaptasi dari alur proses pada penelitian yang dilakukan oleh Yu et. al dan Thamilselvan dan Balasubramanie. Dalam kasus ini, kombinasi antara algoritma genetika dan pencarian tabu berada pada dua tahap dalam proses. Pertama, pencarian tabu disisipkan pada proses seleksi individu yang akan menjadi induk untuk mengoptimalkan induk yang dihasilkan. Namun tidak semua induk yang dipotimalkan
Gambar 4. Flowchart Kombinasi Algoritma Genetika dan Pencarian Tabu
IV. HASIL IMPLEMENTASI DAN ANALISIS Proses penjadwalan dan penentuan rute kendaraan pada kasus ini dilakukan pada salah satu perusahaan produsen bahan kimia sebagai studi kasus. Proses perhitungan awal dilakukan pada permintaan pengiriman dengan jumlah pelanggan sebanyak 17 pelanggan. Contoh hasil keluaran dari perhitungan jadwal dan rute pada program dapat dilihat pada Gambar 5. Selain menggunakan kombinasi algoritma, pada penelitian ini juga dbentuk jadwal dan rute menggunakan algoritma genetika, algoritma pencarian tabu, dan metode penjadwala perusahaan untuk membandingkan solusi yang telah dibentuk. Untuk algoritma kombinasi, algoritma genetika dan algoritma pencarian tabu dilakukan perhitungan sebanyak 10 kali replikasi untuk menghasilkan kemungkinan solusi paling baik. Hasil perbandingan empat metode ini dapat dilihat pada Tabel 3
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7
5
Grafik dari pengaruh ukuran populasi terhadap jumlah generasi pada Tabel 2 dapat dilihat pada Gambar 7. Dari Tabel 2, didapatkan jumlah generasi yang dipengaruhi oleh ukuran populasi tertentu dalam kurun waktu komputasi selama 1 jam (60 menit). Setiap pertambahan ukuran populasi, jumlah generasi yang dihasilkan dalam waktu komputasi selama satu jam menjadi berkurang. Tabel 3 Contoh Perbandingan Hasil Perhitungan tiap-tiap Metode untuk Jadwal dan Rute dengan 17 Pelanggan Metode
Gambar 5. Contoh hasil keluaran program yang berupa jadwal dan rute pengiriman
Grafik Perubahan Nilai Fitness 0,002500 0,002000
Nilai Fitness
0,001500 0,001000
17 Pelanggan 24 Pelanggan 27 Pelanggan
0,000500
1 13 25 37 49 61 73 85 97 109 121 133 145 157 169 181 193
0,000000
Metode Penjadwalan Perusahaan Algoritma Genetika Algoritma Pencarian Tabu Kombinasi Algoritma
Untuk mengetahui kinerja program dalam menghasilkan solusi, maka pada penelitian ini dilakukan uji kinerja dimana uji yang dilakukan adalah membandingkan jumlah generasi yang dihasilkan oleh ukuran populasi yang berbeda dalam kurun waktu komputasi yang ditentukan. Dalam uji ini waktu komputasi ditentukan dengan lama waktu 1 jam. Hasil dari uji kinerja dapat dilihat pada Tabel
1 (17 Pelanggan) 2 (24 Pelanggan) 3 (27 Pelanggan) Data Tes 1 (26 Pelanggan) Data Tes 2 (20 Pelanggan)
25 550 490 416 501
50 390 211 269 319
Jumlah Generasi pada Ukuran Populasi 100 200 300 400 500 750 256 120 63 38 24 23 19 148 57 33 20 20 14 158 64 49 30 28
1000 14 9
Jumlah Generasi
Grafik Perubahan Jumlah Generasi Terhadap Ukuran Populasi dalam 1 jam Waktu Komputasi 600 550 500 450 400 350 300 250 200 150 100 50 0
27 Pelanggan 24 Pelanggan 17 Pelanggan
25
50
100
200
300
400
500
750
1000
Ukuran Populasi Gambar 7. Grafik perubahan jumlah generasi terhadap ukuran populasi dalam kurun waktu komputasi selama 1 jam
Error 1
Error 2
Error 3
368,942 8571
0
0
0
Error 4 4
0,001967 289 0,002315 001
432,066 6667 386,495 2381
0
0
0
3
0
0
0
2
0,002321 498
366,142 9
0
0
0
3
Tabel 4 Perbandingan Biaya Terbaik dari tiap-tiap Metode Jadwal
Jumlah pelanggan 17 Pelanggan 24 Pelanggan 27 Pelanggan 20 Pelanggan
Biaya
Dari perbandingan pada Tabel 3, terlihat bahwa kombinasi algoritma menunjukkan biaya paling baik. Namun hal ini tidak bisa menjadi patokan. Maka dilakukan perbandingan biaya antara empat metode yang digunakan. Perbandingan biaya yang dilakukan adalah perbandingan biaya terbaik dan ratarata biaya yang dihasilkan dari algoritma acuan dengan biaya yang dihasilkan oleh metode penjadwalan kendaraan.
Generasi Gambar.6. Grafik perubahan nilai fitness tiap generasi pada hasil replikasi 1 untuk 17 pelanggan
Tabel 2 Pengaruh Ukuran Populasi Terhadap Jumlah Generasi pada 1 jam Waktu Komputasi
Nilai Fitness 0,002094 436
Metode Metode Penjadwalan Perusahaan
Algoritma Genetika
Algoritma Pencarian Tabu
Kombinasi Algoritma
368,942860
432,066670
386,495240
366,142900 (min)
575,790480 (min)
746,676190
625,333330
572,158670
838,542850
571,978600
779,352380
552,914290
525,447620
423,190480 (min)
423,466670
576,095230
599,942860 564,914200 (min) 544,723810 (min) 427,057140
Tabel 5. Perbandingan Biaya Rata-Rata Algoritma Acuan dengan Biaya dari Metode Penjadwalan Perusahaan Jadwal 1 (17 Pelanggan) 2 (24 Pelanggan) 3 (27 Pelanggan) Data Tes 1 (26 Pelanggan) Data Tes 2 (20 Pelanggan)
Metode Penjadwalan Perusahaan 368,942860 (min) 575,790480 (min) 572,158670 (min) 571,978600 (min) 423,466670 (min)
Metode Algoritma Pencarian Tabu
Algoritma Genetika
Kombinasi Algoritma
526,25619
421,37809
396,53810
815,05524
647,62952
646,39524
865,99240
623,50181
612,78852
793,41172
608,40835
584,46913
542,98395
467,93419
461,14029
Dari Tabel 5.51, didapatkan dari lima jadwal bahwa biaya terbaik paling banyak dihasilkan oleh kombinasi algoritma pada jadwal 1,3 dan data tes 1. Sedangkan biaya terbaik yang dihasilkan dari metode penjadwalan perusahaan ada pada jadwal 2 dan biaya terbaik pada data tes 2 dihasilkan oleh algoritma pencarian tabu. Dari hasil tersebut dapat
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7 dikatakan bahwa kombinasi algoritma berpeluang dapat menghasilkan biaya atau solusi yang lebih baik daripada biaya hasil metode penjadwalan perusahaan. Untuk perbandingan rata-rata biaya tiga algoritma acuan dengan biaya dari metode penjadwalan manual pada Tabel 5.52 didapatkan hasil bahwa biaya dari metode penjadwalan perusahaan lebih minimum daripada biaya rata-rata yang dihasilkan oleh tiga algoritma acuan. Namun dari perbandingan tersebut, didapatkan pula bahwa rata-rata biaya yang paling mendekati biaya yang dihasilkan oleh metode penjadwalan perusahaan adalah rata-rata yang dihasilkan oleh kombinasi algoritma. Dari hasil perbandingan dua jenis biaya yang didapatkan dari masing-masing metode, dapat disimpulkan bahwa kombinasi algoritma memiliki peluang dapat menghasilkan biaya solusi yang lebih baik daripada metode penjadwalan perusahaan. Tidak bisa dikatakan bahwa biaya yang dihasilkan oleh kombinasi algoritma lebih minimum daripada biaya dari metode penjadwalan perusahaan karena solusi yang dihasilkan tiap program dijalankan dapat berbeda-beda karena pembentukan individu awal yang dilakukan adalah secara acak sehinggan menimbulkan perbedaan hasil tiap program dijalankan. V. KESIMPULAN DAN SARAN Kesimpulan yang dapat diambil dari penelitian yang dilakukan antara lain : a) Aplikasi yang dibuat mampu menjalankan semua fungsional yang ditentukan dan mampu memberikan solusi yang sama dengan dengan perhitungan manual. Selain itu, solusi yang dihasilkan oleh aplikasi dapat memenuhi batasan-batasan utama (hard constraints) yang ditetapkan dalam penjadwalan dan penentuan rute kendaraan. b) Dari uji coba kinerja aplikasi, kombinasi algoritma yang digunakan mampu menghasilkan solusi jadwal dan rute kendaraan dengan biaya yang lebih minimum dan lebih baik dibandingkan dengan yang dihasilkan oleh masingmasing algoritma yang dikombinasikan. Rataan biaya yang dihasilkan oleh kombinasi algoritma dalam 10 kali replikasi juga menunjukkan hasil yang lebih baik. Namun demikian, dari aspek waktu komputasi yang diperlukan, algoritma pencarian tabu membutuhkan waktu komputasi yang paling sedikit. c) Kombinasi algoritma yang digunakan dalam aplikasi mempunyai peluang untuk menghasilkan biaya yang lebih minimum dibandingkan dengan biaya yang dihasilkan oleh metode penjadwalan manual perusahaan. Dari lima uji coba penjadwalan yang dilakukan, tiga solusi dengan biaya terrendah dihasilkan oleh kombinasi algoritma. Walaupun rataan biaya yang dihasilkan oleh kombinasi algoritma dari 10 kali replikasi lebih besar dari pada biaya yang dihasilkan oleh metode penjadwalan manual perusahaan, tetapi rataan biaya yang dihasilkan mendekati biaya yang dihasilkan oleh metode penjadwalan manual perusahaan. Adapun saran yang ditambahkan untuk mengembangkan penelitian ini adalah aplikasi perlu diintegrasikan pada sistem peta geografis untuk mendapatkan jarak antar pelanggan yang lebih realistis. Selain itu, perhitungan biaya yang dibutuhkan
6 tidak hanya didasarkan pada jarak dan waktu tempuh, tetapi disesuaikan dengan kondisi nyata, seperti biaya bahan bakar, biaya kebutuhan supir, dan biaya-biaya lain-lain yang relevan. UCAPAN TERIMA KASIH Alhamdulillah, penulis ucapkan puja dan puji syukur kehadirat Allah SWT yang telah memberikan kesempatan pada penulis untuk menyelesaikan penelitian ini. Penulis juga mengucapkan terima kasih kepada semua pihak yang telah membantu proses penelitian ini, terutama kepada Dosen Pembimbing yang telah meluangkan waktu dalam membantu membimbing penulis untuk menyelesaikan penelitian ini. DAFTAR PUSTAKA [1]
Maulik, U and Bandyopadhyay, S. 2000. “Genetic algorithm-based clustering technique”. Pattern Recognition 33 2000, 1455-1465. Available : http://citeseerx.ist .psu.edu/viewdoc/download...pdf. [2] Bodin, L. et. al. 1986. “Routing and Scheduling of Vehicles and Crews”.Computer and Operation Research, 63-211. Available : http://onlinelibrary.wiley.com/doi/10.1002/net.3230110204/abstract. [3] Glover, F. et. al. 1995. “Genetic Algorithms and Tabu Search: Hybrids for Optimization”. Computer and Operation Research, 111-134. http://www.sciencedirect.com/science/article/pii/0305054893E0023M [4] Thamilselvan, R and Balasubramanie, P. 2009. “A Genetic Algorithm with a Tabu Search (GTA) for Traveling Salesman Problem”. International Journal of Recent Trends in Engineering, 607-610. http://www.academypublisher.com/ijrte/vol01/no01/ijrte0101607610.pdf [5] Yu, S. et al. 2011. “A hybrid GA–TS algorithm for open vehicle routing optimization of coal mines material”. Expert Systems with Applications, 10568–10573. Available:http://www.sciencedirect.com/science/article/pii/S095741741 10 03149. [6] Malmborg, J. C. 1996. “A genetic algorithm for service level based vehicle scheduling”. European Joumal of Operational Research 93 1996, 121 – 134. Available:http://www.sciencedirect.com/science/article/pii/S13665545 080013 24. [7] Min, H. et. al. 2010. “The Study of Optimizing of Physical Distribution Routing Problem System with Time Windows Based on Genetic Algorithm”. International Forum on Information Technology and Applications, 59-62. Available:http://ieeexplore.ieee.org/ielx5/5633132/5634735/05634925.p df. [8] Skrlec, D. et. al. 1997. “A Heuristic Modification of Genetic Algorithm Used for Solving the Single Depot Capacited Vehicle Routing Problem”. Electrical Engineering and Computing, 184-188. Available:http://ieeexplore.ieee.org/ielx3/5136/13957/00645214.pdf. [9] Mak, K.L and Guo, Z. G. 2004. “A genetic algorithm for vehicle routing problems with Stochastic demand and soft time windows”. Systems and Information Engineering Design Symposium, 183-190. Available:http://ieeexplore.ieee.org/ielx5/9192/29144/01314679.pdf?tp= &arnumber=1314679&isnumber=29144. [10] Brandao, J and Mercer, A. 1997. “A tabu search algorithm for the multitrip vehicle routing and scheduling problem”. European Journal of Operational Research 100 1997, 180-191. Available:http://www.sciencedirect.com/science /article/pii/ S0377221797000106. [11] Qin, J. et. al. 2011. “A New Coding Method for Genetic Algorithm in Vehicle Routing Problem”. International Conference on Cyber Technology in Automation, Control, and Intelligent Systems, 201-204. Available:http://ieeexplore.ieee.org/ielx5/6005297/6011752/06011793.p df?tp=&arnumber=6011793&isnumber=6011752. [12] Panggabean, H. P. 2005. “Penjadwalan job shop statik dengan Algoritma tabu search”. Integral, 34-45.
JURNAL TEKNIK POMITS Vol. 1, No. 1, (2012) 1-7
[13] [14] [15] [16]
[17] [18]
[19]
[20]
Available:http://home.unpar.ac.id/~integral/Volume%2010/Integral%20 10%20No.%201/Penjadwalan%20Job%20Shop%20dengan%20Tabu%2 0Search.pdf. Mitchell, M. 1999. “An Introduction to Genetic Algorithms”. London, England: The MIT Press. Haupt, R. L., & Haupt, S. E. 2004. “Practical Genetic Algorithms (2nd Edition ed.)”. Hoboken, New Jersey, USA: John Wiley & Sons, Inc. Gendreau, M. 2002. “An Introduction to Tabu Search”. Montreal, Canada: Kluwer Academic Publishers. Prabha, K. A. and Saranya, R. 2011. “Refinement of K-Means Clustering Using Genetic Algorithm”. Journal of Computer Applications, 40-44. Available:http://www.jcaksrce.org/upload/51111134_vol4i2p2.pdf. Rushton, A. et. al. 2006. The Handbook of Logistics and Distribution Management. : Kogan Page Ltd. Duan, Z. et. al. 2010. “An Improved Genetic Algorithm for Time Dependent Vehicle Routing Problem”. Future Computer and Communication International Conference, 835-839. Available:http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=& arnumber=5497310. Liaw, C. 2000. “A hybrid genetic algorithm for the open shop scheduling problem”. European Journal of Operational Research, 2842. Hendrawan, B.E. 2008. “Implementasi Algoritma Paralel Genetic Algorithm untuk Penyelesaian Heterogeneous Fleet Vehicle Routing Problem”. Surabaya : Tugas Akhir Jurusan Teknik Informatika FTIf ITS.
7
