Jurnal Matematika, Sains, dan Pembelajarannya
Vol.10, No.1, Januari 2024, pp. 67~74
DOI:10.31605/saintifik.v10i1.482
ISSN 2622-8904 (online)

## Penjadwalan Kereta Api Daop 8 Surabaya Menggunakan Aljabar Max Plus
Eka Susilowati * , Ratna Widayati Universitas Nahdlatul Ulama Al Ghazali Cilacap e-mail: eka250@gmail.com

## Abstrak
Transportasi umum ini penting terlihat dari semakin bertambahnya kebutuhan akan jasa transportasi guna menunjang pergerakan manusia serta barang. Hal ini diakibatkan adanya peningkatan perkembangan penduduk dan perkembangan pemukiman di kota maupun di desa. Jaringan transportasi merupakan hal yang penting yang perlu diperhatikan. Salah satu moda transportasi yang dijadikan alat yang menunjang mobilitas masyarakat adalah kereta api. Sebagian besar orang memilih kereta api sebagai alat transportasi. Namun, jaringan kereta api terkadang banyak terkendala dengan penundaan yang terjadi sehingga terjadi delay atau ketepatan waktu keberangkatan dan kedatangan yang tentu saja merugikan para penggunanya. Alasan yang sering  terjadi  dikarenakan  jalur  kereta  api  yang  tidak  dapat  dilalui  dua  atau  lebih  kereta  api  sekaligus, sehingga  mengakibatkan  kereta  satu  harus  menunggu  kereta  yang  lain.  Dengan  demikian,  perlu  ada penjadwalan yang tepat terhadap jaringan kereta api sedemikian sehingga delay tersebut tidak terjadi lagi. Tujuan dari penelitian ini adalah menjadwalkan aljabar max plus untuk jaringan kereta api DAOP 8 Surabaya agar meminimalisir delay yang biasanya terjadi sehingga mengganggu mobilitas penggunanya. Berdasarkan penelitian ini, diperoleh periode jadwal keberangkatan setiap 101 menit sekali untuk setiap stasiun yang ada  di  jawa  timur.Dengan  adanya  periode  keberangkatan  kereta  api  ini,  maka  dapat  memudahkan  dalam menjadwal kereta api sehingga lebih tertata.
Kata kunci—Aljabar Max Plus; Kereta Api; Matriks Irreducible.

