I-1

BAB I PENDAHULUAN

Pada bab pertama ini akan diuraikan mengenai latar belakang, rumusan masalah,

tujuan, batasan masalah, metodologi, dan sistematika pembahasan dalam Tugas

Akhir ini.

1.1 Latar Belakang

Kereta api merupakan salah satu alat transportasi utama di seluruh dunia. Di

Indonesia dan banyak negara lain, kereta api menggunakan jalur tunggal, artinya

satu jalur kereta api digunakan untuk dua arah yang berbeda. Karena terdapat

banyak kereta api yang menggunakan jalur atau rute yang sama, penjadwalan

kereta api menjadi satu hal yang mutlak diperlukan. Namun pembuatan jadwal

kereta api bukanlah masalah yang mudah. Terdapat banyak aturan atau batasan

(constraints) yang harus dipenuhi, misalnya aturan penyusulan (overtaking rule),

aturan persilangan (crossing rule), aturan headway, kecepatan maksimal yang

diperbolehkan di suatu jalur, dan sebagainya [SUP01]. Selain batasan-batasan

tersebut, besarnya data yang harus diproses (banyaknya kereta api dan banyaknya

jalur atau rute yang harus ditempuh) juga menjadi masalah dalam penjadwalan

kereta api jalur tunggal.

Perkembangan teknologi informasi saat ini memungkinkan penyelesaian masalah

penjadwalan kereta api jalur tunggal. Ada beberapa pendekatan yang telah

dilakukan untuk menyelesaikan masalah penjadwalan kereta api jalur tunggal,

misalnya pendekatan Mathematical Programming dan Constraint Programming

[OLI01]. Dalam Tugas Akhir ini, pendekatan yang digunakan adalah yang kedua.

Pendekatan ini digunakan karena dapat menangani berbagai macam aturan atau

batasan yang ada dalam masalah penjadwalan kereta api jalur tunggal.

Constraint Programming adalah metode penyelesaian masalah yang terdiri atas

dua langkah, yaitu modelling dan resolution [MON01]. Modelling dilakukan

dengan cara merepresentasikan masalah yang diberikan sebagai sebuah Constraint

Satisfaction Problem (CSP). Dalam CSP terdapat tiga komponen utama, yaitu

I-2

variabel, domain dan batasan. Solusi yang ingin dicari pada masalah yang

diberikan dimodelkan sebagai variabel, himpunan nilai yang mungkin pada solusi

dimodelkan sebagai domain dari variabel dan hubungan yang harus dipenuhi

antara variabel-variabel dimodelkan sebagai batasan CSP [STU03]. Selanjutnya,

proses pencarian solusi CSP dilakukan pada langkah resolution dengan

menggunakan constraint solver.

Dalam masalah penjadwalan kereta api jalur tunggal, salah satu CSP yang dapat

digunakan untuk pemodelan adalah masalah penjadwalan Job-Shop. Pemodelan

dilakukan dengan menganggap perjalanan-perjalanan kereta api sebagai

sekumpulan pekerjaan (jobs) yang dijadwalkan pada sekumpulan sumber daya

(resources) berupa petak-petak blok atau segmen-segmen jalur kereta api

[OLI00]. Sebuah pekerjaan terdiri atas beberapa operasi yang harus dikerjakan

secara berturutan, dimana sebuah operasi adalah bagian perjalanan kereta api

melewati satu petak blok. Antara petak blok satu dengan yang lain dipisahkan

oleh sebuah stasiun atau sinyal. Sebuah contoh model tersebut dapat dilihat pada

Gambar I-1.

Gambar I-1 Contoh Rute Perjalanan Kereta Api

Pada contoh model di atas, pekerjaan yang harus dilakukan adalah sebuah

perjalanan kereta api, misalnya dari stasiun S1 ke stasiun S3. Dalam hal ini,

sumber daya yang digunakan adalah petak blok T1, T2, T3, T4 dan T5. Sebuah

operasi adalah sebuah bagian perjalanan melewati satu petak blok saja. Jadi pada

