MASALAH PENJADWALAN KERETA API JALUR GANDA MENGGUNAKAN MODEL JOB-SHOP NUR APRIANTI DWIYATCITA

MASALAH PENJADWALAN KERETA API JALUR GANDA MENGGUNAKAN MODEL JOB-SHOP

NUR APRIANTI DWIYATCITA

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

ABSTRAK NUR APRIANTI DWIYATCITA. Masalah Penjadwalan Kereta Api Jalur Ganda Menggunakan Model Job-Shop. Dibimbing oleh FARIDA HANUM dan TONI BAKHTIAR. Pemodelan masalah penjadwalan kereta api merupakan kasus khusus dari masalah penjadwalan job-shop. Berdasarkan konsep penjadwalan job-shop, perjalanan kereta api dapat dianggap sebagai pekerjaan (job) yang akan dioperasikan pada suatu sumber daya (resource) yang berupa petak blok atau segmen jalur. Formulasi model penjadwalan kereta api pada karya ilmiah ini disusun sesuai dengan aturan-aturan umum yang berlaku pada sistem perkeretaapian, di antaranya aturan persilangan (crossing), penyusulan (overtaking), dan aturan headway. Khusus jalur ganda, aturan persilangan tidak berlaku, karena terdapat dua jalur yang dapat digunakan untuk dua kereta api yang berlawanan arah. Formulasi model penjadwalan yang dibentuk merupakan jenis integer linear progamming. Model diselesaikan dengan perangkat lunak LINGO 11.0 menggunakan algoritme branch and bound untuk meminimumkan total waktu tempuh maksimum (makespan) kereta api. Aplikasi model dilakukan pada kasus jalur ganda, dengan menggunakan data hipotetik dari MRT (Mass Rapid Transit) rute Lebak Bulus-Sisingamangaraja. Banyaknya MRT Ekonomi yang disimulasikan adalah 11 unit dan MRT Ekspres 7 unit. Jadwal simulasi MRT yang diperlihatkan dengan diagram ruang waktu tidak mengandung konflik dan memiliki total makespan selama 1502 menit. Jadwal pada simulasi menunjukkan adanya penundaan (delay) pada MRT Ekspres selama 11 menit. Penundaan tersebut, pada karya ilmiah ini nilainya dapat dibatasi dengan memberikan kendala tambahan pada model. Namun, nilai makespan yang didapat tidak lebih baik dari sebelumnya. Kata kunci: kereta api, optimisasi, penjadwalan, masalah penjadwalan job-shop

ABSTRACT NUR APRIANTI DWIYATCITA. Double Track Train Scheduling Problem Based on Job-Shop Model. Supervised by FARIDA HANUM and TONI BAKHTIAR. Train scheduling problem can be modeled as a special case of job-shop scheduling problems. Based on the job-shop scheduling concept, the train trip can be considered as a job, which will be scheduled on tracks as resources. In this paper, train scheduling model is formulated under common rules in railroad system, e.g. crossing, overtaking and headway rules. The crossing rule is not implemented for double track, because there are two tracks that can be used by two trains with different directions. The train scheduling model is expressed in the form of integer linear programming and solved by branch and bound algorithm to minimize the total makespan. The model is then implemented for double track case of Mass Rapid Transit (MRT) Lebak BulusSisingamangaraja route, which involves 11 MRT Economy and 7 MRT Express trains using hypothetical data. The train time-space diagrams show that there is no conflicts occurred and the total makespan is 1502 minutes. The result, in particular, indicates that there is an 11 minutes delay for MRT Express. The length of the delay can be reduced by employing an additional delay constraint. But, of course, this will deteriorate the makespan. Keywords: train, optimization, scheduling, job-shop scheduling problem

MASALAH PENJADWALAN KERETA API JALUR GANDA MENGGUNAKAN MODEL JOB-SHOP

NUR APRIANTI DWIYATCITA

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2012

Judul Nama NIM

: Masalah Penjadwalan Kereta Api Jalur Ganda Menggunakan Model Job-Shop : Nur Aprianti Dwiyatcita : G54070031

Menyetujui Pembimbing I

Pembimbing II

Dra. Farida Hanum, M.Si. NIP. 19651019 199103 2 002

Dr. Toni Bakhtiar, M.Sc. NIP. 19720627 199702 1 002

Mengetahui Ketua Departemen

Dr. Berlian Setiawaty, M.S. NIP. 19650505 198903 2 004

Tanggal Lulus:

KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah SWT atas nikmat, rahmat, dan kasih sayangNya sehingga penulis mampu menyelesaikan karya ilmiah ini. Karya ilmiah ini disusun dengan mendapat banyak dukungan baik moril maupun materiil dari berbagai pihak. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1 Sang pencipta, Tuhan semesta alam Allah SWT atas maha karya-Nya yaitu bumi yang sempurna ini; Nabi Muhammad SAW semoga selawat senantiasa tercurah kepadanya, keluarganya, sahabat, dan para pengikutnya; 2 Drs. Rochmani dan Dra. Indrati Soeprapto Putri sebagai orang tua yang selalu mendo’akan, menyayangi, dan memberikan motivasi kepada penulis; Sutidjah, nenek tercinta yang selalu sabar dan mendo’akan penulis; Muhammad Inderawan Sukma, S.Sos.I, kakak tersayang sebagai pemberi semangat, motivasi, dan doa; 3 Dra. Farida Hanum, M.Si. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, dan doa; 4 Dr. Toni Bakhtiar, M.Sc. selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya; 5 Dr. Ir. Amril Aman, M.Sc. selaku dosen penguji yang telah memberikan ilmu, saran, dan doanya; 6 semua dosen Departemen Matematika, atas semua ilmu yang telah diberikan; 7 staf Departemen Matematika: Bapak Yono, Bapak Hery, Bapak Deni, Ibu Ade, Bapak Epul, Bapak Bono, dan Ibu Susi atas semangat dan doanya; 8 sahabat yang selalu memberi semangat dan doa: Kak Bairanti, Uswah, Izzah, Ajeng, Nadia, Kak Yani, Kak Icha, Kak Heggy, Kak Acid, Arina, Deva, Maya, Prama, Ayum, Rofi, Rizky, Ruhiyat, Indin, Lili, Ima, Imam, Denda, Kak Tasrifin, Kak Dwi Setianto dan Kak Wira; 9 keluarga besar Eyang RM. H. M. Soeprapto dan Kong Narmin yang selalu memberi motivasi dan doa; 10 semua teman Matematika 43 yang selalu menjadi contoh yang baik; 11 semua teman Matematika 44 yang saya banggakan dan saya sayangi; 12 semua teman Matematika 45 yang selalu memberi semangat dan doa; 13 teman seperjuangan Aisyah: Kak Achi, Kak Leni, Kak Leli, Kak Awal, Kak Risma, Kak Aulia, Kak Mutty, Kak Imel, Kak Susi, Kak Ipit, dan Nanda; 14 Forkom SMAN 1 Bogor, BEM KM Kabinet Totalitas Perjuangan dan Kabinet Generasi Inspirasi IPB, BEM G FMIPA IPB Kabinet Kesatria Pembaharu, Gumatika, dan Primagama; 15 Yayasan Karya Salemba Empat (KSE), Mien R. Uno Foundation (MRUF), dan E-Camp Indonesia yang telah memberikan beasiswa; 16 semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya bidang matematika dan menjadi inspirasi bagi penelitian selanjutnya.

Bogor, Mei 2012

Nur Aprianti Dwiyatcita

RIWAYAT HIDUP Penulis dilahirkan di Bekasi pada tanggal 19 April 1989 sebagai anak kedua dari dua bersaudara, anak dari pasangan Drs. Rochmani dan Dra. Indrati Soeprapto Putri. Pada tahun 2001 penulis lulus dari SD Negeri Kartika Sejahtera Bogor sebagai lulusan terbaik kedua, kemudian pada tahun 2004 lulus dari SMP Negeri 1 Bojonggede dengan prestasi sebagai siswa teladan. Tahun 2007 penulis lulus dari SMA Negeri 1 Bogor dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur USMI (Undangan Seleksi Masuk IPB), dengan Mayor Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA), kemudian mendapat Minor Statistika mulai tahun kedua perkuliahan. Selama mengikuti perkuliahan, penulis pernah menjadi asisten dosen mata kuliah Pemrograman Linear pada 2010/2011. Tahun 2010 penulis meraih juara IV Olimpiade Matematika dan mewakili IPB dalam OSN (Olimpiade Sains Nasional) bidang Matematika. Penulis juga pernah meraih juara III pada kompetisi Sesi Poster yang diadakan oleh Departemen Matematika IPB. Selain berprestasi, penulis sangat aktif di beberapa kegiatan kemahasiswaan di antaranya:  Anggota Departemen PPSDM BEM KM (Pendidikan dan Pengembangan Sumber Daya Manusia Badan Eksekutif Mahasiswa Keluarga Mahasiswa) IPB 2007/2008,  Sekretaris Departemen Sains dan Teknologi BEM FMIPA IPB 2008/2009,  Direktur Administrasi dan Keuangan Biro Bisnis dan Kemitraan BEM KM IPB 2009/2010,  Ketua Biro Kesekretariatan Gugus Mahasiswa Matematika (Gumatika) FMIPA IPB 2009/2010,  Ketua Bidang Humas Data Center Forum Komunikasi Alumni Muslim SMA Negeri 1 Bogor (Forkom Alims) 2009/2010. Penulis juga sangat aktif di banyak kegiatan kepanitiaan dari organisasi yang sedang diikuti baik tingkat kampus maupun tingkat nasional di antaranya:  Humas acara pemecahan Rekor MURI dalam MPKMB (Masa Perkenalan Kampus Mahasiswa Baru) IPB 2008,  Sekretaris Pesta Sains Nasional 2009,  Sekretaris Lomba Karya Cipta Mahasiwa Nasional 2009,  Manajer Administrasi Program EDU (Entrepreneur Development Unit) BEM KM IPB 2010. Kegiatan keagamaan yakni membina siswi SMA Negeri 1 Bogor melalui adanya mentoring, juga turut menjadi bagian kegiatan penulis. Selain itu, penulis pun sudah bekerja menjadi staf akademik bimbingan belajar Primagama sejak tingkat akhir perkuliahan. Selama kuliah penulis mendapat beasiswa di antaranya Beasiswa Yayasan Karya Salemba Empat (KSE), Mien R. Uno Foundation (MRUF), dan E-Camp Indonesia. Selain mendapat beasiswa berupa dana tunai, penulis aktif mengkuti berbagai kegiatan seminar dan workshop pengembangan softskill yang diadakan oleh beasiswa. Penulis juga pernah mengikuti Program Mahasiswa Wirausaha (PMW) IPB dan mendapat modal untuk mendirikan usaha. Hasil penilaian usaha oleh CDA (Career Development Affair) IPB memberikan rapor hijau atas keberhasilan membangun usaha dan perkembangan usaha penulis yang semakin maju. Oleh karena itu, pada tahun 2010 penulis berkesempatan mengikuti kegiatan Seminar dan Workshop Wirausaha Muda Mandiri di Jakarta Convention Center.

DAFTAR ISI Halaman

I

DAFTAR TABEL ...............................................................................................................

ix

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

ix

DAFTAR LAMPIRAN .......................................................................................................

x

PENDAHULUAN 1.1 Latar Belakang ........................................................................................................... 1.2 Tujuan ........................................................................................................................

1 1

II LANDASAN TEORI 2.1 2.2 2.3 2.4 2.5

Pemrograman Linear .................................................................................................. Solusi Pemrograman Linear ....................................................................................... Algoritme Branch and Bound .................................................................................... Masalah Penjadwalan Job-Shop ................................................................................. Aturan Umum Perjalanan Kereta Api Jalur Tunggal dan Ganda ...............................

1 2 3 5 7

III PEMODELAN MASALAH PENJADWALAN KERETA API DAN APLIKASINYA 3.1 Model Matematika ..................................................................................................... 8 3.2 Aplikasi Model ........................................................................................................... 11 IV SIMPULAN DAN SARAN ............................................................................................... 20 DAFTAR PUSTAKA .............................................................................................................. 20 LAMPIRAN............................................................................................................................. 21

viii

DAFTAR TABEL Halaman 1 Waktu pemrosesan setiap operasi (menit) dari Contoh 3 ......................................................

6

2 Simulasi jadwal kedatangan dan keberangkatan MRT dari Lebak Bulus ke Sisingamangaraja (menit ke-) ................................................................................................ 18 3 Simulasi jadwal kedatangan dan keberangkatan MRT dari Sisingamangaraja ke Lebak Bulus (menit ke-) ....................................................................................................... 19 4 Data simulasi dari perjalanan MRT Lebak Bulus-Sisingamangaraja .................................... 24 5 Waktu kedatangan setiap MRT di stasiun pertama ............................................................... 25 6 Simulasi jadwal kedatangan dan keberangkatan MRT dari Lebak Bulus ke Sisingamangaraja dengan waktu delay MRT Ekspres 6 menit (menit ke-) ........................... 36 7 Simulasi jadwal kedatangan dan keberangkatan MRT dari Sisingamangaraja ke Lebak Bulus dengan waktu delay MRT Ekspres 6 menit (menit ke-) .................................. 37

DAFTAR GAMBAR Halaman 1

Bagan dari penyelesaian ILP (8) dengan algoritme Branch and Bound ..............................

5

2

Diagram Gantt dari Contoh 3 kombinasi 1 ..........................................................................

6

3

Diagram Gantt dari Contoh 3 kombinasi 2 ..........................................................................

7

4

Diagram Gantt dari Contoh 3 kombinasi 3 ..........................................................................

7

5

Ilustrasi dari istilah perkeretaapian ......................................................................................

8

6

Ilustrasi suatu rute perjalanan kereta api jalur ganda ..........................................................

9

7

Ilustrasi perjalanan MRT rute Lebak Bulus-Sisingamangaraja .......................................... 11

8

