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
