Prosiding Seminar Nasional Matematika dan Terapannya 2016 p-ISSN : 2550-0384; e-ISSN : 2550-0392
MINIMALISASI KETERLAMBATAN KERETA API (STUDI KASUS PADA JADWAL KERETA API DI PT KERETA API INDONESIA DAOP IV SEMARANG)
Tegar Arifin Prasetyo Universitas Negeri Semarang
[email protected]
Dwijanto Universitas Negeri Semarang
ABSTRACT. Train is one of vehicles which is commonly used in Indonesia, especially in Semarang. Some of its advantages are relatively cheap cost, relatively short travel time, relatively safe compared to other vehicles, and environmental friendly. However, train also has many weakness, for example arrival delay. Therefore, this paper will discusses about the solution of train delay problem using the Solver in Microsoft Excel and Integer Programming method. The mathematical model is constructed to minimize time of train delays without violating the existing railway capacity and regards other constrains. The constrains are the used of the railway, and the rules of the time difference for the two trains, so that both trains will not crash. Keywords: Solver, Microsoft Excel, Integer Programming
ABSTRAK. Kereta api merupakan salah satu sarana transportasi yang sering digunakan oleh masyarakat Indonesia, khususnya di wilayah Semarang. Beberapa kelebihan yang yang dimiliki oleh alat transportasi tersebut adalah biaya yang relatif murah, waktu tempuh yang relatif cepat, relatif aman dibandingkan angkutan darat lainnya serta ramah lingkungan. Namun, kereta api juga memiliki berbagai masalah misalnya keterlambatan saat tiba di stasiun. Oleh karena itu, makalah ini akan membahas penyelesaian masalah keterlambatan kereta api dengan bantuan Solver dalam Microsoft Excel dan metode Integer Programming. Model matematika dibuat untuk meminimumkan waktu keterlambatan kerata api dengan tidak melanggar kapasitas jalur yang ada dan memperhatikan beberapa batasan lainnya. Batasan yang digunakan adalah penggunaan rel kereta api, dan aturan selisih waktu untuk dua kereta api, agar kedua kereta api tersebut tidak bertabrakan. Kata Kunci: Solver, Microsoft Excel, Integer Programming
Minimalisasi Keterlambatan Kereta Api
82
1. PENDAHULUAN Kereta api merupakan salah satu sarana transportasi utama di berbagai negara termasuk Indonesia. Kereta api umumnya berupa kendaraan dengan tenaga gerak, baik berjalan sendiri (lokomotif) maupun dirangkaikan dengan kendaraan lain yang disebut gerbong kereta api. Serangkaian gerbong kereta api tersebut memiliki ukuran yang cukup luas, sehingga dapat menampung sejumlah penumpang, dan barang dengan kapasitas besar. Saat ini, kebutuhan akan transportasi kereta api sudah sangat diperlukan. Di Indonesia, khususnya di daerah Semarang, kereta api merupakan salah satu transportasi darat yang paling banyak diminati oleh masyarakat. Hal tersebut didukung dari segi biaya yang relatif murah, dan waktu tempuh perjalanan lebih cepat dibandingkan menggunakan transportasi darat lainnya. Selain itu, kelebihan lainnya adalah ramah lingkungan dan relatif aman. Seiring berjalannya waktu, tidak hanya kelebihan saja yang dimiliki kereta api namun sering timbul berbagai masalah. Misalnya kereta api yang terlambat sampai di stasiun. Masalah keterlambatan kereta api merupakan masalah yang serius, dikarenakan berdampak langsung pada kenyamanan penumpang dalam menggunakan transportasi kereta api. Oleh karena hal tersebut, dalam makalah ini akan dibahas penyelesaian masalah keterlambatan kereta api yaitu dengan cara meminimalisir keterlambatan kereta api dengan bantuan Solver dalam Microsoft Excel dengan pendekatan Integer Linear Programming (ILP). Dalam hal ini akan dibuat sebuah model matematika untuk meminimumkan waktu keterlambatan kerata api dengan tidak melanggar kapasitas jalur yang ada dan memperhatikan beberapa batasan yang lain, diantaranya adalah batasan waktu penggunaan rel kereta api dan aturan selisih waktu untuk dua kereta api agar kedua kereta api tersebut tidak bertabrakan. Berdasarkan latar belakang, dapat disimpulkan rumusan masalah yaitu bagaimana cara membuat kendala dan fungsi tujuan untuk meminimalisir keterlambatan kereta api dan bagaimana cara mengoperasikan Solver untuk meminimalisir
keterlambatan
Purwokerto, 3 Desember 2016
kereta
api
dengan
penyelesaian
Integer
83
T. A. Prasetyo dan Dwijanto
Programming. Adapun tujuan dalam pembuatan makalah ini adalah membahas cara membuat kendala dan fungsi tujuan untuk meminimalisir keterlambatan kereta api dan mengetahui cara mengoperasikan Solver untuk meminimalisir keterlambatan kereta api dengan penyelesaian Integer Programming.
2. PEMBAHASAN Perjalanan kereta api didefinisikan sebagai kereta api yang bergerak dari stasiun awal ke stasiun tujuan melewati sejumlah rel. Setiap perjalanan diberikan waktu kedatangan awal. Selain itu, setiap perjalanan mempunyai waktu tinggal minimal dan maksimal di setiap rel yang di gunakan. Untuk rel yang berada di stasiun, waktu tinggal merupakan waktu untuk menghentikan perjalanan kereta api di stasiun itu. Sedangkan, untuk rel yang tidak berada di stasiun, waktu tinggal adalah waktu tempuh kereta api di rel tersebut. Dalam makalah ini, penulis meninjau perjalanan dari stasiun Semarang (Poncol) ke stasiun Tegal melewati beberapa stasiun dan rel. Alur perjalanan kereta api dari stasiun Semarang (Poncol) ke stasiun Tegal diperlihatkan pada gambar: 1 2 3
5
4 Semarang (Poncol)
6 7 8
Weleri
9
10 11 12
15
13 14 Pekalongan
16 17 18 19 Pemalang
21 22 23
20
24 Tegal
Gambar 1. Rel yang akan dilalui oleh kereta api dari stasiun Poncol ke stasiun Tegal
Kereta api yang digunakan dari stasiun Semarang (Poncol) ke stasiun Tegal adalah kereta Kaligung Mas. Dalam makalah ini, di tinjau empat kereta Kaligung Mas yang menuju stasiun Tegal dari stasiun Semarang (Poncol). Kereta tersebut adalah KA 431, KA 429, KA 433, dan KA 427. Jadwal kereta api Kaligung dari Semarang menuju Tegal sebagai berikut:
Purwokerto, 3 Desember 2016
Minimalisasi Keterlambatan Kereta Api
84
Tabel 1. Jadwal kereta api KA 431 dan KA 429 dari stasiun Poncol ke stasiun Tegal KA 431 Stasiun Poncol Weleri Pekalongan Pemalang Tegal
Datang 06.56 07.46 08.17 08.45
Berangkat 06.20 07.02 07.50 08.21 -
KA 429 Stasiun Poncol Weleri Pekalongan Pemalang Tegal
Datang 09.45 10.33 11.05 11.34
Berangkat 09.10 09.49 10.38 11.09 -
Tabel 2. Jadwal kereta api KA 433 dan KA 427 dari stasiun Poncol ke stasiun Tegal KA 433 Stasiun Poncol Weleri Pekalongan Pemalang Tegal
Datang 13.26 14.13 14.14 15.12
Berangkat 12.50 13.29 14.17 14.48 -
KA 427 Stasiun Poncol Weleri Pekalongan Pemalang Tegal
Datang 17.07 17.56 18.28 18.55
Berangkat 16.30 17.17 18.01 18.31 -
Sebelum memodelkan permasalahan penjadwalan kereta api tersebut, terlebih dahulu dipaparkan beberapa definisi himpunan, parameter, dan variabel yang diperlukan sebagai berikut: a.
Himpunan K
: Himpunan Kereta Api
R
: Himpunan Rel
S
: Himpunan Stasiun : Himpunan dari semua rel yang dilewati oleh kereta api : Himpunan rel yang berada di stasiun : Himpunan rel yang berada di luar stasiun
b.
Parameter : Waktu minimal yang yang diperlukan oleh kereta api menyelesaikan
perjalanan
: Waktu tinggal minimal untuk kereta api : Waktu tinggal maksimal untuk kereta api
pada rel pada rel
: Rel pertama yang di gunakan oleh kereta api Purwokerto, 3 Desember 2016
pada rel
untuk
85
T. A. Prasetyo dan Dwijanto
: Rel terakhir yang di gunakan oleh kereta api c.
pada rel
Variabel : Total waktu keterlambatan untuk kereta api
(menit)
: Waktu ketika kereta api
memasuki rel (menit)
: Waktu ketika kereta api
meninggalkan rel (menit)
: Waktu keterlambatan kereta api
Fungsi
tujuan
permasalahan
ini
pada rel (menit)
adalah
meminimumkan
waktu
keterlambatan seluruh kereta api sehingga dapat di rumuskan dalam fungsi sebagai berikut: Minimumkan ∑ dengan kendala: 1.
Setiap kereta api
menempati rel paling sedikit selama
2.
Jika kereta api
menggunakan rel
lebih dari
kelebihan waktu
tersebut dianggap sebagai keterlambatan
3.
Setiap variabel bernilai non–negatif dan integer
Dari data–data yang sudah diperoleh, terdapat waktu tinggal minimal masing–masing kereta api pada setiap rel, dan waktu tinggal maksimal masing– masing kereta api pada setiap rel. Mengetahui waktu tinggal minimum masing-masing kereta api pada setiap rel: Rel Kereta 1 2 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0 4 0 0
4 0 0 0
0 0 4 0
0 0 0 4
36 35 36 37
0 4 0 0
6 0 3 0
0 0 0 10
44 44 44 39
0 0 4 0
4 0 0 0
0 5 0 0
0 0 0 5
0 0 0 0
27 27 27 27
4 0 0 0
0 0 0 4
0 4 0 0
0 0 4 0
24 25 24 24
0 0 0 4
4 0 0 0
0 4 0 0
0 0 4 0
Gambar 2. Tabel waktu tinggal minimum masing-masing kereta api pada setiap rel
Diperoleh nilai
dengan cara menjumlahkan setiap barisnya.
Mengetahui waktu masing-masing kereta api
memasuki rel : Purwokerto, 3 Desember 2016
153 152 150 154
Minimalisasi Keterlambatan Kereta Api
86
Dengan mengetahui tabel waktu tinggal minimum masing-masing kereta api pada setiap rel, kita dapat memperoleh nilai ketika kereta api
memasuki rel
. Tabelnya sebagai berikut: Rel Kereta waktu kereta 1 memasuki rel waktu kereta 2 memasuki rel waktu kereta 3 memasuki rel waktu kereta 4 memasuki rel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 4 0 0
4 0 0 0
0 0 4 0
0 0 0 4
40 39 40 41
0 43 0 0
46 0 43 0
0 0 0 51
90 87 87 90
0 0 91 0
94 0 0 0
0 92 0 0
0 0 0 95
0 0 0 0
121 125 0 0 0 149 0 153 0 0 119 0 0 123 0 148 0 0 152 0 118 0 0 0 122 146 0 0 0 150 122 0 126 0 0 150 154 0 0 0
Gambar 3. Tabel waktu masing-masing kereta api
16
17
18
19
20
21
22
23
24
memasuki rel
Nilainya didapat dari meninjau rel yang hanya dilalui oleh kereta api
dan
dihitung secara berurutan. Misalkan pada saat rel 1 dilewati oleh kereta api 2, maka nilai waktu kereta api 2 memasuki rel 1 sama dengan waktu nilai tinggal minimum kereta api 2 pada rel 1 yaitu bernilai 4. Kemudian ketika kereta api 2 melewati rel 5 maka waktu kereta api 2 memasuki rel 5 adalah waktu tinggal minimum kereta api 2 pada rel 5 ditambahkan dengan waktu kereta api 2 saat memasuki rel sebelumnya yaitu rel 1 kemudian didapat 35+4=39. Kemudian dengan cara yang sama didapat nilai waktu tinggal minimal dari kereta api ke memasuki rel . Mengetahui waktu tinggal maksimal masing-masing kereta api pada setiap rel: Rel Kereta 1 2 3 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0 6 0 0
6 0 0 0
0 0 6 0
0 0 0 6
39 38 39 40
0 6 0 0
8 0 5 0
0 0 0 12
47 47 47 42
0 0 6 0
6 0 0 0
0 7 0 0
0 0 0 7
0 0 0 0
30 30 30 30
6 0 0 0
0 0 0 6
0 6 0 0
0 0 6 0
27 28 27 27
0 0 0 6
6 0 0 0
0 6 0 0
0 0 6 0
Gambar 3. Tabel waktu tinggal maksimal masing-masing kereta api pada setiap rel
Nilai pada tabel diatas diperoleh dengan mengasumsikan untuk waktu pada saat kereta api berada di rel di dalam stasiun ditambahkan dengan 2 menit, dan untuk waktu pada saat kereta api berada di rel di luar stasiun ditambahkan dengan 3 menit. Kemudian dari tabel tersebut didapat nilai
dengan cara
menjumlahkan setiap barisnya. Mengetahui waktu kereta api
meninggalkan rel :
Dari tabel waktu tinggal maksimal kereta nilai waktu kereta api
pada rel , dapat ditentukan
meninggalkan rel . Tabelnya sebagai berikut:
Purwokerto, 3 Desember 2016
175 174 172 176
87
T. A. Prasetyo dan Dwijanto
Rel Kereta waktu kereta 1 meninggalkan rel waktu kereta 2 meninggalkan rel waktu kereta 3 meninggalkan rel waktu kereta 4 meninggalkan rel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0 6 0 0
6 0 0 0
0 0 6 0
0 0 0 6
45 44 45 46
0 50 0 0
53 0 50 0
0 100 0 106 0 0 0 97 0 0 104 0 0 97 103 0 0 0 58 100 0 0 0 107
0 0 0 0
136 142 0 0 0 169 0 175 0 0 134 0 0 140 0 168 0 0 174 0 133 0 0 0 139 166 0 0 0 172 137 0 143 0 0 170 176 0 0 0
Gambar 5. Tabel waktu masing-masing kereta api
16
17
18
19
20
21
22
23
24
meninggalkan rel
Dengan nilainya didapat dari meninjau rel yang hanya dilalui oleh kereta api dan dihitung secara berurutan. Caranya sama seperti saat kereta api
memasuki
rel . Mengetahui waktu
keterlambatan masing-masing kereta api
dan
keterlambatan total kereta api: Dengan menggunakan solver pada microsoft excel dengan kendala yang sudah dijelaskan diperoleh hasil sebagai berikut: Rel Kereta waktu keterlambatan kereta 1 waktu keterlambatan kereta 2 waktu keterlambatan kereta 3 waktu keterlambatan kereta 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
0 0 2 0
0 0 0 0
0 0 0 0
0 0 6 0
6 0 0 0
0 5 0 0
0 0 0 5
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 11
0 11 0 0
0 0 11 0
0 0 0 0
0 0 0 16
16 0 0 0
0 16 0 0
0 0 16 0
keterlambatan kereta 1 keterlambatan kereta 2 keterlambatan kereta 3 keterlambatan kereta 4
22 33 35 32
total keterlambatan 122 Gambar 6. Waktu keterlambatan masing-masing kereta api dan keterlambatan total kereta api
Jadi keterlambatan kereta api 1, 2, 3, dan 4 masing-masing adalah 22 menit, 33 menit, 35 menit, dan 32 menit. Dan total keterlambatan kereta api 1, 2, 3, dan 4 adalah 122 menit. Karena kita memanfaatkan solver pada microssoft excel, maka untuk meminimalisir keterlambatan kereta api, didapat dengan cara mengubah jeda waktu tinggal maksimum kereta api, namun waktu yang diterapkan harus sesuai dengan kebutuhan pelanggan kereta api. Misalnya kita ubah, pada saat kereta api di rel di stasiun waktu tinggal maksimum diubah menjadi 1 menit dari 2 menit, dan pada saat kereta api di rel di luar stasiun waktu tinggal maksimum diubah menjadi 1 menit dari 3 menit. Hasil solver sebagai berikut: Purwokerto, 3 Desember 2016
Minimalisasi Keterlambatan Kereta Api Rel Kereta waktu keterlambatan kereta 1 waktu keterlambatan kereta 2 waktu keterlambatan kereta 3 waktu keterlambatan kereta 4
88
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
0 2 0 0
0 0 2 0
0 0 0 0
0 0 0 3
4 0 0 0
0 4 0 0
0 0 4 0
keterlambatan kereta 1 keterlambatan kereta 2 keterlambatan kereta 3 keterlambatan kereta 4
4 6 6 4
total keterlambatan 20 Gambar 7. Waktu keterlambatan masing-masing kereta api dan keterlambatan total kereta api yang sudah diminimumkan
Jadi keterlambatan kereta api 1, 2, 3, dan 4 masing-masing adalah 4 menit, 6 menit, 6 menit, dan 4 menit. Dan total keterlambatan kereta api 1, 2, 3, dan 4 adalah 20 menit.
3. KESIMPULAN DAN SARAN 3.1 Kesimpulan Jadi penyelesaian untuk meminimalisir keterlambatan kereta api akan sangat efektif jika menggunakan Solver pada Microsoft Excel dengan metode Integer Programming. Dengan menggunakan Solver maka akan sangat memudahkan dalam perhitungan dengan banyak kendala.
3.2 Saran Disarankan untuk pembaca agar dapat memperbaiki makalah ini karena kami yakin masih banyak kekurangan. Disarankan juga mempelajari aplikasi selain Solver dikarenakan Solver hanya dapat menyelesaikan masalah maksimal 200 variabel dan 100 kendala.
UCAPAN TERIMAKASIH Pada bagian ini, penulis ingin mengucapkan terimakasih kepada Dr. Dwijanto, M.S. selaku dosen pembimbing yang sangat membantu dalam penyusunan artikel ini. Purwokerto, 3 Desember 2016
89
T. A. Prasetyo dan Dwijanto
DAFTAR PUSTAKA Friedrich, M., From Transit Systems to Models: Purpose of Modelling, 2016. Kecman, P. dan Goverde, R. M. P., Predictive modelling of running and dwell times in railway traffic, International Journal of Mathematics (Public Transp DOI 10.1007/S12469-015-0106-7), (2015), 1-9. Yuliawan, F, Implementasi Model Penjadwalan Job-Shop Dalam Masalah Penjadwalan Kereta Api Jalur Tunggal Dengan Pendekatan Constraint Programming, Institut Teknologi Bandung, Bandung, 2010, 1-2.
Purwokerto, 3 Desember 2016
