PENJADWALAN KERETA API MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER DWI SETIANTO

PENJADWALAN KERETA API MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER

DWI SETIANTO

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

ABSTRAK DWI SETIANTO. Penjadwalan Kereta Api Menggunakan Pemrograman Linear Integer. Dibimbing oleh PRAPTO TRI SUPRIYO dan TEDUH WULANDARI MAS’OED Karya ilmiah ini memberikan formulasi masalah penjadwalan kereta api menggunakan model pemrograman linear integer. Penjadwalan kereta api tersebut didasarkan pada jalur tunggal yang menghubungkan antar stasiun. Formulasi yang dibangun bertujuan meminimumkan keterlambatan serta menjamin bahwa tidak ada kereta api yang mengalami tabrakan baik searah maupun berlawanan arah. Input model berupa jadwal keberangkatan kereta api yang direncanakan (aktual), sedangkan outputnya berupa jadwal keberangkatan dan kedatangan kereta api yang faktual. Kata kunci: Kereta api, Penjadwalan, Pemrograman Linear Integer (PLI)

i

ABSTRACT DWI SETIANTO. Train Scheduling Using Integer Linear Programming. PRAPTO TRI SUPRIYO and TEDUH WULANDARI MAS’OED

Supervised

by

This research provides the formulation of train scheduling problems using integer linear programming model. The train scheduling is based on a single track that connects between stations. The formulations is aimed at minimizing delay and is constructed to ensure that no train would crash in either one way or two ways direction. Input model of the train departure schedule is as planned (actual), whereas the output model of scheduled train departure and arrival is factual. Key word: Train, Scheduling, Integer Linear Programming

ii

PENJADWALAN KERETA API MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER

DWI SETIANTO

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor

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

iii

Judul Nama NIM

: Penjadwalan Kereta Api Menggunakan Pemrograman Linear Integer : Dwi Setianto : G54062111

Menyetujui,

Pembimbing I

Pembimbing II

Drs. Prapto Tri Supriyo, M.Kom. NIP. 19630715 199002 1 002

Teduh Wulandari Mas'oed, M.Si. NIP. 19740915 199903 2 001

Mengetahui, Ketua Departemen Matematika

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

Tanggal Lulus :

iv

KATA PENGANTAR Puji dan syukur penulis panjatkan kehadirat Allah SWT atas segala nikmat, rahmat dan karunia -NYA sehingga penulis dapat menyelesaikan karya ilmiah ini. Tema yang dipilih adalah Riset Operasi dengan judul Penjadwalan Kereta Api Menggunakan Pemrograman Linear Integer. Skripsi ini merupakan syarat untuk menyelesaikan studi pada Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Pada kesempatan ini penulis menyampaikan ucapan terima kasih kepada : 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

Allah SWT atas limpahan Rahmat dan Karunia-NYA Keluarga tercinta: bapak dan ibu atas kasih sayangnya yang tulus dan ikhlas, untuk kakak Purwo Saputro dan Ema yang telah memberikan saran dan nasihat buat penulis. Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing I yang telah meluangkan waktu, tenaga dan pikiran dalam membimbing penulis. Teduh Wulandari Mas’oed, M.Si. selaku dosen pembimbing II yang memberikan arahan dan masukan pada penulisan karya ilmiah ini. Dr. Ir. Amril Aman, M.Sc. selaku dosen penguji yang telah memberikan saran dan masukan demi kesempurnaan karya ilmiah ini. Seluruh dosen Departemen Matematika, terima kasih atas segala ilmu yang telah diberikan. Staf Departemen Matematika: Bapak Yono, Bapak Deni, Bapak Hery, Bapak Epul, Bapak Bono, Ibu Susi dan Ibu Ade atas saran dan dedikasinya. Fajar Yuliawan dan Salman Farid, terima kasih atas ilmu, saran, waktu dan segala dukungannya. Sahabat yang selalu memberi inspirasi: Elly, Apri, Slamet Riyadi, Ratna, Adin, Kukuh, Ali, Popo, Angga, Widi, Yanti dan Avi. Semua teman Matematika 42 yang selalu menjadi panutan yang baik. Semua teman Matematika 43 yang telah menjadi bagian keluarga. Semua teman Matematika 44 atas segala dukungannya. Semua pihak yang telah membantu sehingga bisa terselesaikannya karya ilmiah ini.

Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya Matematika dan dapat menjadi inspirasi bagi penelitian selanjutnya.

Bogor, Oktober 2011

Dwi Setianto

v

RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 27 Desember 1987 sebagai putra kedua dari dua bersaudara dengan ayah Drs. H. Ngatidjan, M.Pd. dan ibu Suratinah. Tahun 2006 penulis lulus dari SMA Negeri 105 Jakarta dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis memilih Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis ikut aktif dalam kegiatan kemahasiswaan, diantaranya pada tahun 2008-2009 dengan mengikuti beberapa kepanitiaan yang diselenggarakan oleh GUMATIKA salah satunya adalah Try Out SNMPTN siswa SMA sekotamadya Bogor 2008 sebagai anggota humas.

vi

DAFTAR ISI Halaman DAFTAR TABEL .......................................................................................................................... viii DAFTAR GAMBAR ..................................................................................................................... viii LAMPIRAN ................................................................................................................................... viii I PENDAHULUAN 1.1 Latar Belakang .................................................................................................................... 1 1.2 Tujuan ................................................................................................................................. 1 II LANDASAN TEORI 2.1 Pemrograman Linear .......................................................................................................... 1 2.2 Pemrograman Linear Integer .............................................................................................. 3 2.3 Metode Branch and Bound ................................................................................................ 3 III DESKRIPSI DAN PEMODELAN MASALAH 3.1 Deskripsi Masalah .............................................................................................................. 6 3.2 Formulasi Masalah ............................................................................................................. 6 IV CONTOH KASUS DAN PENYELESAIANNYA ...................................................................... 8 V SIMPULAN DAN SARAN 5.1 Simpulan .......................................................................................................................... 12 5.2 Saran................................................................................................................................. 12 DAFTAR PUSTAKA ..................................................................................................................... 12 LAMPIRAN .................................................................................................................................... 13

vii

DAFTAR TABEL Halaman 1 2 3 4 5

Jarak antar stasiun ...................................................................................................................... 8 Data perjalanan masing-masing kereta api ................................................................................ 9 Jadwal keberangkatan kereta di masing-masing stasiun .......................................................... 11 Rute jalur yang digunakan oleh masing-masing kereta (Bk) .................................................... 17 Waktu operasi minimum kereta ( Thkmin ).................................................................................... 17

6

Waktu perpanjangan kereta ( Thkext ) ........................................................................................... 18

DAFTAR GAMBAR Halaman 1 2 3 4 5

Daerah fisibel PLI (2.7) ............................................................................................................... 4 Daerah fisibel untuk Subproblem 2 (x1 ≥ 4) dan Subproblem 3 (x1 ≤ 3)...................................... 5 Seluruh pencabangan pada metode branch and bound untuk menentukan solusi PLI (2.7) ....... 6 Contoh peta jaringan jalur kereta api antara dua stasiun ............................................................. 7 Peta jaringan jalur (rel) kereta api Yogyakarta – Solo balapan ................................................... 9

LAMPIRAN Halaman 1 Syntax Program LINGO 8.0 untuk menyelesaikan linear programming dengan Metode Branch and Bound ................................................................................................................................. 14 2 Data hipotetik awal untuk implementasi penyelesaian masalah penjadwalan kereta api .......... 17 3 Syntax Program LINGO 8.0 untuk mencari penjadwalan dan keterlambatan masing - masing kereta api. .................................................................................................................................. 19

viii

I PENDAHULUAN 1.1 Latar Belakang Semakin tingginya mobilitas penduduk di suatu negara terutama di kota besar tentulah memiliki banyak permasalahan, mulai dari kemacetan yang tak terselesaikan hingga moda transportasi yang efisien. Salah satu moda transportasi yang tepat dalam mengurangi kemacetan adalah kereta api, karena kereta api memiliki daya angkut yang besar dibandingkan angkutan kota pada umumnya. Jumlah penumpang kereta api yang meningkat akan membuat frekuensi keberangkatan kereta semakin padat. Hal ini tentunya harus ditopang dengan perencanaan yang baik. Perencanaan yang dimaksud adalah perencanaan jadwal perjalanan kereta api yang tepat dan efisien dengan memperhatikan segala kendala semisal ketersediaan rangkaian kereta maupun jalur di setiap stasiun. Tentu

tidak mudah ketika telah mendapatkan jadwal perjalanan kereta api tetapi masih memiliki delay (keterlambatan) kereta yang besar. Dalam karya ilmiah ini, akan dibahas penentuan jadwal kereta api menggunakan PLI (Pemrograman Linear Integer) yang meminimumkan delay. Solusi yang didapat menggunakan bantuan software LINGO 8.0. Karya ilmiah ini merupakan rekonstruksi dari sebagian artikel yang berjudul A Heuristic for the Train Pathing and Timetabling Problem yang ditulis oleh Yusin Lee dan Chuen-Yih Chen tahun 2009. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah mencari penyelesaian masalah penjadwalan kereta api yang meminimumkan delay (keterlambatan) menggunakan PLI (Pemrograman Linear Integer).

II LANDASAN TEORI Untuk membuat model penjadwalan kereta api diperlukan pemahaman teori Pemrograman Linear (PL) atau Linear Programming (LP), Pemrograman Linear Integer (PLI) atau Integer Linear Programming (ILP), dan metode branch-andbound. Definisi 1 (Fungsi linear) Suatu fungsi f dalam variabel-variabel x1 , x2 ,..., xn adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta c1 , c2 ,..., cn , fungsi dapat dituliskan sebagai f ( x1 , x2 ,..., xn ) c1 x1 c 2 x2 ... c n xn . (Winston 2004) Sebagai merupakan

f ( x1 , x2 )

f ( x1 , x2 ) 2 x1 3x2 contoh, fungsi linear, sementara x12 x22 bukan fungsi linear.

Definisi 2 (Pertidaksamaan dan persamaan linear) Untuk sembarang fungsi linear f ( x1 , x2 ,..., xn ) dan sembarang bilangan b, pertidaksamaan

