PENGEMBANGAN METODE PENCARIAN LAYAK UNTUK PERSOALAN ALOKASI DERMAGA

PENGEMBANGAN METODE PENCARIAN LAYAK UNTUK PERSOALAN ALOKASI DERMAGA

TESIS

Oleh

RUSTAM EFENDI PASARIBU 077021071/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

PENGEMBANGAN METODE PENCARIAN LAYAK UNTUK PERSOALAN ALOKASI DERMAGA

TESIS

Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

RUSTAM EFENDI PASARIBU 077021071/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

: PENGEMBANGAN METODE PENCARIAN LAYAK UNTUK PERSOALAN ALOKASI DERMAGA Nama Mahasiswa : Rustam Efendi Pasaribu Nomor Pokok : 077021071 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Tulus, M.Si) Ketua

(Dr. Saib Suwilo, M.Sc) Anggota

Ketua Program Studi

Direktur

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: 29 Mei 2009


Telah diuji pada Tanggal 29 Mei 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Tulus, M.Si

Anggota

: 1. Dr. Saib Suwilo, M.Sc 2. Dr. Sutarman, M.Sc 3. Drs. Marwan Harahap, M.Eng


ABSTRAK Persoalan pengalokasian dermaga merupakan persoalan untuk menentukan lokasi ruang sepanjang dermaga terhadap kapal yang datang di terminal konteiner sehingga meminimalkan fungsi tujuan. Tesis ini mengkaji persoalan meminimisasi total biaya untuk menunggu dan penanganan dan juga atas penyelesaian yang terlalu cepat atau terlalu lambat, untuk semua kapal. Diasumsikan kapal dapat tiba pada setiap waktu tertentu, yaitu sebelum atau setelah tempat berlabuh ada tersedia. Persoalan yang dihasilkan, dapat dinyatakan sebagai program 0-1 campuran linier. Karena akan memakan waktu yang terlalu banyak untuk penyelesaian eksak dari kasus berukuran realistis, diajukanlah Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga. Metode pencarian Layak Untuk Persoalan Alokasi Dermaga memberikan penyelesaian optimal untuk semua kasus yang diselesaikan untuk optimalitas dalam Tesis ini.

Kata kunci : Masalah Alokasi Dermaga, Menunggu, Penanganan, Program Integer, dan Metode Pencarian Layak

i Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

ABSTRACT The berth allocation problem is to allocate space along the quayside to incoming ships at a container terminal in order to minimize some objective function. The consider minimization of total costs for waiting and handling as well as earliness or tardiness of completion, for all ships. The assume ships can arrive at any given time, i.e., before or after the berths become available. The resulting problem, which subsumes several previous ones, is expressed as a linear mixed 0-1 program. As it turns out to be too time-consuming for exact solution of instances of realistic size, a submitted Feasible Search Method For Berth Allocation Problem . Feasible Search Method provides optimal solutions for all instances solved to optimality in this Thesis.

Keywords : Berth Allocation Problem; Waiting; Handling; Integer Programming; and Feasible Search Method.

ii Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

KATA PENGANTAR

Dengan rendah hati penulis mengucapkan segala puji dan syukur kehadirat Tuhan Yang Maha Esa atas berkat rahmat dan ridhoNya penulis dapat menyelesaikan studinya pada Program Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara hingga pada tahap penyelesaian penyusunan tesis yang berjudul, ”Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga”. Tesis ini merupakan salah satu syarat penyelesaian studi pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Penulis menyadari bahwa dari awal hingga selesainya penulisan tesis ini, penulis banyak mendapat dukungan dari berbagai pihak, maka pada kesempatan ini penulis mengucapkan terimakasih yang sebesarbesarnya kepada: Bapak Prof. dr. Chairuddin P. Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk menempuh pendidikan di Universitas Sumatera Utara. Ibu Prof. Dr. Ir. T. Chairun Nisa B., M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang sudah memberi kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Bapak Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Bapak Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang sekaligus seba-

iii Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

gai Pembimbing II penulis yang telah memberi bimbingan dan arahan dalam penulisan tesisi ini. Bapak Dr. Tulus, M.Si selaku Ketua Komisi Pembimbing dan Pembimbing I penulis yang telah banyak memberi bimbingan, saran, dan masukan serta petunjuk penulisan tesis ini sehingga tesis ini dapat diselesaikan. Seluruh Staf Pengajar pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah membekali ilmu pengetahuan kepada penulis selama perkuliahan hingga selesai. Ibu Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan pelayanan yang baik kepada penulis yang berhubungan dengan administrasi penulis selama mengikuti pendidikan. Secara khusus penulis menyampaikan terimaksih dan sayang kepada Anni Theresia Simamora, S.Pd sebagai isteri tercinta yang selalu memberikan perhatian, dukungan dan motivasi kepada penulis selama mengikuti pendidikan pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara. Dan kepada Ananda tersayang Yoseph Herman Pasaribu, Simon Praja Hot Parulian Pasaribu, dan Yossi Alleegra Pasaribu. Seluruh keluarga, Ayahanda A. Pasaribu, Ibunda T. Br. Simanullang (alm) semasa hidupnya, kakak dan adik adikku yang senantiasa mendukung dan mendoakan untuk keberhasilan penulis dalam menyelesaikan pendidikan ini, juga Mertuaku Ibu O. Simatupang dan semua sepupuku yang turut serta mendukung dan mendoakan penulis dalam penyelesaian studinya.

iv Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

Rekan-rekan Mahasiswa Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara angkatan tahun 2007 yang tak dapat penulis sebutkan satu persatu yang telah banyak membantu penulis dalam perkuliahan maupun dalam penulisan tesis ini. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihak-pihak yang memerlukannya, namun penulis sadar bahwa sebagai manusia dalam penulisannya tesis ini masih jauh dari sempurna.

Medan,

Mei 2009

Penulis,

Rustam Efendi Pasaribu

v Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

RIWAYAT HIDUP

Rustam Efendi Pasaribu dilahirkan di Medan pada tanggal 30 Desember 1970 dan merupakan anak kedua dari 6 bersaudara dari Ayah Abdul Sumurung Pasaribu dan Ibu Tiolina br. Simanullang (alm). Pada tahun 1978 penulis pertama sekali mengecap pendidikan pada Sekolah Dasar (SD) Trisakti Kecamatan Medan Sunggal sampai tahun 1980. Pada tahun 1980 karena sesuatu hal penulis pindah sekolah ke SD Bersubsidi Alwasliyah Pinang Baris Medan sampai tahun 1981. Tahun 1981 penulis pindah sekolah lagi ke SD Inpres Hutaraja Habinsaran Kecamatan Sipoholon Kabupaten Tapanuli Utara Provinsi Sumatera Utara dan tamat tahun 1984. Menamatkan Sekolah Menengah Pertama (SMP) pada SMP Negeri Hutaraja Kecamatan Sipoholon Kabupaten Tapanuli Utara Provinsi Sumatera Utara pada tahun 1987, Sekolah Menengah Atas (SMA) Jurusan Fisika (A1) pada SMA Negeri Sipoholon Kabupaten Tapanuli Utara Provinsi Sumatera Utara tahun 1990. Selepas tamat SMA penulis tidak langsung melanjutkan pendidikannya ke jenjang perguruan tinggi tetapi sempat menganggur setahun. Baru setahun kemudian yakni pada tahun 1991 penulis melanjutkan pendidikannya di Institut Keguruan dan Ilmu Pendidikan (IKIP) Medan pada Fakultas Matematika Dan Ilmu Pengetahuan Alam (FMIPA) Jurusan Matematika. Di awal semester II T.A 1991/1992 s.d. Semester III T.A 1992/1993 penulis sempat meninggalkan bangku perkuliahan tanpa pemberitahuan atau tanpa membuat surat izin selang karena ekonomi orang tua yang tidak mendukung serta pasrah tidak melanjutkan perkuliahan lagi. Namun setelah penuh pertimbangan untung ruginya pada tahun 1993 awal semester IV penulis kembali lagi ke kampus IKIP Medan (dengan status stop out) dan mengikuti perkuliahan kembali setelah menyelesaikan administrasi

vi Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