## 1. PENDAHULUAN
Transportasi  umum  sangatlah  penting  perannya  dalam  menunjang  mobilitas  masyarakat.  Ketika  mobilitas masyarakat teratasi dengan adanya transportasi umum, maka akan berdampak pada perekonomian masyarakat. Pada  transportasi  darat  berupa  kereta  api  merupakan  transportasi  masyarakat  yang  mempunyai  sejumlah kelebihan  sehingga  menjadi  pilihan  oleh  masyarakat.  Banyak  keunggulan  yang  dimiliki  oleh  transportasi umum  ini.  Adapun  keunggulannya  adalah  tidak  terkena  polusi,  bebas  macet,  dan  menghemat  waktu (Wijayanto,  2019).  Secara  real,  terdapat  banyak  masalah  yang  terjadi  pada  perkeretaapian  di  Indonesia. Penyebabnya  adalah  terjadinya  kecelakaan,  bencana alam,  adanya  perbaikan  jalur  rel  kereta  api  dan masih banyak  lagi.  Apabila  ditilik  Peraturan  Pemerintah  Nomor  72  Tahun  2009  mengenai  arus  Lalu  Lintas  dan transportasi Kereta Api, hal hal mengenai perkeretaapian merupakan satu kesatuan sistem yang dibagi menjadi prasarana,  sarana,  dan  sumber  daya  manusia,  serta  norma,  kriteria,  persyaratan,  dan  prosedur  untuk penggunaan transportasi kereta api. Di sejumlah negara maju seperti Jepang, Jerman, Perancis, Belanda, kereta api merupakan sarana transportasi  unggulan  yang  banyak  dipilih  oleh masyarakat  yang menjadi  penunjang kegiatan sehari hari oleh penduduknya dan aksesibilitas antara daerah-daerah di negaranya. Sistem transportasi yang terhubung antar moda satu dengan lainnya sudah ditata dengan baik dan saling terkait satu sama lain. Penempatan stasiun kereta yang menghubungkan pusat pusat diadakannya kegiatan menjadikan pergerakan bisa diwujudkan secara efektif. Lain daripada itu, infrastruktur sudah didukung dengan baik dan tertata, faktor lain  seperti  hukum,  regulasi,  kesadaran  individu,  kebijakan  sebagai  penentu  terealisasinya  suatu  program terselenggara  dengan  baik  (Biomantara  &  Herdiansyah,  2019).  Bila  ditilik  dari  usaha  dari  PT.Kereta  Api Indonesia  untuk  menanggulangi  angka  terlambatnya  salah  satunya  adalah  dengan  mengusahakan  supaya proses  berjalannya  kereta  api  sesuai  dengan  Gapeka  (Grafik  Perjalanan  Kereta  Api)  dan  memberikan
keutamaan  dalam  persilangan  dan  penyusulan  serta  koordinasi  beberapa  pihak  seperti  Pusdalopka  (Pusat Pengendali  Operasi  Kereta  Api),  Masinis,  PPKA  (Pengatur  Perjalanan  Kereta  Api)  serta  dukungan  sistem seperti Sipoka (Standar Induk Operasi Kereta Api) (Hidayat et al., 2018).
Namun dari berbagai upaya tersebut masih kurang maksimal hasilnya. Moda transportasi ini memiliki berbagai  permasalahan.  Salah  satunya  ketepatan  waktu  memang  merupakan  salah  satu  indikator  dari keberhasilan pengelolaan kereta api yang bagus (Gunoto, 2013). Jaringan kereta api haruslah selalu terkoneksi satu sama lain haruslah solid. Kereta api hanya akan menunggu pada kereta yang terkoneksi kereta terakhir tidak ada atau hanya memiliki delay yang kecil. Salah satu jaringan kereta api di Indonesia yang mengalami keterlambatan adalah kereta api DAOP I Surabaya. Banyaknya antrian kereta api yang masuk menuju Jakarta sehingga menimbulkan keterlambatan (Hidayat et al., 2018).
Salah  satu  penyelesaian  yang  dapat  dipergunakan  dalam  menanggulangi  permasalahan  ini  adalah meminimumkan  delay  kereta  api  dengan  memodelkan  jaringan  kereta  api  di  DAOP  I  Surabaya,  dan penjadwalan  ulang  dengan  menggunakan  model  linear  aljabar  Max  Plus.  Dalam  jaringan  kereta  api  ini, merupakan contoh kejadian diskrit adalah keberangkatan dari atau kedatangan di stasiun kereta api. Evolusi dari  kelas  Sistem  Kejadian  Diskrit  melibatkan  kendala  sinkronisasi,  dapat  diberikan  dengan  model  linear menggunakan  struktur  aljabar  max  plus.  Dalam  jaringan  transportasi,  kendala  yang  biasanya  terjadi  dari keharusan untuk kereta yang harus selalu terhubung. Dengan demikian perlu dirancang control untuk jaringan kereta tersebut.
Pada  penelitian  sebelumnya,  telah  dibahas  mengenai  mengoptimalkan  kecepatan  kereta  api menggunakan  model  prediktif  kontrol  guna  meminimalkan  keterlambatan  jadwal.  (Gunoto,  2013).  Pada penelitian lain, juga telah dibahas mengenai pemodelan jaringan kereta api komuter di DAOP VI Yogyakarta menggunakan aljabar maxplus serta menganalisa penjadwalan kereta api komuternya (Fakhilia et al., 2021). Pada penelitian ini akan dibahas hal lain juga mengenai rancangan control jaringan kereta api menggunakan model linear aljabar maks plus untuk meminimalisir delay yang biasa terjadi. Dalam penelitian ini juga akan dicoba di terapkan pada jaringan kereta api di DAOP I Surabaya. Pemilihan DAOP I Surabaya dikarenakan banyaknya antrian bagi kereta yang menuju ke Surabaya sehingga mengakibatkan keterlambatan. Data diambil dari penelitian (Afif, 2015). Pada penelitian sebelumnya yang dilakukan (Afif, 2015) (Susilowati, 2023), model penjadwalan jaringan kereta api adalah
𝒙(𝒌 + 𝟏) = 𝑨 ⊗ 𝒙(𝒌) ⊕ 𝒅(𝒌 + 𝟏) 𝒚(𝒌) = 𝑪 ⊗ 𝒙 (𝒌) 𝑿(𝟎) = 𝑿 𝟎
Pada penelitian ini, penjadwalan jaringan kereta api di Jawa Timur menggunakan model 𝑥(𝑘) = 𝐴 ⊗ 𝑥(𝑘 − 1) ,  dimana  A  adalah  matriks  bujur  sangkar  yang  irreducible  berisi  lama  perjalanan  kereta  dari  satu stasiun ke stasiun lain sedangkan 𝑥 (𝑘 − 1) adalah waktu keberangkatan yang ke k-1 dari semua kereta api. Penelitian selanjutnya  diharapkan  dapat  berlangsung dengan menerapkan model  linear aljabar  max plus ke jaringan yang lebih kompleks lagi yaitu seluruh jaringan kereta api di pulau jawa secara keseluruhan. Penelitian juga dimungkinkan untuk jaringan kereta api di berbagai pulau di Indonesia.