f ( x1 , x2 ,..., xn )

b

dan

f ( x1 , x2 ,..., xn ) b adalah pertidaksamaan linear, sedangkan suatu persamaan f ( x1 , x2 ,..., xn ) b merupakan persamaan linear. (Winston 2004)

2.1 Pemrograman Linear Pemrograman Linear (PL) adalah suatu masalah optimisasi yang memenuhi ketentuan-ketentuan berikut: a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel , pembatasan tanda menentukan harus tak-negatif ( ) atau tidak dibatasi tandanya (unrestricted in sign). (Winston 2004)

2

Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 (Bentuk Standar suatu PL) Suatu pemrograman linear dalam bentuk standar didefinisikan sebagai:

Ax = = BxB + NxN = b (2.3) Karena matriks B adalah matriks tak singular, maka B memiliki invers, sehingga dari (2.3) xB dapat dinyatakan sebagai: xB = B-1b - B-1NxN Kemudian, fungsi objektifnya menjadi: min z =

max z = (atau min) s.t.

(2.4) berubah

(Winston 2004) (2.1) Dengan mendefinisikan:

Definisi 4 (Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004)

A=

, Maka kendala pada (2.1) dapat ditulis dengan sistem persamaan Ax = b (2.2) (Winston 2004) 2.1.1 Solusi suatu Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimum bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947 (Winston 2004), dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar. Pada masalah PL (2.2), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi dari PL (2.2). Misalkan matriks A dapat 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 elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (2.2). Misalkan x dinyatakan sebagai vektor x = , dengan xB adalah vektor variabel basis dan xN adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan sebagai:

Definisi 5 (Solusi Basis) Solusi basis adalah solusi pada PL yang didapatkan dengan mengatur variabel n–m sama dengan nol dan nilai untuk penyelesaiannya adalah dari sisa variabel m. Hal ini mengasumsikan bahwa mengatur variabel n–m sama dengan nol sehingga membuat nilai yang unik untuk sisa variabel m atau sejenisnya, dan kolom-kolom untuk sisa dari variabel m 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) Untuk masalah maksimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) Ilustrasi untuk solusi basis dan solusi fisibel basis diberikan dalam Contoh 1 di bawah ini. Contoh 1 Misalkan diberikan PL berikut: minimumkan z = -2 - 3 terhadap -x1 + 2x2 + x3 = 10 -2x1 + x2 + x4 = 2 2x1 + x5 = 3 x1, x2, x3, x4, x5 ≥ 0

(2.5)

3

minimisasi, nilai optimum fungsi objektif relaksasi-PL lebih kecil atau sama dengan nilai optimum fungsi objektif PLI. (Winston 2004)

Dari PL (2.5) didapatkan: , b=

A =

Misalkan dipilih T dan = = maka matriks basisnya adalah

B=

N=

T

,

.

Dengan menggunakan tersebut diperoleh

. matriks

basis

2.3 Metode Branch and Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimum dari masalah PLI digunakan software LINGO 8.0, yaitu sebuah program yang dirancang untuk menentukan solusi model linear, nonlinear, dan optimisasi integer. Software LINGO 8.0 ini menggunakan metode branch-and-bound untuk menyelesaikan masalah PLI. Prinsip dasar metode branch-and-bound adalah memecah daerah fisibel dari masalah relaksasi-PL dengan membuat subproblemsubproblem. Terdapat dua konsep dasar dalam algoritma branch-and-bound.

(2.6)

1. Branch (Cabang) Branching (pencabangan) adalah proses membagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi.

Solusi (2.6) merupakan solusi basis, karena solusi tersebut memenuhi kendala PL (2.5) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (2.6) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (2.6) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya lebih dari atau sama dengan nol.

2. Bound (Batas) Bounding (pembatasan) adalah suatu proses untuk mencari atau menghitung batas atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimum pada subproblem yang mengarah ke solusi.

. .

2.2 Pemrograman Linear Integer Pemrograman linear integer (PLI) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming (MIP). PLI dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 PLI (Garfinkel & Nemhauser 1972) Definisi 8 (Relaksasi Pemrograman Linear) Relaksasi pemrograman linear atau sering disebut relaksasi-PL merupakan suatu pemrograman linear yang diperoleh dari suatu PLI dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Untuk masalah maksimisasi, nilai optimum fungsi objektif relaksasi-PL lebih besar atau sama dengan nilai optimum fungsi objektif PLI, sedangkan untuk masalah

Metode branch-and-bound diawali dari menyelesaikan relaksasi-PL dari suatu pemrograman linear integer. Jika semua nilai variabel keputusan solusi optimum sudah berupa integer, maka solusi tersebut merupakan solusi optimum PLI. Jika tidak, dilakukan pencabangan dan penambahan batasan pada relaksasi-PLnya kemudian diselesaikan. Winston (2004) menyebutkan bahwa untuk masalah maksimisasi nilai fungsi objektif optimum untuk PLI lebih kecil atau sama dengan nilai fungsi objektif optimum untuk relaksasi-PL, sehingga nilai fungsi objektif optimum relaksasi-PL merupakan batas atas bagi nilai fungsi objektif optimum untuk masalah PLI. Diungkapkan pula oleh Winston (2004) untuk masalah maksimisasi bahwa nilai fungsi objektif optimum untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimum untuk masalah PLI asalnya. Suatu kandidat solusi diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah PLI,

4

artinya fungsi objektif dan semua variabelnya sudah bernilai integer. Sebelumnya akan dibahas terlebih dahulu pengertian subproblem yang terukur. Menurut Winston (2004), suatu subproblem dikatakan terukur (fathomed) jika salah satu kondisi berikut terpenuhi: a. Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimum bagi PLI. b. 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) nilai fungsi objektif optimum bagi masalah PLI pada saat itu. Bisa jadi subproblem ini menghasilkan solusi optimum untuk masalah PLI. c. Nilai fungsi objektif optimum untuk subproblem tersebut tidak melebihi batas bawah saat itu (untuk masalah maksimisasi). Suatu subproblem dapat dieliminasi apabila subproblem tersebut takfisibel dan batas bawah kandidat solusi lebih kecil (untuk masalah maksimisasi) dari nilai fungsi objektif optimum untuk subproblem tersebut. Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch-and-bound : Langkah 0 Didefinisikan z sebagai batas bawah dari solusi PLI yang optimum. Pada awalnya tetapkan z = − dan i = 0. Langkah 1 Subproblem PL(i) dipilih sebagai bagian masalah berikutnya untuk diteliti. Subproblem PL(i) diselesaikan dan diukur dengan kondisi yang sesuai. a) Jika PL(i) terukur, maka batas bawah z dapat diperbarui. Batas bawah z dapat diperbaharui jika solusi PLI yang lebih baik telah ditemukan. Jika tidak, maka bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah diteliti, maka proses dihentikan. b) Jika PL(i) tidak terukur, lanjutkan ke langkah 2 untuk melakukan pencabangan PL(i).

Langkah 2 Pilih satu variabel xj yang nilai optimumnya, yaitu xj*, tidak memenuhi batasan integer dalam solusi PL(i). Singkirkan bidang [xj*] xj [xj*]+1 dengan membuat dua bagian masalah PL yang berkaitan menjadi dua batasan yang tidak dapat dipenuhi secara bersamaan yaitu: xj ≤ [xj*] dan xj ≥ [xj*]+1, dengan [xj*] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan xj*. Jika PL(i) masih tidak terukur, maka kembali ke Langkah 1. (Taha 1996) Untuk memudahkan pemahaman mengenai metode branch-and-bound diberikan contoh sebagai berikut: Contoh 2 Misalkan diberikan PLI sebagai berikut: Maksimumkan z = 5 x1 + 4 x2 terhadap x1 + x2 5 10 x1 + 6 x2 x1, x2 0 dan integer (2.7) Solusi optimal relaksasi-PL dari masalah PLI (2.7) adalah x1=3.75, x2=1.25, dan z =23.75 (lihat Lampiran 1). Jadi batas atas nilai optimal fungsi objektif masalah PLI (2.7) adalah z= 23.75. Daerah fisibel relaksasi-PL masalah (2.7) ditunjukkan pada Gambar 1 (daerah yang diarsir) sedangkan titik-titik merupakan solusi fisibel masalah PLI (2.7).

x2

Daerah fisibel x1 = 3.75 x2 = 1.25

x1 Gambar 1 Daerah fisibel PLI (2.7) Langkah berikutnya adalah memartisi daerah fisibel relaksasi-PL menjadi dua bagian berdasarkan variabel yang bernilai pecahan (non-integer). Karena x1= 3.75 dan x2=1.25 variabel bernilai pecahan maka dipilih

5

salah satu variabel, misalkan x1, sebagai dasar pencabangan. Jika masalah relaksasi-PL dari PLI (2.7) diberi nama Subproblem 1 dan Subproblem 1 dicabangkan atas x1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: Subproblem 2: Subproblem 1 ditambah kendala x1 ≥ 4 Subproblem 3: Subproblem 1 ditambah kendala x1 ≤ 3. Daerah fisibel untuk kedua subproblem di atas diilustrasikan secara grafis pada Gambar 2.

x2

Subproblem 3

Subproblem 2

x1 Gambar 2 Daerah fisibel untuk Subproblem 2 (x1 ≥ 4) dan Subproblem 3 (x1 ≤ 3). Setiap titik (solusi) fisibel dari PLI (2.7) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Sekarang dipilih subproblem yang belum diselesaikan, misalkan dipilih Subproblem 2. Solusi optimal untuk Subproblem 2 ini adalah x1 = 4, x2 = 0.8333 dan z = 23.333, (lihat Lampiran 1 bagian Subproblem 2). Karena solusi optimal yang dihasilkan Subproblem 2 bukan solusi integer, maka Subproblem 2 dicabangkan atas x2 sehingga diperoleh dua subproblem lagi, yakni: Subproblem 4: Subproblem 3 ditambah kendala x2 ≥ 1; Subproblem 5: Subproblem 3 ditambah kendala x2 ≤ 0.