stop out sampai semester genap T.A. 1996/1997. Pada tahun 1995 s/d 1997 sambil mengikuti perkuliahan penulis menjadi Staf Pengajar (Tentor) pada Bimbingan Test/Studi Medica di Medan Dan berhenti karena sakit awal tahun 1997. Tahun 1997 penulis meninggalkan perkuliahan yang kedua kali selama satu tahun s. d. 1998 pada saat penyusunan skripsi namun judul skripsi penulis saat itu sudah di acc pembimbing juga karena ekonomi penulis yang kurang mendukung, dan menjadi staf pengajar di SLTP sw Bunda Mulia Saribudolok Perwakilan Yayasan St. Yoseph Medan. Di awal Tahun 1998 sadar akan batas waktu maksimum duduk di bangku perkuliahan hanya maksimaum 14 semester maka pada semester XIII penulis kembali ke kampus dan berusaha menyelesaikan skripsinya di semester itu dengan tidak meninggalkan pekerjaan sebagai staf pengajar di SLTP Sw Bunda Mulia Saribudolok Perwakilan Yayasan St. Yoseph Medan. Pada tahun 1998 penulis berhasil memperoleh gelar Sarjana Pendidikan dari IKIP Medan. Tahun 1999 penulis lulus Test Pegawai Negeri Sipil (PNS) dan menjadi Staf Pengajar (guru) pada SMAN 1 Onanrunggu Kabupaten Samosir Provinsi Sumatera Utara sampai dengan sekarang. Penulis menikah pada tahun 1998 dan dikaruniai 3 orang anak ( 2 lakilaki dan 1 perempuan). Pada tahun 2007 penulis mengikuti pendidikan pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara

vii Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

viii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .

x

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang Masalah . . . . . . . . . . . . . . . . . .

1

1.1.1 Gambaran Ringkas Masalah Alokasi Dermaga . . . .

5

1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .

8

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .

8

1.4 Manfaat Penelitian . . . . . . . . . . . . . . . . . . . .

9

1.5 Metodologi . . . . . . . . . . . . . . . . . . . . . . . .

9

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . .

11

2.1 Perkembangan Kajian Persoalan Alokasi Dermaga . . . . .

11

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .

18

3.1 Program Integer

. . . . . . . . . . . . . . . . . . . . .

3.2 Metode Pencarian Layak

18

. . . . . . . . . . . . . . . . .

19

3.2.1 Pengembangan Metode . . . . . . . . . . . . . . .

21

viii Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

3.2.2 Penentuan Pivot

. . . . . . . . . . . . . . . . . .

25

. . . . . . . . . . . . . . . . . . . . . . .

27

4.1 Pemodelan Alokasi Dermaga . . . . . . . . . . . . . . . .

27

4.2 Pengkajian Model . . . . . . . . . . . . . . . . . . . . .

28

4.3 Presentasi Model . . . . . . . . . . . . . . . . . . . . .

30

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .

36

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .

37

BAB 4 PEMBAHASAN

ix Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

DAFTAR GAMBAR

Nomor

Judul

Halaman

1.1

Bagan Dermaga . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Lokasi Dermaga . . . . . . . . . . . . . . . . . . . . . . .

6

1.3

Terminal Peti Kemas . . . . . . . . . . . . . . . . . . . .

8

1.4

Alir Tahapan Penelitian . . . . . . . . . . . . . . . . . . .

10

x Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

BAB 1 PENDAHULUAN

1.1 Latar Belakang Masalah Dermaga adalah platform yang menjorok ke dalam air untuk mempermudah bongkar/muat cargo. Ada lebih 2000 dermaga di seluruh dunia mulai dari dermaga yang menangani beberapa ratus ton pertahun hingga fasilitas serbaguna yang menangani 300 juta ton per tahun. Lalu lintas pelabuhan dunia terdiri dari 36% produk massa cair (terutama minyak, produk petroleum dan bahan kimia), 24% barang massa kering (batubara, bijih besi, gabah, bauxit dan phosphat) dan 40% cargo umum. Untuk statistik tentang pengangkutan laut kami rujuk pembaca ke UNCTAD (2004). Dalam 20 tahun terakhir penggunaan peti kemas untuk cargo umum terus meningkat. Peti kemas adalah kotak logam besar yang dibuat dengan ukuran standar dan dengan ukuran dalam kelipatan 20 kaki yang disebut ”unit ekuivalen dua puluh kaki” (TEU). Pada tahun 2003 produksi peti kemas mencapai dua juta TEU, dengan China bertanggungjawab atas lebih dari 90% output ini. Peti kemas memiliki beberapa kelebihan: Membutuhkan lebih sedikit pengepakan produk, membantu mengurangi kerusakan dan menghasilkan produktivitas yang lebih tinggi selama berbagai tahap penanganan. Tambahan lagi, peti kemas memungkinkan transportasi antar-sarana karena pengangkutan antara kapal, truk atau kereta api mudah dilaksanakan. Kapasitas pelabuhan peti kemas dunia untuk tahun 2002 mencapai 266,3 juta TEU, meningkat 22,5 juta TEU dari 243,8 juta TEU pada tahun 2001.

1 Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

2 Dalam transportasi peti kemas, kapal laut-dalam yang juga disebut kapal induk beroperasi di sejumlah terminal pemindahan-angkutan (poros). Kapalkapal kecil (pengisi) menghubungkan poros dengan pelabuhan lainnya (jari-jari). Topologi network ini menghasilkan konsolidasi kapasitas sepanjang rute yang menghubungkan pelabuhan pemindahan-angkutan dan menghasilkan peningkatan arti pentingnya. Di tahun-tahun belakangan ini, ukuran kapal induk bertambah, yang mencapai hingga 8.000 TEU, dan direncanakan ukuran yang lebih besar. Pada tahun 2002 20 pelabuhan peti kemas pertama menangani 48% dari total lalu lintas. Kapal peti kemas ultra-besar menurunkan biaya pengangkutan. Akan tetapi, pelabuhan poros terpaksa berinvestasi besar-besaran untuk menampung kapal ini dengan memperdalam dan memperlebar saluran dan membangun fasilitas berlabuh baru dengan kedalaman dan panjang yang cukup. Trend ini mengharuskan peningkatan kontinu dalam praktek managemen di terminal konteiner. Ketika kapal tiba di pelabuhan, kapal tersebut masuk ke dermaga dan menunggu merapat di dermaga. Lokasi dimana kapal dapat merapat disebut tempat berlabuh yang dilengkapi dengan derek-derek raksasa, yang disebut derek dermaga, yang digunakan untuk membongkar/muat peti kemas yang dipindahkan ke dan dari yard oleh armada kendaraan. Di terminal pemindahan-angkutan yard memungkinkan sebagai tempat penyimpanan sementara sebelum peti kemas dipindahkan ke kapal lain atau ke sarana angkutan lain (misalnya, sarana angkutan kereta api atau jalan raya). Pemindahan peti kemas di yard juga dilaksanakan untuk mempercepat proses bongkar muat. Hal Ini membutuhkan tingkat koordinasi yang tinggi untuk menjamin proses pemindah-angkutan yang cepat. Memang Teknologi komunikasi


3 dan informasi canggih sudah ada, langkah selanjutnya adalah pengenalan teknik optimisasi yang diperlukan untuk managemen logistik yang optimal di terminal peti kemas. Gambaran ringkas dan klasifikasi berbagai peralatan dan masalah keputusan dalam sistem sedemikian bisa diihat dalam Vis dan Koster (2003). Sebuah tinjauan atas isu-isu penelitian operasional dalam logistik perairan laut, yang terfokus pada penentuan-rute dan penjadwalan kapal dipresentasikan dalam Christiansen, Fagerholt dan Ronen (2004).

Gambar 1.1 Bagan Dermaga

Meningkatnya frekuensi transportasi laut akan mengakibatkan sangat sentralnya pelayanan sebuah dermaga sebagai tempat berlabuhnya kapalkapal laut. Banyak kemungkinan masalah yang terjadi jika pelayanan sebuah dermaga sangat sentral. Mulai dari masalah optimisasi waktu berlabuh, minimum cost, jarak dan berbagai macam kemungkinan yang lain. Hal tersebut sangat dipengaruhi penem-


4 patan yang layak untuk alokasi dermaga, oleh karena itu perlu ditinjau kelayakan suatu alokasi dermaga yang tujuannya untuk meminimalkan persoalan alokasi dermaga (Berth Allocation Problem-BAP). Menentukan dermaga yang layak jelas merupakan masalah kombinatorial yang sulit, karena harus dicari banyak cara yang berbeda secara eksponensial untuk memberikan alokasi yang layak kepada setiap kapal. Hal ini berhubungan dengan jarak dan banyaknya dermaga di suatu pelabuhan. Jika jumlah dermaga yang ada tidak bisa dijamin untuk kapal yang datang maka waktu terlambat kapal ini akan meningkat, yang pada gilirannya akan mempengaruhi efisiensi dan karenanya produktivitas kapal ini juga akan mempengaruhi daya saing jika kapal yang datang perlu menunggu dalam waktu yang lama, tingkat layanan yang ditawarkan kepada kapal tersebut tidak layak. Karenanya meminimalkan waktu untuk menunggu kapal yang datang merupakan elemen yang penting dari BAP. Jika waktu penanganan diinimalkan, produktivitas kapal akan meningkat, yang pada gilirannya akan menguatkan menejemen efektif-biaya kapal, karenanya meminimalkan total waktu yang dihabiskan kapal dalam sistem (jumlah waktu menunggu kapal untuk berlabuh dan waktu penanganannya) akan mencerminkan tujuan BAP. Periode waktu yang memisahkan waktu kedatangan dan keberangkatan kapal kerap kali ditetapkan dengan sistem kontrak (atau dengan kata lain selain waktu kedatangan atau waktu keberangkatan, waktu yang seharusnya atau tanggal yang seharusnya, ditetapkan dan sudah mempunyai jadwal yang ditentukan untuk setiap kapal). Jika operasi penanganan selesai sebelum waktu yang seharusnya, yang dengan demikian memungkinkan keberangkatan dini kapal, premi