## 2. METODE PENELITIAN
Proses  tahapan  penelitian  yang  sudah  dilaksanakan  adalah  peneliti  sudah  mempelajari  mengenai aljabar max plus beserta sifat sifatnya yang nantinya digunakan pada penelitian ini. Tahapan selanjutnya yaitu mengumpulkan data dan penggalian informasi berupa peta rute jalur yang dilalui oleh kereta api, jumlah kereta api  yang  dijalankan,  jadwal  waktu  kereta  api  dating  dan  berangkat di tiap  stasiun  yang  berada  di  DAOP  8 Surabaya. Setelah itu peneliti menyusun jaringan kereta api tersebut dalam bentuk graf berarah. Proses untuk menyusun graf berarah berdasarkan rute kereta api DAOP 8 di Surabaya dimana node menggambarkan stasiun dan bobot arc menggambarkan waktu tempuh yang digunakan menempuh antara stasiun. Langkah berikutnya adalah memodelkan jaringan kereta api sederhana terlebih dahulu dengan menggunakan model linear aljabar max  plus.  Selanjutnya,  penyusunan  penjadwalan  dilakukan  dengan  menggunakan  proses  menghitung  nilai eigen dan vektor eigen dengan menggunakan program MATLAB.
Capaian  yang  ditargetkan dalam  penelitian ini  adalah  penjadwalan jaringan kereta  api.  Selanjutnya juga ditargetkan mendapat desain penjadwalan yang nantinya akan dibandingkan dengan kondisi nyatanya.
Berdasarkan teorema yang dijelaskan di atas
Skema 1. Bagan Alur Penelitian Selama Dua Periode

## 3. HASIL DAN PEMBAHASAN

## 3.1 Persamaan Linear Aljabar Max Plus
Sistem persamaan linear yang akan dibahas pada penelitian ini adalah 𝐴 ⊗ 𝑥 = 𝑏 Dimana 𝐴  ∈ ⊠ 𝑚𝑎𝑥 𝑚𝑥𝑛 , 𝑏 ∈ ⊠ 𝑚𝑎𝑥 𝑚 dan 𝑚, 𝑛  ∈⊠ . Penyelesaian dari sistem persamaan linear tersebut adalah himpunan semua vector 𝑥 ∈ ⊠ 𝑚𝑎𝑥 𝑛 sedemikian  sehingga  memenuhi 𝒙(𝒌) = 𝑨 ⊗ 𝒙(𝒌 − 𝟏) .  Lebih  lanjut  sistem  persamaan 𝒙(𝒌) = 𝑨 ⊗ 𝒙(𝒌 − 𝟏) dapat  dituliskan  lebih  rinci,  persamaan  dinyatakan  dalam  model  umum ⊠ 𝑚𝑎𝑥 yaitu 𝒙(𝒌) = 𝑨 ⊗ 𝒙(𝒌 − 𝟏) untuk 𝑘 = 1,2,3, … serta 𝑥(𝑘 − 1) = (𝑥 1 (𝑘 − 1), 𝑥 2 (𝑘 − 1), … ) dengan A matriks persegi dan vector 𝒙(𝒌 − 𝟏) adalah waktu keberangkatan yang ke k-1 dari semua kereta api.

