1

PENERAPAN METODE FINITE COVERING UNTUK PENUGASAN KAPAL PENYEBERANGAN (FERI) UJUNG-KAMAL

Nama Mahasiswa : Via Elsa Kahar NRP : 1207 100 001 Jurusan : Matematika FMIPA-ITS Dosen Pembimbing : 1. Drs. Sulistiyo, MT

2. Dra. Nuri Wahyuningsih, M.Kes

Abstrak

Sebelum dioperasikannya jembatan Suramadu, pelabuhan Ujung-kamal menjadi satu satunya pintu gerbang yang menghubungkan pulau Jawa dengan pulau Madura. pelabuhan Ujung yang ada di Surabaya dan pelabuhan Kamal yang ada di Bangkalan, Madura. Tetapi setelah dioperasikannya jembatan Suramadu pada pertengahan tahun 2009, arus penyeberangan di Ujung-Kamal menjadi turun drastis, baik dari penumpang maupun kendaraan. Kondisi ini menyebabkan kerugian yang amat besar, khususnya bagi pihak penyedia jasa penyeberangan. Beberapa usaha yang telah dilakukan seperti penyesuaian harga tiket feri dengan harga tiket tol suramadu, dan pereduksian jumlah feri yang beroperasi, kurang memberikan hasil yang maksimal. Untuk itu, dalam tugas akhir ini dilakukan penugasan kembali terhadap feri yang beroperasi di pelabuhan Ujung-Kamal dengan tujuan agar kerugian yang dialami pihak penyedia jasa penyeberangan bisa diminimalkan. Penugasan dilakukan dengan metode finite covering.

Finite covering adalah metode yang dikembangkan dari teori graph. Dalam masalah penugasan feri ini, finite covering, khususnya metode pencabangan digunakan untuk mengatur urutan feri yang akan ditugaskan untuk mengangkut penumpang dan kendaraan yang ada pada setiap tripnya. Dari penugasan ini pula, didapatkan bahwa kerugian yang dialami penyedia jasa penyeberangan bisa diminimalkan.

Kata kunci : penugasan, finite covering, metode pencabangan. 1. PENDAHULUAN

Indonesia adalah negara yang sebagian besar wilayahnya dipisahkan oleh laut. Transportasi laut memiliki peranan yang sangat penting untuk membantu mobilitas penduduk Indonesia, menyalurkan bahan logistik, dan menunjang kepentingan ekonomi lainnya. Jarak pulau yang relatif dekat bisa dilayani dengan menggunakan

kapal penyeberangan (feri) yang bisa mengangkut penumpang dan beberapa jenis kendaraan dalam satu waktu.

Salah satu pelabuhan yang menjadi pelabuhan feri di Indonesia adalah pelabuhan Ujung-Kamal. Sebelum pertengahan tahun 2009, pelabuhan penyeberangan Ujung-Kamal ini ramai dipadati penumpang dan pengendara. Hal ini dikarenakan

2

pelabuhan Ujung-Kamal adalah satu-satunya pintu gerbang menuju pulau Madura. Tetapi, eksistensi kapal penyeberangan (feri) Ujung-Kamal terancam dengan hadirnya jembatan Suramadu yang dioperasikan sejak tanggal 14 Juni 2009. Para penumpang dan pengendara banyak yang beralih melewati jembatan Suramadu karena dirasa lebih efektif dibandingkan menyeberang menggunakan kapal.

Ketua Gabungan Pengusaha Angkutan Sungai, Danau, dan Penyeberangan (Gapasdap) Jawa Timur, Khoiri Soetomo menuturkan bahwa arus penyeberangan mengalami penurunan drastis sejak dioperasikannya jembatan Suramadu. Volume kendaraan roda empat, roda dua dan pejalan kaki menyusut. Penurunan ini mengakibatkan pengusaha feri mengalami kerugian puluhan juta rupiah per harinya. Beliau juga mengatakan, apabila tingkat keterisian penumpang (load factor) feri yang semula 30 persen turun sampai level 10 persen, maka bisnis kapal penyeberangan akan mati dan ribuan orang menjadi pengangguran baru. Hal ini dikarenakan biaya operasional, perawatan, dan bahan bakar tidak sesuai dengan jumlah penumpang dan kendaraan yang diangkut. (Taufiq, November 2010).

Sementara itu, pihak pemerintah berharap kapal penyeberangan (feri) tetap beroperasi karena transportasi alternatif di rute Ujung-Kamal sangat penting, terutama apabila terjadi keadaan darurat yang membuat jembatan Suramadu tak bisa dilewati. Beberapa kebijakan telah dilakukan, seperti penyesuaian harga tiket feri