5 akan dibayar pemilik kapal kepada perusahaan yang mengoperasikan dermaga, jika operasi itu selesai setelah tanggal tersebut, yang dengan demikian memperlambat keberangkatan kapal, maka denda harus dibayar perusahaan yang mengoperasikan dermaga kepada pemilik kapal.

1.1.1 Gambaran Ringkas Masalah Alokasi Dermaga Masalah alokasi dermaga terdiri dari pengalokasian kapal-kapal yang datang ke posisi-posisi berlabuh. Manager menghadapi dua keputusan yang saling terkait, dimana dan kapan kapal-kapal akan merapat. Masa penanganan kapal tergantung pada titik berlabuhnya dan merupakan fungsi dari jarak dari dermaga ke areal tangkapan dan pengiriman peti kemas yang disimpan di yard. Ketergantungan ini sangat mempengaruhi kinerja pelabuhan. Data masa penanganan perlu dibahas secara lebih rinci. Data ini tergantung pada keputusan terkait lainnya, yaitu jumlah derek dermaga yang dialokasikan ke kapal yang datang. Tentu saja, keputusan ini mempengaruhi masa penanganan dan berdampak pada BAP. Dalam sistem yang kompleks seperti pelabuhan pemindahan-angkutan proses pengambilan-keputusan kerapkali bersifat hierarkis. Derek dermaga yang dialokasikan kepada masing-masing kapal dipilih menurut kaidah praktis yang mempertimbangkan panjang kapal dan prioritasnya seperti disajikan pada gambar 1.2 di bawah ini:


6

Gambar 1.2 Lokasi Dermaga

Horizon perencanaan BAP adalah satu minggu, dan rencana berlabuh diupdate setiap hari. Karena masalah diselesaikan dengan horizon berputar, sebagian daerah ruang masa-berlabuh tidak selalu ada tersedia saat masalah dioptimalkan ulang. Beberapa bagian dari dermaga juga mungkin tidak tersedia karena operasi pemeliharaan. Waktu tiba kapal sudah diketahui dimuka. Setiap kapal mempunyai jendela waktu sendiri yang ditentukan oleh waktu tibanya dan waktu penyelesaian maksimalnya yang diperbolehkan. Manager ingin meminimalkan biaya pelabuhan maupun biaya pemakai, yang terkait dengan masa layanan. Disini tujuan dari BAP adalah untuk meminimalkan total masa layanan semua kapal.


7 Karena kapal-kapal tidak sama kebutuhannya, maka jumlah berbobot dari masa layanan kapal mungkin lebih tepat mencerminkan praktek managemen sebagian pelabuhan. Bobot dalam jumlah ini bisa merupakan skema penentuan harga atau jumlah gerakan peti kemas. Pada sebagian varian masalah ketentuan penalti juga bisa dimasukkan dalam fungsi tujuan. Sebagai contoh misalnya, bisa ada penalti bila masa layanan sebuah kapal melebihi nilai kontrak. Jika masalah dipandang dari sudut pandang pemilik, sejumlah besar dermaga tidak bisa disediakan karena setiap dermaga yang menganggur akan menimbulkan biaya bagi pemilik. Karena itu meminimalkan total waktu layanan, yang merupakan jumlah waktu menuggu berlabuh untuk kapal dan penumpangnya akan mencerminkan BAP. Karena itu secara implisit total waktu yang dihabiskan kapal dalam sistem, merupakan fungsi tujuan yang tepat untuk BAP. Penanganan waktu sebuah kapal tergantung dari deret dermaga dan merupakan fungsi dari jarak dan lokasi dermaga. Masalah alokasi dermaga adalah masalah kelayakan alokasi ruang sepanjang dermaga untuk kapal yang masuk dan yang keluar/pergi. Masalah kelayakan lokasi dermaga sebagaimana akan dibahas merupakan masalah taktis perencanaan dan tujuan dalam hal ini adalah untuk mengidentifikasi tempat yang layak sebagai alokasi dermaga. Sehingga pendapatan yang diperoleh pengusaha dermaga maksimal. Dari uraian di atas BAP ditentukan oleh, jarak antara kapal pada suatu dermaga, waktu datang dan pergi kapal, dan pendapatan maksimal.


8

Gambar 1.3 Terminal Peti Kemas

1.2 Perumusan Masalah Yang menjadi masalah dalam penelitian ini adalah: Bagaimana pengembangan metode pencarian layak untuk persoalan alokasi dermaga?

1.3 Tujuan Penelitian Tujuan dari penelitian ini adalah megembangkan metode pencarian layak untuk persoalan alokasi dermaga.


9 1.4 Manfaat Penelitian Penelitian ini diharapkan memberikan sumbangan teoritis dalam bidang matematika khususnya dan bidang perkapalan umumnya, dan ditemukannya metode pencarian layak untuk BAP. Dengan menggunakan metode pencarian layak dapat membantu penyelesaian persoalan alokasi dermaga.

1.5 Metodologi Penelitian ini bersifat literatur dan dilakukan dengan mengumpulkan informasi dan referensi beberapa buku serta jurnal-jurnal dengan langkah-langkah sebagai berikut:

1. Menjelaskan tentang dermaga; 2. Menjelaskan tentang persoalan alokasi dermaga; 3. Menjelaskan tentang kelayakan; 4. Menentukan Metode Pencarian Layak untuk persoalan alokasi dermaga; 5. Menentukan solusi persoalan alokasi dermaga dan 6. Membuat formulasi untuk kesimpulan.


10

Gambar 1.4 Alir Tahapan Penelitian


BAB 2 TINJAUAN PUSTAKA

2.1 Perkembangan Kajian Persoalan Alokasi Dermaga BAP dapat dimodelkan sebagai masalah diskrit jika dermaga dipandang sebagai himpunan berhingga tempat berlabuh. Dalam kasus ini bisa digambarkan sebagai segmen dengan panjang tetap, atau jika dimensi ruang diabaikan, sebagai titik. Akan tetapi, bila kapal-kapal mempunyai panjang yang berbeda-beda, maka membagi dermaga menjadi suatu himpunan segmen adalah sulit karena persyaratan akan sangat bervariasi. Dengan menggunakan segmen-segmen panjang akan dihasilkan pemanfaatan ruang yang buruk, sementara dengan menggunakan segmen-segmen pendek mungkin akan menghasilkan penyelesaian yang tidak layak. Model kontinu mencegah kesulitan ini dengan menganggap bahwa kapal-kapal bisa berlabuh di mana saja sepanjang dermaga. BAP dapat diselesaikan dalam waktu polinomial dengan metode Hungaria karena dapat direduksi menjadi masalah pengalokasian, dengan relaksasi Lagrange yang cocok untuk BAP, di mana sub masalah adalah masalah pengalokasian. Hasil perhitungan menunjukkan bahwa BAP mudah diselesaikan sepanjang kasusnya ”mendekati” kasus statis, dalam artian bahwa sebagian besar kapal sudah ada di pelabuhan saat dermaga tersedia. Fungsi tujuan adalah jumlah masa layanan kapal. Seperti yang ditegaskan penulis, fungsi tujuan ini tidak mempertimbangkan prioritas kapal.


12