Saat ini subproblem yang belum diselesaikan adalah Subproblem 3, 4 dan 5. Salah satu subproblem dipilih, misalnya dengan aturan LIFO (last in first out). Dengan aturan ini berarti dipilih Subproblem 4 atau Subproblem 5. Subproblem 4 takfisibel (lihat Lampiran 1 bagian Subproblem 4) maka subproblem ini tidak dapat menghasilkan solusi optimal, yang tersisa adalah Subproblem 3 dan Subproblem 5. Karena aturan LIFO, dipilih Subproblem 5, yang kemudian menghasilkan solusi optimal x1=4.5, x2=0 dan z=22.5 (lihat Lampiran 1 bagian Subproblem 5). Karena x1=4.5 bukan integer, maka dilakukan kembali pencabangan atas x1, sehingga diperoleh: Subproblem 6: Subproblem 5 ditambah kendala x1≥5 ; Subproblem 7: Subproblem 5 ditambah kendala x1≤4. Misalkan dipilih Subproblem 6. Ternyata Subproblem 6 ini juga takfisibel (lihat Lampiran 1 bagian Subproblem 6), sehingga tidak dapat menghasilkan solusi optimal. Dengan demikian subproblem-subproblem yang belum diselesaikan adalah Subproblem 3 dan Subproblem 7. Karena aturan LIFO, dipilih Subproblem 7. Subproblem ini kemudian menghasilkan solusi opimal x1=4, x2= 0, dan z= 20 (lihat Lampiran 1 bagian Subproblem 7). Dapat dilihat bahwa solusi optimal subproblem ini semuanya berupa integer, sehingga merupakan kandidat solusi untuk PLI (2.7). Nilai z pada kandidat solusi ini merupakan batas bawah bagi nilai optimal PLI. Penyelesaian Subproblem 3 menghasilkan solusi optimal x1= 3, x2= 2 dan z= 23 (lihat Lampiran 1 bagian Subproblem 3). Batas bawah yang ditetapkan dari solusi optimal Subproblem 7 tidak lebih baik dari nilai solusi optimal yang dihasilkan Subproblem 3. Dengan demikian, nilai solusi optimal Subproblem 3, yakni z = 23 menjadi batas bawah yang baru. Semua solusi optimal telah berupa integer dan tidak perlu dilakukan pencabangan kembali, sehingga solusi optimal dari Subproblem 3 merupakan solusi optimal PLI (2.7), yakni x1= 3, x2= 2 dan z= 23. Pohon pencabangan yang menunjukkan proses penyelesaian masalah PLI (2.7) secara keseluruhan ditunjukkan pada Gambar 3.

6

Subproblem 1 t=1

x1=3.75, x2=1.25 dan z = 23.75

x1 ≥ 4 t=2

x1 ≤ 3 t=7

Subproblem 2 x1=4, x2=0.8333 dan z = 23.333

t=3

x1=3, x2=2, dan z = 23 batas bawah bagi IP (2.7) atau Solusi Optimal

x2 ≤ 0

x2 ≥ 1 Subproblem 4

Subproblem 5

t=4

Solusi tak fisibel

x1=4.5, x2=0 dan z = 22.5

x1 ≥ 5 t=5

Subproblem 3

Subproblem 6 Solusi tak fisibel

x1 ≤ 4 t=6

Subproblem 7 x1=4, x2=0, dan z = 20 Kandidat Solusi Optimal

Gambar 3 Seluruh pencabangan pada metode branch and bound untuk menentukan solusi PLI (2.7)

III DESKRIPSI DAN PEMODELAN MASALAH 3.1 Deskripsi masalah Untuk mendeskripsikan masalah penjadwalan kereta api di setiap stasiun, hal utama yang harus diketahui adalah banyaknya rangkaian kereta yang ditugaskan di stasiun tersebut. Kemudian dari kereta api yang ditugaskan tadi, seberapa banyak ketersedian jalur yang dapat dilalui. Banyaknya kereta api yang beroperasi juga bergantung pada kebutuhan atau permintaan penumpang. Dalam memenuhi keinginan penumpang, tersedia dua jenis kereta api yaitu kereta api reguler dan kereta api ekspress. Untuk kereta api regular, waktu tunggu di dalam stasiun lebih lama dibandingkan jenis yang kedua yaitu kereta api ekspress. Selain itu kecepatan kereta api jenis reguler lebih rendah dibandingkan kereta api jenis ekspress. Berikut ini adalah gambaran dari suatu penjadwalan kereta api. Misalkan terdapat n buah stasiun yang masing-masing stasiun memiliki dua buah jalur pemberhentian dan

dari keseluruhan stasiun tersebut saling dihubungkan oleh jalur tunggal. Stasiun ke-1 dan stasiun ke-n adalah stasiun pemberangkatan, sedangkan stasiun ke-2 hingga stasiun ke−(n-1) adalah stasiun pemberhentian. Andaikan dioperasikan p kereta api ekspress dan q kereta api reguler. Kereta api tersebut ada yang diberangkatkan dari stasiun ke-1 dan juga dari stasiun ke-n. Pengelola stasiun dihadapkan pada masalah penjadwalan kereta sedemikian rupa sehingga dapat meminimumkan delay (keterlambatan), dengan memperhatikan kebutuhan pengguna kereta api. 3.2 Formulai masalah Model penjadwalan kereta api bergantung pada ketersedian rangkaian kereta api dan jumlah jalur yang dapat dilalui. Selanjutnya, penjadwalan kereta api dapat diformulasikan dalam bentuk PLI.

7

Model penjadwalan pada karya ilmiah ini menggunakan dua parameter utama sebagai penyusun jadwal, yaitu: 1. Kereta, yaitu seluruh rangkaian kereta api yang terlibat dalam penjadwalan. 2. Jalur, yaitu jalur yang dapat dilalui oleh kereta api dan yang terlibat dalam penjadwalan. Sebagai contoh, pandang penamaan jalur kereta api antara dua buah stasiun di bawah ini. stasiun A stasiun B 1

Variabel-variabel yang digunakan dalam model penjadwalan kereta api ini sebagai berikut: : : : : : :

Bs

:

Bk \ Bs

: :

: :

: : :

:

:

yhk

:

a hk

:

dhk

:

dhm

: :

: 5

Gambar 4 Contoh peta jaringan jalur kereta api antara dua stasiun

s k,m V h B Bk

:

4 3

2

delayk

indeks stasiun. indeks kereta. himpunan seluruh kereta. indeks jalur. himpunan semua jalur. himpunan semua jalur yang dilewati oleh kereta k. himpunan jalur yang terletak di dalam stasiun. himpunan jalur yang terletak di luar stasiun. lama waktu minimum kereta k menyelesaikan seluruh perjalanannya (menit). lama waktu minimum kereta k di jalur h (menit). lama waktu perpanjangan atau maksimum yang diizinkan untuk kereta k di jalur h apabila mengalami delay (menit). jalur pertama yang digunakan oleh kereta k. jalur terakhir yang digunakan oleh kereta k. jalur yang telah digunakan kereta k sebelum memasuki jalur h. Selisih minimum waktu antara dua kereta menggunakan jalur h secara berurutan (menit). waktu ketika kereta k memasuki jalur pertama yang digunakannya.

Selain itu, diperlukan pula pendefinisian suatu variabel keputusan:

total waktu keterlambatan kereta k (menit) keterlambatan kereta k di jalur h (menit) waktu ketika kereta k memasuki jalur h. waktu ketika kereta k meninggalkan jalur h. waktu ketika kereta m meninggalkan jalur h. waktu ketika kereta k meninggalkan jalur terakhir yang digunakannya. waktu ketika kereta k meninggalkan jalur yang telah digunakannya tepat sebelum memasuki jalur h.

Fungsi objektif dari permasalahan ini adalah meminimumkan keterlambatan seluruh kereta api, sehingga dimodelkan sebagai berikut: minimumkan dengan kendala-kendala sebagai berikut: 1) Mengatur waktu kedatangan dan keberangkatan kereta berdasarkan lama waktu operasi minimum kereta. Apabila kereta mengalami delay maka akan diatur di kendala 2. ≥ + h , k V 2) Menyatakan bahwa jika panjang waktu kereta yang dijadwalkan melebihi waktu operasi minimumnya, maka kelebihan waktu ini dianggap sebagai keterlambatan yang dijadwalkan. ≤ + + h , k V Dari kendala 1 dan 2 didapat persamaan berikut: + ≤ ≤ + + Misalkan 7:03 ≤ ≤ 7:06, yang artinya adalah waktu kereta k meninggalkan jalur h adalah pukul 7:03 (tanpa delay) sedangkan apabila mengalami delay maka batas waktu maksimumnya adalah sampai pukul 7:06. 3) Kendala berikut menjelaskan aturan penggunaan satu jalur oleh dua kereta pada saat yang bersamaan baik untuk satu arah maupun berlawanan arah. ≥ h \ , k,m V

8

Perhatikan ilustrasi berikut ini: (contoh berlawanan arah) kereta k

kereta m stasiun A

jalur h

stasiun B

Kereta m (dari A ke B) dan kereta k (dari B ke A) menggunakan jalur yang sama (h), maka harus ada selisih minimum waktu ( ) agar kedua kereta tersebut tidak bertabrakan.

kereta k

Misal kereta k = 1 melalui jalur h = 1, 2, dan 3 (Bk = 1,2,3) h=1

h=2

h=3

Kereta 1

h = 2 maka B21 = 1 sehingga d11 = a 21 h = 3 maka B31 = 2 sehingga d21 = a 31

(contoh satu arah) kereta m (7:00)

4) Waktu kereta k meninggalkan jalur yang telah digunakannya tepat sebelum memasuki jalur h sama dengan waktu kereta k memasuki jalur h. = h , k V

(7:02)

(7:04) (7:06)

(7:02) (7:03) (7:04) (7:05) h=1 h=3 h=2

stasiun A

stasiun B

Diperlukan selisih minimum waktu (Chmk) antara kereta k dan m untuk menghindari kemungkinan terjadinya tabrakan. Kereta k mengalami delay terutama di jalur h = 2.

5) Lama waktu kereta api yang dibutuhkan mulai dari stasiun awal hingga stasiun tujuan. = + , k V Kendala ketaknegatifan ≥ 0 dan bilangan integer delayk ≥ 0 dan delayk bilangan integer

