2
II LANDASAN TEORI Untuk membuat model optimasi penjadwalan bus Transjakarta diperlukan pemahaman beberapa teori. Berikut ini akan dibahas satu per satu. 2.1 Penjadwalan 2.1.1 Definisi Penjadwalan Penjadwalan merupakan proses pengorganisasian, pemilihan, dan penetapan penggunaan sumberdaya dalam rangka melaksanakan semua aktivitas yang diperlukan untuk menghasilkan output yang diinginkan pada saat yang telah direncanakan, dengan pembatas waktu dan hubungan antaraktivitas dan sumberdaya tertentu. (Morton & Pentico 1993) 2.1.2 Tujuan Penjadwalan Beberapa tujuan penjadwalan yang penting yaitu: 1. meningkatkan utilitas atau kegunaan sumberdaya, 2. mengurangi total waktu proses seluruh pekerjaan (makespan), 3. mengurangi rata-rata banyaknya pekerjaan yang menunggu untuk diproses oleh suatu sumberdaya, 4. meminimumkan keterlambatan pemenuhan suatu job. (Bedworth & Bailey 1986) 2.1.3 Kriteria Optimalitas Penjadwalan Pemilihan kriteria optimalitas merupakan tahap di mana seseorang harus memilih output yang diinginkan oleh pengambil keputusan dalam pelaksanaan penjadwalan produksi. Secara umum, kriteria optimalitas dalam proses penjadwalan dapat dikelompokkan menjadi tiga bagian. 1. Berkaitan dengan waktu Beberapa kriteria yang terkait dengan waktu ialah minimasi rata-rata flow time¸ minimasi makespan, dan minimasi tardiness, 2. Berkaitan dengan biaya Kriteria ini lebih menekankan pada unsur biaya, dan kurang atau bahkan tidak memperhatikan kriteria waktu yang ada sehingga dengan suatu penjadwalan produksi tertentu diharapkan ongkos yang minimal. 3. Kriteria gabungan Beberapa kriteria optimalitas dapat digabungkan dan dapat dikombinasikan sehingga menjadi multi kriteria. (Heizer & Render 2010)
2.2 Bus Rapid Transit (BRT) Sistem BRT merupakan sistem transportasi publik yang digunakan sebagai sistem transportasi menuju transportasi berkelanjutan. BRT merupakan moda angkutan yang berorientasi pada layanan pelanggan dengan mengombinasikan stasiun, kendaraan, perencanaan, dan elemen-elemen sistem transportasi yang canggih ke dalam sebuah sistem yang terpadu dan memiliki satu identitas unik. (ITDP 2007) Ciri-ciri utama sistem BRT meliputi: 1. jalur bus terpisah, 2. naik dan turun kendaraan yang cepat, 3. stasiun dan terminal yang bersih, aman, dan nyaman, 4. penarikan ongkos sebelum berangkat yang efisien, 5. penandaan yang jelas dan mudah dikenali, 6. tampilan informasi yang serta merta (real time). (Wright 2003) 2.3 Transjakarta BLUT (Badan Layanan Umum Transjakarta) ialah lembaga yang dibentuk oleh pemerintah Provinsi DKI Jakarta untuk mengelola layanan angkutan umum massal dengan menggunakan moda bus. Pembangunan BRT merupakan salah satu strategi dari Pola Transportasi Makro (PTM) untuk meningkatkan pelayanan dan penyediaan jasa transportasi yang aman, terpadu, tertib, lancar, nyaman, ekonomis, efisien, efektif dan terjangkau oleh masyarakat. BRT yang difasilitasi dengan jalur, armada bus dan infrastruktur yang dibangun khusus, sistem tiket elektronik yang saat ini dioperasikan di Koridor 1-3 serta keramahan petugas ialah layanan yang diberikan kepada masyarakat untuk dapat menggunakan angkutan umum yang lebih baik. Kini masyarakat mempunyai alternatif angkutan umum yang memberikan kemudahan menjangkau seluruh wilayah Jakarta dengan pelayanan yang berbeda dibandingkan dengan angkutan umum lainnya. Sistem Transjakarta Busway terdiri dari sarana dan prasarana yang memadai, sistem operasi dan pengendalian bus yang efektif,
3
sistem tiket yang terkomputerisasi, sistem pengamanan yang handal dan petugas yang terlatih. Mulai dari perencanaan, pembangunan dan pengelolaan sistem Transjakarta dilakukan oleh Pemerintah Daerah DKI Jakarta, sementara kegiatan operasional bus, operasional tiket dan kegiatan penunjang lainnya dilaksanakan bekerjasama dengan pihak operator yaitu : PT Jakarta Express Trans, PT Trans Batavia, PT Jakarta Trans Metropolitan, PT Jakarta Mega Trans, PT Prima Jasa Perdana Raya Utama dan PT Eka Sari Lorena Transport, sehingga pemerintah (BLUT) hanya membayar biaya per kilometer kepada operator bus yang menangani di setiap koridornya. Transjakarta Busway memiliki 141 halte di sepanjang sepuluh koridor busway dengan ketinggian platform 110 centimeter dari tinggi permukaan jalan agar tersedia akses yang rata dengan bus. Setiap halte busway dilengkapi dengan akses untuk pejalan kaki yang terhubung dengan jembatan penyeberangan orang, yang dirancang khusus untuk mempermudah pengguna layanan busway. Sarana dan prasarana yang tersedia di halte antara lain loket pembelian tiket dan pintu barrier sebagai jalan masuk dan jalan keluar bagi pengguna jasa layanan. Selain itu disediakan fasilitas tempat sampah, informasi rute dan pintu otomatis untuk memberikan kenyamanan dan keamanan saat menunggu di halte. Saat ini banyaknya armada bus adalah 426 unit dan dioperasikan berdasarkan rencana operasi yang terjadwal di 10 koridor. Bus yang diberangkatkan pada titik awal diatur sesuai dengan waktu yang telah ditentukan baik pada jam sibuk maupun jam tidak sibuk. Selain rute Koridor 1 dan 8, untuk meningkatkan pelayanan dan mengurangi kepadatan penumpang di halte transit, maka BLUT menambah rute-rute langsung yang berdasarkan pada sistem jaringan dan dapat diakses penumpang sesuai dengan tujuan perjalanannya. 2.4 Pemrograman Linear Pemrograman linear (PL) atau linear programming merupakan metode penyelesaian masalah pengoptimuman dengan tujuan yang diinginkan terhadap kendala tertentu. Model PL meliputi pengoptimuman suatu fungsi linear terhadap kendala linear. Salah satunya dapat menjadi metode penyelesaian dalam masalah pengoptimuman penjadwalan BRT.
Pemrograman linear terdiri atas tiga (3) komponen utama, yaitu: a. variabel keputusan yang telah ditentukan, b. tujuan pengoptimuman yang akan dibutuhkan baik maksimisasi maupun minimisasi, c. kendala untuk menentukan solusi yang memenuhi. (Taha 2007) Definisi 1 (Bentuk Standar PL) Suatu PL dikatakan berbentuk standar jika berbentuk: min z = cTx terhadap Ax = b (1) x≥0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga sebagai matriks kendala. (Nash & Sofer 1996) Pemrograman linear (PL) ialah suatu masalah optimisasi yang memenuhi kendala sebagai berikut: a. tujuan masalah tersebut ialah 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 x i , pembatasan tanda menentukan x i harus taknegatif (x i ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign). (Winston 2004) 2.4.1 Solusi Pemrograman Linear Untuk menyelesaikan suatu masalah pemrograman linear (PL), metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimal. Metode simpleks dikembangkan oleh Dantzig pada tahun 1947. Metode simpleks merupakan metode yang umum digunakan untuk menyelesaikan masalah pemrograman linear, yaitu berupa metode berulang (iteratif) dimana dalam setiap pengulangan (iterasi) berkaitan dengan satu pemecahan dasar (solusi basis). Pada PL (1), vektor x yang memenuhi kendala Ax=b disebut sebagai solusi fisibel dari PL (1). Misalkan matriks A dapat
4
dinyatakan sebagai A=(B N), dengan B ialah matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis PL (1). Jika vektor x dapat dinyatakan sebagai vektor x = xB , dengan x B ialah vektor xN variabel basis dan x N ialah vektor nonbasis, maka Ax = b dapat dinyatakan Sebagai Ax = ( B N ) xB
(2)
xN
= Bx B + Nx N = b . Karena B ialah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai : (3) x B = B -1b − B -1 Nx N Kemudian, fungsi objektifnya berubah menjadi:
min z = cTB x B + cTN x N (Winston 2004) Definisi 2 (Solusi Basis) Solusi basis ialah solusi PL yang didapatkan dengan mengatur variabel n − m sama dengan nol dan nilai untuk penyelesaiannya adalah dari sisa variabel m. Hal ini dengan mengasumsikan bahwa mengatur variabel n − m sama dengan nol akan membuat nilai yang unik untuk sisa variabel m atau sejenisnya, kolom-kolom untuk sisa dari variabel m adalah bebas linear. (Winston 2004) Definisi 3 (Solusi Fisibel Basis) Solusi fisibel basis ialah solusi basis pada PL yang semua variabel-variabelnya taknegatif. (Winston 2004) Ilustrasi solusi basis dan solusi basis fisibel diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan PL berikut : min z = −2 x1 − 4 x2 , terhadap − 2 x1 + x2 + x3 = 5, − x1 + 2 x2 + x4 = 7, x1 + x5 = 9,
x1 , x2 , x3 , x4 , x5 ≥ 0.
(4)
Dari PL tersebut didapatkan : −2 1 1 0 0 5 A= − 1 2 0 1 0 , b = 7 . 1 0 0 0 1 9
Misalkan dipilih X B = (x 1 x 2 x 3 )T dan X N = (x 4 x 5 )T, maka matriks basis 0 1 0 −2 1 1 B -1 = 0 1 / 2 1 / 2 , B = −1 2 0 , 1 −1 / 2 3 / 2 1 0 0
0 0 N= 1 0 0 1
cTB = (−2 −4 0), cTN = (0 0)
Dengan menggunakan matriks basis tersebut, diperoleh x N = (0 0) , T
x B = B b = (9 8 15)T , -1
(5) z = cTB B -1b = −50. Solusi (5) merupakan solusi basis, karena solusi tersebut memenuhi kendala pada PL (4) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5) yaitu B, bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (5) juga merupakan solusi basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Definisi 4 (Daerah Fisibel) Daerah fisibel untuk PL ialah himpunan bilangan yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004) Definisi 5 (Solusi Optimal) Untuk masalah maksimisasi, solusi optimal pada PL ialah suatu titik pada daerah fisibel dengan nilai fungsi objektif paling besar, sedangkan untuk masalah minimisasi, solusi optimal ialah suatu titik pada daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) 2.5 Pemrograman Linear Integer Pemrograman Linear Integer (PLI) ialah 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,
5
maka disebut mixed integer linear programming (MILP). Semua variabel dalam PLI 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 pemprograman 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 minimisasi, nilai optimum fungsi objektif relaksasi-PL lebih kecil atau sama dengan nilai optimum fungsi objektif PLI. (Winston 2004) 2.6 Metode Branch and Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimum dari masalah PLI digunakan software LINGO 11.0 yaitu program untuk menentukan solusi model linear, nonlinear, dan optimisasi integer dengan lebih cepat, mudah, dan lebih efisien. Software LINGO 11.0 menggunakan metode branch and bound untuk menyelesaikan masalah PLI. Prinsip dasar metode branch and bound ialah memecah daerah fisibel dari masalah relaksasi-PL dengan membuat subproblemsubproblem. Daerah fisibel suatu pemrograman linear ialah daerah yang memuat titik-titik yang dapat memenuhi kendala linear masalah pemrograman linear. 1. Branch Branching (pencabangan) ialah proses membagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi. 2. Bound Bounding (pembatasan) ialah 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. 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 nilai fungsi objektif optimum untuk PLI 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 dalam 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, artinya fungsi objektif dan semua variabelnya sudah bernilai integer. Sebelumnya akan dibahas terlebih dulu pengertian subproblem yang terukur. Menurut Winston (2004), suatu subproblem dikatakan terukur (fathomed) jika terdapat situasi sebagai berikut. 1. Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimum untuk PLI. 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) nilai fungsi objektif optimum bagi masalah PLI pada saat itu. Bisa jadi subproblem ini menghasilkan solusi optimum untuk masalah PLI. 3. Nilai fungsi objektif optimum untuk subproblem tersebut tidak melebihi (untuk masalah maksimisasi) batas bawah saat itu, maka subproblem ini dapat dieliminasi. Berikut ini ialah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch-and-bound. • Langkah 0 Didefinisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) PLI yang optimum. Pada awalnya ditetapkan z = −∞ dan i = 0. • Langkah 1 Subproblem PL (i) dipilih sebagai bagian masalah berikutnya untuk diperiksa.
6
Subproblem PL (i) diselesaikan dan diukur dengan kondisi yang sesuai.
X2
Jika PL (i) terukur, batas bawah z diperbarui jika solusi PLI yang lebih baik ditemukan. Jika tidak, subproblem baru i dipilih dan Langkah 1 diulangi. Jika semua subproblem telah diperiksa, maka proses dihentikan. b) Jika PL (i) tidak terukur, proses dilanjutkan ke Langkah 2 untuk melakukan pencabangan PL (i). a)
•
Langkah 2
Dipilih salah satu variabel x j dengan nilai
Daerah fisibel
X1
Gambar 1 Daerah fisibel (daerah yang diarsir) untuk relaksasi-PL dari PLI (6).
*
optimumnya ialah x j yang tidak memenuhi batasan integer dalam solusi PL (i) . Bidang x*j < x j < x*j + 1 dipecah menjadi dua subproblem, yaitu x j ≤ x*j dan x*j ≥ x*j + 1 , dengan x*j didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan
x*j . Jika PL (i) masih tidak terukur, maka kembali ke Langkah 1. (Taha 1996) Untuk memudahkan pemahaman metode branch-and-bound diberikan contoh sebagai berikut.
Hal ini diilustrasikan secara grafis pada Gambar 2.
Contoh 2 Misalkan diberikan PLI berikut: maksimumkan z = 3x 1 +5x 2, dengan kendala x 1 +3x 2 ≤ 15, 5x 1 +6x 2 ≤ 64, x 1 , x 2 ≥ 0, x 1 , x 2 integer.
Langkah berikutnya ialah memartisi daerah fisibel relaksasi-PL menjadi dua bagian berdasarkan variabel yang berbentuk pecahan (non-integer). Karena nilai dari kedua variabel yang diperoleh bukan integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalnya dipilih x 2 sebagai dasar pencabangan. Jika masalah relaksasi-PL diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: • Subproblem 2: Subproblem 1 ditambah kendala x 2 ≤ 1; • Subproblem 3: Subproblem 1 ditambah kendala x 2 ≥ 2;
X2
Subproblem 3 (6)
Solusi optimum relaksasi-PL dari masalah PLI (6) ialah x 1 = 11,33, x 2 = 1,2 dan z = 40,11 (detail pengitungan dapat dilihat pada Lampiran 1). Batas atas nilai optimum fungsi objektif masalah ini ialah z = 40,11. Daerah fisibel relaksasi-PL masalah PLI (6) ditunjukkan pada Gambar 1 (daerah yang diarsir) sedangkan titik-titik merupakan solusi fisibel masalah PLI (6).
Subproblem 2 X1
Gambar 2 Daerah fisibel untuk Subproblem 2 dan Subproblem 3. Setiap titik (solusi) fisibel dari PLI (6) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan Subproblem 3 dikatakan dicabangkan oleh x 2 . Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih Subproblem 2, kemudian diselesaikan. Solusi optimum untuk
7
Subproblem 2 ini ialah x 1 =11,6, x 2 = 1 dan z = 39,8 (detail penghitungan dapat dilihat pada Lampiran 1). Karena solusi optimal yang dihasilkan Subproblem 2 bukan solusi integer, maka dipilih pencabangan pada Subproblem 2 atas x 1 , sehingga diperoleh dua subproblem lagi, yaitu: • Subproblem 4: Subproblem 2 ditambah kendala x 1 ≤ 11; • Subproblem 5: Subproblem 2 ditambah kendala x 1 ≥12. Saat ini subproblem yang belum diselesaikan ialah Subproblem 3, 4, dan 5. Salah satu subproblem dipilih, misalnya dengan aturan LIFO (last in first out). Dengan adanya aturan ini berarti dipilih Subproblem 4 atau Subproblem 5. Subproblem 4 menghasilkan kandidat solusi optimal x 1 = 11, x 2 = 1 dan z = 38 yang berupa integer (detail penghitungan dapat dilihat pada Lampiran 1), sehingga kandidat solusi optimal dari PLI (6) ialah dari subproblem 4. Nilai z baru merupakan batas bawah baru bagi nilai optimal PLI (6). Karena aturan LIFO, dipilih Subproblem 5, yang kemudian menghasilkan solusi optimal x 1 = 12, x 2 = 0,67 dan z = 39,33 (detail penghitungan dapat dilihat pada Lampiran 1). Karena x 2 = 0,67 bukan integer, maka dilakukan kembali pencabangan atas x2 , sehingga diperoleh: • Subproblem 6: Subproblem 5 ditambah kendala x 2 ≤ 0; • Subproblem 7: Subproblem 5 ditambah kendala x 2 ≥ 1. Selanjutnya berdasarkan aturan LIFO, dipilih Subproblem 6. Subproblem yang dipilih menghasilkan solusi optimal x1 = 12,8 , x2 = 0 , dan z = 38, 4 (detail penghitungan dapat
dilihat pada Lampiran 1). Karena solusi optimal yang dihasilkan Subproblem 6 bukan solusi integer, maka dipilih pencabangan pada Subproblem 6 atas x1 , sehingga diperoleh dua subproblem lagi, yaitu: • Subproblem 8: Subproblem 6 ditambah kendala x 1 ≤ 12 ; • Subproblem 9: Subproblem 6 ditambah kendala x 1 ≥ 13. Sekarang dipilih subproblem yang belum diselesaikan, yaitu Subproblem 8, 9, dan 3. Berdasarkan aturan LIFO, dipilih Subproblem 8. Subproblem yang dipilih menghasilkan kandidat solusi optimal x 1 = 12, x 2 = 0 dan z = 36 (detail penghitungan dapat dilihat pada Lampiran 1). Nilai solusi optimal Subproblem 8 masih lebih kecil jika dibandingkan dengan nilai objektif pada Subproblem 4, maka kandidat solusi optimal dari PLI (6) tetap dari Subproblem 4. Tersisa tiga buah subproblem yaitu, Subproblem 9, 7, dan 3. Dengan aturan LIFO dipilih Subproblem 9 lalu Subproblem 7. Karena Subproblem 9 dan 7 takfisibel (detail penghitungan dapat dilihat pada Lampiran 1), maka Subproblem 9 dan 7 tidak dapat menghasilkan solusi optimal; yang tersisa hanya Subproblem 3. Dari tiga kandidat solusi optimal, yaitu solusi dari Subproblem 3, 4 dan 8, akan dipilih satu di antaranya untuk menjadi solusi optimum masalah PLI (6). Solusi optimum pada PLI (6) ialah solusi Subproblem 4 dengan x 1 = 11, x 2 = 1 dan z = 38, karena Subproblem 4 memiliki nilai z lebih baik daripada nilai z Subproblem 3 & 8. Pohon pencabangan yang menunjukkan proses penyelesaian masalah PLI (6) secara keseluruhan ditunjukkan pada Gambar 3.