Lai, K. K., dan Shih, K. (1992) mengajukan algoritma heuristik untuk alokasi dermaga, yang termotivasi oleh penggunaan dermaga dengan lebih efisien di terminal HIT Hong Kong. Masalah mereka mempertimbangkan strategi alokasi Pertama-Datang-Pertama-Dilayani (FCFS), yang bukan merupakan kasus dalam masalah kita. Dalam kasus diskrit, BAP bisa dimodelkan sebagai masalah penjadwalan mesin paralel tak-terkait, di mana kapal dianggap sebagai pekerjaan dan dermaga sebagai mesin. Waktu kedatangan kapal adalah waktu pelepasan pekerjaan. Dalam kasus kontinu, BAP adalah masalah cutting-stock dua-dimensi dengan batasan-batasan tambahan. Selanjutnya Brown et al. (1994) mengkaji penanganan kapal di pelabuhan angkatan laut. Akan tetapi, studi-studi ini tampaknya tidak tepat untuk pelabuhan komersial karena asumsi yang diajukan dalam studi-studi tersebut tidak begitu umum di pelabuhan komersial. Selanjutnya Imai et al. (1997) mengkaji BAP dalam indeks diskrit yang disebut sebagai DBAP untuk pelabuhan komersial. Mereka menyimpulkan bahwa untuk mencapai produktivitas pelabuhan yang tinggi, himpunan optimal dari alokasi kepal-ke-tempat berlabuh haruslah ditentukan tanpa menggunakan kaidah FCFS. Akan tetapi, prinsip ini bisa menyebabkan kapal tertentu tidak puas dengan urutan layanan mereka. Untuk mengatasi dua kriteria evaluasi yang saling bertolak belakang, mereka mengembangkan heuristik untuk menentukan himpunan penyelesaian non inferior yang memaksimalkan yang disebut pertama dan meminimalkan yang disebut terakhir. Studi mereka mengasumsikan situasi statis,


13 di mana kapal-kapal yang akan dilayani untuk horizon perencanaan semuanya tiba di pelabuhan sebelum proses perencanaan alokasi dermaga. Dalam Lim, A. (1998) dermaga digambarkan sebagai garis kontinu. Heuristik menyelesaikan masalah memutuskan titik berlabuh dengan masa berlabuh kapal diketahui, dengan mengasumsikan masa penanganan konstan. Pendekatan ini tidak menyelesaikan masalah umum, di mana masa berlabuh adalah variabel keputusan dan masa penanganan bervariasi sepanjang dermaga. Nishimura et al. (2001) memperluas lebih lanjut versi dinamik dari DBAP untuk konfigurasi multi-kedalaman air. Mereka menggunakan algoritma genetik (GA) untuk menyelesaikan masalah tersebut. Imai, et al. (2001) mengajukan formulasi masalah alokasi dermaga dinamik (DBAP), di mana dermaga digambarkan sebagai himpunan berhingga dari titiktitik berlabuh. Dengan kata lain, dimensi ruang kapal dan dermaga tidak dipertimbangkan. Formulasi ini disebut dinamik, berbeda dengan formulasi sebelumnya yang disebut masalah alokasi dermaga statis (SBAP), yang mengkaji kasus di mana semua kapal sudah berada di pelabuhan sewaktu dermaga sudah tersedia. Selanjutnya Nishimura, et al.

(2001) mempresentasikan suatu program

bilangan-bulat nonlinier (nonlinear integer program) dan algoritma genetik yang didasarkan pada representasi dimensi ruang yang berbeda di mana dermaga adalah koleksi dari segmen-segmen dan hingga dua kapal bisa berbagi segmen yang sama dalam waktu yang bersamaan jika panjang keduanya sepadan dengan panjang segmen dermaga. Batasan tambahan relatif terhadap kedalaman air di dermaga juga dimasukkan.


14 Selanjutnya Imai et al. (2005) memperluas versi statis dari DBAP ke dalam perlakuan dinamis yang serupa dengan pengobatan statis, tetapi dengan perbedaan bahwa sebagian kapal tiba sementara pekerjaan sudah berlangsung. Studi mereka mengasumsikan kedalaman air sama untuk semua dermaga, walaupun di dalam prakteknya pelabuhan tertentu mempunyai dermaga dengan kedalaman air yang berbeda-beda. Selanjutnya Park dan Kim (2002) menyebutkan tujuan BAP yang terdiri dari biaya yang terkait dengan waktu keterlambatan dan biaya relatif terhadap berlabuh di dermaga yang tidak diinginkan. Walaupun kedua isu ini dinilai sebagai tujuan tunggal dengan cara gabungan, namun keduanya bersesuaian (tidak persis sama) dengan dua tujuan yang akan dinilai dalam studi ini. Akan tetapi, seperti yang akan dibahas kemudian, kedua isu ini pada dasarnya bertolak belakang dan karena itu penyelesaian noninferior perlu dipresentasikan kepada pengambil keputusan, untuk membantunya dalam mengambil keputusan yang lebih informatif. Dalam sebagian situasi nyata, operator terminal menetapkan prirotas yang berbeda-beda pada kapal-kapal yang singgah. Dari sudut pandang ini, Imai et al (2003) memperluas DBAP dalam Imai et al .(2005) untuk menangani kapal-kapal dengan prioritas yang berbeda-beda dan mengkaji bagaimana BAP yang diperluas membedakan penanganan kapal dalam bentuk waktu layanan terkaitnya. Selanjutnya Nishimura, et al. (2001) memperluas Formulasi DBAP untuk mempertimbangkan prioritas layanan, yang ditangani dengan memasukkan dalam fungsi tujuan suku yang bersesuaian dengan masa layanan. Prioritas yang misalnya, didasarkan pada volume juga bisa dimasukkan dalam model. Formulasi yang


15 dihasilkan adalah formulasi nonlinier. Ditunjukkan bahwa dengan relaksasi Lagrange yang tepat, submasalah menjadi masalah pengalokasian kuadratik. Park dan Kim (2003) mengajukan model nonlinear integer programming yang juga mempertimbangkan pengalokasian derek dermaga. Asumsi utama yang memungkinkan pengintegrasian BAP dan QCAP adalah bahwa masa penanganan bervariasi secara linier sesuai dengan jumlah derek dermaga yang dialokasikan kepada kapal. Diakui bahwa ini merupakan aproksimasi atas realitas. Di sini dermaga digambarkan sebagai garis kontinu. Fungsi tujuan yang diminimisasi adalah jumlah suku-suku penalti atas semua kapal. Sebagai contoh misalnya, dalam dimensi waktu, masa tunggu kapal menghasilkan biaya linier untuk pelabuhan. Dalam dimensi ruang, penulis mengasumsikan bahwa titik berlabuh optimal diketahui dan menerapkan suatu penalti bilamana diambil pilihan yang berbeda. Algoritma menggunakan relaksasi Lagrange dan teknik optimisasi subgradient. Kim dan Moon (2003) memformulasikan model mixed-integer linear programming untuk kasus kontinu. Pemecah-masalah komersial dapat menentukan optimum untuk kasus yang melibatkan tujuh kapal dan horizon waktu tiga-hari. Heuristik annealing simulasi diajukan untuk menyelesaikan kasus dimensi realistik. Selanjutnya Studi Park dan Kim (2003), mengatakan satu-satunya studi yang mengkaji bahwa waktu penanganan kapal tergantung pada derek dermaga yang dialokasikan secara linier. Hansen et al. (2008) dalam penelitiannya mengatakan masalah alokasi dermaga untuk menentukan lokasi sepanjang dermaga untuk kapal yang datang di terminal dermaga untuk meminimalkan beberapa fungsi tujuan, mengkaji mini-


16 malisasi total biaya untuk menunggu dan menangani sebaik mungkin atas penyelesaian yang terlalu cepat atau terlalu lambat untuk semua kapal. Penelitiannya mengasumsikan kapal bisa tiba pada setiap waktu tertentu, sebelum atau setelah dermaga tersedia. Dalam Imai et al. (2007) penanganan kapal ganda dalam DBAP seperti Nishimura et al. (2001) diaplikasikan pada terminal yang diperluas dengan prosedur sederhana untuk menangani kapal-kapal kecil di dermaga yang diindentasi. Perbandingan dalam kinerja terminal antara terminal yang diindentasi dan terminal konvensional juga ada dibuat. Imai et al. (2008) mengkaji alokasi dermaga yang efisien di terminal peti kemas yang sangat sibuk di sebuah negara sedang berkembang di mana kapasitas tdermaga sangat terbatas untuk menangani banyak kapal yang singgah. Mereka mengkaji alokasi dermaga di terminal, yang mengalokasikan sebagian kapal ke terminal lain. Ada studi lain tentang berbagai BAP yang karena alasan yang berbedabeda menempuh jalur simulasi sebagai prosedur penyelesaian, seperti Lai dan Shih (1992). Masalah BAP bila tempat berlabuh dianggap sebagai sumber daya kontinu, antara lain, dikaji oleh Lim (1998), Park dan Kim (2002), Imai et al. (2005) dan Cordeau et al. (2005). Ulasan berikut menyangkut isu-isu ini dengan operator kapal, disebutkan bahwa kasus di mana kapal yang tiba lebih awal tetap menunggu sampai kapal yang tiba belakangan dilabuhkan dan dilayani di tempat berlabuh. Namun demikian, juga disebutkan bahwa layanan yang diambil alih sedemikian mungkin dapat diterima sepanjang waktu keberangkatan yang dijanjikan terjamin. Dari


