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.