I-3

contoh di atas, perjalanan dari stasiun S1 ke stasiun S3 dapat dipandang sebagai

kumpulan lima buah operasi yang dikerjakan secara berturutan. Operasi pertama

adalah perjalanan melewati petak blok T1, operasi kedua adalah perjalanan

melalui petak blok T2 dan seterusnya.

Solusi yang ingin dicari pada masalah penjadwalan Job-Shop adalah jadwal atau

waktu pelepasan (release time) setiap operasi pada setiap pekerjaan, yaitu waktu

operasi tersebut mulai dikerjakan. Hal ini sama juga dengan waktu penggunaan

sumber daya. Dengan demikian, dalam representasi CSP, variabel pada masalah

penjadwalan Job-Shop adalah waktu pelepasan operasi-operasi tersebut,

domainnya adalah himpunan waktu (detik, menit atau jam), dan batasannya

adalah sebuah sumber daya tidak boleh digunakan oleh dua operasi yang berbeda

pada waktu yang sama. Pada masalah penjadwalan kereta api jalur tunggal,

sebuah petak blok yang digunakan oleh dua perjalanan yang berbeda dapat

mengakibatkan terjadinya tabrakan.

Ada beberapa strategi dan algoritma yang dapat digunakan untuk menyelesaikan

masalah penjadwalan Job-Shop, antara lain Backtracking, Branch and Bound dan

Local Search. Dalam Tugas Akhir ini, algoritma yang digunakan adalah variasi

dari algoritma Local Search yang bernama Hill Climbing dengan strategi variable

and value ordering, dan constraint propagation. Variable and value ordering

digunakan untuk mengurutkan variabel yang akan diberi nilai (urutan operasi

yang akan dijadwalkan lebih dulu) dan constraint propagation digunakan untuk

menghapus nilai-nilai pada domain sebuah variabel jika nilai-nilai tersebut

mengarah kepada pelanggaran batasan [OLI01].

1.2 Rumusan Masalah

Berdasarkan latar belakang di atas, rumusan masalah yang dikaji dalam Tugas

Akhir ini adalah:

1. Bagaimana menemukan solusi yang berupa jadwal kereta api yang memenuhi

batasan-batasan atau aturan-aturan perjalanan kereta api jalur tunggal.

I-4

2. Bagaimana menemukan solusi optimal lokal (local optimum) dari solusi yang

telah ditemukan dengan optimasi minimum total delay atau total

keterlambatan minimal.

1.3 Tujuan

Tujuan dari Tugas Akhir ini adalah implementasi model penjadwalan Job-Shop

dalam masalah penjadwalan kereta api jalur tunggal dengan pendekatan

Constraint Programming. Tujuan khusus dari Tugas Akhir ini adalah sebagai

berikut:

1. Memahami deskripsi sistem perjalanan kereta api, aturan-aturan umum

penjadwalan kereta api jalur tunggal, dan masalah penjadwalan Job-Shop.

2. Membuat model penjadwalan Job-Shop dari masalah penjadwalan kereta api

jalur tunggal.

3. Memahami strategi dan algoritma pencarian solusi dari masalah penjadwalan

Job-Shop.

4. Melakukan implementasi pencarian solusi dari masalah penjadwalan Job-Shop

dengan pendekatan Constraint Programming.

5. Melakukan pengujian dengan menggunakan data perjalanan kereta api yang

sebenarnya.

1.4 Batasan Masalah

Batasan masalah yang dikaji dalam Tugas Akhir ini adalah:

1. Implementasi yang dilakukan hanya mencari satu solusi yang baik (local

optimum), bukan solusi terbaik dari seluruh solusi yang ada (global optimum).

Kriteria optimasi yang digunakan adalah total keterlambatan minimum.

2. Batasan-batasan yang akan diimplementasikan hanyalah batasan yang

menyangkut satu atau dua variabel saja (batasan uner dan biner), sedangkan

batasan n-ary tidak diimplementasikan. Hal ini karena batasan uner dan biner