IV CONTOH KASUS DAN PENYELESAIANNYA Pada bagian ini akan diberikan contoh kasus dengan data hipotetik seperti penamaan stasiun, rangkaian kereta yang digunakan dan jumlah jalur yang tersedia. Misalkan PT KAI (Kereta Api Indonesia) memiliki tujuh stasiun (s) yang jarak dari stasiun satu ke stasiun berikutnya beragam (Tabel 1). Tabel 1 Jarak antar stasiun Stasiun 1 Stasiun 2 Yogyakarta Lempuyangan Lempuyangan Sleman Sleman Kalasan Kalasan Prambanan Prambanan Klaten Klaten Solo balapan

Jarak (m) 7200 14400 7200 14400 7200 7200

Kemudian dari ketujuh stasiun tersebut ada yang memiliki dua maupun tiga jalur kereta api. Sehingga setiap kereta api yang akan melalui jalur (h) tersebut harus sesuai kapasitas masing-masing stasiun. Untuk kereta api sendiri terbagi kedalam dua jenis, yaitu kereta api ekspress dan kereta api reguler. Untuk kereta api ekspress, kecepatan rata-ratanya adalah 144 km/jam dengan waktu

tunggu di dalam stasiun dua menit sedangkan untuk kereta api reguler, kecepatan rataratanya adalah 72 km/jam dengan waktu tunggu di dalam stasiun empat menit. Selanjutnya ada 12 perjalanan kereta api (k) yang siap untuk diberangkatkan yang terbagi ke dalam 6 kereta untuk rute Yogyakarta ke Solo balapan dan 6 kereta lagi untuk rute sebaliknya. Tabel 2 memberikan jam keberangkatan yang direncanakan dengan periode waktu menit (0 – 1440). Jam keberangkatan sesungguhnya akan ditentukan pada hasil perhitungan yang dilakukan oleh model. Dari seluruh kereta api tersebut telah ditentukan urutan jalur atau rute yang akan dilalui oleh masing-masing kereta (Bk) seperti yang tertera pada Tabel 4 (Lampiran 2). Lama waktu yang dibutuhkan oleh masing-masing kereta untuk melalui jalur antar stasiun (Bk \ Bs) tergantung pada kecepatan kereta api tersebut, selengkapnya dapat dilihat pada Tabel 5 (lama waktu minimum kereta) dan Tabel 6 (lama waktu perpanjangan kereta) di setiap jalur yang dilaluinya pada Lampiran 2. Dalam

9

melakukan penjadwalan kereta api juga diperlukan sketsa peta jaringan rel kereta seperti yang tersaji di Gambar 5. Model penjadwalan kereta api ini menggunakan beberapa asumsi. Asumsi yang digunakan diantaranya adalah:

1. Jalur yang menghubungkan antar stasiun adalah jalur tunggal. 2. Tidak ada prioritas kereta.

Tabel 2 Data perjalanan masing-masing kereta api Indeks (k)

Kereta

1 2 3 4 5 6 7 8 9 10 11 12

trans jogja 1 trans jogja 2 trans jogja 3 trans jogja 4 trans jogja 5 trans jogja 6 solo jaya 1 solo jaya 2 solo jaya 3 solo jaya 4 solo jaya 5 solo jaya 6

Yogyakarta

Stasiun asal

Stasiun tujuan

Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan

Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta

Jenis ekspress ekspress regular regular ekspress regular regular ekspress regular ekspress ekspress regular

Lempuyangan

Sleman

7

12

Kalasan

1

Jam berangkat (menit ke-) 22 34 55 77 132 167 4 11 58 96 149 170

Prambanan

Waktu tunggu (menit) 2 2 4 4 2 4 4 2 4 2 2 4

Klaten

Kec (km/jam) 144 144 72 72 144 72 72 144 72 144 144 72

Solo balapan

17

33 23

2

28

18 4 5 6

9 10 11 8

34 20 21 22

14 15 16 13

25 26 27 24

3

30 31 32 29

19

35

Gambar 5 Peta jaringan jalur (rel) kereta api Yogyakarta-Solo balapan

Model penjadwalan tersebut selanjutnya dapat diformulasikan ke dalam bentuk PLI dengan fungsi objektif: 12

delayk

Minimumkan

Sebagai contoh, dengan memperhatikan Tabel 4 (Lampiran 2) untuk kereta k = 3 dan jalur h = 6, diperoleh pertidaksamaan d63 ≥ a 63 + T63min . Sehingga diperoleh seluruhnya 300 pertidaksamaan.

k 1

Dengan kendala : 1) Waktu kereta k meninggalkan jalur h harus lebih besar atau sama dengan waktu kereta k memasuki jalur h ditambah lama waktu minimum kereta k di jalur h.

d hk

a hk

+

min hk

T

,

h

Bk

2) Waktu kereta k meninggalkan jalur h harus lebih kecil atau sama dengan waktu kereta k memasuki jalur h ditambah masa keterlambatan kereta k di jalur h dan lama waktu perpanjangan kereta k di jalur h.

d hk

a hk + yhk + Thkext ,

h

Bk

Sebagai contoh, dengan memperhatikan Tabel 4 (Lampiran 2) untuk kereta k = 1

10

dan jalur h = 8, diperoleh pertidaksamaan d81 ≤ a 81 + y81 + T81ext. Sehingga diperoleh seluruhnya 300 pertidaksamaan. 3) Waktu kereta k memasuki jalur h dikurangi waktu kereta m meninggalkan jalur h lebih besar atau sama dengan selisih minimum waktu antara kereta m dan k di jalur h.

a hk – d hm

chmk s

h Bk \ B atau jalur antar stasiun, yaitu jalur 4, 5, 6, 9, 10, 11, 14, 15, 16, 20, 21, 22, 25, 26, 27, 30, 31, dan 32. Untuk contoh kasus ini diasumsikan nilai

chmk = 1 4) Waktu kereta k meninggalkan jalur yang telah digunakannya tepat sebelum memasuki jalur h sama dengan waktu kereta k memasuki jalur h.

d B k = a hk

,

h

Bk

hk

Sebagai contoh, dengan memperhatikan Tabel 4 (Lampiran 2) untuk kereta k = 1 dan jalur h = 4 , diperoleh persamaan d11 = a 41. Sehingga diperoleh seluruhnya 300 pertidaksamaan. 5) Waktu kereta k meninggalkan jalur terakhir dikurangi waktu kereta k memasuki jalur pertama yang digunakannya sama dengan total waktu keterlambatan kereta k ditambah lama waktu minimum kereta k menyelesaikan perjalanannya. d BF k - a B0k = delayk + Tripk k

k

Sebagai contoh, dengan memperhatikan Tabel 4 (Lampiran 2) untuk kereta k = 1, )= jalur pertama yang digunakannya ( 1 dan jalur terakhir yang digunakan ( ) = 33, diperoleh persamaan d331 – a 11 = delay1 + Trip1. Sehingga diperoleh seluruhnya 12 persamaan. Pada uraian contoh kasus di PT KAI banyak sekali persamaan maupun pertidaksamaan yang harus diselesaikan, hal ini menjadi sulit apabila menggunakan metode branch-and-bound secara manual. Oleh karena itu diperlukan suatu alat bantu yaitu dengan menggunakan software LINGO 8.0. Syntax program dan hasil komputasi dicantumkan pada Lampiran 3. Solusi yang didapat merupakan solusi optimum dengan nilai fungsi objektifnya adalah 8 menit dengan rincian sebagai berikut: Kereta 1 tidak mengalami delay Kereta 2 mengalami delay 4 menit Kereta 3 tidak mengalami delay Kereta 4 tidak mengalami delay Kereta 5 tidak mengalami delay Kereta 6 mengalami delay 2 menit Kereta 7 tidak mengalami delay Kereta 8 mengalami delay 2 menit Kereta 9 tidak mengalami delay Kereta 10 tidak mengalami delay Kereta 11 tidak mengalami delay Kereta 12 tidak mengalami delay Berikut hasil penjadwalan kereta api yang tertera di Tabel 3 yang didapatkan dari software Lingo 8.0.

Yogyakarta - Solo balapan

Yogyakarta tiba berangkat 20 22

Lempuyangan tiba berangkat 25 27

tiba 33

trans jogja 2


32

34

41

43

49

51

54

3

trans jogja 3


51

55

61

65

77

81

4

trans jogja 4


73

77

83

87

99

5

trans jogja 5


130

132

135

137

143


163 167 Solo balapan tiba berangkat 0 4

Indeks (k)

Kereta

1

trans jogja 1

2

Rute

6

trans jogja 6

Indeks (k)

Kereta

7

solo jaya 1

Solo balapan - Yogyakarta

8

solo jaya 2


9

9

solo jaya 3


10

solo jaya 4

11 12

Prambanan tiba berangkat 46 48

tiba 51

56

62

64

67

69

72

74

87

91

103

107

113

117

123

127

103

109

113

125

129

135

139

145

149

145

148

150

156

158

161

163

166

168

tiba 38

Kalasan berangkat 40

201

217

Klaten berangkat 53

Solo balapan tiba selesai 56 58

179 Klaten tiba berangkat 10 14

191 195 Prambanan tiba berangkat 20 24

205 Kalasan tiba berangkat 36 40

221 Sleman tiba berangkat 46 50

227 231 Lempuyangan tiba berangkat 62 66

237 241 Yogyakarta tiba selesai 72 76

13

16

18

21

23

29

31

34

36

42

44

47

49

54

58

64

68

74

78

90

94

100

104

116

120

126

130


94

96

99

101

104

106

112

114

117

119

125

127

130

132

solo jaya 5


147

149

152

154

157

159

165

167

170

172

178

180

183

185

solo jaya 6


166

170

176

180

186

190

202

206

212

216

228

232

238

242

Rute

175

Sleman berangkat 35

Tabel 3 Jadwal keberangkatan kereta di masing-masing stasiun

11

12

V SIMPULAN DAN SARAN 5.1 Simpulan Dalam penulisan karya ilmiah ini telah diperlihatkan penyelesaian dari masalah penjadwalan kereta api yang bertujuan untuk menentukan nilai keterlambatan (delay) yang minimum. Masalah ini dipandang sebagai masalah 0-1 PLI.

5.2 Saran Pada karya ilmiah ini data yang digunakan merupakan data hipotetik, saran untuk penulisan selanjutnya adalah dengan menggunakan data yang asli. Model penjadwalan kereta api ini juga dapat dikembangkan semisal meminimumkan biaya operasional kereta tentunya dengan menambahkan beberapa kendala.

DAFTAR PUSTAKA Garfinkel, R.S & G.L. Nemhauser. 1972. Integer Programming. John Willey & Sons, New York. Lee, Yusin. & Chen, Chuen-Yih. 2009. A heuristic for the train pathing and timetabling problem. Transportation research part B,43:837-851.

Taha, H.A. 1996. Pengantar Riset Operasi. Alih Bahasa:k Drs. Daniel Wirajaya. Binarupa Aksara, Jakarta. Terjemahan dari: Operations Research. Winston, W.L. 2004. Operations Research Applications and Algorithms 4th ed. Duxbury, New York.

LAMPIRAN

14

Lampiran 1 Syntax Program LINGO 8.0 untuk menyelesaikan linear programming dengan Metode Branch and Bound 1) Mencari solusi LP-relaksasi dari subproblem 1 (masalah 2.7) maksimumkan z = 5 x1 + 4 x2 terhadap x1 + x2 5 10 x1 + 6 x2 x1,x2 0 dan integer Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; Hasil yang diperoleh: Global optimum solution found at iteration: 4 Objective value: 23.75000 Variable X1 X2