Diagram ruang waktu dari simulasi penjadwalan MRT dari Lebak Bulus ke Sisingamangaraja yang mengandung konflik .................................................................... 14

9

Diagram ruang waktu dari simulasi penjadwalan MRT dari Sisingamangaraja ke Lebak Bulus yang mengandung konflik .............................................................................. 15

10 Diagram ruang waktu dari simulasi penjadwalan MRT dari Lebak Bulus ke Sisingamangaraja yang sudah tidak mengandung konflik ................................................... 16 11 Diagram ruang waktu dari simulasi penjadwalan MRT dari Sisingamangaraja ke Lebak Bulus yang sudah tidak mengandung konflik ........................................................... 17 12 Diagram ruang waktu dari simulasi penjadwalan MRT dari Lebak Bulus ke Sisingamangaraja dengan waktu delay MRT Ekspres menjadi 6 menit .............................. 34 13 Diagram ruang waktu dari simulasi penjadwalan MRT dari Sisingamangaraja ke Lebak Bulus dengan waktu delay MRT Ekspres menjadi 6 menit ...................................... 35

ix

DAFTAR LAMPIRAN Halaman 1 Syntax Program LINGO 11.0 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch and Bound beserta Hasil yang Diperoleh ..................................................... 22 2 Data Simulasi Penjadwalan MRT Lebak Bulus-Sisingamangaraja ....................................... 24 3 Syntax Program LINGO 11.0 untuk Simulasi Penjadwalan MRT Lebak BulusSisingamangaraja beserta Hasil yang Diperoleh .................................................................... 26 4 Hasil Simulasi Penjadwalan MRT dengan Nilai Delay MRT Ekspres Dibatasi ................... 34

x

I PENDAHULUAN 1.1 Latar Belakang Sarana transportasi yang aman, nyaman, dan cepat sangat dibutuhkan oleh masyarakat, khususnya yang memiliki mobilitas tinggi dalam kesehariannya. Fenomena ibukota sebagai pusat dari kegiatan perekonomian mencerminkan bahwa sudah selayaknya sistem transportasi yang ada minimal memenuhi ketiga standar tersebut. Salah satu alat transportasi darat yang dapat mengangkut massa dalam jumlah banyak, cepat, dan murah adalah kereta api. Sistem penjadwalan kereta api yang optimal harus diperhatikan dalam menciptakan lalu lintas kereta api yang sesuai dengan aturan-aturan perkeretaapian. Sistem penjadwalan kereta api yang efektif dan efisien juga akan meminimalisasi terjadinya penumpukan penumpang di stasiun akibat adanya penundaan keberangkatan kereta api. Masalah penjadwalan kereta api merupakan hal yang tidak mudah diselesaikan terlebih pada jalur kereta api yang cukup kompleks. Terdapat banyak aturan atau batasan yang harus dipenuhi dalam memecahkan masalah ini. Salah satunya adalah bagaimana perjalanan suatu kereta api dapat berlangsung tanpa terjadi tumpang tindih dengan perjalanan kereta api yang lainnya. Oliveira dan Smith (2000) menyebutkan bahwa masalah penjadwalan kereta api dapat dipandang sebagai implementasi masalah

penjadwalan job-shop secara khusus; perjalanan-perjalanan kereta api dianggap sebagai sekumpulan pekerjaan (jobs) yang dijadwalkan pada sekumpulan sumber daya (resources) yang berupa segmen-segmen jalur kereta api. Oleh karena itu, pada karya ilmiah ini akan dibahas penyelesaian masalah penjadwalan kereta api menggunakan model penjadwalan job-shop dengan meminimumkan total waktu tempuh perjalanan. Pemodelan tersebut akan dilakukan pada kasus kereta api dengan jalur ganda. Kemudian dilakukan studi kasus dengan menggunakan data hipotetik. Model yang dihasilkan akan diselesaikan menggunakan perangkat lunak LINGO 11.0. 1.2 Tujuan Tujuan umum dari karya ilmiah ini adalah menyelesaikan masalah penjadwalan kereta api yang merupakan implementasi masalah penjadwalan job-shop secara khusus. Sedangkan tujuan khusus dari karya ilmiah ini adalah sebagai berikut: 1 memodelkan masalah penjadwalan jobshop untuk kereta api jalur ganda, 2 melakukan simulasi penjadwalan kereta api jalur ganda dengan menggunakan data hipotetik, 3 mencari solusi dari model masalah penjadwalan kereta api menggunakan perangkat lunak LINGO11.0,

II LANDASAN TEORI Definisi dan konsep yang harus dipahami dalam memodelkan masalah penjadwalan kereta api akan dijelaskan pada bab ini. Penjelasan yang akan disampaikan adalah teori dasar pemrograman linear dan algoritme penyelesaiannya yakni branch and bound. Selain itu, teori masalah penjadwalan jobshop juga akan dijelaskan pada bab ini. 2.1 Pemrograman Linear Pemrograman linear dapat dijelaskan dengan terlebih dahulu memahami dua definisi berikut ini. Definisi 1 (Fungsi Linear) Suatu fungsi f dalam variabel-variabel , ,…, adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan

konstanta , sebagai f ( , .

,…, ,…,

, fungsi f dapat ditulis )= + + +

(Winston 2004)

Definisi 2 (Pertidaksamaan dan Persamaan Linear) Sembarang fungsi linear f dan sembarang nilai c, yang berbentuk f ( , , … , ) ≤ dan f ( , , … , ) ≥ disebut sebagai pertidaksamaan linear. Sedangkan, untuk sembarang fungsi linear f dan sembarang nilai c, yang berbentuk f ( , , … , ) = disebut sebagai persamaan linear. (Winston 2004) Pemrograman linear adalah suatu masalah optimisasi yang memenuhi hal-hal berikut: 1 bertujuan memaksimumkan atau meminimumkan suatu fungsi linear dari

2

sejumlah variabel keputusan; fungsi yang akan dimaksimumkan atau diminimumkan disebut sebagai fungsi objektif, 2 nilai variabel-variabel keputusannya memenuhi suatu himpunan kendala yang berupa persamaan linear atau pertidaksamaan linear, 3 terdapat pembatasan tanda untuk setiap variabel dalam masalah ini. Misalkan untuk sembarang variabel , nilai dari harus taknegatif ( ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign).

(Winston 2004)

Definisi 3 (Bentuk Standar Pemrograman Linear) Misalkan diberikan suatu pemrograman linear (PL) dengan m kendala dan n variabel ( , , … , ). Bentuk standar dari PL tersebut adalah: maksimumkan z = + + + (atau minimumkan), dengan kendala: + + + = (1) + + + = (2) … + + + = (3) ≥ 0, ( = 1, 2, . . . , ). Kendala (1), (2), dan (3) dapat ditulis dalam bentuk: Ax = b, dengan (4) A=

=

⋮ ⋮

⋮

,

=

⋮

,

. (Winston 2004)

2.2 Solusi Pemrograman Linear Suatu PL dapat diselesaikan dengan berbagai metode, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi yang optimum bagi PL yang menggunakan proses iteratif pada penyelesaiannya. Vektor x yang memenuhi kendala = disebut solusi. Misalkan matriks A dinyatakan sebagai A = (B N), dengan B adalah matriks taksingular berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n – m) yang elemenelemennya berupa koefisien variabel nonbasis pada matriks kendala. Misalkan vektor x

dinyatakan

sebagai

x

=

,

dengan

adalah vektor variabel basis dan adalah vektor variabel nonbasis, maka = dapat dinyatakan sebagai : =(

)

=B

+N

= b.

(5)

Matriks B memiliki invers karena merupakan matriks taksingular, sehingga dari (5) dapat dinyatakan sebagai: = − , (6) dan fungsi objektifnya berubah menjadi: minimumkan z = + .

(Winston 2004)

Definisi 4 (Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004) Definisi 5 (Solusi Basis) Misalkan terdapat suatu masalah PL Ax=B yang dibentuk dari m persamaan linear dan n variabel (n ≥ m). Solusi basis dari Ax=B dapat diperoleh dengan mengatur nilai n-m variabel sama dengan nol dan menyelesaikan m variable sisanya. Cara tersebut dapat menghasilkan nilai yang unik untuk m variable sisanya. Kolom-kolom untuk m variabel sisanya adalah bebas linear. (Winston 2004) Definisi 6 (Solusi Fisibel Basis) Solusi fisibel basis adalah solusi basis pada PL yang semua variabel-variabelnya taknegatif. (Winston 2004) Definisi 7 (Solusi Optimum) Solusi optimum suatu PL untuk masalah maksimisasi merupakan suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Sedangkan solusi optimum suatu PL untuk masalah minimisasi, adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) Ilustrasi solusi basis dan solusi fisibel basis diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan PL berikut: minimumkan z = −2 − 3 terhadap − + 2 + = 10 −2 + + = 2 2 + = 3 , , , , ≥ 0.

(7)

3

Dari PL tersebut diperoleh: −1 A = −2 2

2 1 0

PL-relaksasi untuk masalah minimisasi lebih kecil atau sama dengan nilai optimum fungsi objektif ILP. (Winston 2004)

1 0 0 10 0 1 0 ,b= 2 . 0 0 1 3

Misalkan dipilih: =(

) dan

=(

1 0 , 0

=

maka matriks basisnya adalah: −1 B = −2 2 0 0 N= 1 0 0 1 = (−2

2 1 0

,

−3

0),

= (0

0 0 1

2.3 Algoritme Branch and Bound

) ,

0

1 −2

1 ,

0),

dengan menggunakan matriks basis tersebut, diperoleh: = (0

=

= 0) , = −18.

=

5

, (8)

Solusi (8) merupakan solusi basis, karena memenuhi kendala pada PL (7) dan kolomkolom pada matriks kendala yang berpadanan dengan komponen taknol dari (8), yaitu B bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (8) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Definisi 8 (Integer Linear Progamming) Integer linear progamming (ILP) adalah suatu pemrograman linear yang variabelnya merupakan bilangan bulat yang taknegatif. Apabila semua variablenya merupakan bilangan bulat maka ILP disebut sebagai pure integer progamming. Masalah ILP yang hanya beberapa variabelnya saja berupa bilangan bulat disebut sebagai mixed integer progamming. Selain itu, masalah ILP yang semua variabelnya harus bernilai 0 atau 1 disebut sebagai integer progamming 0-1. (Winston 2004) Definisi 9 (Pemrograman Linear Relaksasi) Relaksasi pemrograman linear atau sering disebut PL-relaksasi merupakan suatu pemrograman linear yang diperoleh dari suatu ILP dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Nilai optimum fungsi objektif PL-relaksasi untuk masalah maksimisasi lebih besar atau sama dengan nilai optimum fungsi objektif ILP. Sedangkan nilai optimum fungsi objektif

Solusi optimum dari masalah ILP pada karya ilmiah ini dicari menggunakan perangkat lunak LINGO 11.0, yaitu sebuah program yang dirancang untuk menentukan solusi model linear, nonlinear, dan optimisasi integer. Perangkat lunak LINGO 11.0 ini menggunakan algoritme branch and bound untuk menyelesaikan masalah ILP. Menurut Taha (1975), terdapat dua konsep dasar dalam algoritme branch and bound, yaitu:  Branching Branching (pencabangan) adalah proses membagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi.  Bounding Bounding (pembatasan) adalah suatu proses untuk mencari atau menghitung batas atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimum subproblem yang mengarah ke solusi optimum ILP. Metode branch and bound diawali dengan menyelesaikan PL-relaksasi dari suatu ILP. Jika semua nilai variabel keputusan solusi optimum sudah berupa integer, maka solusi tersebut merupakan solusi optimum ILP. Jika tidak, dilakukan pencabangan dan penambahan batasan kendala pada PL-relaksasinya. Menurut Winston (2004), pada kasus maksimisasi, nilai fungsi objektif optimum dari ILP ≤ nilai fungsi objektif optimum dari PL-relaksasi, sehingga nilai fungsi objektif optimum PL-relaksasi merupakan batas atas bagi nilai fungsi objektif optimum untuk masalah ILP. Selain itu, untuk masalah maksimisasi nilai fungsi objektif optimum suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimum masalah ILP asalnya. Suatu kandidat solusi diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah ILP, artinya fungsi objektif dan semua variabelnya sudah bernilai integer. Suatu subproblem dikatakan terukur (fathomed) jika terdapat situasi sebagai berikut: 1 subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimum untuk ILP,

4

2 subproblem tersebut menghasilkan suatu solusi optimum dengan semua variabelnya bernilai integer; jika solusi optimum ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimum dan nilai fungsi objektifnya menjadi batas bawah (dalam masalah maksimisasi) dan batas atas (dalam masalah minimisasi); subproblem tersebut dimungkinkan menghasilkan solusi optimum masalah ILP, 3 nilai fungsi objektif optimum subproblem tersebut tidak melebihi batas bawah saat itu (untuk masalah maksimisasi), maka subproblem ini dapat dieliminasi. (Winston 2004) Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch and bound.  Langkah 0 Definisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) ILP yang optimum dan tetapkan z = ─∞ serta i = 0.  Langkah 1 Subproblem PL( ) dipilih sebagai bagian masalah berikutnya untuk diperiksa. Subproblem tersebut diselesaikan dan diukur dengan kondisi yang sesuai. a) Jika PL( ) terukur dan solusi ILP yang lebih baik ditemukan, maka batas bawah z diperbarui. Jika tidak, bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah diperiksa, maka proses dihentikan. b) Jika PL( ) tidak terukur, proses dilanjutkan ke langkah 2 untuk melakukan pencabangan PL( ) .  Langkah 2 Pilih salah satu variabel yang nilai optimumnya adalah ∗ dan tidak memenuhi batasan integer dalam solusi PL( ) . Kemudian bidang  x*j   x j   x*j   1, dipecah menjadi

dua subproblem,yaitu x j   x*j  dan x j   x*j   1, dengan [ ∗ ] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan ∗ . Jika PL( ) masih tidak terukur, maka kembali ke langkah 1. (Taha 1996)

