BAB 1 PENDAHULUAN 1.1 Latar Belakang Dalam masalah pengiriman barang, sebuah rute diperlukan untuk menentukan tempat tujuan berikutnya dari sebuah kendaraan pengangkut baik pengiriman melalui darat, air, ataupun udara. Banyaknya tempat tujuan yang ada dalam kasus pengiriman barang menjadi masalah karena banyaknya kemungkinan rute yang dapat dibentuk. Rute-rute yang terbentuk mempunyai tingkat efisiensi yang berbeda. Selain itu banyaknya kendaraan yang digunakan untuk pengiriman barang menambah permasalahan yang ada, karena ada beberapa kendaraan yang dapat dipakai secara bersamaan untuk melayani tempat-tempat tersebut. Vehicle Routing Problem adalah istilah yang dibuat untuk sebuah problem atau masalah di mana sebuah set rute yang akan dibentuk untuk sejumlah kota dengan sejumlah kendaraan yang didasarkan atas satu atau banyak depot. Setiap kota hanya akan dilalui oleh satu kendaraan. Pemecahan masalah Vehicle Routing Problem dapat dilakukan dengan memeriksa semua jalur secara manual kemudian dihasilkan rute dengan jarak perjalanan yang paling pendek. Cara tersebut dapat diterapkan untuk permasalahan Vehicle Routing Problem dengan jumlah kota yang sedikit, tetapi cara tersebut tidak akan efektif untuk jumlah kota yang banyak. Dengan bertambahnya jumlah kota, jumlah rute yang akan dihasilkan akan bertambah banyak. Akibatnya diperlukan algoritma untuk dapat memecahkan masalah ini dalam waktu yang relatif singkat.
2
Pembentukan rute seringkali terkait dengan efisiensi, karena diharapkan biaya yang dibutuhkan dalam pengiriman barang menjadi minimum tanpa melanggar batasanbatasan yang harus dipenuhi seperti jam kerja, kecepatan rata-rata kendaraan, kapasitas kendaraan, dan sebagainya. Pembentukan rute tersebut dapat dibuat dengan menggunakan perhitungan eksak, tetapi hal itu membutuhkan waktu yang lama untuk masalah yang sederhana. Karena itu dikembangkan perhitungan secara heuristik menggunakan algoritma Genetik, yang diharapkan dapat memperbaiki rute yang telah terbentuk. Dengan menggunakan perhitungan heuristik diharapkan dapat memperoleh hasil yang optimal dengan waktu yang sesuai. Kasus yang dibahas merupakan permodelan dari Vehicle Routing Problem. Vehicle Routing Problem merupakan kasus yang hampir sama seperti dengan kasus Multiple Traveling Salesman Problem. Perbedaan pada Vehicle Routing Problem adalah pada batasan seperti kapasitas, jumlah kendaraan yang digunakan, dan depot yang banyak.
1.2 Perumusan Masalah Rute yang diinginkan adalah rute yang optimal sehingga biaya yang dikeluarkan dapat mencapai hasil yang minimal. Masalah yang ditemui adalah bagaimana membuat rute pengiriman barang dengan algoritma Genetik. Rute yang terbentuk diharapkan dapat mempunyai jarak tempuh yang paling pendek dengan tidak melanggar batasan kapasitas kendaraan. Yang dibahas dalam skripsi ini adalah model Capacitated Vehicle Routing Problem. Pembuatan rute akan menjadi semakin sulit karena ada banyaknya node dan batasan kapasitas kendaraan.
3
1.3 Ruang Lingkup Masalah Ruang lingkup kendaraan yang dipakai:
Tiap kendaraan mempunyai kapasitas dan berat yang sama.
Tiap kendaraan mempunyai biaya/km yang sama.
Kendaraan yang dipakai berjumlah sama dengan jumlah rute yang terbentuk.
Pengaturan posisi barang dalam kendaraan tidak dimasukkan sebagai kendala.
Batasan pada variabel yang dipakai di sini hanya kapasitas, sehingga yang dibahas adalah pemodelan Capacitated Vehicle Routing Problem.
Ruang lingkup daerah-daerah pengiriman barang:
Penggambaran node-node dalam bentuk posisi x dan y.
Satu node hanya dilayani oleh satu kendaraan dan dilalui hanya satu kali.
Bersifat simetris, artinya jarak yang didapat dari node 1 ke node 2 sama dengan jarak dari node 2 ke node 1.
Satu depot dipakai sebagai awal dan tujuan akhir dari suatu rute.
Posisi node depot dan pelanggan didapat dari posisi yang ada dalam peta Jakarta (Hothorf 2004) dengan berpusat pada depot yang berada di alamat PT. Maju Express Indonesia dengan titik (0,0).
Wilayah yang dipakai untuk perhitungan program aplikasi kali hanya pada wilayah Jakarta, Bogor, Depok, Tangerang, dan Bekasi.
Jarak yang dihitung merupakan jarak antara 2 titik pada bidang 2 dimensi menggunakan skala 1 : 200.000.
4
Hasil yang didapat dalam setiap kali program dijalankan dapat memperoleh jalur terpendek yang berbeda-beda, karena banyaknya peluang kombinasi yang mungkin terbentuk dan terbatasnya jumlah iterasi. Sehingga memungkinkan pemakai untuk memilih jalur yang paling mungkin dan sesuai dengan keinginan pemakai berdasarkan pertimbangan dan kebijakan lain pemakai itu sendiri.
1.4 Tujuan dan Manfaat Tujuan yang ingin dicapai adalah: 1.
Melakukan analisis terhadap algoritma Genetik.
2.
Menganalisis jalur pengiriman yang lama.
3.
Memberikan usulan dan merancang jalur pengiriman yang baru.
Manfaat yang diperoleh: 1.
Bagi perusahaan: dapat digunakan untuk meminimalkan biaya-biaya pada bagian pengiriman barang.
2.
Bagi pembaca: dapat memberikan referensi untuk penelitian pada bidang Vehicle Routing Problem selanjutnya.
3.
Bagi penulis: dapat memberikan pengetahuan lebih mengenai algoritma Genetik dan mengenai Vehicle Routing Probem.
1.5 Metodologi Perancangan dibagi menjadi beberapa tahapan sebagai berikut: 1. Analisis Pada tahap analisis dilakukan studi untuk dapat mendalami permasalahan tentang Vehicle Routing Problem dan algoritma Genetik. Analisis juga dilakukan pada
5
perusahaan sebagai tempat untuk mengambil sampel data yang nantinya akan diproses untuk mendapatkan hasil.
2. Perancangan dan pembuatan perangkat lunak Tahap ini dilakukan dalam penelitian untuk menentukan sistem yang tepat dalam perancangan dan pembuatan perangkat lunak. 3. Pengujian dan analisis perangkat lunak Perangkat lunak yang telah dibuat akan diuji dan dianalisis hasilnya, apakah telah mencapai hasil yang optimal atau belum. 4. Evaluasi perangkat lunak dan pengambilan kesimpulan
1.6 Sistematika Penulisan Dalam penyusunan tugas akhir ini, sistematika penulisan dibagi menjadi beberapa bab sebagai berikut. BAB I
PENDAHULUAN Bab ini berisi pembahasan masalah umum yang meliputi latar belakang masalah, rumusan masalah, batasan masalah, tujuan penelitian,
manfaat
sistematika penulisan.
penelitian,
metodologi
penelitian
dan
6
BAB II
LANDASAN TEORI Bab ini memuat landasan teori yang berfungsi sebagai sumber atau alat dalam memahami permasalahan yang berkaitan dengan teori graf, algoritma semut, dan permalahan dalam rute kendaraan.
BAB III
ANALISIS DAN PERANCANGAN SISTEM Bab ini akan memuat tentang riwayat perusahaan, struktur organisasi perusahaan, tata laksana/prosedur yang sedang berjalan dalam perusahaan, permasalahan yang dihadapi dan alternatif pemecahan masalah, dan perancangan layar .
BAB IV
IMPLEMENTASI DAN EVALUASI Bab ini membahas tentang rancangan sistem yang diusulkan yang meliputi tampilan rancangan sistem yang diusulkan dan evaluasi terhadap metode yang digunakan.
BAB V
KESIMPULAN DAN SARAN Memuat kesimpulan-kesimpulan yang merupakan rangkuman dari hasil dan pembahasan perangkat lunak pada bagian sebelumnya dan saran yang perlu diperhatikan berdasarkan keterbatasan yang ditemukan dan asumsi-asumsi yang dibuat selama pembuatan perangkat lunak.