17 sudut pandang ini, minimisasi keterlambatan haruslah lebih mendapat perhatian praktis. Ternyata, seperti yang ditinjau dalam bagian ini, ada studi yang menarik mengkaji isu ini. Dalam tulisan ini dikaji model baru yang disebut Metode pencarian Layak Untuk Persoalan Alokasi Dermaga. Dicatat bahwa keputusan-keputusan di dermaga saling terkait, misalnya keputusan tentang berlabuh terkait erat dengan keputusan tentang penjadwalan.


BAB 3 LANDASAN TEORI

3.1 Program Integer Pada masalah Program Linier penyelesaian optimalnya dapat berupa bilangan real yang berarti penyelesaian bisa berupa bilangan pecahan. Untuk penyelesaian yang berbentuk pecahan jika mengalami pembulatan ke integer terdekat maka hasil yang diperoleh bisa menyimpang jauh dari yang diharapkan. Akan tetapi banyak permasalahan di kehidupan nyata yang memerlukan penyelesaian variabel keputusannya berupa integer sehingga harus dicari model penyelesaian masalah sehingga diperoleh penyelesaian integer yang optimum. Program integer merupakan pengembangan dari Program linier dimana beberapa atau semua variabel keputusannya harus berupa integer. Jika hanya sebagian variabel keputusannya merupakan integer maka disebut program Integer Campuran (Mixed Integer Programming). Jika semua variabel keputusannya bernilai integer disebut Program Integer Murni (Pure Integer Programming). Sedangkan Program Integer 0-1 merupakan berntuk Program Integer dimana semua variabel keputusannya harus bernilai integer 0 atau 1 (binary). Bentuk umum model Program Integer adalah: max(min) Z =

X

cj xj


19 Kendala X

aij xj (≤, =, ≥)bi, (i = 1, 2, . . . , m)

xj ≥ 0, (j = 1, 2, . . . , n) xj bernilai integer untuk beberpa atau semua j Bentuk umum model Program Integer 0-1 adalah: X max(min) Z = cj xj X kendala aij xj (≤, =, ≥)bi, (i = 1, 2, . . . , m) xj ≥ 0, (j = 1, 2, . . . , n)

3.2 Metode Pencarian Layak Perhatikan masalah MILP dengan bentuk berikut Minimalkan P = cT x Dengan batasan Ax ≤ b

(3.1) (3.2)

x≥0

(3.3)

xj bilangan bulat untuk beberapa j ∈ J

(3.4)

Suatu komponen vektor layak dasar optimal (xB )k , untuk MILP yang diselesaikan sebagai kontini bisa ditulis sebagai (xB )k = βk − αk1 (xN )1 − · · · − αkj (xN )j − · · · − αkn − m(xN )n − m

(3.5)

Catat bahwa, rumus ini bisa ditemukan dalam tabel akhir prosedur Simplex. Jika (xB )k adalah variabel bilangan bulat dan diasumsikan bahwa βk bukan


20 bilangan bulat, maka pempartisian βk ke dalam komponen bilangan bulat dan komponen pecahan diberikan βk = [βk ] + fk , 0 ≤ fk ≤ 1

(3.6)

andaikan kita ingin meningkatkan (xB )k ke bilangan bulat terdekat, ([β] + 1). Berdasarkan ide penyelesaian suboptimal dapat dinaikkan variabel nonbasis tertentu, katakanlah (xN )j ∗ , di atas batas nolnya, asalkan αkj ∗ , sebagai salah satu elemen dari vektor αj ∗ , negatip. Misalkan ∆j ∗ adalah jumlah gerakan nonvariabel (xN )j ∗ , sedemikian sehingga nilai numerik dari skala (xB )k bilangan bulat. Kemudian, dengan mengacu kepada Persamaan (3.5), ∆j ∗ dapat dinyatakan sebagai ∆f ∗ =

1 − fk −αkj ∗

(3.7)

sementara nonbasis lainnya tetap sama dengan nol. Dapat dilihat bahwa setelah mensubstitusi (3.6) ke dalam (3.7) untuk (xN )j ∗ dan dengan memperhitungkan pempartisian βk yang diberikan dalam (3.6), diperoleh (xB )k = [β] + 1 Dengan demikian, (xB )k sekarang merupakan bilangan bulat. Sekarang jelaslah sudah bahwa variabel nonbasis memegang peranan penting untuk menjadikan variabel basis yang bersesuaian bilangan bulat. Karena itu, hasil berikut diperlukan untuk menegaskan bahwa haruslah variabel non-bilangan bulat yang ditangani dalam proses menjadikan bilangan bulat.

Teorema 1 Andikan masalah MILP (3.1)-(3.4) mempunyai penyelesaian optimal, maka beberapa variabel nonbasis, (xN )j , j = 1, . . . , n haruslah variabel nonbilangan bulat.


21 Bukti. Masalah diselesaikan sebagai slack variable kontinu (yang bukan bilangan bulat, kecuali dalam kasus batasan kesamaan). Jika diasumsikan bahwa vektor variabel basis xB terdiri dari semua slack variable maka semua variabel bilangan bulat akan termasuk dalam vektor xN dan karenanya bernilai bilangan bulat.

3.2.1 Pengembangan Metode Tampak jelas bahwa komponen-komponen lainnya, a(xB )i6=k , dari vektor xB juga akan terpengaruh apabila nilai anumerik dari skalar (xN )j ∗ meningkat menjadi ∆j ∗ . Akaibatnya, jika ada elemen dari vektor αj ∗ , yaitu αj ∗ untuk i 6= k positip, maka elemen xB yang bersesuaian akan turun, dan akahirnya bisa melewati nol. Akan tetapi, setiap komponen vektor x haruslah tidak boleh di bawah nol disebabkan batasan nonnegativitas. Karena itu, rumus disebut test ratio minimum dibutuhkan untuk melihat bagaimana gerakan maksimum nonbasis (xN )j ∗ sedemikian sehingga seluruh komponen x tetap layak. Test ratio ini akan mencakup dua kasus. 1. Variabel basis (xB )i6=k mula-mula turun menjadi nol (batas bawah). 2. Variabel basis (xB )k naik menjadi bilangan bulat. Pada pokoknya, bersesuaian dengan masing-masing kedua kasus di atas ini, akan dihitung θ1 =

min i6=k|αj ∗ >0

βi αj ∗

θ2 = ∆j ∗


(3.8) (3.9)

22 Sejauh mana didapat melepaskan nonbasis (xN )j ∗ dari batas nolnya, sedemikian sehingga x tetap layak, akan tergantung pada test ratio θ∗ yang diberikan di bawah ini θ∗ − min(θ1, θ2)

(3.10)

Yang jelas, jika θ∗ = θ1, salah satu variabel basis (xB )i6=k akan mengenai batas bawah sebelum (xB )k menjadi bilangan bulat. Jika θ∗ = θ2 , nilai numerik dari variabel basis (xB )k akan berupa bilangan bulat dan kelayakan tetap terjaga. Secara analog, akan dapat mereduksi nilai variabel basis (xB )k ke nilai terdekatnya [βk ]. Dalam kasus ini tingkat pergerakan variabel nonbasis tertentu (xN )j ∗ yang bersesuaian dengan suatu elemen positip dari vektor αj ∗ , diberikan oleh ∆f =

fk αkj

(3.11)

Untuk mempertahankan kelayakan, test ratio θ∗ tetap dibutuhkan. Perhatikan pergerakan variabel nonbasis tertentu ∆ sebagaimana dinyatakan dalam Persamaan (3.7) dan (3.11). Satu-satunya faktor yang perlu dihitung adalah elemen vektor α yang bersesuaian. Vektor αj bisa dinyatakan sebagai αj = B −1 aj , j = 1, . . . , n − m

(3.12)

Karena itu, untuk memperoleh elemen tertentu dari vektor αj kita harus dapat membedakan kolom matriks [B]−1 yang bersesuaian. Andaikan diperlukan nilai dari elemen αkj ∗ , dengan memisalkan vkT adalah vektor kolom k dari [B]−1, maka diperoleh vkT = eTk B −1

(3.13)

Selanjutnya, nilai numerik dari αkj ∗ dapat diperoleh dari αkj ∗ = vkT aj ∗


(3.14)