Value Reduced Cost 3.750000 0.000000 1.250000 0.000000

Row

Slack or Surplus

Dual Price

1 2 3 4 5

23.75000 0.000000 0.000000 3.750000 1.250000

1.000000 2.500000 0.2500000 0.000000 0.000000

Karena solusi yang diperoleh belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu : Subproblem 2, dimana subproblem 1 + kendala (x1 ≥ 4) Subproblem 3, dimana subproblem 1 + kendala (x1 ≤ 3) 2) Mencari solusi LP dari subproblem 2 Maksimumkan z = 5x1 + 4x2 Terhadap x1 + x2 5 10 x1 + 6x2 45 x1 ≥ 4 x1,x2 0 dan integer Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1>=4;

Hasil yang diperoleh: Global optimum solution found at iteration: 5 Objective value: 23.33333 Variable Value Reduced Cost X1 4.000000 0.000000 X2 0.8333333 0.000000 Row

Slack or Surplus

Dual Price

1 2 3 4 5 6

23.33333 0.1666667 0.000000 4.000000 0.8333333 0.000000

1.000000 0.000000 0.6666667 0.000000 0.000000 -1.666667

Karena solusi yang diperoleh belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu : Subproblem 4, dimana subproblem 3 + kendala ( ≥ 1) Subproblem 5, dimana subproblem 3 + kendala ( ≤ 0) 3) Mencari solusi LP dari subproblem 4 Maksimumkan z = 5x1 + 4x2 Terhadap x1 + x2 5 10 x1 + 6x2 45 x1 ≥ 4 x2 ≥ 1 x1,x2 0 dan integer Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1>=4; x2>=1; Hasil yang diperoleh:

15

4) Mencari solusi LP dari subproblem 5 Maksimumkan z = 5x1 + 4x2 Terhadap x1 + x2 5 10 x1 + 6x2 45 x1 ≥ 4 x2 ≤ 0 x1,x2 0 dan integer

x2<=0; x1>=0; x2>=0; Hasil yang diperoleh:

Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1>=4; x2<=0; Hasil yang diperoleh: Global optimum solution found at iteration: 3 Objective value: 22.50000 Variable X1 X2


Row

Slack or Surplus

Dual Price

1 2 3 4 5 6 7

22.50000 0.5000000 0.000000 4.500000 0.000000 0.5000000 0.000000

1.000000 0.000000 0.5000000 0.000000 0.000000 0.000000 1.000000

Karena solusi yang diperoleh belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu : Subproblem 6, dimana subproblem 5 + kendala ( ≥ 5) Subproblem 7, dimana subproblem 5 + kendala ( ≤ 4) 5) Mencari solusi LP dari subproblem 6 Maksimumkan z = 5x1 + 4x2 Terhadap x1 + x2 5 10 x1 + 6x2 45 x1 ≥ 5 x2 ≤ 0 x1,x2 0 dan integer Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=5;

6) Mencari solusi LP dari subproblem 7 Maksimumkan z = 5x1 + 4x2 Terhadap x1 + x2 5 10 x1 + 6x2 45 x1 ≤ 4 x2 ≤ 0 x1,x2 0 dan integer Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1<=4; x2<=0; x1>=0; x2>=0; Hasil yang diperoleh: Global optimum solution found at iteration: 2 Objective value: 20.00000 Variable X1 X2


Row

Slack or Surplus

Dual Price

1 2 3 4 5 6 7

20.00000 1.000000 5.000000 0.000000 0.000000 4.000000 0.000000

1.000000 0.000000 0.000000 5.000000 4.000000 0.000000 0.000000

7) Mencari solusi LP dari subproblem 3 Maksimumkan z = 5x1 + 4x2 Terhadap x1 + x2 5 10 x1 + 6x2 45 x1 3

16

x1,x2 0 dan integer Syntax program pada Lingo 8.0 : max=5*x1+4*x2; x1+x2<=5; 10*x1+6*x2<=45; x1>=0; x2>=0; x1<=3; Hasil yang diperoleh: Global optimum solution found at iteration: 3 Objective value: 23.00000 Variable X1 X2


Row

Slack or Surplus

Dual Price

1 2 3 4 5 6

23.00000 0.000000 3.000000 3.000000 2.000000 0.000000

1.000000 4.000000 0.000000 0.000000 0.000000 1.000000

Hasil yang diperoleh telah memenuhi kendala integer maka subproblem 3 akan dijadikan batas bawah.

17

Lampiran 2 Data hipotetik awal untuk implementasi penyelesaian masalah penjadwalan kereta api

Tabel 4 Rute jalur yang digunakan oleh masing-masing kereta (Bk) Indeks (k) 1 2 3 4 5 6 7 8 9 10 11 12

Kereta

Stasiun asal

trans jogja 1 trans jogja 2 trans jogja 3 trans jogja 4 trans jogja 5 trans jogja 6 solo jaya 1 solo jaya 2 solo jaya 3 solo jaya 4 solo jaya 5 solo jaya 6

Stasiun tujuan

Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan

Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan Solo balapan Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta Yogyakarta

Jalur (h) 1 3 2 1 3 2 34 33 35 33 35 34

4 4 4 4 4 4 32 32 32 32 32 32

5 5 5 5 5 5 31 31 31 31 31 31

6 6 6 6 6 6 30 30 30 30 30 30

8 7 8 7 8 7 28 29 29 28 29

9 9 9 9 9 9 27 27 27 27 27 28 27

10 10 10 10 10 10 26 26 26 26 26 26

11 11 11 11 11 11 25 25 25 25 25 25

12 13 12 12 12 13 23 24 23 24 24

14 14 14 14 14 14 22 22 22 22 22 23 22

15 15 15 15 15 15 21 21 21 21 21 21

Tabel 5 Waktu operasi minimum kereta ( Thkmin ) jalur 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

1 2 0 0 1 1 1 0 2 2 2 2 2 0 1 1 1 2 0 0 2 2 2 0 2 1 1 1 2 0 1 1 1 2 0

2 0 0 2 1 1 1 2 0 2 2 2 0 2 1 1 1 2 0 0 2 2 2 2 0 1 1 1 2 0 1 1 1 0 0

3 0 4 0 2 2 2 0 4 4 4 4 4 0 2 2 2 0 0 4 4 4 4 4 0 2 2 2 0 4 2 2 2 4 0

4 4 0 0 2 2 2 4 0 4 4 4 4 0 2 2 2 0 4 0 4 4 4 0 4 2 2 2 4 0 2 2 2 0 4

5 0 0 2 1 1 1 0 2 2 2 2 2 0 1 1 1 0 2 0 2 2 2 2 0 1 1 1 0 2 1 1 1 2 0

0

2

0

0

0

kereta 6 0 4 0 2 2 2 4 0 4 4 4 0 4 2 2 2 4 0 0 4 4 4 4 0 2 2 2 0 4 2 2 2 0 0

4

7 0 4 0 2 2 2 4 0 4 4 4 4 0 2 2 2 0 0 4 4 4 4 4 0 2 2 2 4 0 2 2 2 0 4

8 0 0 2 1 1 1 0 2 2 2 2 0 2 1 1 1 0 2 0 2 2 2 0 2 1 1 1 0 2 1 1 1 2 0

9 0 4 0 2 2 2 4 0 4 4 4 0 4 2 2 2 4 0 0 4 4 4 4 0 2 2 2 0 4 2 2 2 0 0

10 2 0 0 1 1 1 0 2 2 2 2 2 0 1 1 1 0 0 2 2 2 2 0 2 1 1 1 2 0 1 1 1 2 0

11 0 0 2 1 1 1 0 2 2 2 2 0 2 1 1 1 2 0 0 2 2 2 0 2 1 1 1 0 2 1 1 1 0 0

12 0 4 0 2 2 2 4 0 4 4 4 4 0 2 2 2 0 0 4 4 4 4 4 0 2 2 2 4 0 2 2 2 0 4

0

0

4

0

2

0

16 16 16 16 16 16 20 20 20 20 20 20

17 17 19 18 18 17 19 18 17 19 17 19

20 20 20 20 20 20 16 16 16 16 16 16

21 21 21 21 21 21 15 15 15 15 15 15

22 22 22 22 22 22 14 14 14 14 14 14

24 23 23 24 23 23 12 13 13 12 13

25 25 25 25 25 25 11 11 11 11 11 12 11

26 26 26 26 26 26 10 10 10 10 10 10

27 27 27 27 27 27 9 9 9 9 9 9

28 28 29 28 29 29 7 8 7 8 8

30 30 30 30 30 30 6 6 6 6 6 7 6

31 31 31 31 31 31 5 5 5 5 5 5

32 32 32 32 32 32 4 4 4 4 4 4