Ilustrasi dari masalah ILP yang akan diselesaikan dengan algoritme branch and bound diberikan pada Contoh 2. Contoh 2 Misalkan diberikan ILP sebagai berikut, maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1, x2 ≥ 0 x1, x2 bilangan bulat.

(8)

Algoritme branch and bound untuk menyelesaikan ILP (8) dimulai dengan mencari solusi PL-relaksasi yang disebut sebagai subproblem 1. Solusi optimal dari PLrelaksasi adalah z = 82.5, x1 = 3.75, dan x2 = 2.25 yang dapat dilihat di Lampiran 1. Berdasarkan teori yang telah diberikan sebelumnya, bahwa nilai optimum z dari ILP ≤ nilai optimum z dari PL-relaksasi, maka nilai optimum z dari ILP (8) tidak dapat melebihi 82.5. Kemudian nilai optimum z dari PL-relaksasi ditetapkan sebagai batas atas. Langkah selanjutnya adalah memartisi wilayah fisibel dari PL-relaksasi untuk menemukan solusi optimal dari ILP (8). Nilai dari varibel x1 dan x2 pada PL-relaksasi belum menunjukkan nilai yang integer. Oleh karena itu partisi dapat dimulai dengan melihat nilai x1 atau x2. Misalkan variabel pertama yang akan dipartisi adalah x1. Setiap titik pada wilayah fisibel ILP (8) harus memenuhi x1 ≤ 3 atau x1 ≥ 4, sehingga pencabangan dari variabel x1 menghasilkan dua subproblem, yakni subproblem 2 dan 3. Subproblem 2 merupakan subproblem 1 dengan kendala tambahan x1 ≥ 4 dan subproblem 3 merupakan subproblem 1 dengan kendala tambahan x1 ≤ 3. Solusi optimal dari subproblem 2 adalah z = 82, x1 = 4, dan x2 = 1.8 yang dapat dilihat di Lampiran 1. Nilai x2 dari subproblem 2 belum berupa integer, sehingga dilakukan pencabangan yang menghasilkan subproblem 4 dan 5. Subproblem 4 merupakan subproblem 2 dengan kendala tambahan x2 ≥ 2 dan subproblem 5 merupakan subproblem 2 dengan kendala tambahan x2 ≤ 1. Terdapat tiga subproblem yang belum diselesaikan, yakni 3, 4, dan 5. Berdasarkan aturan LIFO (last-infirst-out) subproblem yang akan diselesaikan terlebih dahulu adalah subproblem 4 atau 5. Misalkan dipilih subproblem 4, solusi dari subproblem 4 ternyata takfisibel yang dapat dilihat di Lampiran 1. Oleh karena itu, subproblem 4 tidak dapat dijadikan sebagai solusi optimal ILP (8). Sedangkan solusi

5

optimal dari subproblem 5 adalah z = 81.11, x1 = 4.44, dan x2 = 1 yang dapat dilihat di Lampiran 1. Nilai x1 pada subproblem 5 belum berupa integer, sehingga dilakukan kembali pencabangan menjadi subproblem 6 dan 7. Subproblem 6 merupakan subproblem 5 dengan kendala tambahan x1 ≥ 5 dan kendala tambahan x1 ≤ 4 untuk subproblem 7. Terdapat tiga subproblem yang belum diselesaikan, yakni 3, 6, dan 7. Berdasarkan aturan LIFO subproblem yang harus diselesaikan terlebih dahulu adalah subproblem 6 dan 7. Misalkan dipilih subproblem 7. Solusi optimal dari subproblem 7 adalah z = 74, x1 = 4, dan x2 = 1 yang dapat dilihat di Lampiran 1. Nilai variabel x1 dan x2 dari subproblem 7 sudah berupa integer, sehingga solusi tersebut merupakan solusi yang fisibel dan merupakan kandidat solusi optimal ILP (8). Kemudian nilai z = 74 dijadikan sebagai batas bawah. Solusi dari subproblem 6 adalah z = 80, x1 = 5, dan x2 = 0 yang dapat dilihat di Lampiran 1. Setiap variabel keputusan dari subproblem 6 juga sudah berupa integer, sehingga turut menjadi salah satu kandidat solusi optimal dari ILP (8). Nilai z pada subproblem 6 lebih besar dari nilai z pada subproblem 7, sehingga batas bawah diganti menjadi z = 80. Subproblem 3 merupakan satu-satunya masalah yang belum diselesaikan. Solusi dari subproblem 3 adalah z = 78 dan x1 = x2 = 3 yang dapat dilihat di Lampiran 1. Walaupun setiap variabel dari subproblem 3 sudah berupa integer, nilai z-nya kurang dari batas bawah yakni z = 80. Oleh karena itu, subproblem 6 dipilih menjadi solusi optimal ILP (8), dengan nilai z = 80, x1 = 5, dan x2 = 0. Bagan dari penyelesaian ILP (8) dengan algoritme branch and bound ditunjukkan pada Gambar 1. 2.4 Masalah Penjadwalan Job-Shop Masalah penjadwalan job-shop akan dijelaskan dengan terlebih dahulu memahami definisi masalah penjadwalan berikut ini. Masalah Penjadwalan Terdapat tiga istilah yang digunakan dalam pembahasan masalah penjadwalan. Ketiga istilah tersebut adalah pekerjaan (job), prosesor (processor), dan operasi (operation). Pekerjaan merupakan sekumpulan aktivitas yang harus diproses, misalnya pembuatan suatu barang pada pabrik manufaktur atau operasi bedah yang akan dilakukan di suatu

rumah sakit. Prosesor adalah sumber daya yang digunakan untuk memproses pekerjaan, misalnya dapat berupa mesin atau alat-alat kedokteran. Prosesor juga disebut sebagai sumber daya (resource) atau mesin (machine). Operasi merupakan aktivitas pemrosesan dari suatu pekerjaan. Berdasarkan ketiga istilah tersebut, masalah penjadwalan dapat diartikan sebagai proses pengalokasian sumber daya untuk suatu operasi pada periode waktu tertentu. (Pham 2008) Subproblem 1 z = 82.5 x1 = 3.75 x2 = 2.25

t=1

x1 ≥ 4

t=2

x1 ≤ 3

Subproblem 2 z = 82 x1 = 4 x2 = 1.8

Subproblem 3 z = 78 x1 = 3 x2 = 3 x2 ≤ 1

x2 ≥ 2 Subproblem 4 (solusi takfisibel) t=3

×

t=7

×

Subproblem 5 z = 81.11 x1 = 4.44 x2 = 1 x1 ≥ 5

t=4

x1 ≤ 4

Subproblem 6 z = 80 x1 = 5 x2 = 0 BB 2 = 80

Subproblem 7 z = 74 x1 = 4 x2 = 1 BB 1 = 74

t=6

t=5

Keterangan:

×

BB = Batas Bawah; =

×

×Fathomed; t = Iterasi

Gambar 1 Bagan dari penyelesaian ILP (8) dengan algoritme branch and bound. Apabila terdapat dua atau lebih pekerjaan menggunakan prosesor yang sama pada saat yang sama pula, maka suatu jadwal belum

6

disebut sebagai jadwal yang fisibel. Kondisi tersebut pada karya ilmiah ini disebut sebagai konflik. Representasi dari penjadwalan dalam suatu industri biasanya ditampilkan dengan menggunakan diagram Gantt (Pham 2008). Diagram tersebut memperlihatkan pemrosesan setiap pekerjaan pada sumber daya yang tersedia dalam bentuk balok-balok sepanjang waktu tertentu. Salah satu contoh diagram Gantt ditunjukkan pada Gambar 2a. Masalah penjadwalan job-shop merupakan masalah pengalokasian sumber daya untuk setiap operasi yang diproses sesuai dengan urutan yang ditentukan. Hal ini dapat diartikan bahwa urutan operasi dari suatu pekerjaan dapat berbeda dengan pekerjaan yang lainnya, namun operasi-operasi tersebut diproses berdasarkan jadwal penggunaan mesin yang ditentukan. Apabila dilambangkan secara matematis, pada umumnya masalah penjadwalan job-shop memiliki karakteristik sebagai berikut:  terdapat sekumpulan n pekerjaan J = {J1, J2, J3, ..., Jn},  terdapat sekumpulan m sumber daya M={M1, M2, M3, ..., Mm},  setiap pekerjaan memiliki sekumpulan operasi (I); pekerjaan ke-i (Ji) memiliki urutan operasi (oi1, oi2, oi3, ..., oik), dengan k merupakan banyaknya operasi yang dilakukan untuk pekerjaan i,

 setiap sumber daya dapat beroperasi maksimum satu operasi dalam selang waktu tertentu,  setiap operasi dari suatu pekerjaan di sebuah sumber daya membutuhkan sejumlah waktu minimum; waktu minimum pekerjaan ke-i beroperasi di sumber daya ke-j dilambangkan dengan pij, untuk 1  i  n dan 1  j  m . (Shukla 2010) Tujuan dari penyelesaian masalah penjadwalan job-shop adalah menentukan jadwal suatu pekerjaan yang fisibel dengan mempertimbangkan urutan pemrosesan dan kapasitas dari setiap sumber daya. Salah satu kriteria optimasi pada masalah penjadwalan job-shop adalah meminimumkan waktu maksimum pemrosesan dari setiap pekerjaan (makespan) yang dilambangkan dengan Cmaks (Liu dan Kozan 2009). Masalah penjadwalan job-shop dengan meminimumkan Cmaks diilustrasikan pada Contoh 3. Contoh 3 Misalkan diberikan himpunan pekerjaan J={1, 2, 3} dan himpunan mesin M = {1, 2, 3}. Setiap pekerjaan ke-i (Ji) memiliki tiga operasi yang harus diproses secara berurutan, yakni (oi1, oi2, oi3). Penugasan mesin dan waktu pemrosesan untuk setiap operasi diberikan pada Tabel 1.

Tabel 1 Waktu pemrosesan setiap operasi (menit) dari Contoh 3 Mesin 1 2 3

Operasi o11

o12

o13

o21

10

o22

o23

o31

o32

20 20

30

10

20

30

Diagram Gantt dari contoh kasus tersebut ditunjukkan pada Gambar 2, dengan makespan pekerjaan J1, J2, dan J3 masingmasing sebesar 90, 60, dan 60 satuan waktu. Total nilai Cmaks adalah sebesar 210 satuan waktu. Urutan penggunaan mesin pada Gambar 2 dapat diubah, sehingga menghasilkan diagram lain yang total nilai Cmaks-nya dapat dibandingkan dengan Cmaks sebelumnya. Misalkan pada Mesin 2, Pekerjaan 1 diproses lebih dulu daripada Pekerjaan 3, sehingga menghasilkan diagram seperti yang ditunjukkan pada Gambar 3.

o33

30

10

Mesin 1 Mesin 2 Mesin 3

0 10 20 30 40 50 60 70 80 90 Waktu Keterangan: Pekerjaan 1

Pekerjaan 3

Pekerjaan 2 Gambar 2 Diagram Gantt dari Contoh 3 Kombinasi 1.

7

Mesin 1 Mesin 2 Mesin 3

0 10 20 30 40 50 60 70 80 90 Waktu

Gambar 3 Diagram Gantt dari Contoh 3 Kombinasi 2. Selain itu, dari perubahan tersebut dapat dihasilkan diagram baru, yakni dengan mengubah urutan penggunaan Mesin 3. Pekerjaan 1 pada Mesin 3 dapat diproses lebih dulu dari Pekerjaan 2, sehingga menghasilkan diagram pada Gambar 4. Total nilai Cmaks dari Gambar 3 dan 4 masing-masing adalah 230 satuan waktu. Nilai tersebut lebih besar dari total nilai Cmaks sebelumnya, sehingga untuk kasus meminimumkan dipilih Cmaks yang terkecil (dalam kasus ini 210 satuan waktu).

(D’Ariano 2008)

Mesin 1 Mesin 2 Mesin 3

 dwell time, yaitu waktu tunggu atau lama berhenti suatu kereta api di stasiun tertentu,  delay, yaitu kondisi yang terjadi pada kereta api yang telah selesai menggunakan suatu petak blok, namun petak blok berikutnya masih digunakan oleh kereta api yang lain, sehingga kereta api tersebut harus menunda perjalanannya,  time headway, yaitu lama waktu minimum antara dua kereta api yang berurutan menggunakan petak blok yang sama baik di stasiun maupun antarstasiun,  crossing (persilangan), yaitu kondisi ketika dua kereta api yang berlawanan arah menggunakan petak blok yang sama pada suatu waktu tertentu,  overtaking (penyusulan), yaitu kondisi pada saat dua kereta api yang arahnya sama menggunakan petak blok yang sama pada suatu waktu tertentu.

0 10 20 30 40 50 60 70 80 90 Waktu

Gambar 4 Diagram Gantt dari Contoh 3 Kombinasi 3. 2.5 Aturan Umum Perjalanan Kereta Api Jalur Tunggal dan Ganda Sebelum dibahas mengenai aturan umum perjalanan kereta api, akan diberikan beberapa penjelasan mengenai istilah-istilah yang digunakan dalam sistem perkeretaapian sebagai berikut:  sinyal, yaitu tanda isyarat pada permulaan jalur yang akan dilintasi kereta api untuk memberi informasi apakah kereta api dapat melintas, harus berhenti, atau mengurangi kecepatan,  petak blok, yaitu segmen jalur di antara dua sinyal berurutan baik di dalam stasiun maupun antarstasiun; satu petak blok hanya dapat digunakan satu kereta api pada suatu waktu tertentu,  sidding, yaitu petak blok yang terdiri atas minimal dua jalur,  jalur tunggal, yaitu satu jalur yang dapat digunakan kereta api dengan dua arah berlawanan,  jalur ganda, yaitu dua jalur yang dapat digunakan kereta api dengan arah yang sama atau berlawanan,