dengan tiket tol Suramadu dan pereduksian jumlah feri yang beroperasi. Saat ini hanya terdapat 6 feri yang dioperasikan di dua dermaga di pelabuhan Ujung dan Kamal, jumlah ini turun dari semula yaitu 16 sampai 18 feri. Dan, beberapa kapal yang tidak dioperasikan telah dialihkan ke lintasan penyeberangan lain di Indonesia.

Namun, kebijakan yang telah dilakukan dirasa belum maksimal. Untuk itu, pada tugas akhir ini akan dilakukan penugasan kapal penyeberangan (feri) yang beroperasi di pelabuhan Ujung-Kamal dengan menggunakan metode finite covering. Finite covering adalah metode yang dikembangkan dari teori graf. Dalam masalah penugasan feri ini, finite covering, khususnya metode pencabangan digunakan untuk mengatur urutan feri yang akan ditugaskan untuk mengangkut penumpang dan kendaraan yang ada pada setiap tripnya agar biaya operasi yang dikeluarkan minimal serta pengangkutan penumpang dan kendaraan optimal. Dengan penugasan ini, diharapkan feri yang nantinya ditugaskan pada trip-trip yang ada sesuai dengan jumlah kendaraan dan penumpang yang ada pula, sehingga tidak menimbulkan kerugian yang besar bagi pihak pengusaha feri.

2. TINJAUAN PUSTAKA 2.1. Studi Pendahuluan

Pada penelitian sebelumnya, metode finite covering telah digunakan dalam penyelesaian beberapa masalah. Seperti pada penyelesaian masalah penugasan feri penyeberangan Merak-Bakauheni yang dilakukan oleh

3

Sulistiyo (2000). Penjadwalan yang dilakukan bertujuan menghasilkan keuntungan atau pendapatan yang maksimal. Pada penelitian tersebut didapatkan jadwal kapal yang akan dioperasikan pada tiap trip yang ada dalam sehari dengan ketentuan kapal yang dioperasikan pada trip pertama akan beregulasi pada trip yang ketujuh, dan seterusnya, dengan mengutamakan angkutan kendaraan yang menunjang pembangunan di bidang ekonomi dan angkutan bus antar pulau antar propinsi. Sedangkan dalam tugas akhir ini, akan dilakukan penugasan feri dengan tujuan meminimalkan kerugian bagi pihak penyedia jasa feri, sehingga penumpang dan kendaraan tidak berpengaruh besar, karena penugasan akan dibuat sesuai dengan penumpang dan kendaraan yang dilayani. Selain itu, penugasan akan dilakukan untuk setiap urutan dalam tiap trip.

2.2. Ujung-Kamal

Ujung adalah nama pelabuhan yang berada di Surabaya Utara. Pelabuhan ini menghubungkan pulau Jawa dengan beberapa pulau, salah satunya dengan pulau Madura. Kamal adalah nama pelabuhan yang terletak di Bangkalan, Madura. Kedua pelabuhan tersebut dikelola oleh PT. ASDP (Angkutan Sungai Danau dan Penyeberangan) Indonesia Ferry (Persero).

Penyeberangan Ujung-Kamal adalah penyeberangan yang menghubungkan pulau Jawa dan Madura dengan jarak sejauh 2.5 mil dan ditempuh dalam waktu 20 menit dengan menggunakan feri melintasi selat

Madura, dan sekarang penyeberangan ini dilayani oleh enam kapal feri yang dioperasikan di dua dermaga.

2.3. Penugasan

Masalah penugasan merupakan salah satu kasus khusus pada masalah transportasi dengan jumlah sumber dan tujuan adalah sama serta dengan jumlah setiap sumber maupun tujuan adalah satu. Dalam masalah penugasan feri ini jumlah sumber adalah satu yaitu pelabuhan Ujung dan jumlah tujuannya juga satu yaitu pelabuhan Kamal. Pada masalah ini, tujuan penugasan adalah untuk menjadwalkan transportasi yang digunakan agar sesuai dengan penumpang dan kendaraan yang ada sedemikian hingga kerugian yang ditimbulkan minimal atau keuntungan yang didapatkan maksimal. Dan, dalam tugas akhir ini yang dilakukan adalah meminimalkan kerugian yang terjadi.

2.4. Graf dan Matriks Menurut Jong (2002) suatu graf