33 35 33 34 33 35 2 3 2 1 3

2

18

Tabel 6 Waktu perpanjangan kereta ( Thkext ) jalur 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

1 3 0 0 2 1 3 0 3 2 3 2 2 0 1 2 2 3 0 0 3 2 2 0 2 2 1 1 3 0 4 3 2 3 0

2 0 0 2 1 1 1 2 0 2 2 2 0 2 1 1 1 2 0 0 2 2 2 2 0 1 1 1 2 0 1 1 1 0 0

3 0 5 0 3 4 2 0 6 4 6 4 5 0 3 3 2 0 0 4 4 6 7 4 0 2 3 2 0 5 2 3 3 5 0

4 5 0 0 3 2 4 5 0 5 4 5 8 0 2 4 2 0 4 0 9 4 5 0 4 3 2 2 4 0 2 5 2 0 4

5 0 0 3 2 5 1 0 2 9 5 7 5 0 1 3 3 0 2 0 4 2 3 4 0 1 5 3 0 3 1 4 1 3 0

0

2

0

0

0

kereta 6 0 4 0 2 2 2 4 0 4 4 4 0 4 2 2 2 4 0 0 4 4 4 4 0 2 2 2 0 4 2 2 2 0 0

4

7 0 6 0 2 4 3 5 0 4 5 6 5 0 3 2 3 0 0 4 4 5 7 4 0 5 5 5 4 0 6 5 2 0 8

8 0 0 2 1 1 1 0 2 2 2 2 0 2 1 1 1 0 2 0 2 2 2 0 2 1 1 1 0 2 1 1 1 2 0

9 0 5 0 5 3 3 4 0 4 4 4 0 4 2 2 2 5 0 0 4 4 4 5 0 2 2 2 0 5 2 3 3 0 0

10 7 0 0 2 1 1 0 7 4 6 7 2 0 1 1 1 0 0 2 2 4 2 0 2 1 2 3 6 0 6 1 1 3 0

11 0 0 9 1 2 7 0 3 7 3 3 0 5 1 1 1 3 0 0 3 2 2 0 3 1 2 2 0 5 1 2 1 0 0

12 0 5 0 2 6 2 4 0 4 7 4 5 0 2 3 2 0 0 5 4 6 4 4 0 3 3 2 6 0 5 5 2 0 5

0

0

9

0

3

0

19

