## Upaya Peningkatan Kinerja Operasional Kapal KM. Kerinci dan KM. Tidar
Improving Operational Performance of MV. Kerinci and MV. Tidar

## Imbang Danandjojo
Puslitbang  Perhubungan  Laut  –  Balitbang  Perhubungan Jln. Medan  Merdeka Timur  No. 5  Jakarta Pusat e-mail: dj_imbang@yahoo.co.id
Naskah diterima 02 januari 2014, direvisi 10 Pebruari 2014, disetujui 24 Pebruari 2014

## ABSTRAK
Penelitian ini bertujuan  mengembangkan varian model VRP  untuk menyusun rute angkutan  laut penumpang dengan keuntungan operasional  optimal  dan  setiap jalur  jaringan pelayanan  dilewati tepat  satu kali  untuk  memberi  frekuensi layanan  yang sama.  Pengembangan ini  dapat diselesaikan  jika jaringannya  berupa Graph  Euler dan  alokasi durasi  satu round trip yang memadai. Hasil modifikasi restrukturisasi rute KM. Kerinci adalah Tanjung Priok – Balikpapan – Tarakan – Nunukan – Pantoloan – Pare-pare – Makassar – Bau-bau – Makassar – Pare-pare – Pantoloan – Nunukan – Tarakan – Balikpapan  – Tanjung  Perak  – Tanjung Priok,  sedangkan rute  KM. Tidar  adalah Tanjung  Priok – Tanjung  Perak  – Makassar –Tanjung  Perak –  Pare-pare – Tanjung  Perak – Pantoloan  – Tanjung  Perak – Bau-bau  – Tanjung  Priok. Jika KM. Tidar dioperasikan pada rute hasil modifikasi, biayanya meningkat 32,71% dari biaya aktual KM. Kerinci, sedangkan KM. Kerinci yang dioperasikan pada rute KM. Tidar meningkat 5,22% dari biaya aktual KM. Tidar. Utilitas jaringan KM. Kerinci meningkat 49,97% dari rute aktualnya, sedangkan utilisasi jaringan KM. Tidar turun 4,54% dari rute aktualnya. LF KM. Tidar meningkat 345,41% dari LF KM. Kerinci aktual, sedangkan LF KM. Kerinci turun 82,05% dari LF KM. Tidar aktual.  Model ini  belum mempertimbangkan  pola  rute  penumpang dinamis,  jumlah pangkalan  tidak tunggal,  dengan kecepatan dan waktu tempuh kapal, penumpang, dan jumlah pelabuhan dalam jaringan yang bersifat stokastik, sehingga membuka peluang  penelitian lanjut.
Kata Kunci: VRP, Angkutan Laut Penumpang, Euler

## ABSTRACT
This study aims to develop a model variant of the VRP to arrange passengers sea transportation with the optimal operational advantages and each service network paths crossed exactly once to provide the same service frequency. This  development  can  be resolved  if the  network is  a Euler  Graph’s  and  allocation  duration of  one  round  trip adequate. Modified restructuring KM. Kerinci is Tanjung Priok – Balikpapan – Tarakan – Nunukan – Pantoloan – Pare-pare –  Makassar –  Bau-bau –  Makassar  –  Pare-pare  –  Pantoloan  –  Nunukan  – Tarakan  – Balikpapan  – Tanjung Perak – Tanjung Priok, while the KM. Tidar is Tanjung Priok – Tanjung Perak – Makassar – Tanjung Perak – Pare-pare – Tanjung Perak – Pantoloan – Tanjung Perak – Bau-bau - Tanjung Priok. If KM. Tidar  operated on a modified route, the cost is increased by 32.71% of the actual cost of KM. Kerinci,  while KM . Kerinci operated on route KM. Tidar risen 5.22% of the actual cost of KM. Tidar. Network utility KM. Kerinci increased by 49.97% of the actual route,  while the  network utilization  KM.  Tidar down  4.54% from  the actual  route. LF  KM. Tidar  increased 345.41% from LF KM. Kerinci actual, while LF KM. Kerinci down 82.05% from LF KM. Tidar actual. These models have not considered the dynamic pattern of passenger service, the number of bases is not a single, with the speed and travel time of ships, the number of passengers, and the number of ports in the network that are stochastic, thus opening up opportunities for  additional research.
Key words: VRP, Passengers Sea Transport, Euler

## J.Pen.Transla Vol.16 No.1 Maret 2014 :  1-38
hampir  dapat  dikatakan  tidak  ada  penumpangnya. Secara  rata-rata,  LF  per  voyage  yang  dicapai  oleh kapal KM.  Kerinci hanya  31,60%.Pada  tahun  yang sama, diperoleh gambaran pengoperasian kapal KM. Tidar bahwa jumlah  penumpang di  atas kapal  pada Pelabuhan Pare-pare, Balikpapan ke arah Pantoloan, dan  Pelabuhan  Balikpapan  kearah Tanjung  Priok, sangat  padat  (dengan  LF  melebihi  100%),  bahkan pada Pelabuhan Pare-pare sudah mencapai 143,67% atau jauh melebihi batas kapasitas angkut kapal.
Sedangkan  pada  Pelabuhan Tanjung  Priok  dan Tanjung  Perak  ke  arah  Tanjung  Priok,  dapat dikatakan tidak ada penumpangnya. LF rendah terjadi pada  Pelabuhan Tarakan  dan  Pelabuhan  Pantoloan, yaitu  hanya  26,75%  dan  23,51%.  Secara  rata-rata, LF  per voyage  yang  dicapai  oleh kapal  KM. Tidar jauh lebih baik daripada capaian KM. Kerinci, yaitu sebesar  62,91%.Berdasarkan  capaian  LF  pada pelabuhan-pelabuhan singgah KM. Kerinci dan KM. Tidar yang rute trayeknya relatif berhimpit, memberi gambaran  bahwa  terjadi  penyusunan  rute  yang kurang tepat, sehingga berakibat terjadi LF melebihi batas  kapasitas  kapal  yang  dioperasikan  (di  atas 100%) pada pelabuhan-pelabuhan tertentu dan di sisi lain  terjadi  sebaliknya  hingga  LF  mencapai  angka 0%.Dari gambaran di atas, dapat disimpulkan bahwa persoalan  penyusunan  ulang  rute  pelayanan Angkutan  Laut  Penumpang  Dalam  Negeri  PT. (Persero) PELNI, khususnya KM. Kerinci dan KM. Tidar, menjadi sangat diperlukan.