23 Dalam terminologi Linear Programming (LP) operasi yang dilaksanakan dalam Persamaan (3.13) dan (3.14) disebut operasi penetapan harga. Vektor biaya tereduksi dj digunakan untuk mengukur kemunduran nilai fungsi tujuan yang disebabkan dengan melepaskan variabel nonbasis dari batasnya. Akibatnya, dalam memutuskan nonbasis mana yang harus dilepaskan dalam proses penetapan bilangan bulat, vektor dj haruslah diperhitungkan, sedemikian sehingga kemunduran terminimalkan. Ingat bahwa penyelesaian kontinu minimum memberikan batas bawah untuk setiap penyelesaian layak-bilangan bulat. Namun demikian, tingkat pergerakan variabel nonbasis tertentu seperti yang diberikan dalam Persamaan (3.7) atau (3.11), tergantung dengan sesuatu cara pada elemen vektor αj yang bersesuaian. Karena itu, dapat diamati bahwa kemunduran nilai fungsi tujuan disebabkan pelepasan variabel nonbasis (xN )k bisa diukur dengan pecahan dk αkj ∗

(3.15)

di mana |a| berarti nilai absolut dari skalar a. Kemudian untuk meminimalkan kemunduran penyelesaian kontinu optimal digunakan strategi berikut untuk memutuskan variabel nonbasis mana yang bisa dinaikkan dari batas nolnya, yaitu min j

dk αkj ∗

, j = 1, . . . , n − m

(3.16)

Dari strategi batasan aktif dan pempartisian batasan yang bersesuaian dengan variabel basis (B), superbasis (S) dan nonbasis (N) dapat kita tulis "x # b b B S N xN = bN I xS


(3.17)

24 atau Bxb + SxS + N xN = b xN = bN

(3.18) (3.19)

Matriks basis B diasumsikan merupakan matriks bujursangkar dan nonsinguler, kita peroleh xB = β − W xS − αxN

(3.20)

di mana β = B −1b

(3.21)

W = B −1 S

(3.22)

α = B −1 N

(3.23)

Rumus (3.19) menunjukkan bahwa variabel nonbasis ditetapkan sama dengan batasnya. Terbukti melalui rumus yang ”hampir” dasar Persamaan (3.20), strategi penetapan bilangan bulat yang dibahas dalam bagian sebelumnya, yang dirancang untuk masalah MILP bisa diimplementasikan. Khususnya, dapat dilepaskan variabel nonbasis dari batasnya, Persamaan (3.19) dan menggantinya dengan variabel basis yang bersesuaian dalam proses penetapan bilangan bulat, walaupun penyelesaian akan mengalami degenerasi. Lebih jauh lagi, Teorema (3.1) di atas juga bisa diperluas untuk masalah MINLP.

Teorema 2 Andaikan masalah MINLP mempunyai penyelesaian kontinu optimal dengan batas, maka selalu bisa diperoleh non-bilangan bulat yj pada vektor variabel basis optimum.


25 Bukti.

1. Jika variabel ini nonbasis, variabel ini akan berada pada batasnya. Karena itu, variabel ini bernilai bilangan bulat. 2. Jika yj superbasis, dimungkinkan menjadikan yj basis dan membawa nonbasis pada batasnya untuk menggantikannya dalam superbasis.

Akan tetapi, test ratio yang dinyatakan dalam (3.10) tidak bisa digunakan sebagai alat untuk menjamin bahwa penyelesaian optimal bilangan bulat akan tetap berada di daerah layak. Namun, digunakan test kelayakan dari Minos untuk memeriksa apakah penyelesaian bilangan bulat layak atau tidak layak.

3.2.2 Penentuan Pivot Sekarang ini, permasalahannya berada di posisi di mana variabel basis tertentu (xB )k dijadikan bilangan bulat, yang dengan demikian variabel nonbasis yang bersesuaian, (cN )j ∗ , dilepaskan dari batas nolnya. Anadikan pergerakan maksimum dari (xN )j ∗ memenuhi θ∗ = ∆j ∗ sedemikian sehingga (xB )k bernilai bilangan bulat untuk mengeksploitasi cara pengubahan basis dalam MINOS, kita akan dapat menggerakkan (xN )j ∗ ke dalam B (untuk menggantikan (xB )k ) dan (xB )k bernilai bilangan bulat ke dalam S untuk mempertahankan penyelesaian bilangan bulat. Sekarang diperoleh penyelesaian degenerasi karena variabel basis berada pada batasnya. Proses penetapan bilangan bulat kontinu dengan himpunan baru [B, S]. Dalam kasus ini, pada


26 akhirnya bisa berakhir dengan semua variabel bilangan bulat merupakan superbasis.

Teorema 3 Ada penyelesaian suboptimal untuk masalah MILP dan MINLP di mana semua variabel bilangan bulat adalah superbasis.

Bukti

1. Jika semua variabel bilangan bulat ada dalam N, maka variabel tersebut akan merupakan batas. 2. Jika variabel bilangan bulat adalah basis maka dimaungkinkan untuk a. menukarnya dengan variabel kontinu superbasis, atau b. menjadikan variabela bilangan bulat ini superbasis dan membawa nonbasis ke batasnya untuk menggantinya dalam basis yang menghasilkan penyelesaian degenerasi.

Kasus lainnya yang bisa terjadi adalah bahwa variabel basis yang berbeda (xB )i6=k bisa mengenai batasnya sebelum (xB )k menjadi bilangan bulat. Atau dengan kata lain, berada dalam situasi di mana θ∗ = ∆1 Dalam kasus ini digerakkan variabel basis (xN )i ke dalam N dan posisinya di dalam vektor variabel basis akan digantikan oleh nonbasis (xN )j ∗ . Catat (xB )k tetap merupakan variabel basis non-bilangan bulat dengan nilai baru.


BAB 4 PEMBAHASAN

4.1 Pemodelan Alokasi Dermaga Pertama-tama diasumsikan bahwa:

a. Suatu himpunan B dari dermaga, yang diberi indeks dengan i = 1, 2, . . . , I yang tersedia di pelabuhan container untuk menerima kapal, dari waktu Si , i = 1, 2, . . . , I, berturut-turut dan seterusnya. b. Suatu himpunan V dari kapal, yang diberi indeks dengan j = 1, 2, . . . , T sampai ke pelabuhaan pada waktu kedatangan Aj , j = 1, 2, . . . , T dan mungkin harus menunggu sebelum dilayani. Ini mengisyaratkan biaya tunggu tergantung kapal αj per satuan waktu. c. Setiap dermaga dapat menagani satu kapal sekali melayani atau tetap menganggur untuk suatu jangka waktu. d. Setiap kapal j bisa ditangani di setiap dermaga i, dengan waktu penanganan tij dan biaya penanganan cij , i = 1, 2, . . . , I, j = 1, 2, . . . , T , tergantung pada kapal dan dermaga. d. Semua kapal akan dilayani, pada atau sebelum tanggal yang seharusnya Dj , j = 1, 2, . . . , T , jika memungkinkan dan optimal untuk minimisasi biaya; kesegeraan, yaitu menyelesaikan penanganan sebelum Dj akan memberikan premi βj tergantung kapal per satuan waktu dan keterlambatan,


28 yaitu menyelesaikan penanganan setelah Dj akan mengisyaratkan denda γj tergantung-kapal per satuan waktu. Selain itu, kita asumsikan βj < γj . f. Total biaya, yaitu, jumlah biaya menunggu, biaya penanganan, biaya kesegeraan dan biaya keterlambatan untuk semua kapal akan diminimalkan.

Masalah ini akan disingkat sebagai MCBAP. Seperti yang telah disebutkan dalam pendahuluan, Imai et al. (2003) merumuskan PBAP, seperti yang telah ditunjukkan sebelumnya, merupakan kasus MCBAP, sebagai program matematik 0-1 campuran, kuadratik dalam variabel 0-1 dan linier dalam variabel kontinu. Selanjutnya dipresentasikan model liner programming 0-1 campuran yang lebih sederhana untuk MCBAP. Model ini memperluas salah satu model Hansen dan Oguz (2003) yang diajukan untuk DBAP. Perubahan yang berarti, yaitu variabel, fungsi tujuan dan batasan baru dibutuhkan dalam generalisasi ini.

4.2 Pengkajian Model Dikaji dua himpunan variabel biner:

(i) Variabel xijk terkait dengan keputusan dimana dan kapan menangani kapal:    1 jika kapal ke-j adalah ditangani ke-k di dermaga ke-i Xijk =   0 untuk lainnya (Perhatikan bahwa notasi x0ijk digunakan dalam Hansen dan Oguz (2003) untuk tujuan ini, sebagai pengganti xijk , yang dicanangkan untuk penanganan kapal dengan urutan kronologis terbalik. Ini tidak perlu, tidak berguna, dalam tulisan ini).