Aturan umum yang berlaku pada perjalanan kereta api adalah sebagai berikut:  aturan penundaan pada kasus persilangan dan penyusulan, yaitu apabila akan terjadi persilangan atau penyusulan, salah satu kereta api harus ditunda perjalanannya di stasiun atau sidding,  aturan headway, yaitu antara dua kereta api berurutan dalam suatu segmen jalur terdapat jarak aman dalam waktu tertentu, sehingga akan menghindari terjadinya tabrakan antarkereta api,  aturan kecepatan rata-rata minimum dan maksimum kereta api dalam melakukan perjalanan di suatu petak blok yang ditentukan berdasarkan jarak dan waktu tempuh di petak blok tersebut. (Higgins et al. 1996) Aturan persilangan pada jalur ganda tidak berlaku. Hal tersebut karena terdapat dua jalur yang dapat digunakan untuk dua kereta api berlawanan arah. Contoh sebuah ilustrasi perjalanan kereta api jalur tunggal dapat dilihat pada Gambar 5. Gambar 5 menunjukkan bahwa terdapat enam stasiun {s1, s2, …, s6} dan delapan petak blok {r1, r2, ..., r8}. Stasiun s1 dan s2 dipisahkan oleh dua petak blok { r1, r2}, antara stasiun s3 dan s4 terdapat tiga petak blok { r4, r5, r6} dan yang lainnya hanya dipisahkan oleh satu petak blok. Petak blok antarstasiun yang lebih dari satu membentuk petak jalan dan antarpetak blok dipisahkan oleh sinyal (Yuliawan 2008).

8

sidding

petak jalan

petak blok Keterangan:

Stasiun

Sinyal Crossing

Overtaking Gambar 5 Ilustrasi dari istilah perkeretaapian.

III PEMODELAN MASALAH PENJADWALAN KERETA API DAN APLIKASINYA 3.1 Model Matematika Masalah penjadwalan kereta api pada karya ilmiah ini akan dimodelkan dengan mempertimbangkan asumsi sebagai berikut: 1 model dibangun untuk kasus kereta api jalur ganda, 2 satuan waktu terkecil yang digunakan dalam penjadwalan adalah menit, 3 tidak ada urutan prioritas kereta api yang akan menggunakan petak blok yang sama. Model penjadwalan kereta api pada karya ilmiah ini dirancang sebagai alat untuk merencanakan jadwal kereta api pada periode operasi tertentu. Jadwal yang akan dihasilkan merupakan jadwal faktual. Jadwal aktual akan sama dengan jadwal faktual apabila tidak terjadi gangguan operasional seperti pemadaman listrik, bencana alam yang mengakibatkan kerusakan infrastruktur, gangguan sinyal, dan lain sebagainya. Referensi utama yang digunakan penulis dalam memodelkan masalah penjadwalan kereta api jalur ganda adalah tulisan Higgins, et al. (1996). Notasi-notasi yang akan digunakan pada model penjadwalan kereta api sebagai kasus khusus dari masalah penjadwalan job-shop didefinisikan sebagai berikut: n = banyaknya kereta api m = banyaknya petak blok

q S J Ji

= banyaknya stasiun = himpunan stasiun, S = { 1, 2, ..., q} = himpunan kereta api, J = {1, 2, …, n} = perjalanan kereta api i (i = 1, 2, ..., n) (pekerjaan) oik = operasi di petak blok k (k = 1, 2, ..., m) (sumber daya) dari kereta api i h = time headway Xias = waktu kedatangan kereta api i di stasiun s Xids = waktu keberangkatan kereta api i dari stasiun s dk = panjang petak blok k v ik = kecepatan rata-rata minimum kereta api i di petak blok ke-k vik = kecepatan rata-rata maksimum kereta api i di petak blok ke-k pis = lama waktu berhenti kereta api i di stasiun s = waktu delay kereta api i di stasiun s M = bilangan bulat positif besar Cmaks = waktu tempuh maksimum. Misalkan diberikan n buah perjalanan kereta api J1, J2, ..., Jn yang harus dijadwalkan pada l buah rute. Sebuah perjalanan Ji melewati suatu rute yang terdiri atas q buah stasiun dan m buah petak blok. Oleh karena itu pekerjaan yang merepresentasikan perjalanan Ji tersebut terdiri atas m buah operasi oi1, oi2, oi3, ..., oim. Setiap operasi yang dilakukan dalam perjalanan Ji tersebut

9

menggunakan tepat satu sumber daya berupa satu petak blok pada rute yang dilalui, yaitu operasi oik. Misalkan pada suatu rute perjalanan kereta api jalur ganda yang diilustrasikan pada Gambar 6 terdapat m petak blok dan q stasiun. Himpunan kereta api yang akan dioperasikan adalah J = {1, 2, ..., r, r + 1, ..., n}, dengan indeks 1 sampai r untuk kereta api outbound dan r+1 sampai n untuk kereta api inbound. Kereta api outbound pada karya ilmiah ini merupakan jenis kereta api yang melakukan perjalanan dari stasiun ke-1 ke arah stasiun ke-q, sedangkan kereta api inbound merupakan jenis kereta api yang melakukan perjalanan dengan arah sebaliknya. Didefinisikan variabel biner untuk beberapa kondisi antara dua kereta api yang akan terjadi konflik, yaitu: 1, jika kereta api outbound i, dengan  i  r menggunakan petak blok k  Aijk   sebelum kereta api outbound j ,  dengan j  r  0, lainnya, 1, jika kereta api inbound i, dengan  i  r menggunakan petak blok k  Bijk   sebelum kereta api inbound j ,  dengan j  r  0, lainnya.

Fungsi Objektif Minimumkan (9) Cmaks = ∑ − +∑ − , dengan: = waktu kedatangan kereta api i di stasiun ke-1, untuk i = 1, 2, …, r. = waktu keberangkatan kereta api i dari stasiun ke-q untuk kembali ke stasiun pertama atau masuk ke dalam depo, dengan i = 1, 2, …, r. = waktu kedatangan kereta api i di stasiun ke-q, untuk i= r+1, r+2, …, n. = waktu keberangkatan kereta api i dari stasiun ke-1 untuk kembali ke stasiun pertama atau masuk ke dalam depo, dengan i = r+1, r+2, …, n. Kendala-kendala yang harus dipenuhi dalam rangka mendapatkan solusi jadwal kereta api yang fisibel diberikan pada pertaksamaan (10) sampai (24): Kendala 1 (Urutan operasi)

X ias  pis   is  X ids , i  r , s  1, 2, ..., q.

(10)

X ias  pis   is  X ids , i  r , s  q, q  1, ..., 1.

(11)

Kendala (10) dan (11) menunjukkan urutan operasi pada satu perjalanan kereta api di stasiun. Kedua kendala tersebut dikembangkan dari konsep masalah penjadwalan jobshop, yaitu operasi ke-(k + 1) pada pekerjaan Ji hanya bisa dimulai setelah operasi ke-k telah selesai dikerjakan. Waktu dimulainya operasi oi(k + 1) yaitu Xids harus lebih dari atau sama dengan waktu dimulainya operasi oik yaitu Xias ditambah lama waktu pemrosesannya yaitu pis. Selain itu, terdapat variabel delay ( ) yang merupakan lama waktu penundaan dari suatu perjalanan kereta api i di stasiun s untuk menghindari konflik. Waktu tiba kereta api di stasiun pertama merupakan waktu tiba kereta api yang keluar dari depo atau waktu kembali dari stasiun tujuan akhir ke stasiun asal. indeks stasiun inbound

Tujuan penjadwalan kereta api pada karya ilmiah ini adalah meminimumkan total waktu tempuh maksimum. Hal ini dapat dihitung berdasarkan selisih antara waktu kedatangan di stasiun pertama dan waktu keberangkatan dari stasiun akhir kembali ke stasiun awal atau masuk ke dalam depo. Depo merupakan tempat peristirahatan kereta api untuk mendapatkan perawatan, perbaikan mesin, dan sebagainya. Secara matematis fungsi objektif dari masalah penjadwalan kereta api ditunjukkan pada persamaan (9). Kereta api dari 1 sampai r (outbound) berakhir di stasiun q. Sedangkan kereta api r + 1 sampai n (inbound) berakhir di stasiun 1. outbound

1 dk

2

3

.......

indeks petak blok

q

q─1

.......

2

1

m─1 Keterangan:

Gambar 6 Ilustrasi suatu rute perjalanan kereta api jalur ganda.

m Sinyal

10

Kendala 2 (Aturan Penyusulan)

M (1  Bijk )  X jas  X ias  h,

Misalkan terdapat kereta api i dan j dengan arah yang sama akan menggunakan petak blok ke-k secara bersamaan, sehingga operasi oik dan ojk akan diproses pada waktu yang sama. Terdapat dua langkah yang dapat dilakukan agar tidak terjadi konflik. Kedua langkah tersebut adalah dengan mendahulukan perjalanan kereta api Jj atau mendahulukan perjalanan kereta api Ji. Oleh karena itu, kendala dikalikan dengan M, yaitu bilangan positif besar yang digunakan khusus pada kendala either or (pilih salah satu). Pengalian dengan bilangan M terdapat pada kendala (12) sampai (19). Aturan penyusulan untuk jenis kereta api outbound didefinisikan pada kendala (12) sampai (15). Kendala (12) dan (13) digunakan apabila nilai Aijk = 0, yaitu perjalanan kereta api Jj didahulukan, sehingga kereta api j tiba lebih awal dari kereta api i di stasiun berikutnya. Nilai h juga ditambahkan agar terdapat jarak antarkereta api ketika keluar dan masuk stasiun. Kendala (14) dan (15) dapat dijelaskan dengan cara yang sama dengan nilai Aijk = 1, yaitu kereta api i berangkat lebih dulu dari j.

i  j; s  q 1, q  2, ..., 1;

MAijk  X ia ( s 1)  X ja ( s 1)  h,

(12)

(13)

(16)

k  m, m 1, ..., 1.

k  m, m 1, ..., 1.

Kendala 3 (Aturan lama waktu beroperasi) Waktu penggunaan sumber daya pada masalah penjadwalan job-shop secara umum diberikan sebagai input. Waktu tersebut pada masalah penjadwalan kereta api sama dengan jarak tempuh dibagi dengan kecepatan rataratanya. Waktu rata-rata minimum dan maksimum penggunaan suatu petak blok diberikan pada kendala (20) untuk kereta api outbound dan kendala (21) untuk kereta api inbound.

dk d  X ia ( s 1)  X ids  k , i  1, 2, ..., r ; (20) vik v ik

k  1, 2, ..., m; s  1, 2, ..., q 1. dk d  X ia ( s )  X id ( s 1)  k , vik v ik

(21)

Kendala 4 (Stasiun pemberhentian)

X ias  X ids , i  J dan s  S

i  j; s  q 1, q  2, ..., 1;

i  j; s  q 1, q  2, ..., 1;

k  m, m 1, ..., 1.

(15)

Aturan penyusulan pada kereta api inbound juga dapat dijelaskan dengan cara yang sama seperti kereta api outbound. Kendala aturan penyusulan pada kereta api inbound diberikan pada pertaksamaan (16) sampai (19) .

MBijk  X id ( s 1)  X jd ( s 1)  h,

i  j; s  q 1, q  2, ..., 1;

Apabila terdapat kereta api yang hanya berhenti di stasiun-stasiun tertentu, terdapat kendala yang ditambahkan khusus untuk kereta api tersebut, yaitu:

i  j; s  1, 2, ..., q  1; k  1, 2, ..., m.

MBijk  X ias  X jas  h,

(19)

(14)

i  j; s  1, 2, ..., q  1; k  1, 2, ..., m.

M (1  Aijk )  X jds  X ids  h,

M (1  Bijk )  X jd ( s 1)  X id ( s 1)  h,

s  q  1, q  2, ..., 1.

i  j; s  1, 2, ..., q  1; k  1, 2, ..., m.

M (1  Aijk )  X ja ( s 1)  X ia ( s 1)  h,

k  m, m 1, ..., 1.

i  r  1, r  2, ..., n ; k  m, m 1, ..., 1;

i  j; s  1, 2, ..., q  1; k  1, 2, ..., m.

MAijk  X ids  X jds  h,

(18)

(17)

(22)

Kendala (22) menggambarkan bahwa apabila kereta api tidak berhenti di stasiun ke-s, maka waktu kedatangan dan keberangkatan kereta api tersebut di stasiun ke-s adalah sama. Selain itu, sebagai input, waktu tunggu di stasiun tersebut bernilai nol. Kendala 5 (Ketaknegatifan dan biner) Selain kendala-kendala yang telah dijelaskan sebelumnya, terdapat kendala ketaknegatifan dan biner. Kedua kendala tersebut secara berturut-turut didefinisikan sebagai berikut, (23) h, pis , X ias , X ids  0

Aijk , Bijk bernilai 1 atau 0

(24)

11

3.2 Aplikasi Model Aplikasi model pada karya ilmiah ini akan diterapkan dengan data hipotetik pada kasus kereta api jalur ganda yaitu jalur MRT (Mass Rapid Transit) rute Lebak BulusSisingamangaraja, dengan asumsi sebagai berikut: 1 banyaknya kereta api jenis outbound (Lebak Bulus-Sisingamangaraja) adalah sepuluh unit dan jenis inbound (Sisingamangaraja-Lebak Bulus) delapan unit, 2 waktu yang disimulasikan dimulai dari pukul 06.00 WIB, 3 simulasi penjadwalan pada setiap kereta api dilakukan untuk satu kali perjalanan, 4 terdapat dua jenis kereta api, yaitu MRT Ekonomi dan MRT Ekspres. Ilustrasi perjalanan kereta api dapat dilihat pada Gambar 7. Terdapat tujuh stasiun, yaitu: Lebak Bulus (LB), Fatmawati (FA), Cipete Raya (CR), Haji Nawi (HN), Blok A (BA), Blok M (BM), dan Sisingamangaraja (SI). Stasiun Lebak Bulus memiliki delapan jalur dan stasiun Sisingamangaraja memiliki empat jalur. Kedua stasiun tersebut memiliki depo. Stasiun di antara Lebak Bulus dan Sisingamangaraja beserta enam petak blok yang menghubungkannya hanya memiliki dua jalur. MRT Ekonomi berhenti di setiap