terdiri dari dua himpunan yang berhingga yaitu himpunan titik-titik tidak kosong (melambangkan vertex) yang dihubungkan oleh garis-garis (melambangkan edge). Graf sering dinotasikan dengan 𝐺𝐺 = (𝑉𝑉,𝐸𝐸) dengan 𝑉𝑉 adalah himpunan tidak-kosong dari titik (vertex) berhingga = {𝑣𝑣1, 𝑣𝑣2, . . . , 𝑣𝑣𝑛𝑛}, dan 𝐸𝐸 adalah himpunan garis (edge) yang menghubungkan sepasang vertex = {𝑒𝑒1, 𝑒𝑒2, . . . , 𝑒𝑒𝑛𝑛}.

Ada berbagai macam jenis graf. Berdasarkan orientasi arahnya, graf

4

dibagi menjadi dua, yaitu graf tak berarah dan graf berarah.

Sedangkan, menurut Liu (1986) matriks adalah suatu deretan empat persegi panjang dari bilangan-bilangan yang tersusun dari m baris dan n kolom. Untuk selanjutnya dalam pembahasan berikutnya matriks akan digambarkan pada sebuah persegi yang akan dibagi menjadi beberapa baris dan kolom.

Suatu graf dapat disajikan dalam bentuk matriks. Hal ini sangat membantu untuk membuat program yang berhubungan dengan graf, sehingga akan mempermudah perhitungan. Kesulitan utama mempresentasikan graf dalam matriks adalah keterbatasan matriks untuk mencakup semua informasi yang ada dalam graf. Akibatnya, ada bermacam-macam matriks yang digunakan untuk menyatakan suatu graf. Adapun matriks yang berkenaan dengan tugas akhir ini adalah matriks berhubungan langsung (adjacency matrix) dan matriks keterkaitan (incidence matrix). Selanjutnya dalam tugas akhir ini hanya digunakan matriks incidence. Incidence Matrix

Misalkan 𝐺𝐺 adalah graf dengan 𝑛𝑛 buah vertex 𝑣𝑣1, 𝑣𝑣2, … , 𝑣𝑣𝑛𝑛 dan 𝑡𝑡 buah edge 𝑒𝑒1, 𝑒𝑒2, … , 𝑒𝑒𝑡𝑡 . Maka, Incidence Matrix dari graf 𝐺𝐺 adalah matriks 𝐼𝐼(𝐺𝐺) = (𝑚𝑚𝑖𝑖𝑖𝑖 ) berordo 𝑛𝑛𝑛𝑛𝑡𝑡 yang baris-barisnya dilabel dengan label vertex 𝐺𝐺 dan kolom-kolomnya dilabel dengan label edge 𝐺𝐺, sedemikian hingga

mij = �0, jika edge ej tidak terkait dengan titik vi 1, jika edge ej tekait dengan titik vi

�

2.5. Finite Covering

Menurut Ronald (1983) finite covering adalah metode yang dikembangkan dari teori graf. Permasalahan finite covering biasanya diselesaikan dengan metode pencabangan dan metode aljabar. Penugasan kapal feri merupakan salah satu contoh permasalahan finite covering yang penyelesaiannya menggunakan teknik pencabangan (branching method). Definisi 2.5.1:

Covering adalah suatu garis 𝑛𝑛 = 𝑢𝑢𝑣𝑣 yang menutup atau mengcover titik 𝑢𝑢 dan 𝑣𝑣, dengan kata lain bahwa setiap titik sedikitnya bersinggungan dengan satu garis (Ronald, 1983). Definisi 2.5.2 :

Misalkan diberikan graf 𝐺𝐺 = (𝑉𝑉,𝐸𝐸) dengan 𝑉𝑉 = {𝑣𝑣1, … , 𝑣𝑣𝑖𝑖} dan 𝐸𝐸 ={𝑒𝑒1, … , 𝑒𝑒𝑖𝑖 } yang membentuk relasi incidence 𝑣𝑣𝑣𝑣𝑒𝑒 ⇔ 𝑣𝑣𝑣𝑣𝑒𝑒, maka graf tersebut merupakan permasalahan covering (𝑉𝑉,𝑣𝑣,𝐸𝐸) untuk 𝑣𝑣𝑣𝑣𝑉𝑉 dan 𝑒𝑒𝑣𝑣𝐸𝐸 (William F. Lucas, Fred S. Robert and Robert M. Thrall, 1983).