Lampiran 3 Syntax Program LINGO 8.0 untuk mencari panjadwalan dan keterlambatan masing-masing kereta api SETS: jalur/1..35/; kereta/1..12/:delay,trip; variable1(jalur,kereta):d,a,y,Tmin,Text; variabel2(jalur,kereta,kereta):C; ENDSETS data: trip=38 38 76 76 38 76 76 38 76 38 38 76; @OLE('jadwal KAI.xlsx','d','a')=D,A; Tmin,Text=@OLE('jadwal KAI.xlsx','tmin','text'); C=1; enddata min=@sum(kereta(k):delay(k)); !waktu tiba kereta di stasiun awal; a(1,1)=20;a(3,2)=32;a(2,3)=51;a(1,4)=73;a(3,5)=130;a(2,6)=163;a(34,7)=0;a(33,8)=9; a(35,9)=54;a(33,10)=94;a(35,11)=147;a(34,12)=166; !kendala1; !@for(jalur(h):@for(kereta(k):d(h,k)>=a(h,k)+Tmin(h,k))); @for(jalur(h)|h#eq#1#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#8#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#17#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#24#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#28#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#33:@for(kereta(k)|k#eq#1:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#3#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#7#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#13#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#17#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#28#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#35:@for(kereta(k)|k#eq#2:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#2#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#8#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#19#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#29#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#33:@for(kereta(k)|k#eq#3:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#1#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#7#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#18#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#24#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#28#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#34:@for(kereta(k)|k#eq#4:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#3#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#8#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#18#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#29#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#33:@for(kereta(k)|k#eq#5:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#2#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#7#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#13#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#17#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#29#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#35:@for(kereta(k)|k#eq#6:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#34#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#28#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#23#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#19#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#12#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#7#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#2:@for(kereta(k)|k#eq#7:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#33#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#29#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#24#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#18#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#13#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#8#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#3:@for(kereta(k)|k#eq#8:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#35#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#29#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#23#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#17#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#13#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#7#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#2:@for(kereta(k)|k#eq#9:d(h,k)>=a(h,k)+Tmin(h,k))) ; @for(jalur(h)|h#eq#33#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#28#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#24#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#19#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#12#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#8#or#h#e

20

q#6#or#h#eq#5#or#h#eq#4#or#h#eq#1:@for(kereta(k)|k#eq#10:d(h,k)>=a(h,k)+Tmin(h,k)) ); @for(jalur(h)|h#eq#35#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#29#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#24#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#17#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#13#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#8#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#3:@for(kereta(k)|k#eq#11:d(h,k)>=a(h,k)+Tmin(h,k)) ); @for(jalur(h)|h#eq#34#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#28#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#23#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#19#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#12#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#7#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#2:@for(kereta(k)|k#eq#12:d(h,k)>=a(h,k)+Tmin(h,k)) ); !kendala2; !@for(jalur(h):@for(kereta(k):d(h,k)<=a(h,k)+y(h,k)+Text(h,k))); @for(jalur(h)|h#eq#1#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#8#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#17#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#24#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#28#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#33:@for(kereta(k)|k#eq#1:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#3#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#7#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#13#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#17#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#28#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#35:@for(kereta(k)|k#eq#2:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#2#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#8#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#19#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#29#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#33:@for(kereta(k)|k#eq#3:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#1#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#7#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#18#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#24#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#28#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#34:@for(kereta(k)|k#eq#4:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#3#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#8#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#12#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#18#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#29#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#33:@for(kereta(k)|k#eq#5:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#2#or#h#eq#4#or#h#eq#5#or#h#eq#6#or#h#eq#7#or#h#eq#9#or#h#eq#10# or#h#eq#11#or#h#eq#13#or#h#eq#14#or#h#eq#15#or#h#eq#16#or#h#eq#17#or#h#eq#20#or#h# eq#21#or#h#eq#22#or#h#eq#23#or#h#eq#25#or#h#eq#26#or#h#eq#27#or#h#eq#29#or#h#eq#30 #or#h#eq#31#or#h#eq#32#or#h#eq#35:@for(kereta(k)|k#eq#6:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#34#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#28#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#23#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#19#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#12#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#7#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#2:@for(kereta(k)|k#eq#7:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#33#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#29#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#24#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#18#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#13#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#8#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#3:@for(kereta(k)|k#eq#8:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#35#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#29#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#23#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#17#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#13#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#7#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#2:@for(kereta(k)|k#eq#9:d(h,k)<=a(h,k)+y(h,k)+Text (h,k))); @for(jalur(h)|h#eq#33#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#28#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#24#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#19#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#12#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#8#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#1:@for(kereta(k)|k#eq#10:d(h,k)<=a(h,k)+y(h,k)+Tex t(h,k))); @for(jalur(h)|h#eq#35#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#29#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#24#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#17#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#13#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#8#or#h#e q#6#or#h#eq#5#or#h#eq#4#or#h#eq#3:@for(kereta(k)|k#eq#11:d(h,k)<=a(h,k)+y(h,k)+Tex t(h,k))); @for(jalur(h)|h#eq#34#or#h#eq#32#or#h#eq#31#or#h#eq#30#or#h#eq#28#or#h#eq#27#or#h# eq#26#or#h#eq#25#or#h#eq#23#or#h#eq#22#or#h#eq#21#or#h#eq#20#or#h#eq#19#or#h#eq#16 #or#h#eq#15#or#h#eq#14#or#h#eq#12#or#h#eq#11#or#h#eq#10#or#h#eq#9#or#h#eq#7#or#h#e

21

q#6#or#h#eq#5#or#h#eq#4#or#h#eq#2:@for(kereta(k)|k#eq#12:d(h,k)<=a(h,k)+y(h,k)+Tex t(h,k))); !kendala3; !@for(jalur(h):@for(kereta(k):@for(kereta(m):a(h,k)-d(h,m)>=C(h,m,k)))); @for(jalur(h)|h#eq#26:@for(kereta(k)|k#eq#8:@for(kereta(m)|m#eq#7:a(h,k)-d(h,m)>= C(h,m,k)))); @for(jalur(h)|h#eq#9:@for(kereta(k)|k#eq#2:@for(kereta(m)|m#eq#8:a(h,k)-d(h,m)>= C(h,m,k)))); @for(jalur(h)|h#eq#9:@for(kereta(k)|k#eq#6:@for(kereta(m)|m#eq#11:a(h,k)-d(h,m)>= C(h,m,k)))); !kendala4; !untuk kereta k = 1; d(1,1)=a(4,1);d(4,1)=a(5,1);d(5,1)=a(6,1);d(6,1)=a(8,1);d(8,1)=a(9,1);d(9,1)=a(10, 1);d(10,1)=a(11,1);d(11,1)=a(12,1);d(12,1)=a(14,1);d(14,1)=a(15,1);d(15,1)=a(16,1) ;d(16,1)=a(17,1);d(17,1)=a(20,1);d(20,1)=a(21,1);d(21,1)=a(22,1);d(22,1)=a(24,1);d (24,1)=a(25,1);d(25,1)=a(26,1);d(26,1)=a(27,1);d(27,1)=a(28,1);d(28,1)=a(30,1);d(3 0,1)=a(31,1);d(31,1)=a(32,1);d(32,1)=a(33,1); !untuk kereta k = 2; d(3,2)=a(4,2);d(4,2)=a(5,2);d(5,2)=a(6,2);d(6,2)=a(7,2);d(7,2)=a(9,2);d(9,2)=a(10, 2);d(10,2)=a(11,2);d(11,2)=a(13,2);d(13,2)=a(14,2);d(14,2)=a(15,2);d(15,2)=a(16,2) ;d(16,2)=a(17,2);d(17,2)=a(20,2);d(20,2)=a(21,2);d(21,2)=a(22,2);d(22,2)=a(23,2);d (23,2)=a(25,2);d(25,2)=a(26,2);d(26,2)=a(27,2);d(27,2)=a(28,2);d(28,2)=a(30,2);d(3 0,2)=a(31,2);d(31,2)=a(32,2);d(32,2)=a(35,2); !untuk kereta k = 3; d(2,3)=a(4,3);d(4,3)=a(5,3);d(5,3)=a(6,3);d(6,3)=a(8,3);d(8,3)=a(9,3);d(9,3)=a(10, 3);d(10,3)=a(11,3);d(11,3)=a(12,3);d(12,3)=a(14,3);d(14,3)=a(15,3);d(15,3)=a(16,3) ;d(16,3)=a(19,3);d(19,3)=a(20,3);d(20,3)=a(21,3);d(21,3)=a(22,3);d(22,3)=a(23,3);d (23,3)=a(25,3);d(25,3)=a(26,3);d(26,3)=a(27,3);d(27,3)=a(29,3);d(29,3)=a(30,3);d(3 0,3)=a(31,3);d(31,3)=a(32,3);d(32,3)=a(33,3); !untuk kereta k = 4; d(1,4)=a(4,4);d(4,4)=a(5,4);d(5,4)=a(6,4);d(6,4)=a(7,4);d(7,4)=a(9,4);d(9,4)=a(10, 4);d(10,4)=a(11,4);d(11,4)=a(12,4);d(12,4)=a(14,4);d(14,4)=a(15,4);d(15,4)=a(16,4) ;d(16,4)=a(18,4);d(18,4)=a(20,4);d(20,4)=a(21,4);d(21,4)=a(22,4);d(22,4)=a(24,4);d (24,4)=a(25,4);d(25,4)=a(26,4);d(26,4)=a(27,4);d(27,4)=a(28,4);d(28,4)=a(30,4);d(3 0,4)=a(31,4);d(31,4)=a(32,4);d(32,4)=a(34,4); !untuk kereta k = 5; d(3,5)=a(4,5);d(4,5)=a(5,5);d(5,5)=a(6,5);d(6,5)=a(8,5);d(8,5)=a(9,5);d(9,5)=a(10, 5);d(10,5)=a(11,5);d(11,5)=a(12,5);d(12,5)=a(14,5);d(14,5)=a(15,5);d(15,5)=a(16,5) ;d(16,5)=a(18,5);d(18,5)=a(20,5);d(20,5)=a(21,5);d(21,5)=a(22,5);d(22,5)=a(23,5);d (23,5)=a(25,5);d(25,5)=a(26,5);d(26,5)=a(27,5);d(27,5)=a(29,5);d(29,5)=a(30,5);d(3 0,5)=a(31,5);d(31,5)=a(32,5);d(32,5)=a(33,5); !untuk kereta k = 6; d(2,6)=a(4,6);d(4,6)=a(5,6);d(5,6)=a(6,6);d(6,6)=a(7,6);d(7,6)=a(9,6);d(9,6)=a(10, 6);d(10,6)=a(11,6);d(11,6)=a(13,6);d(13,6)=a(14,6);d(14,6)=a(15,6);d(15,6)=a(16,6) ;d(16,6)=a(17,6);d(17,6)=a(20,6);d(20,6)=a(21,6);d(21,6)=a(22,6);d(22,6)=a(23,6);d (23,6)=a(25,6);d(25,6)=a(26,6);d(26,6)=a(27,6);d(27,6)=a(29,6);d(29,6)=a(30,6);d(3 0,6)=a(31,6);d(31,6)=a(32,6);d(32,6)=a(35,6); !untuk kereta k = 7; d(34,7)=a(32,7);d(32,7)=a(31,7);d(31,7)=a(30,7);d(30,7)=a(28,7);d(28,7)=a(27,7);d( 27,7)=a(26,7);d(26,7)=a(25,7);d(25,7)=a(23,7);d(23,7)=a(22,7);d(22,7)=a(21,7);d(21 ,7)=a(20,7);d(20,7)=a(19,7);d(19,7)=a(16,7);d(16,7)=a(15,7);d(15,7)=a(14,7);d(14,7 )=a(12,7);d(12,7)=a(11,7);d(11,7)=a(10,7);d(10,7)=a(9,7);d(9,7)=a(7,7);d(7,7)=a(6, 7);d(6,7)=a(5,7);d(5,7)=a(4,7);d(4,7)=a(2,7); !untuk kereta k = 8; d(33,8)=a(32,8);d(32,8)=a(31,8);d(31,8)=a(30,8);d(30,8)=a(29,8);d(29,8)=a(27,8);d( 27,8)=a(26,8);d(26,8)=a(25,8);d(25,8)=a(24,8);d(24,8)=a(22,8);d(22,8)=a(21,8);d(21 ,8)=a(20,8);d(20,8)=a(18,8);d(18,8)=a(16,8);d(16,8)=a(15,8);d(15,8)=a(14,8);d(14,8 )=a(13,8);d(13,8)=a(11,8);d(11,8)=a(10,8);d(10,8)=a(9,8);d(9,8)=a(8,8);d(8,8)=a(6, 8);d(6,8)=a(5,8);d(5,8)=a(4,8);d(4,8)=a(3,8); !untuk kereta k = 9; d(35,9)=a(32,9);d(32,9)=a(31,9);d(31,9)=a(30,9);d(30,9)=a(29,9);d(29,9)=a(27,9);d( 27,9)=a(26,9);d(26,9)=a(25,9);d(25,9)=a(23,9);d(23,9)=a(22,9);d(22,9)=a(21,9);d(21 ,9)=a(20,9);d(20,9)=a(17,9);d(17,9)=a(16,9);d(16,9)=a(15,9);d(15,9)=a(14,9);d(14,9

22

)=a(13,9);d(13,9)=a(11,9);d(11,9)=a(10,9);d(10,9)=a(9,9);d(9,9)=a(7,9);d(7,9)=a(6, 9);d(6,9)=a(5,9);d(5,9)=a(4,9);d(4,9)=a(2,9); !untuk kereta k = 10; d(33,10)=a(32,10);d(32,10)=a(31,10);d(31,10)=a(30,10);d(30,10)=a(28,10);d(28,10)=a (27,10);d(27,10)=a(26,10);d(26,10)=a(25,10);d(25,10)=a(24,10);d(24,10)=a(22,10);d( 22,10)=a(21,10);d(21,10)=a(20,10);d(20,10)=a(19,10);d(19,10)=a(16,10);d(16,10)=a(1 5,10);d(15,10)=a(14,10);d(14,10)=a(12,10);d(12,10)=a(11,10);d(11,10)=a(10,10);d(10 ,10)=a(9,10);d(9,10)=a(8,10);d(8,10)=a(6,10);d(6,10)=a(5,10);d(5,10)=a(4,10);d(4,1 0)=a(1,10); !untuk kereta k = 11; d(35,11)=a(32,11);d(32,11)=a(31,11);d(31,11)=a(30,11);d(30,11)=a(29,11);d(29,11)=a (27,11);d(27,11)=a(26,11);d(26,11)=a(25,11);d(25,11)=a(24,11);d(24,11)=a(22,11);d( 22,11)=a(21,11);d(21,11)=a(20,11);d(20,11)=a(17,11);d(17,11)=a(16,11);d(16,11)=a(1 5,11);d(15,11)=a(14,11);d(14,11)=a(13,11);d(13,11)=a(11,11);d(11,11)=a(10,11);d(10 ,11)=a(9,11);d(9,11)=a(8,11);d(8,11)=a(6,11);d(6,11)=a(5,11);d(5,11)=a(4,11);d(4,1 1)=a(3,11); !untuk kereta k = 12; d(34,12)=a(32,12);d(32,12)=a(31,12);d(31,12)=a(30,12);d(30,12)=a(28,12);d(28,12)=a (27,12);d(27,12)=a(26,12);d(26,12)=a(25,12);d(25,12)=a(23,12);d(23,12)=a(22,12);d( 22,12)=a(21,12);d(21,12)=a(20,12);d(20,12)=a(19,12);d(19,12)=a(16,12);d(16,12)=a(1 5,12);d(15,12)=a(14,12);d(14,12)=a(12,12);d(12,12)=a(11,12);d(11,12)=a(10,12);d(10 ,12)=a(9,12);d(9,12)=a(7,12);d(7,12)=a(6,12);d(6,12)=a(5,12);d(5,12)=a(4,12);d(4,1 2)=a(2,12); !kendala5; !@for(jalur(h):@for(kereta(k):d(h,k)-a(i,k)=delay(k)+trip(k))); @for(jalur(h)|h#eq#33:@for(jalur(i)|i#eq#1:@for(kereta(k)|k#eq#1:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#35:@for(jalur(i)|i#eq#3:@for(kereta(k)|k#eq#2:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#33:@for(jalur(i)|i#eq#2:@for(kereta(k)|k#eq#3:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#34:@for(jalur(i)|i#eq#1:@for(kereta(k)|k#eq#4:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#33:@for(jalur(i)|i#eq#3:@for(kereta(k)|k#eq#5:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#35:@for(jalur(i)|i#eq#2:@for(kereta(k)|k#eq#6:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#2:@for(jalur(i)|i#eq#34:@for(kereta(k)|k#eq#7:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#3:@for(jalur(i)|i#eq#33:@for(kereta(k)|k#eq#8:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#2:@for(jalur(i)|i#eq#35:@for(kereta(k)|k#eq#9:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#1:@for(jalur(i)|i#eq#33:@for(kereta(k)|k#eq#10:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#3:@for(jalur(i)|i#eq#35:@for(kereta(k)|k#eq#11:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h)|h#eq#2:@for(jalur(i)|i#eq#34:@for(kereta(k)|k#eq#12:d(h,k)-a(i,k)= delay(k)+trip(k)))); @for(jalur(h):@for(kereta(k):@gin(y(h,k)))); @for(kereta(k):@gin(delay(k))); end

Global optimal solution found at iteration: 17 Objective value: 8.000000 Variable DELAY( 2) DELAY( 6) DELAY( 8) D( 1, 1) D( 1, 4) D( 1, 10) D( 2, 3) D( 2, 6)

Value 4.000000 2.000000 2.000000 22.00000 77.00000 132.0000 55.00000 167.0000

Reduced Cost 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000

D( D( D( D( D( D( D( D( D( D( D( D( D(

2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4,

7) 9) 12) 2) 5) 8) 11) 1) 2) 3) 4) 5) 6)

76.00000 130.0000 242.0000 34.00000 132.0000 49.00000 185.0000 23.00000 35.00000 57.00000 79.00000 133.0000 169.0000

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

23

D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D(

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

72.00000 47.00000 126.0000 130.0000 183.0000 238.0000 24.00000 40.00000 59.00000 81.00000 134.0000 173.0000 70.00000 46.00000 124.0000 129.0000 182.0000 236.0000 25.00000 41.00000 61.00000 83.00000 135.0000 175.0000 68.00000 45.00000 122.0000 128.0000 181.0000 234.0000 43.00000 87.00000 179.0000 66.00000 120.0000 232.0000 27.00000 65.00000 137.0000 44.00000 127.0000 180.0000 29.00000 45.00000 69.00000 91.00000 139.0000 183.0000 62.00000 42.00000 116.0000 125.0000 178.0000 228.0000 31.00000 47.00000 73.00000 95.00000 141.0000 187.0000 58.00000 40.00000 112.0000 123.0000 176.0000 224.0000 33.00000 49.00000 77.00000 99.00000 143.0000 191.0000 54.00000 38.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 0.000000


11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,

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

108.0000 121.0000 174.0000 220.0000 35.00000 81.00000 103.0000 145.0000 50.00000 119.0000 216.0000 51.00000 195.0000 36.00000 104.0000 172.0000 36.00000 52.00000 83.00000 105.0000 146.0000 197.0000 46.00000 34.00000 100.0000 117.0000 170.0000 212.0000 37.00000 53.00000 85.00000 107.0000 147.0000 199.0000 44.00000 33.00000 98.00000 116.0000 169.0000 210.0000 38.00000 54.00000 87.00000 109.0000 148.0000 201.0000 42.00000 32.00000 96.00000 115.0000 168.0000 208.0000 40.00000 56.00000 205.0000 94.00000 167.0000 113.0000 150.0000 31.00000 91.00000 40.00000 114.0000 206.0000 42.00000 58.00000 95.00000 117.0000 152.0000 209.0000 36.00000 29.00000 90.00000 112.0000

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

24


20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,

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

165.0000 202.0000 44.00000 60.00000 99.00000 121.0000 154.0000 213.0000 32.00000 27.00000 86.00000 110.0000 163.0000 198.0000 46.00000 62.00000 103.0000 125.0000 156.0000 217.0000 28.00000 25.00000 82.00000 108.0000 161.0000 194.0000 64.00000 107.0000 158.0000 221.0000 24.00000 78.00000 190.0000 48.00000 129.0000 23.00000 106.0000 159.0000 49.00000 65.00000 109.0000 131.0000 159.0000 223.0000 20.00000 21.00000 74.00000 104.0000 157.0000 186.0000 50.00000 66.00000 111.0000 133.0000 160.0000 225.0000 18.00000 20.00000 72.00000 103.0000 156.0000 184.0000 51.00000 67.00000 113.0000 135.0000 161.0000 227.0000 16.00000 19.00000 70.00000 102.0000 155.0000 182.0000

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

D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( D( A( A( A( A( A( A( A( A( A( A( A( A( A( A(

28, 1) 28, 2) 28, 4) 28, 7) 28, 10) 28, 12) 29, 3) 29, 5) 29, 6) 29, 8) 29, 9) 29, 11) 30, 1) 30, 2) 30, 3) 30, 4) 30, 5) 30, 6) 30, 7) 30, 8) 30, 9) 30, 10) 30, 11) 30, 12) 31, 1) 31, 2) 31, 3) 31, 4) 31, 5) 31, 6) 31, 7) 31, 8) 31, 9) 31, 10) 31, 11) 31, 12) 32, 1) 32, 2) 32, 3) 32, 4) 32, 5) 32, 6) 32, 7) 32, 8) 32, 9) 32, 10) 32, 11) 32, 12) 33, 1) 33, 3) 33, 5) 33, 8) 33, 10) 34, 4) 34, 7) 34, 12) 35, 2) 35, 6) 35, 9) 35, 11) 1, 1) 1, 4) 1, 10) 2, 3) 2, 6) 2, 7) 2, 9) 2, 12) 3, 2) 3, 5) 3, 8) 3, 11) 4, 1) 4, 2)

