BAB I PENDAHULUAN
1.1. Latar Belakang Masalah Dalam kehidupan sehari-hari, masalah yang berhubungan dengan optimisasi sering kali terjadi, misalnya dalam bidang ekonomi dan industri sering dijumpai masalah meminimalkan biaya produksi, memaksimalkan keuntungan dan sebagainya. Masalah optimisasi juga banyak dijumpai oleh perusahaan seperti masalah pendistribusian yang tujuannya meminimalkan biaya perjalanan, meminimalkan jarak perjalanan, memaksimalkan penjualan dan lain-lain. Masalah pendistribusian atau masalah pengiriman barang merupakan masalah yang memerlukan rute optimal agar barang-barang tersebut tiba di tempat tujuan sesuai permintaan pelanggan dengan tepat waktu. Distribusi barang merupakan suatu proses penyaluran dari produsen kepada konsumen untuk memenuhi sejumlah permintaan pelanggan dalam kurun waktu tertentu. Distribusi barang juga sebagai salah satu kegiatan operasional bagi perusahaan untuk menunjang proses pemasaran produknya. Salah satu faktor penting dalam masalah distribusi barang ialah penentuan jadwal keberangkatan atau penentuan rute perjalanan. Secara khusus, dalam menentukan rute perjalanan akan melibatkan himpunan rute yang mungkin akan dilewati kendaraan. Dalam masalah menentukan rute perjalanan, kondisi yang harus diperhatikan ialah kendaraan mengunjungi beberapa tempat dengan memulai dan mengakhiri perjalanannya pada suatu depot, seperti gudang, perusahaan, pabrik dan sebagainya. Masalah rute kendaraan ini bertujuan untuk meminimalkan jarak perjalanan, dengan syarat beberapa kendaraan yang dimiliki harus memenuhi permintaan pelanggan yang dikunjungi dan harus memperhatikan batasan waktu (time windows) yang dimiliki oleh pelanggan. Setiap kendaraan hanya dapat melewati satu rute dan kendaraan tidak diijinkan melaya-
1
2 ni permintaan pelanggan melebihi kapasitasnya. Masalah rute kendaraan di atas merupakan masalah rute kendaraan dengan kendala time windows (VRPTW). Aplikasi dari VRPTW banyak dijumpai di kehidupan yang serba modern dan praktis ini, misalnya masalah layanan pesan antar makanan suatu restoran, layanan bus antar jemput siswa, pendistribusian surat kabar, dan lain sebagainya. Masalah-masalah tersebut memiliki sejumlah permintaan dan time windows dari para pelanggan, sehingga perusahaan harus mencari rute fisibel yang dapat mengoptimalkan pelayanannya. Dalam masalah ini, pendekatan solusi optimal dari masalah VRPTW akan diperoleh dengan menggunakan metode pembangkitan kolom atau column generation.
1.2. Perumusan Masalah Berdasarkan latar belakang masalah yang telah dijelaskan sebelumnya, adapun rumusan masalah yang akan dibahas dalam skripsi ini yaitu : 1. Pengertian masalah rute kendaraan dengan kendala time windows. 2. Asumsi dan batasan yang digunakan untuk masalah rute kendaraan dengan kendala time windows. 3. Model matematis dan dekomposisi dari masalah rute kendaraan dengan kendala time windows. 4. Tahap-tahap menyelesaikan permasalahan rute kendaraan dengan time windows menggunakan metode pembangkitan kolom. 5. Penggunaan metode pembangkitan kolom pada aplikasi dari masalah distribusi barang.
1.3. Batasan Masalah Pada penulisan skripsi ini, pembahasan masalah akan terbatas pada masalah rute kendaraan dengan hard time windows, yaitu untuk setiap kendaraan tidak
3 diijinkan datang telambat dan tidak terdapat pembayaran yang dilakukan selama pelayanan. Kendaraan yang digunakan pada masalah VRPTW di sini dianggap memiliki jenis dan muatan yang sama, sehingga armada kendaraan bersifat homogen.
1.4. Tujuan dan Manfaat penelitian Penulisan skripsi ini dilakukan untuk memenuhi salah satu syarat kelulusan Program Strata-1 (S1) Program Studi Matematika Universitas Gadjah Mada, selain itu penulisan skripsi ini juga bertujuan untuk : 1. Menjelaskan pengertian dari masalah rute kendaraan dengan kendala time windows. 2. Memberikan asumsi dan batasan yang akan digunakan pada masalah rute kendaraan dengan time windows untuk jenis kendaraan yang homogen. 3. Menguraikan model matematis yang merupakan masalah bilangan bulat serta mendekomposisikan masalah rute kendaraan menjadi masalah utama dan submasalah. 4. Menjelaskan tahapan untuk menyelesaikan masalah rute kendaraan dengan kendala time windows menggunakan metode pembangkitan kolom. 5. Memberikan contoh aplikasi dari masalah rute kendaraan dengan time windows disertai dengan penyelesaiannya.
1.5. Tinjauan Pustaka Penulisan skripsi ini disusun dengan mengacu pada beberapa referensi. Jurnal utama yang digunakan dalam skripsi ini adalah jurnal yang ditulis oleh Kallehauge dkk (2005). Pada jurnal tersebut, dibahas mengenai model matematika dan dekomposisi permasalahannya dengan asumsi jenis kendaraan yang digunakan homogen serta permasalahan yang akan dibahas ialah masalah rute kendaraan dengan kendala hard time windows.
4 Selain dari jurnal utama, penulisan skripsi ini menggunakan berbagai referensi lain. Untuk memahami permasalahan rute kendaraan lebih lanjut, penulis menggunakan jurnal dari Chabrier (2005). Dalam jurnal tersebut diberikan dekomposisi dari program linear awal ke dalam masalah utama restriksi dan submasalah. Masalah utama akan menjadi masalah partisi himpunan dan submasalah adalah masalah untuk mencari path terpendek yang mungkin akan dibangkitkan. Masalah utama merupakan masalah partisi himpunan yang memiliki definisi dan model matematika seperti yang dijelaskan oleh Garfinkel dan Nemhauser (1972). Pada penulisan skripsi ini membutuhkan beberapa materi sebagai landasan teorinya. Untuk menjelaskan definisi dan beberapa teorema mengenai program linear, program bilangan bulat dan masalah path terpendek digunakan buku yang ditulis oleh Winston (2004), Rao (1978), dan B. Susanto (1994). Pada VRPTW, suatu permasalahan dapat disajikan melalui graf. Untuk menjelaskan definisi mengenai graf beserta contohnya, digunakan buku yang ditulis oleh Deo (1997) dan Ahuja dkk (1993). Permasalahan VRPTW yang dibahas pada jurnal-jurnal di atas banyak disebutkan algoritma waktu non-deterministik polinomial NP-hard, sehingga pengertian mengenai NP-hard mengacu pada referensi buku yang ditulis oleh Bodin dkk (1983) dan situs pencarian Wikipedia yang diakses pada bulan Januari 2016. Untuk mempelajari mengenai metode pembangkitan kolom, penulis menggunakan referensi jurnal yang ditulis oleh Desrosiers dan L¨ubbecke (2005). Selanjutnya, dengan referensi tugas akhir yang ditulis oleh Wihartiko (2006) dan jurnal yang ditulis oleh Hanum (2005), penulis mempelajari bagaimana aplikasi dari penggunaan metode pembangkitan kolom pada masalah sehari-hari.
1.6. Metodologi Penelitian Dalam pembuatan skripsi ini metode yang digunakan adalah dengan terlebih dahulu melakukan studi literatur mengenai latar belakang masalah rute kendaraan, yang kemudian lebih difokuskan pada masalah rute kendaraan dengan kendala ti-
5 me windows. Setelah melakukan studi literatur mengenai latar belakang masalah, selanjutnya dapat dibentuk asumsi dan batasan untuk masalah VRPTW yang akan dibahas. Selanjutnya penulis mempelajari pengertian dan model dari permasalahan di atas. Penulis juga mempelajari metode penyelesaian untuk masalah tersebut dengan membaca dari berbagai referensi. Kemudian dilakukan pertemuan secara rutin kepada dosen pembimbing untuk melakukan konsultasi dan mendiskusikan masalah di atas.
1.7. Sistematika Penulisan Pada pembuatan skripsi ini, penulis menggunakan sistematika penulisan yaitu sebagai berikut: BAB I
PENDAHULUAN
Pada bab ini dibahas mengenai latar belakang permasalahan, perumusan masalah, batasan masalah, tujuan dan manfaat penulisan, tinjauan pustaka, metodologi penelitian, serta sistematika penulisan skripsi. BAB II
DASAR TEORI
Pada bab ini dibahas konsep yang mendasari pembahasan di bab-bab berikutnya. Konsep dasar yang dibahas antara lain : program linear, dualitas, program bilangan bulat, graf, masalah path terpendek, permasalahan NP-hard, masalah partisi himpunan dan metode pembangkitan kolom. BAB III MASALAH RUTE KENDARAAN DENGAN KENDALA TIME WINDOWS Pada bab ini dibahas mengenai permasalahan rute kendaraan dengan kendala time windows, faktor-faktor yang mempengaruhi masalah rute kendaraan dengan time windows, pemodelan secara matematis untuk masalah rute kendaraan dengan time windows, masalah utama dan submasalah, serta tahap-tahap penyelesaian masalah rute kendaraan dengan time windows. Selanjutnya, akan diberikan contoh dari permasalahan rute kendaraan dengan time windows yang akan diselesaikan dengan
6 metode pembangkitan kolom. BAB IV PENUTUP Pada bab ini akan diberikan kesimpulan dari permasalahan yang telah dibahas pada bab sebelumnya. Selanjutnya akan diberikan saran untuk penelitian berikutnya.