Jika diberikan graph 𝐺𝐺 = (𝑉𝑉,𝐸𝐸) adalah masalah covering (𝐴𝐴,𝑣𝑣,𝐵𝐵) dengan 𝐴𝐴 = 𝑉𝑉,𝐵𝐵 = 𝐸𝐸, 𝑎𝑎𝑣𝑣𝐴𝐴, 𝑏𝑏𝑣𝑣𝐵𝐵, dan R adalah Relasi Incidence Vertex Edge(RIVE). Maka, RIVE dari 𝐴𝐴 ke 𝐵𝐵 diberikan dalam bentuk matriks incidence 𝑣𝑣 = �𝑟𝑟𝑖𝑖𝑖𝑖 � yang mempunyai elemen 1 dan 0, dan diasumsikan bahwa tiap kolomnya minimal mempunyai satu elemen 1. Maka, secara umum dapat dituliskan 𝑟𝑟𝑖𝑖𝑖𝑖 =1 ⇔ 𝑎𝑎𝑖𝑖𝑣𝑣𝑏𝑏𝑖𝑖 , artinya 𝑎𝑎𝑖𝑖 mengcover 𝑏𝑏𝑖𝑖 jika 𝑎𝑎𝑖𝑖𝑣𝑣𝑏𝑏𝑖𝑖 .

2.6. Teknik Reduksi

5

Teknik reduksi adalah teknik awal yang dilakukan sebelum masalah covering diselesaikan dengan metode pencabangan. Definisi 2.6.1:

Suatu sel a dikatakan esensial jika nilainya berada di antara nilai terendah dan nilai tertinggi yang ditandai dengan nilai 1 dan sel a dikatakan inesensial jika tidak berada di antara nilai terendah dan nilai tertinggi yang ditandai dengan 0. (William F. Lucas, Fred S. Robert and Robert M. Thrall, 1983). Definisi 2.6.2 :

Jika diberikan graph 𝐺𝐺 = (𝑉𝑉,𝐸𝐸) maka himpunan bagian vertex {𝑣𝑣1, 𝑣𝑣2, … , 𝑣𝑣𝑠𝑠} dinyatakan sebagai himpunan dominasi jika 𝑣𝑣𝑣𝑣𝑉𝑉 → 𝑣𝑣 = 𝑣𝑣𝑖𝑖 atau {𝑣𝑣, 𝑣𝑣𝑖𝑖 } 𝑣𝑣 𝐸𝐸 untuk 1 ≤ 𝑖𝑖 ≤ 𝑠𝑠, yaitu jika setiap vertex yang berdekatan adalah himpunan bagian. (William F. Lucas, Fred S. Robert and Robert M. Thrall, 1983).

Dengan definisi awal mengenai permasalahan covering secara umum (𝐴𝐴,𝑣𝑣,𝐵𝐵). Maka, sel a dikatakan essensial jika pada titik b dalam covering (𝐴𝐴,𝑣𝑣,𝐵𝐵) sel a merupakan satu-satunya sel dari A yang mengcover titik b di 𝐵𝐵. Dalam hubungannya dengan matriks incidence, kolom b akan memiliki satu elemen pada baris yang berhubungan dengan a. Dalam terminologi matriks dapat ditulis sebagai berikut: Jika 𝑣𝑣 = [𝑟𝑟𝑖𝑖𝑖𝑖 ] merupakan matriks incidence dengan 𝐴𝐴 = {𝑎𝑎1,𝑎𝑎2, … ,𝑎𝑎𝑛𝑛} dan 𝐵𝐵 = {𝑏𝑏1, 𝑏𝑏2, … , 𝑏𝑏𝑚𝑚 }, maka 𝑏𝑏𝑖𝑖 disebut mendominasi 𝑏𝑏𝑘𝑘 (𝑏𝑏𝑖𝑖 > 𝑏𝑏𝑘𝑘) jika 𝑟𝑟𝑖𝑖𝑘𝑘 = 1 → rij = 1 untuk semua 𝑖𝑖, dengan 𝑖𝑖 = 1,2,3, … ,𝑛𝑛 dan 𝑎𝑎𝑖𝑖 dikatakan

mendominasi 𝑎𝑎𝑘𝑘 (𝑎𝑎𝑖𝑖 > 𝑎𝑎𝑘𝑘 ), jika 𝑟𝑟𝑘𝑘𝑖𝑖 = 1 → 𝑟𝑟𝑖𝑖𝑖𝑖 = 1 untuk semua 𝑖𝑖, dengan 𝑖𝑖 = 1,2,3, … . ,𝑚𝑚.

Terdapat tiga aturan pereduksian yang bisa dipakai dalam permasalahan covering yaitu: 1. Semua kolom pada baris esensial

yang pada barisnya mempunyai elemen 1.

2. Dominasi baris. 3. Dominasi kolom.

2.7. Metode Pencabangan Metode pencabangan (branching

method) adalah salah satu metode yang digunakan pada riset operasi untuk penugasan. Untuk mempercepat pencarian ke vertex solusi, maka setiap vertex diberi sebuah nilai ongkos (cost). Vertex berikutnya yang akan diekspansi berdasarkan pada vertex yang memiliki ongkos yang paling kecil (least cost search). Nilai ongkos pada setiap vertex i menyatakan taksiran ongkos termurah lintasan dari vertex i ke vertex solusi (goal node).