stasiun, sedangkan MRT Ekspres hanya berhenti di stasiun Lebak Bulus, Haji Nawi, dan Sisingamangaraja. Data kecepatan ratarata MRT Ekonomi dan MRT Ekspres pada setiap petak blok antarstasiun diberikan pada Tabel 4 yang dapat dilihat pada Lampiran 2. Kecepatan tersebut diperhitungkan berdasarkan jarak yang harus ditempuh pada setiap petak blok. Himpunan kereta api yang akan dijadwalkan adalah J = {1, 2, ..., 10, 11, ..., 18}, dengan indeks untuk kereta api outbound dari 1 sampai 10 dan kereta api inbound dari 11 sampai 18. Nilai-nilai variabel biner didefinisikan sebagai berikut:

1,   Aijk     0,

jika kereta api outbound i, dengan i  10 menggunakan petak blok k sebelum kereta api outbound j , dengan j  10 lainnya,

1, jika kereta api inbound i, dengan  i  10 menggunakan petak blok k  Bijk   sebelum kereta api inbound j,  dengan j  10  0, lainnya.

d6 d5 d4 d3

d1

d2

Gambar 7 Ilustrasi perjalanan MRT rute Lebak Bulus-Sisingamangaraja.

12

Formulasi secara matematis dari aplikasi model masalah penjadwalan kereta api kasus jalur ganda diberikan pada persamaan dan pertaksamaan (25) sampai (41). Fungsi Objektif Minimumkan Cmaks = ∑

(

−

)+∑

(

−

),

(25)

dengan: = waktu kedatangan kereta i di stasiun Lebak Bulus, dengan i = 1, 2, …, 10. = waktu keberangkatan kereta i dari stasiun Sisingamangaraja untuk kembali ke stasiun Lebak Bulus atau masuk ke dalam depo, dengan i = 1, 2, …, 10. = waktu kedatangan kereta i di stasiun Sisingamangaraja, dengan i = 11, 12, …, 18. = waktu keberangkatan kereta i dari stasiun Lebak Bulus untuk kembali ke stasiun Sisingamangaraja atau masuk ke dalam depo, dengan i = 11, 12, …, 18. Kendala-kendala: X ias  pis   is  X ids , i  10, s  1, 2, ..., 7.

(26)

X ias  pis   is  X ids , i  10, s  7, 6, ..., 1.

(27)

MAijk  X ia ( s 1)  X ja ( s 1)  h,

(28)

i  j; s  1, 2, ..., 6; k  1, 2, ..., 6.

MAijk  X ids  X jds  h,

(29)

i  j; s  1, 2, ..., 6; k  1, 2, ..., 6.

M (1  Aijk )  X ja ( s 1)  X ia ( s 1)  h,

(30)

i  j; s  1, 2, ..., 6; k  1, 2, ..., 6.

M (1  Aijk )  X jds  X ids  h,

(31)

i  j; s  1, 2, ..., 6; k  1, 2, ..., 6.

MBijk  X ias  X jas  h,

(32)

i  j; s  6, 5, ..., 1; k  6, 5, ..., 1. MBijk  X id ( s 1)  X jd ( s 1)  h,

(33)

i  j; s  6, 5, ..., 1; k  6, 5, ..., 1. M (1  Bijk )  X jas  X ias  h,

i  j; s  6, 5, ..., 1; k  6, 5, ..., 1.

(34)

M (1  Bijk )  X jd ( s 1)  X id ( s 1)  h,

(35)

i  j; s  6, 5, ..., 1; k  6, 5, ..., 1. dk d  X ia ( s 1)  X ids  k , vik v ik

(36)

dk d  X ia ( s )  X id ( s 1)  k , vik v ik

(37)

X ias = X ids , dengan i  7, 8, 9, 10 dan

(38)

X ias = X ids , dengan i  16, 17, 18 dan

(39)

h, pis , X ias , X ids  0.

(40)

Aijk , Bijk . bernilai 1 atau 0.

(41)

i  1, 2, ..., 10; k  1, 2, ..., 6; s  1, 2, ..., 6.

i  11, 12, ..., 18; k  6, 5, ..., 1; s  6, 5, ..., 1. s  2, 3, 5, 6. s  6, 5, 3, 2.

Misalkan diberikan waktu kedatangan setiap kereta api di stasiun pertama sebagai nilai awal yang dapat dilihat pada Tabel 5 di Lampiran 2. Waktu headway (h) antarkereta api adalah lima menit. Pertaksamaan (36) dan (37) dapat disubstitusi langsung dengan menggunakan Tabel 4 pada Lampiran 2. Lama waktu pemberhentian (pis) kereta api di setiap stasiun juga diberikan pada Tabel 4 yang dapat dilihat di Lampiran 2. Jadwal kereta api sebelum menggunakan model dapat dilihat pada Gambar 8 dan 9. Gambar tersebut memperlihatkan terjadi banyak konflik di beberapa petak blok, salah satunya pada petak blok di antara stasiun Fatmawati dan Cipete Raya, dengan rute dari Lebak Bulus ke Sisingamangaraja. Terjadi kasus penyusulan oleh MRT Ekspress terhadap MRT Ekonomi pada petak blok tersebut. Konflik yang lainnya pun terjadi akibat melanggar aturan penyusulan dan aturan headway. Berdasarkan data yang ada, model dikonstruksi pada perangkat lunak LINGO 11.0. Kemudian didapat solusi optimal dengan menggunakan algoritme branch and bound. Program dan solusi yang diperoleh dapat dilihat pada Lampiran 3. Nilai fungsi objektif yang didapatkan adalah 1502 menit. Nilai tersebut merupakan jumlah dari total waktu tempuh MRT outbound dan inbound.

13

Representasi dalam diagram ruang-waktu dari solusi yang diperoleh dapat dilihat pada Gambar 10 dan 11. Gambar tersebut memperlihatkan bahwa jadwal yang diperoleh tidak terdapat konflik baik karena melanggar aturan penyusulan maupun headway. Diagram tersebut diubah dalam bentuk tabel yang dapat dilihat pada Tabel 2 dan 3. Ukuran menit dapat diubah dalam bentuk jam, misalkan pada karya ilmiah ini dimulai dari pukul 06.00 WIB. Berdasarkan asumsi pada karya ilmiah ini, bahwa tidak ada prioritas dalam menentukan perjalanan kereta api yang harus ditunda untuk menghindari konflik, solusi jadwal yang dihasilkan menunjukkan MRT Ekspres mengalami penundaan perjalanan di stasiun Haji Nawi selama 11 menit, baik MRT Ekspres jenis inbound maupun outbound. Delay selama 11 menit pada MRT Ekspres bagi sebagian penumpang masih dianggap

terlalu lama. Panjang delay dapat dikurangi dengan menambahkan kendala:

 i 4  c, i  J . Indeks i merupakan indeks MRT Ekspres yaitu {6, 7, 8, 9, 10, 16, 17, 18} dan s = 4 (indeks stasiun Haji Nawi pada simulasi ini). Nilai c merupakan konstanta yang dapat dicari untuk membatasi waktu delay sekecil mungkin. Kendala tersebut mampu membatasi delay sampai batas tertentu. Namun pembatasan ini berimplikasi pada penambahan waktu tempuh maksimum (Cmaks). Jika c = 6, maka Cmaks berubah dari 1502 menit ke 1612 menit. Diagram ruang waktu dengan delay MRT Ekspres menjadi 6 menit ditunjukkan pada Gambar 12 dan 13 yang dapat dilihat di Lampiran 4. Jadwal dalam bentuk tabel diberikan pada Tabel 6 dan 7 yang juga dapat dilihat di Lampiran 4.

14

120

6. MRT Ekonomi

110

5. MRT Ekonomi 4. MRT Ekonomi

100

90

3. MRT Ekonomi

80

2. MRT Ekonomi 10. MRT Ekspres 1. MRT Ekonomi

Waktu (menit)

70

9. MRT Ekspres

60

8. MRT Ekspres

50 7. MRT Ekspres

40

30

20

10

0 LB(a)

LB(d)

FA(a)

Lebak Bulus

Keterangan :

FA(d)

Fatmawati

CR(a)

CR(d)

Cipete Raya

HN(a)

HN(d)

Haji Nawi

BA(a)

BA(d)

Blok A

BM(a)

BM(d)

Blok M

SI(a)

SI(d)

Sisingamangaraja

Konflik

Gambar 8 Diagram ruang waktu dari simulasi penjadwalan MRT dari Lebak Bulus ke Sisingamangaraja yang mengandung konflik.

15

120

110

15. MRT Ekonomi

100

14. MRT Ekonomi

90

13. MRT Ekonomi 12. MRT Ekonomi

80 11. MRT Ekonomi 70 Waktu (menit)

18. MRT Ekspres

60 17. MRT Ekspres

50

16. MRT Ekspres

40

30

20

10

0 SI(a)

SI(d)

Sisingamangaraja

Keterangan :

BM(a) BM(d) Blok M

BA(a)

BA(d)

Blok A

HN(a)

HN(d)

Haji Nawi

CR(a)

CR(d)

Cipete Raya

FA(a)

FA(d)

Fatmawati

LB(a)

LB(d)

Lebak Bulus

Konflik

Gambar 9 Diagram ruang waktu dari simulasi penjadwalan MRT dari Sisingamangaraja ke Lebak Bulus yang mengandung konflik.

16

160 6. MRT Ekonomi

150

140 10. MRT Ekspres 5. MRT Ekonomi

130

4. MRT Ekonomi 120

9. MRT Ekspres

110

8. MRT Ekspres 3. MRT Ekonomi

100

Waktu (menit)

90 7. MRT Ekspres 80

2. MRT Ekonomi 1. MRT Ekonomi

70

60

50

40

30

20

10

0 LB(a)

LB(d)

Lebak Bulus

FA(a)

FA(d)

Fatmawati

CR(a)

CR(d)

Cipete Raya

HN(a)

HN(d)

Haji Nawi

BA(a)

BA(d)

Blok A

BM(a)

BM(d)

Blok M

SI(a)

SI(d)

Sisingamangaraja

Gambar 10 Diagram ruang waktu dari simulasi penjadwalan MRT dari Lebak Bulus ke Sisingamangaraja yang sudah tidak mengandung konflik.

17

15. MRT Ekonomi 140

130 18. MRT Ekspres 14. MRT Ekonomi

120

110 17. MRT Ekspres 13. MRT Ekonomi

100

12. MRT Ekonomi 90

80 Waktu (menit)

16. MRT Ekspres 11. MRT Ekonomi

70

60

50

40

30

20

10

0 SI(a)

SI(d)

Sisingamangaraja

BM(a)

BM(d)

Blok M

BA(a)

BA(d)

Blok A

HN(a)

HN(d)

Haji Nawi

CR(a)

CR(d)

Cipete Raya

FA(a)

FA(d)

Fatmawati

LB(a)

LB(d)

Lebak Bulus

Gambar 11 Diagram ruang waktu dari simulasi penjadwalan MRT dari Sisingamangaraja ke Lebak Bulus yang sudah tidak mengandung konflik.

18

Tabel 2 Simulasi jadwal kedatangan dan keberangkatan MRT dari Lebak Bulus ke Sisingamangaraja (menit ke-) Indeks MRT

Jenis MRT

1

Lebak Bulus

Fatmawati

Cipete Raya

Haji Nawi

Blok A

Blok M

Sisingamangaraja

LB(a)

LB(d)

FA(a)

FA(d)

CR(a)

CR(d)

HN(a)

HN(d)

BA(a)

BA(d)

BM(a)

BM(d)

SI(a)

SI(d)

MRT Ekonomi

5

10

19

20

31

32

40

41

48

49

58

59

70

75

2

MRT Ekonomi

10

15

24

25

36

37

45

46

53

54

63

64

75

80

7

MRT Ekspres

15

31

-

-

-

-

50

62

-

-

-

-

80

85

3

MRT Ekonomi

20

36

45

46

57

58

66

67

74

75

84

85

96

101

8

MRT Ekspres

25

52

-

-

-

-

71

83

-

-

-

-

101

106

9

MRT Ekspres

30

57

-

-

-

-

76

88

-

-

-

-

106

111

4

MRT Ekonomi

35

62

71

72

83

84

92

93

100

101

110

111

122

127

5

MRT Ekonomi

40

67

76

77

88

89

97

98

105

106

115

116

127

132

10

MRT Ekspres

45

83

-

-

-

-

102

114

-

-

-

-

132

137

6

MRT Ekonomi

50

88

97

98

109

110

118

119

126

127

136

137

148

153

Keterangan : “-“ = Tidak berhenti, (a) = Arrival (Kedatangan), (d) = Departure (Keberangkatan). 18

19

Tabel 3 Simulasi jadwal kedatangan dan keberangkatan MRT dari Sisingamangaraja ke Lebak Bulus (menit ke-) Indeks MRT

Jenis MRT

11

Sisingamangaraja

Blok M

Blok A

Haji Nawi

Cipete Raya

Fatmawati

Lebak Bulus

SI(a)

SI(d)

BM(a)

BM(d)

BA(a)

BA(d)

HN(a)

HN(d)

CR(a)

CR(d)

FA(a)

FA(d)

LB(a)

LB(d)

MRT Ekonomi

5

10

21

22

31

32

39

40

48

49

60

61

70

75

16

MRT Ekspres

10

26

-

-

-

-

44

56

-

-

-

-

75

80

12

MRT Ekonomi

15

31

42

43

52

53

60

61

69

70

81

82

91

96

13

MRT Ekonomi

20

36

47

48

57

58

65

66

74

75

86

87

96

101

17

MRT Ekspres

25

52

-

-

-

-

70

82

-

-

-

-

101

106

14

MRT Ekonomi