## 3.2 Pembuatan graf berarah pada rute pilihan
Pada sub bab ini, akan dibahas graf berarah berbobot yang diperoleh dari rute pilihan kereta api yang beroperasi di DAOP 8 Surabaya.
Tabel 1. Jalur 1: Surabaya - Madiun PP Dari Tujuan Waktu Tempuh Rata-Rata  Banyak Kereta Api Madiun Nganjuk Kertosono Jombang Mojokerto Gubeng Mojokerto Jombang Kertosono Nganjuk Nganjuk Kertosono Jombang Mojokerto Gubeng Mojokerto Jombang Kertosono Nganjuk Madiun 48 22 19 29 52 53 31 18 21 45 1 2 3 3 4 2 3 3 1 2 Periode I (3 bulan) Dalam tiga bulan pertama, direncanakan  untuk  mengumpulkan semua data waktu setiap rute kereta api di DAOP 8 Surabaya

## Periode II (6 bulan)
Dalam enam bulan selanjutnya, direncanakan untuk membuat  program  Matlab  untuk  menyelesaikan persamaan linear

## Periode III (3 bulan)
Dalam  tiga  bulan  terakhir,  direncanakan  untuk  dengan menggunakan  program  MATLAB.  untuk  menyelesaikan persamaan linear dan menyelesaikan jadwal kereta api DAOP 8 Surabaya.
Tabel 2. Jalur 2: Malang – Madiun PP
Dari Tujuan Waktu Tempuh Rata-Rata Banyak Kereta Api Madiun Nganjuk Kertosono Kediri Tulung agung Blitar Malang Blitar Tulung agung Kediri Kertosono Nganjuk Nganjuk Kertosono Kediri Tulung agung Blitar Malang Blitar Tulung agung Kediri Kertosono Nganjuk Madiun 44 25 36 42 49 134 132 49 42 34 23
44 2 2 3 1 1 3 1 2 2 3 2 2 Tabel 3. Jalur 3: Surabaya – Cepu PP Dari Tujuan Waktu Tempuh Rata-Rata  Banyak Kereta Api Cepu Bojonegoro Babat Lamongan Pasarturi Lamongan Babat Bojonegoro Bojonegoro Babat Lamongan Pasarturi Lamongan Babat Bojonegoro Cepu 37 33 29 45 50 29 37 33
3 3 4 4 1 2 2 1 Tabel 4. Jalur 4: Surabaya – Banyuwangi PP Dari Tujuan Waktu Tempuh Rata-Rata  Banyak Kereta Api Banyuwangi Jember Probolinggo Bangil Gubeng Bangil Probolinggo Jember Jember Probolinggo Bangil Gubeng Bangil Probolinggo Jember Banyuwangi 175 112 68 50 56 69 115 165 1 1 1 1 1 1 1 1
Tabel 5. Jalur 5 Surabaya – Malang PP Dari Tujuan Waktu tempuh Rata-Rata Banyak Kereta Api Gubeng Bangil Malang Bangil Bangil Malang Bangil Gubeng 53 75 76 52 2 1 2 2
Gambar 1. Jalur Kereta Api
Tabel 6. Keterangan Gambar Jalur Kereta Api Warna arc GUB-MDU: Jalur 1 MLG – MDU: Jalur 2
PSRT- CPU: Jalur 3
GUB – BNW: Jalur 4 GUB – MLG: Jalur 5 GUB – PSRT: Integrasi Jalur
Node GUB: Gubeng PSRT: Pasar Turi MJR: Mojokerto JBG: Jombang KRTS: Kertosono NGJK: Nganjuk
MDU: Madiun KDR: Kediri TLG: Tulung Agung BLT: Blitar MLG: Malang LMNG: Lamongan BT: Babat
BJN: Bojonegoro CPU: Cepu BNG: Bangil PRB: Probolinggo JMB: Jember
BNW: Banyuwangi
Tabel 7. Defenisi Variabel setiap jalur kereta api Variabel Kereta api berangkat dari dan ke Variabel Kereta api berangkat dari dan ke MDU1 menuju NGJK1 ketika waktu ke k NGJK2 menuju MDU2 ketika waktu ke k NGJK1 menuju KRTS1 ketika waktu ke k CPU menuju BJN ketika waktu ke k KRTS1 menuju JBG ketika waktu ke k BJN menuju BT ketika waktu ke k JBG menuju MJR ketika waktu ke k BT menuju LMNG ketika waktu ke k MJR menuju SBY1 ketika waktu ke k LMNG menuju PSRT ketika waktu ke k SBY1 menuju MJR ketika waktu ke k PSRT menuju LMNG ketika waktu ke k MJR menuju JBG ketika waktu ke k LMG menuju PSRT ketika waktu ke k JBG menuju KRTS1 ketika waktu ke k BT menuju BJN ketika waktu ke k KRTS1 menuju NGJK1 ketika waktu ke k BJN menuju CPU ketika waktu ke k NGJK1 menuju MDU1 ketika waktu ke k BNW menuju JMB ketika waktu ke k MDU2 menuju NGJK2 ketika waktu ke k JMB menuju PRB ketika waktu ke k
Variabel Kereta api berangkat dari dan ke Variabel Kereta api berangkat dari dan ke NGJK2 menuju KRTS2 ketika saat ke k PRB menuju BNG1 ketika waktu ke k KRTS2 menuju KDR ketika waktu ke k BNG1 menuju GUB ketika waktu ke k KDR menuju TLG ketika waktu ke k GUB2 menuju BNG1 ketika waktu ke k TLG menuju BLT ketika waktu ke k BNG1 menuju PRB ketika waktu ke k BLT menuju MLG1 ketika waktu ke k PRB menuju JMB ketika waktu ke k MLG1 menuju BLT ketika waktu ke k JMB menuju BNW ketika waktu ke k BLT menuju TLG ketika waktu ke k GUB3 menuju BNG2 ketika waktu ke k TLG menuju KDR ketika waktu ke k BNG2 menuju MLG2 ketika waktu ke k KDR menuju KRTS2 ketika waktu ke k MLG2 menuju BNG2 ketika waktu ke k KRTS2 meunju NGJK2 ketika waktu ke k BNG2 menuju GUB3 ketika waktu ke k
Pada penelitian ini, vector 𝑥 (𝑘) berdimensi 1 x 42 dan matriks A berukuran 42 x 42.
Dimana matriks bersesuaian dengan jadwal berangkatnya kereta api yang ke k
Tabel 8. Matriks jadwal keberangkatan kereta api Matriks A yang berkaitan dengan 𝒙(𝒌) Baris Kolom Entri2 2 1 48 6 34 50 10 9 21 11 22 44 15 14 42 16 15 49 17 40 86 18 17 132 23 30 33 28 27 50 31 38 163 32 31 175 33 32 112 34 33 68 35 34 50 36 35 56 37 36 69 38 37 115 40 33 68 41 40 86 42 35 56