## METODE
Konsep  dasar  VRP  merupakan  upaya menyusun  sejumlah  rute  yang  meminimalkan  total cost  perjalanan  (dapat  berupa  biaya,  jarak,  waktu tempuh, atau sejenisnya), untuk melayani pengiriman permintaan  pelanggan,  dengan  batasan-batasan permintaan  setiap  pelanggan  harus  terpenuhi,  rute pelayanan harus berawal dan berakhir pada titik yang sama (dalam hal ini dinyatakan sebagai depot), serta adanya  keterbatasan  kapasitas  alat  angkut.  Dengan demikian, VRP sangat bergantung pada karakteristik rute yang dilayani, karakteristik depot, karakteristik pelanggan, karakteristik permintaan, dan karakteristik pelayanannya.  VRP  merupakan  bentuk  umum  dari TSP  dan  membutuhkan  runtime  yang  sangat  lama. Oleh karena itu, masalah ini  digolongkan ke  dalam NP–Hard  atau Non-deterministic  Polynomial  Time Hard , yaitu suatu kumpulan persoalan yang mungkin belum  ditemukan  metoda  eksaknya  untuk memperoleh  nilai  optimal  dan  dapat  diselesaikan secara sempurna hanya dengan runtime polynomial. VRP sering didefinisikan pada pembatasan kapasitas dan panjang  rute.
Tujuan  penyelesaian VRP  adalah  mencari  rute kendaraan  optimal  untuk  memenuhi  seluruh permintaan  pelanggan.Dalam  penelitian  ini dikembangkan  suatu  penyusunan  rute  dan penempatan armada kapal angkutan laut penumpang yang  efisiensi  biayanya  optimal  dalam  melayani kebutuhan pergerakan penumpang  antar pulau pada pelabuhan  singgah  dalam  jaringan  pelayanan  yang telah  ditetapkannya.  Rute  yang  disusun  merupakan rute tertutup, yaitu setiap rute berawal dan perakhir pada  pelabuhan  pangkalan  yang  sama.  Mengingat kondisi  geografis  Indonesia  yang  sangat  luas  dan berbentuk kepulauan, maka rute-rute yang dibentuk memiliki  pelabuhan  pangkalan  lebih  dari  satu. Pelabuhan singgah yang dilayani tersebar di seluruh wilayah Indonesia dan tidak berubah secara  jumlah selama  proses  pelayanannya.  Sedangkan  asumsi- asumsi  yang  digunakan,  adalah  sebagai  berikut:  (i) Permintaan perjalanan penumpang pada suatu jalur, diasumsikan tetap; (ii) Analisis yang dilakukan hanya pada  kondisi  saat  tahun  2011,  sehingga  tidak dilakukan upaya proyeksi; (iii) Jumlah armada kapal yang  dioperasikan  dianggap  tetap,  sehingga optimalisasi  jumlah  dan  kapasitas  kapal,  tidak dipertimbangkan dalam penelitian ini; (iv) Masalah penyusunan  rute  angkutan  laut  penumpang,  adalah pemilihan rute untuk pasangan asal – tujuan dengan matriks  perjalanan  tetap;  (v)  Fungsi  biaya  link merupakan fungsi biaya operasi kapal di laut dan di pelabuhan;  (vi)  Fungsi  tujuan  diformulasikan berdasarkan  informasi  tentang  besaran  jumlah permintaan  perjalanan  penumpang,  tarif  yang diterapkan,  dan  biaya  operasi  kapal  yang melayaninya.
Terkait  dengan  penyusunan  rute,  ada  beberapa metoda  yang dapat  digunakan untuk  mencari  solusi optimal,  antara lain Iterative  Decomposition  Algo- rithm [25], Branch–and–Bound [15] ,  Branch– and–Backtrack  Heuristics  [23],  Branch–and– Bound  +  Stochastic  Increment  Assignment [2], Cumulative  genetic  Algorithm  [30],  Generalised Benders  Decompocition  Methods  with  Support Function [12] ,  Ant  Systems [21], Hybrids  of  Ant Systems,  Ant  Colony  with  Genetic  Algorithm, Simulated Annealing, dan Tabu Search [22] , Simu- lated  Annealing [16] ,  Branch–and–Bound  Heu- ristic  dan  Simulated  Annealing [8] ,  Tabu  Search
[6] ,  Genetic  Algorithm  dan  Simulated  Annealing [7] , Chaotic Optimization Algorithm [29] , Branch– and–Bound  with  Sensitivity  Analysis  Based [17] , Descent  Algorithm,  Simulated  Annealing,  Tabu Search,  dan  Genetic  Algorithm [9] ,  Hybrid  of Simulated  Annealing  and  Genetic  Algorithm  dan Evolutionary  Simulated  Annealing [18] ,  Genetic Algorithm [10] , [14] , dan [26] , Genetic  Algorithm

