10
IV STUDI KASUS Misalkan pada suatu daerah terdapat jaringan rel kereta. Jaringan rel kereta tersebut memiliki 23 stasiun dengan 23 edge antarstasiun. Gambar jaringan dapat dilihat pada Gambar 6. Angka di setiap simpul/verteks menyatakan stasiun, sedangkan angka pada setiap edge menyatakan banyaknya penumpang pada edge (rute kereta antarstasiun) tersebut. Setiap edge terdiri atas dua jalur yang memiliki arah yang berbeda. Arah 1 merupakan arah perjalanan kereta yang menjauhi stasiun awal, sedangkan arah 2 merupakan arah perjalanan kereta yang mendekati stasiun awal. Banyaknya penumpang yang tertera pada Gambar 6 merupakan banyaknya penumpang antarstasiun pada setiap arah. Jaringan
tersebut memiliki 5 rute kereta. Rute 1 meliputi stasiun 1, 6, 12, 13, 14, 15 dengan stasiun 1 sebagai stasiun awal. Rute 2 meliputi stasiun 2, 7, 8, 12, 13, 14, 15 dengan stasiun 2 sebagai stasiun awal. Rute 3 meliputi stasiun 3, 9, 13, 14, 15, 16, 17 dengan stasiun 3 sebagai stasiun awal. Rute 4 meliputi stasiun 4, 10, 15, 18, 19, 22, 23 dengan stasiun 4 sebagai stasiun awal. Rute 5 meliputi stasiun 5, 11, 17, 20, 21, 22, 23 dengan stasiun 5 sebagai stasiun awal. Perjalanan kereta dimulai dari stasiun awal ke stasiun tepat setelahnya sampai ke stasiun akhir kemudian kembali ke stasiun awal untuk setiap rutenya. Pada setiap rute, kereta harus berhenti di setiap stasiun secara berurut.
Gambar 6 Jaringan rel kereta.
Tipe kereta yang tersedia ada 8 tipe. Setiap tipe kereta memiliki karakteristik dan biaya masing-masing. Karakteristiknya terdiri dari waktu perjalanan kereta antarstasiun, waktu maksimum dan minimum perjalanan kereta antarstasiun, waktu tunggu kereta di stasiun, kapasitas tiap gerbong, serta waktu kereta dari stasiun awal sampai kembali lagi ke stasiun tersebut (cycle time). Setiap rute memiliki jarak tertentu dan akan dilalui satu tipe kereta. Biayanya terdiri dari biaya tetap mesin kereta dan gerbong kereta, biaya taktetap mesin kereta dan gerbong kereta. Pada kasus kali ini, waktu periodiknya adalah 60 menit (P = 60
menit). Jadi selisih waktu keberangkatan kereta di stasiun awal untuk setiap rute adalah 60 menit. Data yang ada dapat dilihat pada Lampiran 2. Data dan jaringan rute rel kereta pada karya ilmiah ini merupakan data hipotetik. Banyaknya gerbong yang tersedia adalah 2, 4, 6, atau 8 gerbong pada setiap tipe kereta. Data yang ada kemudian diolah dalam program dengan menggunakan perangkat lunak LINGO 11.0. Pada pembahasan penyelesaian masalah karya ilmiah ini akan dijelaskan penyelesaian setiap subprolem beserta penyelesaian tahapan setiap subproblem. Penyelesaian masalah ini
11
tidak dapat dilakukan dalam satu tahap. Terdapat 4 tahapan yang diperlukan dalam memecahkan setiap subproblem yang ada. Tahapannya yaitu pemilihan kereta, penjadwalan tahap I, penjadwalan tahap II (perbaikan jadwal dengan penundaan waktu tiba atau waktu keberangkatan), kemudian pemeriksaan kefisibelan. Pada tahap 1, yaitu pemilihan kereta, data yang diperlukan adalah waktu keberangkatan kereta dari stasiun awal sampai kembali lagi ke stasiun tersebut (cycle time), selisih waktu keberangkatan antarkereta dari stasiun awal, biaya tetap mesin kereta dan gerbong kereta, biaya taktetap mesin kereta dan gerbong kereta, jarak setiap rute, kapasitas gerbong kereta, kapasitas penumpang antarstasiun. Tahap ini hanya menggunakan sebagian formulasi model MCSP yaitu fungsi objektif (1), serta kendala (2) dan (3) yang terdapat di Bab III. Pada tahap 2, penjadwalan tahap I, data yang diperlukan adalah waktu perjalanan kereta antarstasiun dan waktu tunggu kereta di stasiun. Pada tahap ini formulasi yang digunakan yaitu persamaan (5) dan (6) yang terdapat pada Bab III. Pada tahap 3, penjadwalan tahap II, data yang diperlukan adalah waktu keberangkatan dan kedatangan kereta yang diperoleh dari tahap 2. Formulasi yang digunakan pada tahap ini yaitu kondisi (7), fungsi objektif (8), kendala (9), serta persamaan (10), (11), (12), (13), (14), (15), (15), dan (17) pada Bab III. Pada tahap 4, pemeriksaan kefisibelan, data yang diperlukan adalah waktu perjalanan maksimum dan minimum, serta waktu keberangkatan dan kedatangan yang diperoleh dari tahap 3. Pada tahap ini fomulasi model MCSP yang digunakan yaitu kendala (4) pada Bab III. 1. Subproblem 1 Pada Subproblem 1, himpunan tipe kereta yang dapat digunakan pada suatu rute masih lengkap. Tahap 1 Data yang ada pada tahap 1 ini dimasukkan ke dalam program menggunakan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4) dan diperoleh hasil pada Tabel 13 Lampiran 3. Pada rute 1 terpilih kereta tipe 5 dengan banyaknya gerbong adalah 4. Pada rute 2 terpilih kereta tipe 7 dengan banyaknya gerbong adalah 6. Pada rute 3 terpilih kereta tipe 5 dengan banyaknya gerbong adalah 6. Pada rute 4 terpilih kereta tipe 4 dengan banyaknya gerbong adalah 6. Pada rute 5
terpilih kereta tipe 5 dengan banyaknya gerbong adalah 6. Pemilihan kereta ini mengeluarkan biaya Rp 76.602.000,-. Biaya ini menjadi batas bawah untuk biaya minimum pada proses selanjutnya. Tahap 2 Pada tahap selanjutnya dibuat penjadwalan tahap I dari tipe kereta yang terpilih. Penjadwalan dibuat dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Penjadwalannya dibuat untuk satu perjalanan kereta dari stasiun awal kembali ke stasiun awal lagi. Jeda kereta berikutnya pada rute yang sama adalah 60 menit. Hasil penjadwalan tahap I dapat dilihat pada Tabel 1. Tahap 3 Dari penjadwalan tahap I didapat bahwa terjadi tabrakan kereta di rute 4 dan 5 antara stasiun 22 dan 23 pada arah 2. Pada rute 4 dan 5 berturut-turut kereta berangkat dari stasiun 23 ke 22 pada menit ke-379 dan menit ke-384 sedangkan kereta datang di stasiun 22 dari 23 pada menit ke-439 dan menit ke-437 dengan kecepatan kereta konstan untuk setiap kereta. Oleh karena itu, dilakukan penjadwalan tahap II dengan melakukan penundaan yang efektif antara waktu keberangkatan atau waktu tiba di rute 4 atau rute 5 dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Dari proses ini, didapatkan hasil bahwa penundaan terjadi pada kedatangan kereta di stasiun 22 dari stasiun 23 pada rute 5 selama 2 menit, tetapi keberangkatan kereta dari stasiun 23 ke stasiun 22 tidak mengalami penundaan. Hal ini mengakibatkan kecepatan kereta di rute 5 mengalami penurunan antara stasiun 22 dan 23 pada arah 2 dibandingkan dengan sebelum penundaan tetapi kecepatannya tetap konstan sehingga tidak terjadi tabrakan. Perbaikan penjadwalannya dapat dilihat pada Tabel 2. Tahap 4 Pada tahap berikutnya dilakukan pemeriksaan kefisibelan perjalanan antarstasiun setelah dilakukan penjadwalan. Pemeriksaan dilakukan dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Pada tahap ini didapat hasil bahwa rute 5 antara stasiun 22 dan 23 takfisibel pada arah 2. Hal ini dikarenakan waktu perjalanan tidak berada pada rentang waktu perjalanan minimum dan maksimum akibat penundaan kereta pada tahp sebelumnya. Karena kendala (5) tidak terpenuhi, dapat disimpulkan bahwa Subproblem 1 takfisibel.
12
Tabel 1 Penjadwalan kereta tahap I Subproblem 1 Waktu (dalam menit) 1 6 Datang 0 63 R1,K5,C2 1 Berangkat 6 70 Datang 620 556 2 Berangkat 563 Waktu (dalam menit) 2 7 Datang 0 61 R2,K7,C3 1 Berangkat 7 67 Datang 743 683 2 Berangkat 689 Waktu (dalam menit) 3 9 Datang 0 60 R3,K5,C3 1 Berangkat 6 66 Datang 752 692 2 Berangkat 698 Waktu (dalam menit) 4 10 Datang 0 65 R4,K4,C3 1 Berangkat 6 73 Datang 745 677 2 Berangkat 685 Waktu (dalam menit) 5 11 Datang 0 54 R5,K5,C3 1 Berangkat 7 60 Datang 752 699 2 Berangkat 705
Stasiun 12 13 14 123 184 249 131 191 255 495 435 371 503 442 377 Stasiun 8 12 13 123 183 242 129 190 248 621 560 502 627 567 508 Stasiun 13 14 15 121 186 246 128 192 254 630 566 504 637 572 512 Stasiun 15 18 19 131 187 244 137 193 250 613 557 500 619 563 506 Stasiun 17 20 21 119 183 245 125 192 253 634 567 506 640 576 514
Tabel 2 Penjadwalan tahap II Subproblem 1 untuk rute 5 Waktu Stasiun (dalam menit) 5 11 17 20 Datang 0 54 119 183 R5,K5,C3 1 Berangkat 7 60 125 192 Datang 752 699 634 567 2 Berangkat 705 640 576
2. Subproblem 2 Pada Subproblem 2, himpunan tipe kereta yang dapat digunakan pada suatu rute berkurang. Himpunan tipe kereta yang dapat digunakan pada suatu rute di Subproblem 2 adalah himpunan kereta seluruhnya dikurangi himpunan penyelesaian pada Subproblem 1 yang takfisibel yaitu kereta 5 pada rute 5. Tahap 1
21 245 253 506 514
15 309 317 14 305 315 435 445
15 370 380
16 311 319 439 447
17 376 382
22 302 311 439* 448
23 371 379*
22 313 322 437* 446
23 375 384*
22 313 322 439* 446
23 375 384
Data yang ada dimasukkan dalam program dengan menggunakan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4) kemudian diperoleh hasil pada Tabel 14 Lampiran 3. Pada rute 1 terpilih kereta tipe 5 dengan banyaknya gerbong adalah 4. Pada rute 2 terpilih kereta tipe 7 dengan banyaknya gerbong adalah 6. Pada rute 3 terpilih kereta tipe 5 dengan banyaknya gerbong adalah 6.
13
Pada rute 4 terpilih kereta tipe 4 dengan banyaknya gerbong adalah 6. Pada rute 5 terpilih kereta tipe 7 dengan banyaknya gerbong adalah 6. Pada pemilihan kereta ini biaya minimumnya sejumlah Rp 77.392.000,. Biaya ini menjadi batas bawah terbaru pada proses selanjutnya. Tahap 2 Pada tahap selanjutnya dibuat penjadwalan tahap I dari tipe kereta yang terpilih. Penjadwalan dibuat dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Penjadwalannya dapat dilihat pada Tabel 3. Tahap 3 Dari penjadwalan tahap I didapat bahwa terjadi tabrakan kereta di rute 4 dan 5 antara stasiun 22 dan 23 pada arah 1. Pada rute 4 dan 5 berturut-turut kereta berangkat dari stasiun 22 ke 23 pada menit ke-311 dan menit ke-320 sedangkan kereta datang di stasiun 23 dari 22 pada menit ke-371 dan menit ke-361 dengan Tabel 3 Penjadwalan kereta tahap I Subproblem 2 Waktu (dalam menit) 1 6 Datang 0 63 R1,K5,C2 1 Berangkat 6 70 Datang 620 556 2 Berangkat 563 Waktu (dalam menit) 2 7 Datang 0 61 R2,K7,C3 1 Berangkat 7 67 Datang 743 683 2 Berangkat 689 Waktu (dalam menit) 3 9 Datang 0 60 R3,K5,C3 1 Berangkat 6 66 Datang 752 692 2 Berangkat 698 Waktu (dalam menit) 4 10 Datang 0 65 R4,K4,C3 1 Berangkat 6 73 Datang 745 677 2 Berangkat 685 Waktu (dalam menit) 5 11 Datang 0 56 R5,K7,C3 1 Berangkat 9 65 Datang 723 667 2 Berangkat 676
kecepatan kereta konstan untuk setiap kereta. Oleh karena itu, dilakukan penjadwalan tahap II dengan melakukan penundaan yang efektif antara waktu keberangkatan atau waktu tiba di rute 4 atau rute 5 dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Dari proses ini, didapatkan hasil bahwa penundaan terjadi pada keberangkatan kereta dari stasiun 22 ke stasiun 23 pada rute 4 selama 2 menit, tetapi kedatangan kereta di stasiun 23 dari stasiun 22 tidak mengalami penundaan. Hal ini mengakibatkan kecepatan kereta di rute 4 harus ditingkatkan antara stasiun 22 dan 23 pada arah 1 dibandingkan dengan sebelum penundaan tetapi kecepatannya tetap konstan sehingga tidak terjadi keterlambatan waktu kedatangan kereta di stasiun 23 dari stasiun 22 pada rute 4. Perbaikan penjadwalannya dapat dilihat pada Tabel 4.
Stasiun 12 13 14 123 184 249 131 191 255 495 435 371 503 442 377 Stasiun 8 12 13 123 183 242 129 190 248 621 560 502 627 567 508 Stasiun 13 14 15 121 186 246 128 192 254 630 566 504 637 572 512 Stasiun 15 18 19 131 187 244 137 193 250 613 557 500 619 563 506 Stasiun 17 20 21 118 180 245 125 187 253 607 545 479 614 552 487
15 309 317 14 305 315 435 445
15 370 380
16 311 319 439 447
17 376 382
22 302 311* 439 448
23 371* 379
22 313 320* 412 419
23 361* 371
14
Tabel 4 Penjadwalan tahap II Subproblem 1 untuk rute 4 Waktu (dalam menit) 4 10 15 Datang 0 65 131 R4,K4,C3 1 Berangkat 6 73 137 Datang 745 677 613 2 Berangkat 685 619
Tahap 4 Pada tahap berikutnya dilakukan pemeriksaan kefisibelan perjalanan antarstasiun setelah dilakukan penjadwalan. Pemeriksaan dilakukan dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Pada tahap ini didapat hasil bahwa rute 4 antara stasiun 22 dan 23 takfisibel pada arah 1. Hal ini dikarenakan waktu perjalanan tidak berada pada rentang waktu perjalanan minimum dan maksimum. Dapat disimpulkan Subprobem 2 takfisibel karena kendala (5) tidak terpenuhi. 3. Subproblem 3 Pada Subproblem 3, himpunan tipe kereta yang dapat digunakan pada suatu rute berkurang. Himpunan tipe kereta yang dapat digunakan pada suatu rute di Subproblem 3 adalah himpunan kereta pada Subproblem 2 dikurangi himpunan penyelesaian pada subproblem 2 yang takfisibel yaitu kereta 4 pada rute 4. Tahap 1 Data yang ada dimasukkan dalam program dengan menggunakan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4) kemudian diperoleh hasil pada Tabel 15 Lampiran 3. Pada rute 1 terpilih kereta tipe 5 dengan banyaknya gerbong adalah 4. Pada rute 2 terpilih kereta tipe 7 dengan banyaknya gerbong adalah 6. Pada rute 3 terpilih kereta tipe 5 dengan banyaknya gerbong adalah 6. Pada rute 4 terpilih kereta tipe 7 dengan banyaknya gerbong adalah 6. Pada rute 5 terpilih kereta tipe 7 dengan banyaknya gerbong adalah 6. Pada pemilihan kereta ini
Stasiun 18 187 193 557 563
19 244 250 500 506
22 302 320* 439 448
23 371 379
biaya minimumnya sejumlah Rp 78.478.000,-. Biaya ini menjadi batas bawah terbaru pada proses selanjutnya. Tahap 2 Pada tahap selanjutnya dibuat penjadwalan tahap I dari tipe kereta yang terpilih. Penjadwalan dibuat dengan program menggunakan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Hasil penjadwalannya dapat dilihat pada Tabel 5. Dari penjadwalan tahap I didapat bahwa tidak terjadi tabrakan antarkereta yang melalui stasiun dan jalur yang sama pada arah yang sama. Oleh karena itu, tidak dilakukan tahap 3 yaitu penjadwalan tahap II. Tahap 4 Pada tahap berikutnya dilakukan pemeriksaan kefisibelan perjalanan antarstasiun setelah dilakukan penjadwalan. Pemeriksaan dilakukan dengan perangkat lunak LINGO 11.0 (dapat dilihat di Lampiran 4). Pada tahap ini diperoleh hasil bahwa seluruh kendala terpenuhi maka solusi yang ada pada Subproblem 3 fisibel. Karena penjadwalan yang ada fisibel, maka proses dihentikan dan didapatkan solusi yang optimal pada Subproblem 3 yaitu rute 1 terpilih kereta tipe 5 dengan banyaknya 4 gerbong, rute 2 terpilih kereta tipe 7 dengan banyaknya 6 gerbong, rute 3 terpilih kereta tipe 5 dengan banyaknya 6 gerbong, rute 4 terpilih kereta tipe 7 dengan banyaknya 6 gerbong, dan rute 5 terpilih kereta tipe 7 dengan banyaknya 6 gerbong dengan biaya minimum Rp 78.478.000,-.
Tabel 5 Penjadwalan kereta tahap I Subproblem 3 Waktu (dalam menit) 1 6 Datang 0 63 R1,K5,C2 1 Berangkat 6 70 Datang 620 556 2 Berangkat 563
Stasiun 12 13 123 184 131 191 495 435 503 442
14 249 255 371 377
15 309 317
15
Penjadwalan kereta tahap I Subproblem 3 (Lanjutan)
R2,K7,C3
R3,K5,C3
R4,K7,C3
R5,K7,C3
Waktu (dalam menit) Datang 1 Berangkat Datang 2 Berangkat Waktu (dalam menit) Datang 1 Berangkat Datang 2 Berangkat Waktu (dalam menit) Datang 1 Berangkat Datang 2 Berangkat Waktu (dalam menit) Datang 1 Berangkat Datang 2 Berangkat
Tabel 5 merupakan penjadwalan akhir pada penyelesaian masalah ini. Ilustrasi perjalanan kereta dari penjadwalan akhir (Tabel 5) dapat dilihat pada Lampiran 5. Waktu yang ada tertera dalam satuan menit dihitung dari waktu tiba kereta pada stasiun awal. Waktu tersebut diperuntukkan kereta pertama pada setiap rute. Kereta berikutnya memiliki jeda 60 menit (P = 60 menit) setelahnya dengan kereta pertama pada
Stasiun 12 13 183 242 190 248 560 502 567 508 Stasiun 13 14 15 121 186 246 128 192 254 630 566 504 637 572 512 Stasiun 15 18 19 133 201 262 143 209 269 609 543 483 619 551 490 Stasiun 17 20 21 118 180 245 125 187 253 607 545 479 614 552 487
2 7 8 0 61 123 7 67 129 743 683 621 689 627
14 15 305 370 315 435 445 380
3 9 0 60 6 66 752 692 698
16 17 311 376 319 439 447 382
4 10 0 66 10 74 742 678 686 5 11 0 56 9 65 723 667 676
22 23 323 371 330 422 429 381 22 23 313 361 320 412 419 371
seluruh waktu tiba dan waktu berangkat untuk setiap rute. Begitu seterusnya sampai kereta terakhir yang dioperasikan untuk setiap rute. Langkah-langkah penyelesaian masalah dalam karya ilmiah ini dapat dilihat pada Gambar 7. Ada 3 subproblem dalam penyelesaian kasus di karya ilmiah ini. Solusi optimal diperoleh pada Subproblem 3 dengan biaya minimum Rp 78.478.000,-.