## 3.3 Menghitung Nilai Eigen dan Vektor Eigen
Matriks A yang didapatkan dari model matematika dari rute pilihan yang terhubung antara stasiun- stasiun  transfer.  Proses  analisa  ini  dilaksanakan  dengan  cara  menghitung  nilai  eigen  dan  vektor  eigen  dari matriks A. Selanjutnya, didasari nilai eigen dan vektor eigen yang diperoleh, didapat periode keberangkatan kereta api komuter di DAOP 8 Surabaya.
Berdasarkan  matriks  A  yang  telah  diinput  ke  program  Matlab,  matriks  A  yang  merupakan  lama keberangkatan kereta api yang ke k, ternyata merupakan matriks tidak irreducible. Matriks tidak irreducible dikarenakan  tidak  terdapat  kereta  api  di  setiap  busur.  Dengan  demikian  matriks  tersebut  terlihat  tidak terhubung kuat.    Dengan  demikian,  program yang  dibuat tidak  dapat ditemukan vektor  eigen namun  dapat ditemukan  nilai  eigen.  Sehingga  dapat  disimpulkan  syarat  cukup matriks  A  merupakan matriks  irreducible perlu untuk menjamin vektor eigen pada aljabar max plus.
Menurut  hasil  keluaran  merunning  program  Matlab  yang  telah  dibuat,  diperoleh  nilai  eigen  dari matriks A yang merupakan matriks dengan entri lama keberangkatan kereta api ke k, nilai eigen matriks A tersebut adalah 101. Hal ini menggambarkan periodic keberangkatan kereta api di setiap stasiun asal adalah setiap  101  menit  sekali  atau  bisa  diartikan  1  jam  41  menit.  Hasil  ini  tidak  jauh  berbeda  jika  dibandingkan dengan penelitian yang dilakukan (Alif, 2015), dimana nilai eigen yang diperoleh 93,625 ≤ 𝜆  ≤ 101,25 .