dapat dimodelkan sebagai sisi graf sedangkan batasan n-ary tidak. Contoh

batasan uner dalam masalah penjadwalan kereta api adalah waktu berangkat

sebuah kereta api. Contoh batasan biner misalnya urutan stasiun yang harus

dilalui, dua kereta api tidak boleh berada di segmen jalur yang sama secara

bersamaan dan penggunaan sebuah kereta yang sama oleh dua perjalanan

I-5

kereta api (misalnya dari Jakarta ke Bandung kemudian dari Bandung ke

Jakarta dalam satu hari). Contoh batasan n-ary misalnya lima buah kereta api

tidak boleh berada di sebuah stasiun kecil dalam waktu yang sama.

1.5 Metodologi

Metodologi yang digunakan dalam pengerjaan Tugas Akhir ini adalah:

1. Studi Pustaka

Studi pustaka dilakukan selama pengerjaan Tugas Akhir. Studi pustaka

dilakukan dengan mempelajari deskripsi sistem perjalanan kereta api, aturan-

aturan penjadwalan kereta api jalur tunggal, masalah penjadwalan Job-Shop,

Constraint Programming dan contoh-contoh penyelesaian masalah dengan

pendekatan Constraint Programming.

2. Pemodelan Masalah

Masalah penjadwalan kereta api jalur tunggal akan dianalisis dan dimodelkan

sebagai sebuah masalah penjadwalan Job-Shop.

3. Analisis dan Perancangan

Tahapan analisis dilakukan dengan menentukan spesifikasi kebutuhan utama

perangkat lunak yang dibangun. Hal ini mencakup kebutuhan fungsional dan

non-fungsional. Selain itu juga dilakukan identifikasi fitur-fitur utama dengan

diagram use-case. Kemudian pada tahap perancangan dilakukan pembagian

kelas-kelas utama perangkat lunak dan hubungan antara kelas-kelas tersebut

berdasarkan hasil analisis yang telah dilakukan. Hal ini direpresentasikan

dengan menggunakan diagram kelas.

4. Implementasi dan Pengujian

Dari model penjadwalan Job-Shop yang telah dibuat dan juga analisis dan

perancangan perangkat lunak yang telah dilakukan, akan dilakukan

implementasi dengan menggunakan pendekatan Constraint Programming.

Paradigma pemrograman yang digunakan dalam implementasi adalah

paradigma pemrograman berorientasi objek. Bahasa pemrograman yang

digunakan adalah Java.

I-6

5. Pengujian

Setelah implementasi selesai, pengujian dilakukan dengan menggunakan

berbagai macam data perjalanan kereta api.

1.6 Sistematika Pembahasan

Sistematika pembahasan Tugas Akhir ini adalah sebagai berikut:

1. Bab I Pendahuluan berisi penjelasan mengenai latar belakang, rumusan

masalah, tujuan, batasan masalah, metodologi, serta sistematika pembahasan

yang digunakan dalam penyusunan Tugas Akhir ini.

2. Bab II Dasar Teori berisi dasar teori yang diperlukan dalam pemodelan,

analisis, perancangan dan penyelesaian masalah yang telah dimodelkan.

3. Bab III Pemodelan Masalah berisi tentang bagaimana cara melakukan

pemodelan masalah nyata dengan menggunakan model yang ada dan

algoritma serta strategi apa saja yang dapat digunakan untuk mencari solusi

pada model yang telah dibuat.

4. Bab IV Analisis dan Perancangan berisi analisis kebutuhan-kebutuhan utama

perangkat lunak, fitur-fitur utama, perancangan antarmuka aplikasi dan

perancangan kelas-kelas aplikasi.

5. Bab V Implementasi dan Pengujian berisi penjelasan mengenai implementasi

dan pengujian yang telah dilakukan berdasarkan pemodelan, analisis dan

perancangan yang telah dilakukan sebelumnya.

6. Bab VI Kesimpulan dan Saran berisi kesimpulan dan saran selama

pelaksanaan Tugas Akhir.