Perpustakaan Digital ITB

Penentuan rute dan penjadwalan kapal (ship routing and scheduling) adalah salah satu topik dalam penentuan rute dan penjadwalan transportasi (transportation routing and scheduling). Permasalahan pada penentuan rute dan penjadwalan kapal merupakan permasalahan yang kompleks, terutama bila terdapat banyak pelabuhan yang harus dilalui. Pada perancangan rute kapal ini, setiap pelabuhan harus dilalui minimal oleh satu rute. Masalah ini dapat dipandang sebagai masalah set covering. Permasalahan set covering (termasuk masalah set partitioning dan set packing) termasuk dalam kategori permasalahan NP-hard.Banyak permasalahan penentuan rute dan penjadwalan kapal dipecahkan dengan algoritma set covering / partitioning. Aplikasi dari algoritma set covering / partitioning biasanya membutuhkan metoda pembangkitan rute yang layak. Rute yang layak dapat dibentuk secara enumerasi lengkap (exhaustive enumeration) maupun secara heuristik. Bila terdapat banyak pelabuhan, sangat tidak mungkin untuk membangkitkan semua rute yang layak secara enumerasi lengkap karena akan memberikan kemungkinan yang besar. Oleh karena itu suatu pendekatan heuristik perlu dikembangkan untuk membangkitkan satu himpunan yang layak. Tujuan penelitian ini adalah mengusulkan suatu metoda penentuan rute dan penugasan kapal yang layak.Salah satu permasalahan nyata pada penentuan rute dan penjadwalan kapal adalah merancang rute dan penugasakan kapal pada rute-rute yang terbentuk. Permasalahan ini muncul dari situasi nyata yang dihadapi oleh PT.Pelni, perusahaan kapal milik negara Indonesia. Salah satu dari misi dari perusahaan adalah mengurangi biaya dengan tetap memperhatikan kepuasan konsumen. Salah satu cara untuk mengefisienkan operasi adalah dengan dengan membentuk satu himpunan rute yang lebih efisien dan menugaskan kapal pada rute yang tepat.