29 (ii) Variabel zik terkait dengan keputusan menggunakan dermaga atau tidak.    1 jika tidak ada kapal ditangani ke-k di dermaga i Zik =   0 untuk lainnya Kendala akan dibutuhkan untuk menghindari inkonsistensi, yaitu kapal ditangani sebagai ke-k tetapi tidak sebagai ke-(k − 1) di dermaga i. Tambahan lagi, empat himpunan variabel kontinu dipertimbangkan: (iii) Variabel Sik terkait dengan awal penanganan cargo:    1 waktu saat mana kapal ke-k mulai ditangani di dermaga ke-i Sik =   0 jika tidak ada kapal (iv) Variabel yik dimasukkan untuk memperhitungkan biaya satuan αj untuk menunggu, sambil menjaga model tetap linier:    αj Sik jika kapal ke-j adalah ditangani ke-k di dermaga ke-i Yik =   0 jika tidak ada kapal (v) Variabel eik dimasukkan untuk memperhitungkan biaya satuan βj untuk kesegeraan (atau keuntungan, apabila muncul dengan tanda negatif dalam fungsi tujuan), sambil menjaga model tetap linier.     βj (Dj − sik − tij ) jika kapal ke-j adalah ditangani ke-k di dermaga     eik = ke-i dan Dj − sik − tij ≥ 0       0 jika tidak ada kapal


30 (vi) Variabel lik dimasukkan untuk memperhitungkan biaya satuan γj untuk keterlambatan, sambil menjaga model tetap linier.     γj (sik + tij − Dj ) jika kapal ke-j adalah ditangani ke-k di dermaga     lik = ke-i dan (sik + tij − Dj ) ≥ 0       0 untuk lainnya 4.3 Presentasi Model Sekarang dipresentasikan model berikut, yang diikuti dengan penjelasan tahap demi tahap: min

XX

yik −

X

αj Aj +

j∈v

i∈B k∈v

XXX i∈B j∈V k∈V

cij xijk −

XX i∈B k∈V

eik +

XX

ìk (4.1)

i∈B k∈V

Kendala : XX

xijk = 1 ∀j ∈ V

(4.2)

j∈B k∈V

X

xijk + zik = 1

∀i ∈ B, k ∈ V

(4.3)

j∈V

zik ≥ zi,k−1 ∀i ∈ B, k ∈ V \{1} X sik ≥ Aj xijk ∀i ∈ B, k ∈ V

(4.4) (4.5)

j∈V

si1 ≥ Si − si zi1 ∀i ∈ B X sik ≥ si,k−1 + tij xij,k−1 − Mik zik

(4.6) ∀i ∈ B, k ∈ V,

(4.7)

j∈V 0 0 xijk − Mik yik ≥ αj sik + Mik

∀i ∈ B, k ∈ V, j ∈ V,

j.zjb ≤ tj untuk ∀j, ∀b eik −

βj 00 00 ìk ≤ βj Dj xijk − βj sik − βj tij xijk − Mik xijk + Mik (1 − zik ) γj


(4.8) (4.9)

31

∀i ∈ B, k ∈ V, j ∈ V,

(4.10) 000

000

ìk ≥ −γj Dj xijk + γj sik + γj tij xijk + Mik xijk − Mik ∀i ∈ B, k ∈ V, j ∈ V,

(4.11)

xijk ∈ {0, 1} ∀i ∈ B, k ∈ V, j ∈ V,

(4.12)

zik ∈ {0, 1}

(4.13)

∀i ∈ B, k ∈ V, j ∈ V,

sik ≥ 0 ∀i ∈ B, k ∈ V, j ∈ V,

(4.14)

yik ≥ 0 ∀i ∈ B, k ∈ V, j ∈ V,

(4.15)

ìk ≥ 0 ∀i ∈ B, k ∈ V, j ∈ V,

(4.16)

eik ≥ 0 ∀i ∈ B, k ∈ V, j ∈ V,

(4.17)

0 Nilai untuk Mik , Mik , M 00 ik , dan M 000ik bisa dipilih sebagai berikut:

1. Mik adalah jumlah Aj terbesar dan (k − 1)tij terbesar; 0 sama dengan αj terbesar dikali Mik ; 2. Mik 00 sama dengan βj terbesar dikali (Dj − Aj ); 3. Mik 000 sama dengan γj terbesar dikali Mik . 4. Mik