53.00000 69.00000 139.0000 14.00000 101.0000 180.0000 117.0000 163.0000 231.0000 18.00000 68.00000 154.0000 54.00000 70.00000 119.0000 141.0000 164.0000 233.0000 10.00000 16.00000 64.00000 99.00000 152.0000 176.0000 55.00000 71.00000 121.0000 143.0000 165.0000 235.0000 8.000000 15.00000 62.00000 98.00000 151.0000 174.0000 56.00000 72.00000 123.0000 145.0000 166.0000 237.0000 6.000000 14.00000 60.00000 97.00000 150.0000 172.0000 58.00000 127.0000 168.0000 13.00000 96.00000 149.0000 4.000000 170.0000 74.00000 241.0000 58.00000 149.0000 20.00000 73.00000 130.0000 51.00000 163.0000 72.00000 126.0000 238.0000 32.00000 130.0000 47.00000 183.0000 22.00000 34.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 0.000000

25

A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A(

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

55.00000 77.00000 132.0000 167.0000 70.00000 46.00000 124.0000 129.0000 182.0000 236.0000 23.00000 35.00000 57.00000 79.00000 133.0000 169.0000 68.00000 45.00000 122.0000 128.0000 181.0000 234.0000 24.00000 40.00000 59.00000 81.00000 134.0000 173.0000 66.00000 44.00000 120.0000 127.0000 180.0000 232.0000 41.00000 83.00000 175.0000 62.00000 116.0000 228.0000 25.00000 61.00000 135.0000 42.00000 125.0000 178.0000 27.00000 43.00000 65.00000 87.00000 137.0000 179.0000 58.00000 40.00000 112.0000 123.0000 176.0000 224.0000 29.00000 45.00000 69.00000 91.00000 139.0000 183.0000 54.00000 38.00000 108.0000 121.0000 174.0000 220.0000 31.00000 47.00000 73.00000 95.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 0.000000


11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20,

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

141.0000 187.0000 50.00000 36.00000 104.0000 119.0000 172.0000 216.0000 33.00000 77.00000 99.00000 143.0000 46.00000 117.0000 212.0000 49.00000 191.0000 34.00000 100.0000 170.0000 35.00000 51.00000 81.00000 103.0000 145.0000 195.0000 44.00000 33.00000 98.00000 116.0000 169.0000 210.0000 36.00000 52.00000 83.00000 105.0000 146.0000 197.0000 42.00000 32.00000 96.00000 115.0000 168.0000 208.0000 37.00000 53.00000 85.00000 107.0000 147.0000 199.0000 40.00000 31.00000 94.00000 114.0000 167.0000 206.0000 38.00000 54.00000 201.0000 90.00000 165.0000 109.0000 148.0000 29.00000 87.00000 36.00000 112.0000 202.0000 40.00000 56.00000 91.00000 113.0000 150.0000 205.0000

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

26


20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,

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

32.00000 27.00000 86.00000 110.0000 163.0000 198.0000 42.00000 58.00000 95.00000 117.0000 152.0000 209.0000 28.00000 25.00000 82.00000 108.0000 161.0000 194.0000 44.00000 60.00000 99.00000 121.0000 154.0000 213.0000 24.00000 23.00000 78.00000 106.0000 159.0000 190.0000 62.00000 103.0000 156.0000 217.0000 20.00000 74.00000 186.0000 46.00000 125.0000 21.00000 104.0000 157.0000 48.00000 64.00000 107.0000 129.0000 158.0000 221.0000 18.00000 20.00000 72.00000 103.0000 156.0000 184.0000 49.00000 65.00000 109.0000 131.0000 159.0000 223.0000 16.00000 19.00000 70.00000 102.0000 155.0000 182.0000 50.00000 66.00000 111.0000 133.0000 160.0000 225.0000 14.00000 18.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 0.000000

A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( A( Y( Y( Y(

27, 9) 27, 10) 27, 11) 27, 12) 28, 1) 28, 2) 28, 4) 28, 7) 28, 10) 28, 12) 29, 3) 29, 5) 29, 6) 29, 8) 29, 9) 29, 11) 30, 1) 30, 2) 30, 3) 30, 4) 30, 5) 30, 6) 30, 7) 30, 8) 30, 9) 30, 10) 30, 11) 30, 12) 31, 1) 31, 2) 31, 3) 31, 4) 31, 5) 31, 6) 31, 7) 31, 8) 31, 9) 31, 10) 31, 11) 31, 12) 32, 1) 32, 2) 32, 3) 32, 4) 32, 5) 32, 6) 32, 7) 32, 8) 32, 9) 32, 10) 32, 11) 32, 12) 33, 1) 33, 3) 33, 5) 33, 8) 33, 10) 34, 4) 34, 12) 35, 2) 35, 6) 35, 9) 35, 11) 5, 2) 5, 6) 33, 8)

Row 2 3 4 … 915 916

68.00000 101.0000 154.0000 180.0000 51.00000 67.00000 135.0000 10.00000 99.00000 176.0000 113.0000 161.0000 227.0000 16.00000 64.00000 152.0000 53.00000 69.00000 117.0000 139.0000 163.0000 231.0000 8.000000 15.00000 62.00000 98.00000 151.0000 174.0000 54.00000 70.00000 119.0000 141.0000 164.0000 233.0000 6.000000 14.00000 60.00000 97.00000 150.0000 172.0000 55.00000 71.00000 121.0000 143.0000 165.0000 235.0000 4.000000 13.00000 58.00000 96.00000 149.0000 170.0000 56.00000 123.0000 166.0000 9.000000 94.00000 145.0000 166.0000 72.00000 237.0000 54.00000 147.0000 4.000000 2.000000 2.000000

Slack or Surplus 0.000000 0.000000 0.000000 … 0.000000 0.000000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 Dual Price 0.000000 0.000000 0.000000 … 0.000000 0.000000

27

PENJADWALAN KERETA API MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER DWI SETIANTO

Recommend Documents