Dari pereduksian awal akan dihasilkan dua permasalahan yang lebih kecil. Dari sini akan didapatkan pencabangan yang akan direduksi lagi untuk mendapatkan pencabangan lagi sedemikian hingga akan didapatkan nilai minimalnya.

Langkah-langkah dalam penyelesaian permasalahan finite covering dengan metode pencabangan adalah sebagai berikut: 1. Membentuk matriks awal

perhitungan yang berupa matriks incidence.

6

2. Mencari sel-sel esensial yang berpengaruh, yaitu mencari nilai variabel yang diharapkan akan terpenuhi dalam model.

3. Mencari satu kolom esensial yaitu kolom yang berisi sel esensial untuk mengawali perhitungan.

4. Dari kolom esensial akan didapatkan baris esensial yaitu baris yang mempunyai nilai 1 pada kolom esensial. Baris eensial ini merupakan calon penyelesaian.

5. Mengambil satu baris esensial dan dilakukan penghapusan (reduksi) kolom yang memiliki sel esensial dan juga baris esensial. Hasil sisa penghapusan (reduksi) berupa matriks dengan baris esensial terhapus.

6. Dilakukan dominasi baris yaitu mencari baris dimana elemen bernilai 1 mendominasi baris yang besangkutan.

7. Dilakukan dominasi kolom. 8. Dilakukan pengcoveran terhadap

kolom-kolom esensial yaitu mencari kolom-kolom esensial yang lebih berpengaruh terhadap kolom-kolom esensial yang lain.

9. Kembali ke langkah 5, dihitung sampai baris esensial habis terhitung.

3. METODE PENELITIAN Dalam tugas akhir ini akan

dilakukan penugasan feri lintas penyeberangan Ujung-Kamal setelah beroperasinya jembatan Suramadu. Metode penelitian yang digunakan terdiri dari beberapa tahap yang akan dijabarkan sebagai berikut:

3.1. Pengumpulan dan Pengolahan Data Pada tahap ini dilakukan

pengumpulan data dan kemudian dilanjutkan dengan pengolahan data. Data yang digunakan dalam tugas akhir ini didapat dari PT. ASDP Indonesia Ferry (Persero) cabang Surabaya sebagai pengelola pelabuhan Ujung-Kamal. Data yang telah diperoleh kemudian diolah sehingga didapat data kekuatan armada feri, jumlah penumpang dan pengendara feri, serta biaya operasional feri yang akan digunakan dalam pengerjaan tugas akhir ini. 3.2. Pembentukan Matriks Incidence

Dari data hasil pendapatan dan pengeluaran masing-masing feri, akan disusun matriks Incidence untuk tiap tripnya. Matriks incidence awal ini digunakan untuk melakukan perhitungan pada tahap selanjutnya. 3.3. Penugasan dengan metode

Finite Covering Pada tahap ini, dilakukan

perhitungan dengan metode Finite Covering dengan menggunakan algoritma yang telah ada sampai didapat minimal covering yang nantinya akan dijadikan penyelesaian. Perhitungan dilakukan pada urutan-urutan yang ada untuk tiap tripnya dan di masing-masing dermaga.

3.4. Penarikan Kesimpulan Pada tahap ini dilakukan

penarikan kesimpulan dari hasil perhitungan dan analisis pada tahap sebelumnya.

7

4. PEMBAHASAN 4.1. Perhitungan Pendapatan dan

Pengeluaran Setelah beroperasinya jembatan

Suramadu, dilakukan pereduksian jumlah feri yang beroperasi. Feri yang beroperasi berjumlah enam buah, dan dioperasikan setiap harinya di dua dermaga untuk tetap melayani pengguna jasa penyeberangan yang menggunakan fasilitas penyeberangan. Sementara itu, pendapatan yang diperoleh seringkali tidak seimbang dengan pengeluaran untuk biaya operasional feri maupun biaya untuk perawatan fasilitas dalam feri dan pelabuhan Ujung sendiri.

Dalam tugas akhir ini, dilakukan perhitungan pendapatan dan pengeluaran feri. Pendapatan dihasilkan dari penjualan tiket di pelabuhan untuk lintas penyeberangan Ujung-Kamal. Sedangkan pengeluarannya meliputi modal, biaya tetap, dan biaya perjalanan tiap feri Ujung-Kamal dalam satu tripnya. Satu trip adalah satu kali perjalanan feri menuju pelabuhan Kamal. Berdasarkan data yang telah didapat, diketahui kondisi penyeberangan yang normal terjadi pada tanggal 28 Mei 2011, kondisi yang ramai terjadi pada tanggal 13 Februari 2011, dan kondisi yang sepi terjadi pada tanggal 24 Februari 2011.