## PENDAHULUAN
Penelitian  ini  membahas  persoalan  penentuan rute angkutan laut penumpang dari dua sudut pandang, yaitu dari sisi akademis dan dari sisi praktis. Dari sisi akademis,  VRP  pada  umumnya  digunakan  dalam penyusunan  rute  untuk  distribuasi  barang  atau komoditas diterapkan untuk menyusun rute angkutan umum  penumpang. Tulisan-tulisan  atau  penelitian- penelitian  tentang  penerapannya  untuk  angkutan penumpang  masih  jarang,  apa  lagi  tentang penerapannya pada angkutan laut penumpang. Salah satu  penelitian  tentang  penerapan  VRP  untuk penumpang, pernah dilakukan [13].
Konsep  dasar  VRP  merupakan  upaya meminimalkan  total  cost  perjalanan  (dapat  berupa biaya, jarak, waktu tempuh, atau sejenisnya), dalam melayani  permintaan  pelanggan  dengan  batasan– batasan  permintaan  pelanggan harus  terpenuhi,  rute pelayanan  harus  berawal  dan  berakhir  pada  titik (dinyatakan  sebagai  depot)  yang  sama  [19],  serta adanya keterbatasan jumlah dan kapasitas alat angkut [5]. Dengan demikian, VRP sangat bergantung pada karakteristik rute yang dilayani, karakteristik depot, karakteristik pelanggan, karakteristik permintaan, dan karakteristik pelayanannya  [1],  [3], [20],  dan  [28]. Pada kehidupan  nyata, batasan-batasan  model VRP tidak sesederhana yang dirumuskan. Banyak hal-hal yang  di  luar  dugaan  bertentangan  dengan  sifat alamiah perilaku manusia dan kondisi alam.
Dari  sisi  praktis,  angkutan  laut  penumpang  di Indonesia  memiliki  karakteristik  yang  unik.  Di samping  penumpangnya  merupakan  penumpang yang tidak memiliki moda transportasi pilihan yang lain untuk melayani keperluan pergerakannya ( cap- tive ),  juga  armada  kapal  yang  dioperasikan  pada umumnya  merupakan  bersifat  mandatori  dari pemerintah dalam rangka menjaga kestabilan politik, ekonomi,  sosial,  maupun  budaya,  dalam  bingkai Wawasan  Nusantara.  Salah  satu  perusahaan pelayaran yang melaksanakan mandatori pemerintah tersebut  adalah  PT.  (Persero)  PELNI.Kapal-kapal PELNI  pada  tahun 2003  tercatat  telah  mengangkut penumpang antarpulau di seluruh tanah air sebanyak 5 juta orang lebih. Padahal, tahun 2002 masih sekitar 6 juta penumpang, tahun 2001 sekitar 7 juta, dan tahun 2000 bahkan  sekitar  8  juta. Pada  tahun  2008,  load factor rata-rata hanya mencapai 50%. Apalagi, untuk jalur  pelayaran  yang  sejajar  dengan  jalur penerbangan,  jumlah  penumpangnya  benar-benar turun  drastis.
Di  sisi  lain,  armada  yang  dioperasikan  terus bertambah. Pada tahun 2009, armada angkutan laut penumpang  PELNI  mencapai  30  kapal.  Padahal, ketika  mengangkut  8  juta  penumpang  lebih,
armadanya  hanya  24  unit  pada  tahun 1999.Berdasarkan  data  operasional  tahun  2011, diperoleh gambaran bahwa trayek kapal KM. Kerinci dan KM. Tidar berhimpit pada pelabuhan pangkalan, yaitu  Pelabuhan  Tanjung  Priok,  serta  beberapa pelabuhan  singgahnya,  seperti  Pelabuhan  Tanjung Perak,  Makassar,  Balikpapan,  Pare-pare,  dan Pelabuhan  Pantoloan.  Rute pada  trayek  kapal  KM. Kerinci berbelok ke Pelabuhan Bau-bau, sedangkan rute  pada  kapal  KM. Tidar  berbelok  ke  Pelabuhan Tarakan  dan  Nunukan.
Dari  sisi  tingkat  pemanfaatan  atau  utilitas jaringan trayek pelayanan Angkutan Laut Penumpang Dalam Negeri PT. (Persero)  PELNI oleh pengguna jasanya, rata-rata hanya mencapai  65,92%. Hal  ini, berarti bahwa 34,08% link pelayanan yang diberikan tidak membawa muatan penumpang. Utilitas jaringan pada  trayek  kapal  KM.  Kerinci  hanya  mencapai 38,10%, sedangkan pada kapal KM. Tidar mencapai 78,57%.  Di  sisi  lain,  biaya  operasi  kapal  untuk melayani setiap trayek, rata-rata mencapai lebih dari 4 Milyar Rupiah per voyage. Tercatat, KM. Kerinci mencapai Rp. 4.591.437,16 tiap voyage, sedangkan kapal KM. Tidar mencapai Rp. 6.548.184.256,12 tiap voyage.Dengan  melakukan  relokasi  kapal  terhadap trayek-trayek yang dilayani pada tahun 2011, biaya operasi  kapal  dapat  diturunkan  rata-rata  sampai 31,26%. Hal ini akan semakin menurun biaya operasi kapalnya,  jika  secara  bersamaan  dilakukan penyusunan  ulang  rute  atau  trayek  pelayanannya.
Ditinjau dari pengoperasian kapal pengganti yang dapat  menurunkan  biaya  operasi  suatu  kapal pelaksana mandatori melayani suatu trayek tertentu, kapal  KM.  Kerinci  menduduki  peringkat  ke-dua dengan  mampu  menurunkan  biaya  operasi  untuk melayani  trayeknya  hingga  50,32%  jika  kapal  lain dioperasikan  pada trayek  tersebut. Sedangkan  KM. Tidar dapat turun sampai dengan 41,22%, jika kapal lain dioperasikan pada trayek yang dilayaninya.Dari sisi besarnya Load Factor (LF) yang dihasilkan oleh kedua  kapal  tersebut,  menunjukkan  bahwa  KM. Kerinci  hanya  mencapai  31,60%  dan  KM.  Tidar mencapai  62,91%.  Hasil  pengoperasian  kapal  KM. Kerinci pada tahun 2011, diperoleh gambaran bahwa jumlah  penumpang  di  atas  kapal  pada  Pelabuhan Bau-bau,  Makassar,  dan  Pelabuhan  Balikpapan, sangat padat (dengan LF hampir mendekati 100%), bahkan pada Pelabuhan Balikpapan sudah mencapai 110,40% atau melebihi kapasitas angkut kapal.
Sedangkan  pada  Pelabuhan  Tanjung  Priok, Tanjung Perak, Balikpapan ke arah Pantoloan, Pare- pare  ke  arah  Pantoloan  atau  sebaliknya  (ke  arah Balikpapan),  Bau-bau  ke  arah Tanjung  Priok,  dan Pelabuhan Tanjung  Perak  ke  arah  Tanjung  Priok,

