I PENDAHULUAN 1.1 Latar Belakang Masalah penentuan rute bus karyawan mendapat perhatian dari para peneliti selama lebih kurang 30 tahun belakangan ini. Masalah optimisasi rute bus karyawan secara matematis termasuk dalam kelas permasalahan yang disebut Vehicle Routing Problem (VRP). Bentuk dasar VRP berkaitan dengan masalah penentuan suatu himpunan rute kendaraan (vehicle) yang melayani suatu himpunan pelanggan. Dalam kehidupan sehari-hari banyak ditemukan terapan VRP, antara lain pendistribusian barang hasil produksi oleh produsen ke konsumen, pengambilan surat dari kotak-kotak pos yang tersebar di seluruh kota, pengantaran dan penjemputan anak sekolah dengan bus sekolah. Karakteristik khusus yang diperhatikan dalam masalah bus karyawan di antaranya, bus tidak kembali ke pos yang sudah
dilewatinya setelah melengkapi rute perjalanannya tetapi bus mengakhiri perjalanannya di depot, serta banyaknya karyawan pada setiap bus tidak melebihi kapasitas bus. Tulisan ini akan membahas bagaimana mengoptimalkan biaya yang berhubungan dengan pengangkutan karyawan dengan menggunakan PLI (pemrograman linear integer) sedemikian sehingga kendalakendalanya dipenuhi. Model penentuan rute bus karyawan pada karya ilmiah ini berdasarkan pada artikel berjudul “Solving school bus routing problems through integer programming” yang ditulis oleh T Bektas dan Seda Elmastas tahun 2007. 1.2 Tujuan Tujuan penulisan ini adalah memodelkan dan menyelesaikan masalah penentuan rute bus karyawan dengan PLI.
II LANDASAN TEORI Untuk membuat model penentuan rute bus karyawan dan teknik-teknik pemecahan yang digunakan dalam karya tulis ini, diperlukan pemahaman teori pemrograman linear (PL), Pemrograman Linear Integer (PLI) atau Integer Linear Programming (ILP), dan metode branch-and-bound.
Sebagai gambaran, f ( x1 , x 2 ) = 2 x1 + x 2 merupakan fungsi linear, sementara 2 f ( x1 , x 2 ) = x1 x 2 bukan fungsi linear.
2.1Fungsi Linear dan Pertidaksamaan Linear Fungsi linear dan pertidaksamaan linear merupakan salah satu konsep dasar yang harus dipahami terkait dengan konsep pemrograman linear.
pertidaksamaan
Definisi 1 (Fungsi Linear) Misalkan f ( x1 , x 2 ,..., x n ) menyatakan suatu fungsi dalam variabel-variabel x1 , x2 ,..., xn . Fungsi f ( x1 , x 2 ,..., x n ) dikatakan linear jika dan hanya jika untuk suatu himpunan konstanta c1 , c 2 ,..., c n , fungsi f dapat dituliskan sebagai f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . (Winston 2004)
2.2 Pemrograman Linear Menurut Winston (2004), pemrograman linear (PL) adalah suatu masalah optimisasi yang memenuhi ketentuan-ketentuan sebagai berikut. a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif.
Definisi 2 (Pertidaksamaan dan Persamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b, dan f ( x1 , x 2 ,..., x n ) ≤ b f ( x1 , x 2 ,..., x n ) ≥ b adalah pertidaksamaan linear; sedangkan f ( x1 , x 2 ,..., x n ) = b merupakan persamaan linear. (Winston 2004)
2
b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel x i , pembatasan tanda menentukan x i harus taknegatif ( xi ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign).
variabel basis dan x N adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan ⎛x ⎞ sebagai Ax = ( B N ) ⎜ B ⎟ ⎝ xN ⎠
Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut.
Definisi 4 (Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004)
Definisi 3 (Bentuk Standar PL) Pemrograman linear min z = cTx terhadap Ax = b x≥0
(2.1)
dikatakan PL dalam bentuk standar, dengan x dan c vektor-vektor berukuran n, vektor b berukuran m, dan A matriks berukuran m × n yang disebut sebagai matriks kendala, dengan m ≤ n. (Nash & Sofer 1996) Sebagai catatan, yang dimaksud dengan vektor berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1. Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimal bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947, dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar. Pada masalah PL (2.1), vektor x yang memenuhi kendala Ax = b disebut solusi PL (2.1). Misalkan matriks A dapat dinyatakan sebagai A = ( B N ) , dengan B adalah
matriks berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n − m) yang elemen-elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (2.1). Misalkan x dapat dinyatakan sebagai ⎛x ⎞ vektor x = ⎜ B ⎟ , dengan xB adalah vektor ⎝ xN ⎠
(2.2) = Bx B + Nx N = b. Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2.2) xB dapat dinyatakan sebagai: xB = B-1b – B-1NxN. (2.3)
Definisi 5 (Solusi Basis) Solusi dari suatu PL disebut solusi basis jika memenuhi syarat berikut: i. solusi tersebut memenuhi kendala pesamaan pada PL, ii. kolom-kolom dari matriks kendala yang berpadanan dengan komponen taknol dari solusi tersebut adalah bebas linear. (Nash & Sofer 1996) Definisi 6 (Solusi Fisibel Basis) Solusi fisibel basis adalah solusi basis pada PL yang semua variabel-variabelnya taknegatif. (Winston 2004) Definisi 7 (Solusi Optimal) Untuk masalah maksimisasi, solusi optimal suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimal suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004)
Ilustrasi solusi basis dan solusi fisibel basis diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan PL (2.4) berikut: min z = −2x1 – 3x2
terhadap
−2x1 + x2 + x3 = 4 −x1 + 2x2 + x4 = 11 x1 + x5 = 5 x1, x2, x3, x4, x5 ≥ 0
Dari PL (2.4) diperoleh:
(2.4)
3
2.4 Relaksasi Pemrograman Linear Konsep relaksasi pemrograman linear atau relaksasi-PL diberikan dalam definisi berikut ini.
⎛ −2 1 1 0 0 ⎞ ⎛4⎞ ⎜ ⎟ ⎜ ⎟ A = ⎜ −1 2 0 1 0 ⎟ , b = ⎜ 11⎟ . ⎜ 1 0 0 0 1⎟ ⎜5⎟ ⎝ ⎠ ⎝ ⎠ Misalkan dipilih
xB = ( x3
x4
x5 ) dan xN = ( x1 T
x2 ) , T
maka matriks basisnya adalah ⎛1 0 0⎞ ⎜ ⎟ B = ⎜0 1 0⎟ . ⎜0 0 1⎟ ⎝ ⎠ Dengan menggunakan matriks basis di atas didapatkan T T x N = ( 0 0 ) , x B = B −1b = ( 4 11 5 ) . (2.5) Solusi (2.5) merupakan solusi basis, karena memenuhi kendala pada PL (2.4) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (2.5), yaitu B , bebas linear. Solusi (2.5) juga merupakan solusi fisibel basis, karena nilainilai variabelnya lebih dari atau sama dengan nol. PL (2.1) dapat dinyatakan dalam bentuk xB dan x N sebagai berikut min z = c TB x B + c TN x N terhadap Bx B + Nx N = b
(2.6)
x ≥ 0, dengan cB vektor koefisien variabel basis pada fungsi objektif dan cN vektor koefisien variabel nonbasis pada fungsi objektif. Jika persamaan (2.3) disubstitusikan ke dalam fungsi objektif PL (2.6) maka akan didapat z = cTB (B−1b − B−1 NxN ) + cTN xN
= cTB B−1b + (cTN − cTB B−1 N)xN .
Definisi 8 (Relaksasi Pemrograman Linear) Pemrograman linear relaksasi atau sering disebut relaksasi-PL merupakan suatu pemrograman linear yang diperoleh dari suatu IP dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Untuk masalah maksimisasi, nilai optimal fungsi objektif relaksasi-PL lebih besar atau sama dengan nilai optimal fungsi objektif IP, sedangkan untuk masalah minimisasi, nilai optimal fungsi objektif relaksasi-PL lebih kecil atau sama dengan nilai optimal fungsi objektif IP. (Winston 1995) 2.5 Graf Konsep graf yang digunakan dalam karya ilmiah ini meliputi definisi-definisi berikut ini. Definisi 9 (Graf) Suatu graf G adalah pasangan terurut (V, E) dengan V himpunan takkosong dan berhingga yang anggota-anggotanya disebut simpul (node/vertex) dan E merupakan himpunan berhingga garis yang menghubungkan simpul-simpul anggota V yang disebut dengan sisi (edge). Sisi yang menghubungkan simpul i dengan simpul j dinyatakan dengan {i, j}. (Foulds 1992) Graf seperti disebutkan pada definisi di atas disebut juga graf tak berarah. Ilustrasi graf tak berarah dapat dilihat pada Gambar 1 berikut: G: 1
(Winston 2004) 2.3 Pemrograman Integer (Integer Programming) pemrograman integer (PI) atau Integer programming (IP) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Garfinkel & Nemhauser 1972)
4 2
5 3
Gambar 1 Graf G = (V, E) Pada Gambar 1 di atas diperlihatkan bahwa V = {1, 2,3, 4,5} dan E = {{1, 2},{1, 3},{1, 4},{2, 3},{3, 4},{3, 5}}. Definisi 10 (Graf Berarah) Dalam suatu graf, jika sisi yang menghubungkan simpul-simpulnya berarah
4
maka graf tersebut dinamakan graf berarah (directed graph/digraph). Sisi yang menghubungkan simpul i dengan simpul j berarah dinyatakan dengan {i, j}. (Foulds 1992)
Definisi 14 (Path Berarah) Path berarah pada graf berarah G’ adalah suatu walk berarah yang semua simpulnya berbeda. (Foulds 1992)
Ilustrasi graf berarah dapat dilihat pada gambar berikut
Ilustrasi walk dan path berarah diberikan sebagai berikut. Pada graf berarah G ' yang terdapat dalam Gambar 2, contoh walk berarah adalah 1,3, 2,1, 4,3,5 , dan contoh
G ' : 1 4 2 5 3
Gambar 2 Graf G ' = (V , A). Pada Gambar 2 diperlihatkan bahwa V = {1, 2,3, 4,5} dan A = {(1, 2), (1, 3), (1, 4), (2,1), (3, 2), (3, 5), (4,3)}. Definisi 11 (Walk) Suatu walk pada graf G = (V, E) adalah suatu barisan simpul dan sisi dari G dengan bentuk: v1 , {v1 , v2 } , v2 , {v2 , v3 } ,..., {vn −1 , vn } , vn ,
path berarah adalah 2,1, 4,3,5 . Definisi 15 (Graf Berbobot) Suatu graf G = (V, E) atau graf berarah G ' = (V , A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau l : A → ℜ (dengan ℜ himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau A. (Foulds 1992) Ilustrasi graf berbobot diberikan dalam Gambar 3. G': 1
vn . (Foulds 1992) Definisi 12 (Path) Path pada suatu graf G adalah suatu walk dengan semua simpulnya berbeda. (Foulds 1992) Ilustrasi walk dan path diberikan sebagai berikut. Pada graf G yang terdapat dalam Gambar 1, salah satu contoh walk adalah 1, 2,3,4,3,5 , sedangkan 1,2,3,5 adalah salah satu contoh path. Definisi 13 (Walk Berarah) Walk berarah pada suatu graf berarah G ' = (V , A) adalah suatu barisan terurut simpul dan sisi pada G ' yang berbentuk v0 , a1 , v1 ,...,an , vn , dengan setiap sisi berarah ai menghubungkan simpul-simpul vi-1 dan vi secara berurutan. (Foulds 1992)
4
0 3
2
atau ditulis dengan ringkas : v1 , v2 ,..., vn atau v1 , v2 ,..., vn . Walk tersebut menghubungkan simpul v1 dengan simpul
2
1
‐2
3
5 0
Gambar 3 Graf berbobot G ' = (V , A). Misalkan diberikan l : A → ℜ untuk graf berbobot G ' = (V , A) pada Gambar 3, maka l((4,3)) = 3 atau dapat pula ditulis
l 4,3 = 3; l 2,1 = 1; l 1,3 = l 3,5 = 0; l 3, 2 = − 2; l 1, 4 = 2. 2.6 Masalah Path Terpendek Masalah penentuan rute perjalanan dengan biaya minimum merupakan aplikasi dari masalah penentuan path terpendek dalam suatu graf berbobot. Didefinisikan panjang untuk sembarang path berarah dalam suatu network sebagai jumlah biaya semua sisi berarah dalam path tersebut. Dalam masalah ini akan dicari suatu path terpendek, yakni path berarah dari suatu simpul asal ke simpul tujuan dengan panjang terkecil. Dalam bab ini, juga dijelaskan tentang traveling salesman problem (TSP) yang merupakan dasar dari vehicle routing problem (VRP), kemudian akan diperlihatkan
5
Konsumen
penggunaan pemrograman linear integer (PLI) untuk mencari solusi dari kasus VRP. 2.7 Traveling Salesman Problem (TSP) Dalam TSP, seorang salesman harus mengunjungi seluruh kota yang ada dan diharuskan kembali ke kota awal pada akhir perjalanannya. Tujuan dari TSP adalah menetukan rute perjalanan yang fisibel sedemikian sehingga jarak tempuh yang melalui rute tersebut minimum.
Rute
Depot
Gambar 4 Contoh rute dalam traveling salesman problem (TSP).
Definisi 16 (m-TSP) m-TSP adalah salah satu variasi dari TSP. Dalam m-TSP terdapat m salesman mengunjungi seluruh kota tetapi setiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Setiap salesman berangkat dari suatu depot dan pada akhir perjalanannya juga harus kembali ke depot tersebut. Tujuan dari m-TSP adalah meminimumkan total jarak dari setiap rute. Masalah m-TSP dikenal juga sebagai vehicle routing problem (VRP). Dalam masalah tersebut, sebuah kota diasosiasikan sebagai konsumen dan tiap kendaraan memiliki kapasitas tertentu. Total jumlah permintaan dalam suatu rute tidak boleh melebihi kapasitas dari kendaraan yang beroperasi. (Larsen 1999) Contoh solusi dari TSP dapat dilihat pada Gambar 4.
+
+ +
Vehicle Routing Problem (VRP) VRP merupakan masalah pendistribusian setiap kendaraan yang terletak di depot untuk memenuhi permintaan para pelanggan yang tersebar di banyak tempat. Masalah utama dari VRP adalah membuat rute yang fisibel dengan biaya yang rendah untuk setiap kendaraan dengan ketentuan bahwa setiap kendaraan memulai dan mengakhiri perjalanan dari depot. Misalkan V’ adalah himpunan pelanggan yang harus dilayani. Fungsi objektif dari sebuah VRP adalah mencari sebanyak m buah rute kendaraan dengan total biaya yang minimum sehingga setiap pelanggan di V’ dikunjungi oleh tepat satu kendaraan. Sebuah rute Ri dikatakan fisibel jika setiap pelanggan dikunjungi tepat satu kali oleh sebuah kendaraan. Gambar berikut mencoba menjelaskan input dari sebuah VRP dan solusi yang mungkin terjadi.
+
+
+
Pelanggan
+ +
+ Depot
+ +
+ +
+ Gambar 5 Input dari sebuah VRP.
6
Rute kendaraan
+
+ +
+
+
+
+ +
+ Depot
+ +
+
+ +
Gambar 6 Solusi yang mungkin dari VRP pada Gambar 5 dengan tiga kendaraan.
Tujuan dari VRP adalah menentukan sejumlah rute untuk melakukan pengiriman pada setiap konsumen, dengan mengikuti beberapa ketentuan antara lain : 1. setiap rute berawal dan berakhir di depot, 2. setiap konsumen dikunjungi tepat satu kali oleh tepat satu kendaraan, 3. jumlah permintaan tiap rute tidak melebihi kapasitas kendaraan, 4. meminimumkan biaya perjalanan, (Cordeau et al. 2002) Definisi 17 (Capacitated Vehicle Routing Problem) Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi dari masalah VRP dengan penambahan kendala kapasitas kendaraan. Setiap kendaraan yang melayani konsumen disyaratkan memiliki batasan kapasitas sehingga banyaknya konsumen yang dilayani oleh setiap kendaraan dalam satu rute bergantung pada kapasitas kendaraan. CVRP bertujuan meminimumkan waktu tempuh rute perjalanan kendaraan dalam mendistribusikan barang dari tempat produksi yang dinamakan dengan depot ke sejumlah konsumen dan memenuhi batasan kapasitas. 2.8 Metode Branch-and-Bound Dalam karya ilmiah ini, untuk memperoleh solusi optimum dari masalah PLI digunakan software LINGO 8.0, yaitu sebuah program yang dirancang untuk menentukan solusi model linear, taklinear, dan optimisasi integer. Software LINGO 8.0 ini menggunakan metode branch-and-bound untuk menyelesaikan masalah PLI.
Prinsip dasar metode branch-and-bound adalah memecah daerah fisibel dari masalah relaksasi-PL dengan membuat subproblemsubproblem. Terdapat dua konsep dasar dalam algoritme branch-and-bound. • Branch (Cabang) Branching (pencabangan) adalah proses membagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi fisibel. • Bound (Batas) Bounding (pembatasan) adalah suatu proses untuk mencari atau menghitung batas atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimum pada subproblem yang mengarah ke solusi. (Taha 1975) Metode branch-and-bound diawali dari menyelesaikan relaksasi-PL dari suatu pemrograman linear integer. Jika semua nilai variabel keputusan solusi optimal sudah berupa integer, maka solusi tersebut merupakan solusi optimal PLI. Jika tidak, dilakukan pencabangan dan penambahan batasan pada relaksasi-PLnya kemudian diselesaikan. Winston (2004) menyebutkan bahwa untuk masalah maksimisasi nilai fungsi objektif optimum untuk PLI ≤ nilai fungsi objektif optimum untuk relaksasi-PL, sehingga nilai fungsi objektif optimum relaksasi-PL merupakan batas atas bagi nilai fungsi objektif optimum untuk masalah PLI. Diungkapkan pula oleh Winston (2004) untuk
7
masalah maksimisasi bahwa nilai fungsi objektif optimal untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimum untuk masalah PLI asalnya. Suatu kandidat solusi diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah PLI, artinya fungsi objektif dan semua variabelnya sudah bernilai integer. Sebelumnya akan dibahas terlebih dulu pengertian subproblem yang terukur. Menurut Winston (2004), suatu subproblem dikatakan terukur (fathomed) jika terdapat situasi sebagai berikut: a. Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimum untuk PLI. b. Subproblem tersebut menghasilkan suatu solusi optimum dengan semua variabelnya bernilai integer. Jika solusi optimum ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimum dan nilai fungsi objektifnya menjadi batas bawah (dalam masalah maksimisasi) dan batas atas (dalam masalah minimisasi) nilai fungsi objektif optimum bagi masalah PLI pada saat itu, bisa jadi subproblem ini menghasilkan solusi optimum untuk masalah PLI. c. Nilai fungsi objektif optimum untuk subproblem tersebut tidak melebihi batas bawah saat itu (untuk masalah maksimisasi), maka subproblem ini dapat dieliminasi. Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch-and-bound. • Langkah 0 Didefinisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) PLI yang optimum. Pada awalnya ditetapkan z = −∞ dan i = 0. • Langkah 1 Subproblem PL(i) dipilih sebagai bagian masalah berikutnya untuk diteliti. Subproblem PL(i) diselesaikan dan diukur dengan kondisi yang sesuai. a) Jika PL(i) terukur, batas bawah z diperbarui jika solusi PLI yang lebih baik ditemukan. Jika tidak, bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah diteliti, maka proses dihentikan. b) Jika PL(i) tidak terukur, proses dilanjutkan ke langkah 2 untuk melakukan pencabangan PL(i).
• Langkah 2 Dipilih salah satu variabel xj dengan nilai optimumnya adalah xj* yang tidak memenuhi batasan integer dalam solusi PL(i). Bidang [xj*] < xj < [xj*] + 1 disingkirkan dengan membuat dua subproblem PL yang berkaitan menjadi dua subproblem yang tidak dapat dipenuhi secara bersamaan, yaitu xj ≤ [xj*] dan xj ≥ [xj*] + 1, dengan [xj*] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan xj*. Jika PL(i) masih tidak terukur, maka kembali ke Langkah 1. (Taha 1996) Untuk memudahkan pemahaman metode branch-and-bound diberikan contoh sebagai berikut. Contoh 3 (Metode Branch-and-Bound) Misalkan diberikan integer programming (IP) berikut: maks z = 5x1 + 4x2 terhadap
x1 + x2 ≤ 5 10x1 + 6x2 ≤ 45
(2.7)
x1, x2 ≥ 0 x1, x2 integer. Solusi optimal relaksasi-PL dari masalah IP (2.7) adalah x1 = 3.75, x2 = 1.25, dan z = 23.75 (yang dapat dilihat di Lampiran 1). Batas atas nilai optimal fungsi objektif masalah ini adalah z = 23.75. Daerah fisibel masalah (2.7) ditunjukkan pada Gambar 7.
Gambar 7 Daerah fisibel untuk relaksasi-PL dari IP (2.7). Keterangan : = solusi optimal relaksasi-PL IP (2.7) = titik-titik fisibel bagi IP (2.7) Langkah berikutnya adalah memartisi daerah fisibel relaksasi-PL menjadi dua bagian berdasarkan variabel yang bernilai
8
pecahan (non-integer). Karena nilai dari kedua variabel yang diperoleh bukan integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalkan dipilih x1 sebagai dasar pencabangan. Jika masalah relaksasi-PL diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: • Subproblem 2: Subproblem 1 ditambah kendala x1 ≥ 4; • Subproblem 3: Subproblem 1 ditambah kendala x1 ≤ 3. Hal ini diilustrasikan secara grafis pada Gambar 8.
Subproblem 2 Subproblem 3
Gambar 8 Daerah fisibel untuk Subproblem 2 dan Subproblem 3 dari IP (2.7). Setiap titik (solusi) fisibel dari IP (2.7) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan Subproblem 3 dikatakan dicabangkan oleh x1. Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih Subproblem 2, kemudian diselesaikan. Solusi optimal untuk Subproblem 2 ini adalah x1 = 4, x2 = 0.83, dan z = 23.33 (lihat Lampiran 1). Karena solusi optimal yang dihasilkan Subproblem 2 bukan solusi integer, maka dipilih pencabangan pada Subproblem 2 atas x2 , sehingga diperoleh dua subproblem lagi, yakni: • Subproblem 4: Subproblem 2 ditambah kendala x2 ≥ 1; • Subproblem 5: Subproblem 2 ditambah kendala x2 ≤ 0. Saat ini subproblem yang belum diselesaikan adalah Subproblem 3, 4, dan 5. Salah satu subproblem dipilih, misalnya
dengan aturan LIFO (Last In First Out). Dengan adanya aturan ini berarti dipilih Subproblem 4 atau Subproblem 5. Karena Subproblem 4 takfisibel (lihat pada Lampiran 1), maka subproblem ini tidak dapat menghasilkan solusi optimal, yang tersisa adalah Subproblem 3 dan Subproblem 5. Karena aturan LIFO, dipilih Subproblem 5, yang kemudian menghasilkan solusi optimal x1 = 4.5, x2 = 0, dan z = 22.5 (lihat pada Lampiran 1). Karena x1 = 4.5 bukan integer, maka dilakukan kembali pencabangan atas x1, sehingga diperoleh: • Subproblem 6: Subproblem 5 ditambah kendala x1 ≥ 5; • Subproblem 7: Subproblem 5 ditambah kendala x1 ≤ 4. Misalkan dipilih Subproblem 6. Ternyata subproblem ini juga takfisibel (lihat pada Lampiran 1), sehingga tidak dapat menghasilkan solusi optimal. Dengan demikian subproblem-subproblem yang belum diselesaikan adalah Subproblem 3 dan Subproblem 7. Karena aturan LIFO, dipilih Subproblem 7. Subproblem ini kemudian menghasilkan solusi optimal x1 = 4, x2 = 0, dan z = 20 (lihat pada Lampiran 1). Dapat dilihat bahwa solusi optimal subproblem ini semuanya berupa integer, sehingga merupakan kandidat solusi untuk IP (2.7). Nilai z pada kandidat solusi ini merupakan batas bawah bagi nilai optimal IP. Penyelesaian Subproblem 3 menghasilkan solusi optimal x1 = 3, x2 = 2, dan z = 23 (lihat pada Lampiran 1). Batas bawah yang ditetapkan dari solusi optimal Subproblem 7 terlalu lemah dan tidak lebih baik dari nilai solusi optimal yang dihasilkan oleh Subproblem 3. Dengan demikian, nilai solusi optimal Subproblem 3, yakni z = 23 menjadi batas bawah yang baru. Semua solusi optimal telah berupa integer dan tidak perlu lagi dilakukan pencabangan, sehingga solusi optimal dari Subproblem 3 merupakan solusi optimal IP (2.7), yakni x1 = 3, x2 = 2, dan z = 23. Pohon pencabangan yang menunjukkan penyelesaian masalah IP (2.7) secara keseluruhan ditunjukkan pada Gambar 9.
9
t=1
Subproblem 1 x1 = 3.75, x2 = 1.25, z = 23.75 Batas atas = 23.75
x1 ≥ 4
t=2
x1 ≤ 3
Subproblem Subproblem2 2 x1 = 4, x2 = 0.83, z = 23.33 x1 = 4, x2 = 0.83, z = 23.33 x2 ≤ 0
x2 ≥ 1 t=3
t =7
Subproblem 4 takfisibel
Subproblem 55 Subproblem x1 = 4.5, x2 = 0, z = 22.5 x1 = 4.5, x2 = 0, z = 22.5 x1 ≥ 5
t=5
Subproblem 3* x1 = 3, x2 = 2, z = 23 Batas bawah = 23 Solusi Optimal
Subproblem 6 takfisibel
t=4
x1 ≤ 4
t=6
Subproblem 7* x1 = 4, x2 = 0, z = 20 Batas bawah = 20 Kandidat Solusi
Gambar 9 Seluruh pencabangan pada metode branch-and-bound untuk menyelesaikan IP (2.7). Pada Gambar 9, solusi Subproblem 3 dan Subproblem 7 adalah kandidat solusi terbaik karena semua variabelnya bernilai integer. Namun, karena nilai z untuk Subproblem 3 lebih besar dari Subproblem 7 maka solusi
dari Subproblem 3 merupakan solusi optimum untuk masalah IP pada Contoh 3. Tanda (*) pada Subproblem 3 dan Subproblem 7 menyatakan kandidat solusi untuk masalah IP tersebut.
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah Rute Bus Karyawan Masalah rute bus karyawan adalah masalah penentuan rute bus untuk menjemput karyawan dari pos-pos yang sudah ditentukan menuju perusahaan dan mengantarkan karyawan dari perusahaan ke pos-pos, kemudian bus tersebut kembali ke tempat asalnya, yaitu perusahaan (depot), dengan biaya yang minimum sehingga kendala kapasitas atau kendala waktu tempuh terpenuhi. Untuk meminimumkan biaya operasional bus, hal yang harus dipertimbangkan adalah biaya perjalanan setiap bus dan biaya tetap untuk mengirimkan bus.
3.2 Model Masalah Rute Bus Karyawan Dalam model ini, rute untuk menjemput karyawan dari pos-pos menuju perusahaan dan rute untuk mengantarkan karyawan dari perusahaan ke pos-pos, diasumsikan sama karena pos-pos penjemputan dan pengantaran karyawan adalah sama. Masalah penentuan rute bus karyawan sangat berhubungan dengan VRP dan graf. Secara matematis VRP dapat dinyatakan sebagai suatu digraf G = (V, A) dengan V = {0, 1, ... , n} adalah himpunan simpul yang menunjukkan pos-pos antar-jemput karyawan dan A={(i, j) | i, j ∈ V, i ≠ j} yaitu himpunan sisi berarah yang menyatakan jalan penghubung antarpos. Pos 0 menunjukkan