4.2. Penugasan feri dengan metode

finite covering Pertama, dibentuk matriks yang

mempresentasikan kekuatan armada pada keadaan normal, didapatkan matriks berikut : Dermaga I 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4

𝑎𝑎1 264 12 18 877.584 𝑎𝑎2 256 15 15 892.905 𝑎𝑎3 230 20 15 747.931 Dermaga III 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4 𝑏𝑏1 208 20 15 736.735 𝑏𝑏2 268 12 19 1.181.295 𝑏𝑏3 400 25 35 1.045.010

Matriks untuk arus penyeberangan yang ramai. Dermaga I 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4 𝑎𝑎1 264 12 18 893.095 𝑎𝑎2 256 15 15 913.899 𝑎𝑎3 230 20 15 779.703 Dermaga III 𝑐𝑐5 𝑐𝑐6 𝑐𝑐7 𝑐𝑐8 𝑏𝑏1 208 20 15 914.702 𝑏𝑏2 268 12 19 1.124.322 𝑏𝑏3 400 25 35 1.017.785

Sedangkan, untuk kondisi penyeberangan yang sepi didapatkan susunan matriks sebagai berikut : Dermaga I 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4 𝑎𝑎1 264 12 18 890.733 𝑎𝑎2 256 15 15 909.561 𝑎𝑎3 230 20 15 781.662 Dermaga III 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4 𝑏𝑏1 208 20 15 918.190 𝑏𝑏2 268 12 19 1.128.609 𝑏𝑏3 400 25 35 1.018.535 dengan : 𝑎𝑎1 adalah feri Tongkol 𝑎𝑎2 adalah feri jokotole 𝑎𝑎3 adalah feri Selat Madura I 𝑏𝑏1 adalah feri Selat Madura II 𝑏𝑏2 adalah feri Gajahmada 𝑏𝑏3 adalah feri Wicitra Dharma 𝑐𝑐1 adalah kapasitas angkut penumpang

dalam kapal

8

𝑐𝑐2 adalah kapasitas angkut roda dua dalam kapal

𝑐𝑐3 adalah kapasitas angkut roda empat dan campuran dalam kapal

𝑐𝑐4 adalah biaya operasi kapal / trip Setelah terbentuk matriks di atas,

langkah selanjutnya adalah melakukan perhitungan untuk setiap urutan pada tiap tripnya pada kondisi penyeberangan yang normal, ramai, dan sepi.

Hal pertama yang dilakukan adalah membentuk matriks incidence untuk tiap urutan dalam satu trip dengan catatan : 1 : semua muatan (penumpang dan

kendaraan) terangkut dalam feri atau hasil pendapatan melebihi biaya operasi.

0 : muatan (penumpang dan kendaraan) tidak terangkut kedalam feri atau pendapatan kurang dari biaya operasi.

dan dilanjutkan dengan perhitungan manual dengan menggunakan algoritma pencabangan. Dalam menggunakan algoritma pencabangan, dipertimbangkan besarnya biaya operasi feri setiap tripnya yang terdapat pada kolom 𝑐𝑐4, dengan tujuan agar kerugian yang terjadi bisa diminimalkan yang selanjutnya akan dijadikan kolom esensial.

Perhitungan untuk penugasan feri pada kondisi penyeberangan yang normal.

Dari matriks di atas, selanjutnya dilakukan perhitungan di dermaga I dan III. Perhitungan untuk dermaga I adalah sebagai berikut : Trip ke-1

Dengan 65 penumpang , 35 roda dua, 6 roda empat campuran dengan

hasil penjualan tiket sebesar Rp. 508.000 pada urutan pertama didapatkan matriks incidence sebagai berikut : 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4 𝑎𝑎1 1 1 1 0 𝑎𝑎2 1 1 1 0 𝑎𝑎3 1 1 1 0

Langkah selanjutnya adalah mencari satu kolom esensial untuk memulai perhitungan. Telah dijelaskan bahwa 𝑐𝑐4 adalah kolom esensial karena memiliki pengaruh besar terhadap untung dan rugi. Dari kolom esensial kemudian dicari baris esensial (baris yang memiliki nilai 1 pada kolom esensial). Dari kolom esensial 𝑐𝑐4, tidak terdapat baris esensial, sehingga diambil kolom lain sebagai kolom esensial. Ini artinya biaya operasi feri tidak sesuai dengan pendapatan yang diperoleh. Selanjutnya, misalkan 𝑐𝑐3 adalah kolom esensial yang baru dengan baris esensial 𝑎𝑎1, 𝑎𝑎2, 𝑎𝑎3. Selanjutnya, adalah mengambil satu baris esensial dan kolom esensial untuk direduksi. Jika diambil 𝑎𝑎2 dan 𝑐𝑐3 untuk direduksi, maka diperoleh : 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑎𝑎1 1 1 0 𝑎𝑎3 1 1 0