Fungsi tujuan (4.1) menyatakan minimisasi ketiga jenis biaya. Dua suku pertama bersesuaian dengan biaya menunggu. Perhatikan bahwa tanggal awal berbobot dijumlahkan menurut dermaga dan kapal yang ditangani di sana (dengan menggunakan variabel yik dimana nilai yang tepat akan dijamin oleh kendala (4.5)-(4.8) sementara tanggal kedatangan hanya dijumlahkan untuk semua kapal. Suku ketiga bersesuaian dengan biaya penanganan. Suku keempat dan kelima bersesuaian


32 dengan premi kesegeraan dan denda keterlambatan, yang lagi-lagi dijumlahkan menurut dermaga dan kapal yang ditangani di sana. Kendala (4.2) menyatakan bahwa setiap kapal harus ditangani pada satu dan hanya satu dermaga, karena kapal ke-k ditangani di sana untuk suatu k. Kendala (4.3) menyatakan bahwa kapal ke-j dapat ditangani ke-k di dermaga ke-i (yaitu, xijk = 1, xilk = 0∀l ∈ V \{j}, zik = 0) atau tidak ada kapal ke-k ditangani di dermaga tersebut (yaitu, xilk = 0, ∀l ∈ V, zik = 1) Kendala (4.4) menjamin kekuatan nilai variabel zik : jika zik = 1, yaitu jika tidak ada kapal ke-k ditangani di dermaga i maka tidak ada kapal lebih lanjut yang akan ditangani di sana. Kendala (4.5) menetapkan bahwa waktu sik pada saat mana cargo kapal ke-j, dilayani ke-k di dermaga ke-i, mulai ditangani tidak boleh lebih kecil dari waktu kedatangannya Aj . Jika zik = Aj tidak ada waktu menunggu untuk kapal; untuk lainnya waktu menunggu sama dengan sik − Aj . Kendala (4.6) menyatakan bahwa jika dermaga i memang digunakan yaitu zil = 0, maka waktu saat mana cargo kapal pertama yang dilayani di sana mulai ditangani tidak bisa lebih kecil dari waktu saat mana dermaga ini menjadi tersedia. Dalam hal lainnya, dermaga tidak digunakan, zil = 1 dan sil bisa menjadi sama dengan 0 (sebagaimana dibutuhkan untuk mempunyai nilai fungsi tujuan yang tepat). Tambahan lagi, minimisasi yil dalam fungsi tujuan akan memaksa sil nilai ini disebabkan kendala (4.8). Kendala (4.7) menghitung secara rekursif nilai-nilai dari sik ; di dermaga i, jika kapal ke-k dilayani (zik = 0) waktu sik saat mana cargo mulai ditangani tidak


33 bisa lebih kecil dari waktu si,k−1 saat mana cargo dari kapal ke-j sebelumnya yang dilayani di dermaga ke-i mulai ditangani plus waktu penanganannya tij . Sekali lagi, jika kapal ke-k ditangani di dermaga ke-i, maka zik dan ruas kanan dari (4.7) menjadi non-positif (disebabkan nilai Mik ). Tambahan lagi, sik akan terpaksa turun ke nilai ini dengan minimisasi yik dalam fungsi tujuan dan kendala (4.8). Kendala (4.8), yang penting untuk model, memasukkan variabel tambahan yik untuk memperoleh waktu awal berbobot αj sik dalam model linier. Dalam hal ini perlu diketahui kapal ke-j mana yang akan ditangani pada posisi ke-k di dermaga ke-i. Ini dispesifikasi oleh xijk = 1: maka kedua suku terakhir pada ruas kanan dari (4.8) lenyap dn minimasasi yik dalam fungsi tujuan memaksanya turun ke nilai αj sik . Jika xijk = 0 ruas kanan dari (4.8) non-positip dan yik akan terpaksa turun ke 0. Kendala (4.9) menyatakan tentang waktu yang disediakan untuk berlabuh. Kendala (4.10) dan (4.11) serupa dengan kendala (4.8) dan digunakan untuk mendapatkan premi berbobot untuk kesegeraan dan denda berbobot untuk keterlambatan dalam model linier, masing-masing melalui variabel eik dan lik . Kendala (4.11) tidak rumit dan menyatakan bahwa batas bawah berbobot γj (sik + tij − Dj ditetapkan atas keterlambatan berbobot lik jika kapal ke-j ditangani sebagai kapal ke-k di dermaga ke-i ( yaitu, xijk = 1). Dalam hal lainnya, ruas kanan dari (4.11) tereduksi ke nilai negatif. disebabkan suku terakhirnya. Kendala (4.10) dijelaskan lebih rinci dengan tiga kasus sebagai berikut:

(i) Jika Dj − sik − tij > 0 bila kapal ke-j ditangani sebagai kapal ke-k di dermaga ke-i (yaitu, xijk = 1 dan zik = 0), kesegeraan positif dan ruas


34 kanan menetapkan batas atas β(Dj − sik − tij ) atas kesegeraan berbobot eik ; untuk semua l#j lainnya, 1 ∈ V (dengan xilk = 0) ruas kanan dalam (4.10) lebih besar daripada nilai disebut disebabkan suku terakhir; karenanya batas ini akan dicapai apabila eik mencapai koefisien negatip dalam fungsi tujuan dan tidak muncul dalam batasan lainnya selain dari (4.10) kecuali untuk eik > 0). (ii) Jika sik +tij −Dj > 0 bila kapal ke-j ditangani sebagai kapal ke-k di dermaga ke-i (yaitu, lagi-lagi xijk = 1 dan zik = 0), keterlambatan dan keterlambatan berbobot lik adalah positif; jika eik sendiri yang ada dalam ruas kiri dari (4.10), ini akan mengimplikasikan batas atas negatif dan kontradiksi dengan β

eik ≥ 0; karenanya suku korektif − γjj lik ditambahkan pada ruas kiri ini, maka jika (4.11) ketaksamaan murni, kendala (4.10) tereduksi ke batas atas nol pada eik , batas atas ini akan dicapai sebagaimana halnya untuk semua 1#j lainnya, 1 ∈ V (dengan xilk = 0) kendala (4.11) memberikan batas atas besar, dan setiap penyelesaian di mana lik akan benar-benar lebih besar daripada batas bawahnya dan karenanya eik positip dan sedemikian sehingga (4.10) ketaksamaan ketat, tidak akan optimal jika

βj γj

< 1.

(iii) Jika tidak ada kapal ke-j ditangani sebagai kapal ke-k di dermaga ke-i (yaitu, xijk = 0, ∀j ∈ V dan zik = 1), sik = 0 dan ljk = 0 karena alasan yang sama dengan yang disebutkan di atas, maka (4.10) tereduksi menjadi eik ≥ 0.

Kendala-kendala lainnya menetapkan bahwa kapal j ditangani pada posisi k di dermaga i atau tidak sama sekali, sehingga dermaga i menangani secara keseluruhan atau tidak sama sekali cargo kapal ke-k, dan terkhir bahwa waktu awal tak berbobot dan berbobot dan juga kesegeraan dan keterlambatan berbobot


35 untuk penanganan cargo non-negatif. Seperti yang disebut diatas, model MCBAP merangkum beberapa model sebelumnya sebagai kasus tertentu, tentu saja.

(i) Dengan menghilangkan eik dan lik , dan juga kendala (4.10) dan (4.11), maka dengan menetapkan cij = αj tij untuk semua i ∈ B, j ∈ V , menghasilkan model untuk WDBAP (atau PBAP); (ii) Dengan menetapkan lebih lanjut αj = 1 untuk semua j ∈ V , memberikan model untuk DBAP (iii) Terakhir, juga dengan menetapkan Aj = 0 untuk semua j ∈ V dan Si = 0 untuk semua i ∈ B memberikan model untuk BAP (yang bagaimanapun tidak akan merupakan model paling efisien, seperti yang ditunjukkan Imai et al.(1997) bahwa BAP bisa direduksi menjadi masalah penugasan klasik, untuk mana algoritma polinomial ada tersedia.

Beberapa percobaan atas model (4.1)-(4.17) ada dilakukan dengan menggunakan CPLEX 8.1 untuk menilai ukuran masalah yang dapat diselesaikan secara eksak dalam waktu yang layak. Ditemukan bahwa ini merupakan hasil yang diperkirakan karena formulasi yang diberikan adalah formulasi alamiah dan tidak diupayakan menyelesaikan kendala kasus yang dapat diselesaikan. Karena itu, dalam studi ini diajukan heuristik yang didasarkan pada pengamatan ini dan melempangkan jalan untuk penelitian masa mendatang.


BAB 5 KESIMPULAN

Penelitian ini membahas Pengembangan metode pencarian layak untuk masalah alokasi dermaga. Model baru untuk alokasi dermaga adalah diperkenalkannya masalah alokasi dermaga biaya minimum (MCBAP). Model ini adalah masalah integer programing 0-1 linier campuran, model ini merangkum sebagai kasus khusus masalah alokasi dermaga. Ini lebih realistis dari pada model sebelumnya dimana model tidak mengasumsikan biaya penanganan sebanding dengan waktu penanganan dan memperhitungkan premi kesegeraan dan denda keterlambatan tergantung kapal. Dari kendala master problem ditetapkan bahwa setiap kapal harus ditangani pada satu dan hanya satu dermaga saja. Setiap satu dermaga digunakan hanya untuk melayani sekumpulan kapal tertentu dan selalu melayani kapal yang sama.


DAFTAR PUSTAKA

Brown, G. G., Lawphongpanich, S., and Thurman, K. P. 1994. Optimizing ship berthing. Naval Res. Logist. 41 : 1-15. Christiansen, M., K. Fagerholt., D. Ronen. 2004. Ship routing and scheduling: Status and perspectives. Transportation Sci. 38 : 1-18. Cordeau, J. F., Laporte, G., Legato, P., and Moccia, L. 2005. Models and tabu search heuristics for the berth-allocation problem. Transportation Sci. 39: 526-538. Cordeau, J. F., Laporte, G., A. Mercier. 2001. A unified tabu search heuristic for vehicle routing problems wit time windows. J. Oper. Res. Soc. 52 : 928-936. Hansen, P., Mladenovic, N. 2008. Variable neighborhood search for minimum cost berth allocation. Eur. J. Oper. Res. 191: 636-649 Imai, A., Chen, H. C., Nishimura, E., and Papadimitriou, S. 2007. The simultaneous berth and quay crane allocatioan problem, Transportation Res. E. 44: 900-920. Imai, A., Chen, H. C., Nishimura, E., Hattori, M., and Papadimitriou, S. 2007. Berth allocation at indented berth for mega-containerships, Eur. J. Oper. Res. 179: 579-593. Imai, A., Chen, H. C., Nishimura, E., and Papadimitriou, S. 2008. Berthing ships at a multi container terminal with a limited quay capacity, Transportation Res. E 44: 136-151. Imai, A., Nagaiwa, K., and Chan, WT. 1997. Efficient planning of berth allocation for container terminals in Asia. J. Advanced Transportation 31 : 75-94. Imai, A., Nishimura, E., Papadimitriou, S. 2001. The dynamic berth allocation problem for a container port. Transportation Res. B 35 : 401-417. Imai, A., Nishimura, E., and Papadimitriou, S. 2003. Berth allocation with service priority. Transportation Res. B 37: 437-457. Imai, A., Nishimura, E., and Papadimitriou, S. 2005. Berth allocation in acontainer port : Using a continuous location space approach. Transportation Res. B. 39 : 199-221. Imai, A., Nishimura, E., Hattori, M., and Papadimitriou, S. 2007. Berth allocation at indented berths for mega-containerships. Eur. J. Oper. Res. 179: 579-593. Glover, F. 1986. Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13 : 533-549. Kim, K. H., and Moon, K. C. 2003. Berth scheduling by simulated annealing. Transportation Res. B. 37: 541-560. 37 Rustam Efendi Pasaribu : Pengembangan Metode Pencarian Layak Untuk Persoalan Alokasi Dermaga, 2009. USU Repository © 2009

38 Lai, K. K., Shih, K. 1992. A study of container berth allocation. J. Advanced Transformation 26: 45-60. Legato, P., Mazza, R.M., 2001. Berth planning and resources optimisation at a container terminal via discrete event simulation. Eur. J. Oper. Res. 133 : 537-547. Lim, A. 1998. The berth planning problem. Oper. Res. Lett. 22: 105-110. Nishimura, E., Imai, A., Papadimitriou, S. 2001. Berth Allocation planning in the public berth system by genetic algorithms. Eur. J. Oper. Res., 131: 282-292. Park, K.T., Kim, K.H. 2002. Berth scheduling for container terminals by using sub-gradient optimization technique. J. Oper. Res. Soc. 53: 1054-1062. Park, Y. M., and Kim, KH. 2003. A scheduling method for berth and quay cranes. OR Spectrum 25: 1-23. Vis, I. F. A.,Koster R. D. 2003. Transshipment of containers at a container terminal: An overview. Eur. J. Oper. Res. 147 : 1-16.


PENGEMBANGAN METODE PENCARIAN LAYAK UNTUK PERSOALAN ALOKASI DERMAGA

Recommend Documents