1
PENYELESAIAN MASALAH PELANGSIRAN UNIT KERETA PENUMPANG PADA STASIUN KERETA API DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM
Oleh:
DINA LIANITA SARI G54102025
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2006
2
ABSTRAK DINA LIANITA SARI. Penyelesaian Masalah Pelangsiran Unit Kereta Penumpang pada Stasiun Kereta Api dengan Menggunakan Teknik Pembangkitan Kolom. Dibimbing oleh FARIDA HANUM dan DONNY CITRA LESMANA. Dalam suatu stasiun kereta api, pada jam-jam tertentu terdapat kereta api penumpang yang tidak dioperasikan untuk mengangkut penumpang. Perusahaan kereta api harus melakukan kegiatan pelangsiran dengan biaya minimum agar kereta api dapat beroperasi dengan baik. Dalam praktiknya, masalah pelangsiran adalah suatu masalah yang sangat kompleks yang harus dihadapi oleh perusahaan kereta api. Dua proses penting dalam masalah pelangsiran adalah pendataan unit kereta api yang harus diparkir di tempat pelangsiran menjadi unit kereta api yang harus diberangkatkan dari tempat pelangsiran serta pemarkiran unit -unit kereta api pada rel pelangsiran. Pada proses pendataan kereta-api-datang menjadi kereta-api-berangkat, didefinisikan part sebagai subset dari himpunan unit kereta yang berdampingan pada suatu kereta api. Dalam proses ini akan dicari suatu kombinasi part dari kereta-api-datang yang akan meminimumkan biaya untuk ditetapkan menjadi kereta-api-berangkat. Solusi dari masalah ini dicari dengan menggunakan LINDO 6.1. Dari proses ini diperoleh himpunan part dari kereta-api-datang yang ditetapkan menjadi himpunan part dari kereta-api-berangkat yang disebut dengan blok. Blok-blok ini akan digunakan dalam proses pemarkiran unit-unit kereta pada rel pelangsiran. Assignment fisibel adalah cara menyusun blok-blok pada suatu rel pelangsiran yang tidak boleh melebihi panjang rel dan tidak mengandung crossing. Crossing terjadi jika suatu blok menghalangi blok yang lain pada suatu rel pelangsiran. Memilih assignment fisibel pada proses pemarkiran unit kereta dapat dimodelkan sebagai masalah pemartisian himpunan dengan kendala tambahan dengan banyaknya variabel jauh lebih besar jika dibandingkan dengan banyaknya kendala. Penyelesaian masalah pemartisian himpunan dalam skala besar di antaranya dapat menggunakan teknik pembangkitan kolom (column generation). Teknik pembangkitan kolom ini merupakan teknik penyelesaian masalah yang hanya menggunakan sebagian variabel saja untuk menghasilkan solusi optimal dari masalah utama. Dari teknik pembangkitan kolom ini akan dihasilkan suatu himpunan assignment fisibel yang meminimumkan biaya pelangsiran.
3
PENYELESAIAN MASALAH PELANGSIRAN UNIT KERETA PENUMPANG PADA STASIUN KERETA API DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM
Skripsi
Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Oleh: DINA LIANITA SARI G54102025
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2006
4
Dengan segala ketulusan hati, kupersembahkan karya kecilku kepada kedua orangtuaku, Ira, Andi, Nanang, dan jiwa-jiwa yang selalu haus akan ilmu.
5
RIWAYAT HIDUP
Penulis dilahirkan di Bogor pada tanggal 25 November 1984 sebagai anak pertama dari pasangan bapak Fahmi D.S dan ibu Ermina Zaenah. Pada tahun 2002 penulis lulus dari SMUN 3 Depok dan berhasil menjadi mahasiswa Departemen Matematika, Fakultas Matematika dan Ilmu pengetahuan Alam, Institut Pertanian Bogor melalui jalur USMI (Undangan Seleksi Masuk IPB). Selain mengikuti kegiatan perkuliahan, penulis pernah menjadi asisten dosen pada mata kuliah Matematika Dasar (2003), Kalkulus 1 (2004), dan Analisis Kompleks (2005). Penulis juga aktif pada kegiatan kemahasiswaan Gumatika (Gugus Mahasiswa Matematika) pada periode 2003/2004.
6
PRAKATA
Bismillahhirrahmanirrahim, Puji dan syukur penulis panjatkan kepada Allah SWT atas segala karunia, rahmat tak terhingga dan kekuatan yang mengisi relung jiwa sehingga penulis dapat menyelesaikan karya ilmiah ini. Dengan segala kerendahan hati, penulis ingin berterima kasih kepada segala cinta yang telah menggenapkan karya ilmiah ini: 1. Ibu Farida Hanum selaku pembimbing 1 yang telah memberikan saran dan masukan serta bantuan yang tak terbalaskan. 2. Bapak Donny Citra Lesmana selaku pembimbing 2 yang telah banyak membantu dalam penulisan karya ilmiah ini. 3. Bapak I Gusti Putu Purnaba atas bimbingan dan kesediaannya menjadi penguji. 4. Papa dan mama tercinta yang tiada hentinya memberikan nasihat, do’a dan dukungan. Terima kasih atas segenap kasih sayang yang tak terbalaskan. Kedua adik, Ira yang telah banyak membantu dala m pengetikan dan seminar dan Andi yang telah banyak memberi senyum lewat tingkah lakunya. 5. Nanang Siswanto yang telah memberikan warna baru dalam kehidupan pada tiga tahun terakhir. Selalu untuk semangat, kesabaran dan support yang tak berujung yang menjadikan hari ini ada. 6. Sepupu-sepupu tersayang, ayuk Rian, ayuk Dika, Riska, dan semua keluarga besar Yusuf Basir atas segala nasihat, do’a, dan semua cerita pengalamannya. 7. Sahabat-sahabat terbaikku, nonoy (teman sekamarku yang baik), desi (teman se-kosan yang bijak), tami (teman se-kosan yang kritis), nita (teman se-kosan yang lucu), eryt (temanku yang gemar makan), mere (temanku yang dewasa), tika (temanku yang selalu ceria), ade atas segala kebersamaan dalam mengerjakan skripsi serta kisah-kisah seru bersama sampah. 8. Arif, Febi, Ardhi, dan Avie, kalian selalu aku anggap sebagai sahabat-sahabat terindahku. 9. Teman-teman Math ’39 yang tidak bisa aku sebutkan satu persatu, terima kasih atas segala kebersamaan serta momen-momen terindah dalam setiap detiknya. 10. Dosen-dosen Departemen Matematika atas segala ilmu yang telah diberikan tanpa lelah. 11. Staf-staf Departemen Matematika ibu Susi (atas segala nasihat dan ceritanya), ibu Ade, mas Deni, mas Yono, mas Bono, ibu Marisi, pak Juanda, dan mbak Yanti. 12. Teman-teman Math ’38 dan Math ’40 serta seluruh civitas Matematika yang membuat kisah hidup lebih lengkap. 13. Serta semua pihak yang telah membantu terselesaikannya skripsi ini. Akhir kata, semoga karya ilmiah ini menjadi amal saleh bagi penulis dan bagi orang-orang yang terlibat di dalamnya serta dapat bermanfa’at bagi siapapun yang tertarik terhadap karya ilmiah ini. Amin.
Bogor, Januari 2006 Dina Lianita Sari
7
DAFTAR ISI
Halaman DAFTAR TABEL ................................................................................................................................... viii DAFTAR GAMBAR ............................................................................................................................ viii DAFTAR LAMPIRAN .......................................................................................................................... viii I PENDAHULUAN Latar Belakang .......................................................................................................................... Tujuan ..........................................................................................................................................
1 1
II LANDASAN TEORI Pemrograman Linear ................................................................................................................. Masalah Dual .............................................................................................................................. Pemrograman Linear Bilangan Bulat .................................................................................... Graf ..............................................................................................................................................
1 3 5 6
III DESKRIPSI DAN FORMULASI MASALAH PELANGSIRAN UNIT KERETA PENUMPANG PADA STASIUN KERETA Masalah Pelangsiran Unit Kereta Penumpang pada Stasiun Kereta ................................ 8 Pendekatan Solusi ...................................................................................................................... 10 IV MENYELESAIKAN MASALAH PENETAPAN BLOK PADA REL PELANGSIRAN DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM (COLUMN GENERATION) Representasi Network dan Masalah Penetapan Blok pada Rel Pelangsiran .................... 15 Memeriksa Kefisibelan Suatu Assignment dengan Menggunakan Algoritme Pemrograman Dinamik .............................................................................................................. 17 Teknik Pembangkitan Kolom untuk Optimisasi Penetapan Blok pada Rel Pelangsiran.. 17 V CONTOH KASUS PELANGSIRAN UNIT KERETA PENUMPANG PADA STASIUN KERETA Penyelesaian Masalah Pemadanan Kereta-api-datang Menjadi Kereta-api-berangkat dengan Menggunakan LINDO 6.1 ..................................................... 19 Penyelesaian Masalah Penetapan Blok pada Rel Pelangsiran dengan Menggunakan Teknik Pembangkitan Kolom ........................................................................ 21 VI SIMPULAN DAN SARAN Simpulan ..................................................................................................................................... 31 Saran ............................................................................................................................................ 32 DAFTAR PUSTAKA ........................................................................................................................... 32 LAMPIRAN
........................................................................................................................................... 33
8
DAFTAR TABEL Halaman Contoh tabel waktu untuk sebuah jalur-bebas ........................................................................... 9 Daftar biaya pemarkiran blok ke rel pelangsiran 1, 2, dan 3 .................................................. 23 Daftar assignment yang tidak mengandung crossing serta biayanya masing-masing .......... 23 Daftar assignment fisibel yang diperoleh dengan menggunakan Algoritme Pemrograman Dinamik..................................................................................................................... 27 5 Biaya tereduksi dari assignment fisibel k pada rel pelangsiran s untuk RP0 ......................... 30 6 Biaya tereduksi dari assignment fisibel k pada rel pelangsiran s untuk RP1 ......................... 31 1 2 3 4
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Halaman Graf G = (V,E) ................................................................................................................................. 6 Digraf G’ = (V,A) ............................................................................................................................ 7 Sisi berarah menjauhi atau mendekati, suksesor dan predesesor ............................................ 7 Situasi di rel pelangsiran pada Selasa pukul 06.00 .................................................................... 10 Situasi di rel pelangsiran pada Selasa pukul 06.00 jika Kereta 561 dan Kereta 3678 memasuki rel pelangsiran melalui sisi yang sama ..................................................................... 10 Network dari Kereta 3629 pada Tabel 1 ...................................................................................... 11 Network dari Kereta 3629 pada Tabel 1 tanpa simpul rekaan ................................................. 12 Contoh dari sebuah network untuk jalur-bebas dengan 3 blok ................................................ 16 Network dari Kereta 3628 pada Tabel 1 ...................................................................................... 19 Network dari Kereta 561 pada Tabel 1 ......................................................................................... 19 Network dari Kereta 3678 pada Tabel 1 ...................................................................................... 19 Network dari Kereta 3629 pada Tabel 1 ...................................................................................... 19 Network dari Kereta 520 pada Tabel 1 ....................................................................................... 19 Keadaan di stasiun yang sesuai dengan Tabel 1 dan memiliki 2 jalur-bebas dan 1 jalur-satu-arah ............................................................................................................................. 22 Network yang terbentuk dari assignment yang tidak mengandung crossing pada rel pelangsiran 3 .............................................................................................................................. 22 Graf G yang terbentuk dari assignment yang tidak mengandung crossing pada rel pelangsiran 1 dan 2 dengan notasi i = 1,2,…,15 untuk masing-masing simpul-antara ..... 25 Graf G yang terbentuk dari assignment yang tidak mengandung crossing pada rel pelangsiran 3 dengan notasi i = 1,2,…,6 untuk masing-masing simpul-antara ..................... 26
DAFTAR LAMPIRAN Halaman 1 Contoh penyelesaian suatu pemrograman linear dengan algoritme simpleks .................... 33 2 Hasil penghitungan Contoh 3 dengan menggunakan LINDO 6.1 ............................................ 34 3 Hasil penghitungan masalah pemadanan kereta-api-datang menjadi kereta-api-berangkat dengan menggunakan LINDO 6.1 .......................................................... 35 4 Prosedur pemeriksaan kefisibelan dan kedominanan assignment di graf G dengan menggunakan Algoritme Pemrograman Dinamik ...................................................... 36 5 Hasil penghitungan RP0 dan RP1 dengan menggunakan LINDO 6.1 ................................... 55
9
I PENDAHULUAN 1.1 Latar Belakang Pada jam-jam tertentu, dalam suatu stasiun kereta api terdapat kereta api penumpang yang tidak dioperasikan untuk mengangkut penumpang. Perusahaan kereta api harus melakukan kegiatan pelangsiran agar kereta api dapat beroperasi dengan baik. Kegiatan pelangsiran ini meliputi pendataan kereta api yang datang ke stasiun kereta api menjadi kereta api yang berangkat dari stasiun kereta api, pemarkiran keretaapi-datang pada rel-rel pelangsiran, pemeliharaan kereta, serta perencanaan pekerja yang akan melakukan kegiatan pelangsiran. Dua proses penting dalam masalah pelangsiran adalah pendataan unit keretaapi-datang (arriving shunt unit) yang harus diparkir di tempat pelangsiran menjadi unit kereta-api-berangkat (departing shunt unit) yang harus diberangkatkan dari tempat pelangsiran, serta pemarkiran unit-unit kereta api pada rel pelangsiran. Dalam praktiknya, kegiatan pelangsiran adalah suatu masalah yang sangat kompleks yang harus dihadapi oleh perusahaan kereta api. Masalah pelangsiran ini telah banyak dibahas dan dipelajari, di antaranya dalam
(Freling et al., 2000) dan (Lentink et al., 2003). Penyelesaian dari masalah pelangsiran ini dapat menggunakan algoritme simpleks, namun akan membutuhkan waktu yang lama karena banyaknya variabel yang harus diselesaikan. Pada tulisan ini digunakan teknik pembangkitan kolom. Teknik pembangkitan kolom merupakan teknik yang telah banyak digunakan untuk menyelesaikan masalah dalam bidang transportasi dan penjadwalan. Salah satunya dikenalkan dalam (Barnhart et al., 1998) yang menggunakan teknik pembangkitan kolom dalam konteks pemrograman bilangan bulat. Tulisan ini merupakan rekonstruksi dari tulisan Richard Frelling, Ramon M. Lentink, Leo G. Kroon & Dennis Huisman (2002) yang berjudul “ Shunting of passenger train units in a railway station”. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah mempelajari penyelesaian masalah pelangsiran unit kereta penumpang pada stasiun kereta api dengan menggunakan teknik pembangkitan kolom (column generation).
II LANDASAN TEORI
2.1 Pemrograman Linear Pemrograman linear adalah kegiatan merencanakan untuk mendapatkan hasil yang optimal. Model Pemrograman Linear (PL) meliputi pengoptimuman suatu fungsi linear terhadap kendala linear (Hillier & Lieberman, 1990). Pada tulisan ini, suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut: Definisi 1 (Bentuk Standar Suatu PL) Suatu pemrogra man linear dalam bentuk standar didefinisikan sebagai:
z = cT x Ax = b x ≥0 (1) dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa Minimumkan terhadap
matriks berukuran m × n yang disebut juga sebagai matriks kendala. (Nash & Sofer, 1996) 2.1.1 Solusi suatu Pemrograman Linear Untuk menyelesaikan suatu masalah Pemrograman Linear (PL), metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum. Metode ini mulai dikembangkan oleh Dantzig tahun 1947. Sejak perkembangannya, metode ini adalah metode yang paling umum digunakan untuk menyelesaikan PL, yaitu berupa metode iteratif untuk menyelesaikan masalah PL dalam bentuk standar. Pada PL (1), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi PL (1). Misalkan matriks A dapat dinyatakan sebagai A = (B N) dengan B adalah matriks berukuran m × m yang merupakan matriks
10
taksingular yang elemennya berupa koefisien variabel basis dan N adalah matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala . Matriks B disebut matriks basis untuk PL. Misalkan x dapat dinyatakan sebagai
x vektor x = B , dengan x B adalah vektor xN variabel basis dan x N adalah vektor variabel nonbasis. Maka Ax = b dapat dinyatakan sebagai x Ax = (B N) B xN = Bx B + N x N = b . (2) Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai: x B = B −1b − B −1Nx N (3) Definisi 2 (Solusi Basis) Vektor x disebut solusi basis dari suatu pemrograman linear jika : 1. x memenuhi kendala dari PL, dan 2. kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari x adalah bebas linear. (Nash & Sofer, 1996) Definisi 3 (Solusi Basis Fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x ≥ 0 . (Nash & Sofer, 1996) Ilustrasi solusi basis dan solusi basis fisibel dapat dilihat dalam contoh berikut: Contoh 1 Misalkan diberikan pemrograman linear berikut: Minimumkan z = −2 x1 − 3x 2 terhadap − 2x1 + x 2 + x3 = 4
− x1 + 2x 2 + x 4 = 11 x1 + x5 = 5 x1 , x 2 , x3 , x4 , x5 ≥ 0
Misalkan dipilih
x B = ( x3 x 4 x5 )T dan x N = (x1 x 2 )T maka matriks basis 1 0 0 B = 0 1 0 . 0 0 1 Dengan menggunakan matriks basis tersebut diperoleh x B = B −1b = (4 11 5)T ,
x N = (0 0)T . (5) Solusi (5) merupakan solusi basis, karena solusi tersebut memenuhi kendala pada PL (4) dan kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari (5) yaitu B adalah 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. PL (1) dapat dinyatakan dalam x B dan x N sebagai berikut:
z = c B T x B + c N T x N (6) terhadap Bx B + N x N = b x ≥0 dengan c B adalah koefisien variabel basis pada fungsi objektif, c N adalah koefisien variabel nonbasis pada fungsi objektif. Jika Persamaan (3) dis ubstitusikan ke Persamaan (6) maka akan didapat: Minimumkan
(
)
z = c B T B −1b − B −1 Nx N + c N T x N
(
)
= c B T B −1b + c N T − c B T B −1N x N . Jika didefinisikan
(
)
T
y = c B T B −1 = B −T c B maka z dapat dinyatakan dalam y:
(
)
z = y T b + cN T − yT N x N . (7) Vektor y disebut vektor pengali simpleks (simplex multiplier). Untuk suatu solusi basis x N = 0 dan x = bˆ = B −1b , maka: B
(4)
Dari pemrograman linear tersebut didapatkan: 1 0 0 −2 1 4 A = −1 2 0 1 0 , b = 11 . 1 5 0 0 0 1
zˆ = c B T B − 1b . Notasi zˆ adalah notasi untuk z optimal. Koefisien cˆ j disebut biaya tereduksi (reduced cost) dari xj dengan cˆ j adalah
(
)
elemen dari cˆ N T = c N T − c B T B − 1N . Biaya tereduksi adalah penambahan nilai fungsi objektif jika suatu variabel nonbasis
11
dijadikan variabel basis (artinya menjadi solusi taknol) pada suatu pemrograman linear. 2.1.2 Penyelesaian Pemrograman Linear dengan Algoritme Simpleks Solusi suatu pemrograman linear dapat diketahui optimal atau tidak untuk PL tersebut melalui algoritme sebagai berikut: •
Tes Keoptimalan
Vektor y = c B T B −1 dihitung, kemudian dapat dihitung pula nilai biaya tereduksi cˆ N T = c N T − y T N .
(
)
Jika cˆ N T ≥ 0 maka solusi diperoleh adalah solusi optimal.
yang
Jika cˆ N T < 0 maka dipilih variabel xt yang memenuhi cˆ t < 0 sebagai variabelmasuk yaitu variabel xt yang akan masuk ke dalam basis. •
Langkah tertentu t ˆ = B −1 A , yaitu koefisien Hitung A t t kendala yang berhubungan dengan variabelmasuk ke t. Indeks s ditentukan pada kolom kendala yang berhubungan dengan variabelmasuk yang memenuhi bˆ s min bˆi ; ai ,t > 0 . = a s,t 1 ≤ i ≤ m ai, t Memilih indeks dengan cara tersebut disebut dengan uji nisbah minimum (minimum ratio test). Variabel yang menjadi variabel-keluar (variabel yang akan keluar dari basis dan digantikan oleh variabel-masuk) dan pivot entry adalah variabel yang berpadanan dengan aˆ s , t . Jika aˆ i ,t ≤ 0 , 1 ≤ i ≤ m untuk semua i, maka masalah PL disebut takterbatas . • Pivot Matriks basis B dan vektor basis xB diperbaiki, kemudian dilanjutkan ke tes keoptimalan. Berikut contoh penggunaan algoritme simpleks: Contoh 2 Misalkan diberikan PL (4) seperti pada Contoh 1, maka dengan menggunakan algoritme simpleks akan diperoleh solusi:
x1 = 5, x 2 = 8, x 3 = 6, x 4 = x 5 = 0 dengan z = −34 (lihat Lampiran 1). 2.2 Masalah Dual Setiap masalah pemrograman linear memiliki padanan, yaitu masalah lain yang disebut pemrograman linear dual. Pemrograman linearnya sendiri disebut masalah primal. Misalkan diberikan masalah primal: Minimumkan terhadap
z = cT x Ax ≥ b x ≥0.
(8)
Masalah dual dari (8) adalah Maksimumkan w = bT y terhadap
AT y ≤ c y ≥ 0.
(9)
Jika masalah primal memiliki n variabel dan m kendala, maka masalah dual akan memiliki m variabel dan n kendala. Koefisien fungsi objektif masalah primal merupakan nilai sisi kanan pada masalah dual, begitu pula sebaliknya. Jika masalah primal merupakan masalah minimisasi maka masalah dual merupakan masalah maksimisasi. Solusi optimal dari masalah dual merupakan pengali simpleks pada masalah primal. Pada kondisi optimal, solusi dari masalah dual dan masalah primal akan menghasilkan nilai fungsi objektif yang sama. Hal ini disebutkan dalam Teorema Dualitas Kuat, namun sebelumnya perlu diperkenalkan pula Teorema Dualitas Lemah yang akan digunakan untuk membuktikan Teorema Dualitas Kuat. Teorema 1 (Teorema Dualitas Lemah) Misalkan diberikan pemrograman linear primal dan masalah dualnya. Misalkan x adalah solusi fisibel untuk masalah primal dalam bentuk standarnya dan misalkan y solusi fisibel untuk masalah dual, maka nilai fungsi objektif dari masalah primal selalu lebih besar atau sama dengan nilai fungsi objektif dari masalah dual. Bukti: lihat (Nash & Sofer, 1996). Salah satu akibat langsung dari Teorema Dualitas Lemah digunakan untuk membuktikan Teorema Dualitas Kuat. Hal ini disebutkan dalam Akibat 1 berikut:
12
Akibat 1 Jika x adalah solusi fisibel untuk masalah primal, y adalah solusi fisibel untuk masalah dual, dan b y = c x , maka x dan y adalah solusi optimal berturut-turut untuk masalah primal dan dual. T
T
Teorema 2 (Teorema Dualitas Kuat) Misalkan diberikan pemrograman linear primal dan masalah dualnya. Jika salah satu dari masalah primal atau masalah dual tersebut memiliki solusi optimal, maka masalah lainnya juga memiliki solusi optimal dan nilai fungsi objektif optimalnya adalah sama. Bukti: Misalkan diasumsikan bahwa masalah primal dalam bentuk standar dan mempunyai solusi x yang merupakan solusi basis fisibel optimal. Misalkan x dapat x dinyatakan sebagai vektor x = B , xN dengan x B adalah vektor variabel basis dan x N adalah vektor variabel nonbasis. Selain itu, seperti telah dijelaskan sebelumnya matriks A dapat dinyatakan sebagai A = (B N) dan matriks koefisien pada fungsi objektif c dapat dinyatakan
c sebagai c = B . Karena B adalah matriks cN taksingular, maka B memiliki invers sehingga x B dapat dinyatakan sebagai
x B = B −1 b . Dari tes keoptimalan pada algoritme simpleks diketahui pula, jika solusi x optimal maka biaya tereduksinya adalah c TN − c TB B −1 N ≥ 0 atau c TB B −1N ≤ c TN (*) Misalkan y adalah vektor dari pengali simpleks yang berhubungan dengan solusi basis fisibel, dengan y = B −T c B atau y T = c TB B − 1. Akan ditunjukkan bahwa: 1) Nilai dari fungsi objektif masalah primal dan dual adalah sama, yaitu bT y = c T x , dan 2) y adalah optimal untuk masalah dual. Bukti: 1) Sebelumnya akan diperiksa terlebih dahulu kefisibelan dari y : y T A = c TB B − 1 (B N )
(
= c TB
) (
c TB B −1N ≤ c TB
)
cTN ..dari (*)
T
= c . Sehingga AT y ≤ c dan y fisibel untuk masalah dual, kemudian dihitung nilai objektif untuk masalah primal (z) dan dual (w): z = c T x = c TB x B = c TB B −1b
w = b T y = y T b = c TB B −1 b = z . Jadi y adalah fisibel untuk masalah dual dan nilai fungsi objektif solusi optimal dari masalah primal dan dual mempunyai nilai yang sama. 2) Berdasarkan Akibat 1 dan bT y = c T x maka y adalah solusi optimal untuk masalah dual. < Bukti dari Teorema Dualitas Kuat menghasilkan solusi optimal dual. Misalkan x c x = B , A = (B N) , dan c = B xN cN maka nilai optimal dari variabel dual diberikan oleh vektor pengali simpleks y = B −T c B . Dari bukti teorema dualitas kuat terlihat bahwa kondisi primal optimal c TN − c TB B −1 N ≥ 0 adalah ekivalen dengan kondisi fisibel dual AT y ≤ c atau c − A T y ≥ 0 . Jadi vektor dari biaya tereduksi cˆ adalah variabel slack dual cˆ = c − A T y . Contoh 3 Misalkan diberikan pemrograman linear primal sebagai berikut: Minimumkan z = 5 x1 + 7 x 2 + 9 x3 + 7x 4 + 5 x5 terhadap x1 + x 2 ≥ 1
x1 + x3 + x 4 ≥ 1 x2 + x3 + x4 ≥ 1 x1 + x 5 ≥ 1 x 2 + x3 ≥ 1 x 3 + x 4 + x5 ≥ 1 x4 ≥ 1 xi ≥ 0 , untuk i = {1,2,3,4,5} . Masalah dual dari masalah tersebut adalah sebagai berikut:
13
Maksimumkan w = y1 + y 2 + y 3 + y 4 + y5 + y 6 + y 7 terhadap y1 + y 2 + y 4 ≤ 5
y1 + y 3 + y5 ≤ 7 y 2 + y3 + y 5 + y 6 ≤ 9 y 2 + y3 + y 6 + y 7 ≤ 7 y4 + y6 ≤ 5 yi ≥ 0 , untuk i = {1,2,3, 4,5, 6,7} . Dengan menggunakan LINDO 6.1, diperoleh solusi dari masalah primal sebagai berikut: x1 = x2 = x4 = 1, x 3 = x5 = 0 dengan nilai fungsi objektifnya z = 19 (lihat Lampiran 2). Nilai pengali simpleks untuk masing-masing kendala adalah sebagai berikut: y1 = y 2 = y 3 = y 6 = 0, y 4 = 5, y 5 = y 7 = 7 dengan yi adalah nilai pengali simpleks kendala ke -i. Solusi dari masalah dual tersebut juga dapat dicari menggunakan LINDO 6.1 yang menghasilkan solusi: y1 = y 2 = y 3 = y 6 = 0, y 4 = 5, y 5 = y 7 = 7 dengan nilai fungsi objektif w = 19 (lihat Lampiran 2). Dari penghitungan tersebut, nilai pengali simpleks masalah primal sama dengan optimal dari masalah dual dan fungsi objektif dari masalah primal dan dual mempunyai nilai yang sama seperti yang dinyatakan Teorema 2. 2.3 Pemrograman Linear Bilangan Bulat (PLBB) Model pemrograman linear bilangan bulat atau disebut juga pemrograman bilangan bulat adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat. Jika semua variabel harus berupa bilangan bulat maka masalah tersebut disebut pemrograman bilangan bulat alami . Jika hanya sebagian yang harus bilangan bulat maka disebut Pemrograman bilangan bulat campuran. Pemrograman bilangan bulat dengan semua variabelnya harus bernilai 0 atau 1 disebut 01 PLBB. Definisi 4 (PL-Relaksasi) PL-Relaksasi dari suatu PLBB merupakan pemrograman linear yang diperoleh dari PLBB tersebut dengan menghilangkan kendala bilangan bulat atau kendala 0-1 pada variabelnya. (Winston, 1995)
Model yang digunakan pada tulisan ini yang berkaitan dengan masalah PLBB adalah masalah pemartisian himpunan (set partitioning problem). 2.3.1 Masalah Pemartisian Himpunan (Set PartitioningProblem) Definisi 5 (Partisi) Misalkan diberikan himpunan I = {1,2,..., m}
dan himp unan P = {P1 , P2 ,..., Pn } dengan Pj adalah himpunan bagian dari I, j ∈ J = {1,2,..., n} .
Pj
Himpunan
dengan
j∈J* ⊆ J
adalah partisi dari I jika :
j, k ∈ J * , j ≠ k ⇒ P j ∩ Pk = ø dan
UP
j ∈J
j
=I
*
(Garfikel & Nemhauser, 1972) Ilustrasi dari suatu partisi dapat dilihat pada Contoh 4 berikut: Contoh 4 Misalkan diberikan himpunan I = {1, 2,3, 4,5,6} dan kelas-kelas P1 = {1,6} ,
P2 = {3,4} , P3 = {1,4,5} , P5 = {2,3, 5,6} .
Partisi dari {P1 , P2 , P4 } ,
I
di
P4 = {2,5} ,
antaranya karena
adalah untuk
J * = {1,2,4} berlaku j, k ∈ J * , j ≠ k ⇒ P j ∩ Pk = dan
UP
j
ø
=I
j∈J *
Masalah pemartisian himpunan (set partitioning problem/SPP) adalah masalah menentukan partisi dari himpunan I yang mempunyai biaya minimum. Untuk mendapatkan partisi tersebut, misalkan didefinisikan variabel 0-1 sebagai berikut: 1, jika Pj termasuk dalam partisi xj = 0, selainnya Misalkan
pula
cj ≥0
ongkos/biaya dari setiap P j ∈ I .
adalah
14
x1 + x5 = 1
Bentuk umum SPP:
x j = 0 atau 1, untuk j = {1, 2,3, 4,5} .
n
Minimumkan
∑c x j
j
j =1 n
terhadap
∑ A( j )x
=1
j
j =1
x j = 0 atau 1 dengan cj adalah biaya Pj , A(j) adalah matriks koefisien kendala, dan 1 adalah vektor dengan dimensi n dengan semua komponennya sama dengan 1. Model ini memiliki beberapa sifat penting, yaitu: Sifat 1 Masalah pada model merupakan masalah minimisasi dan semu a kendalanya berupa persamaan. Sifat 2 Nilai sisi kanan semua kendala adalah 1. Sifat 3 Semua elemen matriks koefisien A(j) adalah 0 atau 1. Contoh 5 (Masalah Pemartisian Himpunan) Misalkan diberikan himpunan I beserta kelas-kelas P seperti pada Contoh 4. Misalkan diketahui biaya dari masingmasing kelas Pj , yaitu cj , dengan c1 = 5, c 2 = 10, c 3 = 9, c4 = 8, c5 = 7 . Diinginkan himpunan dari Pj yang dapat memartisi I dengan biaya minimum. Masalah tersebut dapat dimodelkan sebagai masalah pemartisian himpunan. Misalkan didefinisikan variabel 0-1 sebagai berikut: 1, jika Pj termasuk dalam partisi xj = 0, selainnya 1, jika elemen ke-i di I merupakan elemen Pj , dengan j = 1, 2,...,5 A(j) =
Pada tulisan ini, model matematika dalam penetapan unit kereta pada rel pelangsiran diformulasikan sebagai masalah pemartisian himpunan dengan kendala tambahan. masalah pemartisian himpunan dengan kendala tambahan adalah masalah pemartisian himpunan dengan beberapa kendala tambahan yang berbeda dengan kendala yang berada pada SPP itu sendiri. Dalam tulisan ini juga diperlukan konsep tentang graf. Berikut uraian tentang teori graf yang berhubungan dengan masalah pelangsiran unit kereta pada stasiun kereta api dan algoritme pembangkitan kolom. 2.4 Graf Definisi 6 (Graf) Suatu graf adalah pasangan terurut (V,E) dengan V himpunan takkosong dan hingga dan E adalah himpunan pasangan takterurut yang menghubungkan elemenelemen V dan dinotasikan dengan G = (V , E ) . Elemen V dinamakan simpul (node), dan elemen E dinamakan sisi (edge), dinotasikan sebagai {i, j} , yaitu sisi yang menghubungkan simpul i dengan simpul j, dengan i, j ∈V . (Foulds, 1992) Ilustrasi graf dapat dilihat pada Contoh 6 berikut:
0, selainnya
Masalah tersebut dapat dimodelkan sebagai berikut: 5
SPP : Minimumkan
Dengan mengunakan LINDO 6.1 diperoleh solusi untuk masalah SPP tersebut sebagai berikut: x1 = x 2 = x4 = 1, x 3 = x5 = 0 , dan nilai fungsi objektif sebesar 23.
∑c x j
Contoh 6 G: v1
v5
j
j =1
terhadap x1 + x 3 = 1
x 4 + x5 = 1 x 2 + x5 = 1 x 2 + x3 = 1 x 3 + x4 + x5 = 1
v4
v2
v3 Gambar 1. Graf G = (V, E).
15
Pada Gambar 1, V = {v1 , v 2 , v 3 , v 4 , v 5 } dan E = {{v1 , v 2 }, {v1 , v5 }, {v 2 , v3 }, {v2 , v 5 }, {v 3 , v4 }
{v 3 , v 5 }, {v 4 , v5 }} .
Definisi 7 (Walk) Suatu walk pada graf G = (V , E ) adalah suatu barisan simpul dan sisi dari G dengan bentuk: v1 , {v1 , v2 }, v2 , {v 2 , v3 },...,{vn−1, v n }, v n , atau ditulis dengan ringkas: v1, v2 ,...,vn atau ( v1, v2 ,..., vn ) . Walk tersebut menghubungkan simpul v1 dengan
vn .
Pada Gambar 2, digraf G’ memiliki himpunan simpul V = {v1 , v 2 , v 3 , v 4 , v 5 } dan
A = {( v1 , v2 ), (v1 , v 5 ), ( v2 , v 3 ), ( v5 , v3 ), (v 3 , v 4 ), (v 5 , v 4 )} .
Definisi 10 (Sisi Berarah Menjauhi atau Mendekati, Suksesor dan Predesesor) Misalkan diberikan digraf D = (V , A ) .
(
dikatakan menjauhi v i dan mendekati v j . Simpul v i disebut predesesor bagi simpul
v j , simpul v j disebut suksesor bagi simpul vi . (Foulds, 1992)
(Foulds, 1992) Definisi 8 (Path) Path pada suatu graf G adalah suatu walk dengan semua simpulnya berbeda. (Foulds, 1992) Berikut diberikan ilustrasi dari walk dan path. Pada graf G yang terdapat pada Gambar 1 salah satu contoh walk adalah ( v1, v 2 , v 5 , v4 , v 3 , v 2 , v 5 ) , sedangkan salah satu contoh path adalah ( v1, v2 , v 5 , v 4 ) . Definisi 9 (Digraf) Digraf (directed graf/graf berarah) adalah pasangan terurut (V, A) dengan V adalah himpunan takkosong dan hingga, dan A adalah himpunan pasangan terurut dari elemen-elemen di V. Elemen dari A disebut sisi berarah (arc) dan dituliskan sebagai (i, j ) dengan i, j ∈ V . (Foulds, 1992) Ilustrasi digraf Contoh 7 berikut:
dapat
dilihat
Contoh 7 v1
v5 v4
v2
v3
Gambar 2. Digraf G' = (V , A) .
pada
)
Jika a = vi , v j ∈ A maka sisi berarah ini
Definisi tersebut dapat digambarkan dalam digraf seperti berikut:
vi
vj
Gambar 3. Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor. Definisi 11 (Graf Berbobot) Suatu graf G = (V , E )
atau digraf
D = (V , A ) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau ϑ : A → ℜ (dengan ℜ himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau A. (Foulds, 1992) Terdapat kasus khusus dari graf berbobot yaitu network. Beberapa definisi yang digunakan dalam network adalah sebagai berikut: Definisi 12 (Simpul sumber) Simpul sumber (source) adalah suatu simpul dengan tidak ada sisi berarah yang mendekati simpul tersebut. (Foulds, 1992) Definisi 13 (Simpul tujuan) Simpul tujuan (sink ) adalah suatu simpul sehingga tidak ada sisi berarah yang menjauhi simpul tersebut. (Foulds, 1992) Definisi 14 (Network) Network adalah suatu digraf yang mempunyai tepat satu simpul sumber dan satu simpul tujuan. (Foulds, 1992)
16
Contoh 8 Graf G’ pada Gambar 2 merupakan network dengan v1 sebagai simpul sumber dan v4 sebagai simpul tujuan. Masalah graf berbobot ini biasanya untuk suatu kasus tertentu diinginkan bobot yang terkecil, salah satunya adalah masalah path terpendek (shortest path problem).
Definisi 15 (Shortest Path Problem) Masalah path terpendek adalah masalah untuk menemukan path terpendek (path dengan biaya minimum) dari suatu simpul ke suatu simpul lain dalam suatu network . (Foulds, 1992)
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Masalah Pelangsiran Unit Kereta Penumpang pada Stasiun Kereta Dalam jam-jam sibuk, kereta api penumpang khusus dioperasikan untuk mengangkut penumpang, sedangkan di luar jam sibuk, terdapat kelebihan kereta api yang tidak dioperasikan. Kelebihan kereta api tersebut dapat diparkir di rel-rel tertentu pada stasiun kereta api. Proses dari pendataan, pemarkiran, dan pemeliharaan unit kereta api beserta proses lain yang berhubungan disebut pelangsiran (shunting). Namun dalam tulisan ini hanya akan dibahas mengenai pendataan dan pemarkiran unit kereta api saja. Pelangsiran dari unit kereta biasanya dilakukan di stasiun kereta yang memiliki jumlah rel yang banyak. Unit kereta-apidatang yang akan dilangsir (unit pelangsiran) dapat diletakkan pada rel-rel di depan peron ataupun rel-rel di sekitar peron. Ada dua jenis peron pada stasiun kereta, yaitu peron kedatangan dan peron keberangkatan. Unit kereta yang diparkir di depan peron adalah unit kereta dari keretaapi-terus. Kereta-api-terus adalah jenis kereta yang memiliki jangka waktu yang cukup dekat antara kedatangan ke stasiun dan keberangkatan dari stasiun. Rel yang jarang digunakan untuk memarkir unit pelangsiran adalah rel yang sering digunakan oleh kereta-api-terus. Hal ini bertujuan agar aktivitas kereta-api-terus tidak terganggu karena pelangsiran biasanya memerlukan waktu yang tidak singkat. Unit kereta api yang harus diparkir di tempat pelangsiran disebut unit kereta-api datang (arriving shunt unit), sedangkan unit kereta-api-berangkat (departing shunt unit) didefinisikan sebagai unit kereta api yang harus diberangkatkan dari tempat pelangsiran. Unit kereta-api-datang dapat berasal dari kereta api yang telah selesai
dioperasikan dalam jangka waktu tertentu, sedangkan unit kereta-api-berangkat membentuk suatu rangkaian kereta yang akan dioperasikan untuk melayani penumpang. Sebagian besar kereta api dapat bergerak dalam dua arah dan tidak membutuhkan lokomotif. Dalam masalah ini, unit kereta diklasifikasikan berdasarkan tipe dan subtipe. Tipe dari suatu unit kereta api merupakan kelas kereta api, misalkan kereta api tipe (kelas) bisnis, ekonomi atau eksekutif. Pada masalah ini diasumsikan bahwa hanya unit kereta dari tipe yang sama yang dapat dikombinasikan untuk membentuk suatu rangkaian kereta api. Sedangkan subtipe dari suatu unit kereta didasarkan atas banyaknya gerbong per unit kereta. Sebagai contoh, kereta api dengan subtipe MAT1_3 terdiri atas 1 unit kereta tipe MAT1 dengan banyaknya gerbong 3 buah. Kereta api dengan subtipe MAT1_3 MAT1_4 terdiri atas 2 unit kereta MAT1 dengan banyaknya gerbong 7 buah, di mana unit pertama terdiri atas 3 gerbong dan unit kedua dengan 4 gerbong. Dalam penggunaannya, unit kereta dari subtipe yang sama dapat dipertukarkan urutannya. Secara umum, masalah pelangsiran unit kereta terdiri atas dua submasalah. Pertama adalah pendataan unit kereta-api-datang menjadi unit kereta-api-berangkat. Kedua berhubungan dengan pemarkiran unit-unit kereta pada rel pelangsiran. Selanjutnya, akan diminimumkan ongkos dari sebuah rencana pelangsiran sehingga kapasitas dari rel pelangsiran tidak terlebihi. Kendala dari masalah pelangsiran unit kereta secara umum terdiri atas empat hal, yaitu: 1. Kedatangan dan keberangkatan dari unit kereta pada suatu stasiun tidak harus berurutan. Artinya, kereta yang pertama
17
2.
3.
4.
datang di stasiun tidak harus yang pertama kali berangkat dari stasiun. Rel-rel pelangsiran dapat memiliki tipe serta panjang yang berbeda. Tipe dari sebuah rel menentukan bagaimana suatu unit pelangsiran dapat memasuki rel. Dalam hal ini, rel pelangsiran dibagi menjadi dua tipe, yaitu jalur-satu-arah (Last In First Out track) yang dapat dimasuki hanya dari salah satu sisi rel dan jalur-bebas (free track) yang dapat dimasuki dari dua sisi. Unit pelangsiran dapat memiliki subtipe (banyaknya gerbong) yang berbeda. Hal ini membatasi himpunan rel pelangsiran di mana unit pelangsiran dapat diparkir karena rel-rel pelangsiran memiliki ukuran panjang yang berbeda. Kereta api mempunyai waktu yang tetap untuk kedatangan dan keberangkatan dari peron, namun
mempunyai waktu kedatangan dan keberangkatan dari rel pelangsiran yang fleksibel. Sebagai contoh, waktu keberangkatan sebuah unit kereta-apidatang dari sebuah peron kedatangan ke tempat pelangsiran dapat fleksibel dalam suatu interval waktu. Keberangkatan dapat dimulai dari waktu kedatangan dari unit tersebut ke peron dan berakhir pada sebuah kedatangan selanjutnya dari sebuah unit kereta pada peron kedatangan yang sama. Tabel 1 adalah sebuah contoh dari tabel waktu (time table) untuk sebuah rel pelangsiran bertipe jalur-bebas. Tabel waktu ini berisi identitas (ID) kereta, subtipe dari kereta, dan waktu kedatangan dan/atau keberangkatan kereta serta peron stasiun yang digunakan.
Tabel 1. Contoh tabel waktu untuk sebuah jalur-bebas Kereta-api-datang ID Peron Waktu Kereta 3628 5A Senin 11:09 561 3B Senin 21:02 3678 5B Senin 23:43
Kereta-api-berangkat ID Peron Waktu Kereta 3629 Selasa 5A 07:49 520 Selasa 1A 07:18 3629 Selasa 5A 07:49
Tabel 1 menjelaskan sebuah rencana pelangsiran dari 5 unit kereta pada sebuah jalur-bebas. Setiap baris menunjukkan pendataan dari unit kereta-api-datang menjadi unit-kereta-api-berangkat. Dalam contoh ini, satu unit subtipe MAT64_4 dari kereta dengan ID 3628 tiba di peron 5A pada Senin pukul 11:09 dan unit ini akan meninggalkan stasiun dengan Kereta 3629 dari peron 5A pada Selasa pukul 07:49. Selanjutnya, baris ketiga menjelaskan bahwa
Subtipe Unit Kereta MAT64_4 ICM_4 ICM_3 MAT64_2 MAT64_2
dua unit kereta dengan subtipe MAT64_2 tiba dengan Kereta 3678 di peron 5B pada Senin pukul 23:43 dan akan berangkat juga dengan Kereta 3629 dari peron 5A pada Selasa 07:49. Jadi unit-unit dari Kereta 3628 dan Kereta 3678 dipasangkan berdekatan pada rel pelangsiran yang sama. Gambar 4 menggambarkan situasi di rel pelangsiran bertipe jalur-bebas pada Selasa pagi pukul 06:00 berdasarkan Tabel 1.
18
Kereta-apidatang
Kereta 561
ICM_4
Kereta-apiberangkat
Kereta 3628
MAT 64_4
ICM_3
Kereta 520
Kereta 3678
MAT 64_2
MAT 64_2
Kereta 3629
Gambar 4. Situasi di rel pelangsiran pada Selasa pukul 06:00. Pada Gambar 4, Kereta 3628 berangkat dari peron 5A ke rel pelangsiran melalui salah satu sisi rel. Kemudian dari peron 3B Kereta 561 memasuki rel pelangsiran melalui sisi kiri rel, sedangkan Kereta 3678 berangkat dari peron 5A ke rel pelangsiran melalui sisi kanan rel. Kereta 561 dan 3678
Kereta-apidatang
Kereta 3628
MAT 64_4
Kereta-apiberangkat
Kereta 3629
tidak dapat memasuki rel pelangsiran dari sisi yang sama baik kiri maupun kanan. Gamb ar 5 menggambarkan situasi di rel pelangsiran Selasa pukul 06:00 jika unit-unit dari Kereta 561 dan 3678 memasuki rel pelangsiran melalui sisi yang sama (dalam contoh ini melalui sisi kanan rel).
Kereta 561
ICM_4
Kereta 3678
ICM_3
Kereta 520
MAT 64_2
MAT 64_2
Kereta 3629
Gambar 5. Situasi di rel pelangsiran pada Selasa pukul 06:00 jika Kereta 561 dan Kereta 3678 memasuki rel pelangsiran melalui sisi yang sama. Pada Gambar 5, Kereta 520 yang harus berangkat lebih dulu daripada Kereta 3629 akan tertutup dari kedua sisi rel oleh Kereta 3628 dan Kereta 3678. Hal ini disebut crossing dan tidak diperbolehkan karena akan menyulitkan proses pemberangkatan kereta. Selanjutnya, dalam kasus ini Kereta 3628 dan Kereta 3678 yang akan membentuk Kereta-api-berangkat 3629 tidak dapat diparkir berdekatan pada rel pelangsiran yang sama. Hal ini juga akan menyulitkan proses pelangsiran pada pagi hari. Jika rel berupa jalur-bebas, crossing hanya dapat dihindari dengan memarkir beberapa unit pada rel yang berbeda.
3.2 Pendekatan Solusi Untuk mencari solusi dari masalah pelangsiran secara utuh adalah hal yang rumit. Oleh karena itu, untuk memudahkan pencarian solusi dari masalah pelangsiran, pendekatan solusi dipecah ke dalam dua submasalah. Langkah pertama adalah proses pemadanan dari sejumlah unit kereta-apidatang menjadi unit kereta-api-berangkat. Setiap unit kereta-api-datang ditetapkan menjadi unit kereta-api-berangkat. Misalkan berdasarkan tabel waktu pada Tabel 1, unit kereta-api-datang dengan subtipe MAT64_4 dari Kereta 3628 ditetapkan menjadi unit kereta-api-berangkat
19
dengan subtipe yang sama dari Kereta 3629. Hal yang perlu diperhatikan bahwa unit kereta-api-datang dan unit kereta-apiberangkat dari suatu kereta tertentu adalah dua unit kereta dari subtipe yang sama, hanya saja penamaan keretanya yang berbeda. Pada contoh ini kereta yang datang dinamakan Kereta 3628, sedangkan kereta yang berangkat dinamakan Kereta 3629. Hasil dari langkah ini adalah himpunan gabungan dari satu atau lebih unit kereta yang digunakan secara bersama-sama selama periode tertentu yang didefinisikan sebagai blok. Sebagai contoh, unit kereta ICM_4 dan ICM_3 dalam Gambar 4 membentuk sebuah blok karena kedua unit ini digunakan secara bersama-sama pada Kereta 561. Unit kereta ICM_3 dan MAT64_4 tidak membentuk blok karena kedua unit ini tidak digunakan secara bersama-sama dalam pembentukan suatu kereta. Langkah kedua berkaitan dengan pemarkiran unit-unit pelangsiran pada rel-rel pelangsiran. Dalam hal ini, setiap blok diparkir di suatu rel pelangsiran sedemikian sehingga kapasitas rel tidak terlebihi dan crossing tidak terjadi.
0
1
3.2.1 Formulasi Masalah Pemadanan kereta-api-datang menjadi keretaapi-berangkat Untuk setiap kereta-api-datang dan kereta-api-berangkat didefinisikan sebuah network . Simp ul-simpul dari network menyatakan unit-unit kereta dan sebuah simpul rekaan (dummy/simpul 0). Simpulsimpul tersebut dapat mewakili tempattempat di mana unit kereta dapat dibagi ke dalam beberapa part. Part adalah himpunan bagian dari unit-unit kereta yang berdampingan pada suatu kereta api. Sisi berarah pada network mewakili part yang mungkin terbentuk dari suatu kereta. Secara matematis, banyaknya part yang dapat dibentuk dari suatu kereta dapat dinyatakan sebagai kombinasi m C n , dengan m adalah banyaknya simpul dari suatu kereta dan n adalah banyaknya simpul yang berada di antara simpul sumber dan simpul tujuan pada suatu network dari kereta. Gambar 6 menggambarkan suatu network untuk Kereta-api-berangkat 3629 pada Tabel 1.
2
3
Gambar 6. Network dari Kereta 3629 pada Tabel 1. Simpul 0 adalah simpul rekaan, sedangkan simpul 1, 2, 3 adalah unit kereta dari Kereta 3629, yang secara berurutan memiliki subtipe MAT64_4, MAT64_2, MAT64_2. Setiap sisi berarah bersesuaian dengan satu part dan terdapat 6 part yang berbeda yang mungkin pada contoh ini. Himpunan part yang terbentuk pada network di Gambar 6 diperoleh dari kombinasi yang mungkin semua subtipe unit kereta dari Kereta 3629 pada Tabel 1 dan sebuah simpul rekaan. Sebagai contoh sisi berarah (0,1) pada network menyatakan bahwa subtipe MAT64_4 dari Kereta 3629 membentuk suatu part, sedangkan sisi berarah (0,2) menyatakan bahwa subtipe MAT64_4 dan
MAT64_2 dari Kereta 3629 membentuk suatu part. Sebuah path dari simpul pertama sampai yang terakhir pada network ini bersesuaian dengan pembagian kereta ke dalam beberapa part. Sebagai contoh, path 0-2-3 pada Gambar 6 menyatakan bahwa unit kereta 1 dan 2 membentuk satu part dan unit kereta 3 membentuk part yang lain. Sebuah blok merupakan suatu kombinasi dari part-part pada kereta api. Simpul rekaan pada network dari Kereta 3629 dibutuhkan karena terdapat kemungkinan bahwa dua unit kereta membentuk satu part dan unit kereta lainnya membentuk part yang berbeda. Gambar 7 adalah network dari Kereta 3629 pada Tabel 1 tanpa simpul rekaan.
20
1
2
3
Gambar 7. Network dari Kereta 3629 pada
Ct− :
himpunan dari semua simpul-antara di network pada kereta t; simpulantara adalah simpul-simpul yang berada di antara simpul sumber dan simpul tujuan pada suatu network , himpunan part dari kereta-apiberangkat dengan konfigurasi pemadanan yang sama sebagai part dari kereta-api-datang i, himpunan part dari kereta-apidatang dengan konfigurasi pemadanan yang sama sebagai part dari kereta-api-berangkat j.
Ji :
Tabel 1 tanpa simpul rekaan. Jika tidak ada simpul rekaan pada network ini, maka hanya ada 3 part yang mungkin terbentuk. Dalam hal ini path yang dapat dibentuk hanya ada dua. Pertama, path 1-2-3 pada Gambar 7 yang menyatakan bahwa ketiga unit kereta membentuk part yang berbeda, sedangkan yang kedua, path 1-3 pada Gambar 7 yang menyatakan bahwa ketiga unit kereta hanya membentuk 1 part. Misalkan diberikan I sebagai himpunan dari semua part yang mungkin untuk keretaapi-datang dan J sebagai himpunan dari semua part yang mungkin untuk kereta-apiberangkat. Secara formal diperkenalkan sebuah formulasi matematika dengan variabel biner sebagai berikut: 1, jika part i ∈ I digunakan pada suatu kereta-api-datang ui =
Misalkan Q menyatakan penalti untuk setiap part dari kereta-api-datang yang ada di rel pelangsiran tetapi tidak ditetapkan menjadi part dari kereta-api-berangkat. Misalkan pula wij menyatakan ongkos dari penetapan part dari kereta-api-datang i menjadi part dari kereta-api-berangkat j. Dalam tulisan ini ongkos didefinisikan sebagai perbedaan antara waktu datang dan berangkat dari part i dan j. Model matematikanya: Minimumkan Q
∑u + ∑ ∑w z
( 10)
∀t ∈ T a
(11)
i
i∈ I
terhadap ui = 1
∑
ij ij
i ∈I j∈ J i
i ∈ At0+
0, selainnya 1, jika part j ∈ J digunakan pada suatu kereta-api-berangkat vj =
∑ u − ∑u i
i ∈ Ath+
= 0 , ∀t ∈T a , ∀h ∈ Ct−
i
(12)
i ∈Ath−
∑v
j
=1
∀t ∈ T d
(13)
j ∈ A0t+
0, selainnya 1, jika part i ∈ I menjadi part j ∈ J
Ij :
ditetapkan
zij =
∑v − ∑v j
j ∈ Ath+
∑z
j
= 0 , ∀t ∈T d , ∀h ∈ Ct− (14)
j ∈ Ath−
ij
= ui
∀i ∈ I
(15)
ij
= vj
∀j ∈ J
(16)
j ∈J i
0, selainnya Misalkan: T a : himpunan dari kereta-api-datang dengan unit pelangsirannya, d T : himpunan dari kereta-api-berangkat dengan unit pelangsirannya, t A : himpunan sisi berarah pada network dari kereta t, t+ Ah : himpunan sisi berarah yang menjauhi simpul h untuk kereta t, t− Ah : himpunan sisi berarah yang mendekati simpul h pada network kereta t,
∑z i ∈I j
z ij , u i , v j ∈ {0,1} ∀i ∈ I , ∀j ∈ J
(17)
Tujuan dari fungsi objektif (10) adalah meminimumkan jumlah terboboti dari banyaknya part dan ongkos penetapan part dari kereta-api-datang menjadi part dari kereta-api-berangkat sehingga unit-unit kereta dapat dikelompokkan sebanyak mungkin ke dalam suatu part. Kendala (11) dan (12) menjamin tercovernya setiap unit kereta-api-datang oleh sebuah part, sedangkan kendala (13) dan (14) menjamin
21
tercovernya setiap unit kereta-api-berangkat oleh sebuah part. Kendala (15) menjamin bahwa untuk setiap part dari kereta-apidatang ditetapkan menjadi suatu part pada kereta-api-berangkat jika dan hanya jika part dari kereta-api-datang adalah hasil dari pemecahan kereta. Kendala (16) memodelkan hal yang sama untuk setiap part dari kereta-api-berangkat. Kendala (17) menyatakan bahwa variabel yang digunakan adalah variabel 0-1 yang telah didefinisikan. Hasil dari langkah ini adalah himpunan part dari kereta-api-datang yang ditetapkan menjadi part dari kereta-api-berangkat, yang sebelumnya kita sebut dengan blok. Blokblok ini akan digunakan dalam langkah 2. 3.2.2 Formulasi Masalah Penetapan Unit Kereta pada Rel Pelangsiran Seperti telah dijelaskan sebelumnya, pemadanan dari sejumlah unit kereta-apidatang menjadi unit kereta-api-berangkat dari unit pelangsiran menghasilkan sebuah himpunan blok B. Blo k yang tidak perlu diparkir di rel pelangsiran tidak dimasukkan dalam himpunan B ini. Untuk setiap blok diberikan waktu kedatangan dan keberangkatan serta peron kedatangan dan keberangkatan. Selain itu diberikan pula ongkos rute antara rel-rel di depan peron dan semua rel pelangsiran yang fisibel untuk setiap blok. Rel pelangsiran yang fisibel untuk suatu blok adalah rel pelangsiran yang memiliki tipe serta panjang yang sesuai untuk suatu blok. Ongkos rute untuk jalur-bebas dapat berbeda antara sisi kanan dan kirinya. Hal ini disebabkan antara lain karena jarak yang berbeda antara rel-rel di depan peron dengan rel-rel pelangsiran jika dimasuki dari sisi kiri atau kanan. Berdasarkan informasi-informasi di atas, langkah kedua dari pendekatan solusi masalah pelangsiran terdiri dari penetapan blok pada rel pelangsiran dengan ongkos yang minimum sehingga kapasitas dari rel pelangsiran tidak terlebihi dan tidak terjadi crossing antarblok. Crossing terjadi jika suatu blok menghalangi blok yang datang ke rel pelangsiran atau blok yang berangkat dari rel pelangsiran. Submasalah dari penetapan blok pada rel pelangsiran ini disebut sebagai Track Assignment Problem (TAP). TAP diformulasikan sebagai sebuah masalah pemartisian hinpunan dengan kendala tambahan.
Untuk formulasi ini, didefinisikan suatu track assignment, yang disingkat dengan assignment, sebagai sebuah penyusunan dari blok-blok pada rel pelangsiran yang fisibel dalam suatu periode perencanaan. Sebuah assignment dikatakan fisibel jika memenuhi kondisi-kondisi berikut: § assignment tidak mengandung crossing. § panjang total dari unit kereta pelangsiran pada rel tidak melebihi panjang rel. § semua blok mempunyai kesempatan yang sama untuk parkir pada rel. Tabel 1 dan Gambar 1 memuat sebuah contoh assignment yang tidak mengandung crossing dari blok terhadap sebuah rel pelangsiran. Misalkan S adalah himpunan dari rel pelangsiran dan misalkan pula Ks adalah himpunan assignment fisibel pada rel s ∈ S dan Kbs adalah himpunan assignment fisibel pada rel s ∈ S yang mengandung blok b ∈ B. Kemudian didefinisikan variabelvariabel biner berikut: 1, jika assignment fisibel k ∈ Ks digunakan pada rel pelangsiran s ∈S
xks = 0, selainnya
yb =
1, jika blok b ∈ B tidak diparkir pada rel pelangsiran s ∈ S
0, selainnya Misalkan c sk menyatakan ongkos dari suatu assignment k pada rel s. Ongkos ini merupakan jumlah ongkos rute pelangsiran dari blok-b lok yang berbeda pada suatu assignment. Misalkan d menyatakan penalti jika sebuah blok tidak diparkir pada sebuah rel. TAP kemudian diformulasikan sebagai berikut: Minimumkan terhadap
∑ ∑c x
s s k k
s ∈S k ∈K s x ks + s ∈S k ∈K bs
∑∑ ∑x
k∈K s
s k
≤1 ,
+d
yb = 1 ,
∑y
b
(18)
b ∈B
∀ b ∈ B (19)
∀s ∈ S (20)
22
xks ∈{0,1} , ∀s ∈ S , ∀k ∈ K s (21) yb ∈ {0,1} , ∀ b ∈ B (22) Tujuan dari fungsi objektif (18) adalah meminimumkan ongkos dari assignmentassignment yang fisibel serta meminimumkan banyaknya blok yang tidak diparkir pada rel pelangsiran. Kendala (19) menyatakan bahwa setiap blok dicover oleh tepat satu assignment pada satu rel pelangsiran atau tidak diparkir sama sekali. Selanjutnya, kendala (20) menyatakan bahwa setiap rel pelangsiran dapat
mempunyai paling banyak satu assignment. Kendala (21) dan (22) menyatakan bahwa variabel yang digunakan adalah variabel 0-1 yang telah didefinisikan. Kolom pada matriks kendala dari masalah TAP tersebut menunjukkan assignment pada rel pelangsiran tertentu dan baris pada matriks menunjukkan blok dan rel pelangsiran. Jika blok b tercover dalam assignment k pada suatu rel s, maka elemen matriks pada baris b dan kolom ks memiliki nilai 1, dan 0 jika blok b tidak tercover dalam assignment tersebut.
IV PENYELESAIAN MASALAH PENETAPAN BLOK PADA REL PELANGSIRAN DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM Penyelesaian masalah pelangsiran secara utuh dengan menggunakan algoritme simpleks adalah hal yang rumit. Hal ini disebabkan banyaknya assignment yang terbentuk pada masalah penetapan blok di rel pelangsiran. Karena banyaknya variabel yang besar, menyelesaikan masalah minimisasi penetapan blok pada rel pelangsiran dengan menggunakan metode simpleks akan menghabiskan banyak waktu dalam pengerjaannya. Di sini akan dibahas salah satu teknik yang dapat digunakan untuk menyelesaikan masalah penetapan blok pada rel pelangsiran, yaitu teknik pembangkitan kolom atau column generation. Teknik pembangkitan kolom adalah salah satu teknik untuk menyelesaikan suatu pemrograman linear dengan hanya menggunakan sebagian variabel dari masalah keseluruhan. Jika solusi PL tersebut belum mencapai kondisi optimal pada masalah secara keseluruhan, maka dengan kriteria tertentu ditambahkan variabel pada PL tersebut. Setelah itu diselesaikan kembali PL yang telah ditambah tersebut sampai diperoleh suatu kriteria pemberhentian. Masalah induk (master problem/MP) dari masalah ini merupakan masalah pemilihan himpunan assignment yang sesuai dengan model (18) – (22), yaitu:
Minimumkan terhadap
∑ ∑c x
s s k k
s ∈S k ∈K s x ks + s s ∈S k ∈K b
∑∑ ∑x
s k
k∈K s x ks ≥ 0
≤1 ,
+d
∑y
b
b ∈B
yb = 1 , ∀ b ∈ B ∀s ∈ S
,
∀s ∈ S , ∀k ∈ K s
yb ≥ 0 ,
∀b ∈ B
(23)
Masalah induk merupakan masalah PLrelaksasi. Dalam teknik pembangkitan kolom digunakan pemrograman linear masalah induk terbatas (Restricted Master Problem/RMP), yaitu pemrograman linear yang hanya menggunakan sebagian variabel dari MP. Variabel (kolom) yang belum digunakan dalam RMP dibangkitkan berdasarkan nilai variabel dual yang diperoleh dari masalah induk. Oleh karena itu, diperkenalkan variabel dual λ b (b ∈ B) dan µs ( s ∈ S ) berturut-turut untuk kendala (19) dan (20). Biaya tereduksi dari suatu PL dapat diperoleh dari masalah dual PL tersebut. Misalkan Bks adalah himpunan blok dari assignment k yang diparkir pada rel s. Dengan informasi ini, masalah dual dari masalah induk (23) adalah:
23
Maksimumkan
∑λ +∑µ b
b∈ Bks
terhadap λ b + µ s ≤ c ks ,
∑
s
s ∈S
∀s ∈ S , k ∈ K s
(24)
b∈ Bsk
λ1 , λ 2 ,..., λb takterbatas µ1 , µ 2 ,..., µ s ≤ 0 Berdasarkan pemaparan bukti dari Teorema Dualitas Kuat (Nash & Sofer, 1996), kondisi optimal primal yang merupakan biaya tereduksi adalah ekivalen dengan kondisi fisibel pada masalah dual. Sehingga kendala (24) merupakan biaya tereduksi dari masalah induk (23). Misalkan biaya tereduksi tersebut dinotasikan dengan c ks , maka sesuai dengan kendala (24) :
c ks = cks −
∑λ
b
− µ s , ∀s ∈ S , k ∈ K s (25)
b∈B ks
Persamaan (25) mewakili biaya tereduksi dari assignment k pada rel pelangsiran s. Selanjutnya akan didiskusikan representasi network untuk masalah penetapan blok pada rel pelangsiran dan akan diberikan teknik pembangkitan kolom untuk optimisasi penetapan blok pada rel pelangsiran. Hasil dari algoritme ini adalah sebuah himpunan kolom atau himpunan assignment untuk suatu rel pelangsiran. 4.1 Representasi Network dari Masalah Penetapan Blok pada Rel Pelangsiran Representasi network digunakan untuk membangkitkan assignment-assignment pada satu rel pelangsiran. Misalkan F adalah himpunan tipe pendekatan yang berbeda dari dan ke suatu rel pelangsiran. Untuk suatu jalur-satu-arah, F hanya mengandung satu elemen, yaitu datang dari dan berangkat ke arah yang sama, baik kiri (LL) atau kanan (RR). Sedangkan untuk suatu jalur-bebas, F mengandung 4 elemen: § Datang dari kiri dan berangkat ke kiri (LL) § Datang dari kiri dan berangkat ke kanan (LR) § Datang dari kanan dan berangkat ke kiri (RL) § Datang dari kanan dan berangkat ke kanan (RR) Untuk memudahkan pembentukan assignment pada tulisan ini diasumsikan
bahwa himpunan blok B yang perlu diparkir disusun secara berurutan berdasarkan waktu kedatangan. Setiap blok b ∈ B diwakili oleh suatu lapisan ke -b dalam suatu rel pelangsiran atau disebut juga sebagai lapisan Lb yang terdiri
dari
simpul-simpul
n bf
dengan
b f ∈ F dan simpul nnot yang berpadanan dengan tidak diparkirnya suatu blok b pada rel. Simpul-simpul pada network memuat sebuah simpul sumber o, sebuah simpul tujuan t dan untuk setiap blok b terdapat lapisan Lb . Karena blok-blok disusun secara berurutan berdasarkan waktu kedatangan, maka blok yang pertama kali harus diparkir di rel pelangsiran diwakili oleh lapisan L1 , blok yang kedua datang diwakili oleh lapisan L2 , dan seterusnya. Sisi-sisi berarah pada network ini diarahkan dari simpul sumber ke setiap simpul pada lapisan pertama, dari setiap simpul di lapisan terakhir ke simpul tujuan, dan antara dua simpul pada lapisan-lapisan yang berturutan antara simpul sumber dan simpul tujuan jika blok-blok yang berhubungan dapat diparkir pada suatu rel tanpa terjadi crossing. Sisi yang menghasilkan crossing dikatakan sisi yang takfisibel. Misalkan didefinisikan B − sebagai himpunan dari blok tanpa adanya crossing, kemudian didefinisikan sebuah network G = ( N , A) yang telah dijelaskan di atas sebagai :
N = U Lb ∪ {o, t } A=
b∈B nib , n bj+1
{(
): b ∈ B
−
(26)
, i ∈ Lb , j ∈ Lb+1 dan
(n , n ) adalah fisibel } ∪
(27)
{(o, n ): i ∈ L }∪ n
(28)
b i
b +1 j
1 i
dengan
1
B
B j
, t : j ∈ L B
adalah banyaknya anggota
(kardinalitas) himpunan B. Pada Gambar 8 diilustrasikan network dengan 3 blok untuk sebuah jalur-bebas. Network ini mewakili rencana pemarkiran dari 3 blok yang datang ke peron kedatangan dengan rencana pelangsiran pada Tabel 1 untuk sebuah jalur-bebas.
24
G: L1
o
L2
L3
LL
LL
LL
LR
LR
LR
RL
RL
RL
RR
RR
RR
not
not
not
t
Gambar 8. Contoh dari sebuah network untuk jalur-bebas dengan 3 blok.
Pada Gambar 8, berdasarkan waktu kedatangan seperti yang telah diberikan pada Tabel 1 lapisan L1 mewakili blo k 1 yaitu Kereta 3628, lapisan L2 mewakili blok 2 yaitu Kereta 561, dan lapisan L3 mewakili blok 3 yaitu Kereta 3678. Sisi-sisi berarah yang dicetak tebal dalam gambar ini mewakili sebuah path dalam network ini. Path ini membentuk sebuah asssignment di mana semua blok diparkir di rel. Dalam hal ini assignment yang terbentuk adalah blok pertama datang dari kiri dan berangkat dari sisi kanan, sedangkan blok kedua datang dan berangkat dari sisi kiri, dan blok ketiga datang dan berangkat dari sisi kanan. Assignment ini adalah assignment yang tidak mengandung crossing karena tidak me muat sisi-sisi berarah yang takfisibel. Sebagai contoh, tidak ada sisi berarah dari simpul ’RR’ di lapisan L2 ke simpul ’RR’ di lapisan L3 . Karena jika Kereta 561 dan Kereta 3678 datang dan berangkat dari rel pelangsiran melalui sisi kanan, maka Kereta 561 yang harus berangkat lebih dulu daripada Kereta 3678 akan tertutup dari sisi kanan rel. Hal ini akan menyebabkan sisi berarah menghasilkan crossing atau dikatakan sisi berarah yang takfisibel seperti yang telah diilustrasikan pada Gambar 5 yang selanjutnya akan menghasilkan assignment yang takfisibel.
Simpul ’not’ pada setiap blok mengandung arti setiap blok memiliki kemungkinan untuk tidak diparkir pada rel tersebut. Jika path yang terbentuk adalah onot-not-not-t, maka dalam contoh di atas tidak ada satu pun blok yang diparkir pada rel ini. Ongkos-ongkos didefinisikan pada sisisisi berarah dari network. Ongkos dari sebuah sisi berarah mewakili ongkos dari simpul ke mana sisi berarah tersebut diarahkan, yang merupakan ongkos dari penetapan blok tertentu ke rel pelangsiran tertentu, yang datang dari dan berangkat ke rel ini baik lewat sisi kiri atau kanannya. Ongkos rute blok-blok yang menyusun suatu path dari rel di depan peron kedatangan ke rel pelangsiran tertentu dan kembali ke rel di depan peron keberangkatan. Sebagai contoh, ongkos pada sisi berarah dari simpul sumber o ke LL pada lapisan L1 adalah ongkos pelangsiran blok pertama yang datang dari rel di depan peron ke rel pelangsiran melalui sisi kiri dan berangkat dari rel ini lewat sisi kiri pula. Ongkos-ongkos pada sisi-sisi berarah ke simpul tujuan t menyatakan penggunaan dari suatu rel pelangsiran s. Semua path yang terbentuk pada network mewakili assignment yang tidak mengandung crossing. Sebuah path dalam
25
network mewakili assignment fisibel terhadap rel jika beberapa kendala tambahan terpenuhi. Kendala-kendala ini berhubungan dengan panjang dari blok-blo k pada rel serta waktu kedatangan dan keberangkatannya. 4.2 Memeriksa Kefisibelan Suatu Assignment dengan Menggunakan Algoritme Pemrograman Dinamik Assignment-assignment yang diperoleh dari representasi network pada bagian 4.1 belum tentu fisibel, karena kefisibelan suatu assignment juga harus memenuhi syarat bahwa panjang total dari blok yang menyusun suatu assignment tidak boleh melebihi panjang rel yang digunakan. Artinya banyaknya gerbong kereta suatu assignment tidak boleh melebihi banyaknya gerbong kereta maksimum yang dapat dimuat pada suatu rel pelangsiran. Untuk memeriksa kefisibelan suatu assignment digunakan algoritme pemrograman dinamik. Misalkan didefinisikan Pi sebagai himpunan path fisibel (o-i) di G. Selain itu didefinisikan pula l (i,..., j ) sebagai panjang dari path ( i,..., j) dengan i adalah simpul pertama dan j adalah simpul terakhir dalam suatu path di graf G, serta b j sebagai predesesor dari simpul j pada graf G. Untuk memeriksa kefisibelan suatu assignment digunakan algoritme pemrograman dinamik dengan prosedur sebagai berikut: Untuk setiap simpul i ∈ N Untuk setiap path p ∈ Pi Untuk setiap sisi berarah i, j ∈ A
P jnew = CheckRules( p (i, j )) Jika P jnew ada, maka
memeriksa kefisibelan suatu assignment tinggal diperiksa panjang assignmentnya saja. Jika l (i,..., j ) ≤ r, maka path
( i,..., j) akan membentuk assignment fisibel, dengan r adalah panjang dari suatu rel s. Sebaliknya jika l (i,..., j ) > r, maka path ( i,..., j) akan membentuk assignment takfisibel. Selain itu perlu pula memeriksa kedominanan suatu path. Sebuah path pi dikatakan didominasi oleh path pj (atau dikatakan path pj lebih baik daripada path p i ) jika beberapa kendala pada path pi lebih baik daripada kendala pada path p j . Sebagai contoh, jika terdapat 2 path p1 dan p 2 yang memiliki total panjang blok yang sama pada rel tertentu namun path p1 memerlukan biaya lebih besar daripada path p2 , maka path p1 dikatakan didominasi oleh path p2 . Pemeriksaan kedominanan suatu path dilakukan pada simpul-simpul di blo k terakhir dalam suatu graf. Hal ini dikarenakan, suatu path baru dapat dibandingkan dengan path lainnya jika proses pemeriksaan kefisibelan suatu path telah selesai dilakukan. Selanjutnya path yang didominasi tidak diperhitungkan dalam proses pembangkitan kolom, sehingga tidak perlu dicari biaya tereduksinya. 4.3 Teknik Pembangkitan Kolom untuk Optimisasi Penetapan Block pada Rel Pelangsiran Misalkan RMP pada langkah tertentu j, dinotasikan dengan RPj dapat dinyatakan sebagai: Minimumkan c sk xks + d yb
∑∑
∑∑
terhadap
UpdatePathList ( Pj , P jnew )
∑x
End
b∈B
+ yb = 1 , ∀ b ∈ B
s k
≤1 ,
∀s ∈ S
k∈K sj
End
Karena path-path yang terbentuk pada graf G sudah membentuk assignment-assignment yang tidak mengandung crossing, oleh karena itu dalam algoritme ini untuk
xks
s ∈S k ∈ K bs j
End
Dalam fungsi CheckRules( p(i, j )) , beberapa aturan diperiksa untuk menentukan apakah path baru yang diperoleh dengan menambahkan sisi berarah (i,j) pada path p adalah fisibel. Jika path tersebut fisibel, maka path yang diperluas tadi menjadi sebuah path baru yang dinamakan P jnew .
∑
s ∈S k ∈ K sj
x ks ≥ 0 ,
∀s ∈ S , ∀ k ∈ K sj
yb ≥ 0 , K sj
{
∀b ∈ B
}
⊆ K = 1 ,2 ,... k ,..., 1 , 2 s ,..., k s , s
1
1
1
s
s
dengan k menyatakan assignment k pada rel s pelangsiran s. Himpunan K j menyatakan
himpunan indeks elemen Ks yang dipilih. Misalkan K s = 11 ,31 ,51 ,2 2 ,4 2 ,7 2 ,2 3 , 53 merupakan himpunan assignment fisibel k pada rel s. Kemudian misalkan dipilih assignment 1 pada rel 1, assignment 4 pada
{
}
26
rel 2, dan assignment 2 pada rel 3 pada suatu RPj , maka assignment tersebut diurutkan kembali sebagai K sj = 11 ,1 2 ,13 . Teknik
{
}
Minimumkan terhadap
Inisialisasi Didefinisikan masalah terkendala awal
RP0 : Minimumkan
∑ ∑c s ∈S k∈ K0s
terhadap
∑∑
x ks
s s k xk
+d
∑y b ∈B
+ y b = 1 , ∀b ∈ B
s ∈S k∈ Kbs 0
∑x
s k
≤1 ,
∀s ∈ S
k∈K 0s
x ks ≥ 0 , yb ≥ 0 ,
∀s ∈ S, ∀k ∈ K 0s ∀b ∈ B
dengan K0s adalah himpunan indeks dari assignment fisibel yang terdapat dalam RP0 . Pada langkah inisialisasi ini, sebagian dari assignment yang menghasilkan solusi fisibel dipakai sebagai input. Assignment ini digunakan sebagai variabel pada RMP. c.
Langkah Tertentu Pada langkah tertentu j didefinisikan RMP sebagai berikut : RPj :
∑ ∑x
∑x
s k
∑y
b
b∈B
+ yb = 1 , ∀ b ∈ B
s k
≤ 1,
∀s ∈ S
k∈ K sj
x ks ≥ 0 , yb ≥ 0 , dengan
K sj
∀s ∈ S , ∀ k ∈ K sj ∀b ∈ B
⊆K . s
Adapun tahap-tahap penyelesaian langkah ke -j adalah sebagai berikut: •
Penyelesaian RPj dengan Menggunakan Metode Simpleks RPj diselesaikan menggunakan metode simpleks, sehingga diperoleh nilai variabel dual λ b (b ∈ B ) untuk kendala (19) dan
µ s (s ∈ S ) untuk kendala (20).
•
b
+d
k ∈ K sj
s ∈S k ∈ K bs j
a.
b.
s s k k
s ∈S
pembangkitan kolom untuk optimisasi penetapan blok pada rel pelangsiran yang dimodifikasi dari teknik serupa dalam (Lavoie et al., 1988) adalah sebagai berikut: Membangun data input Blok-blok didaftarkan dengan informasinya, yaitu waktu kedatangan dan keberangkatan serta peron kedatangan dan keberangkatan. Selain itu, didaftarkan pula assignment-assignment fisibel yang dapat dibentuk dari blok-blok tersebut. Assignment ini dibentuk dengan menggunakan konsep network dan algoritme pemrograman dinamik yang telah dijelaskan pada bagian 4.1 dan 4.2.
∑ ∑c x
Prosedur Pembangkitan Kolom Prosedur pembangkitan kolom adalah proses pencarian kolom dari semua assignment fisibel yang memiliki biaya tereduksi negatif. Berdasarkan nilai-nilai variabel dual pada RP0 , maka biaya tereduksi dari assignment fisibel k pada rel pelangsiran s dapat dihitung dengan menggunakan (25). Jika biaya tereduksi yang dihasilkan dari masing-masing assignment k adalah taknegatif, maka proses selesai, dan solusi pada RP0 adalah solusi dari TAP. Sebaliknya, jika terdapat assignment k yang memiliki biaya tereduksi negatif maka variabel yang berpadanan dengan assignment yang memiliki biaya tereduksi ”paling negatif” ditambahkan pada RP0 sehingga membentuk RP1 . Proses diulangi sampai tidak diperoleh lagi assignment yang memiliki biaya tereduksi negatif sehingga diperoleh RPj , dengan j = 1,2,3,… Solusi pada RPj , yaitu solusi ke-j (j = 1,2,3,…) yang tidak memuat lagi assignment yang mengandung biaya tereduksi negatif adalah solusi dari TAP.
27
V CONTOH KASUS PELANGSIRAN UNIT KERETA PENUMPANG PADA STASIUN KERETA 5.1 Penyelesaian Masalah Pemadanan Kereta-api -datang Menjadi Keretaapi-berangkat dengan Menggunakan LINDO 6.1 Misalkan diberikan tabel waktu seperti pada Tabel 1, maka dapat didaftarkan semua part yang mungkin terbentuk untuk setiap kereta-api-datang dan kereta-apiberangkat. Setiap angka pada sisi berarah menunjukkan indeks dari part yang terbentuk. §
Pada Gambar simpul rekaan, 2 adalah unit yang memiliki MAT64_2. §
§
2
9
10
12 13
Gambar 12. Network dari Kereta 3629 pada Tabel 1. Pada Gambar 12, simpul 0 adalah simpul rekaan, sedangkan simpul 1, 2, 3 adalah unit kereta dari Kereta 3629, yang secara berurutan memiliki subtipe MAT64_4, MAT64_2, MAT64_2.
Gambar 9. Network dari Kereta 3628 pada Tabel 1. Pada Gambar 9, simpul 0 adalah simpul rekaan, sedangkan simpul 1 adalah unit kereta dari Kereta 3628 yang memiliki subtipe MAT64_4.
1
8
11
1
1
Untuk Kereta-api-berangkat 3629 0
Untuk Kereta-api-datang 3628 0
11, simpul 0 adalah sedangkan simpul 1 dan kereta dari Kereta 3678 subtipe yang sama yaitu
§
Untuk Kereta-api-berangkat 520 0
14
1
2 15
Untuk Kereta-api-datang 561 0
2
1
3
2
16
Gambar 13. Network dari Kereta 520 pada Tabel 1. 4
Gambar 10. Network dari Kereta 561 pada Tabel 1. Pada Gambar 10, simpul 0 adalah simpul rekaan, sedangkan simpul 1 dan 2 adalah unit kereta dari Kereta 561 yang berturut-turut memiliki subtipe ICM_4, ICM_3. §
Untuk Kereta-api-datang 3678 0
5
1
6
2
7
Gambar 11. Network dari Kereta 3678 pada Tabel 1.
Pada Gambar 13, simpul 0 adalah simpul rekaan, sedangkan simpul 1 dan 2 adalah unit kereta dari Kereta 520 yang berturut-turut memiliki subtipe ICM_4, ICM_3. Jadi, himpunan part dari kereta-apidatang diberikan oleh himpunan I = {1,2,3,4,5, 6,7} dan himpunan part dari kereta-api-berangkat diberikan oleh himpunan J = {8,9,10,11,12,13,14,15,16} . Berdasarkan Tabel 1, himpunan keretaapi-datang adalah T a = {3628,561,3678} , sedangkan himpunan kereta-api-berangkat diberikan oleh T d = {3629,520} . Pada bagian 3.2, telah dijelaskan bahwa sisi berarah pada network mewakili part yang mungkin terbentuk dari suatu kereta.
3
28
Misalkan didefinisikan himpunan sisi berarah pada network dari kereta t sebagai At . Jadi, diperoleh himpunan A3628 = {} 1,
A561 = {2,3,4} ,
A3678 = {5,6,7} ,
A3629 = {8,9,10,11,12,13} , A520 = {14,15,16} . Himpunan sisi berarah yang menjauhi/mendekati simpul h pada network kereta t diberikan oleh himpunan Aht + / Aht− . §
- A2561+ = { }
0, selainnya 1, jika part j ∈ J digunakan pada suatu kereta-api-berangkat vj = 0, selainnya
Untuk kereta-datang 3678 - A03678+ = {5,7} - A03678− = { } -
A13678+
= {6}
-
A23678+
={ }
-
A13678−
= {5}
-
A23678−
= {6,7}
I j . Jadi,
ui =
- A1561− = {2}
- A2561− = {3,4}
himpunan
1, jika part i ∈ I digunakan pada suatu kereta-api-datang
Untuk kereta-datang 561 - A0561+ = {2, 4} - A0561− = { } - A1561+ = {3}
§
- A13628− = {} 1
oleh
J 1 = {8} , J 2 = {14} , J 3 = {15} , J 4 = {16} , J 5 = {9} , J 6 = {10} , J 7 = {12} , I 8 = {} 1 , I 9 = {5} , I 10 = {6} , I 11 = { } , I 12 = {7} , I 13 = { } , I 14 = {2} , I 15 = {3} , I 16 = {4} . Untuk menentukan solusi dari masalah pemadanan kereta-api-datang menjadi kereta-api-berangkat, terlebih dahulu didefinisikan:
Untuk kereta-datang 3628 - A03628+ = {} 1 - A03628− = { } - A13628+ = { }
§
j diberikan
1, jika part i ∈ I menjadi part j ∈ J
ditetapkan
zij = 0, selainnya
§
Untuk kereta-berangkat 3629 - A03629+ = {8,11,13} - A03629− = { } - A13629+ = {9,12}
- A13629− = {8}
- A33629+ = { }
- A33629− = {10,12,13}
- A23629+ = {10}
§
- A23629− = {9,11}
Untuk kereta-berangkat 520 - A0520+ = {14,16} - A0520− = { } - A1520+ = {15} - A2520+ = { }
- A1520− = {14}
- A2520− = {15,16}
Himpunan semua simpul-antara di network pada kereta t diberikan oleh − himpunan Ct− . Jadi, C3628 = { }, − C561 = {1} ,
− C3678 = {1} ,
− C 3629 = {1, 2} ,
− C520 = {} 1. Himpunan part dari kereta-apiberangkat dengan konfigurasi pemadanan yang sama sebagai part dari kereta-apidatang i diberikan oleh himpunan J i , sedangkan himpunan part dari kereta-apidatang dengan konfigurasi pemadanan yang sama sebagai part dari kereta-api-berangkat
dengan I = {1,2,3,4,5, 6,7} dan
J = {8,9,10,11,12,13,14,15,16} .
Misalkan penalti Q untuk setiap part dari kereta-api-datang yang ada di rel pelangsiran tetapi tidak ditetapkan menjadi part dari kereta-api-berangkat adalah sebesar 50. Selain itu ongkos penetapan part i menjadi part j, yaitu wi, j dirumuskan sebagai perbedaan antara waktu datang dan berangkat dari part i dan j (dalam jam) . Berdasarkan Tabel 1, maka akan diperoleh:
w1,8 = 20 . 67 , w2 ,14 = w3,15 = w4 ,16 = 10 .27 , w5, 9 = w6 ,10 = w7 ,12 = 7 .1 . Berdasarkan informasi-informasi di atas, maka model matematika untuk contoh ini adalah: Minimumkan 50(u1 + u2 + u3 + u4 + u5 + u6 + u 7 ) +
20 .67 z1,8 + 10.27 (z 2,14 + z 3,15 + z 4,16 ) + 7.1(z 5, 9 + z 6,10 + z 7,12 )
29
terhadap
u1 = 1 u2 +u4 =1 u5 + u 7 = 1
(29)
u3 − u 2 = 0 u6 − u5 = 0 v8 + v11 + v13 = 1 v14 + v16 = 1 v9 + v12 − v8 = 0 v10 − v9 − v11 = 0 v15 − v14 = 0 z1, 8 = u 1
(32)
z 2 ,14 = u 2
(40)
z 3 ,15 = u 3
(41)
z 4,16 = u 4
(42)
z 5 ,9 = u 5
(43)
z 6 ,10 = u 6
(44)
z 7 ,12 = u 7
(45)
z1, 8 = v8
(46)
z 2 ,14 = v14
(47)
z 3,15 = v15
(48)
z 4 ,16 = v16
(49)
z 5 ,9 = v9
(50)
z 6 ,10 = v10
(51)
z 7 ,12 = v12
(52)
(30) (31) (33) (34) (35) (36) (37) (38) (39)
Kendala (29) menyatakan bahwa himpunan part dari kereta-api-datang yang menjauhi simpul 0 pada Kereta 3628 harus dipilih tepat satu part. Kendala (30) dan (31) secara berturut-turut menyatakan hal yang sama untuk Kereta 561 dan 3678. Kendala (32) menyatakan bahwa himpunan part dari kereta-api-datang yang menjauhi setiap simpul-antara pada Kereta 561 dipilih jika dan hanya jika himpunan part yang mendekati setiap simpul-antara tersebut dipilih. Kendala (33) menyatakan hal yang sama untuk Kereta 3678. Kendala (34) dan (35) secara berturut-turut untuk Kereta 3629 dan 520 menyatakan bahwa himpunan part dari kereta-api-berangkat yang menjauhi simpul 0 harus dipilih tepat satu part. Kendala (36) dan (37) menyatakan bahwa himpunan part dari kereta-api-berangkat yang menjauhi setiap simpul antara pada Kereta 3629 dipilih jika dan hanya jika himpunan part yang mendekati setiap simpul-antara tersebut dipilih. Kendala (38)
menyatakan hal yang sama untuk Kereta 520. Kendala (39)-(45) menyatakan bahwa part dari kereta-api-datang i pada kereta-apidatang yang ditetapkan menjadi part j dari kereta-api-berangkat akan dipilih jika dan hanya jika part i dipilih. Sebagai contoh, Kendala (39) menyatakan bahwa part 1 pada Kereta 3628 yang ditetapkan menjadi part 8 pada Kereta 3629 akan dipilih jika dan hanya jika part 1 dipilih. Kendala (46)-(52) menyatakan bahwa part i dari kereta-apidatang yang ditetapkan menjadi part j dari kereta-api-berangkat akan dipilih jika dan hanya jika part j dipilih. Sebagai contoh, Kendala (46) menyatakan bahwa part 1 pada Kereta 3628 yang ditetapkan menjadi part 8 pada Kereta 3629 akan dipilih jika dan hanya jika part 8 dipilih. Dengan menggunakan LINDO 6.1 diperoleh hasil optimal sebagai berikut (lihat Lampiran 3) : u1 = u 4 = u 7 = v8 = v12 = v16 = z1, 8 = z 4,16 =
z 7,12 = 1, u 2 = u 3 = u5 = u 6 = v 9 = v10 = v11 = v13 = v14 = v15 = z 2,14 = z 3,15 = z 5,9 = z 6,10 = 0 dan nilai objektif sebesar 188.04. Dari langkah pemadanan kereta-apidatang menjadi kereta-api-berangkat diperoleh himpunan part dari kereta-apidatang yang ditetapkan menjadi part pada kereta-api-berangkat atau disebut dengan blok. Hasil di atas menunjukkan bahwa terdapat 3 blok yang terbentuk, yaitu part 1 (Kereta 3628) yang ditetapkan menjadi part 8 (Kereta 3629), part 4 (Kereta 561) yang ditetapkan menjadi part 16 (Kereta 520) , dan part 7 (Kereta 3678) yang ditetapkan menjadi part 12 (Kereta 3629). 5.2 Penyelesaian Masalah Penetapan Blok pada Rel Pelangsiran dengan Menggunakan Teknik Pembangkitan Kolom. 1
Membangun Data Input Dari langkah pemadanan kereta-apidatang menjadi kereta-api-berangkat diperoleh 3 blo k yang akan diparkir di rel-rel pelangsiran yaitu Kereta 3628, Kereta 561, dan Kereta 3678 yang peron kedatangan dan keberangkatan serta waktu kedatangan dan keberangkatan diberikan pada Tabel 1. Misalkan keadaan di suatu stasiun yang sesuai dengan Tabel 1 dan memiliki 2 jalur-
30
bebas yaitu rel pelangsiran 1 dan 2, serta memiliki 1 jalur-satu-arah yaitu rel pelangsiran 3 (hanya dapat dimasuki dari
sisi kiri) seperti yang diilustrasikan pada Gambar 14.
Peron 1A Rel 1 Peron 5A Rel 2 Peron 5B Rel 3 Peron 3B Gambar 14. Keadaan di stasiun yang sesuai dengan Tabel 1 dan memiliki 2 jalur-bebas dan 1 jalur-satu-arah. Blok-blok yang akan diparkir tersebut disusun secara berurutan berdasarkan waktu kedatangannya. Berdasarkan Tabel 1, Kereta 3628 adalah kereta yang pertama tiba di peron 5A, oleh karena itu Kereta 3628 harus diletakkan paling pertama di rel pelangsiran. Setelah itu, Kereta 561 dan Kereta 3678 secara berturut-turut diletakkan di rel pelangsiran. Dalam graf G, Kereta 3628 diwakili oleh lapisan L1 , Kereta 561 diwakili oleh lapisan L2 , dan Kereta 3678 diwakili oleh lapisan L3 . Berdasarkan informasiinformasi di atas, maka semua path fisibel untuk masing-masing rel pelangsiran dapat diilustrasikan pada sebuah network dengan 3 blok. Salah satu contohnya adalah seperti yang telah diilustrasikan pada Gambar 8. Assignment yang tidak mengandung crossing untuk jalur-bebas 1 dan 2 dapat digambarkan pada network dengan banyaknya simpul-antara adalah 15, yaitu
L1 LL
banyaknya blok (ada 3 blok) dikalikan dengan banyaknya pendekatan dari blok ke suatu rel pelangsiran (ada 4 pendekatan : LL, LR, RL, RR) ditambah dengan simpul ‘not’ untuk masing-masing blok (ada 3 simpul ‘not’). Assignment yang tidak mengandung crossing untuk jalur-satu-arah 3 dapat digambarkan pada network dengan banyaknya simpul-antara adalah 6, yaitu banyaknya blok (ada 3 blok) dikalikan dengan banyaknya pendekatan dari blo k ke suatu rel pelangsiran (ada 1 pendekatan : LL) ditambah dengan simpul ‘not’ untuk masing-masing blok (ada 3 simpul ‘not’). Network yang terbentuk pada rel pelangsiran 1 dan 2 sama seperti yang telah diilustrasikan pada Gambar 8, sedangkan network yang terbentuk pada rel pelangsiran 3 dapat dilihat pada Gambar 15.
L2 LL
L3 LL
o
t not
not
not
Gambar 15. Network yang terbentuk dari assignment yang tidak mengandung crossing pada rel pelangsiran 3. Misalkan biaya penggunaan dari rel pelangsiran 1, 2, dan 3 berturut-turut sebesar
35, 30, 25. Selain itu, misalkan biaya penalti d jika sebuah blok tidak diparkir pada
31
sebuah rel ditetapkan sebesar 50, maka ongkos dari masing-masing assignment dapat dihitung. Tabel 2 adalah daftar biaya
ID Kereta
dari pemarkiran blok ke rel pelangsiran 1, 2, atau 3 melalui pendekatan yang berbeda dari dan ke suatu rel pelangsiran.
Tabel 2. Daftar biaya pemarkiran blok ke rel pelangsiran 1, 2, dan 3 Biaya Pemarkiran Blok Rel Pelangsiran 1 Rel Pelangsiran 2 Rel Pelangsiran 3 LL LR RL RR LL LR RL RR LL
3628 (blok 1)
5
9
9
16
6
9
9
14
9
561 (blok 2)
10
11
11
16
6
11
11
18
5
3678 (blok 3)
12
13
13
18
8
13
13
20
7
Tabel 3 adalah daftar assignment yang tidak mengandung crossing seperti yang telah digambarkan pada Gambar 8 dan 15 beserta biayanya masing-masing. Biaya suatu assignment diperoleh dari jumlah biaya masing-masing blok yang menyusun suatu assignment yang telah diberikan pada Tabel 2 ditambah dengan biaya penggunaan suatu rel tertentu. Sebagai contoh, biaya dari assignment 1 yang akan diparkir di rel pelangsiran 1 adalah sebesar 63. Nilai ini
diperoleh dari penjumlahan ongkos rute dari Kereta 3628 yang datang dan berangkat melalui sisi kiri yaitu sebesar 5, ongkos rute dari Kereta 561 yang datang dan berangkat melalui sisi kiri yaitu sebesar 10, ongkos rute dari Kereta 3678 yang datang melalui sisi kanan dan berangkat melalui sisi kiri yaitu sebesar 13, serta biaya karena menggunakan rel pelangsiran 1 yang sebelumnya telah ditetapkan sebesar 35.
Tabel 3. Daftar assignment yang tidak mengandung crossing serta biayanya masing-masing Assignment k pada Assignment k pada Biaya Biaya Blok-blok Blok-blok rel pelangsiran s rel pelangsiran s s ( ck ) ( c ks ) penyusun penyusun ( x ks ) ( x ks )
x11 x12 x13 x14 x 15 x16 x17 x18 x 19 x110 1 x11 x112 x113 x114 x115 x116 x117 x118
63
x 42
LL, RR, LL
62
LL, LL, RR
68
LL, RR, LR
67
LL, LL, not
100
LL, RR, not
104
LL, RR, LL
68
LL, not, LL
94
LL, RR, LR
69
x 52 x 62 x 72 x 82 x 92 2 x10 2 x11 2 x12 2 x13 2 x14 2 x15 2 x16 2 x17 2 x18 2 x19 2 x 20 x 221
LL, not, LR
99
LL, not, RL
99
LL, not, RR
106
LL, not, not
136
LR, LL, RL
58
LR, LL, RR
65
LR, LL, not
95
LR, RR, LL
65
LR, RR, LR
70
LR, RR, not
107
LR, not, LL
97
LR, not, LR
102
LR, not, RL
102
LR, not, RR
109
LL, LL, RL
LL, RR, not
106
LL, not, LL
102
LL, not, LR
103
LL, not, RL
103
LL, not, RR
108
LL, not, not
140
LR, LL, RL
67
LR, LL, RR
72
LR, LL, not
104
LR, RR, LL
72
LR, RR, LR
73
LR, RR, not
110
LR, not, LL
106
32
x119 x 120 x121 x 122 x123 x 124 x125 x 126 x 127 x128 x 129 x130 x131 x132 x133 x134 x135 x136 x 137 x138 x139 x 140 x 141 x 142 x143 x 144 x145 x 146 x 147 x148 x 149 x 150 x 151 x 152 x 153 x 154 x 155 x 156
107
2 x 22
LR, not, not
139
LR, not, RL
107
RL, LL, RL
58
LR, not, RR
112
RL, LL, RR
65
LR, not, not
144
RL, LL, not
95
RL, LL, RL
67
RL, RR, LL
65
RL, LL, RR
72
RL, RR, LR
70
RL, LL, not
104
RL, RR, not
107
RL, RR, LL
72
RL, not, LL
97
RL, RR, LR
73
RL, not, LR
102
RL, RR, not
110
RL, not, RL
102
RL, not, LL
106
RL, not, RR
109
RL, not, LR
107
RL, not, not
139
RL, not, RL
107
RR, LL, LR
63
RL, not, RR
112
RR, LL, RR
70
RL, not, not
144
RR, LL, not
100
RR, LL, LR
74
RR, RR, LL
70
RR, LL, RR
79
RR, RR, LR
75
RR, LL, not
111
RR, RR, not
112
RR, RR, LL
79 80
RR, not, LL RR, not, LR
102
RR, RR, LR RR, RR, not
117
RR, not, RL
107
RR, not, LL
113
RR, not, RR
114
RR, not, LR
114
RR, not, not
144
RR, not, RL
114
not, LL, RL
99
RR, not, RR
119
not, LL, RR
106
RR, not, not
151
not, LL, not
136
not, LL, RL
108
not, LR, LL
99
not, LL, RR
113
not, LR, LR
111
not, LL, not
145
not, LR, not
141
not, LR, LL
108
not, RL, RL
104
not, LR, LR
109
not, RL, RR
111
not, LR, not
146
not, RL, not
141
not, RL, RL
109
not, RR, LL
106
not, RL, RR
114
not, RR, LR
111
not, RL, not
146
not, RR, not
148
not, RR, LL
113
not, not, LL
138
not, RR, LR
114
not, not, LR
143
not, RR, not
151
x 223 2 x 24 x 225 2 x 26 2 x 27 x 228 2 x 29 2 x30 2 x31 2 x32 2 x33 2 x34 2 x35 2 x36 2 x 37 2 x38 2 x39 2 x 40 2 x 41 2 x 42 x 243 2 x 44 x 245 2 x 46 2 x 47 x 248 2 x 49 2 x 50 2 x 51 2 x 52 2 x 53 2 x 54 2 x 55 2 x 56 2 x 57 2 x 58 2 x 59
not, not, RL
143
LR, not, LR
107
33
x 157
147
2 x 60
not, not, RR
150
not, not, LR
148
not, not, not
150
not, not, RL
148
LL, LL, not
89
not, not, RR
153
LL, not, LL
91
not, not, not
150
LL, not, not
134
LL, LL, RL
55
not, LL, not
130
LL, LL, RR
62
not, not, LL
132
LL, LL, not
92
2 x 61 x13 x23 x33 x43 x 53 x 36
not, not, not
150
not, not, LL
x 158 x 159 x 160 x 161 x12 x 22 x 32
Himpunan assignment yang didaftarkan pada Tabel 3 belum tentu fisibel, untuk memeriksa kefisibelan suatu assignment digunakan algoritme pemrograman dinamik.
semua path dihitung biaya tereduksinya perlu diperiksa kedominanan suatu path. Misalkan dalam contoh ini, rel pelangsiran 1, 2, dan 3 berturut-turut dapat memuat paling banyak 8, 12, dan 15 gerbong kereta. Diketahui pula dari Tabel 1 bahwa Kereta 3628, Kereta 561, dan Kereta 3678 berturut-turut memiliki 4, 7, dan 4 gerbong. Untuk kemudahan, pada algoritme ini digunakan notasi i = 1,2 ,...,15 untuk masing-masing simpul-antara pada graf G pada jalur-bebas dan notasi i = 1, 2,..., 6 untuk masing-masing simpul-antara pada graf G pada jalur-satu-arah. Gambar 16 adalah graf G yang terbentuk dari assignment yang tidak mengandung crossing untuk rel pelangsiran 1 dan 2, sedangkan Gambar 17 adalah graf G untuk rel pelangsiran 3.
2
Memeriksa Kefisibelan Suatu Assignment dengan Menggunakan Algoritme Pemrograman Dinamik Setiap assignment yang terbentuk pada graf G yang telah diilustrasikan pada Gambar 8 dan Gambar 15 akan diperiksa kefisibelannya. Path-path yang terbentuk pada graf G di Gambar 8 dan Gambar 15 membentuk assignment-assignment yang tidak mengandung crossing, oleh karena itu untuk memeriksa kefisibelan suatu assignment tinggal diperiksa panjang assignment-nya saja. Selanjutnya, agar tidak
o
L1
L2
L3
1
6
11
2
7
12
3
8
13
4
9
14
5
10
15
t
Gambar 16. Graf G yang terbentuk dari assignment yang tidak mengandung crossing pada rel pelangsiran 1 dan 2 dengan notasi i = 1,2 ,...,15 untuk masing-masing simpul-antara.
34
L1
L2
L3
1
3
5
o
t 2
4
6
Gambar 17. Graf G yang terbentuk dari assignment yang tidak mengandung crossing pada rel pelangsiran 3 dengan notasi i = 1, 2,..., 6 untuk masing-masing simpul-antara. Misalkan didefinisikan Pi sebagai himpunan path fisibel (o,…,i) di G. Selain itu didefinisikan pula l (i,..., j ) sebagai
§
Untuk simpul i = 2 Suksesor simpul 2 adalah 3 dan 4 Untuk path (o,2) Untuk sisi berarah (2,3) - l(2,3) = 7 gerbong - b2 = o - l(o,2,3) = 7 gerbong ≤ 15 gerbong - Path (o,2,3) membentuk assignment fisibel Untuk sisi berarah (2,4) - l(2,4) = 0 gerbong - b2 = o - l(o,2,4) = 0 gerbong ≤ 15 gerbong - Path (o,2,4) membentuk assignment fisibel
§
Untuk simpul i = 3 Suksesor simpul 3 adalah 6 Untuk path (o,1,3) Untuk sisi berarah (3,6) - l(3,6) = 4 gerbong - b3 = 1 - l(o,1,3,6) = 15 gerbong ≤ 15 gerbong - Path (o,1,3,6) membentuk assignment fisibel Untuk path (o,2,3) Untuk sisi berarah (3,6) - l(3,6) = 4 gerbong - b3 = 1 - l(o,2,3,6) = 11 gerbong ≤ 15 gerbong - Path (o,2,3,6) membentuk assignment fisibel
§
Untuk simpul i = 4 Suksesor simpul 4 adalah 5 dan 6 Untuk path (o,1,4) Untuk sisi berarah (4,5) - l(4,5) = 4 gerbong - b4 = 1 - l(o,1,4,5) = 8 gerbong ≤ 15 gerbong
panjang dari path ( i,..., j) dengan i adalah simpul pertama dan j adalah simpul terakhir dalam suatu path di graf G, serta b j sebagai predesesor dari simpul j pada graf G. Dengan menggunakan Gambar 16 dan 17, berikut prosedur pemeriksaan kefisibelan dan kedominanan setiap assignment di graf G untuk rel pelangsiran 1, 2 (lihat Lampiran 4), dan rel pelangsiran 3 menggunakan algoritme pemrograman dinamik: §
Rel pelangsiran 3 (memuat paling banyak 15 gerbong kereta) § Untuk simpul i = o Suksesor simpul o adalah 1 dan 2 Untuk path (o,o) Untuk sisi berarah (o,1) - l(o,1) = 4 gerbong ≤ 15 gerbong -Path (o,1) membentuk assignment fisibel Untuk sisi berarah (o,2) - l(o,2) = 0 gerbong ≤ 15 gerbong -Path (o,2) membentuk assignment fisibel §
Untuk simpul i = 1 Suksesor simpul 1 adalah 3 dan 4 Untuk path (o,1) Untuk sisi berarah (1,3) - l(1,3) = 7 gerbong - b1 = o - l(o,1,3) = 11 gerbong ≤ 15 gerbong - Path (o,1,3) membentuk assignment fisibel Untuk sisi berarah (1,4) - l(1,4) = 0 gerbong - b1 = o - l(o,1,4) = 4 gerbong ≤ 15 gerbong - Path (o,1,4) membentuk assignment fisibel
35
- Path (o,1,4,5) membentuk assignment fisibel Untuk sisi berarah (4,6) - l(4,6) = 4 gerbong - b4 = 1 - l(o,1,4,6) = 4 gerbong ≤ 15 gerbong - Path (o,1,4,6) membentuk assignment fisibel Untuk path (o,2,4) Untuk sisi berarah (4,5) - l(4,5) = 4 gerbong - b4 = 2 - l(o,2,4,5) = 4 gerbong ≤ 15 gerbong - Path (o,2,4,5) membentuk assignment fisibel Untuk sisi berarah (4,6) - l(4,6) = 0 gerbong - b4 = 2 - l(o,2,4,6) = 0 gerbong ≤ 15 gerbong - Path (o,2,4,6) membentuk assignment fisibel §
Untuk simpul i = 5 Suksesor simpul 5 adalah t Untuk path (o,1,4,5) Untuk sisi berarah (5,t) - l(5,t) = 0 gerbong - b5 = 4 - l(o,1,4,5,t) = 8 gerbong ≤ 15 gerbong - Path (o,1,4,5,t) membentuk assignment fisibel ( x 32 fisibel) = 91 Untuk path (o,2,4,5) Untuk sisi berarah (5,t) - l(5,t) = 0 gerbong - b5 = 4 - l(o,2,4,5,t) = 4 gerbong ≤ 15 gerbong - Path (o,2,4,5,t) membentuk assignment fisibel ( x53 fisibel)
c 32
Dari algoritme pemrograman dinamik diperoleh himpunan assignment yang fisibel, serta diperoleh pula himpunan assignment yang memiliki panjang sama namun mendominasi assignment lainnya dalam hal ‘biaya’ pada rel pelangsiran 1, 2, dan 3. Tabel 4 adalah daftar assignment yang
§
- c 53 = 132 Untuk simpul i = 6 Suksesor simpul 6 adalah t Untuk path (o,1,3,6,t) Untuk sisi berarah (6,t) - l(6,t) = 0 gerbong - b6 = 3 - l(o, 1,3,6,t) = 11 gerbong ≤ 15 gerbong - Path (o,1,3,6,t) membentuk assignment fisibel ( x13 fisibel) - c13 = 89 Untuk path (o,2,3,6,t) Untuk sisi berarah (6,t) - l(6,t) = 0 gerbong - b6 = 3 - l(o, 2,3,6,t) = 7 gerbong ≤ 15 gerbong - Path (o,2,3,6,t) membentuk assignment fisibel ( x 34 fisibel) - c 43 = 130 Untuk path (o,1,4,6,t) Untuk sisi berarah (6,t) - l(6,t) = 0 gerbong - b6 = 4 - l(o, 1,4,6,t) = 4 gerbong ≤ 15 gerbong - Path (o,1,4,6,t) membentuk assignment fisibel ( x33 fisibel) - c 33 = 134 ≥ c53 ( x33 didominasi oleh x53 ) Untuk path (o,2,4,6,t) Untuk sisi berarah (6,t) - l(6,t) = 0 gerbong - b6 = 4 - l(o, 2,4,6,t) = 0 gerbong ≤ 15 gerbong - Path (o,2,4,6,t) membentuk assignment fisibel ( x 36 fisibel) - c 63 = 175
fisibel yang diperoleh dengan menggunakan algoritme pemrograman dinamik. Assignment yang dicetak tebal adalah assignment dengan panjang sama yang didominasi assignment lainnya dalam hal ‘biaya’.
36
Tabel 4. Daftar assignment fisibel yang diperoleh dengan menggunakan algoritme pemrograman dinamik Assignment k pada Assignment k pada Blok-blok Biaya Biaya Blok-blok rel pelangsiran s rel pelangsiran s penyusun s penyusun ( ck ) ( c ks ) ( x ks ) ( x ks )
x17
LL, not, LL
102
2 x20
x81 x 19 1 x10 1 x11 1 x18 1 x19 x120 x121 x122 x129 x130 x131 x132 x133 x140 1 x 41 x142 x143 x144 x147 1 x 50 1 x 53 1 x 56 1 x 57 1 x 58 x159 x 160 x161 x32 x62 x72 x82 x 92
LR, not, RL
102
LL, not, LR
103
LR, not, RR
109
LL, not, RL
103
LR, not, not
139
LL, not, RR
108
RL, LL, not
95
LL, not, not
140
RL, RR, not
107
LR, not, LL
106
RL, not, LL
97
LR, not, LR
107
RL, not, LR
102
LR, not, RL
107
RL, not, RL
102
LR, not, RR
112
RL, not, RR
109
LR, not, not
144
RL, not, not
139
RL, not, LL
106
RR, LL, not
100
RL, not, LR
107
RR, RR, not
112
RL, not, RL
107
RR, not, LL
102
RL, not, RR
112
2 x21 2 x22 2 x25 2 x28 2 x29 2 x30 2 x31 2 x32 2 x33 2 x36 2 x39 2 x40 2 x 41 2 x42 2 x43 2 x44 2 x45 2 x46 2 x47 2 x48 2 x 49 2 x 50 2 x 51 2 x 52 2 x 53 2 x 54 2 x 55 2 x 56 2 x 57 2 x58 2 x 59 2 x 60 2 x 61
RR, not, LR
107
RR, not, RL
107
RR, not, RR
114
RR, not, not
144
not, LL, RL
99
not, LL, RR
106
not, LL, not
136
not, LR, LL
99
not, LR, LR
111
not, LR, not
141
not, RL, RL
104
not, RL, RR
111
not, RL, not
141
not, RR, LL
106
not, RR, LR
111
not, RR, not
148
not, not, LL
138
not, not, LR
143
not, not, RL
143
not, not, RR
150
not, not, not
180
RL, not, not
144
RR, not, LL
113
RR, not, LR
114
RR, not, RL
114
RR, not, RR
119
RR, not, not
151
not, LL, not
145
not, LR, not
146
not, RL, not
146
not, RR, not
151
not, not, LL
147
not, not, LR
148
not, not, RL
148
not, not, RR
153
not, not, not
185
LL, LL, not
92
LL, RR, not
104
LL, not, LL
94
LL, not, LR
99
LL, not, RL
99
37
2 x10 2 x11 2 x14 2 x17 2 x18 2 x19
LL, not, RR
106
x13
LL, LL, not
89
LL, not, not
136
LL, not, LL
91
LR, LL, not
95
LL, not, not
134
LR, RR, not
107
not, LL, not
130
LR, not, LL
97
not, not, LL
132
LR, not, LR
102
x32 x33 x34 x 53 x 63
not, not, not
175
Untuk menentukan solusi dari masalah penetapan blok pada suatu rel pelangsiran ini, terlebih dahulu didefinisikan:
dengan K s adalah himpunan assignment fisibel k pada rel pelangsiran s dan S = {1,2,3} .
1, jika suatu assignment k ∈ Ks digunakan pada rel pelangsiran s ∈S
1, jika blok b ∈ B tidak diparkir pada rel pelangsiran s ∈ S
xks =
yb =
0, selainnya
0, selainnya
dengan B = {1, 2, 3} dan S = {1,2,3} . TAP yang terbentuk adalah sebagai berikut: Minimumkan: 1 2 2 102 x 17 + 140 x11 + 145 x 147 + 185 x 161 + 92 x32 + 94 x72 + 136 x11 + 136 x 247 + 180 x61 + 89 x13 + 91 x23 + 130 x 34 +
132 x 53 + 175 x63 + 50 ( y1 + y2 + y 3 ) terhadap 1 2 x17 + x11 + x32 + x 72 + x11 + x13 + x23 + y1 = 1
(53)
x147 + x 32 + x 247 + x13 + x43 + y 2 = 1 x17 + x72 + x32 + x53 + y 3 = 1 1 x 17 + x11 + x 147 + x 161 ≤ 1 2 2 2 x 32 + x 72 + x 11 + x 47 + x 61 ≤1 3 3 3 3 3 x1 + x 2 + x3 + x 4 + x 5 + x 36 ≤ 1
(54) (55) (56) (57) (58)
x ks = 0 atau 1, k ∈ K s , s ∈ S = {1, 2,3} , K s adalah himpunan assignment fisibel k pada rel pelangsiran s. yb = 0 atau 1, b ∈ B = {1, 2,3} Kendala (53) menyatakan bahwa blok 1 hanya boleh dimuat pada tepat satu assignment pada suatu rel pelangsiran atau blok 1 tidak diparkir pada rel pelangsiran manapun. Kendala (54) dan (55) secara berturut-turut menyatakan hal yang sama untuk blok 2 dan 3. Kendala (56) menyatakan bahwa rel pelangsiran 1 hanya boleh ditempati oleh paling banyak satu assignment. Kendala (57) dan (58) secara berturut-turut menyatakan hal yang sama untuk rel pelangsiran 2 dan 3.
Masalah induk pada masalah TAP ini diperoleh dengan mengganti batasan x ks = 0 atau 1 dengan batasan
x ks ≥ 0 , untuk
k ∈ K s dan s ∈ S = {1, 2,3} , serta mengganti
yb = 0 dengan batasan yb ≥ 0 , untuk b ∈ B = {1, 2,3} . batasan
3
Inisialisasi Misalkan dipilih variabel untuk RP0 1 2 adalah x11 , x47 , x 32 . Dengan demikian RP0 yang terbentuk adalah sebagai berikut:
38
RP0 : 1 2 Minimumkan 140 x11 + 136 x 47 + 91 x23 + 50 ( y1 + y 2 + y 3 ) 1 terhadap x11 + x23 + y1 = 1 2 x47 + y2 = 1
x23 + y3 = 1 1 x11 ≤1 2 x 47 ≤1
x 32 ≤ 1 1 2 x11 , x 47 , x23 , y1 , y2 , y3 ≥ 0
Dengan menggunakan LINDO 6.1, masalah RP0 di atas akan menghasilkan solusi berikut: 1 2 x 32 = y 2 = 1 , x11 = x 47 = y1 = y 3 = 0 Dari hasil LINDO 6.1 juga dapat diketahui variabel dual untuk masing-masing kendala sebagai berikut : λ1 = 41, λ 2 = 50, λ 3 = 50, µ1 = µ 2 = µ 3 = 0 (lihat Lampiran 5).
3.a Mencari Biaya tereduksi dari Masing-masing Assignment Fisibel k pada Rel Pelangsiran s Seperti yang telah dijelaskan sebelumnya, himpunan assignment yang didominasi tidak diperhitungkan dalam proses pembangkitan kolom, sehingga tidak perlu dicari biaya tereduksinya. Berdasarkan nilai-nilai variabel dual pada RP0 , maka biaya tereduksi dari assignment fisibel k pada rel pelangsiran s dapat dihitung dengan menggunakan (25) yang dapat dilihat pada Tabel 5 berikut:
Tabel 5. Biaya tereduksi dari assignment fisibel k pada rel pelangsiran s untuk RP0 Biaya Biaya Assignment k pada rel Assignment k pada rel Biaya Biaya tereduksi tereduksi pelangsiran s pelangsiran s ( c ks ) ( c ks ) ( x ks ) ( x ks ) ( c ks ) ( c ks )
x17 x 147 x 161 x 72
11
2 x 61
180
180
145
95
89
-2
185
185
132
82
94
3
x13 x 53 x 36
175
175
102
Dari Tabel 5 terlihat bahwa assignment fisibel dan memiliki biaya tereduksi yang paling negatif adalah assignment 1 pada rel pelangsiran 3 yang berpadanan dengan
variabel x13 . Variabel ini ditambahkan pada RP0 sehingga membentuk RP1 seperti berikut:
RP1 : 1 2 Minimumkan 140 x11 + 136 x 47 + 89 x13 + 91x 23 + 50 ( y1 + y 2 + y 3 ) 1 terhadap x11 + x13 + x23 + y1 = 1 2 x47 + x13 + y2 = 1
x23 + y3 = 1 1 x11 ≤1 2 x 47 ≤1
x13 + x 23 ≤ 1 1 2 x11 , x47 , x13 , x23 , y1, y2 , y3 ≥ 0
39
Dengan menggunakan LINDO 6.1, masalah RP1 di atas akan menghasilkan solusi berikut: 1 2 x13 = y3 = 1 , x11 , x 47 , x13 , x 23 , y1, y 2 = 0 Dari hasil LINDO 6.1 juga dapat diketahui variabel dual untuk masing-masing kendala sebagai berikut:
λ1 = 41, λ 2 = 48, λ3 = 50, µ1 = µ 2 = µ 3 = 0 (lihat Lampiran 5). Berdasarkan nilai-nilai variabel dual pada RP1 , maka biaya tereduksi dari assignment fisibel k pada rel pelangsiran s dapat dihitung dengan menggunakan (25) yang dapat dilihat pada Tabel 6 berikut:
Tabel 6. Biaya tereduksi dari assignment fisibel k pada rel pelangsiran s untuk RP1 Biaya Biaya Assignment k pada Assignment k pada Biaya Biaya Tereduksi Tereduksi rel pelangsiran s rel pelangsiran s ( c ks ) ( c ks ) s ( x ks ) ( x ks ) ( ck ) ( c ks )
x17 x 147 x 161 x 72
11
2 x 61
180
180
145
97
132
82
185
185
x 53 x 36
175
175
94
3
102
Dari Tabel 6 tidak ada lagi kolom atau variabel yang memiliki biaya tereduksi negatif, hal ini berarti solusi pada RP1 merupakan solusi optimal pada masalah induk. Dalam contoh kasus ini, blok yang dapat diparkir agar biaya pelangsiran minimum adalah Kereta 3628 dan Kereta 561 di rel pelangsiran 2 yang datang dan berangkat melalui sisi kiri serta dengan tidak memarkir Kereta 3678 pada rel pelangsiran. Dari contoh kasus di atas, proses pemarkiran kereta api yang meminimumkan biaya adalah sebagai berikut: 1. Kereta 3628 yang tiba di peron kedatangan 5A pada Senin pukul 11:09 akan memasuki rel pelangsiran 2 melalui sisi kiri. 2. Kemudian Kereta 561 yang tiba di peron kedatangan 3B pada Senin pukul 21:02 akan memasuki rel pelangsiran 2 melalui sisi kiri pula.
3.
Kereta 3678 yang tiba di peron kedatangan 5B pada Senin pukul 23:43 tidak diparkir di rel pelangsiran. 4. Kereta 520 harus berangkat pada Selasa pukul 07:18, oleh karenanya kereta ini yang pertama kali meninggalkan rel pelangsiran 2 melalui sisi kiri menuju peron keberangkatan 1A. 5. Kereta 3628 akan dipasangkan dengan Kereta 3678 membentuk Kereta 3629 yang akan berangkat pada Selasa pukul 07:49. Oleh karena itu, Kereta 3628 meninggalkan rel pelangsiran 2 melalui sisi kiri menuju peron keberangkatan 5A, kemudian disusul dengan Kereta 3678 yang berangkat dari peron kedatangan 5B ke peron keberangkatan 5A. Biaya yang diperlukan dalam proses pelangsiran ini adalah sebesar 139.
VI SIMPULAN DAN SARAN 6.1 Simpulan Pelangsiran adalah suatu proses dari pendataan, pemarkiran, dan pemeliharaan unit kereta api beserta proses lain yang berhubungan yang harus dilakukan oleh Perusahaan Kereta Api agar kereta api dapat beroperasi dengan baik dalam mengangkut penumpang. Model matematika dari pendataan kereta-api-datang menjadi kereta-apiberangkat dan pemarkiran unit-unit keretaapi-datang pada masalah pelangsiran
memiliki variabel yang banyak, salah satu cara penyelesaiannya adalah dengan menggunakan teknik pembangkitan kolom, Teknik pembangkitan kolom adalah penyelesaian masalah dengan hanya menggunakan sebagian variabel dari masalah keseluruhan sehingga diperoleh solusi dari masalah awal. Dalam tulisan ini, terlihat bahwa teknik pembangkitan kolom menghasilkan himpunan unit-unit keretaapi-datang yang akan diparkir di rel pelangsiran dengan biaya minimum.
40
Pada contoh kasus terdapat 3 keretaapi-datang yang akan ditetapkan menjadi kereta-api-berangkat dan diparkir di 3 rel pelangsiran, dengan 2 rel jalur-bebas dan 1 rel jalur-satu-arah. Pada contoh ini diperoleh proses pelangsiran yang meminimumkan biaya, yaitu Kereta-api-datang 3628 dan 561 secara berturut-turut akan ditetapkan menjadi Kereta-api-berangkat 3629 dan 520 kemudian diparkir di rel pelangsiran 2 yang datang dan berangkat lewat sisi kiri rel, sedangkan Kereta-api-datang 3678 akan ditetapkan menjadi Kereta-api-berangkat
3629 dan tidak diparkir di rel pelangsiran manapun. 6.2 Saran Pada tulisan ini telah dibahas mengenai penetapan blok pada rel pelangsiran dengan menggunakan teknik pembangkitan kolom. Assignment fisibel yang terbentuk dari blokblok ini sangat banyak dan membutuhkan waktu serta ketelitian yang tinggi dalam pemeriksaannya, oleh karena itu alangkah lebih baik jika pencarian assignment fisibel tersebut menggunakan program komputasi.
DAFTAR PUSTAKA Barnhart, C., E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh & P.H. Vance. 1998. Branch and price: column generation for solving huge integer programs. Operations Research 46: 316-329. Foulds, L.R. 1992. Graph Theory Applications. Springer-Verlag, New York. Freling, R., R.M. Lentink, L.G. Kroon & D. Huisman. 2002. Shunting of passenger train units in a railway station. Econometric Institute Report E12002-26. http://www2.eur.nl/WebDOC/doc/econ ometrie/feweco20020917130601.pdf. [13 Juli 2005] Freling, R., R.M. Lentink & M.A. Oduk. 2000. Scheduling train crews: a case study for the dutch railways. http://www2.eur.nl/WebDOC/doc/econ ometrie/feweco20000510163950.pdf. [11 Januari 2006] Garfinkel, R.S & G.L. Nemhauser. 1972. Integer Programming. John Wiley & Sons, New York.
Hillier, F.S. & G.J. Lieberman. 1990. Introduction to Mathematical Programming. McGraw-Hill, New York. Lavoie, S., M. Minoux & E. Odier. 1988. A new approach for crew pairing problems by column generation with an application to air transportation. European Journal of Operational Research 35: 45-58. Lentink, R.M., P.J. Fioole, L.G. Kroon & C.V. Woudt. 2003. Applying operations research techniques to planning of train shunting. https://ep.eur.nl/bitstream/1765/1100/1/ ERS+2003+094+LIS+.pdf. [11 Januari 2006] Nash, S.G. & A. Sofer. 1996. Linear and Nonlinear Programming. McGraw-Hill, New York. Williams, H.P. 1985. Model Building in Mathematical Programming 2 nd ed. Universities Pr, Northen Ireland. Winston, W.L. 1995. Introduction to Mathematical Programming 2 nd ed. Duxbury, New York.
41
Lampiran 1 Contoh Penyelesaian Suatu PL dengan Algoritme Simpleks Dari PL pada − 2 bahwa A = − 1 1
Contoh 2, dapat diketahui 1 1 0 0 4 2 0 1 0 , b = 11 , 5 0 0 0 1
dan c T = (− 2 − 3 0 0 0) .
Iterasi 1 Misalkan dipilih sebagai basis adalah
x B = ( x3
c TB
x4
x5 )T dan x N = (x1
x 2 )T ,
B = I = B −1 , = (0 0 0) , c TN = (− 2 − 3) , dan
− 2 1 N = −1 2 . 1 0 −1 ˆ Nilai dari x B = b = B b = (4 11 5)T . Dengan basis ini nilai pengali simpleks y T = c TB B −1 = (0 0 0) dan nilai biaya tereduksinya adalah cˆ TN = c TN − y T N = (− 2 − 3) . Keduanya bernilai negatif, jadi basis ini belum optimal. Nilai cˆ TN 2 , yaitu nilai elemen baris
( )
kedua dari cˆ TN , memiliki nilai negatif yang lebih besar, maka pilih x2 (variabel nonbasis kedua) sebagai variabel-masuk. Untuk uji nisbah, hitung 1 ˆA = B −1 A = 2 , 2 2 0 maka perbandingannya adalah : 4 11 bˆ1 / aˆ1,2 = dan bˆ 2 / aˆ 2, 2 = . 1 2 Perbandingan pertama bernilai lebih kecil, maka x3 (variabel basis pertama) merupakan variabel yang akan meninggalkan basis. Iterasi 2 Pada iterasi ini, x2 menggantikan x3 dalam basis. Jadi
x B = (x 2
x4
x 5 )T dan x N = (x1
x 3 )T ,
1 0 0 1 0 0 −1 B = 2 1 0 , B = − 2 1 0 , 0 0 1 0 0 1
c TB = (− 3 0 0) , c TN = (− 2 0 ) , dan − 2 N = −1 1 Sehingga dapat dihitung x = bˆ = B −1b = (4 B T
1 0 . 0 3 5)T
y = c TB B −1 = (− 3 0 0)
cˆ TN = c TN − y T N = (− 8 3) Biaya tereduksi pertama benilai negatif, maka basis ini belum optimal, dan x1 (variabel nonbasis pertama) sebagai variabel-masuk. Kolom yang berpadanan dengan variabel-masuk adalah − 2 ˆA = B −1A = 3 . 1 1 1 Dari uji nisbah minimum, yaitu hasil dari min bˆ2 / aˆ 2,1 = 1, bˆ3 / aˆ 3,1 = 5 , variabel
{
}
x4 yang merupakan variabel basis kedua akan menjadi variabel-keluar. Iterasi 3 Pada iterasi ini, x1 menggantikan x4 dalam basis. Jadi
x B = ( x2
x1
x 5 )T dan x N = (x 4
1 − 2 0 B = 2 − 1 0 , B −1 = 0 1 1
1 − 3 − 2 3 2 3
2 3 1 3 1 3
−
x3 )T , 0 0 1
c TB = (− 3 − 2 0 ) , c TN = (0 0) , dan 0 N = 1 0 Sehingga dapat dihitung x B = bˆ = B −1b = (6 7 y T = c TB B −1 = 3
1 0 . 0 1 4)T −
8 3
0
7 8 cˆ TN = c TN − y T N = − 3 3 Biaya tereduksi kedua benilai negatif, maka basis ini belum optimal, dan x3 (variabel nonbasis kedua) sebagai variabelmasuk. Kolom yang berpadanan dengan variabel-masuk adalah
42
ˆ = B −1 A = A 3 3
c TB = (− 3 − 2 0) , c TN = (0 0) , dan
1 − 3 − 2 . 3 2 3
Calon untuk uji nisbah minimum hanya 15 satu, yaitu bˆ / aˆ = , maka x5 sebagai 3
3 ,1
2
0 N = 1 0 Sehingga dapat dihitung x B = bˆ = B −1b = (8
Iterasi 4 Pada iterasi ini, x3 menggantikan x5 dalam basis. Jadi
x1
x 3 )T dan x N = (x 4
1 0 1 − 2 1 2 B = 2 − 1 0 , B −1 = 0 0 0 1 0 1 − 1 2
5 6)T
3 y T = c TB B −1 = 0 − 2
variabel-keluar.
x B = ( x2
0 0 . 1
x5 )T ,
1 2 1 3 2
7 − 2
3 7 cˆ TN = c TN − y T N = 2 2 Nilai biaya terduksi dengan menggunakan basis ini bernilai positif. Hal ini berarti basis telah optimal. Jadi solusi optimalnya adalah x1 = 5, x2 = 8, x3 = 6 , x 4 = x 5 = 0 , dengan nilai fungsi objektif optimal z = −34 .
Lampiran 2 Hasil Penghitungan Contoh 3 dengan Menggunakan LINDO 6.1 §
Hasil Penghitungan Masalah Primal MIN 5X1 + 7X2 + 9X3 + 7X4 + 5X5 SUBJECT TO X1 + X2 >= 1 X1 + X3 + X4 >= 1 X2 + X3 + X4 >= 1 X1 + X5 >= 1 X2 + X3 >= 1 X3 + X4 + X5 >= 1 X4 >= 1 END LP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1) 19.00000 VARIABLE X1 X2 X3 X4 X5
VALUE REDUCED COST 1.000000 0.000000 1.000000 0.000000 0.000000 2.000000 1.000000 0.000000 0.000000 0.000000
ROW SLACK OR SURPLUS 2) 1.000000 3) 1.000000 4) 1.000000 5) 0.000000 6) 0.000000 7) 0.000000 8) 0.000000 NO. ITERATIONS= 7
DUAL PRICES 0.000000 0.000000 0.000000 -5.000000 -7.000000 0.000000 -7.000000
43
§
Hasil Penghitungan Masalah Dual MAX Y1 + Y2 + Y3 + Y4 + Y5 + Y6 + Y7 SUBJECT TO Y1 + Y2 + Y4 <= 5 Y1 + Y3 + Y5 <= 7 Y2 + Y3 + Y5 + Y6 <= 9 Y2 + Y3 + Y6 + Y7 <= 7 Y4 + Y6 <= 5 END LP OPTIMUM FOUND AT STEP 3 OBJECTIVE FUNCTION VALUE 1) 19.00000 VARIABLE VALUE Y1 0.000000 Y2 0.000000 Y3 0.000000 Y4 5.000000 Y5 7.000000 Y6 0.000000 Y7 7.000000
REDUCED COST 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 1.000000 4) 2.000000 0.000000 5) 0.000000 1.000000 6) 0.000000 1.000000 NO. ITERATIONS= 3
Lampiran 3 Hasil Penghitungan Masalah Pemadanan Kereta-api-datang Menjadi Kereta-api-berangkat dengan Menggunakan LINDO 6.1 MIN 50 U1 + 50 U2 + 50 U3 + 50 U4 + 50 U5 + 50 U6 +10.27 Z315 + 10.27 Z416 + 7.1 Z59 + 7.1 Z610 + 7.1 Z712 SUBJECT TO U1 = 1 U2 + U4 = 1 U5 + U7 = 1 U3 - U2 = 0 U6 - U5 = 0 V8 + V11 + V13 = 1 V14 + V16 = 1 V9 + V12 - V8 = 0 V10 - V9 - V11 = 0 V15 - V14 = 0 Z18 - U1 = 0 Z214 - U2 = 0 Z315 - U3 = 0 LP OPTIMUM FOUND AT STEP 0 OBJECTIVE FUNCTION VALUE 1) 188.0400
+ 50 U7 + 20.67 Z18 + 10.27 Z214
Z416 - U4 = 0 Z59 - U5 = 0 Z610 - U6 = 0 Z712 - U7 = 0 Z18 - V8 = 0 Z214 - V14 = 0 Z315 - V15 = 0 Z416 - V16 = 0 Z59 - V9 = 0 Z610 - V10 = 0 Z712 - V12 = 0 END
44
VARIABLE U1 U2 U3 U4 U5 U6 U7 Z18 Z214 Z315 Z416 Z59 Z610 Z712 V8 V11 V13 V14 V16 V9 V12 V10 V15
VALUE 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000
REDUCED COST 0.000000 60.270000 0.000000 0.000000 57.099998 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -70.669998 3) 0.000000 -60.270000 4) 0.000000 -57.099998 5) 0.000000 -60.270000 6) 0.000000 -57.099998 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 0.000000 0.000000 10) 0.000000 0.000000 11) 0.000000 0.000000 12) 0.000000 -20.670000 13) 0.000000 -10.270000 14) 0.000000 -10.270000 15) 0.000000 -10.270000 16) 0.000000 -7.100000 17) 0.000000 -7.100000 18) 0.000000 -7.100000 19) 0.000000 0.000000 20) 0.000000 0.000000 21) 0.000000 0.000000 22) 0.000000 0.000000 23) 0.000000 0.000000 24) 0.000000 0.000000 25) 0.000000 0.000000 NO. ITERATIONS=0
Lampiran
4
0
Prosedur Pemeriksaan Kefisibelan dan Kedominanan Assignment di graf G dengan Menggunakan Algoritme Pemrograman Dinamik
45
§
- l(o,1,10) = 4 gerbong ≤ 8 gerbong - Path (o,1,10) akan membentuk assignment fisibel
Rel pelangsiran 1 (memuat paling banyak 8 gerbong kereta) § Untuk simpul i = o Suksesor simpul o adalah 1, 2, 3, 4, dan 5 Untuk path (o,o) Untuk sisi berarah (o,1) - l(o,1) = 4 gerbong ≤ 8 gerbong - Path (o,1) akan membentuk assignment fisibel Untuk sisi berarah (o,2) - l(o,2) = 4 gerbong ≤ 8 gerbong - Path (o,2) akan membentuk assignment fisibel Untuk sisi berarah (o,3) - l(o,3) = 4 gerbong ≤ 8 gerbong - Path (o,3) akan membentuk assignment fisibel Untuk sisi berarah (o,4) - l(o,4) = 4 gerbong ≤ 8 gerbong - Path (o,4) akan membentuk assignment fisibel Untuk sisi berarah (o,5) - l(o,5) = 0 gerbong ≤ 8 gerbong - Path (o,5) akan membentuk assignment fisibel §
Untuk simpul i = 1 Suksesor simpul 1 adalah 6, 9, dan 10 Untuk path (o,1) Untuk sisi berarah (1,6) - l(1,6) = 7 gerbong - b1 = o - l(o,1,6) = 11 gerbong > 8 gerbong - Path (o,1,6) akan membentuk assignment yang takfisibel ( x11, x12 dan x13 takfisibel) Untuk sisi berarah (1,9) - l(1,9) = 7 gerbong - b1 = o - l(o,1,9) = 11 gerbong > 8 gerbong - Path (o,1,9) akan membentuk assignment yang takfisibel ( x 14 , x15 dan x16 takfisibel) Untuk sisi berarah (1,10) - l(1,10) = 0 gerbong - b1 = o
§
Untuk simpul i = 2 Suksesor simpul 2 adalah 6, 9, dan 10 Untuk path (o,2) Untuk sisi berarah (2,6) - l(2,6) = 7 gerbong - b2 = o - l(o,2,6) = 11 gerbong > 8 gerbong - Path (o,2,6) akan membentuk assignment yang takfisibel 1 1 ( x12 , x13 dan x114 takfisibel) Untuk sisi berarah (2,9) - l(2,9) = 7 gerbong - b2 = o - l(o,2,9) = 11 gerbong > 8 gerbong - Path (o,2,9) akan membentuk assignment yang takfisibel 1 1 ( x15 , x16 dan x117 takfisibel) Untuk sisi berarah (2,10) - l(2,10) = 0 gerbong - b2 = o - l(o,2,10) = 4 gerbong ≤ 8 gerbong Path (o,2,10) akan membentuk assignment fisibel
§
Untuk simpul i = 3 Suksesor simpul 3 adalah 6, 9, dan 10 Untuk path (o,3) Untuk sisi berarah (3,6) - l(3,6) = 7 gerbong - b3 = o - l(o,3,6) = 11 gerbong > 8 gerbong - Path (o,3,6) akan membentuk assignment yang takfisibel ( x 123 , x124 dan x125 takfisibel) Untuk sisi berarah (3,9) - l(3,9) = 7 gerbong - b3 = o - l(o,3,9) = 11 gerbong > 8 gerbong - Path (o,3,9) akan membentuk assignment yang takfisibel ( x 126 , x 127 dan x128 takfisibel) Untuk sisi berarah (3,10)
46
- l(o,5,8) = 7 gerbong ≤ 8 gerbong - Path (o,5,8) akan membentuk assignment fisibel Untuk sisi berarah (5,9) - l(5,9) = 7 gerbong - b5 = o - l(o,5,9) = 7 gerbong ≤ 8 gerbong - Path (o,5,9) akan membentuk assignment fisibel Untuk sisi berarah (5,10) - l(5,10) = 0 gerbong - b5 = o - l(o,5,10) = 0 gerbong ≤ 8 gerbong - Path (o,5,10) akan membentuk assignment fisibel
- l(3,10) = 0 gerbong - b3 = o - l(o,3,10) = 4 gerbong ≤ 8 gerbong - Path (o,3,10) akan membentuk assignment fisibel §
§
Untuk simpul i = 4 Suksesor simpul 4 adalah 6, 9, dan 10 Untuk path (o,4) Untuk sisi berarah (4,6) - l(4,6) = 7 gerbong - b4 = o - l(o,4,6) = 11 gerbong > 8 gerbong - Path (o,4,6) akan membentuk assignment yang takfisibel ( x 134 , x135 dan x136 takfisibel) Untuk sisi berarah (4,9) - l(4,9) = 7 gerbong - b4 = o - l(o,4,9) = 11 gerbong > 8 gerbong - Path (o,4,9) akan membentuk assignment yang takfisibel ( x 137 , x138 dan x139 takfisibel) Untuk sisi berarah (4,10) - l(4,10) = 0 gerbong - b4 = o - l(o,4,10) = 4 gerbong ≤ 8 gerbong - Path (o,4,10) akan membentuk assignment fisibel Untuk simpul i = 5 Suksesor simpul 5 adalah 6, 7, 8, 9, dan 10 Untuk path (o,5) Untuk sisi berarah (5,6) - l(5,6) = 7 gerbong - b5 = o - l(o,5,6) = 7 gerbong ≤ 8 gerbong - Path (o,5,6) akan membentuk assignment fisibel Untuk sisi berarah (5,7) - l(5,7) = 7 gerbong - b5 = o - l(o,5,7) = 7 gerbong ≤ 8 gerbong - Path (o,5,7) akan membentuk assignment fisibel Untuk sisi berarah (5,8) - l(5,8) = 7 gerbong - b5 = o
§
Untuk simpul i = 6 Suksesor simpul 6 adalah 13, 14 dan 15 Untuk path (o,5,6) Untuk sisi berarah (6,13) - l(6,13) = 4 gerbong - b6 = 5 - l(o,5,6,13) = 11 gerbong > 8 gerbong - Path (o,5,6,13) membentuk assignment takfisibel ( x145 takfisibel) Untuk sisi berarah (6,14) - l(6,14) = 4 gerbong - b6 = 5 - l(o,5,6,14) = 11 gerbong > 8 gerbong - Path (o,5,6,14) membentuk assignment takfisibel ( x 146 takfisibel) Untuk sisi berarah (6,15) - l(6,15) = 0 gerbong - b6 = 5 - l(o,5,6,15) = 7 gerbong ≤ 8 gerbong - Path (o,5,6,15) membentuk assignment fisibel
§
Untuk simpul i = 7 Suksesor simpul 7 adalah 11, 12 dan 15 Untuk path (o,5,7) Untuk sisi berarah (7,11) - l(7,11) = 4 gerbong - b7 = 5 - l(o,5,7,11) = 11 gerbong > 8 gerbong
47
- Path (o,5,7,11) membentuk assignment takfisibel ( x148 takfisibel) Untuk sisi berarah (7,12) - l(7,12) = 4 gerbong - b7= 5 - l(o,5,7,12) = 11 gerbong > 8 gerbong - Path (o,5,7,12) membentuk assignment takfisibel ( x 149 takfisibel) Untuk sisi berarah (7,15) - l(7,15) = 0 gerbong - b7 = 5 - l(o,5,7,15) = 7 gerbong ≤ 8 gerbong - Path (o,5,7,15) membentuk assignment fisibel §
§
Untuk simpul i = 8 Suksesor simpul 8 adalah 13, 14 dan 15 Untuk path (o,5,8) Untuk sisi berarah (8,13) - l(8,13) = 4 gerbong - b8 = 5 - l(o,5,8,13) = 11 gerbong > 8 gerbong - Path (o,5,8,13) membentuk assignment takfisibel ( x151 takfisibel) Untuk sisi berarah (8,14) - l(8,14) = 4 gerbong - b8= 5 - l(o,5,8,14) = 11 gerbong > 8 gerbong - Path (o,5,8,14) membentuk assignment takfisibel ( x152 takfisibel) Untuk sisi berarah (8,15) - l(8,15) = 0 gerbong - b8 = 5 - l(o,5,8,15) = 7 gerbong ≤ 8 gerbong - Path (o,5,8,15) membentuk assignment fisibel Untuk simpul i = 9 Suksesor simpul 9 adalah 11, 12 dan 15 Untuk path (o,5,9) Untuk sisi berarah (9,11) - l(9,11) = 4 gerbong - b9 = 5 - l(o,5,9,11) = 11 gerbong > 8 gerbong
- Path (o,5,9,11) membentuk assignment takfisibel ( x154 takfisibel) Untuk sisi berarah (9,12) - l(9,12) = 4 gerbong - b9 = 5 - l(o,5,9,12) = 11 gerbong > 8 gerbong - Path (o,5,9,12) membentuk assignment takfisibel ( x155 takfisibel) Untuk sisi berarah (9,15) - l(9,15) = 0 gerbong - b9 = 5 - l(o,5,9,15) = 7 gerbong ≤ 8 gerbong - Path (o,5,9,15) membentuk assignment fisibel §
Untuk simpul i = 10 Suksesor simpul 10 adalah 11, 12, 13, 14, dan 15 Untuk path (o,1,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 1 - l(o,1,10,11) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 1 - l(o,1,10,12) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 1 - l(o,1,10,13) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 1 - l(o,1,10,14) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 1 - l(o,1,10,15) = 4 gerbong ≤ 8 gerbong
48
- Path (o,1,10,15) membentuk assignment fisibel Untuk path (o,2,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 2 - l(o,2,10,11) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 2 - l(o,2,10,12) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 2 - l(o,2,10,13) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 2 - l(o,2,10,14) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 2 - l(o,2,10,15) = 4 gerbong ≤ 8 gerbong - Path (o,2,10,15) membentuk assignment fisibel Untuk path (o,3,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 3 - l(o,3,10,11) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 3 - l(o,3,10,12) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 3
- l(o,3,10,13) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 3 - l(o,3,10,14) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 3 - l(o,3,10,15) = 4 gerbong ≤ 8 gerbong - Path (o,1,10,15) membentuk assignment fisibel Untuk path (o,4,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 4 - l(o,4,10,11) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 4 - l(o,4,10,12) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 4 - l(o,4,10,13) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 4 - l(o,4,10,14) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 4 - l(o,4,10,15) = 4 gerbong ≤ 8 gerbong - Path (o,4,10,15) membentuk assignment fisibel Untuk path (o,5,10) Untuk sisi berarah (10,11)
49
- c118 = 106 ≥ c17
- l(10,11) = 4 gerbong - b 10 = 5 - l(o,5,10,11) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,11) membentuk assignment fis ibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 5 - l(o,5,10,12) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 5 - l(o,5,10,13) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 5 - l(o,5,10,14) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 5 - l(o,5,10,15) = 0 gerbong ≤ 8 gerbong - Path (o,5,10,15) membentuk assignment fisibel §
Untuk simpul i = 11 Suksesor simpul 11 adalah t Untuk path (o,1,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,1,10,11,t) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,11,t) membentuk assignment fisibel ( x17 fisibel) - c 17 = 102 Untuk path (o,2,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,2,10,11,t ) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,11,t) membentuk assignment fisibel ( x118 fisibel)
- x118 didominasi oleh x17
Untuk path (o,3,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,3,10,11,t) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,11,t) membentuk assignment fisibel ( x 129 fisibel) - c 129 = 106 ≥ c 17 - x 129 didominasi oleh x17 Untuk path (o,4,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,4,10,11,t) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,11,t) membentuk assignment fisibel ( x 140 fisibel) - c 140 = 113 ≥ c17 - x 140 didominasi oleh x17 Untuk path (o,5,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,5,10,11,t) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,11,t) membentuk assignment fisibel ( x157 fisibel) - c 157 = 147 §
Untuk simpul i = 12 Suksesor simpul 12 adalah t Untuk path (o,1,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,1,10,12,t) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,12,t) membentuk assignment fisibel ( x18 fisibel) - c 18 = 103 ≥ c17
50
- x18 didominasi oleh x17 Untuk path (o,2,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,2,10,12,t ) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,12,t) membentuk assignment fisibel ( x119 fisibel) -
1 c19 x119
= 107 ≥ c 17 didominasi oleh x17
Untuk path (o,3,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,3,10,12,t ) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,12,t) membentuk assignment fisibel ( x130 fis ibel) -
c 130 x130
= 107 ≥ c 17 didominasi oleh x17
Untuk path (o,4,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,4,10,12,t ) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,12,t ) membentuk assignment fisibel ( x141 fisibel) -
c 141 = 114 ≥ c 17 x141 didominasi
oleh x17
Untuk path (o,5,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,5,10,12,t ) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,12,t ) membentuk assignment fisibel ( x158 fisibel) §
c 158 x158
= 148 ≥
c157
didominasi oleh x157
Untuk simpul i = 13 Suksesor simpul 13 adalah t
Untuk path (o,1,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,1,10,13,t ) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,13,t) membentuk assignment fisibel ( x19 fisibel) - c 19 = 103 ≥ c 17 - x19 didominasi oleh x17 Untuk path (o,2,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,2,10,13,t ) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,13,t) membentuk assignment fisibel ( x 120 fisibel) - c 120 = 107 ≥ c 17 - x 120 didominasi oleh x17 Untuk path (o,3,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,3,10,13,t ) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,13,t) membentuk assignment fisibel ( x131 fisibel) - c 131 = 107 ≥ c17 - x131 didominasi oleh x17 Untuk path (o,4,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,4,10,13,t ) = 8 gerbong ≤ 8 gerbong - Path (o,4,10,13,t) membentuk assignment fisibel ( x 142 fisibel) - c 142 = 114 ≥ c 17 - x 142 didominasi oleh x17 Untuk path (o,5,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10
51
- l(o,5,10,13,t) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,13,t) membentuk assignment fisibel ( x159 fisibel)
- Path (o,4,10,14,t) membentuk assignment fisibel ( x143 fisibel) - c 143 = 119 ≥ c17 - x143 didominasi oleh x17
- c 159 = 148 ≥ c157 - x159 didominasi oleh x157 §
Untuk simpul i = 14 Suksesor simpul 14 adalah t Untuk path (o,1,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,1,10,14,t) = 8 gerbong ≤ 8 gerbong - Path (o,1,10,14,t) membentuk assignment fisibel ( x110 fisibel) 1 - c10 = 108 ≥ c17
- x110 didominasi oleh x17 Untuk path (o,2,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,2,10,14,t) = 8 gerbong ≤ 8 gerbong - Path (o,2,10,14,t) membentuk assignment fisibel ( x121 fisibel) - c 121 = 112 ≥ c17 - x121 didominasi oleh x17 Untuk path (o,3,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,3,10,14,t) = 8 gerbong ≤ 8 gerbong - Path (o,3,10,14,t) membentuk assignment fisibel ( x132 fisibel) - c 132 = 112 ≥ c17 - x132 didominasi oleh x17 Untuk path (o,4,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,4,10,14,t) = 8 gerbong ≤ 8 gerbong
Untuk path (o,5,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,5,10,14,t) = 4 gerbong ≤ 8 gerbong - Path (o,5,10,14,t) membentuk assignment fisibel ( x160 fisibel) - c 160 = 153 ≥ c157 - x160 didominasi oleh x157 §
Untuk simpul i = 15 Suksesor simpul 15 adalah t Untuk path (o,1,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,1,10,15,t) = 4 gerbong ≤ 8 gerbong - Path (o,1,10,15,t) membentuk 1 assignment fisibel ( x11 fisibel) 1 - c11 = 140 ≤ c157 1 - x157 didominasi oleh x11
Untuk path (o,2,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,2,10,15,t) = 4 gerbong ≤ 8 gerbong - Path (o,2,10,15,t) membentuk assignment fisibel ( x 122 fisibel) - c122 = 144 ≥ c111 -
1 x122 didominasi oleh x11
Untuk path (o,3,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,3,10,15,t) = 4 gerbong ≤ 8 gerbong - Path (o,3,10,15,t) membentuk assignment fisibel ( x133 fisibel)
52
1 - c133 = 119 ≤ c11
-
- l(15,t) = 0 gerbong - b 15 = 9 - l(o,5,9,15,t) = 7 gerbong ≤ 8 gerbong - Path (o,5,9,15,t) membentuk assignment fisibel ( x156 fisibel)
1 x133 didominasi oleh x11
Untuk path (o,4,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,4,10,15,t) = 4 gerbong ≤ 8 gerbong - Path (o,4,10,15,t) membentuk assignment fisibel ( x 144 fisibel)
- c 156 = 151 ≥ c147 - x156 didominasi oleh x 147 Untuk path (o,5,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,5,10,15,t) = 0 gerbong ≤ 8 gerbong - Path (o,5,10,15,t) membentuk assignment fisibel ( x 161 fisibel)
- c 144 = 151 ≥ c 133 dan c 144 ≥ c122 1
- x 144 didominasi oleh x11 Untuk path (o,5,6,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 6 - l(o,5,6,15,t) = 7 gerbong ≤ 8 gerbong - Path (o,5,6,15,t) membentuk assignment fisibel ( x 147 fisibel) - c 147 = 145 Untuk path (o,5,7,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 7 - l(o,5,7,15,t) = 7 gerbong ≤ 8 gerbong - Path (o,5,7,15,t) membentuk assignment fisibel ( x150 fisibel) - c 150 = 146 ≥ c147 - x150 didominasi oleh x 147 Untuk path (o,5,8,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 8 - l(o,5,8,15,t) = 7 gerbong ≤ 8 gerbong - Path (o,5,8,15,t) membentuk assignment fisibel ( x153 fisibel) - c 153 = 146 ≥ c 147 - x153 didominasi oleh x 147 Untuk path (o,5,9,15,t) Untuk sisi berarah (15,t)
- c 161 = 185 §
Rel pelangsiran 2 (memuat paling banyak 12 gerbong kereta) § Untuk simpul i = o Suksesor simpul o adalah 1, 2, 3, 4, dan 5 Untuk path (o,o) Untuk sisi berarah (o,1) - l(o,1) = 4 gerbong ≤ 12 gerbong - Path (o,1) akan membentuk assignment fisibel Untuk sisi berarah (o,2) - l(o,2) = 4 gerbong ≤ 12 gerbong - Path (o,2) akan membentuk assignment fisibel Untuk sisi berarah (o,3) - l(o,3) = 4 gerbong ≤ 12 gerbong - -Path (o,3) akan membentuk assignment fisibel Untuk sisi berarah (o,4) - l(o,4) = 4 gerbong ≤ 12 gerbong - Path (o,4) akan membentuk assignment fisibel Untuk sisi berarah (o,5) - l(o,5) = 0 gerbong ≤ 12 gerbong - Path (o,5) akan membentuk assignment fisibel §
Untuk simpul i = 1
53
Suksesor simpul 1 adalah 6, 9, dan 10 Untuk path (o,1) Untuk sisi berarah (1,6) - l(1,6) = 7 gerbong - b1 = o - l(o,1,6) = 11 gerbong ≤ 12 gerbong - Path (o,1,6) akan membentuk assignment fisibel Untuk sisi berarah (1,9) - l(1,9) = 7 gerbong - b1 = o - l(o,1,9) = 11 gerbong ≤ 12 gerbong - Path (o,1,9) akan membentuk assignment fisibel Untuk sisi berarah (1,10) - l(1,10) = 0 gerbong - b1 = o - l(o,1,10) = 4 gerbong ≤ 12 gerbong - Path (o,1,10) akan membentuk assignment fisibel §
§
Untuk simpul i = 2 Suksesor simpul 2 adalah 6, 9, dan 10 Untuk path (o,2) Untuk sisi berarah (2,6) - l(2,6) = 7 gerbong - b2 = o - l(o,2,6) = 11 gerbong ≤ 12 gerbong - Path (o,2,6) akan membentuk assignment fisibel Untuk sisi berarah (2,9) - l(2,9) = 7 gerbong - b2 = o - l(o,2,9) = 11 gerbong ≤ 12 gerbong - Path (o,2,9) akan membentuk assignment fisibel Untuk sisi berarah (2,10) - l(2,10) = 0 gerbong - b2 = o - l(o,2,10) = 4 gerbong ≤ 12 gerbong - Path (o,2,10) akan membentuk assignment fisibel Untuk simpul i = 3 Suksesor simpul 3 adalah 6, 9, dan 10 Untuk path (o,3) Untuk sisi berarah (3,6) - l(3,6) = 7 gerbong - b3 = o
- l(o,3,6) = 11 gerbong ≤ 12 gerbong - Path (o,3,6) akan membentuk assignment fisibel Untuk sisi berarah (3,9) - l(3,9) = 7 gerbong - b3 = o - l(o,3,9) = 11 gerbong ≤ 12 gerbong - Path (o,3,9) akan membentuk assignment fisibel Untuk sisi berarah (3,10) - l(3,10) = 0 gerbong - b3 = o - l(o,3,10) = 4 gerbong ≤ 12 gerbong - Path (o,3,10) akan membentuk assignment fisibel §
Untuk simpul i = 4 Suksesor simpul 4 adalah 6, 9, dan 10 Untuk path (o,4) Untuk sisi berarah (4,6) - l(4,6) = 7 gerbong - b4 = o - l(o,4,6) = 11 gerbong ≤ 12 gerbong - Path (o,4,6) akan membentuk assignment fisibel Untuk sisi berarah (4,9) - l(4,9) = 7 gerbong - b4 = o - l(o,4,9) = 11 gerbong ≤ 12 gerbong - Path (o,4,9) akan membentuk assignment fisibel Untuk sisi berarah (4,10) - l(4,10) = 0 gerbong - b4 = o - l(o,4,10) = 4 gerbong ≤ 12 gerbong - Path (o,4,10) akan membentuk assignment fisibel
§
Untuk simpul i = 5 Suksesor simpul 5 adalah 6, 7, 8, 9, dan 10 Untuk path (o,5) Untuk sisi berarah (5,6) - l(5,6) = 7 gerbong - b5 = o - l(o,5,6) = 7 gerbong ≤ 12 gerbong - Path (o,5,6) akan membentuk assignment fisibel Untuk sisi berarah (5,7)
54
§
- l(5,7) = 7 gerbong - b5 = o - l(o,5,7) = 7 gerbong ≤ 12 gerbong - Path (o,5,7) akan membentuk assignment fisibel Untuk sisi berarah (5,8) - l(5,8) = 7 gerbong - b5 = o - l(o,5,8) = 7 gerbong ≤ 12 gerbong - Path (o,5,8) akan membentuk assignment fisibel Untuk sisi berarah (5,9) - l(5,9) = 7 gerbong - b5 = o - l(o,5,9) = 7 gerbong ≤ 2 gerbong - Path (o,5,9) akan membentuk assignment fisibel Untuk sisi berarah (5,10) - l(5,10) = 0 gerbong - b5 = o - l(o,5,10) = 0 gerbong ≤ 12 gerbong - Path (o,5,10) akan membentuk assignment fisibel Untuk simpul i = 6 Suksesor simpul 6 adalah 13, 14 dan 15 Untuk path (o,1,6) Untuk sisi berarah (6,13) - l(6,13) = 4 gerbong - b6 = 1 - l(o,1,6,13) = 15 gerbong > 12 gerbong - Path (o,1,6,13) membentuk assignment yang takfisibel ( x12 takfisibel) Untuk sisi berarah (6,14) - l(6,14) = 4 gerbong - b6 = 1 - l(o,1,6,14) = 15 gerbong > 12 gerbong - Path (o,1,6,14) membentuk assignment takfisibel ( x22 takfisibel) Untuk sisi berarah (6,15) - l(6,15) = 0 gerbong - b6 = 1 - l(o,1,6,15) = 11 gerbong ≤ 12 gerbong - Path (o,1,6,15) membentuk assignment fisibel Untuk path (o,2,6) Untuk sisi berarah (6,13)
- l(6,13) = 4 gerbong - b6 = 2 - l(o,2,6,13) = 15 gerbong > 12 gerbong - Path (o,2,6,13) membentuk assignment takfisibel 2 ( x12 takfisibel) Untuk sisi berarah (6,14) - l(6,14) = 4 gerbong - b6 = 2 - l(o,2,6,14) = 15 gerbong > 12 gerbong - Path (o,2,6,14) membentuk assignment takfisibel 2 ( x13 takfisibel) Untuk sisi berarah (6,15) - l(6,15) = 0 gerbong - b6 = 2 - l(o,2,6,15) = 11 gerbong > 12 gerbong - Path (o,2,6,15) membentuk assignment fisibel Untuk path (o,3,6) Untuk sisi berarah (6,13) - l(6,13) = 4 gerbong - b6 = 3 - l(o,3,6,13) = 15 gerbong > 12 gerbong - Path (o,3,6,13) membentuk assignment takfisibel 2 ( x23 takfisibel) Untuk sisi berarah (6,14) - l(6,14) = 4 gerbong - b6 = 3 - l(o, 3,6,14) = 15 gerbong > 12 gerbong - Path (o,3,6,14) membentuk assignment takfisibel 2 ( x24 takfisibel) Untuk sisi berarah (6,15) - l(6,15) = 0 gerbong - b6 = 3 - l(o,3,6,15) = 11 gerbong ≤ 12 gerbong - Path (o,3,6,15) membentuk assignment fisibel Untuk path (o,4,6) Untuk sisi berarah (6,13) - l(6,13) = 4 gerbong - b6 = 4 - l(o,4,6,13) = 15 gerbong > 12 gerbong - Path (o,4,6,13) membentuk assignment takfisibel
55
2 ( x34 takfisibel) Untuk sisi berarah (6,14) - l(6,14) = 4 gerbong - b6 = 4 - l(o,4,6,14) = 15 gerbong > 12 gerbong - Path (o,4,6,14) membentuk assignment takfisibel 2 ( x35 takfisibel) Untuk sisi berarah (6,15) - l(6,15) = 0 gerbong - b6 = 1 - l(o,1,6,15) = 11 gerbong ≤ 12 gerbong - Path (o,1,6,15) membentuk assignment fisibel
- Path (o,5,7,12) membentuk assignment fisibel Untuk sisi berarah (7,15) - l(7,15) = 0 gerbong - b7 = 5 - l(o,5,7,15) = 7 gerbong ≤ 12 gerbong - Path (o,5,7,15) membentuk assignment fisibel §
Untuk simpul i = 8 Suksesor simpul 8 adalah 13, 14 dan 15 Untuk path (o,5,8) Untuk sisi berarah (8,13) - l(8,13) = 4 gerbong - b8 = 5 - l(o,5,8,13) = 11 gerbong ≤ 12 gerbong - Path (o,5,8,13) membentuk assignment fisibel Untuk sisi berarah (8,14) - l(8,14) = 4 gerbong - b8= 5 - l(o,5,8,14) = 11 gerbong ≤ 12 gerbong - Path (o,5,8,14) membentuk assignment fisibel Untuk sisi berarah (8,15) - l(8,15) = 0 gerbong - b8 = 5 - l(o,5,8,15) = 7 gerbong ≤ 12 gerbong - Path (o,5,8,15) membentuk assignment fisibel
§
Untuk simpul i = 9 Suksesor simpul 9 adalah 11, 12 dan 15 Untuk path (o,5,9) Untuk sisi berarah (9,11) - l(9,11) = 4 gerbong - b9 = 5 - l(o,5,9,11) = 11 gerbong ≤ 12 gerbong - Path (o,5,9,11) membentuk assignment fisibel Untuk sisi berarah (9,12) - l(9,12) = 4 gerbong - b9 = 5 - l(o,5,9,12) = 11 gerbong ≤ 12 gerbong - Path (o,5,9,12) membentuk assignment fisibel Untuk sisi berarah (9,15) - l(9,15) = 0 gerbong - b9 = 5
Untuk path (o,5,6) Untuk sisi berarah (6,13) - l(6,13) = 4 gerbong - b6 = 5 - l(o,5,6,13) = 11 gerbong ≤ 12 gerbong - Path (o,5,6,13) membentuk assignment fisibel Untuk sisi berarah (6,14) - l(6,14) = 4 gerbong - b6 = 5 - l(o,5,6,14) = 11 gerbong ≤ 12 gerbong - Path (o,5,6,14) membentuk assignment fisibel Untuk sisi berarah (6,15) - l(6,15) = 0 gerbong - b6 = 5 - l(o,5,6,15) = 7 gerbong ≤ 12 gerbong - Path (o,5,6,15) membentuk assignment fisibel §
Untuk simpul i = 7 Suksesor simpul 7 adalah 11, 12 dan 15 Untuk path (o,5,7) Untuk sisi berarah (7,11) - l(7,11) = 4 gerbong - b7 = 5 - l(o,5,7,11) = 11 gerbong ≤ 12 gerbong - Path (o,5,7,11) membentuk assignment fisibel Untuk sisi berarah (7,12) - l(7,12) = 4 gerbong - b7= 5 - l(o,5,7,12) = 11 gerbong ≤ 12 gerbong
56
- l(o,5,9,15) = 7 gerbong ≤ 12 gerbong - Path (o,5,9,15) membentuk assignment fisibel §
Untuk simpul i = 10 Suksesor simpul 10 adalah 11, 12, 13, 14, dan 15 Untuk path (o,1,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 1 - l(o,1,10,11) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 1 - l(o,1,10,12) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 1 - l(o,1,10,13) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 1 - l(o,1,10,14) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 1 - l(o,1,10,15) = 4 gerbong ≤ 12 gerbong - Path (o,1,10,15) membentuk assignment fisibel Untuk path (o,2,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 2 - l(o,2,10,11) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 2 - l(o,2,10,12) = 8 gerbong ≤ 12 gerbong
- Path (o,2,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 2 - l(o,2,10,13) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 2 - l(o,2,10,14) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 2 - l(o,2,10,15) = 4 gerbong ≤ 12 gerbong - Path (o,2,10,15) membentuk assignment fisibel Untuk path (o,3,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 3 - l(o,3,10,11) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 3 - l(o,3,10,12) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 3 - l(o,3,10,13) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 3 - l(o,3,10,14) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 3 - l(o,3,10,15) = 4 gerbong ≤ 12 gerbong
57
- l(o,5,10,13) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,13) membentuk assignment fisibel
- Path (o,1,10,15) membentuk assignment fisibel Untuk path (o,4,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 4 - l(o,4,10,11) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 4 - l(o,4,10,12) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 4 - l(o,4,10,13) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,13) membentuk assignment fisibel Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 4 - l(o,4,10,14) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 4 - l(o,4,10,15) = 4 gerbong ≤ 12 gerbong - Path (o,4,10,15) membentuk assignment fisibel Untuk path (o,5,10) Untuk sisi berarah (10,11) - l(10,11) = 4 gerbong - b 10 = 5 - l(o,5,10,11) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,11) membentuk assignment fisibel Untuk sisi berarah (10,12) - l(10,12) = 4 gerbong - b 10 = 5 - l(o,5,10,12) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,12) membentuk assignment fisibel Untuk sisi berarah (10,13) - l(10,13) = 4 gerbong - b 10 = 5
Untuk sisi berarah (10,14) - l(10,14) = 4 gerbong - b 10 = 5 - l(o,5,10,14) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,14) membentuk assignment fisibel Untuk sisi berarah (10,15) - l(10,15) = 0 gerbong - b 10 = 5 - l(o,5,10,15) = 0 gerbong ≤ 12 gerbong - Path (o,5,10,15) membentuk assignment fisibel §
Untuk simpul i = 11 Suksesor simpul 11 adalah t Untuk path (o,1,9,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 9 - l(o,1,9,11,t) = 15 gerbong > 12 gerbong - Path (o,1,9,11,t) membentuk assignment takfisibel ( x42 takfisibel) Untuk path (o,2,9,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 9 - l(o,2,9,11,t) = 15 gerbong > 12 gerbong - Path (o,2,9,11,t) membentuk assignment takfisibel 2 ( x15 takfisibel) Untuk path (o,3,9,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 9 - l(o,3,9,11,t) = 15 gerbong > 12 gerbong - Path (o,3,9,11,t) membentuk assignment takfisibel 2 ( x26 takfisibel) Untuk path (o,4,9,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 9
58
- l(o,4,9,11,t) = 15 gerbong > 12 gerbong - Path (o,4,9,11,t) membentuk assignment takfisibel 2 ( x37 takfisibel)
Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 7 - l(o,5,7,11,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,7,11,t) membentuk assignment fisibel ( x 248 fisibel)
Untuk path (o,1,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,1,10,11,t) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,11,t) membentuk assignment fisibel ( x 72 fisibel)
2 - c48 = 99
Untuk path (o,5,9,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 9 - l(o,5,9,11,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,9,11,t) membentuk 2 assignment fisibel ( x54 fisibel)
- c 72 = 94 Untuk path (o,2,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,2,10,11,t) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,11,t) membentuk assignment fisibel 2 ( x18 fisibel)
2 2 - c54 = 106 ≥ c48 2 2 ( x54 didominasi oleh x48 )
Untuk path (o,5,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,5,10,11,t) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,11,t) membentuk 2 assignment fisibel ( x57 fisibel)
2 - c18 = 97 ≥ c 72 2 ( x18 didominasi oleh x 72 )
Untuk path (o,3,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,3,10,11,t) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,11,t) membentuk assignment fisibel 2 ( x 29 fisibel) 2 - c 29 = 97 ≥ c72 2 ( x 29 didominasi oleh x 72 )
Untuk path (o,4,10,11,t) Untuk sisi berarah (11,t) - l(11,t) = 0 gerbong - b 11 = 10 - l(o,4,10,11,t) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,11,t) membentuk 2 assignment fisibel ( x 40 fisibel) 2 - c 40 = 102 ≥ c 72 2 ( x 40 didominasi oleh x 72 )
Untuk path (o,5,7,11,t)
2 - c 57 = 138
§
Untuk simpul i = 12 Suksesor simpul 12 adalah t Untuk path (o,1,9,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 9 - l(o,1,9,12,t) = 15 gerbong > 12 gerbong - Path (o,1,9,12,t) membentuk assignment takfisibel ( x52 takfisibel) Untuk path (o,2,9,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 9 - l(o,2,9,12,t) = 15 gerbong > 12 gerbong - Path (o,2,9,12,t) membentuk assignment takfisibel 2 ( x16 takfisibel) Untuk path (o,3,9,12,t) Untuk sisi berarah (12,t)
59
- l(12,t) = 0 gerbong - b 12 = 9 - l(o,3,9,12,t) = 15 gerbong > 12 gerbong - Path (o,3,9,12,t) membentuk assignment tak fisibel 2 ( x27 tak fisibel)
- l(12,t) = 0 gerbong - b 12 = 10 - l(o,4,10,12,t) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,12,t) membentuk assignment fisibel ( x 241 fisibel) 2 - c 41 = 107 ≥ c72 2 ( x 41 didominasi oleh x 72 )
Untuk path (o,4,9,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 9 - l(o,4,9,12,t) = 15 gerbong > 12 gerbong - Path (o,4,9,12,t) membentuk assignment takfisibel 2 ( x38 tak fisibel)
Untuk path (o,5,7,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 7 - l(o,5,7,12,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,7,12,t) membentuk 2 assignment fisibel ( x 49 fisibel) 2 2 - c49 = 111 ≥ c48
Untuk path (o,1,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,1,10,12,t) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,12,t) membentuk assignment fisibel ( x 82 fisibel)
2 2 ( x 49 didominasi oleh x48 )
Untuk path (o,5,9,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 9 - l(o,5,9,12,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,9,12,t) membentuk 2 assignment fisibel ( x55 fisibel)
- c 82 = 99 ≥ c72 ( x 82 didominasi oleh x 72 )
2 2 - c55 = 111 ≥ c48
Untuk path (o,2,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,2,10,12,t) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,12,t) membentuk 2 assignment fisibel ( x19 fisibel)
2 2 ( x55 didominasi oleh x48 )
Untuk path (o,5,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,5,10,12,t) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,12,t) membentuk 2 assignment fisibel ( x58 fisibel)
2 - c19 = 102 ≥ c 72 2 ( x19 didominasi oleh x 72 )
Untuk path (o,3,10,12,t) Untuk sisi berarah (12,t) - l(12,t) = 0 gerbong - b 12 = 10 - l(o,3,10,12,t) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,12,t) membentuk 2 assignment fisibel ( x30 fisibel) 2 - c 30 = 102 ≥ c72 2 ( x30 didominasi oleh x 72 )
Untuk path (o,4,10,12,t) Untuk sisi berarah (12,t)
2 2 - c 58 = 143 ≥ c 57 2 2 ( x58 didominasi oleh x57 )
§
Untuk simpul i = 13 Suksesor simpul 13 adalah t Untuk path (o,1,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,1,10,13,t) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,13,t) membentuk assignment fisibel ( x 92 fisibel)
60
- c 92 = 99 ≥ c72
- Path (o,5,8,13,t) membentuk 2 assignment fisibel ( x51 fisibel)
( x 92 didominasi oleh x 72 )
2 2 2 2 - c51 = 104 ≥ c45 dan c51 ≥ c48
Untuk path (o,2,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,2,10,13,t) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,13,t) membentuk 2 assignment fisibel ( x 20 fisibel)
2 2 ( x51 didominasi oleh x45 dan 2 x48 )
Untuk path (o,5,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,5,10,13,t) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,13,t) membentuk 2 assignment fisibel ( x59 fisibel)
2 - c 20 = 102 ≥ c 72 2 ( x 20 didominasi oleh x 72 )
Untuk path (o,3,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,3,10,13,t) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,13,t) membentuk 2 assignment fisibel ( x31 fisibel) 2 - c 31 = 102 ≥ c 72 2 ( x31 didominasi oleh x 72 )
Untuk path (o,4,10,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 10 - l(o,4,10,13,t) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,13,t) membentuk 2 assignment fisibel ( x 42 fisibel) 2 - c 42 = 107 ≥ c 72 2 ( x 42 didominasi oleh x 72 )
Untuk path (o,5,6,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 6 - l(o,5,6,13,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,6,13,t) membentuk assignment fisibel ( x 245 fisibel) 2 - c45 = 99
Untuk path (o,5,8,13,t) Untuk sisi berarah (13,t) - l(13,t) = 0 gerbong - b 13 = 8 - l(o,5,8,13,t) = 11 gerbong ≤ 12 gerbong
2 2 - c 59 = 143 ≥ c57 2 2 ( x59 didominasi oleh x57 )
§
Untuk simpul i = 14 Suksesor simpul 14 adalah t Untuk path (o,1,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,1,10,14,t) = 8 gerbong ≤ 12 gerbong - Path (o,1,10,14,t) membentuk 2 assignment fisibel ( x10 fisibel) 2 - c10 = 106 ≥ c 72 2 ( x10 didominasi oleh x 72 )
Untuk path (o,2,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,2,10,14,t) = 8 gerbong ≤ 12 gerbong - Path (o,2,10,14,t) membentuk assignment fisibel ( x 221 fisibel) 2 - c 21 = 109 ≥ c72
( x 221 didominasi oleh x 72 ) Untuk path (o,3,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,3,10,14,t) = 8 gerbong ≤ 12 gerbong - Path (o,3,10,14,t) membentuk 2 assignment fisibel ( x32 fisibel) 2 - c 32 = 109 ≥ c72
61
2 ( x32 didominasi oleh x 72 )
Untuk path (o,4,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,4,10,14,t) = 8 gerbong ≤ 12 gerbong - Path (o,4,10,14,t) membentuk assignment fisibel ( x 243 fisibel) 2 - c 43 = 114 ≥ c72
( x 243 didominasi oleh x 72 ) Untuk path (o,5,6,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 6 - l(o,5,6,14,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,6,14,t) membentuk 2 assignment fisibel ( x 46 fisibel) 2 2 2 2 - c46 = 106 ≥ c45 dan c46 ≥ c48 2 2 ( x 46 didominasi oleh x45 dan 2 x48 )
Untuk path (o,5,8,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 8 - l(o,5,8,14,t) = 11 gerbong ≤ 12 gerbong - Path (o,5,8,14,t) membentuk 2 assignment fisibel ( x52 fisibel) 2 2 2 - c52 = 111 ≥ c45 dan c52 ≥ c248
-
2 ( x52 didominasi 2 x48 )
oleh
2 x45
dan
Untuk path (o,5,10,14,t) Untuk sisi berarah (14,t) - l(14,t) = 0 gerbong - b 14 = 10 - l(o,5,10,14,t) = 4 gerbong ≤ 12 gerbong - Path (o,5,10,14,t) membentuk assignment fisibel ( x 260 fisibel) -
§
2 2 c 60 = 150 ≥ c57 ( x 260 didominasi
Untuk simpul i = 15
2 oleh x57 )
Suksesor simpul 15 adalah t Untuk path (o,1,6,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 6 - l(o,1,6,15,t) = 11 gerbong ≤ 12 gerbong - Path (o,1,6,15,t) membentuk assignment fisibel ( x 32 fisibel) 2 2 - c32 = 92 ≤ c45 dan c32 ≤ c48 2 2 ( x45 dan x48 didominasi oleh
x32 ) Untuk path (o,1,9,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 9 - l(o,1,9,15,t) = 11gerbong ≤ 12 gerbong - Path (o,1,9,15,t) membentuk assignment fisibel ( x 62 fisibel) - c 62 = 104 ≥ c 32 ( x 62 didominasi oleh x 32 ) Untuk path (o,1,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,1,10,15,t) = 4 gerbong ≤ 12 gerbong - Path (o,1,10,15,t) membentuk 2 assignment fisibel ( x11 fisibel) 2 2 - c11 = 136 ≤ c57 2 2 ( x57 didominasi oleh x11 )
Untuk path (o,2,6,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 6 - l(o,2,6,15,t) = 11 gerbong ≤ 12 gerbong - Path (o,2,6,15,t) membentuk 2 assignment fisibel ( x14 fisibel) 2 - c14 = 95 ≥ c32 2 ( x14 didominasi oleh x 32 )
Untuk path (o,2,9,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 9 - l(o,2,9,15,t) = 11 gerbong ≤ 12 gerbong
62
- Path (o,2,9,15,t) membentuk 2 assignment fisibel ( x17 fisibel) 2 - c17 = 107 ≥ c32 2 ( x17 didominasi oleh x 32 )
Untuk path (o,2,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,2,10,15,t) = 4 gerbong ≤ 12 gerbong - Path (o,2,10,15,t) membentuk 2 assignment fisibel ( x 22 fisibel) -
2 c22 = 139 ≥ c112
2 2 ( x 22 didominasi oleh x11 )
Untuk path (o,3,6,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 6 - l(o,3,6,15,t) = 11 gerbong ≤ 12 gerbong - Path (o,3,6,15,t) membentuk assignment fisibel ( x 225 fisibel) 2 - c 25 = 95 ≥ c 32
( x 225 didominasi oleh x 32 ) Untuk path (o,3,9,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 9 - l(o,3,9,15,t) = 11 gerbong ≤ 12 gerbong - Path (o,3,9,15,t) membentuk assignment fisibel ( x 228 fisibel) 2 - c 28 = 107 ≥ c 32
( x 228 didominasi oleh x 32 ) Untuk path (o,3,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,3,10,15,t) = 4 gerbong ≤ 12 gerbong - Path (o,3,10,15,t) membentuk 2 assignment fis ibel ( x33 fisibel) -
2 c33 = 139 ≥ c112
2 2 ( x33 didominasi oleh x11 )
Untuk path (o,4,6,15,t) Untuk sisi berarah (15,t)
- l(15,t) = 0 gerbong - b 15 = 6 - l(o,4,6,15,t) = 11 gerbong ≤ 12 gerbong - Path (o,4,6,15,t) membentuk 2 assignment fisibel ( x36 fisibel) 2 - c 36 = 100 ≥ c32 2 ( x36 didominasi oleh x 32 )
Untuk path (o,4,9,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 9 - l(o,4,9,15,t) = 11 gerbong ≤ 12 gerbong - Path (o,4,9,15,t) membentuk 2 assignment fisibel ( x39 fisibel) 2 - c 39 = 112 ≥ c32 2 ( x39 didominasi oleh x 32 )
Untuk path (o,4,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,4,10,15,t) = 4 gerbong ≤ 12 gerbong - Path (o,4,10,15,t) membentuk 2 assignment fisibel ( x 44 fisibel) -
2 c44 = 144 ≥ c112
2 2 ( x 44 didominasi oleh x11 )
Untuk path (o,5,6,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 6 - l(o,5,6,15,t) = 7 gerbong ≤ 12 gerbong - Path (o,5,6,15,t) membentuk assignment fisibel 2 ( x 47 fisibel) 2 - c 47 = 136
Untuk path (o,5,7,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 7 - l(o,5,7,15,t) = 7 gerbong ≤ 12 gerbong - Path (o,5,7,15,t) membentuk assignment fisibel 2 ( x50 fisibel) 2 - c 50 = 141 ≥ c 247
63
2 ( x50 didominasi oleh x 147 ) Untuk path (o,5,8,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 8 - l(o,5,8,15,t) = 7 gerbong ≤ 12 gerbong - Path (o,5,8,15,t) membentuk assignment fisibel 2 ( x53 fisibel) 2 2 - c 53 = 141 ≥ c47 2 2 ( x53 didominasi oleh x 47 )
Untuk path (o,5,9,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 9
- l(o,5,9,15,t) = 7 gerbong ≤ 12 gerbong - Path (o,5,9,15,t) membentuk assignment fisibel 2 ( x56 fisibel) 2 2 - c 56 = 148 ≥ c47 2 2 ( x56 didominasi oleh x 47 )
Untuk path (o,5,10,15,t) Untuk sisi berarah (15,t) - l(15,t) = 0 gerbong - b 15 = 10 - l(o,5,10,15,t) = 0 gerbong ≤ 12 gerbong - Path (o,5,10,15,t) membentuk assignment fisibel ( x 261 fisibel) 2 - c 61 = 180
Lampiran 5 Hasil Penghitungan RP0 dan RP1 dengan Menggunakan LINDO 6.1 §
RP0
MIN 140 X11,1 + 136 X47,2 + 91 X2,3 + 50 Y1 + 50 Y2 + 50 Y3 SUBJECT TO X11,1 + X2,3 + Y1 = 1 X47,2 + Y2 = 1 X2,3 + Y3 = 1 X1,1 <= 1 X47,2 <= 1 X2,3 <= 1 END LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 141.0000 VARIABLE VALUE REDUCED COST X11,1 0.000000 99.000000 X47,2 0.000000 86.000000 X2,3 1.000000 0.000000 Y1 0.000000 9.000000 Y2 1.000000 0.000000 Y3 0.000000 0.000000 X1,1 0.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -41.000000 3) 0.000000 -50.000000 4) 0.000000 -50.000000 5) 1.000000 0.000000 6) 1.000000 0.000000 7) 0.000000 0.000000 NO. ITERATIONS= 1
64
§ RP1 MIN 140 X11,1 + 136 X47,2 + 89 X1,3 + 91 X2,3 + 50 Y1 + 50 Y2 + 50 Y3 SUBJECT TO X11,1 + X1,3 + X2,3 + Y1 = 1 X47,2 + X1,3 + Y2 = 1 X2,3 + Y3 = 1 X1,1 <= 1 X47,2 <= 1 X1,3 + X2,3 <= 1 END LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 139.0000 VARIABLE VALUE REDUCED COST X11,1 0.000000 99.000000 X47,2 0.000000 88.000000 X1,3 1.000000 0.000000 X2,3 0.000000 0.000000 Y1 0.000000 9.000000 Y2 0.000000 2.000000 Y3 1.000000 0.000000 X1,1 0.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -41.000000 3) 0.000000 -48.000000 4) 0.000000 -50.000000 5) 1.000000 0.000000 6) 1.000000 0.000000 7) 0.000000 0.000000 NO. ITERATIONS= 2