30

57

68

69

78

79

86

87

95

96

107

108

117

122

18

MRT Ekspres

35

73

-

-

-

-

91

103

-

-

-

-

122

127

15

MRT Ekonomi

40

78

89

90

99

100

107

108

116

117

128

129

138

143

Keterangan : “-“ = Tidak berhenti, (a) = Arrival (Kedatangan), (d) = Departure (Keberangkatan).

19

IV SIMPULAN DAN SARAN 4.1 Simpulan Masalah penjadwalan kereta api merupakan kasus khusus dari masalah penjadwalan job-shop, sehingga model masalah penjadwalan kereta api dapat dibentuk dari konsep model masalah penjadwalan job-shop. Aturan-aturan umum yang berlaku pada masalah penjadwalan jobshop dapat dimodifikasi sesuai aturan-aturan umum yang berlaku pada kasus jalur ganda. Penyelesaian model dengan algoritme branch and bound menghasilkan solusi jadwal kereta api yang optimal, yakni tidak terjadinya konflik antarkereta api. Hal tersebut dibuktikan dengan simulasi yang dilakukan pada rute MRT Lebak Bulus-

Sisingamangaraja menghasilkan jadwal kereta api yang tidak mengandung konflik. Waktu delay akibat akan terjadinya suatu konflik, dapat dikurangi dengan menambahkan kendala yang membatasi nilai delay tersebut. 4.2 Saran Pemodelan dan simulasi penjadwalan kereta api sebaiknya dilakukan untuk perjalanan MRT secara keseluruhan. Selain itu, agar lebih aplikatif sebaiknya dibuat model penjadwalan MRT yang mempertimbangkan kapasitas MRT dalam mengangkut penumpang dan faktor lain yang bersifat aktual.

DAFTAR PUSTAKA D’Ariano A. 2008. Improving real-time train dispatching: models, algorithms and applications [tesis]. Delft: Faculty of Civil Engineering and Geosciences, Delft University of Technology. Higgins A, Kozan E, Ferreira L. 1996. Optimal scheduling of trains on a single line track. Transportation Research 30B (2): 147-161. Liu SQ, Kozan E. 2009. Scheduling trains as a blocking parallel-machine job shop scheduling problem. Computers & Operations Research 36: 2840-2852. Oliveira E, Smith BM. 2000. A job-shop scheduling model for the single-track railway scheduling problem. Technical Report University of Leeds 21: 145-160. Pham DN. 2008. Complex job shop scheduling: formulations, algorithms and a health care application [tesis]. Fribourg: Faculty of Economics and Social Sciences, University of Fribourg.

Shukla A. 2010. Single track train scheduling [tesis]. Bombay: Department of Computer Science and Engineering, Indian Institute of Technology. Taha HA. 1975. Integer Programming: Theory, Applications, and Computations. New York: Academic Press. Taha HA. 1996. Pengantar Riset Operasi. Wirajaya D, penerjemah. Jakarta: Binarupa Aksara. Terjemahan dari: Operations Research. Winston WL. 2004. Operations Research Applications and Algorithms. Ed. ke-4. New York: Duxbury. Yuliawan F. 2008. Implementasi model penjadwalan job-shop dalam masalah penjadwalan kereta api jalur tunggal dengan pendekatan constraint progamming [skripsi]. Bandung: Sekolah Teknik Elektro dan Informatika, Institut Teknologi Bandung.

21

LAMPIRAN

22

Lampiran 1 Syntax Program LINGO 11.0 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch and Bound beserta Hasil yang Diperoleh 1) PL-relaksasi dari ILP (8) Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90; x1>=0;x2>=0; end Hasil yang diperoleh: Global optimal solution found. Objective value:82.50000 Infeasibilities:0.000000 Total solver iterations:2 Variable Value Reduced Cost X1 3.750000 0.000000 X2 2.250000 0.000000 2) Subproblem 2 Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1 ≥ 4 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90; x1>=4; x1>=0;x2>=0; end Hasil yang diperoleh: Global optimal solution found. Objective value: 82.00000 Infeasibilities: 0.000000 Total solver iterations: 3 Variable Value Reduced Cost X1 4.000000 0.000000 X2 1.800000 0.000000

3) Subproblem 3 Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1 ≤ 3 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90; x1<=3; x1>=0; x2>=0; end Hasil yang diperoleh: Global optimal solution found. Objective value: 78.00000 Infeasibilities: 0.000000 Total solver iterations: 1 Variable Value Reduced Cost X1 3.000000 0.000000 X2 3.000000 0.000000 4) Subproblem 4 Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1 ≥ 4 x2 ≥ 2 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90; x1>=4; x2>=2; x1>=0; x2>=0; end

23

Hasil yang diperoleh:

5) Subproblem 5 Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1 ≥ 4 x2 ≤ 1 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90; x1>=4; x2<=1;x1>=0; x2>=0; end Hasil yang diperoleh: Global optimal solution found. Objective value: 81.11111 Infeasibilities: 0.000000 Total solver iterations: 1 Variable Value Reduced Cost X1 4.444444 0.000000 X2 1.000000 0.000000 6) Subproblem 6 Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1 ≥ 4 x2 ≤ 1 x1 ≥ 5 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90;

x1>=4; x2<=1; x1>=5; x1>=0; x2>=0; end Hasil yang diperoleh: Global optimal solution found. Objective value: 80.00000 Infeasibilities: 0.000000 Total solver iterations:0 Variable Value Reduced Cost X1 5.000000 0.000000 X2 0.000000 0.000000 7) Subproblem 7 Maksimumkan z = 16x1 + 10x2 terhadap, 2x1 + 2x2 ≤ 12 18x1 + 10x2 ≤ 90 x1 ≥ 4 x2 ≤ 1 x1 ≤ 4 x1, x2 ≥ 0 Syntax program pada LINGO 11.0: !Fungsi Objektif; max=16*x1+10*x2; !Kendala; 2*x1+2*x2<=12; 18*x1+10*x2<=90; x1>=4; x2<=1; x1<=4; x1>=0; x2>=0; end Hasil yang diperoleh: Global optimal solution found. Objective value: 74.00000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable Value Reduced Cost X1 4.000000 0.000000 X2 1.000000 0.000000

24

Lampiran 2

Data Simulasi Penjadwalan MRT Lebak Bulus-Sisingamangaraja

Tabel 4 Data simulasi dari perjalanan MRT Lebak Bulus-Sisingamangaraja

Indeks stasiun

Stasiun

Indeks Petak Blok (dk)

Jarak antarstasiun (km)

1

Lebak Bulus (LB)

-

2