Dari matriks di atas, tidak terdapat dominasi baris. Sehingga, langsung dilanjutkan ke tahap berikutnya, yaitu pengcoveran. Dengan melihat biaya operasi yang minimal, maka didapatkan 𝑎𝑎3 yaitu feri Selat Madura I sebagai penyelesaian pada urutan pertama. Selanjutnya, dengan cara yang sama, dilakukan perhitungan untuk urutan kedua dan ketiga. Untuk urutan kedua dengan jumlah penumpang 108, roda

9

dua 66, roda empat campuran 1, dan hasil penjualan tiket sebesar Rp. 615.000,- disusun matriks incidence sebagai berikut : 𝑐𝑐1 𝑐𝑐2 𝑐𝑐3 𝑐𝑐4 𝑎𝑎1 1 1 1 0 𝑎𝑎2 1 1 1 0 Pada kolom esensial 𝑐𝑐4 tidak ada baris esensial. Dengan memisalkan 𝑐𝑐3 sebagai kolom esensial yang baru, didapatkan baris esensial 𝑎𝑎1,𝑎𝑎2. Jika diambil baris esensial 𝑎𝑎2 dan kolom esensial 𝑐𝑐3 untuk direduksi, maka diperoleh: 𝑐𝑐1 𝑐𝑐2 𝑐𝑐4 𝑎𝑎1 1 1 0 Dari matriks di atas, kemudian dilakukan pengcoveran, dan didapatkan feri 𝑎𝑎1 yaitu Tongkol yang akan melayani urutan kedua.

Selanjutnya, untuk urutan ketiga dengan jumlah penumpang 68, roda dua 14, roda empat campuran 2, akan dilayani oleh feri yang masih tersisa yaitu Jokotole.

Untuk trip dua dan selanjutnya, dilakukan dengan cara yang sama dengan cara di atas. Dan dari perhitungan didapatkan hasil sebagai berikut : Tabel 1 : Hasil penugasan feri di

dermaga I pada kondisi normal

Urutan ke Feri yang melayani 1 Selat Madura I 2 Tongkol 3 Jokotole

Tabel 2 : Hasil penugasan feri di dermaga III pada kondisi normal

Urutan ke Feri yang melayani 1 Selat Madura II

2 Wicitra Dharma 3 Gajah Mada

Tabel 3 : Hasil penugasan feri di dermaga I pada kondisi ramai

Urutan ke Feri yang melayani 1 Selat Madura I 2 Tongkol 3 Jokotole

Tabel 4 : Hasil penugasan di dermaga

III pada kondisi ramai Urutan ke Setelah penugasan

1 Selat Madura II 2 Wicitra Dharma 3 Gajah Mada

Tabel 5 : Hasil penugasan feri di dermaga I pada kondisi sepi

Urutan ke Kapal yang melayani 1 Selat Madura I 2 Tongkol 3 Jokotole

Tabel 6 : Hasil penugasan feri di dermaga III pada kondisi sepi

Urutan ke Kapal yang melayani 1 Selat Madura II 2 Wicitra Dharma 3 Gajah Mada

4.2 Pehitungan Laba dan Rugi

Dari perhitungan yang dikerjakan dengan menggunakan metode finite covering pada sub bab sebelumnya, didapatkan hasil penugasan feri di setiap tripnya. Kemudian dilakukan perhitungan laba rugi sebagai berikut :

Berdasarkan hasil pada tabel-tabel di atas, didapatkan perhitungan pendapatan dan pengeluaran berikut : Pendapatan Dermaga I : Rp.20.042.500,-

10

Dermaga III : Rp. 39.566.000,-

Rp.19.523.500,- +

Pengeluaran Dermaga I : Rp.20.147.360 Dermaga III : Rp.23.704.320 Rp.43.851.680,-

+

Dapat diketahui, pada kondisi normal pihak penyedia jasa penyeberangan feri mengalami kerugian sebesar Rp. 4.285.680,- per hari. Sedangkan pada kondisi penyeberangan yang ramai , yaitu pada tanggal 13 Februari 2011, dalam satu hari dihasilkan : Pendapatan Dermaga I : Rp.23.581.000,- Dermaga III : Rp. 46.884.500,-