## J.Pen.Transla Vol.16 No.1 Maret 2014 :  1-38
menghubungkan  link pergerakan  penumpang  secara langsung  dapat  dikatakan  tidak  ada,  karena  sudah dibebankan  pada  setiap  jalur  yang  dilaluinya. Sedangkan  pola  rute  yang  disusun  model  adalah menyinggahi  setiap  jalur  tepat  satu  kali,  sehingga setiap  link  pergerakan  penumpang  dilayani  secara langsung. Akibatnya, biaya operasi kapal ditanggung link  yang  bersangkutan  dan  menjadi  sangat  besar. Di samping itu, karena satu kapal hanya disediakan untuk  melayani  pergerakan  penumpang  satu  link, maka  berakibat  pada  LF  yang  juga  menjadi  sangat rendah.Di  sisi  lain,  waktu  tempuh  pergerakan penumpang  dari  pelabuhan asal  ke  pelabuan  tujuan yang semula rata-rata sebesar 54,44 Jam pada trayek kapal  KM.  Kerinci,  dalam  model  ini  turun  sekitar 29,62% atau menjadi 38,332 Jam. Sedangkan waktu tempuh pergerakan  penumpang  dari  pelabuhan  asal ke  pelabuan  tujuan  yang  semula  rata-rata  sebesar 63,92 Jam pada trayek kapal KM. Tidar, dalam model ini  turun  sekitar  35,93%  atau  menjadi  40,96 Jam.Berdasarkan  link  dan  volume  pergerakan penumpang  yang  harus  dilayani  oleh  kapal  KM. Kerinci hasil perbaikan solusi, terlihat terdapat link layanan  bolak-balik,  seperti  Tanjung  Priok  – Balikpapan, Tanjung Priok – Tarakan, Tanjung Priok – Nunukan, Tanjung Priok – Pantoloan, Tanjung Priok –  Pare-pare,  Tanjung  Priok  –  Bau-bau,  Tanjung Perak  –  Tarakan,  Tanjung  Perak  –  Nunukan, Nunukan  –  Bau-bau,  Nunukan  –  Makassar. Sedangkan  link  layanan  yang  hanya  searah  adalah Tanjung Priok – Makassar, Tanjung Perak – Tanjung Priok, Tarakan – Bau-bau, Makassar – Tarakan, dan Bau-bau  – Tanjung  Perak.    Sehingga,  rute  trayek kapal  KM.  Kerinci  hasil  perbaikan  solusi  dapat
dimodifikasi menjadi Tanjung Priok – Balikpapan – Tarakan  –  Nunukan  –  Pantoloan  –  Pare-pare  – Makassar  –  Bau-bau  –  Makassar  –  Pare-pare  – Pantoloan – Nunukan – Tarakan – Balikpapan – Tanjung Perak – Tanjung Priok, seperti pada Gambar 1.
Namun demikian, dengan adanya modifikasi rute ini, akan membawa kemungkinan bahwa pergerakan penumpang  pada  link-link  yang  sebelumnya merupakan bagian dari pelayanan kapal KM. Tidar, menjadi  berpeluang  untuk  ikut  trayek  kapal  KM. Kerinci  ini.  Link-link  pergerakan  penumpang  yang merupakan bagian layanan kapal KM. Tidar dari hasil perbaikan solusi dan berpeluang bergeser untuk ikut trayek  KM.  Kerinci,  antara  lain  Balikpapan  – Tarakan, Tarakan – Nunukan, Nunukan – Pantoloan, Pantoloan  –  Pare-pare,  Pare-pare  –  Makassar, Makassar  –  Bau-bau,  Bau-bau  –  Makassar, Makassar  –  Pare-pare,  Pare-pare  –  Pantoloan, Pantoloan – Nunukan, Nunukan – Tarakan, Tarakan – Balikpapan, Balikpapan – Tanjung Perak, Makassar – Tanjung Priok, Balikpapan – Bau-bau, Bau-bau – Balikpapan,  Balikpapan  –  Pare-pare,  Pare-pare  – Balikpapan,  Balikpapan  –  Makassar,  Makassar  – Balikpapan,  Balikpapan  –  Pantoloan,  Pantoloan  – Balikpapan,  Balikpapan  –  Nunukan,  Nunukan  – Balikpapan, Tanjung  Perak  –  Balikpapan, Tarakan –  Pantoloan,  Pantoloan  –  Tarakan,  Tarakan  – Makassar,  Tarakan  –  Pare-pare,  Pare-pare  – Tarakan, Bau-bau – Tarakan, Nunukan – Pare-pare, Pare-pare  –  Nunukan,  Pantoloan  –  Makassar, Makassar  –  Pantoloan,  Pantoloan  –  Bau-bau,  Bau- bau  –  Pantoloan,  Pare-pare  –  Bau-bau,  dan  Bau- bau  –  Pare-pare.  Sehingga,  rute  kapal  KM. Tidar hasil berbaikan solusi hanya melayani link-link Tanjung
Sumber: Hasil Analisis
Gambar 1. Rute KM. Kerinci Hasil Perbaikan Solusi Awal Layak
Nunukan Tarakan
Balikpapan
Pantoloan
Pare-pare
Bau-bau Makassar
Tanjung Priok Tanjung Perak
dan Genetic Local search [11], Genetika + VEGA [11],  Kombinasi  Penuh  [4]  dan  [27],  dan Genetic Algorithm dan Tabu  Search [31].
Pada  dasarnya,  semua  metoda  tersebut  mampu memberi hasil optimal sesuai yang diharapkan, namun yang paling sering mendapat perhatian adalah metoda heuristik, GA, karena metoda ini selalu berkembang. Hal ini mengindikasikan bahwa GA mampu memberi hasil optimal yang lebih baik dan selalu dikembangkan untuk meningkatkan kemampuan analisisnya dengan melakukan penggabungan  dengan metoda  lain  yang membentuk metoda heuristik.Dalam proses analisis, penelitian  ini  menggunakan  pendekatan  tiga  tahap, yaitu  tahap  persiapan  data,  tahap  inisialisasi,  dan tahap  perbaikan  solusi.  Pada  tahap  persiapan  data, karena  rute  yang  disusun  harus  menyinggahi  setiap jalur tepat  satu kali,  maka jaringan  pelayanan  yang dimodelkan harus merupakan Graph Euler.
Pada  tahap  inisialisasi  atau  tahap  pencarian solusi awal layak, digunakan metoda Nearest Addi- tion yang  juga  dinamakan  metoda Nearest  Neigh- borhood  Heuristic .  Metoda  ini  dimulai  dengan menentukan  banyaknya  kendaraan  yang  tersedia  di depot. Setiap  iterasinya  menambahkan  simpul  yang terdekat dengan titik akhir rute. Demikian seterusnya, hingga  kapasitas  kendaraan  terpenuhi.  jika  tidak terdapat posisi yang layak untuk menempatkan simpul baru karena alasan kendala kapasitas atau time win- dows (Bräysy & Gendreau, 2005, dalam [24]), maka kendaraan  tersebut  harus  kembali  ke  depot.
Selanjutnya, kendaraan berikutnya dioperasikan dengan aturan yang sama seperti kendaraan pertama, sampai  seluruh  jalur  dilewati  oleh  kendaraan  yang tersedia  di  depot.Pada  tahap  perbaikan  solusi menggunakan  pendekatan  metoda Genetic  Algo- rithm (GA),  dengan  tahapan  sebagai  berikut:  (i) Mendefinisikan Individu, yaitu kandidat solusi opti- mal global yang dihasilkan pada tahap inisialisasi. Satu individu adalah satu solusi awal layak, dapat dikatakan sama  dengan  satu  kromosom  yang  merupakan kumpulan gen; (ii) Mendefinisikan nilai fitness , yaitu ukuran  baik  atau  tidaknya  suatu  individu  yang dihasilkan. Nilai fitness merepresentasikan baik atau tidaknya  suatu  individu  atau  solusi  dan  digunakan sebagai  pedoman  dalam mencapai  nilai  solusi  opti- mal  global  dalam  GA.  Dalam  penelitian  ini,  yang diinginkan  adalah  kromosom  dengan  fitness  yang lebih kecil akan mempunyai peluang lebih besar untuk terpilih  kembali.  Oleh  karena  itu,  maka  digunakan pendekatan inverse, yaitu: .
Menentukan  proses  seleksi  yang  akan  digunakan. Seleksi  digunakan  untuk  memilih  individu-individu mana  yang  akan  dipilih  untuk  proses  kawin  silang ( crossover ) dan mutasi. Di samping itu, seleksi untuk memperoleh  calon  induk  yang  baik,  dengan  asumsi bahwa induk yang baik akan menghasilkan keturunan yang baik pula. Proses awal seleksi adalah mencari nilai fitness .
Seluruh  individu  ditempatkan  dalam  wadah seleksi  dan  menerima  probabilitas  reproduksi  yang besarannya  tergantung  pada  nilai  obyektif  fitness dirinya sendiri terhadap nilai obyektif seluruh individu dalam  wadah  tersebut.  Dalam  penelitian  ini, digunakan teknik  seleksi Roulette Wheel  Selection ; (iv) Menentukan proses persilangan ( crossover ) dan mutasi gen yang akan diterapkan. Persilangan adalah operator  GA  yang  melibatkan  dua  induk  untuk membentuk kromosom baru. Operasi ini tidak selalu diterapkan kepada seluruh individu yang ada, tetapi dipilih  secara  acak.  Prinsip  persilangan  adalah melakukan operasi pertukaran secara aritmatika pada gen-gen  yang  bersesuaian  dari  dua  induk,  untuk menghasilkan  individu  baru.  Proses  persilangan diterapkan pada setiap individu dengan probabilitas persilangan tertentu. Dalam penelitian ini, kromosom yang  akan  dijadikan  induk  dipilih  secara  acak  dan jumlah  kromosom  yang  akan  dikawin-silangkan ditentukan berdasarkan probabilitas persilangan atau crossover probability ( pc ) sebesar 75%. Sedangkan dalam  proses  mutasi,  jumlah  kromosom  yang  akan mengalami  mutasi  dalam  suatu  populasi  ditentukan berdasarkan tingkat mutasi atau mutation rate (?m) sebesar  2%.  Proses  mutasi  dilakukan  dengan  cara menukar  gen  yang  dipilih  secara  acak  dengan  gen sesudahnya.  Jika  gen  tersebut  berada  di  akhir kromosom, maka ditukar dengan gen yang berada di awal kromosom. Pertama dihitung dulu total panjang gen  yang  ada  pada  satu  populasi,  dengan  formula Total Panjang Gen = Jml Gen dalam 1 Kromosom ? Jml  Kromosom.  Untuk  memilih  posisi  gen  yang mengalami mutasi dilakukan dengan membangkitkan bilangan  acak  antara  satu  sampai  dengan  Total panjang  gen;  dan  (v)  Menentukan  kriteria penghentian  iterasi,  adalah  kriteria  yang  digunakan untuk  menghentikan  proses  iterasi  dan  solusi  opti- mal dianggap sudah dicapai. Dalam penelitian ini, jika setelah  dalam  beberapa  generasi  berturut-turut diperoleh nilai fitness terendah yang tidak berubah.