Fatmawati (FA

3

Kecepatan minimum (km/jam)

Kecepatan maksimum (km/jam)

Waktu tempuh minimum (menit)

Waktu tempuh maksimum (menit)

Waktu tunggu di stasiun (menit)

MRT Eko.

MRT Eks.

MRT Eko.

MRT Eks.

MRT Eko.

MRT Eks.

MRT Eko.

MRT Eks.

MRT Eko.

MRT Eks.

-

-

-

-

-

-

-

-

-

5

3

d1

7.95

43.36

79.50

53.00

119.25

11

6

9

4

1

0

Cipete Raya (CR)

d2

8.25

38.08

61.88

45.00

82.50

13

8

11

6

1

0

4

Haji Nawi (HN)

d3

7.30

43.80

87.60

54.75

146.00

10

5

8

3

1

1

5

Blok A (BA)

d4

5.25

35.00

78.75

45.00

157.50

9

4

7

2

1

0

6

Blok M (BM)

d5

6.70

36.55

67.00

44.67

100.50

11

6

9

4

1

0

7

Sisingamangaraja (SI)

d6

7.25

33.46

54.38

39.55

72.50

13

8

11

6

5

3

Keterangan: Eko. = MRT Ekonomi, Eks. = MRT Ekspres.

24

25

Tabel 5 Waktu kedatangan setiap MRT di stasiun pertama

Indeks MRT

Jenis MRT

Waktu Kedatangan (menit ke-)

1

MRT Ekonomi

5

2

MRT Ekonomi

10

3

MRT Ekonomi

20

4

MRT Ekonomi

35

5

MRT Ekonomi

40

6

MRT Ekonomi

50

7

MRT Ekspres

15

8

MRT Ekspres

25

9

MRT Ekspres

30

10

MRT Ekspres

45

11

MRT Ekonomi

5

12

MRT Ekonomi

15

13

MRT Ekonomi

20

14

MRT Ekonomi

30

15

MRT Ekonomi

40

16

MRT Ekspres

10

17

MRT Ekspres

25

18

MRT Ekspres

35

26

Lampiran 3 Syntax Program LINGO 11.0 untuk Simulasi Penjadwalan MRT Lebak BulusSisingamangaraja beserta Hasil yang Diperoleh model: sets: kereta/1..18/;stasiun/1..7/;petakb lok/1..6/; link1(kereta,stasiun):Xd,Xa,S,D; link2(kereta,kereta,petakblok):A,B ; endsets data: h=5; M=100; S= 5 1 5 1 5 1 5 1 5 1 5 1 3 0 3 0 3 0 3 0 5 1 5 1 5 1 5 1 5 1 3 0 3 0 3 0

1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0

1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0

5 5 5 5 5 5 3 3 3 3 5 5 5 5 5 3 3 3

; enddata !Fungsi Objektif; min=@sum(kereta(i)|i#LE#10:Xd(i,7) Xa(i,1))+@sum(kereta(i)|i#GT#10:Xd (i,7)-Xa(i,1)); !kendala 1: Urutan operasi pada setiap kereta api; !outbound; @for(kereta(i)|i#LE#10:@for(stasiu n(l):Xa(i,l)+S(i,l)+D(i,l)=Xd(i,l) ));

!outbound; @for(kereta(i)|i#LE#10:@for(kereta (j)|j#NE#i#AND#j#LE#10:@for(petakb lok(k):@for(stasiun(l)|l#GE#2:M*A( i,j,k)+Xa(i,l)>Xa(j,l)+h)))); @for(kereta(i)|i#LE#10:@for(kereta (j)|j#NE#i#AND#j#LE#10:@for(petakb lok(k):@for(stasiun(l):M*A(i,j,k)+ Xd(i,l)>Xd(j,l)+h)))); !inbound; @for(kereta(i)|i#GT#10:@for(kereta (j)|j#NE#i#AND#j#GT#10:@for(petakb lok(k):@for(stasiun(l)|l#GE#2:M*B( i,j,k)+Xa(i,l)>Xa(j,l)+h)))); @for(kereta(i)|i#GT#10:@for(kereta (j)|j#NE#i#AND#j#GT#10:@for(petakb lok(k):@for(stasiun(l):M*B(i,j,k)+ Xd(i,l)>Xd(j,l)+h)))); !kereta i mendahului kereta j; !outbound; @for(kereta(i)|i#LE#10:@for(kereta (j)|j#NE#i#AND#j#LE#10:@for(petakb lok(k):@for(stasiun(l)|l#GE#2:M*(1 -A(i,j,k))+Xa(j,l)>Xa(i,l)+h)))); @for(kereta(i)|i#LE#10:@for(kereta (j)|j#NE#i#AND#j#LE#10:@for(petakb lok(k):@for(stasiun(l):M*(1A(i,j,k))+Xd(j,l)>Xd(i,l)+h)))); !inbound; @for(kereta(i)|i#GT#10:@for(kereta (j)|j#NE#i#AND#j#GT#10:@for(petakb lok(k):@for(stasiun(l)|l#GE#2:M*(1 -B(i,j,k))+Xa(j,l)>Xa(i,l)+h)))); @for(kereta(i)|i#GT#10:@for(kereta (j)|j#NE#i#AND#j#GT#10:@for(petakb lok(k):@for(stasiun(l):M*(1B(i,j,k))+Xd(j,l)>Xd(i,l)+h)))); !kendala 3: Rata-rata kecepatan setiap kereta api untuk menempuh masing-masing petak blok; !outbound; @for(kereta(i)|i#LE#6:9<(Xa(i,2)Xd(i,1))); @for(kereta(i)|i#LE#6:(Xa(i,2)Xd(i,1))<11);

!inbound; @for(kereta(i)|i#GT#10:@for(stasiu n(l):Xa(i,l)+S(i,l) +D(i,l)=Xd(i,l)));

@for(kereta(i)|i#LE#6:11<(Xa(i,3)Xd(i,2))); @for(kereta(i)|i#LE#6:(Xa(i,3)Xd(i,2))<13);

!Kendala 2: Aturan penyusulan;

@for(kereta(i)|i#LE#6:8<(Xa(i,4)Xd(i,3)));

!kereta j mendahului kereta i;

27

@for(kereta(i)|i#LE#6:(Xa(i,4)Xd(i,3))<10); @for(kereta(i)|i#LE#6:7<(Xa(i,5)Xd(i,4))); @for(kereta(i)|i#LE#6:(Xa(i,5)Xd(i,4))<9); @for(kereta(i)|i#LE#6:9<(Xa(i,6)Xd(i,5))); @for(kereta(i)|i#LE#6:(Xa(i,6)Xd(i,5))<11); @for(kereta(i)|i#LE#6:11<(Xa(i,7)Xd(i,6))); @for(kereta(i)|i#LE#6:(Xa(i,7)Xd(i,6))<13); @for(kereta(i)|i#LE#10#AND#i#GT#6: 4<(Xa(i,2)-Xd(i,1))); @for(kereta(i)|i#LE#10#AND#i#GT#6: (Xa(i,2)-Xd(i,1))<6); @for(kereta(i)|i#LE#10#AND#i#GT#6: 6<(Xa(i,3)-Xd(i,2))); @for(kereta(i)|i#LE#10#AND#i#GT#6: (Xa(i,3)-Xd(i,2))<8); @for(kereta(i)|i#LE#10#AND#i#GT#6: 3<(Xa(i,4)-Xd(i,3))); @for(kereta(i)|i#LE#10#AND#i#GT#6: (Xa(i,4)-Xd(i,3))<5); @for(kereta(i)|i#LE#10#AND#i#GT#6: 2<(Xa(i,5)-Xd(i,4))); @for(kereta(i)|i#LE#10#AND#i#GT#6: (Xa(i,5)-Xd(i,4))<4); @for(kereta(i)|i#LE#10#AND#i#GT#6: 4<(Xa(i,6)-Xd(i,5))); @for(kereta(i)|i#LE#10#AND#i#GT#6: (Xa(i,6)-Xd(i,5))<6);

@for(kereta(i)|i#GT#10#AND#i#LE#15 :(Xa(i,2)-Xd(i,1))<13); @for(kereta(i)|i#GT#10#AND#i#LE#15 :(Xa(i,3)-Xd(i,2))<11); @for(kereta(i)|i#GT#10#AND#i#LE#15 :(Xa(i,4)-Xd(i,3))<9); @for(kereta(i)|i#GT#10#AND#i#LE#15 :(Xa(i,5)-Xd(i,4))<10); @for(kereta(i)|i#GT#10#AND#i#LE#15 :(Xa(i,6)-Xd(i,5))<13); @for(kereta(i)|i#GT#10#AND#i#LE#15 :(Xa(i,7)-Xd(i,6))<11); @for(kereta(i)|i#LE#18#AND#i#GT#15 :6<(Xa(i,2)-Xd(i,1))); @for(kereta(i)|i#LE#18#AND#i#GT#15 :4<(Xa(i,3)-Xd(i,2))); @for(kereta(i)|i#LE#18#AND#i#GT#15 :2<(Xa(i,4)-Xd(i,3))); @for(kereta(i)|i#LE#18#AND#i#GT#15 :3<(Xa(i,5)-Xd(i,4))); @for(kereta(i)|i#LE#18#AND#i#GT#15 :6<(Xa(i,6)-Xd(i,5))); @for(kereta(i)|i#LE#18#AND#i#GT#15 :4<(Xa(i,7)-Xd(i,6))); @for(kereta(i)|i#LE#18#AND#i#GT#15 :(Xa(i,2)-Xd(i,1))<8); @for(kereta(i)|i#LE#18#AND#i#GT#15 :(Xa(i,3)-Xd(i,2))<6); @for(kereta(i)|i#LE#18#AND#i#GT#15 :(Xa(i,4)-Xd(i,3))<4); @for(kereta(i)|i#LE#18#AND#i#GT#15 :(Xa(i,5)-Xd(i,4))<5); @for(kereta(i)|i#LE#18#AND#i#GT#15 :(Xa(i,6)-Xd(i,5))<8); @for(kereta(i)|i#LE#18#AND#i#GT#15 :(Xa(i,7)-Xd(i,6))<6); !Waktu kedatangan masing-masing kereta di stasiun pertama;

@for(kereta(i)|i#LE#10#AND#i#GT#6: 6<(Xa(i,7)-Xd(i,6))); @for(kereta(i)|i#LE#10#AND#i#GT#6: (Xa(i,7)-Xd(i,6))<8);

!outbound; Xa(1,1)=5;Xa(2,1)=10;Xa(3,1)=20;Xa (4,1)=35;Xa(5,1)=40;Xa(6,1)=50; Xa(7,1)=15;Xa(8,1)=25;Xa(9,1)=30;X a(10,1)=45;

!inbound; @for(kereta(i)|i#GT#10#AND#i#LE#15 :11<(Xa(i,2)-Xd(i,1))); @for(kereta(i)|i#GT#10#AND#i#LE#15 :9<(Xa(i,3)-Xd(i,2))); @for(kereta(i)|i#GT#10#AND#i#LE#15 :7<(Xa(i,4)-Xd(i,3))); @for(kereta(i)|i#GT#10#AND#i#LE#15 :8<(Xa(i,5)-Xd(i,4))); @for(kereta(i)|i#GT#10#AND#i#LE#15 :11<(Xa(i,6)-Xd(i,5))); @for(kereta(i)|i#GT#10#AND#i#LE#15 :9<(Xa(i,7)-Xd(i,6)));

!inbound; Xa(11,1)=5;Xa(12,1)=15;Xa(13,1)=20 ;Xa(14,1)=30;Xa(15,1)=40; Xa(16,1)=10;Xa(17,1)=25;Xa(18,1)=3 5; ! Kendala 4: Pemberhentian Ekspress; ! Outbound; Xa(7,2)=Xd(7,2); Xa(7,3)=Xd(7,3); Xa(7,5)=Xd(7,5); Xa(7,6)=Xd(7,6);

28

Xa(8,2)=Xd(8,2); Xa(8,3)=Xd(8,3); Xa(8,5)=Xd(8,5); Xa(8,6)=Xd(8,6); Xa(9,2)=Xd(9,2); Xa(9,3)=Xd(9,3); Xa(9,5)=Xd(9,5); Xa(9,6)=Xd(9,6); Xa(10,2)=Xd(10,2); Xa(10,3)=Xd(10,3); Xa(10,5)=Xd(10,5); Xa(10,6)=Xd(10,6); !inbound; Xa(16,2)=Xd(16,2); Xa(16,3)=Xd(16,3); Xa(16,5)=Xd(16,5); Xa(16,6)=Xd(16,6); Xa(17,2)=Xd(17,2); Xa(17,3)=Xd(17,3); Xa(17,5)=Xd(17,5); Xa(17,6)=Xd(17,6); Xa(18,2)=Xd(18,2); Xa(18,3)=Xd(18,3); Xa(18,5)=Xd(18,5); Xa(18,6)=Xd(18,6); !Kendala 5: nilai biner untuk A dan B; @for(kereta(i)|i#LE#10:@for(kereta (j)|j#LE#10:@for(petakblok(k):@bin (A(i,j,k))))); @for(kereta(i)|i#GT#10:@for(kereta (j)|j#GT#10:@for(petakblok(k):@bin (B(i,j,k))))); !Outbound; A(1,2,1)=1; A(1,3,1)=1; A(1,4,1)=1; A(1,5,1)=1; A(1,6,1)=1; A(1,7,1)=1; A(1,8,1)=1; A(1,9,1)=1; A(1,10,1)=1; A(2,3,1)=1; A(2,4,1)=1; A(2,5,1)=1; A(2,6,1)=1; A(2,7,1)=1; A(2,8,1)=1; A(2,9,1)=1; A(2,10,1)=1; A(7,3,1)=1; A(7,4,1)=1; A(7,5,1)=1; A(7,6,1)=1;

A(7,8,1)=1; A(7,9,1)=1; A(7,10,1)=1; A(3,4,1)=1; A(3,5,1)=1; A(3,6,1)=1; A(3,8,1)=1; A(3,9,1)=1; A(3,10,1)=1; A(8,4,1)=1; A(8,5,1)=1; A(8,6,1)=1; A(8,9,1)=1; A(8,10,1)=1; A(9,4,1)=1; A(9,5,1)=1; A(9,6,1)=1; A(9,10,1)=1; A(4,5,1)=1; A(4,6,1)=1; A(4,10,1)=1; A(5,6,1)=1; A(5,10,1)=1; A(10,6,1)=1; !inbound; B(11,12,1)=1; B(11,13,1)=1; B(11,14,1)=1; B(11,15,1)=1; B(11,16,1)=1; B(11,17,1)=1; B(11,18,1)=1; B(16,12,1)=1; B(16,13,1)=1; B(16,14,1)=1; B(16,15,1)=1; B(16,17,1)=1; B(16,18,1)=1; B(12,13,1)=1; B(12,14,1)=1; B(12,15,1)=1; B(12,17,1)=1; B(12,18,1)=1; B(13,14,1)=1; B(13,15,1)=1; B(13,17,1)=1; B(13,18,1)=1; B(17,14,1)=1; B(17,15,1)=1; B(17,18,1)=1; B(14,15,1)=1; B(14,18,1)=1; B(18,15,1)=1; end

29

30

Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable H M XD( 1, 1) XD( 1, 2) XD( 1, 3) XD( 1, 4) XD( 1, 5) XD( 1, 6) XD( 1, 7) XD( 2, 1) XD( 2, 2) XD( 2, 3) XD( 2, 4) XD( 2, 5) XD( 2, 6) XD( 2, 7) XD( 3, 1) XD( 3, 2) XD( 3, 3) XD( 3, 4) XD( 3, 5) XD( 3, 6) XD( 3, 7) XD( 4, 1) XD( 4, 2) XD( 4, 3) XD( 4, 4) XD( 4, 5) XD( 4, 6) XD( 4, 7) XD( 5, 1) XD( 5, 2) XD( 5, 3) XD( 5, 4) XD( 5, 5) XD( 5, 6) XD( 5, 7) XD( 6, 1) XD( 6, 2) XD( 6, 3) XD( 6, 4) XD( 6, 5) XD( 6, 6) XD( 6, 7) XD( 7, 1) XD( 7, 2) XD( 7, 3) XD( 7, 4) XD( 7, 5) XD( 7, 6) XD( 7, 7) XD( 8, 1) XD( 8, 2) XD( 8, 3) XD( 8, 4) XD( 8, 5) XD( 8, 6) XD( 8, 7) XD( 9, 1) XD( 9, 2) XD( 9, 3) XD( 9, 4) XD( 9, 5) XD( 9, 6)

1502.000 1502.000 0.000000 0 1303

Value 5.000000 100.0000 10.00000 20.00000 32.00000 41.00000 49.00000 59.00000 75.00000 15.00000 25.00000 37.00000 46.00000 54.00000 64.00000 80.00000 36.00000 46.00000 58.00000 67.00000 75.00000 85.00000 101.0000 62.00000 72.00000 84.00000 93.00000 101.0000 111.0000 127.0000 67.00000 77.00000 89.00000 98.00000 106.0000 116.0000 132.0000 88.00000 98.00000 110.0000 119.0000 127.0000 137.0000 153.0000 31.00000 37.00000 45.00000 62.00000 66.00000 72.00000 85.00000 52.00000 58.00000 66.00000 83.00000 87.00000 93.00000 106.0000 57.00000 63.00000 71.00000 88.00000 92.00000 98.00000

Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

XD( 9, 7) XD( 10, 1) XD( 10, 2) XD( 10, 3) XD( 10, 4) XD( 10, 5) XD( 10, 6) XD( 10, 7) XD( 11, 1) XD( 11, 2) XD( 11, 3) XD( 11, 4) XD( 11, 5) XD( 11, 6) XD( 11, 7) XD( 12, 1) XD( 12, 2) XD( 12, 3) XD( 12, 4) XD( 12, 5) XD( 12, 6) XD( 12, 7) XD( 13, 1) XD( 13, 2) XD( 13, 3) XD( 13, 4) XD( 13, 5) XD( 13, 6) XD( 13, 7) XD( 14, 1) XD( 14, 2) XD( 14, 3) XD( 14, 4) XD( 14, 5) XD( 14, 6) XD( 14, 7) XD( 15, 1) XD( 15, 2) XD( 15, 3) XD( 15, 4) XD( 15, 5) XD( 15, 6) XD( 15, 7) XD( 16, 1) XD( 16, 2) XD( 16, 3) XD( 16, 4) XD( 16, 5) XD( 16, 6) XD( 16, 7) XD( 17, 1) XD( 17, 2) XD( 17, 3) XD( 17, 4) XD( 17, 5) XD( 17, 6) XD( 17, 7) XD( 18, 1) XD( 18, 2) XD( 18, 3) XD( 18, 4) XD( 18, 5) XD( 18, 6) XD( 18, 7) XA( 1, 1) XA( 1, 2) XA( 1, 3) XA( 1, 4) XA( 1, 5) XA( 1, 6) XA( 1, 7) XA( 2, 1) XA( 2, 2)

111.0000 83.00000 89.00000 97.00000 114.0000 118.0000 124.0000 137.0000 10.00000 22.00000 32.00000 40.00000 49.00000 61.00000 75.00000 31.00000 43.00000 53.00000 61.00000 70.00000 82.00000 96.00000 36.00000 48.00000 58.00000 66.00000 75.00000 87.00000 101.0000 57.00000 69.00000 79.00000 87.00000 96.00000 108.0000 122.0000 78.00000 90.00000 100.0000 108.0000 117.0000 129.0000 143.0000 26.00000 34.00000 40.00000 56.00000 61.00000 69.00000 80.00000 52.00000 60.00000 66.00000 82.00000 87.00000 95.00000 106.0000 73.00000 81.00000 87.00000 103.0000 108.0000 116.0000 127.0000 5.000000 19.00000 31.00000 40.00000 48.00000 58.00000 70.00000 10.00000 24.00000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

31

XA( 2, 3) XA( 2, 4) XA( 2, 5) XA( 2, 6) XA( 2, 7) XA( 3, 1) XA( 3, 2) XA( 3, 3) XA( 3, 4) XA( 3, 5) XA( 3, 6) XA( 3, 7) XA( 4, 1) XA( 4, 2) XA( 4, 3) XA( 4, 4) XA( 4, 5) XA( 4, 6) XA( 4, 7) XA( 5, 1) XA( 5, 2) XA( 5, 3) XA( 5, 4) XA( 5, 5) XA( 5, 6) XA( 5, 7) XA( 6, 1) XA( 6, 2) XA( 6, 3) XA( 6, 4) XA( 6, 5) XA( 6, 6) XA( 6, 7) XA( 7, 1) XA( 7, 2) XA( 7, 3) XA( 7, 4) XA( 7, 5) XA( 7, 6) XA( 7, 7) XA( 8, 1) XA( 8, 2) XA( 8, 3) XA( 8, 4) XA( 8, 5) XA( 8, 6) XA( 8, 7) XA( 9, 1) XA( 9, 2) XA( 9, 3) XA( 9, 4) XA( 9, 5) XA( 9, 6) XA( 9, 7) XA( 10, 1) XA( 10, 2) XA( 10, 3) XA( 10, 4) XA( 10, 5) XA( 10, 6) XA( 10, 7) XA( 11, 1) XA( 11, 2) XA( 11, 3) XA( 11, 4) XA( 11, 5) XA( 11, 6) XA( 11, 7) XA( 12, 1) XA( 12, 2) XA( 12, 3) XA( 12, 4) XA( 12, 5)

36.00000 45.00000 53.00000 63.00000 75.00000 20.00000 45.00000 57.00000 66.00000 74.00000 84.00000 96.00000 35.00000 71.00000 83.00000 92.00000 100.0000 110.0000 122.0000 40.00000 76.00000 88.00000 97.00000 105.0000 115.0000 127.0000 50.00000 97.00000 109.0000 118.0000 126.0000 136.0000 148.0000 15.00000 37.00000 45.00000 50.00000 66.00000 72.00000 80.00000 25.00000 58.00000 66.00000 71.00000 87.00000 93.00000 101.0000 30.00000 63.00000 71.00000 76.00000 92.00000 98.00000 106.0000 45.00000 89.00000 97.00000 102.0000 118.0000 124.0000 132.0000 5.000000 21.00000 31.00000 39.00000 48.00000 60.00000 70.00000 15.00000 42.00000 52.00000 60.00000 69.00000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

XA( 12, 6) XA( 12, 7) XA( 13, 1) XA( 13, 2) XA( 13, 3) XA( 13, 4) XA( 13, 5) XA( 13, 6) XA( 13, 7) XA( 14, 1) XA( 14, 2) XA( 14, 3) XA( 14, 4) XA( 14, 5) XA( 14, 6) XA( 14, 7) XA( 15, 1) XA( 15, 2) XA( 15, 3) XA( 15, 4) XA( 15, 5) XA( 15, 6) XA( 15, 7) XA( 16, 1) XA( 16, 2) XA( 16, 3) XA( 16, 4) XA( 16, 5) XA( 16, 6) XA( 16, 7) XA( 17, 1) XA( 17, 2) XA( 17, 3) XA( 17, 4) XA( 17, 5) XA( 17, 6) XA( 17, 7) XA( 18, 1) XA( 18, 2) XA( 18, 3) XA( 18, 4) XA( 18, 5) XA( 18, 6) XA( 18, 7) S( 1, 1) S( 1, 2) S( 1, 3) S( 1, 4) S( 1, 5) S( 1, 6) S( 1, 7) S( 2, 1) S( 2, 2) S( 2, 3) S( 2, 4) S( 2, 5) S( 2, 6) S( 2, 7) S( 3, 1) S( 3, 2) S( 3, 3) S( 3, 4) S( 3, 5) S( 3, 6) S( 3, 7) S( 4, 1) S( 4, 2) S( 4, 3) S( 4, 4) S( 4, 5) S( 4, 6) S( 4, 7) S( 5, 1)

81.00000 91.00000 20.00000 47.00000 57.00000 65.00000 74.00000 86.00000 96.00000 30.00000 68.00000 78.00000 86.00000 95.00000 107.0000 117.0000 40.00000 89.00000 99.00000 107.0000 116.0000 128.0000 138.0000 10.00000 34.00000 40.00000 44.00000 61.00000 69.00000 75.00000 25.00000 60.00000 66.00000 70.00000 87.00000 95.00000 101.0000 35.00000 81.00000 87.00000 91.00000 108.0000 116.0000 122.0000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

32

S( 5, 2) S( 5, 3) S( 5, 4) S( 5, 5) S( 5, 6) S( 5, 7) S( 6, 1) S( 6, 2) S( 6, 3) S( 6, 4) S( 6, 5) S( 6, 6) S( 6, 7) S( 7, 1) S( 7, 2) S( 7, 3) S( 7, 4) S( 7, 5) S( 7, 6) S( 7, 7) S( 8, 1) S( 8, 2) S( 8, 3) S( 8, 4) S( 8, 5) S( 8, 6) S( 8, 7) S( 9, 1) S( 9, 2) S( 9, 3) S( 9, 4) S( 9, 5) S( 9, 6) S( 9, 7) S( 10, 1) S( 10, 2) S( 10, 3) S( 10, 4) S( 10, 5) S( 10, 6) S( 10, 7) S( 11, 1) S( 11, 2) S( 11, 3) S( 11, 4) S( 11, 5) S( 11, 6) S( 11, 7) S( 12, 1) S( 12, 2) S( 12, 3) S( 12, 4) S( 12, 5) S( 12, 6) S( 12, 7) S( 13, 1) S( 13, 2) S( 13, 3) S( 13, 4) S( 13, 5) S( 13, 6) S( 13, 7) S( 14, 1) S( 14, 2) S( 14, 3) S( 14, 4) S( 14, 5) S( 14, 6) S( 14, 7) S( 15, 1) S( 15, 2) S( 15, 3) S( 15, 4)

1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000 1.000000 1.000000 5.000000 5.000000 1.000000 1.000000 1.000000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

S( 15, 5) S( 15, 6) S( 15, 7) S( 16, 1) S( 16, 2) S( 16, 3) S( 16, 4) S( 16, 5) S( 16, 6) S( 16, 7) S( 17, 1) S( 17, 2) S( 17, 3) S( 17, 4) S( 17, 5) S( 17, 6) S( 17, 7) S( 18, 1) S( 18, 2) S( 18, 3) S( 18, 4) S( 18, 5) S( 18, 6) S( 18, 7) D( 1, 1) D( 1, 2) D( 1, 3) D( 1, 4) D( 1, 5) D( 1, 6) D( 1, 7) D( 2, 1) D( 2, 2) D( 2, 3) D( 2, 4) D( 2, 5) D( 2, 6) D( 2, 7) D( 3, 1) D( 3, 2) D( 3, 3) D( 3, 4) D( 3, 5) D( 3, 6) D( 3, 7) D( 4, 1) D( 4, 2) D( 4, 3) D( 4, 4) D( 4, 5) D( 4, 6) D( 4, 7) D( 5, 1) D( 5, 2) D( 5, 3) D( 5, 4) D( 5, 5) D( 5, 6) D( 5, 7) D( 6, 1) D( 6, 2) D( 6, 3) D( 6, 4) D( 6, 5) D( 6, 6) D( 6, 7) D( 7, 1) D( 7, 2) D( 7, 3) D( 7, 4) D( 7, 5) D( 7, 6) D( 7, 7)

1.000000 1.000000 5.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 3.000000 0.000000 0.000000 1.000000 0.000000 0.000000 3.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 11.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 22.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 22.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 33.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 13.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 10.00000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 9.000000 9.000000 5.000000 5.000000 5.000000 2.000000 0.000000 4.000000 4.000000 0.000000 3.000000 3.000000 3.000000 0.000000 4.000000 4.000000 4.000000 4.000000 4.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

33

D( 8, 1) D( 8, 2) D( 8, 3) D( 8, 4) D( 8, 5) D( 8, 6) D( 8, 7) D( 9, 1) D( 9, 2) D( 9, 3) D( 9, 4) D( 9, 5) D( 9, 6) D( 9, 7) D( 10, 1) D( 10, 2) D( 10, 3) D( 10, 4) D( 10, 5) D( 10, 6) D( 10, 7) D( 11, 1) D( 11, 2) D( 11, 3) D( 11, 4) D( 11, 5) D( 11, 6) D( 11, 7) D( 12, 1) D( 12, 2) D( 12, 3) D( 12, 4) D( 12, 5) D( 12, 6) D( 12, 7) D( 13, 1) D( 13, 2) D( 13, 3) D( 13, 4) D( 13, 5) D( 13, 6) D( 13, 7) D( 14, 1) D( 14, 2) D( 14, 3) D( 14, 4)

24.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000 24.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000 35.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 11.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 11.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 22.00000 0.000000 0.000000 0.000000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 8.000000 8.000000 8.000000 2.000000 2.000000 2.000000 2.000000 0.000000 6.000000 6.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 5.000000 5.000000 5.000000 2.000000 0.000000 0.000000 0.000000 0.000000

D( 14, 5) D( 14, 6) D( 14, 7) D( 15, 1) D( 15, 2) D( 15, 3) D( 15, 4) D( 15, 5) D( 15, 6) D( 15, 7) D( 16, 1) D( 16, 2) D( 16, 3) D( 16, 4) D( 16, 5) D( 16, 6) D( 16, 7) D( 17, 1) D( 17, 2) D( 17, 3) D( 17, 4) D( 17, 5) D( 17, 6) D( 17, 7) D( 18, 1) D( 18, 2) D( 18, 3) D( 18, 4) D( 18, 5) D( 18, 6) D( 18, 7) A( 1, 1, 1) . . . A( 18, 18, 6) B( 1, 1, 1)

0.000000 0.000000 0.000000 33.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 13.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000 24.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000 35.00000 0.000000 0.000000 11.00000 0.000000 0.000000 2.000000 0.000000

3.000000 3.000000 2.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

0.000000 0.000000

0.000000 0.000000

0.000000

0.000000

. . . B( 18, 18, 6)

34

Lampiran 4 Hasil Simulasi Penjadwalan MRT dengan Nilai Delay MRT Ekspres Dibatasi 180 170

6. MRT Ekonomi*

160 150

10. MRT Ekspres* 5. MRT Ekonomi*

140

4. MRT Ekonomi*

130 120 9. MRT Ekspres* 8. MRT Ekspres*

110

Waktu (menit)

3. MRT Ekonomi* 100 90 7. MRT Ekspres* 80

2. MRT Ekonomi* 1. MRT Ekonomi*

70 60 50 40 30 20 10 0 LB(a)

LB(d)

Lebak Bulus

FA(a)

FA(d)

Fatmawati

CR(a)

CR(d)

Cipete Raya

HN(a)

HN(d)

Haji Nawi

BA(a)

BA(d)

Blok A

BM(a) BM(d) Blok M

SI(a)

SI(d)

Sisingamangaraja

Gambar 12 Diagram ruang waktu dari simulasi penjadwalan MRT dari Lebak Bulus ke Sisingamangaraja dengan waktu delay MRT Ekspres menjadi 6 menit.

35

160

15. MRT Ekonomi*

150

140 18. MRT Ekspres* 14. MRT Ekonomi*

130

120

17. MRT Ekspres*

110

13. MRT Ekonomi* 12. MRT Ekonomi*

100

Waktu (menit)

90

80

16. MRT Ekspres* 11. MRT Ekonomi*

70

60

50

40

30

20

10

0 SI(a)

SI(d)

Sisingamangaraja

BM(a)

BM(d)

Blok M

BA(a)

BA(d)

Blok A

HN(a)

HN(d)

Haji Nawi

CR(a)

CR(d)

Cipete Raya

FA(a)

FA(d)

Fatmawati

LB(a)

LB(d)

Lebak Bulus

Gambar 13 Diagram ruang waktu dari simulasi penjadwalan MRT dari Sisingamangaraja ke Lebak Bulus dengan waktu delay MRT Ekspres menjadi 6 menit.

36

Tabel 6 Simulasi jadwal kedatangan dan keberangkatan MRT dari Lebak Bulus ke Sisingamangaraja dengan waktu delay MRT Ekspress 6 menit (menit ke-) Indeks MRT

Jenis MRT

1

Lebak Bulus

Fatmawati

Cipete Raya

Haji Nawi

Blok A

Blok M

Sisingamangaraja

LB(a)

LB(d)

FA(a)

FA(d)

CR(a)

CR(d)

HN(a)

HN(d)

BA(a)

BA(d)

BM(a)

BM(d)

SI(a)

SI(d)

MRT Ekonomi

5

10

19

20

31

32

40

41

48

49

58

59

70

75

2

MRT Ekonomi

10

15

24

25

36

37

45

46

53

54

63

64

75

80

7

MRT Ekspres

15

36

-

-

-

-

55

62

-

-

-

-

80

85

3

MRT Ekonomi

20

41

50

51

62

63

71

72

79

80

89

90

101

106

8

MRT Ekspres

25

62

-

-

-

-

81

88

-

-

-

-

106

111

9

MRT Ekspres

30

67

-

-

-

-

86

93

-

-

-

-

111

116

4

MRT Ekonomi

35

72

81

82

93

94

102

103

110

111

120

121

132

137

5

MRT Ekonomi

40

77

86

87

98

99

107

108

115

116

125

126

137

142

10

MRT Ekspres

45

98

-

-

-

-

117

124

-

-

-

-

142

147

6

MRT Ekonomi

50

103

112

113

124

125

133

134

141

142

151

152

163

168

Keterangan : “-“ = Tidak berhenti, (a) = Arrival (Kedatangan), (d) = Departure (Keberangkatan). 36

37

Tabel 7 Simulasi jadwal kedatangan dan keberangkatan MRT dari Sisingamangaraja ke Lebak Bulus dengan waktu delay MRT Ekspress 6 menit (menit ke-) Indeks MRT

Jenis MRT

11

Sisingamangaraja

Blok M

Blok A

Haji Nawi

Cipete Raya

Fatmawati

Lebak Bulus

SI(a)

SI(d)

BM(a)

BM(d)

BA(a)

BA(d)

HN(a)

HN(d)

CR(a)

CR(d)

FA(a)

FA(d)

LB(a)

LB(d)

MRT Ekonomi

5

10

21

22

31

32

39

40

48

49

60

61

70

75

16

MRT Ekspres

10

31

-

-

-

-

49

56

-

-

-

-

75

80

12

MRT Ekonomi

15

36

47

48

57

58

65

66

74

75

86

87

96

101

13

MRT Ekonomi

20

41

52

53

62

63

70

71

79

80

91

92

101

106

17

MRT Ekspres

25

62

-

-

-

-

80

87

-

-

-

-

106

111

14

MRT Ekonomi

30

67

78

79

88

89

96

97

105

106

117

118

127

132

18

MRT Ekspres

35

88

-

-

-

-

106

113

-

-

-

-

132

137

15

MRT Ekonomi

40

93

104

105

114

115

122

123

131

132

143

144

153

158

Keterangan : “-“ = Tidak berhenti, (a) = Arrival (Kedatangan), (d) = Departure (Keberangkatan).

37

38