Rp.23.303.500,- +

Pengeluaran Dermaga I : Rp.20.693.576 Dermaga III : Rp.24.454.472 Rp.45.148.048,-

+

Dapat diketahui, pada kondisi penyeberangan yang ramai, pihak penyedia jasa penyeberangan feri bisa mendapatkan keuntungan sebesar Rp. 1.849.844,-per harinya. Kemudian, pada kondisi penyeberangan yang sepi , yaitu pada tanggal 24 Februari 2011, dalam satu hari dihasilkan : Pendapatan Dermaga I : Rp.13.878.707,- Dermaga III : Rp. 27.756.707,-

Rp.13.878.000,- +

Pengeluaran Dermaga I : Rp.20.655.808,- Dermaga III : Rp.24.454.472,- Rp.45.110.280,-

+

Dari perhitungan di atas, dapat diketahui, pada kondisi penyeberangan yang sepi pihak penyedia jasa penyeberangan feri mengalami kerugian sebesar Rp. 17.353.573,-.

Dalam kenyataannya, feri mengalami kerugian rata-rata sebesar Rp.20 juta sampai dengan Rp.25 juta per harinya. Dan dengan penugasan yang dibuat, kerugian bisa diminimalkan sekitar Rp.7 juta rupiah per harinya, jika kondisi penyeberangan sedang sepi. Sementara dalam keadaan normal, kerugian bisa penugasan yang dilakukan sudah optimal.

5. KESIMPULAN DAN SARAN 5.1 Kesimpulan

Dari penugasan feri dengan metode finite covering, khususnya dengan metode pencabangan dapat disimpulkan bahwa: 1. Dari penugasan yang dilakukan,

untuk semua kondisi penyeberangan pelabuhan Ujung menuju pelabuhan Kamal di dermaga I bisa dilayani oleh feri dengan urutan feri Selat Madura I, Tongkol, Jokotole di setiap tripnya. Sedangkan pada dermaga III, untuk semua kondisi penyeberangan bisa dilayani feri dengan urutan feri Selat Madura II,Wicitra Dharma, Gajah Madadi setiap tripnya.

2. Pada kondisi arus penyeberangan Ujung ke Kamal yang normal terjadi kerugian yang dialami oleh pihak penyedia jasa penyeberangan sebesar Rp. 4.285.680.-, dan pada kondisi yang sepi kerugiannya mencapai Rp. 17.353.573,-. Sedangkan pada kondisi yang ramai, kerugian yang dialami sudah bisa ditanggulangi, karena pada kondisi yang ramai pihak jasa penyeberangan mendapat

11

keuntungan sebesar Rp. 1.849.844,-.

3. Kondisi yang ramai hanya terjadi pada saat tertentu saja. Sehingga dengan keuntungan yang tidak begitu banyak, pihak pengelola feri belum mampu menutupi kerugian yang dialami ketika kondisi penyeberangan sedang sepi maupun normal. Jadi, perlu adanya subsidi dari pemerintah untuk keberlangsungan lintas penyeberangan Ujung-Kamal.

5.2 Saran Saran yang diberikan untuk

penelitian selanjutnya adalah 1. Penelitian bisa dilakukan untuk

penugasan feri pada lintas penyeberangan lain di Indonesia.

2. Penelitian akan lebih baik, jika data muatan yang ada di kapal juga tersedia dalam satuan berat.

DAFTAR PUSTAKA Budayasa, I Ketut. 2007. Teori Graph

dan Aplikasinya. Surabaya. id.wikipedia.org [diakses tanggal 02

Juni 2011]. Siang, Jong Jek. 2002. Matematika

Diskrit dan Aplikasinya pada Ilmu Komputer. Edisi kedua. Yogyakarta: ANDI

Sulistiyo. 2000. Penyelesaian Masalah Penugasan dengan Metode Finite Covering. Prosiding, Jurusan Matematika FMIPA-ITS. Surabaya.

Taha, Hamdy A. 2007. Operations Research an Introduction. Prentice-Hall, Inc. New Jersey.

Taufiq, Rohman. Tarif Kapal Feri Ujung-Kamal. Tempo. Diakses 3 Januari 2011

Wardani, Tjita Kusuma. 2004. Pemilihan Menu Makanan Tradisional Indonesia Bagi Penderita Kadar Asam Urat Tinggi(Hiperurisemia) dengan Metode Finite Covering. Tugas Akhir, jurusan matematika FMIPA-ITS. Surabaya.

William F. Lucas, Fred S. Robert and Robert M. Thrall. 1983. Discrete and System Models. Springer-Verleg. New York Inc., New York.