## 4. KESIMPULAN
Berdasarkan dari hasil penelitian yang telah dilakukan, maka dapat disimpulkan sebagai berikut:
1. Aljabar  max  plus  dapat  diterapkan  pada  penyusunan  model  sistem  jaringan  kereta  api  di  Jawa  Timur. Model yang digunakan 𝒙(𝒌) = 𝑨 ⊗ 𝒙(𝒌 − 𝟏) dimana A adalah matriks berukuran 42 x 42.
2. Dengan  menggunakan  model  sistem  jaringan  kereta  api 𝒙(𝒌) = 𝑨 ⊗ 𝒙(𝒌 − 𝟏) diperoleh  periode keberangkatan masing masing stasiun 101 menit sekali.
3. Ketika matriks A tidak irreducible maka dengan menggunakan program Matlab, belum dapat ditentukan vektor eigennya.

## DAFTAR PUSTAKA
Wijayanto, H. (2019). Peranan Penggunaan Transportasi Publik di Perkotaan (Studi Kasus Penggunaan Kereta Commuterline  Indonesia  Rute  Jakarta-Bekasi). Kybernan:  Jurnal  Studi  Kepemerintahan , 2 (2),  1–8. https://doi.org/10.35326/kybernan.v5i2.365
Biomantara,  K.,  &  Herdiansyah,  H.  (2019).  Peran  Kereta  Api  Indonesia  (KAI)  sebagai  Infrastruktur Transportasi Wilayah Perkotaan. Cakrawala: Jurnal Humaniora Bina Sarana Informatika , 19 (1), 1- 8 . https://doi.org/10.31294/jc.v19i1.4356
Hidayat, M., Anggoro, D., & Sarinah, S. (2018). Faktor Keterlambatan Kedatangan Kereta Api Penumpang dan Kinerja Daerah Operasi 1 Jakarta. Jurnal Manajemen Bisnis Transportasi Dan Logistik , 4 (2), 225- 232 . http://dx.doi.org/10.54324/j.mbtl.v4i2.846
Gunoto,  P.  (2013).  Optimasi  Kecepatan  Kereta  Api  Menggunakan  Metode  Kontrol  Model  Prediksi. Jurnal Integrasi , 5 (1), 33-37.
Fakhilia,  I.,  Rusdiana,  Y.,  &  Setiawan,  T.  H.  (2021).  Pemodelan  Jaringan  Dan  Analisa  Penjadwalan  KRL Commuter  Line  Jabodetabek  Dengan  Menggunakan  Metode  Aljabar  Max-Plus. Jurnal  Sains Indonesia , 2 (1), 1-8.
Afif,  A.  (2015). Aplikasi  Petri  Net  dan  aljabar  Max-Plus  Pada  Sistem  Jaringan  Kereta  Api  di  Jawa Timur (Doctoral dissertation, Tesis. Program Magister Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam. Surabaya: Institut Teknologi Sepuluh Nopember).
Susilowati, E., & Hartono, B. P. (2023). Penjadwalan Proyek Rumah Dengan Menggunakan Metode CPM Pendekatan Aljabar Max Plus. SAINTIFIK , 9 (1), 7 - 17. https://doi.org/10.31605/saintifik.v9i1.387
Susilowati, E. (2023). Penerapan Sistem Persamaan Linear Aljabar Max Plus Pada Masalah Ground Handling di Terminal 1 Bandara Internasional Juanda. SAINTIFIK , 9 (2), 180 - 188. https://doi.org/10.31605/saintifik.v9i2.439