## HASIL  DAN  PEMBAHASAN
Pada pola rute aktual, pelabuhan singgah disusun sedemikian  rupa  sehingga  tidak  semua  link pergerakan  penumpang  dilayani  langsung  oleh  satu kapal, namun pergerakannya mengikuti pola rute yang ada.  Sehingga  biaya  operasi  kapal  yang
] [ 1 ] [ i fitness i Q 
Sedangkan  untuk  mencari  probabilitas, digunakan  formula  P[i]  =  Total  (Q[i]);  (iii)

## J.Pen.Transla Vol.16 No.1 Maret 2014 :  1-38

## Tabel 1.
Perbandingan Kinerja Operasional  Aktual KM. Kerinci dan  KM. Tidar, dengan Modifikasi Rute Kapal KM. Kerinci Hasil Perbaikan Solusi
No. Uraian Kinerja Sat Nama Kapal KM. Kerinci KM. Tidar Kondisi Aktual 1.  Biaya Operasi / Voyage Rp. 4.591.719.437,16 6.548.184.256,12 2.  Utilitas Jaringan % 38,10 78,57 3. Load Factor ( LF ) Rata-rata % 31,60 62,91 4. Waktu Tempuh rata-rata dari pelabuhan asal ke pelabuhan tujuan, sesuai trayek Jam 54,44 63,92 Modifikasi Rute KM. Kerinci Hasil Restrukturisasi Rute 1.  Biaya Operasi / Voyage Rp. 7.741.674.100,00 5.872.122.600,00 2.  Utilitas Jaringan % 57,14 75,00 3. Load Factor ( LF ) Rata-rata % 174,09 9,12 4. Waktu Tempuh rata-rata dari pelabuhan asal ke pelabuhan tujuan, sesuai trayek Jam 5,63 44,39

## Sumber: Hasil Analisis

## KESIMPULAN
Varian  model  VRP  dapat  dikembangkan  tidak hanya untuk mencari rute pelayanan pendistribusian suatu  komoditas  kepada  para  pelanggan  yang tersebar  secara  geografis  dan  menghasilkan  total biaya terkecil, tetapi juga dapat dikembangkan untuk menyusun  dan  menentukan  rute  angkutan  umum yang melayani permintaan pergerakan pelanggannya dengan  menghasilkan  total  pendapatan  operasional optimal.  Namun,  perlu  elaborasi  lanjutan  untuk memperoleh  susunan  rute  yang  optimal  dengan menerapkan pola penumpang ikutan, yaitu beberapa jalur tidak dilayani secara langsung tetapi mengikuti rute  perjalanan  yang  menyinggahi  beberapa pelabuhan antara. Pengembangan varian model VRP dalam penelitian ini ditujukan untuk menyusun  rute angkutan  umum  yang  melayani  permintaan pergerakan  penumpang  pada  setiap  jalur  dalam jaringan  pelayanannya.  Rute  yang  disusun  berawal dan  berakhir  pada  suatu  terminal  atau  pangkalan tertentu  dan  menghasilkan  pendapatan  operasional optimal.  Dengan  alasan  pemberian  frekuensi pelayanan yang sama, maka setiap jalur akan dilewati tepat  satu  kali  dan  rute  yang  dihasilkan  akan membentuk  Graph  Euler.
Rute  terbaik  diperoleh  dari  modifikasi restrukturisasi rute KM. Kerinci, yaitu Tanjung Priok –  Balikpapan  – Tarakan  –  Nunukan  –  Pantoloan  – Pare-pare  –  Makassar  –  Bau-bau  –  Makassar  – Pare-pare  –  Pantoloan  –  Nunukan  –  Tarakan  – Balikpapan  –  Tanjung  Perak  –  Tanjung  Priok, sedangkan  rute  KM. Tidar  adalah Tanjung  Priok  – Tanjung Perak  – Makassar  –Tanjung Perak  – Pare- pare – Tanjung Perak – Pantoloan – Tanjung Perak – Bau-bau  – Tanjung  Priok.Dari  sisi  biaya  operasi, modifikasi  hasil  restrukturisasi  rute  KM.  Kerinci
hanya butuh 7.741.674.100,00, atau hampir 25% dari total  biaya  semula,  sedangkan  KM.  Tidar membutuhkan  biaya  pelayaran  satu  voyage  yang turun menjadi Rp. 5.872.122.600,00 atau hampir 20% dari biaya semula. Dari sisi utilisasi jaringan, kapal KM.  Kerinci  menunjukkan  nilai  sebesar  57,14%, sedangkan kapal KM. Tidar turun menjadi 75%.
Dari  sisi  LF,  kapal  KM.  Kerinci  menunjukkan nilai  rata-rata  sebesar  174,09%,  sedangkan  kapal KM.  Tidar  turun  menjadi  9,12%.  Dari  sisi  waktu tempuh  rata-rata  dari  suatu  pelabuhan  asal  ke pelabuhan singgah dalam rute pelayanan, kapal KM. Kerinci  menunjukkan  waktu  rata-rata  5,63  Jam, sedangkan  kapal  KM.  Tidar  membutuhkan  waktu rata-rata 44,39 Jam.Dari penelitian yang dilakukan, telah  dihasilkan  kontribusi  dalam  menambah khasanah baru untuk pemahaman varian model VRP yang dapat dikembangkan tidak hanya untuk mencari rute  pelayanan  pendistribusian  suatu  komoditas kepada  para  pelanggan  yang  tersebar  secara geografis dan menghasilkan total biaya terkecil, tetapi juga  dapat  dikembangkan  untuk  menyusun  dan menentukan  rute  angkutan  umum  yang  melayani permintaan  pergerakan  pelanggannya  dengan menghasilkan total pendapatan operasional optimal. Namun,  perlu elaborasi  lanjutan untuk  memperoleh susunan rute yang optimal dengan menerapkan pola penumpang ikutan, yaitu beberapa jalur tidak dilayani secara langsung tetapi mengikuti rute perjalanan yang menyinggahi  beberapa  pelabuhan  antara.

## UCAPAN TERIMA KASIH
Mengucapkan terima kasih kepada Kepala Pusat Penelitian dan Pengembangan Perhubungan Laut, Dewan Redaksi, dan Instansi yang membantu penelitian ini.
Priok – Tanjung Perak, Tanjung Perak  – Makassar, Makassar  – Tanjung  Perak, Tanjung  Perak  –  Pare- pare,  Pare-pare  – Tanjung  Perak, Tanjung  Perak  – Pantoloan, Pantoloan – Tanjung Perak, dan Tanjung Perak  –  Bau-bau.Peningkatan  kualitas  hasil  dari modifikasi  pada  rute  kapal  KM.  Kerinci  yang diperoleh  dari  perbaikan  solusi,  menunjukkan perbedaan  yang  sangat  signifikan.  Dari  sisi  biaya operasi,  yang  semula  kapal  KM.  Kerinci membutuhkan Rp. 28.178.165.100,00 untuk melayari satu voyage rute hasil  perbaikan solusi berdasarkan durasi satu voyage 1.500 Jam, dengan modifikasi ini hanya butuh 7.741.674.100,00, atau hampir 25% dari total  biaya  semula.  Kerugian  operasi  yang  semula mencapai  Rp.  27.520.380.300,00  setiap  voyage, dengan modifikasi rute KM. Kerinci hanya menderita kerugian operasional  sebesar Rp.  4.131.889.300,00 atau kurang dari  20% kerugian semula.  Pada kapal KM.  Tidar,  yang  semula  membutuhkan  biaya pelayaran satu voyage sebesar Rp. 24.581.171.500,00,  dengan  adanya  modifikasi  ini menurun sangat drastis menjadi Rp. 5.872.122.600,00 atau  hampir  20%  dari  biaya  semula  seperti  pada Gambar  2.
Terkait  dengan  utilisasi  jaringan,  dari  hasil perbaikan  solusi,  rute  kapal  KM.  Kerinci menunjukkan  angka  utilisasi  jaringan  sebesar 28,00%.  Sedangkan  hasil  modifikasi  rute  ini menunjukkan nilai sebesar  57,14%. Artinya, terjadi peningkatan utilisasi jaringan dua kali lipat dari kondisi semula. Di sisi lain, pada kapal KM. Tidar, utilisasi jaringan  yang  semula  mencapai  76,60%,  dengan
modifikasi ini turun menjadi 75%. Waktu tempuh rata- rata dari pelabuhan asal ke pelabuhan tujuan, sesuai trayek,  untuk  kapal  KM.  Kerinci  hanya membutuhkan waktu sekitar 5,63 Jam, dan untuk rute kapal  KM.  Tidar  rata-rata  membutuhkan  waktu selama 44,39 Jam.Dari hasil perhitungan besaran LF yang  terjadi,  menunjukkan  nilai  rata-rata  sebesar 174,09%  atau  melebihi  kapasitas  kapal  sampai hampir mencapai 75%. LF tinggi terjadi di Pelabuhan Balikpapan, Tarakan, Nunukan, Pantoloan, Makassar, dan  Pare-pare,  yaitu  mencapai  150%  –  283,46%, baik  yang  ke  arah  Pelabuhan  Bau-bau  maupun  ke arah  Pelabuhan  Tanjung  Priok.  Bahkan  pada Pelabuhan  Pantoloan  menduduki  prestasi  tertinggi, yaitu 283,46%. Dibandingkan dengan prestasi yang dicapai  pada  saat  rute  kapal  KM.  Kerinci  hasil perbaikan  solusi  yang  hanya  mencapai  2,31%,  LF rute hasil modifikasi perbaikan solusi sangat berbeda jauh.Perhitungan  LF  pada  pergerakan  penumpang yang diangkut oleh kapal KM. Tidar berdasarkan hasil modifikasi perbaikan solusi, menunjukkan nilai rata- rata hanya sebesar 9,12%. Prestasi tertinggi dicapai oleh  Pelabuhan  Tanjung  Perak  yang  akan  menuju ke  Pelabuhan  Pare-pare,  yaitu  mencapai  25,48%. Dibandingkan dengan prestasi yang dicapai pada saat rute  kapal  KM. Tidar  hasil  perbaikan  solusi  belum dimodifikasi yang hanya mencapai 11,53%, LF rute hasil  modifikasi  perbaikan  solusi  selisihnya  tidak terpaut jauh.Hasil perbandingan antara kondisi aktual dan  modifikasi  rute  kapal  KM.  Kerinci  yang dihasilkan oleh perbaikan solusi berdasarkan durasi satu voyage 1.500 Jam, disajikan pada tabel 1.

## Sumber: Hasil Analisis
Gambar 2. Hasil Modifikasi Rute KM. Kerinci Hasil Perbaikan Solusi
KM. Ker inci KM. Tidar Nunukan
Tarakan
Balikpapan
Pantoloan Pare-pare Bau-bau Makassar Tanjung Priok Tanjung Perak

## DAFTAR PUSTAKA
[1] Chang, Mei-Shiang, Hsueh, Che-Fu, & Chen, Shyang-Ruey. 2003.  Real-Time  Vehicle  Routing  Problem  with  Time Windows And Simultaneous Delivery/Pickup Demands. Journal of the Eastern Asia Society for Transportation Studies. Vol.5, October.
[2] Chen, M., & Alfa, AS. 1991. A Network Design Algorithm Using  A  Stochastic  Incremental  Traffic  Assignment Approach, Transportation Science, Vol. 25, No. 3, pp. 215–224.
[3] Choi, Eunjeong, & Tcha,  Dong-Wan. 2005. A column generation approach to the heterogeneous fleet vehicle routing problem, Elsevier Ltd. All rights reserved, Available online at www.sciencedirect.com.
[4] Crainic, TG., Florian, M., & Leal, JE., (1990), A Model for The Strategic Planning of National Freight Transportation in Brazil: Methodology and Application, Part 1, 13–39.
[5] Dell’Amico, Mauro, Monaci, Michele, Pagani, Corrado,
& Vego, Daniele. 2006.  Heuristic Approaches for The Fleet Size and Mix Vehicle Routing Problem with Time Windows,  Transportation  Science,  Vol.  41,  No.  4, November  2007,  pp.  516–526,  INROFMS,  http:// transci.journal.informs.org/content/41/4/516.full.pdf, diunduh tanggal 6 Juli 2010 pukul 06:35 PM.
[6] Drezner,  Z.,  &  Salhi,  S.  2000.  Selecting  A  Good Configuration of One-Way and Two-Way Routes Using Tabu Search, Control and Cybernetics, Vol. 29, No. 3, pp.725–740.
[7] Drezner, Z., & Salhi, S. 2002. Using Hybrid Metaheuristics for
The One-Way and Two-Way Network Design Problem, Naval Research Logistics (NRL), vol. 49, No. 5, pp. 449–463.
[8] Drezner,  Z.,  &  Wesolowsky,  GO.  1997.  Selecting  An Optimum Configuration of One-Way and Two-Way Routes, Ttransportation Science, Vol, 31, No. 4, pp. 386–394.
[9] Drezner, Z., & Wesolowsky, GO. 2003. Network Design: Selection  and  design  of  Links  and  Fasility  Location, Transportation research Part A, Vol. 37, No. 3, pp. 241–256.
[10] Feng, CM., Hsieh, CH., & Peng, SC. 2009.  Optimization of Urban Bus Routes Based on Principles of Sustainable Transportation.
[11] Frazila,  RB.  2005.  Optimising  The  Design  of  Freight Transport Network, Desertation, Hirosima University.
[12] Gao, Z., Wu, J., & Sun, H. 2005. Solution Algorithm for Bi– Level  Discrete  Network  Design Problem,  Transportation Research Part B, Vol. 39, No. 6, pp. 479–495.
[13] Jayakrishnan, R., (n.d), Mass Transport Vehicle Routing
Problem (MTVRP) and The Associated Network Design Problem (MTNDP), Department of Civil Engineering and Institute  of  Transportation  Studies,  University  of California, Irvine, CA. 92967, USA, http://www.uctc.net/ papers/748.pdf, diunduh tanggal 04 Maret 2014, pukul 07:37PM.
[14] Kim, BJ., & Kim, W., (2006), An Equilibrium Network Design  Model  with  A  Social  Cost  for  Multimodal Networks, School of Air Transport, Transportation, and Logistics, Hankuk Aviation University, South Korea.
[15] Leblanc, LJ. 1975. An Algoritma for The Discrite Network
Design Problem, Transportastion Science, Vol 9, No. 3, pp. 183–199;
[16] Lee, C., & Yang, K. 1994. Network Design of One-Way
Streets  with  Simulated Annealing,  Paper  in  Regional Science, Vol. 73, No. 2, pp. 119–13.
[17] Long, J., Gao, Z., Zhang, H., & Szeto, WY. 2010. A Turning Restriction  Design Problem  in  Urban Road  Networks, European Journal of Operational Research, Vol. 206, No.
3, pp. 469 – 57.
[18] Miandoabchi,  E.,  &  Farahani,  RZ.  2010.  Optimizing Reserve Capacity of Urban Road Network In A Discrete
Network  Design  Problem,  Advances  In  Engineering Software, Vol. 42, No. 12, pp. 1041–1050.
[19] Novoa, Clara. 2006.  A Set-Partitioning-Based Model for the Stochastic Vehicle Routing Problem, Department of Engineering and Technology, Texas State University, 601
University  Drive,  San  Marcos,  TX  78666,  http:// homepages.cae.wisc.edu/~linderot/papers/Novoa-Et-Al- 06-TR.pdf, diunduh tanggal 6 Juli 2010 pukul 07:25 PM.
[20] Özyurt,  Zeynep,  Aksen,  Deniz, Aras,  &  Necati,  (n.d),
Open  Vehicle  Routing  Problem  with  Time  Deadlines: Solution  Methods  and  an  Application,  http:// home.ku.edu.tr/~daksen/Ozyurt-Aksen-Aras-GOR2005- OVRPTD.pdf, diunduh tanggal 6 Juli 2010 pukul 07:05 PM.
[21] Poorzahedy, H., & Abulghasemi, F. 2005.  Application of
Ant System to Network Design Problem, Transportastion, Vol. 32, No. 3, pp 251–273.
[22] Poorzahedy,  H.,  &  Rouhani,  OM.  2007.  Hybrid Metaheuristic Algorithms  for  Solving  Network  Design Problem, European Journal of Operational Research, Vol.
182, No. 2, pp. 578–596.
[23] Poorzahedy, H., & Turnquist, MA. 1982.  Approximate Algorithms for The Discrete Network Design Problem, Transport Research–B, Vol. 16B, No. 1, pp. 45–55;
[24] Salaki, Deiby  Tineke. 2009.  Penyelesaian Vehicle  Routing Problem Menggunakan Beberapa Metoda Heuristik Konstruktif, Sekolah Pascasarjana Institut Pertanian Bogor. Bogor.
[25] Steenbrink, PA. 1974. Transport Network Optimization
In  The  Dutch  Integral  Transportation  Study,
Transportation Research, Vol. 8, No. 1, pp. 11–27.
[26] Taniguchi, E., Thompson, RG., Yamada, T. 2007. Incorporating Risks In City Logistics, City Logistics VI, Sixth International Conference On City Logistics, pp. 1–20.
[27] Tavassy, LA.1996. Modeling European Freight Transport Flows, PhD Thesis, TU. Delft.
[28] Woensel, T. Van, Kerbache, L., Peremans, H., & Vandaele,
N., (n.d), A Vehicle Routing Problem With Stochastic Travel
Times,  http://www.icsd.aegean.gr/aic  2003/papers/
vanwoensel-kerbache.pdf, diunduh tanggal 6 Juli 2010
pukul 08.22 PM.
[29] Wu, JJ., Sun, HJ., Gao, ZY., & Zhang, HZ. 2009. Reversible
Lane–Based  Traffic  Network  Optimization  with  An Advanced  Traveller  information  System.  Engineering Optimization, Vol. 41, pp. 87–97.
[30] Xiong, Y., & Schneider, JB.1992. Transportation Network Design Using A Cumulative Algorithm and neural Network, Transportation Research Record, Vol. 1364, pp. 37–44.
[31] Yamada, T., Frazila, RB., Castro, J., & Taniguchi, E. 2009.
Designing  Multimodal  Freight  Transport  Networks:  A Heuristic Approach and Applications, Ttransport Science.
Vol. 43, No. 2, pp. 129–143.