1
PENYELESAIAN MASALAH PENGAMBILAN DAN PENGIRIMAN DENGAN KENDALA WAKTU MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM
Oleh: FAJAR DELLI WIHARTIKO G54102035
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
2
ABSTRAK FAJAR DELLI WIHARTIKO. Penyelesaian Pengambilan dan Pengiriman dengan Kendala Waktu Menggunakan Teknik Pembangkitan Kolom. Dibimbing oleh FARIDA HANUM dan DONNY CITRA LESMANA. Masalah penentuan rute kendaraan merupakan persoalan yang sering dijumpai oleh produsen, pemerintah maupun oleh penyedia jasa pengiriman barang. Salah satu varian dari masalah penentuan rute kendaraan adalah masalah pengambilan dan pengiriman dengan kendala waktu (pick up and delivery problem with time windows/PDPTW). Dalam PDPTW sejumlah rute harus dikonstruksi guna memenuhi semua permintaan transportasi (transportation request/TR). Permintaan transportasi dapat diartikan sebagai suatu permintaan pengiriman barang yang harus dibawa secara langsung dari lokasi pengambilan ke lokasi pengiriman. Setiap permintaan transportasi memiliki kendala waktu dan kendala kapasitas suatu kendaraan. Kendala waktu dalam PDPTW diartikan sebagai selang waktu untuk menunggu pengambilan atau pengiriman di suatu tempat. Rute yang dikonstruksi harus memenuhi syarat kefisibelan. Setelah semua rute fisibel ditemukan, maka harus dicari bagaimana memenuhi semua permintaan transportasi dengan biaya yang minimum. Dalam karya ilmiah ini, pemilihan rute yang memenuhi semua permintaan transportasi dimodelkan sebagai masalah pemartisian himpunan (set partitioning problem/SPP). Penyelesaian masalah pemartisian himpunan dalam skala yang besar dapat menggunakan teknik pembangkitan kolom (column generation). Teknik ini merupakan teknik untuk menyelesaikan suatu pemrograman linear (PL) dengan hanya menggunakan sebagian variabel dari masalah keseluruhan.
3
PENYELESAIAN MASALAH PENGAMBILAN DAN PENGIRIMAN DENGAN KENDALA WAKTU 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: FAJAR DELLI WIHARTIKO G54102035
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
4
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 25 Maret 1984 sebagai anak kedua dari dua bersaudara dari pasangan bapak Hari Harsono dan ibu Sri Wiedarti. Pada tahun 2002 penulis lulus dari SMUN 2 Bogor dan berhasil menjadi mahasiswa Jurusan Matematika (yang sekarang berganti menjadi Departemen Matematika), Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor melalui jalur USMI (Undangan Seleksi Masuk IPB). Selama mengikuti kegiatan perkuliahan, penulis pernah menjadi asisten pada mata kuliah Kalkulus I pada tahun 2003. Penulis juga aktif mengikuti kegiatan Badan Eksekutif Mahasiswa FMIPA pada tahun 2003/2004. Selain itu penulis juga pernah aktif dalam kepengurusan GUMATIKA (Gugus Mahasiswa Matematika) pada periode 2003/2004.
5
PRAKATA Syukur Alhamdulillah kepada Allah SWT, karena dengan rahmat dan kekuasaan-Nya penulis dapat menyelesaikan skripsi dengan judul ”P enyelesaian Masalah P engambilan dan P engiriman dengan Kendala Waktu Menggunakan Teknik Pembangkitan Kolom”. Pada kesempatan ini penulis mengucapkan terimakasih kepada : 1 Ibu Dra. Farida Hanum, M.Si. dan Bapak Donny Citra Lesmana, S.Si. selaku dosen pembimbing yang telah memberikan bimbingan dan arahan sampai penyelesaian skripsi. 2 Bapak Ir. N. K. Kutha Ardana, M.Sc sebagai dosen penguji atas saran dan masukannya. 3 Ayahanda, Ibunda dan kakakku atas dorongan semangat baik moril maupun materiel. 4 Seluruh dosen beserta staf Departemen Matematika atas ilmunya yang tak ternilai. 5 Teman-teman angkatan 39 atas kenangan yang indah selama masa perkuliahan. 6 Seluruh rekan seperjuangan angkatan 35, 36, 37, 38, 40 dan 41. 7 Seluruh pihak yang telah membantu terselesaikannya skripsi ini yang tidak dapat disebutkan satu per satu. Penulis menyadari dalam penyusunan skripsi ini masih jauh dari sempurna. Penulis mengharapkan saran dan kritik yang membangun untuk kesempurnaan skripsi ini. Semoga skripsi ini bermanfaat baik bagi penulis maupun pihak-pihak lain yang memerlukannya. Bogor, Januari 2006 Fajar Delli Wihartiko
6
DAFTAR ISI Halaman DAFTAR TABEL …………...…………………………………………………………….……
7
DAFTAR GAMBAR ………...…………………………………………………………………
7
DAFTAR LAMPIRAN……...………………………………………………….……………...... 7 I
II
PENDAHULUAN Latar Belakang …………………………………………………………………..….... Tujuan …………………………………………………………………………..….....
8 8
LANDASAN TEORI Graf ……………………………………………………………………………….... .. 8 Pemrograman Linear …………………………………………………………….…… 9 Masalah Dual ………………………………………………………………………… 11 Pemrograman Linear Bilangan Bulat ..……………………………………………..... 13 Masalah Pemartisian Himpunan …………………………………………….……...... 13
III DESKRIPSI DAN FORMULASI MASALAH Masalah Pengambilan dan Pengiriman dengan Kendala Waktu …………………….. 15 Formulasi Masalah sebagai Masalah Pemartisian Himpunan ………………………. 19 IV PENYELESAIAN MASALAH Teknik Pembangkitan Kolom ……………………………………………………….. 19 Pricing Problem ……………………….…………………………………………….. 20 V
CONTOH KASUS …………….........................................................................................
21
VI SIMPULAN ……………………………………………………………………………… 29 DAFTAR PUSTAKA ........................................................................................................... .....
30
LAMPIRAN ............................................................................................................................. .. 31
7
DAFTAR TABEL Halaman 1 2 3 4
TR dan kendala waktu …………………………………………………………………… Permintaan transportasi suatu perusahaan ………………………………………………. Contoh kasus masalah PDPTW …………………………………………………………. Hasil setiap iterasi menggunakan teknik pembangkitan kolom ...........................................
15 17 21 29
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8
Graf G = ( V, E) ………………………………………………………………………….. Digraf D = ( V , A ) ………………………………………………………………………. Contoh 8 dalam bentuk graf ……………………………………………………………. Graf dari m tempat ……………………………………………………………………… Graf dari Contoh 10 ……………………………………………………………………… Graf dari Tabel 3 ………………………………………………………………………….. Graf dari V1 ∪ S 1 …………………………………………………………………………... Graf dari V 2 ∪ S 2 ……………………………… …………………………………………
8 9 15 16 18 23 25 27
DAFTAR LAMPIRAN Halaman 1 2 3 4 5 6
Contoh penyelesaian suatu P L dengan menggunakan algoritme simpleks ……………….. 32 Hasil perhitungan Contoh 5 menggunakan LINDO 6.1 …………………………………... 33 Rute Fisibel PDPTW ……………………………………………………………………… 34 RMP0, P 1,0 dan P 2,0 ............................................................................................................... 41 RMP1, P 1,1 dan P 2,1 ……………………………………………………………………….. 45 RMP2, P 1,2 dan P 2,2 ………………………………………………………………………… 45
8
I PENDAHULUAN 1.1 Latar Belakang Pendistribusian suatu barang merupakan persoalan yang sering dijumpai baik oleh pemerintah maupun oleh produsen. Dalam pelaksanaannya sering kali dihadapkan pada berbagai masalah seperti efisiensi biaya, efisiensi waktu ataupun masalah efektifitas kendaraan. Contoh pendistribusian barang adalah pengangkutan sampah oleh Dinas Kebersihan, pendistribusian produk perusahaan kepada agen, pengambilan surat di kotak pos oleh PT Pos Indonesia dan mas ih banyak lagi. Contoh-contoh tersebut termasuk dalam masalah pengambilan dan pengiriman (pick up and delivery problem / PDP). Masalah pengambilan dan pengiriman dengan kendala waktu (pick up and delivery problem with time windows/PDPTW) merupakan pengembangan dari PDP. Kendala waktu dalam PDPTW diartikan sebagai selang waktu untuk menunggu pengambilan atau pengiriman di suatu tempat.
Masalah PDP dan PDPTW telah banyak dibahas dan dipelajari, di antaranya oleh Mitrofic-Minic (1998) yang membahas metode heuristik untuk menyelesaikan masalah PDPTW, Bruggen et al. (1993) membahas PDPTW dengan satu depot, Dumas et al. (1991) membahas penyelesaian PDPTW dengan menggunakan teknik pembangkitan kolom yang dipandang sebagai masalah path terpendek serta M. Sol & M.W.P. Savelsberg (1995) yang membahas PDP secara luas. Tulisan ini merupakan rekonstruksi dari tulisan M. Sol & M.W.P. Savelsberg (1994) yang berjudul “A Branch-and-Price Algorithm for the Pickup and Delivery Problem with Time Windows”. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah mempelajari penyelesaian masalah pengambilan dan pengiriman berkendala waktu dengan menggunakan teknik pembangkitan kolom .
II LANDASAN TEORI Beberapa konsep yang dibutuhkan dalam masalah pengambilan dan pengiriman dengan kendala waktu adalah sebagai berikut: 2.1 Graf Definisi 1 (Graf) Suatu graf adalah pasangan terurut (V,E) dengan V himpunan takkosong dan hingga dan E adalah himpunan pasangan takterurut yang menghubungkan elem en-elemen 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 1 berikut: Contoh 1 v5 v6 v1 G:
v2
v3
v4
Gambar 1 Graf G = (V, E).
Pada Gambar 1, V = {v 1 , v 2 , v 3 , v 4 , v 5 , v 6 } dan E = {{v1 , v 2 },{v1 , v 6 }, {v 2 , v 3 },{v 3 , v 6 },
{v3 , v4 }, {v5 , v6 },{v4 , v5 }}.
Definisi 2 (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 , atau dengan ringkas : v1 , v 2 ,..., v n atau v1 , v2 ,..., vn . Walk tersebut menghubungkan simpul v1 dengan v n . (Foulds, 1992) ditulis
Definisi 3 (Closed Walk, Cycle) Suatu walk v 1 , v 2 ,..., v n pada suatu graf G dikatakan tertutup (closed walk) jika v1 = vn . Suatu walk tertutup yang mengandung setidaknya tiga simpul dan semua simpulnya berbeda disebut cycle. (Foulds, 1992) Berikut ini diberikan ilustrasi dari walk tertutup dan cycle. Salah satu contoh walk
9
tertutup pada graf G dalam Contoh 1 adalah v1 ,v 6 , v1 , v 2 , v1 , sedangkan v1 , v2 , v3 , v6 , v1 adalah salah satu contoh cycle. Definisi 4 (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 elemenelemen di V dan dinotasikan sebagai D = (V , A) . Elemen dari A disebut sisi berarah (arc) dan dituliskan sebagai (i, j ) dengan i , j ∈V . (Foulds, 1992) Contoh berikut merupakan ilustrasi digraf. Contoh 2 D: v1
v6
v1-v2-v3-v6-v1, sedangkan cycle v 1, v 6, v 3,v 2,v 1 pada digraf D bukan merupakan cycle berarah. Definisi 7 (Graf Berbobot) Suatu graf G = (V , E ) atau digraf D = (V , A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau ϑ : A → ℜ (dengan ℜ adalah himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau elemen A. (Foulds, 1992) 2.2 Pemrograman Linear Pemrograman linear adalah kegiatan merencanakan untuk mendapatkan hasil yang optimal. Model pemrograman linear (P L) meliputi pengoptimuman suatu fungsi linear terhadap kendala linear . (Hillier & Lieberman, 1990)
v5 Pada tulisan ini, suatu P L mempunyai bentuk standar seperti yang didefinisikan sebagai berikut:
v2
v3
v4
Gambar 2 Digraf D = (V , A) . Pada Gambar 2, digraf D memiliki V = {v1 ,v2 , v3 , v4 , v5 , v6 } dan
A = {(v1 , v2 ), (v6 , v1 ),(v2 , v3 ), (v3 , v6 ), (v3 , v4 ) (v5 , v 6 ), (v 4 , v 5 )} .
Definisi 5 (Walk berarah) Suatu walk berarah pada digraf D = (V , A) adalah suatu barisan simpul dan sisi dari G dengan bentuk: (v1 − (v1 , v2 ) − v2 − (v2 , v3 ) − ... − (vn −1 ,vn ) − vn ) atau ditulis dengan ringkas: (v1 − v 2 − ... − v n ) atau v1-v 2-…-vn. Walk tersebut menghubungkan simpul v1 dengan v n . (Foulds, 1992) Definisi 6 (Cycle berarah) Suatu walk berarah
(v1 − v 2 − ... − v n )
dengan v1 = v n dan mempunyai setidaknya tiga simpul berbeda disebut sebagai cycle berarah. (Foulds, 1992) Berikut ini diberikan ilustrasi mengenai cycle berarah. Salah satu contoh cycle berarah pada digraf D dalam Contoh 2 adalah cycle
Defi nisi 8 (Bentuk Standar Suatu PL) Suatu pemrograman linear didefinisikan mempunyai bentuk standar: Minimumkan z = cT x Ax = b terhadap (1) x ≥0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga sebagai matriks kendala. (Nash & Sofer, 1996) 2.2.1 Solusi S uatu 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 Pemrograman Linear (1), vektor x yang memenuhi kendala Ax = b disebut sebagai solusi P L (1). Misalkan matriks A dapat dinyatakan sebagai A = (B N), dengan B adalah matriks taksingular berukuran m × m yang merupakan matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa
10
koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk P L. Misalkan x dapat dinyatakan sebagai x vektor x = B , dengan x B adalah vektor xN variabel basis dan xN adalah vektor variabel nonbasis. Maka A x = b dapat dinyatakan sebagai x Ax = (B N ) B xN (2) = ? x B + Nx N = b . Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai: (3) x B = B−1 b − B−1N x N . Definisi 9 (Solusi Basis) Vektor x disebut solusi basis dari suatu pemrograman linear jika x memenuhi kendala dari PL dan kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari x adalah bebas linear. (Nash & Sofer, 1996) Definisi 10 (Solusi Basis Fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x ≥ 0. (4) (Nash & Sofer, 1996) Ilustrasi solusi basis dan solusi basis fisibel dapat dilihat dalam contoh berikut: Contoh 3 Misalkan diberikan pemrograman linear berikut: Minimumkan z = − x1 − 2x 2 terhadap −2 x1 + x 2 + x 3 = 2
− x1 + 2 x2 + x4 = 7
(5)
x1 + x 5 = 3
x1 , x2 , x3 , x4 , x5 ≥ 0 Dari pemrograman linear tersebut didapatkan: 1 0 0 − 2 1 2 A = −1 2 0 1 0 , b = 7 1 3 0 0 0 1 Misalkan dipilih
x B = (x3
x4
x5 )T dan x N = (x1
x2 )T
maka matriks basis
1 0 0 B = 0 1 0 0 0 1 Dengan menggunakan matriks basis tersebut, diperoleh x B = B −1b = (2 7 3)T , x N = (0 0 )T . (6) Solusi (6) merupakan solusi basis, karena solusi tersebut memenuhi kendala pada P L (5) dan kolom-kolom pada matriks kendala yang berkorespondensi dengan komponen taknol dari (6) yaitu B adalah bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (6) juga merupakan solusi basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol._ PL (1) dapat dinyatakan dalam xB dan xN sebagai berikut: Minimumkan z = cBT x B + cN T x N terhadap B x B + Nx N = b x ≥0 dengan c B adalah koefisien variabel basis pada fungsi objektif, c N adalah koefisien variabel nonbasis pada fungsi objektif. Jika P ersamaan (3) disubstitusikan ke fungsi objektif z = cBT x B + c N T x N maka akan didapat:
(
)
z = c B T B − 1b − B − 1Nx N + c N T x N −1
(
)
z = cB B b + c N − c BT B − 1N x N . T
T
( ) z = yT b + (cN T − yT N )x N .
−1 T
Jika didefinisikan y = c B B = B −T c B maka z dapat dinyatakan dalam y: T
(7) Vektor y disebut vektor pengali simpleks (simplex multiplier). Untuk suatu solusi basis, x N = 0 dan
x B = bˆ = B −1b , maka zˆ = c B T B − 1b . Notasi zˆ adalah notasi untuk z optimal. Koefisien cˆ j disebut biaya tereduksi (reduced cost) dari x j dengan
(
cˆ j adalah
)
elemen dari vektor cˆ N T = cN T − cBT B − 1N . Biaya tereduksi adalah penambahan nilai fungsi objektif jika suatu variabel nonbasis dijadikan variabel basis (artinya menjadi solusi taknol) pada suatu pemrograman linear.
11
2.2.2 Penyelesaian Pemrograman Linear dengan Algoritme S impleks Solusi suatu pemrograman linear dapat diketahui optimal atau tidak untuk P L 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 = cN T − yT b . Jika cˆ N T ≥ 0 maka solusi yang diperoleh adalah solusi optimal. Jika cˆ N T < 0 maka variabel xt yang memenuhi cˆt < 0 dipilih sebagai variabelmasuk, yaitu variabel xt yang akan masuk ke dalam basis. • Langkah tertentu (t) Kolom Aˆ t = B −1 At , yaitu kolom koefisien kendala yang berhubungan dengan variabel-masuk ke t dihitung kemudian ditentukan indeks s pada kolom kendala yang berhubungan dengan variabel-masuk yang memenuhi min bˆi bˆs = : a i ,t > 0 . (8) a s, t 1 ≤ i ≤ m a i, t Pemilihan indeks dengan cara tersebut disebut dengan uji nisbah minimum (minimum ratio test). Variabel yang menjadi variabel-keluar (variabel yang akan keluar dari basis, tergantikan oleh variabel -masuk) dan pivot entry adalah variabel yang berhubungan dengan aˆ s ,t . Jika aˆ i ,t ≤ 0 , (1 ≤ i ≤ m) untuk semua i, maka masalah P L disebut masalah takterbatas (unbounded). • Pivot Matriks basis B dan vektor basis x B diperbaharui dan kemudian kembali ke tes keoptimalan. Berikut ini diberikan contoh penggu naan algoritme simpleks: Contoh 4 Misalkan diberikan PL(5) dalam Contoh 3. Dengan menggunakan algoritme simpleks akan diperoleh solusi x1 = 3, x2 = 5, x3 = 3, x4 = x5 = 0 dengan z = - 13 (lihat Lampiran 1). _ 2.3 Masalah Dual Setiap masalah pemrograman linear memiliki padanan, yaitu masalah lain yang disebut pemrograman linear dual. Pemrograman linearnya sendiri disebut
sebagai masalah primal. Misalkan diberikan masalah primal: Minimumkan z = cT x terhadap Ax ≥ b (9) x≥0 Maka masalah dual dari (9) adalah Maksimumkan
w = bT y
AT y ≤ c y≥0 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 adalah 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 dibuktikan dalam teorema dualitas kuat. Akibat dari teorema dualitas lemah digunakan untuk membuktikan teorema dualitas kuat. terhadap
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). Akibat 1 Jika x adalah solusi fisibel untuk masalah primal, y adalah solusi fisibel untuk masalah dual, dan b T y = c T x , maka x dan y adalah solusi optimal berturut-turut untuk masalah primal dan dual. 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.
12
Bukti : Misalkan diasumsikan bahwa masalah primal dalam bentuk standar dan mempunyai solusi x yang merupakan solusi basis fisibel optimal. Misalkan x dapat dinyatakan sebagai x vektor x = B , dengan xB adalah vektor xN variabel basis dan xN adalah vektor variabel nonbasis. Selain itu, seperti telah dijelaskan sebelumnya matriks A dapat dinyatakan sebagai A = (B N ) dan vektor koefisien pada fungsi objektif c dapat dinyatakan c sebagai c = B . Karena B adalah matriks cN taksingular, maka B memiliki invers sehingga
Bukti dari teorema dualitas kuat menghasilkan solusi optimal dual. Misalkan x c x = B , A = (B N ) , dan c = B x N cN maka nilai optimal dari variabel dual diberikan
xB dapat dinyatakan sebagai x B = B − 1b . Dari sebelumnya diketahui pula, jika x optimal maka biaya tereduksinya adalah
Contoh 5 Misalkan diberikan pemrograman linear primal sebagai berikut: Minimumkan z = 51x1 + 27 x2 + 93x3 + 74 x4 + 55 x 5 terhadap x1 + x2 ≥ 1
c TN − c TB B − 1N ≥ 0 atau (*) cTB B − 1N ≤ cTN Misalkan y adalah vektor dari pengali simpleks yang berhubungan dengan solusi basis fisibel, dengan y = B −T c B atau
yT = cTB B − 1 . Akan ditunjukkan bahwa: 1 Nilai dari fungsi objektif masalah primal 2
dan dual adalah sama, yaitu bT y = cT x . y adalah optimal untuk masalah dual.
Bukti: 1 Sebelumnya akan diperiksa dahulu kefisibelan dari y:
y T A = c TB B −1 (B N )
(
= cTB
) (
terlebih
)
cTB B −1 N ≤ cTB cTN dari (*)
= cT
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 = bT y = y T b = cTBB −1b = z. Jadi y adalah fisibel untuk masalah dual dan nilai fungsi objektif solusi optimal dari masalah primal dan dual mempunyai nilai yang sama. 2
Karena b T y = cT x maka y adalah solusi optimal untuk masalah dual (dari Akibat 1)._
oleh vektor pengali simpleks y = B −T c B . Dari bukti teorema dualitas kuat terlihat bahwa kondisi primal optimal
cTN − cTB B − 1N ≥ 0 adalah ekivalen dengan kondisi fisibel dual A T y ≤ c atau c − A T y ≥ 0 . Jadi vektor dari biaya tereduksi cˆ adalah vektor variabel slack dual cˆ = c − AT y.
x1 + x2 + x3 + x4 ≥ 1
x1 + x5 ≥ 1 x2 + x3 ≥ 1 x3 + x 4 + x5 ≥ 1 x4 ≥ 1
xi ≥ 0 , untuk i = {1, 2,3, 4,5} . Masalah dual dari masalah tersebut adalah sebagai berikut: Maksimumkan w = y1 + y 2 + y3 + y4 + y5 + y6 terhadap y1 + y 2 + y3 ≤ 51 y1 + y 2 + y 4 ≤ 27
y2 + y 4 + y 5 ≤ 93 y2 + y5 + y6 ≤ 74 y3 + y5 ≤ 55 y i ≥ 0 , untuk i = {1, 2,3, 4,5,6}. Dengan menggunakan LINDO 6.1, diperoleh solusi dari masalah primal sebagai berikut: x1 = x 2 = x 4 = 1, x 3 = x 5 = 0 dengan nilai fungsi objektifnya z = 152 (lihat Lampiran 2). Nilai pengali simpleks untuk masing-masing kendala adalah sebagai berikut: y1 = y2 = 0, y3 = 51, y 4 = 27 , y5 = 4 , y6 = 70 dengan yi adalah nilai pengali simpleks kendala ke-i.
13
Solusi dari masalah dual tersebut juga dapat dicari dengan menggunakan LINDO 6.1 yang menghasilkan solusi: y1 = y 2 = y 5 = 0 , y 3 = 51 , y 4 = 27 , y 6 = 74 dengan nilai fungsi objektif w = 152 (lihat Lampiran 2). Dari penghitungan tersebut, terlihat bahwa fungsi objektif dar i masalah primal dan dual mempunyai nilai yang sama seperti dinyatakan dalam Teorema 2. _ 2.4 Pemrograman Linear Bilangan Bulat Model pemrograman linear bilangan bulat (Integer Linear Programming/ILP) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa bilangan bulat, maka masalah tersebut disebut ILP-murni. Jika hanya sebagian yang harus bilangan bulat maka disebut ILP-campuran. ILP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 I LP.
Partisi dari I di antaranya adalah
karena untuk himpunan J = {3,5} memenuhi: Υ Pj = I dan j∈ J *
untuk j , k ∈ J * , j ≠ k ⇒ P j ∩ Pk =
Model yang digunakan pada tulisan ini yang berkaitan dengan masalah ILP adalah model masalah pemartisian himpunan. 2.5 Masalah Pemartisian Himpunan Definisi 12 (Partisi) Misalkan diberikan dua himpunan, yaitu I = {1,2,..., m} dan P = {P1 , P2 ,..., Pn } dengan P j adalah suatu himpunan bagian dari I, j ∈ J = {1,2,..., n} . Himpunan Pj , j ∈ J * ⊆ J adalah partisi dari I jika: Υ Pj = I dan j∈ J *
untuk j , k ∈ J * , j ≠ k ⇒ P j ∩ Pk = ø. (Garfinkel & Nemhauser, 1972) Ilustrasi dari suatu partisi dapat dilihat pada Contoh 6 berikut: Contoh 6 Misalkan diberikan himpunan I = {1,2,3,4,5,6} dan kelas-kelas himpunan P1 = {1, 6} , P2 = {3,4} , P3 = {1,4,6}, P4 = {2} ,
P5 = {2,3,5}.
ø. _
Masalah pemartisian himpunan (set partitioning problem/SPP) adalah masalah menentukan partisi dari himpunan I dengan biaya minimum. Untuk mendapatkan partisi tersebut, misalkan didefinisikan variabel 0-1 sebagai berikut: 1, jika Pj termasuk dalam partisi xj = 0, selainnya Bentuk umum SPP: n
Minimumkan Definisi 11 (Pemrograman Linear Relaksasi) PL-relaksasi dari suatu ILP merupakan pemrograman linear yang diperoleh dari ILP tersebut dengan menghilangkan kendala bilangan bulat atau kendala 0-1 pada variabelnya. (Winston, 1995)
{P3 , P4 } ,
*
∑ cjx j j =1
n
terhadap
∑ A( j )x j = 1 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 memiliki kendala berupa persamaan. Sifat 2 Nilai sisi kanan semua kendala adalah 1. Sifat 3 Semua elemen matriks koefisien A(j) adalah 0 atau 1. Contoh 7 (Masalah pemartisian himpunan) Misalkan diberikan himpunan I beserta kelas -kelas P seperti pada Contoh 6. Misalkan diketahui biaya dari masing-masing kelas Pj , yaitu cj , dengan c1 = 15, c2 = 10 , c3 = 19 , c4 = 18, c5 = 17 . 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
14
1, jika elemen ke-j di I merupakan elemen Pj , dengan j = 1,2 ,...,5 A(j) = 0, selainnya Masalah tersebut dapat dimodelkan sebagai SPP berikut: Minimumkan 15 x1 + 10 x 2 + 19 x3 + 18 x4 + 17 x5 terhadap x1 + x 3 = 1 (elemen 1)
x4 + x5 = 1
(elemen 2)
x2 + x5 = 1
(elemen 3)
x2 + x3 = 1 (elemen 4) (elemen 5) x5 = 1 (elemen 6) x1 + x3 = 1 x j = 0 atau 1, untuk j = {1, 2, 3, 4, 5} . Dengan mengunakan LINDO 6.1 diperoleh solusi untuk masalah SPP sebagai berikut: x1 = x2 = x4 = 0, x3 = x5 = 1 , dan nilai fungsi objektif sebesar 36. Jadi partisi dari I = {1, 2,3,4,5,6} dengan biaya minimum adalah P3 = {1,4,6} dan P5 = {2,3,5}.
III DESKRIPSI DAN FORMULASI MASALAH Dalam masalah pengambilan dan pengiriman (PDP) sejumlah rute harus dikonstruksi guna memenuhi semua permintaan transportasi (transportation request/TR). Permintaan transportasi dapat diartikan sebagai suatu permintaan pengiriman barang yang harus dibawa secara langsung dari lokasi pengambilan barang (tempat asal) ke lokasi pengiriman (tempat tujuan). Setiap permintaan transportasi memiliki kuantitas barang yang dibawa oleh suatu kendaraan. Kuantitas barang yang dibawa ke tempat tujuan belum tentu semuanya diturunkan pada tempat tujuan. Bisa jadi hanya sebagian barang yang diturunkan atau bahkan tidak diturunkan sama sekali. Barang yang tidak diturunkan kemudian dikirimkan ke tempat tujuan selanjutnya. Bisa jadi dalam pengiriman tersebut ditambah dengan barang yang diangkut pada tempat penurunan barang. Kuantitas barang dalam permintaan transportasi terkadang tidak selalu diketahui pada masalah pengambilan dan pengiriman. Kuantitas tersebut dapat dicari melalui kuantitas suatu barang yang harus diangkut atau diturunkan pada suatu tempat Armada kendaraan sangat dibutuhkan dalam PDP. Armada kendaraan dapat beroperasi dalam berbagai rute. Suatu armada dapat memiliki berbagai macam tipe kendaraan. Setiap tipe kendaraan memiliki depot dan kapasitas pengangkutan barang. Depot merupakan tempat di mana kendaraan tersebut diberangkatkan dan kembali setelah perjalanan usai. Masalah pengambilan dan pengiriman dengan kendala waktu (pick up and delivery problem with time windows/PDPTW) merupakan pengembangan dari PDP, dengan
kendala waktu diartikan sebagai selang waktu untuk menunggu pengambilan atau pengiriman di suatu tempat. Sebagai ilustrasi pada pengambilan surat oleh PT Pos Indonesia. Misalkan saja waktu pengambilan surat di suatu kotak pos adalah tepat pukul 9.00. Sering kali dalam pelaksanaannya dihadapkan pada berbagai masalah perjalanan, sehingga diperkirakan kendaraan tersebut akan tiba sekitar pukul 8.50 sampai pukul 9.10. Perkiraan waktu tersebut digunakan sebagai kendala waktu pada PDPTW. Dalam masalah pengambilan dan pengiriman dengan kendala waktu, setiap permintaan transportasi memiliki kendala waktu yang ada pada saat pengambilan maupun pengiriman. Hal ini berarti setiap kendaraan harus mengunjungi setiap tempat sesuai dengan kendala waktu yang ada. Di depot, s etiap tipe kendaraan dalam armada juga memiliki kendala waktu, sehingga kendaraan tersebut berangkat dan pulang ke depot sesuai dengan waktu yang tersedia. Jika rute-rute dalam PDPTW yang memenuhi permintaan transportasi telah dikonstruksi, maka harus dicari bagaimana cara memenuhi semua permintaan transportasi tersebut dengan biaya minimum. Beberapa asumsi digunakan dalam model PDPTW ini. Asumsi tersebut adalah: 1 Barang yang diambil dan dikirim merupakan barang yang homogen. 2 Barang tersebut dikirimkan oleh satu kendaraan dari lokasi pengambilan ke lokasi pengiriman tanpa adanya biaya pengangkutan di tengah lokasi. 3 Waktu yang diperlukan untuk bongkar muat barang pada lokasi pengambilan dan lokasi pengiriman dapat dengan mudah
15
digabungkan pada waktu perjalanan, sehingga tid ak akan dibahas secara eksplisit. 3.1 Masalah Pengambilan dan Pengiriman dengan Kendala Waktu Masalah pengambilan dan pengiriman dengan kendala waktu dapat dimodelkan sebagai berikut: Misalkan S adalah himpunan permintaan transportasi. Untuk setiap permintaan transportasi i ∈ S, muatan qi?∈ Ν ∪{0} akan diantarkan dari tempat asal i + ke tempat tujuan i-, dengan Ν adalah himpunan bilangan asli. Misalkan didefinisikan Sˆ + ={i+¦ i ∈ S} sebagai himpunan tempat asal dan Sˆ − = {i − i ∈ S } sebagai himpunan tempat tujuan. Untuk setiap i ∈ S, misalkan kendala waktu pengambilan pada tempat i+ + + dinotasikan sebagai [e i , li ] dan kendala waktu pada saat pengiriman di tempat idinotasikan dengan [ e i-, li-]. Misalkan M adalah himpunan dari tipe kendaraan. Setiap kendaraan dengan tipe k ∈ M, mempunyai kapasitas muatan Q k ∈ Ν, , memiliki depot k + dan dapat digunakan dalam selang waktu [ek+, lk+]. Banyaknya kendaraan bertipe k dinotasikan sebagai m k. Didefinisikan M+={k +¦ k ∈ M} sebagai himpunan dari depot. Misalkan didefinisikan himpunan S +={ i + i ∈ Sˆ + − M + }, himpunan S− =
Contoh 8 berikut merupakan ilustrasi untuk memodelkan PDPTW ke dalam suatu graf. Contoh 8 Suatu perusahaan harus mendistribusikan produknya ke tiga agen penjualan. Misalkan setiap tempat saling berhubungan sehingga membentuk cycle berarah. Misalkan pula hanya ada satu kendaraan dengan muatan maksimum sebesar 70 kg. Kendaraan tersebut beroperasi dari pukul 1.00 selama 4 jam. Kendala waktu di setiap agen diberikan seperti pada Tabel 1. Tabel 1. TR dan kendala waktu TR
qi
(i)
(kg)
Asal
Tujuan
Pengambilan
Pengiriman
a b c d
70
v1 v2 v3 v4
v2 v3 v4 v1
1.00 - 1.10
1.45 - 1.55
2.00 - 2.10
2.45 - 2.55
3.00 - 3.10
3.45 - 3.55
4.00 - 4.10
4.45 - 4.55
30 50 50
Untuk setiap i,j ∈ V, k ∈M didefinisikan: • t ki j sebagai waktu perjalanan yang
•
ditempuh oleh kendaraan tipe k dari tempat i ke tempat j. cik j sebagai biaya perjalanan yang ditempuh oleh kendaraan tipe k dari tempat i ke tempat j.
3.1.1 Pemodelan Masalah Pengambilan dan Pengiriman dengan Kendala Waktu ke dalam Suatu Graf Masalah pengambilan dan pengiriman dapat dimodelkan ke dalam suatu graf berbobot, dengan: • Sisi berarah melambangkan permintaan transportasi dengan bobot melambangkan muatan sebes ar q, dan untuk set iap sisi i ∈ S dilabeli dengan i, q i . • Simpul melambangkan tempat asal dan tempat tujuan.
Batas Waktu
Maka masalah tersebut dapat dimodelkan sebagai berikut:
v1
a,70
v2 b, 30
d,50
v4
{i − i ∈ Sˆ − − M + } dan himpunan V = S+ ∪ S-
∪ M+.
Tempat
c, 50
v3
Gambar 3. Contoh 8 dalam bentuk graf. Dari contoh tersebut, depot perusahaan dilambangkan oleh v1 . Kendaraan beroperasi dari pukul 1.00 sampai pukul 5.00. Himpunan permintaan transportasi adalah S = {a, b, c, d}. Setiap kendaraan yang melewati permintaan transportasi akan membawa barang dari tempat asal ke tempat tujuannya. Sebagai contoh, kendaraan yang melewati permintaan transportasi a (TR a) akan membawa barang sebesar 70 kg dari tempat asal a + (atau v 1 ) ke tempat tujuan a- (atau v2 )._ 3.1.2
Kuantitas Barang di Tempat Pengambilan dan Pengiriman Barang Misalkan didefinisikan Q i ∈ Ζ sebagai kuantitas barang yang ada di tempat i ∈ W= S + ∪ S − , dengan Ζ adalah himpunan bilangan bulat dan W adalah himpunan seluruh
16
tempat pengambilan dan pengiriman tanpa adanya suatu depot. Terdapat tiga kasus untuk kuantitas barang Q i. • Jika Qi < 0, maka barang sebanyak Q i. harus diangkut di tempat i. • Jika Qi > 0, maka barang sebanyak Q i. harus diturunkan di tempat i. • Jika Q i = 0, maka pada tempat i tidak akan dilakukan pengangkutan maupun penurunan barang.
Misalkan terdapat j tempat dalam PDP. Misalkan pula v i adalah suatu tempat sedemikian sehingga untuk v 1, v 2, …, v i-1 merupakan tempat asal bagi v i yang dihubungkan oleh TR 1, 2,… i-1, sedangkan vi+1, v i+2, …,v j adalah tempat tujuan dari vi yang dihubungkan oleh TR i+1, i+ 2, …, j. Setiap TR memiliki kuantitas barang sebesar q1, q 2,…, qi-1 , qi+1, qi+2 , …, qj. Masalah PDP ini dapat dimodelkan dalam bentuk graf berikut.
_______________________________________________________________________________ v i+1
v1 i+1, qi+1
1, q1
v2
. . .
2, q2
i+2, qi+2 vi
i-1, q i-1
v i-1
j, q j
v i+2
. . . vj
Gambar 4. Graf dari m tempat. _______________________________________________________________________________ Karena barang yang dikirimkan merupakan barang yang homogen, maka banyaknya barang pada tempat v i dapat dimodelkan sebagai berikut: i −1
j
n =1
n =i + 2
Q v i = ∑ q n − ∑ qn .
(10)
Hal ini berarti kuantitas barang yang masuk pada tempat v i harus sama dengan jumlah barang di tempat v i ditambah jumlah barang yang keluar dari vi. Persamaan (10) belum tentu berlaku pada suatu depot. Karena kuantitas barang pada saat kendaraan berangkat dari depot belum tentu sama dengan kuantitas barang setelah perjalanan usai. Ilustrasi mengenai kuantitas barang di suatu tempat dapat dilihat dalam Contoh 9. Contoh 9 Perhatikan masalah PDPTW dalam Contoh 8. TR a mengirimkan 70 kg barang dari v1 ke v 2, sehingga pada tempat v 2 terdapat 70 kg barang. Lalu barang tersebut diambil kembali sebesar 30 kg dan dikirimkan ke tempat v 3 sesuai dengan TR b. Akibatnya kuantitas barang yang diturunkan pada tempat v 2 sebesar 40 kg. Dengan cara yang sama
dapat dicari nilai kuantitas barang pada tempat v3 dan v 4. Pada tempat v3 dilakukan pengangkutan barang sebesar 20 kg, sedangkan pada tempat v4 tidak dilakukan pengangkutan maupun penurunan barang. Setelah perjalanan usai, kendaraan masuk ke depot dengan membawa barang yang akan diturunkan sebesar 50 kg. _ Dalam PDP, kuantitas barang dalam permintaan transportasi terkadang harus dicari melalui kuantitas barang pada tempat asal dan tempat tujuan. Kuantitas barang pada TR tidak selalu mencerminkan kuantitas pada tempat pengambilan maupun tempat pengiriman karena pada dasarnya kuantitas pada TR adalah kuantitas barang yang dibawa oleh suatu kendaraan dari tempat asal ke tempat tujuan. Untuk mencari nilai kuantitas barang dalam TR dari suatu PDP secara keseluruhan, dapat dimulai dengan memilih arah perjalanan. Perjalanan dimulai dan diakhiri dari suatu depot. Kuantitas TR dapat dicari dengan menggunakan Persamaan (10). Pencarian dihentikan setelah semua TR ditemukan.
17
3.1.3 Rute dalam Masalah Pengambilan dan Pengiriman dengan Kendala Waktu Ada banyak cycle y ang dapat dibuat dari PDPTW. Namun cycle-cycle tersebut belum tentu menjadi rute dalam PDPTW. Misal kan didefinisikan: • V k = S+ ∪ S - ∪ {k +} • Sk
= Himpunan TR yang berpadanan dengan Vk
• D k+ = waktu pengambilan/waktu
i−
sedemikian sehingga harus memenuhi: ? Dik+ + t ik ≤ Dik−
• D k− = waktu pengiriman/waktu tiba i
?
kendaraan tipe k pada tempat i −
t ik+ i −
1, jika kendaraan tipe k
• xk = i j
5 Setiap tempat di V k′ (kecuali depot k +) dikunjungi sesuai dengan kendala waktuny a. Ini berarti: i+
keberangkatan kendaraan tip e k pada tempat i +
=
dikunjungi terlebih dahulu dari pada i − . 4 Setiap tempat di Vk′ (kecuali depot k +) dikunjungi tepat 1 kali .
∀i ∈ S ′k , ∃ D k ∈ [e i + , li + ] ∧ D k ∈ [ei − , l i − ]
i
• t ik
himpunan permintaan transportasi dalam rute Rk. 3 Setiap i ∈ S k′ , jika {i+, i − } ⊆ Vk′ maka i+
melewati tempat i ke tempat j
0, selainnya
Rute dalam PDPTW didefinisikan sebagai berikut. Definisi 13 (Rute Fisibel PDPTW) Rute pengambilan dan pengiriman Rk untuk kendaraan tipe k yang fisibel untuk PDPTW adalah cycle berarah pada Vk′ ⊆ Vk yang memenuhi: 1 Dalam rut e Rk kendaraan berangkat dari depot k+ dan tidak berangkat sebelum waktu pemberangkatan kendaraan yang ditentukan ( ek+). 2 Setiap i ∈ S ′k harus memenuhi i+ ∈ Vk′ jika
x ik+ i − = x kj + j − = 1 ⇒ Di − ≤ D j +
dengan j ∈ S ′k dan i − = j + . 6 Muatan kendaraan tidak pernah melebihi Qk, dengan Qk adalah kapasitas kendaraan tipe k . 7 Dalam rute Rk kendaraan berhenti pada depot k + dan tidak melebihi waktu tiba kendaraan ( lk+) pada depot k +. Contoh berikut ini adalah ilustrasi mengenai suatu rute dalam PDPTW.
Contoh 10: Pencarian rute PDPTW Misalkan diketahui permintaan transportasi (TR) dari suatu perusahaan seperti pada Tabel 2. Misalkan hanya terdapat satu depot dan dilambangkan dengan Tempat 1. T erdapat satu kendaraan berkapasitas maksimum 100 kg dari satu tipe kendaraan yang beroperasi dalam PDPTW ini. Kendaraan tersebut hanya dapat dioperasikan mulai pukul 7.00 pagi sampai dengan pukul dan hanya jika i − ∈ Vk′ , dengan S k′ adalah 10.00 pagi. _______________________________________________________________________________ Tabel 2. Permintaan transportasi suatu perusahaan Tempat Asal T ujuan
Batas Waktu Pengambilan Pengiriman
t 1i
TR (i )
qi (kg)
a b c d
120 100 90 100
1 1 3 2
2 3 2 4
7.00 – 7.05 7.00 – 7.05 7.25 – 7.30 7.40 – 7.45
7.25 7.15 7.50 7.50 -
7.35 7.20 7.55 8.05
20 15 25 15
e f g
70 70 10
4 4 3
3 5 5
8.15 – 8.20 8.15 – 8.20 8.40 – 8.45
8.30 - 8.35 8.50 - 9.05 8.55 - 9.00
10 40 17
h
5
5
1
9.05 – 9.10
9.50 -10.00
50
(menit)
18
Untuk mempermudah pencarian rute, masalah pada Contoh 10 dapat dimodelkan dalam suatu graf berikut.
a,120
∃D 1+ = 7.00 ∈ [7 .00, 7. 05] b
∧ D1b − = 7 .15 ∈[ 7.15, 7 .20] ∋ ? ?
2
7. 00 + 15 ≤ 7. 15
x11,3 = x13, 5 = 1
d,100
b,100
3
b
Untuk i = g, ∃D 1g + = 8.40 ∈ [8.40 , 8.45] e,70
4
g,10 h,5
⇒ D 1 − ≤ D1g + ⇒ 7.15 ≤ D1g +
c,90
1
Untuk i=b,
f,70
∧ D1g − = 8.57 ∈[8 .55, 9.00 ] ? ? ?
5 Gambar 5. Graf dari Contoh 10. Dalam Gambar 5, himpunan tempat asal, tempat tujuan dan Depot 1 adalah V 1 = S+ ∪ S ∪ {1} = {1,2,3,4,5}. Terdapat empat cycle berarah yang berawal dan berakhir di Simpul 1. C ycle tersebut adalah 1-3-5-1, 1-3-2-4-5-1, 1-2-4-3-5-1, dan 1-2-4-5-1. Ke empat cycle tersebut belum tentu menjadi suatu rute dalam PDPTW. Suatu cycle dapat dikatakan rute PDPTW jika memenuhi seluruh persyaratan dalam Definisi Rute Fisibel PDPTW. Perhatikan cycle pertama (1-3-5-1). Ambil {1,3,5} ⊆ V1. Cycle tersebut memenuhi ketujuh syarat dalam Definisi Rute Fisibel PDPTW. 1 Dalam cycle pertama, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.05. Waktu keberangkatan kendaraan pada Depot 1 adalah pukul 7.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 1. 2 Untuk setiap permintaan transportasi i ∈ {b,g,h} memenuhi i+ ∈ {1,3,5} jika dan hanya jika i − ∈ {1,3,5}. 3 Untuk setiap permintaan transportasi i ∈{b,g,h} dan {i+, i − } ⊆ {1,3,5}, berlaku i + dikunjungi terlebih dahulu dari pada i − . 4 T empat 3 dan 5 dikunjungi tepat 1 kali. 5 Tem pat 3 dan 5 dikunjungi sesuai dengan kendala waktunya.. Operasi penjumlahan pada langkah ini merupakan penjumlahan antara waktu keberangkatan dengan lamanya perjalanan dalam satuan menit. Cycle 1-3-5-1 memenuhi:
∋
= = 1 ⇒ 7.15 ≤ 8.40 8.40 + 17 ≤ 8.57
x11, 3
x 13,5
x13,5 = x15 ,1 = 1
⇒ D1g − ≤ D1h + ⇒ 8.57 ≤ D1h +
Untuk i = h, ∃D 1h + = 9.08 ∈ [9 .05, 9.10 ]
∧ D1h − = 9.58 ∈ [9.50, 10.00]
∋
x13,5 = x15 ,1 = 1 ⇒ 8.57 ≤ 9.08 ? 9.08 + 50 ≤ 9.58 . 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 100 kg, karena kuantitas maksimum pada TR i ∈ {b,g,h} adalah sebesar 100 kg. 7 Rute kendaraan cycle pertama berhenti pada Depot 1 pada pukul 9.58. Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 10.00. Rute tersebut tidak melewati batas waktu tiba kendaraan di Depot 1 . Akibatnya cycle pertama merupakan rute fisibel PDPTW. Berbeda dengan cycle pertama, cycle kedua (1-3-2-4-5-1) bukan merupakan rute fisibel PDPTW, karena tidak memenuhi syarat kelima dalam Definisi Rute Fisibel PDPTW. Ambil {1,2,3,4,5} ⊆ V1. Perhatikan permintaan transportasi c dan d. Pada TR c, muatan sebesar 90 kg akan dikirimkan ke Simpul 2 ( c − ) dengan batas waktu pukul 7.50 - 7.55 . Kendaraan tersebut diharuskan memenuhi TR selanjutnya, yakni TR d. Kendala waktu pemberangkatan pada Simpul 2 (d+ ) adalah pukul 7.40 - 7.45, yang tidak mungkin dipenuhi jika kendala waktu pada c − adalah 7.50 - 7.55. Ini berarti cycle kedua bukan merupakan rute fisibel PDPTW. Perhatikan cycle ketiga (1-2-4-3-5-1) dan cycle keempat (1-2-4-5-1). Ambil {1,2,3,4,5} ⊆ V1 untuk cycle ketiga dan {1,2,4,5} ⊆ V1 untuk cycle keempat. Kedua cycle tersebut bukan suatu rute fisibel dalam PDPTW, karena muatan barang yang ?
19
dikirimkan melalui TR a melebihi kapasitas kendaraan. _ 3.2 Formulasi Masalah sebagai Masalah Pemartisian Himpunan Untuk memformulasikan PDPTW sebagai masalah pemartisian himpunan, Misalkan didefinisikan: ? k = himpunan semua rute pengambilan dan pengiriman yang fisibel untuk tipe kendaraan k. 1, jika i ∈ S ada dalam rute r ∈ Ω k δ irk = 0, selainnya
1, jika rute r ∈ Ω k digunakan x rk = 0, selainnya
c r = biaya dari rute r ∈ ? k . Biaya dari rute yang fisibel dapat di definisikan sebagai penjumlahan seluruh biaya pada TR yang digunakan pada rute tersebut, yaitu: k
c kr = ∑
∑ c ij x ij = ∑ ci + i − δ ir .
i∈V j ∈V
k
k
k
k
i∈S
Masalah pengambilan dan pengiriman dengan kendala waktu diformulasikan sebagai
pemrograman linear bilangan bulat (ILP) berikut: minimumkan ∑ ∑ c rk x rk (11) k∈M r∈Ω k
∑ ∑ dirk x rk = 1 ; ∀i ∈ S (12)
terhadap
k∈M r ∈O k
∑ xrk ≤ m k ; ∀k ∈ M
(13)
r∈Ωk
xkr ∈ {0,1}; ∀k ∈ M , r ∈ Ω k . Fungsi objektif (11) menyatakan bahwa akan dicari rute yang memiliki biaya minimum dari semua rute yang ada pada kendaraan tipe k. Kendala (12) menyatakan setiap permintaan transportasi hanya dilewati oleh satu rute kendaraan tipe k. Kendala ini disebut sebagai kendala pemartisian. Kendala (13) menyatakan rute kendaraan tipe k dapat dilewati oleh maksimum m k kendaraan. Kendala (13) ini disebut sebagai kendala ketersediaan kendaraan. Kolom pada matriks kendala menyatakan rute pengambilan dan pengiriman yang fisibel untuk kendaraan bertipe k .
IV PENYELESAIAN MASALAH 4.1 Teknik Pembangkitan Kolom Masalah pengambilan dan pengiriman dengan kendala waktu (PDPTW) berskala besar sering m elibatkan rute dalam jumlah yang banyak. Masalah seperti ini dapat diselesaikan dengan algoritme simpleks, namun memerlukan banyak waktu dalam pengerjaannya. Alternatif lain penyelesaian masalah ini adalah t eknik pembangkitan kolom (column generation). Teknik pembangkitan kolom merupakan teknik untuk menyelesaikan suatu pemrograman linear dengan hanya menggunakan sebagian variabel dari masalah kes eluruhan. Masalah PL dengan sebagian variabel tersebut diselesaikan hingga mendapatkan solusi yang optimal. Jika kondisi tersebut belum mencapai kondisi optimal pada masalah keseluruhan, maka P L dari sebagian variabel akan ditambahkan dengan variabel yang memenuhi suatu kriteria tertentu, kemudian diselesaikan untuk mendapatkan solusi yang optimal bagi P L tersebut. Hal ini terus dilakukan hingga mencapai kondisi optimal pada masalah keseluruhan atau telah mencapai suatu kriteria pemberhentian.
Dalam teknik pembangkitan kolom masalah PDPTW diselesaikan melalui P Lrelaksasinya. P L-relaksasi dari masalah PDPTW didapatkan dengan cara mengganti batasan x kr ∈ {0,1} dengan x rk ≥ 0 , sehingga PL-relaksasi dari masalah PDPTW adalah: minimumkan ∑ ∑ c kr x rk k ∈M r∈Ω k
terhadap
∑ ∑ dirk x kr = 1 ; ∀i ∈ S
(14)
∑ x kr ≤ m k ; ∀k ∈ M
(15)
k∈M r∈O k
r ∈Ω k
xrk ≥ 0; ∀k ∈ M , r ∈ Ω k . Masalah PL-relaksasi disebut sebagai masalah induk (master problem/MP). Dalam teknik pembangkitan kolom digunakan masalah indu k terbatas (restricted master problem/RMP), yaitu masalah pemrograman linear dengan menggunakan sebagian variabel dari MP. Misalkan RMP pada langkah tertentu t, dinotasikan dengan RMPt, dapat dinyatakan sebagai:
20
RMPt: minimumkan ∑
1
∑ c kr x rk
k ∈M r∈Ω′k
terhadap
∑ ∑ dirk x rk = 1 ; ∀i ∈ S
2
k∈M r∈O ′k
∑ x kr ≤ mk ; ∀k ∈ M
3
r ∈Ω′k
xrk ≥ 0 ; ∀k ∈ M , r ∈ Ω' k ⊆ Ωk . Misalkan masalah induk (MP) dari PDPTW mempunyai solusi fisibel x. Jika biaya tereduks i dari masalah MP tersebut adalah taknegatif maka x merupakan solusi optimal bagi MP. Biaya tereduksi dari masalah PL dapat ditemukan melalui masalah dualnya. Untuk mencari masalah dual dari MP, misalkan variabel dual u i (i ∈ S) diasosiasikan dengan Kendala (14) dan variabel dual v k (k ∈ M) diasosiasikan dengan Kendala (15). Maka masalah dual dari MP adalah: maksimumkan ∑ ui + ∑ mk v k i∈S
k∈M
terhadap k k ∑ δir ui + vk ≤ c r ; ∀r ∈ Ωk , k ∈ M
(16)
i∈S
u i takterbatas dan vk ≤ 0. Misalkan didefinisikan d rk sebagai biaya tereduksi dari masalah MP dengan d rk = crk − ∑δirkui − v k ; ∀r ∈ Ω k , k ∈ M . i∈S
Keoptimalan solusi RMP untuk masalah keseluruhan dapat diperiksa dengan mencari nilai biaya tereduksi dari seluruh rute yang fisibel. Masalah pencarian biaya tereduksi dari masalah keseluruhan disebut sebagai pricing problem. Pricing problem untuk masalah PDPTW adalah sebagai berikut: minimumkan{crk − ∑δirk ui −vk ∀r ∈Ωk ,k ∈ M }. i∈S
Misalkan z adalah solusi dari pricing problem. Misalkan k z adalah tipe kendaraan k yang berpadanan dengan z dan rz adalah rute yang berpadanan dengan z. Jika z ≥ 0, tidak ada lagi rute yang dapat dioptimalkan, sehingga solusi optimal RMP merupakan solusi optimal untuk MP. Sebaliknya jika z < 0, maka xrkz
Himpunan awal Ω′k ditentukan sehingga anggota dari himpunan tersebut mempunyai solusi fisibel untuk vektor x. Masalah induk terbatas diselesaikan dengan menggunakan algoritme simpleks. Pricing problem diselesaikan. Jika z ≥ 0 maka proses berakhir. Jika z < 0, maka Ω ′k = Ω ′k z ∪ {rz } dan kembali ke Langkah 2.
4.2 Pricing Problem Pricing problem dalam PDPTW dapat didekomposisi menjadi beberapa submasalah, berdasarkan tipe kendaraan untuk mempermudah pencarian biaya tereduksi jika dihadapkan pada tipe kendaraan yang beragam. Misalkan pricing problem Pk adalah masalah mencari biaya tereduksi dari rute fisibel untuk kendaraan bertipe k, sehingga Pk adalah masalah: meminimumkan c kr − ∑ δ irk u i − v k r ∈ Ω k . i∈S Masalah pricing problem Pk dapat dimodifikasi menjadi masalah pemrograman linear, dengan tujuan mempermudah pencarian biaya tereduksi untuk kendaraaan bertipe sama dalam skala besar. Misalkan didefinis ikan c i′+ i − = c ik+ i − − u i ,
c′k′+ j = c′k + j − vk dan biaya rute fisibel r oleh kendaraan bertipe k didefinisikan sebagai: k
cr =
Secara ringkas teknik pembangkitan kolom untuk optimasi PDPTW dapat dituliskan sebagai berikut:
k
k
k
k
(17)
i∈S
Biaya tereduksi dari rute fisibel r oleh kendaraan bertipe k dapat dituliskan menjadi: d rk = crk − ∑δ irkui − vk i∈S
=
k k k ∑ ∑ c ij x ij − ∑δ irui − vk
i∈V j ∈V i∈S k k c i + i − x i + i − − δ irkui − vk . = i∈S i∈S k x Karena nilai i + i − akan sama dengan
∑
∑
nilai δ irk
untuk rute fisibel yang sama, maka: k k d rk = ∑ ci + i − − ui x i + i − − v k i∈S
z
merupakan variabel yang dapat masuk ke dalam basis, sehingga kolom (rute) r z untuk kendaraan tipe k z ditambahkan ke dalam Ω ′k z .
∑ ∑ c ij x ij = ∑ ci + i − δ ir .
i∈V j ∈V
=
(
)
∑ ∑ c ′ij xij − v k k
(18)
i∈V j∈V
Biaya Tereduksi (18) dapat digunakan untuk mencari rute fisibel dengan biaya tereduksi minimum, namun perlu dijamin agar TR yang dipilih akan membentuk suatu rute fisibel, sehingga pricing problem Pk dapat diformulasikan sebagai berikut:
21
∑ ∑ c′ij xijk − vk
Minimumkan
dilewati satu kali (
(a)
objektif Pk dapat dituliskan menjadi: ∑ (c ′k + j − v k )x kk + j + ∑ ∑ c′ij xijk
i∈V k j∈V k
b∈V k
terhadap:
∑ xkk+ j = 1
j∈V k
∑ x kj k + = 1
(b)
j∈V k
∑ xik+ j = ∑ x kj i + = Yi ; ∀i ∈ S k
j∈V k
j∈V k
Yi ∈ {0,1} e
k+
i
xi + i − = 1 ⇒ x ik+ i − = x kj +
i Dik+
(c)
; ∀i ∈ S k
(d)
; ∀i ∈ S k
(e)
+ t i ≤ D ik− ; ∀i ∈ S k
(f)
≤ D k+ ≤ D k− ≤ l
k+
= 1 ⇒ Di − ≤ D j + ;
j−
−
i = j + , j ∈ S k , ∀i ∈ S k
(g)
e+ ≤ D+ ≤l+
; ∀i ∈ S k
(h)
e− ≤D− ≤l−
; ∀i ∈ S k
(i)
xi + i − = 1 ⇒ q i ≤ Qk ; ∀ i ∈ S k
(j)
i
i
i
i
i
i
xi , j ∈ {0,1}
; ∀i , j ∈ Vk
(k)
Fungsi objektif Pk dapat disederhanakan menjadi: ∑ ∑ c ′ij x ijk − v k i∈V k j∈V k
=
∑ c ′k + j x kk + j +
j∈V k
∑ +
i∈S ∪S
−
∑ xkk+ j = 1), maka fungsi
(19)
∑ cij′ xijk − vk . j ∈Vk
Karena TR yang berawal dari depot menuju ke seluruh tempat i ∈V k hanya
i∈S + ∪S −
j∈V k
=
∑
c ′k′ + j x kk+ j
∑
∑ c′ij′ xijk .
j ∈Vk
=
+
∑ +
i∈S ∪S
−
j∈Vk
∑ c′ij xijk j∈Vk
i∈V k j∈V k
Fungsi objektif (19) menyatakan bahwa akan dicari TR yang memiliki biaya tereduksi minimum. Kendala (a) menjamin akan dipilih satu TR yang berawal dari depot k + ke tempat j ∈Vk . Kendala (b) menjamin menjamin akan dipilih satu TR yang berawal dari tempat j ∈ V k ke depot k +. Kendala (c) dan (d) menjamin kendaraan berangkat dari depot k+, satu kali melewati TR i ∈ S k , satu kali melewati tempat i ∈V k dan berakhir pada depot yang sama. Kendala (e), (f), (g), ( h) dan (i) menjamin kendaraan mengunjungi tempat pengambilan dan pengiriman sesuai dengan kendala waktu. Kendala (j) menjamin kendaraan melewati TR sesuai dengan kendala kapasitas kendaraan. Misalkan z k adalah solusi dari pricing problem Pk . Nilai biaya tereduksi terkecil dari seluruh pricing problem Pk adalah: z = min { z1 , z 2 ,..., z k }, ∀k ∈ M . Nilai biaya tereduksi tersebut digunakan untuk memeriksa keoptimalan solusi RMP untuk masalah keseluruhan.
V CONTOH KASUS Misalkan permintaan transportasi (TR) dari suatu perusahaan diberikan dalam Tabel 3. Depot dilambangkan oleh Tempat 1 dan 2. Terdapat dua tipe kendaraan yang dapat dioperasikan dari pukul 7 pagi hingga pukul 12 siang. Tipe kendaraan pertama berangkat dari Depot 1, sedangkan tipe kendaraan kedua berangkat dari Depot 2. Terdapat 4 kendaraan untuk setiap tipe kendaraan. Kendaraan tipe
pertama memiliki kapasitas maksimum sebesar 140 unit barang, sedangkan kendaraan tipe kedua memiliki kapasitas maksimum sebesar 100 unit barang. Biaya rute fisibel didefinisikan sebagai biaya TR yang digunakan dalam rute tersebut. Masalah PDPTW ini dapat dimodelkan ke dalam suatu graf seperti pada Gambar 6.
22
Tabel 3. Contoh kasus masalah PDPTW
TR (i)
qi (unit )
a b c d e f g h i j k l m n o p q r s t u v w x y z aa bb
140 120 100 80 0 100 50 10 0 0 30 50 70 0 30 60 80 110 110 70 10 100 40 20 0 70 40 5
Tempat Asal Tujuan 1 3 4 5 6 2 6 3 5 2 7 9 8 1 9 10 8 7 1 14 16 1 13 14 15 2 12 11
3 4 5 6 1 6 3 5 2 7 9 8 2 9 10 8 7 1 14 16 1 13 14 15 1 12 11 2
Batas waktu Pengambilan Pengiriman 07.00 08.00 09.20 09.50 10.50 08.00 09.15 10.10 11.00 07.30 08.00 08.00 10.00 07.00 08.00 08.00 08.00 10.00 07.00 09.00 10.10 07.00 08.40 10.30 11.00 08.00 09.20 10.30
- 07.15 - 08.10 - 09.30 - 10.00 - 11.00 - 08.15 - 09.20 - 10.20 - 11.15 - 07.40 - 10.00 - 10.00 - 10.10 - 07.15 - 10.00 - 10.00 - 10.00 - 10.10 - 07.15 - 09.10 - 10.15 - 07.15 - 09.00 - 10.35 - 11.15 - 08.15 - 09.30 - 10.40
07.45 09.00 09.40 10.30 11.20 09.10 09.40 10.40 12.00 08.00 08.00 08.00 10.40 08.00 08.00 08.00 08.00 10.40 07.40 10.00 10.40 08.00 10.00 11.00 11.50 09.00 10.00 12.00
- 08.00 - 09.15 - 10.00 - 10.45 - 11.35 - 09.15 - 10.00 - 10.50 - 12.15 - 10.00 - 10.00 - 10.00 - 11.00 - 10.00 - 10.00 - 10.00 - 10.00 - 11.00 - 08.00 - 10.10 - 11.00 - 08.15 - 10.20 - 11.05 - 12.00 - 09.20 - 10.15 - 12.30
t
1 i
= t
2 i
Biaya Perjalanan Kendaraan
(menit)
Tipe 1
Tipe 2
40 60 30 30 25 60 25 30 60 30 30 30 35 30 30 30 30 30 40 60 40 30 75 25 40 60 30 50
100 90 70 40 30 10 10 80 13 15 10 90 14 70 90 110 140 140 50 90 100 90 50 70 50 85 96 23
19 60 50 20 30 80 70 70 40 50 60 90 100 40 40 40 15 12 45 63 25 86 96 65 54 130 100 150
23
4 b,120
16
c,100 11 h, 10
3 u, 10
t, 70
a,140
15 x. 20
g, 50 e, 0
5 d, 80 i, 0
6
bb, 5
f, 100
aa, 40
y, 0
14
1
2 r, 110
j, 0
s, 110 z, 70
7
n, 0 w, 40
v, 100
m, 70
q, 80
k, 30
12 13
l, 50
9
o, 30
8
p, 60 10
Gambar 6. Graf dari Tabel 3. _______________________________________________________________________________ Terdapat 13 cycle berarah yang dapat dibentuk dari Gambar 6. Namun hanya ada 10 rute yang fisibel untuk masalah PDPTW. Pencarian rute PDPTW yang fisibel dapat dilihat dalam Lampiran 3. Rute kendaraan yang fisibel untuk masalah PDPTW adalah: R1,1 = 1-3-4-5-6-1 untuk TR { a,b,c,d,e} R1,2 = 1-9-10-8-7-1 untuk TR {n,o,p,q,r } R1,3 = 1-9-8-7-1 untuk TR { n,l,q,r } R1,4 = 1-14 -16-1 untuk TR {s,t,u} R1,5 = 1-14 -15-1 untuk TR {s,x,y} R1,6 = 1-13-14 -15-1 untuk TR {v,w,x,y} R2,1 = 2-6-3-5-2 untuk TR { f,g,h,i} R2,2 = 2-7-9-8-2 untuk TR { j,k,l,m } R2,3 = 2-7-9-10-8-2 untuk TR {j,k,o,p,m} R2,4 = 2-12-11-2 untuk TR {z,aa,bb}. Untuk memformulasikan PDPTW sebagai masalah pemartisian himpunan, didefinisikan: M = {1,2} ? 1 = {1,2,3,4,5,6} ? 2 = {1,2,3,4}
1, jika i ∈ S ada dalam rute r ∈ Ω k δ irk := 0, selainnya 1, jika rute r ∈ Ω k digunakan x rk := 0, selainnya
c11 = c11, 3 + c13, 4 + c14,5 + c15 ,6 + c16 ,1 = 100 + 90 + 70 + 40 + 30 = 330 c 12 = c11, 9 + c 19 ,10 + c 110,8 + c 18, 7 + c 17,1 = 70 + 90 + 110 + 140 + 140 = 550
c13 = c11, 9 + c19 ,8 + c18 ,7 + c17 ,1 = 70 + 90 + 140 + 140 = 440 1 1 c 14 = c11,14 + c14 ,16 + c 16,1
= 50 + 90 + 100 = 240 1 1 c15 = c11,14 + c14 ,15 + c 15,1
= 50 + 70 + 50 = 170 1 1 1 1 c16 = c1,13 + c13,14 + c 14,15 + c15,1 = 260
= 90 + 50 + 70 + 50 = 260
c12 = c22,6 + c62,3 + c32,5 + c52, 2 = 80 + 70 +70 + 40
= 260
c22 = c22,7 + c72,9 + c92,8 + c82, 2 c 32
= 50 + 60 + 90 + 100 = 300 2 2 = c 22, 7 + c 72,9 + c 92,10 + c 10 ,8 + c 8 ,2 = 50 +60 + 40 + 40 + 100 = 290
2 2 c42 = c 22,12 + c12 ,11 + c 11, 2
= 130 + 100 + 150 = 380 Masalah PDPTW diformulasikan berikut:
sebagai
24
_______________________________________________________________________________ minimumkan 330 x11 + 550 x12 + 440 x13 +240 x14 + 170 x15 + 260 x16 + 260 x12 + 300 x22 + 290 x32 +380 x 24 terhadap: a) x11 = 1 l) x13 + x 22 =1 w) x16 = 1 b)
x11 = 1
m) x 22 + x 32 = 1
x)
x 15 + x 16 = 1
c)
x11 = 1
n)
x12 + x13 = 1
y)
x15 + x16 = 1
d)
o)
x 24 = 1
p)
x 12 + x12 +
z)
e)
x11 = 1 x11 = 1
f)
x12 = 1
q)
x12 + x13 = 1
bb) x 24 = 1
g)
r)
x11 + x 12 + x 13 + x 14 + x 15 + x 16 ≤ 4
2)
x12 + x 22 + x32 + x 24 ≤
t)
x 12 + x 13 = 1 x14 + x15 = 1 x 14 = 1
1)
i)
x12 = 1 x12 = 1 x12 = 1
3)
x11 ,
j)
x22 + x32 = 1
u)
x14 = 1
h)
s)
x 32 = 1 x32 = 1
aa) x 24 = 1
x 12 ,
x 13 ,
x 14 ,
4
x 15 ,
x 16 ,
x 12 , x 22 ,
x32 , x42 ∈ {0 ,1}
k) x22 + x32 = 1 v) x16 = 1 _______________________________________________________________________________ Masalah induk dari masalah PDPTW variabel untuk RMP0 yang memiliki solusi diperoleh dengan mengganti batasan fisibel bagi RMP0. Variabel tersebut adalah x rk ∈ {0,1} dengan x rk ≥ 0 ; untuk k = 1, r = x11 , x 12 , x 14 , x 16 , x 12 , x 22 dan x 24 . Dengan 1,2,3,4,5,6 dan untuk k = 2, r = 1,2,3,4. Dalam demikian RMP0 yang terbentuk adalah sebagai teknik pembangkitan kolom, misalkan dipilih berikut: _______________________________________________________________________________ minimumkan 330 x11 + 550 x12 + 240 x14 + 260 x16 + 260 x12 + 300 x 22 + 380 x 24 terhadap: a)
x11 = 1
i)
x12 = 1
q)
x12 = 1
y)
x16 = 1
b)
x11 = 1
j)
x 22 = 1
r)
x 12 = 1
z)
x 24 = 1
c)
x11 = 1
k)
x 22 = 1
s)
x14 = 1
aa)
x 24 = 1
d)
x11 = 1
l)
x 22 =1
t)
x 14 = 1
bb)
x 24 = 1
e)
x11 = 1
m)
x 22 = 1
u)
x14 = 1
1)
x11 + x12 + x14 + x16 ≤
f)
x12 = 1 x12 = 1 x12 = 1
n)
x12 = 1 x 12 = 1 x12 = 1
v)
x16 = 1 x 16 = 1 x16 = 1
g) h)
o) p)
w) x)
2)
x12 + x 22 + x 24 ≤ 4 x11 , x 12 , x 14 , x 16 , x 12 ,
4
x 22 , x 24 ≥ 0
_______________________________________________________________________________ Dengan menggunakan LINDO 6.1 masalah RMP0 menghasilkan solusi berikut: x11 = x12 = x14 = x16 = x12 = x 22 = x42 =1, dengan biaya sebesar 2320 (lihat Lampiran 4). Solusi masalah dual untuk RMP0 adalah: ua = 330, uf = 260, uj = 300, un = 550, us = 240, uv = 260, uz = 380 dan ub = uc = ud = ue = ug = uh = u i = uk = ul = u m = uo = up = uq = ur = ut = uu = u w = ux = uy = u aa = ubb = v 1 = v 2 = 0. Keoptimalan solusi RMP untuk MP dapat diperiksa dengan menyelesaikan pricing
problem . Karena terdapat dua tipe kendaraan, maka pricing problem dapat didekomposisi berdasarkan tipe kendaraannya. Masalah pencarian rute dengan biaya tereduksi terkecil untuk kendaraan Tipe 1 dinotasikan sebagai P1 dan untuk kendaraan Tipe 2 dinotasikan sebagai P2. Seluruh tempat dan TR yang digunakan dalam P1, dapat dimodelkan ke dalam bentuk graf berikut:
25
_______________________________________________________________________________ 4 c,100
b,120
16
h, 10
3 u, 10
t, 70
5 d, 80
a,140
15
e, 0
x. 20
y, 0
14
6
1 r, 110 s, 110 7
n, 0 w, 40
v, 100
q, 80
13
l, 50
9
o, 30
8
p, 60 10
Gambar 7. Graf dari V1 ∪ S 1 . _______________________________________________________________________________ Pricing problem P 1 dapat dituliskan menjadi: Minimumkan (100–ua –v 1 )x1,3 + (90– u b) x 3,4 + (70– uc )x4,5+ (40– ud )x5,6 + (30 –ue) x6,1 + (80–uh )x3,5 + (90 – ul) x9,8 + (70 – un – v 1) x 1,9 + (90 – u o) x 9,10 + (110 – up )x 10,8 + (140 – uq ) x8,7 + (140 – ur )x7,1 + (50 – us – v 1) x1,14 + (90 – ut )x14,16 + (100 – uu ) x16,1 + (90 – uv – v1) x1,13 + (50 – u w ) x13,14 + (70 – ux ) x14,15 + (50 – uy ) x15,1 terhadap: a) x1,3 + x1,9 + x1,13 + x1,14 = 1 b) x16,1 + x15,1 + x7,1 + x6,1 = 1 c.1) x1,3 + x1,9 + x1,13 + x1,14 = x16,1 + x15,1 + x7,1 + x6,1 = Ya c.2) x1,3 = x3,4 + x3,5 = Yb c.3) x3,4 = x4,5 = Yc c.4) x4,5 + x3,5 = x5,6 = Yd c.5) x5,6 = x6,1 = Ye c.6) x5,6 = x6,1 = Yg c.7) x1,3 = x3,4 + x3,5 = Yh c.8) x8,7 = x7,1 = Yk c.9) x1,9 = x9,8 + x9,10 = Yl c.10) x1,3 + x1,9 + x1,13 + x1,14 = x16,1 + x15,1 + 140 x 7,1 + 30 x 6,1 = Yn c.11) x1,9 = x9,10 + x9,8 = Yo
c.12) c.13) c.14) c.15) c.16) c.17) c.18) c.19) c.20) c.21) d) e)
f.1) f.2) f.3) f.4) f.5) f.6) f.7) f.8)
x9,10 = x 10,8 = Yp x9,8 + x10,8 = x8,7 = Yq x8,7 = x7,1 = Yr x1,3 + x 1,9 + x1,13 + x1,14 = x16,1 + x15,1 + x7,1 + x 6,1 = Ys x1,14 + x13,14 = x14,16 + x14,15 = Yt x14,16 = x 16,1 = Yu x1,3 + x 1,9 + x1,13 + x1,14 = x16,1 + x15,1 + x7,1 + x6,1 = Yv x1,13 = x 13,14 = Yw x1,14 + x13,14 = x14,16 + x14,15 = Yx x14,15 = x 15,1 =Yy Yi ∈ {0,1} ; i = a, b, c, d, e, f, h, n, o, p, q, r, s, t, u, v , w, x, y + − 7. 00 ≤ D i ≤ Di ≤ 12.00 ; i = a, b, c, d, e, f, h, n, o, p, q, r, s, t, u, v, w,x, y x1,3 = 1 ⇒ D a+ + 40 ≤ Dax3,4= 1 ⇒ D b+ + 60 ≤ D bx4,5= 1 ⇒ D c+ + 30 ≤ D cx5,6= 1 ⇒ D d+ + 30 ≤ D dx6,1= 1 ⇒ D e+ + 25 ≤ D ex3,5= 1 ⇒ D h+ + 30 ≤ D hx9,8 = 1 ⇒ D l+ + 30 ≤ Dlx1,9 = 1 ⇒ D n+ + 30 ≤ D n-
26
f.9) f.10) f.11) f.12) f.13) f.14) f.15) f.16) f.17) f.18) f.19) g.1) g.2) g.3) g.4) g.5) g.6) g.7) g.8) g.9) g.10) g.11) g.12) g.13) g.14) g.15) g.16) g.17) g.18) g.19) h.1) h.2) h.3) h.4) h.5) h.6) h.7) h.8) h.9) h.10) h.11) h.12) h.13) h.14) h.15) h.16) h.17) h.18)
⇒ Do+ + 30 ≤ Dox9,10 = 1 ⇒ Dp+ + 30 ≤ Dpx10,8 = 1 ⇒ Dq+ + 30 ≤ Dqx8,7 = 1 ⇒ Dr+ + 30 ≤ Drx7,1 = 1 ⇒ Ds+ + 40 ≤ Dsx1,14 = 1 x14,16 = 1 ⇒ Dt+ + 60 ≤ Dt⇒ Du+ + 40 ≤ Dux16,1 = 1 ⇒ Dv+ + 30 ≤ Dvx1,13 = 1 x13,14 = 1 ⇒ Dw+ + 75 ≤ Dwx14,15=1 ⇒ Dx+ + 25 ≤ Dxx15,1 =1 ⇒ Dy+ + 40 ≤ Dyx1,3 = x3,4 = 1 ⇒ D a- ≤ Db+ x1,3 = x3,5 = 1 ⇒ Da- ≤ Dh+ x3,4 = x4,5 = 1 ⇒ D b- ≤ Dc+ x4,5 = x5,6 = 1 ⇒ D c- ≤ Dd+ x5,6 = x6,1 = 1 ⇒ D d- ≤ De+ x3,5 = x5,6= 1 ⇒ D h- ≤ Dd+ x9,8 = x8,7 = 1 ⇒ D l- ≤ Dq+ x1,9 = x9,10 = 1 ⇒ D n- ≤ Do+ x1,9 = x9,8 = 1 ⇒ D n- ≤ Dl+ x9,10 = x10,8 = 1 ⇒ D o- ≤ Dp+ x10,8 = x8,7 = 1 ⇒ D p- ≤ Dq+ x8,7 = x7,1 = 1 ⇒ D q- ≤ Dr+ x1,14 = x14,16 = 1 ⇒ D s- ≤ Dt+ x1,14 = x14,15 = 1 ⇒ D s- ≤ Dx+ x14,16 = x16,1 = 1 ⇒ D t- ≤ Du+ x1,13 = x13,14 = 1 ⇒ D v- ≤ Dw+ x13,14 = x 14,16 = 1 ⇒ D w- ≤ Dt+ x13,14 = x 14,15= 1 ⇒ D w- ≤ Dx+ x14,15= x15,1 = 1 ⇒ D x- ≤ Dy+ 07.00 ≤ D a+ ≤ 07.15 08.00 ≤ D b+ ≤ 08.10 09.20 ≤ D c+ ≤ 09.30 09.50 ≤ D d+ ≤ 10.00 10.50 ≤ D e+ ≤ 11.00 10.10 ≤ D h+ ≤ 10.20 08.00 ≤ D l+ ≤ 10.00 07.00 ≤ D n+ ≤ 07.15 08.00 ≤ D o+ ≤ 10.00 08.00 ≤ D p+ ≤ 10.00 08.00 ≤ D q+ ≤ 10.00 10.00 ≤ D r+ ≤ 10.10 07.00 ≤ D s+ ≤ 07.15 09.00 ≤ D t+ ≤ 09.10 10.10 ≤ D u+ ≤ 10.15 07.00 ≤ D v+ ≤ 07.15 08.40 ≤ D w+ ≤ 09.00 10.30 ≤ D x+ ≤ 10.35
h.19) i.1) i.2) i.3) i.4) i.5) i.6) i.7) i.8) i.9) i.10) i.11) i.12) i.13) i.14) i.15) i.16) i.17) i.18) i.19) j.1) j.2) j.3) j.4) j.5) j.6) j.7) j.8) j.9) j.10) j.11) j.12) j.13) j.14) j.15) j.16) j.17) j.18) j.19) k)
11.00 ≤ Dy+ ≤ 11.15 07.45 ≤ Da- ≤ 08.00 09.00 ≤ Db- ≤ 09.15 09.40 ≤ Dc- ≤ 10.00 10.30 ≤ Dd- ≤ 10.45 11.20 ≤ De- ≤ 11.3 5 10.40 ≤ Dh- ≤ 10.50 08.00 ≤ Dl- ≤ 10.00 08.00 ≤ Dn- ≤ 10.00 08.00 ≤ Do- ≤ 10.00 08.00 ≤ Dp- ≤ 10.00 08.00 ≤ Dq- ≤ 10.00 10.40 ≤ Dr- ≤ 11.00 07.40 ≤ Ds- ≤ 08.00 10.00 ≤ Dt- ≤ 10.10 10.40 ≤ Du- ≤ 11.00 08.00 ≤ Dv- ≤ 08.15 10.00 ≤ Dw- ≤ 10.20 11.00 ≤ Dx- ≤ 11.05 11.50 ≤ Dy- ≤ 12.00 ⇒ 140 ≤ 140 x1,3 = 1 ⇒ 120 ≤ 140 x3,4 = 1 x4,5= 1 ⇒ 100 ≤ 140 x5,6 = 1 ⇒ 80 ≤ 140 x6,1= 1 ⇒ 0 ≤ 140 x3,5= 1 ⇒ 10 ≤ 140 x9,8 = 1 ⇒ 50 ≤ 140 x1,9 = 1 ⇒ 0 ≤ 140 x9,10 = 1 ⇒ 30 ≤ 140 x10,8 = 1 ⇒ 60 ≤ 140 x8,7 = 1 ⇒ 80 ≤ 140 x7,1 = 1 ⇒ 110 ≤ 140 x1,14 = 1 ⇒ 110 ≤ 140 x14,16 = 1 ⇒ 70 ≤ 140 x16,1 = 1 ⇒ 10 ≤ 140 x1,13 = 1 ⇒ 100 ≤ 140 x13,14 = 1 ⇒ 40 ≤ 140 x14,15 =1 ⇒ 20 ≤ 140 x15,1 =1 ⇒ 0 ≤ 140 x1,3, x4,5, x5,6, x6,1 x 3,5, x9,10, x10,8, x8,7, x 7,1, x1,14 , x14,16, x16,1, x 1,13, x13,14 , x14,15, x 15,1, x9,8 ∈ {0 ,1} .
Pricing problem P2 merupakan masalah pencarian nilai biaya tereduksi dari kendaraan Tipe 2. Gambar 8 merupakan graf dari seluruh tempat dan TR yang digunakan oleh kendaraan Tipe 2.
27
__________________________________________________________________ 4 c,100
b,120
11
h, 10 3
5 g, 50 6
i, 0
bb, 5
f, 100 aa, 40 2 j, 0 z, 70 k, 30
m, 70
7
12 l, 50
9
o, 30
8
p, 60 10
Gambar 8. Graf dari V2 ∪ S 2 .
__________________________________________________________________ Pricing problem P 2 dapat diformulasikan sebagai berikut: Minimumkan (60 – ub )x3,4 + (50 – uc )x4,5 + (80– u f – v 2 ) x2,6 + (70 – ug ) x6,3 + (70– u h)x3,5 +(40 –ui) x5,2 + (50 – u– v 2)x 2,7 + (60– uk )x7,9 + (90 – ul )x9,8 +(100 –um) x8,2 + (40 –u o)x9,10 + (40–up)x10,8 + (130 – uz – v 2)x2,12 + (100 – uaa )x12,11 + (150 – ubb) x11,12 terhadap: a) x2,7 + x2,12 + x2,6 = 1 b) x5,2 + x8,2 + x11,12 = 1 c.1) x2,7 + x2,12 + x2, =x5,2 + x8,2 + x11,12 = Yf c.2) x2,6 = x6,3 = Yg c.3) x6,3 = x3,5 + x3,4 = Yh c.4) x4,5 + x3,5 = x5,2 = Yi c.5) x6,3 = x3,5 + x3,4 = Yb c.6) x3,4 = x4,5 = Yc c.7) x2,7 + x2,12 + x2,6 =x5,2 + x8,2 + x11,12= Yj c.8) x2,7 = x7,9 = Yk c.9) x7,9 = x 9,8 + x9,10 = Yl c.10) x9,8 + x10,8 = x8,2 = Ym c.11) x7,9 = x 9,8 + x9,10 = Yo c.12) x9,10 + x10,8 = Yp
c.13) x2,7 + x2,12 + x2,6 =x5,2 + x8,2 + x11,12 = Yz c.14) x2,12 = x 12,11 = Yaa c.15) x12,11 = x11,12= Ybb d) Yi ∈ {0,1} ; i = b, c, f, g, h, i, j, k, l, m, o, p, z, aa, bb + − 7.00 ≤ Di ≤ D i ≤ 12. 00 ; i= b, c, f, g, h, i, j, k , l, m, o, p, z, aa, bb f.1) x3,4 = 1 ⇒ D b+ + 60 ≤ D bf.2) x4,5 = 1 ⇒ D c+ + 30 ≤ D cf.3) x2,6 = 1 ⇒ D f+ + 60 ≤ Dff.5) x6,3 = 1 ⇒ D g+ + 25 ≤ D gf.6) x3,5 = 1 ⇒ D h+ + 30 ≤ D hf.7) x5,2 = 1 ⇒ D i+ + 60 ≤ Dif.8) x2,7= 1 ⇒ D j+ + 30 ≤ Dj⇒ D k+ + 30 ≤ D kf.9) x7,9 = 1 ⇒ f.10) x9,8 = 1 D l+ + 30 ≤ Dl⇒ f.11) x 8,2 = 1 D m+ + 35 ≤ Dm⇒ D o+ + 30 ≤ D of.12) x9,10 = 1 ⇒ D p+ + 30 ≤ D pf.13) x10,8 = 1 ⇒ D z+ + 60 ≤ D zf.14) x2,12 = 1 f.15) x12,11 = 1 ⇒ D aa+ + 30 ≤ D aa⇒ D bb+ + 50 ≤ D bbf.16) x11,2 = 1
e)
28
g.1) x2,6 = x6,3 = 1 ⇒ Df- ≤ Dg+ g.2) x6,3 = x3,5 = 1 ⇒ Dg- ≤ D h+ g.3) x6,3 = x3,4 = 1 ⇒ Dg- ≤ D b+ g.4) x3,4 = x4, 5= 1 ⇒ Db- ≤ D c+ g.5) x3,5 = x5,2 = 1 ⇒ Dh- ≤ D i+ g.6) x2,7= x7,9 = 1 ⇒ Dg- ≤ D k+ g.7) x7,9 = x9,8 = 1 ⇒ Dk- ≤ Dl+ g.8) x7,9 = x9,10 = 1 ⇒ Dk- ≤ Do+ g.9) x9,8 = x8,2 = 1 ⇒ Dl- ≤ Dm+ g.10) x9,10 = x10,8 = 1 ⇒ Do- ≤ Dp+ g.11) x10,8 = x8,2 = 1 ⇒ Dp- ≤ D m+ g.12) x2,12 = x12,11= 1 ⇒ Dz- ≤ D aa+ g.13) x12,11 = x 11,2 = 1 ⇒ Daa- ≤ Dbb+ h.1) 08.00 ≤ D b+ ≤ 08.10 h.2) 09.20 ≤ D c+ ≤ 09.30 h.3) 08.00 ≤ D f+ ≤ 08.15 h.4) 09.15 ≤ D g+ ≤ 09.20 h.5) 10.10 ≤ D h+ ≤ 10.20 h.6) 11.00 ≤ D i+ ≤ 11.15 h.7) 07.30 ≤ D j+ ≤ 07.40 h.8) 08.00 ≤ D k+ ≤ 10.00 h.9) 08.00 ≤ D l+ ≤ 10.00 h.10) 10.00 ≤ D m+ ≤ 10.10 h.11) 08.00 ≤ D o+ ≤ 10.00 h.12) 08.00 ≤ D p+ ≤ 10.00 h.13) 08.00 ≤ D z+ ≤ 08.15 h.14) 09.20 ≤ D aa+ ≤ 09.30 h.15) 10.30 ≤ D bb+ ≤ 10.40 i.1) 09.00 ≤ D b- ≤ 09.15 i.2) 09.40 ≤ D c- ≤ 10.00 i.3) 09.10 ≤ D f- ≤ 09.15 i.4) 09.40 ≤ D g- ≤ 10.00 i.5) 10.40 ≤ D h- ≤ 10.50 i.6) 12.00 ≤ D i- ≤ 12.15 i.7) 08.00 ≤ D j- ≤ 10.00 i.8) 08.00 ≤ D k- ≤ 10.00 i.9) 08.00 ≤ D l- ≤ 10.00 i.10) 10.40 ≤ D m- ≤ 11.00 i.11) 08.00 ≤ D o- ≤ 10.00 i.12) 08.00 ≤ D p- ≤ 10.00 i.13) 09.00 ≤ D z- ≤ 09.20 i.14) 10.00 ≤ D aa- ≤ 10.15 i.15) 12.00 ≤ D bb- ≤ 12.30 ⇒ 120 ≤ 100 j.1) x3,4 = 1 ⇒ 100 ≤ 100 j.2) x4,5 = 1 ⇒ 100 ≤ 100 j.3) x2,6 = 1 ⇒ 50 ≤ 100 j.4) x6,3 = 1 j.5) x3,5 = 1 ⇒ 10 ≤ 100 j.6) x5,2 = 1 ⇒ 0 ≤ 100 j.7) x2,7= 1 ⇒ 0 ≤ 100 j.8) x7,9 = 1 ⇒ 30 ≤ 100 j.9) x9,8 = 1 ⇒ 50 ≤ 100 j.10) x8,2 = 1 ⇒ 70 ≤ 100 j.11) x9,10 = 1 ⇒ 30 ≤ 100 j.12) x10,8 = 1 ⇒ 60 ≤ 100 j.13) x2,12 = 1 ⇒ 70 ≤ 100
⇒ 40 ≤ 100 j.14) x12,11 = 1 ⇒ 5 ≤ 100 j.15) x11,2= 1 k) x3,4, x 4,5, x2,6 , x6,3, x3,5, x5,2, x 2,7, x11,2,
x9,8, x8,2, x 9,10, x10,8, x2,12, x 12,11, x7,9 ∈ {0 ,1} . Keoptimalan solusi RMP0 untuk masalah keseluruhan dapat diperiksa dengan menyelesaikan P1 dan P2 . Fungsi objektif P1 dapat dituliskan menjadi: minimumkan –230 x1,3 + 90 x3,4 + 70 x4,5 + 40 x5,6 + 30 x 6,1 + 80x3,5 + 90 x9,8 – 480 x1,9 + 90x 9,10 + 110x10,8 + 140x8,7 + 140 x7,1 – 190x1,14 + 90x14,16 + 100 x16,1 – 170 x 1,13 + 50 x13,14 + 70 x14,15 +50 x15,1. Dengan menggunakan LINDO 6.1, rute kendaraan yang memiliki biaya tereduksi terkecil adalah rute 1-9-8-7-1, yakni sebesar – 110 (lihat Lampiran 4). Rute tersebut berpadanan dengan kolom x13 . Fungsi objektif P2 dapat dituliskan menjadi: minimumkan 60 x 3,4 +50x4,5+–180x2,6 + 70 x6,3 + 70 x 3,5 + 40 x 5,2 – 250 x 2,7 + 60 x7,9+ 90x9,8 + 100x8,2 + 40x9,10 + 40x10,8 – 50x2,12 + 100x12,11 +150 x11,12. Dengan menggunakan LINDO 6.1, rute kendaraan Tipe 2 yang memiliki biaya tereduksi terkecil adalah rute 2-7-9-10-8-2, yakni sebesar –10 (lihat Lampiran 4). Kolom yang berpadanan dengan rute 2-7-9-10-8-2 adalah x 32 . Dari P1 dan P2 , rute yang memiliki biaya tereduksi terkecil adalah rute 1-9-8-7-1 yang berpadanan dengan kolom x13 . Kolom tersebut ditambahkan ke dalam RMP0 yang kemudian menjadi RMP1, sehingga variabel yang digunakan pada RMP1 adalah x11 , x 12 ,
x14 , x16 , x12 , x 22 , x 24 dan x13 . Secara ringkas hasil setiap iterasi pada teknik pembangkitan kolom dapat dilihat pada Tabel 4. Pada RMP1 terdapat dua rute yang memiliki biaya tereduksi terkecil (lihat Lampiran 5). Rute-rute tersebut berpadanan dengan kolom x15 dan x32 . Kedua kolom tersebut kemudian ditambahkan ke RMP1 yang kemudian menjadi RMP2, sehingga variabel yang digunakan pada RMP2 adalah x11 , x 12 ,
x13 , x14 , x15 , x16 , x12 , x 22 , x32 dan x 24 . Solusi yang dihasilkan pada RMP2 merupakan solusi yang optimal bagi MP. Hal ini terlihat dari nilai biaya tereduksi untuk masalah P1 dan P 2 adalah taknegatif, sehingga solusi optimal bagi MP adalah x11 = x13 = x14 =
29
x16 = x12 = x32 = x 24 = 1 dan x12 = x15 = x22 = 0 (lihat Lampiran 6). Perusahaan dapat menggunakan rute R1,1, R 1,3 , R1,4, R1,6, R2,1 ,
R2,3 dan R 2,4 untuk permintaan transportasi minimum.
memenuhi semua dengan biaya yang
__________________________________________________________________ Tabel 4. Hasil setiap iterasi menggunakan teknik pembagkitan kolom
RMP
Variabel yang Digunakan
Solusi Optimum
Biaya Perjalanan
P1
0
x11 , x 12 , x 14 , x 16
x11 = x12 = x14 = x16 = x12 = x 22 = x 24 =1
2320
-110
x 13
-10
x 32
x11 , x12 , x 13 , x14
x11 = x12 = x14 = x16 = x12 = x 22 = x 24 =1
2320
- 70
x 15
- 70
x32
x 16 , x 12 , x 22 , x 42
x 13 = 0
x11 , x12 , x13 , x14 x15 ,
x11 = x13 = x14 = x16 = x12 = x32 = x 24 =1
2200
0
-
0
-
x16 , x12 , x 22 x32 , x 24
x12 = x15 = x22 = 0
Biaya tereduksi Terkecil Kolom P2 Kolom
x12 , x22 , x 24 1
2
VI SIMPULAN Dalam suatu graf, masalah pengambilan dan pengiriman dengan kendala waktu (PDPTW) dapat dipandang sebagai masalah mencari rute-rute fisibel yang mengoptimalkan biaya dan melewati setiap sisi sebanyak satu kali. Sisi tersebut melambangkan suatu permintaan transportasi yang didefinisikan sebagai permintaan pengiriman barang yang harus dibawa secara langsung oleh kendaraan dari tempat asal ke tempat tujuan. Dalam permintaan transportasi terdapat kendala waktu dan kendala kapasitas kendaraan. Kendaraan tersebut berangkat dan pulang ke suatu depot sesuai waktu yang tersedia. Rute kendaraan yang fisibel adalah rute yang memenuhi semua kendala yang ada dalam PDPTW. Masalah untuk memilih sejumlah rute fisibel yang memenuhi semua permintaan transportasi dapat dimodelkan dalam bentuk masalah pemartisian himpunan. Pada masalah pemartisian himpunan rute fisibel PDPTW dinyatakan sebagai kolom dari matriks kendala. Penyelesaian masalah pemartisian himpunan dalam skala yang besar dapat menggunakan teknik pembangkitan kolom. Teknik pembangkitan kolom merupakan teknik untuk menyelesaikan suatu
pemrograman linear dengan menggunakan sebagian variabel. Masalah pemrograman linear dengan sebagian variabel diselesaikan dengan menggunakan metode simpleks yang akan menghasilkan variabel dual. Variabel dual tersebut digunakan untuk menghitung biaya tereduksi pada masalah keseluruhan. Masalah pencarian nilai biaya tereduksi terkecil untuk masalah keseluruhan disebut sebagai pricing problem. Variabel yang memiliki biaya tereduksi negatif ditambahkan pada masalah sebelummya dan kemudian diselesaikan kembali dengan menggunakan metode simpleks. Proses ini terus berulang hingga tidak ada lagi variabel dalam masalah keseluruhan yang memiliki biaya tereduksi negatif, sehingga solusi yang dihasilkan pada masalah sebagian variabel merupakan solusi optimal untuk masalah keseluruhan. Teknik pembangkitan kolom akan menghasilkan rute fisibel PDPTW dengan biaya yang minimum. Pada contoh kasus terlihat bagaimana menyelesaikan masalah PDPTW dalam bentuk masalah pemartisian himpunan dengan menggunakan teknik pembangkitan kolom. Variabel yang digunakan pada iterasi terakhir adalah variabel pada masalah keseluruhan yang berarti masalah tersebut akhirnya
30
diselesaikan dengan menggunakan seluruh variab el yang ada, sehingga teknik pembangkitan kolom terlihat kurang efisien. Dalam kasus lain, teknik pembangkitan kolom
akan membantu untuk menyelesaikan PL pada skala yang besar dengan menggunakan sebagian variabel dari masalah keseluruhan.
DAFTAR PUSTAKA Bruggen, L.J.J. van der., J.K. Lenstra & P.C. Schuur. 1993. Variable-depth search for the s ingle-vehicle p ickup and delivery problem with time windows. Operations Research Society of America, 3: 298-311. Dumas, Y., J. Desrosiers & F. Soumis. 1991. The pickup and delivery problem with time windows. European Journal of Operational Research , 54: 7-22. Foulds, L.R. 1992. Graph Theory Applications. Springger-Verlag, New York. Garfinkel, R.S. & G.L. Nemhauser. 1972. Integer Programmining. John Wiley & Sons, New York. Hillier, F.S. & G.J. Lieberman. 1990. Introduction to Mathematical Programming. McGraw-Hill, New York.
Mitrovi c-Minic, S . 1998. Pickup and Delivery Problem with Time Windows: A Survey. Simon Fraser University CMPT TR 1998-12. ftp://fas.sfu.ca/pub/cs/techreports/1998. Nash, S.G. & A. Sofer. 1996. Linear and Nonlinear Programming. McGraw -Hill. New York. Sol, M. & M. W. P. Savelsbergh. 1994. A Branch-and-Price Algorithm for the Pickup and Delivery Problem with Time Windows. http://www.isye.gatech.edu/research/files /lec9406.pdf. [29 Juli 2005]. Sol, M. & M. W. P. Savelsbergh. 1995. The General Pickup and Delivery Problem.http://www.isye.gatech.edu/~m wps/publications/ts29.pdf.[29 Juli 2005]. Winston, W.L. 1995. Introduction to Mathematical Programming 2nd ed. Duxbury, New York.
31
LAMPIRAN
32
Lampiran 1 Contoh penyelesaian suatu PL dengan menggunakan algoritme simpleks Dari PL pada − 2 1 1 A = −1 2 0 1 0 0
Contoh 4. diketahui bahwa 0 0 2 dan 1 0 , b = 7 3 0 1
c = (−1 − 2 0 0 0 ) . T
Iterasi 1 Misalkan dipilih sebagai basis adalah
x B = (x3
x5 )
T
x4
dan
x N = (x1
x2 )T ,
B = I = B − 1 , c B T = (0 0 0),
−2 1 c N = (− 1 − 2 ) dan N = −1 2 . 1 0 −1 ˆ Nilai dari x B = b = B b = (2 7 3)T . Dengan basis ini nilai pengali simpleks y T = c TB B −1 = (0 0 0) dan nilai biaya tereduksi adalah T T cˆ N = c N − yT N = (− 1 − 2) . Keduanya bernilai negatif sehingga basis ini belum optimal. T
(
)
Nilai ( cˆ N T ) 2 , yaitu nilai elemen baris
−2 1 N = −1 0 . 1 0
Nilai dari x B = bˆ = B −1 b = (2 3 3)T . Dengan basis ini nilai pengali simpleks yT = cTB B−1 = (−2 0 0 ) dan nilai biaya tereduksi adalah cˆ N T = c N T − y T N = (− 5 2 ) .
(
Iterasi 3 Pada iterasi ini,
T
kedua dari cˆ N , memiliki nilai negatif yang lebih besar, maka pilih x2 (variabel nonbasis kedua) sebagai variabel-masuk . Untuk uji 1 −1 ˆ nisbah, hitung A2 = B A2 = 2 , 0 maka perbandingannya: bˆ / aˆ = 2 dan bˆ / aˆ = 7 . 1
1,2
2
3
2 ,2
2
Perbandingan pertama bernilai lebih kecil, maka x3 (variabel basis pertama) merupakan variabel yang akan meninggalkan basis (variabel -keluar). Iterasi 2 Pada iterasi ini, x 2 menggantikan x3 dalam basis, sehingga
x B = (x 2
x4 x5 ) , x N = (x1 x3 ) , 1 0 0 1 0 0 −1 B = 2 1 0 , B = − 2 1 0 , 0 0 1 0 0 1 T
T
c B T = (− 2 0 0 ), c N T = (− 1 0 ) dan
)
Biaya tereduksi pertama bernilai negatif sehingga basis ini belum optimal. pilih x1 (variabel nonbasis pertama) sebagai variabelmasuk. Kolom yang berpadanan dengan − 2 −1 ˆ variabel-masuk adalah A1 = B A1 = 3 . 1 Dari uji nisbah minimum, yaitu hasil dari bˆ bˆ min 2 = 1, 3 = 3, variabel x4 (variabel aˆ 3,1 aˆ 2,1 basis kedua) merupakan variabel yang akan meninggalkan basis (variabel-keluar).
x N = (x3
B −1
x4 )
T
− 1 3 = − 23 2 3
x B = (x 2
x5 )T ,
x1
1 − 2 0 , B = 2 − 1 0 , 0 1 1 2 3 1 3 − 13
c B T = (− 2 − 1 0),
0 0 , 1
c N T = (0 0 )
dan
1 0 N = 0 1 . Dapat diperoleh nilai dari 0 0 T ˆ x B = b = B −1 b = (4 1 2) . Dengan basis y T = c TB B −1 =
ini nilai pengali simpleks
( 43
)
− 53 0 dan nilai biaya tereduksi adalah
(
) (
cˆ N = c N − y T N = − 43 T
T
5 3
).
Biaya tereduksi pertama bernilai negatif sehingga basis ini belum optimal.
pilih x3
(variabel nonbasis pertama) sebagai variabel-
33
masuk. Kolom yang berpadanan dengan
B −1
− 1 3 variabel-masuk adalah Aˆ 3 = B −1 A3 = − 23 . 2 3 Calon untuk uji nisbah minimum hanya ada satu yaitu bˆ3 / aˆ 3,1 = 3 , sehingga variabel x 3 merupakan variabel yang akan meninggalkan basis. Iterasi 4
Pada iterasi ini, x B = (x2
x N = (x4
x5 )
T
1 2
1 , cB T 3 2 0 = (0 0 ) dan N = 1 0
1 − 2 1 , B = 2 − 1 0 , 0 1 0
Hasil dengan menggunakan LINDO 6.1 6
OBJECTIVE FUNCTION VALUE 1)
152.0000
VARIABLE X1 X2 X3 X4 X5 ROW 1) 2) 3) 4) 5) 6)
VALUE 1.000000 1.000000 0.000000 1.000000 0.000000 SLACK OR SURPLUS 1.000000 2.000000 0.000000 0.000000 0.000000 0.000000
NO. ITERATIONS=
6
0 0 . Nilai dari 1
T
Lampiran 2 Hasil perhitungan Contoh 5 menggunakan LINDO 6.1 Masalah Primal: min 51 x1 + 27 x2 + 93 x3 + 74 x4 + 55 x5 subject to 1) x1 + x2 >= 1 2) x1 + x2 + x3 + x4 >= 1 3) x1 + x5 >= 1 4) x2 + x3 >= 1 5) x3 + x4 + x5 >= 1 6) x4 >= 1 End
NO. ITERATIONS= 3 LP OPTIMUM FOUND AT STEP
= (− 2 − 1 0),
x B = bˆ = B −1 b = (5 3 3 ) . Dengan basis ini nilai pengali simpleks y T = c TB B −1 = (0 −1 − 2 ) dan nilai biaya tereduksi adalah T T cˆ N = c N − y T N = (1 2 ) . Nilai biaya tereduksi dengan menggunakan basis ini bernilai positif. Hal ini berarti basis telah optimal. Solusi optimal untuk Contoh 4 adalah x 1= 3, x 2 = 5, x3 = 3, x 4 = x5 = 0 dengan z = –13.
(
T x3 ) dan
x1
cN
T
0 1 2 =0 0 1 1 − 2
REDUCED COST 0.000000 0.000000 62.000000 0.000000 0.000000 DUAL PRICES 0.000000 0.000000 -51.000000 -27.000000 -4.000000 -70.000000
)
34
Masalah Dual: Max y1 + y2 + Subject to 1) y1 + y2 2) y1 + y2 3) y2 + y4 4) y2 + y5 5) y3 + y5 End
y3 + y4 + y5 + y6 + y3 <= + y4 <= + y5 <= + y6 <= <= 55
51 27 93 74
LP OPTIMUM FOUND AT STEP
3
OBJECTIVE FUNCTION VALUE 1)
152.0000
VARIABLE Y1 Y2 Y3 Y4 Y5 Y6
ROW 1) 2) 3) 4) 5)
VALUE 0.000000 0.000000 51.000000 27.000000 0.000000 74.000000
SLACK OR SURPLUS 0.000000 0.000000 66.000000 0.000000 4.000000
NO. ITERATIONS=
REDUCED COST 1.000000 2.000000 0.000000 0.000000 0.000000 0.000000
DUAL PRICES 1.000000 1.000000 0.000000 1.000000 0.000000
3
Lampiran 3 Rute Fisibel PDPTW Terdapat 13 cycle berarah yang dapat dibentuk dari Gambar 6. Cycle tersebut adalah: • 1-3-4-5-6-1 • 1-9-10-8-7-1 • 1-9-8-7-1 • 1-14 -16-1 • 1-14 -15-1 • 1-13-14 -15-1 • 1-3-5-6-1 • 1-13-14-16-1 • 2-6-3-5-2 • 2-7-9-8-2 • 2-7-9-10-8-2 • 2-12-11-2 • 2-6-3-4-5-2 Misal didefinisikan: V1 = S+ ∪ S - ∪ {1} = {1, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16} S1 = {a, b, c, d, e, h, l, n, o, p, q, r, s, t, u, v, w, x, y}
V2 = S + ∪ S - ∪ {2} = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} S2 = { b, c, f, g, h, i, j, k, l, m, o, p, z, aa, bb}. Ketiga -belas cycle tersebut diperiksa kefisibelannya menggunakan Definisi 13. Operasi penjumlahan dalam syarat kelima pada Definisi 13 merupakan penjumlahan antara waktu keberangkatan dengan lama perjalanan dalam satuan menit. Cycle 1-3-4-5-6-1 Ambil {1,3,4,5,6} ⊆ V1. Cycle 1-3-4-56-1 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 1-3-4-5-6-1, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.15. Kendaraan dapat berangkat dari Depot 1 pada pukul 7.00, sehingga batas waktu pengambilan tidak mendahului
35
2
3
4 5
waktu pemberangkatan kendaraan pada Depot 1. Setiap i ∈ {a,b,c,d,e,} memenuhi i + ∈ {1,3,4,5,6} jika dan hanya jika i∈{1,3,4,5,6}. Setiap i ∈{a,b,c,d,e,} dan {i+,i -} ⊆ {1,3,4,5,6} , berlaku i+ dikunjungi terlebih dahulu dari pada i-. Tempat 3, 4, 5 dan 6 dikunjungi tepat 1 kali. Tempat 3, 4, 5 dan 6 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = a , ∃Da1 + = 7.00 ∈ [ 7.00, 7.15]
∧ D1a − = 7.45 ∈ [7.45, 8 .00] ? 7. 00 + 40 ≤ 7 .45 ?
∋
x11, 3 = x 13,4 = 1 ⇒ D1a − ≤ Db1 +
⇒ 7.45 ≤ D1b + Untuk i = b , ∃Db1+ = 8 .00 ∈ [8.00, 8. 10]
∧ D1b − = 9.00 ∈ [9 .00, 9.15 ] ? ? ?
∋
= = 1 ⇒ 7.45 ≤ 8.00 8.00 + 60 ≤ 9.00 x 13, 4 = x 14 ,5 = 1 ⇒ D1 − ≤ Dc1 + x11,3
x13, 4
b
⇒ 9.00 ≤ D1c + Untuk i = c , ∃Dc1 + = 9.20 ∈ [9.20, 9.30]
∧ D1c − = 9.50 ∈ [9.40, 10.00] ∋
? x 13,4 = x 14 ,5 = 1 ⇒ 9.00 ≤ 9.20 ? 9.20 + 30 ≤ 9.50 ? x14, 5 = x15 ,6 = 1 ⇒ D1c − ≤ Dd1 +
⇒ 9.50 ≤ D1d + Untuk i = d , ∃ Dd1 + = 9.50 ∈ [9.50, 10.00]
∧ D1d − = 10.30 ∈ [10.30, 10.45] ∋ ?
x14, 5
=
x15 ,6
= 1 ⇒ 9.50 ≤ 9.50
? 9.50 + 30 ≤ 10.30 ? x 15,6 = x 16 ,1 = 1 ⇒ D1d
−
≤ De1 +
⇒ 10.30 ≤ D1e + Untuk i = e , ∃ De1 + = 10.50 ∈ [10.50,11.00] ∧ D1e − = 11.20 ∈ [11.20, 11.35] ∋
6
? x 14, 5 = x 15 ,6 = 1 ⇒ 10.30 ≤ 10.50 ? 10.30 + 25 ≤ 11.20 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 140 unit,
karena kuantitas maksimum pada TR i ∈ {a,b,c,d,e,} adalah sebesar 140 unit. 7 Rute kendaraan cycle 1-3-4-5-6-1 berhenti di Depot 1 pada pukul 11.20. Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 1. Akibatnya cycle 1-3-4-5-6-1 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R1,1. Cycle 1-9-10-8-7-1 Ambil {1,7,8,9,10} ⊆ V1. Cycle 1-9-108-7-1 memenuhi ketujuh syarat dalam definisi rut e fisibel PDPTW. 1 Dalam cycle 1-9-10-8-7-1, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.15. Kendaraan dapat berangkat dari Depot 1 pada pukul 7.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 1. 2 Setiap i ∈ {n,o,p,q,r} memenuhi i + ∈ {1,7,8,9,10} jika dan hanya jika i– ∈ {1,7,8,9,10}. 3 Setiap i ∈ {n,o,p,q,r} dan {i+ ,i-} ⊆ {1,7,8,9,10}, berlaku i + dikunjungi – terlebih dahulu dari pada i . 4 Tempat 7, 8, 9 dan 10 dikunjungi tepat 1 kali. 5 Tempat 7, 8, 9 dan 10 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = n , ∃ D1n + = 7.00 ∈ [7.00,7.15]
∧ D1n − = 8.00 ∈ [8.00,10.00] ∋ ? 7.00 + 30 ≤ 8.00 ? x 11,9 = x 19,10 = 1 ⇒ D 1n − ≤ D1o +
⇒ 8.00 ≤ D1o + Untuk i = o , ∃ D1o + = 8.00 ∈ [8.00,10.00]
∧ D1o − = 8.30 ∈ [8.00,10.00]
∋
? = 1 ⇒ 8.00 ≤ 8.00 ? 8.00 + 30 ≤ 8.30 1 1 1 ? x19,10 = x10 ,8 = 1 ⇒ Do − ≤ D p + x11, 9
x 19,10 =
⇒ 8.30 ≤ D1p + Untuk i = p , ∃ D1p + = 8.30 ∈ [8.00,10.00]
∧ D1p − = 9.00 ∈ [8.00,10.00]
∋
1 ? x 19 ,10 = x10 ⇒ 8.30 ≤ 8.30 ,8 =1 ? 8.30 + 30 ≤ 9.00
36
?
1 1 x10 ,8 = x 8 ,7 =1
⇒ D1p − ≤ D 1q +
? 7.00 + 30 ≤ 8.00
⇒ 9.00 ≤ D1q +
?
Untuk i = q , ∃ D 1q + = 9.00 ∈ [8.00,10.00]
∧ D1q − = 9.30∈ [8.00,10.00] ∋ 1 1 ? x10 ,8 = x 8,7 =1
⇒ 9.00 ≤ 9.00
? 9.00 + 30 ≤ 9.30 ?
x 18,7 = x 17 ,1 =1
⇒ D1q − ≤ D1r + ⇒ 9.30 ≤ D1r +
Untuk i = r , ∃ D 1r + = 10.10∈ [10.00,10.10]
∧
D1r −
= 10.40 ∈ [10.40,11.00] ∋
⇒ 9.30 ≤ 10.10 ? 10.10+ 30 ≤ 10.40 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 140 unit, karena kuantitas maksimum pada TR i ∈ {n,o,p,q,r} adalah sebesar 110 unit. 7 Rute kendaraan cycle 1-9-10-8-7-1 berhenti di Depot 1 pada pukul 10.40. Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu t iba kendaraan pada Depot 1. Akibatnya cycle 1-9-10-8-7-1 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R1,2. ? x18,7 = x17 ,1 =1
Cycle 1-9-8-7-1 Ambil {1,7,8,9} ⊆ V1. Cycle 1-9-8-7-1 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 1-9-8-7-1, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.15. Kendaraan dapat berangkat dari Depot 1 pada pukul 7.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 1. 2 Untuk i ∈ {n,l,q,r} memenuhi i + ∈ {1,7,8,9} jika dan hanya jika i– ∈ {1,7,8,9} . 3 Setiap i ∈ {n,l,q,r}dan {i + ,i- } ⊆ {1,7,8,9}, berlaku i + dikunjungi terlebih dahulu dari pada i–. 4 Tempat 7, 8 dan 9 dikunjungi tepat 1 kali. 5 Tempat 7, 8 dan 9 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = n , ∃ D 1n + = 7.00 ∈ [7.00,7.15]
∧ D1n − = 8.00∈ [8.00,10.00] ∋
x 11,9 =
x19,8 = 1 ⇒ D1n − ≤ D1l + ⇒ 8.00 ≤ D1l +
Untuk i = l , ∃ D1l + = 8.00 ∈ [8.00,10.00]
∧ D1l − = 8.30 ∈ [8.00,10.00] ∋
? x11, 9 = x19 ,8 = 1 ⇒ 8.00 ≤ 8.00 ? 8.00 + 30 ≤ 8.30 ? x 19 ,8 = x 18,7 = 1 ⇒ Dl1 − ≤ D1q +
⇒ 8.30 ≤ D1q + Untuk i = q , ∃ D1q + = 9.00 ∈ [8.00,10.00]
∧ D1q − = 9.30 ∈ [8.00,10.00]
∋
? x 19 ,8 = x 18 ,7 = 1 ⇒ 8.30 ≤ 9.00 ? 9.00 + 30 ≤ 9.30 ? x18 ,7 = x17 ,1 = 1 ⇒ D 1q − ≤ D1r +
⇒ 9.30 ≤ D1r + Untuk i = r , ∃ D1r + = 10.10 ∈ [10.00,10.10]
∧ D1r − = 10.40 ∈ [10.40,11.00] ∋
⇒ 9.30 ≤ 10.10 ? 10.10+ 30 ≤ 10.40 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 140 unit , karena kuantitas maksimum pada TR i ∈ {n,l,q,r} adalah sebesar 110 unit. 7 Rute kendaraan cycle 1-9-8-7-1 berhenti pada Depot 1 pukul 10.40. Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 1. Akibatnya cycle 1-9-8-7-1 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R1,3. ? x18 ,7 = x17 ,1 = 1
Cycle 1-14-16-1 Ambil {1,14,16} ⊆ V1. Cycle d memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 1-14-16-1, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.15. Kendaraan dapat berangkat dari Depot 1 pada pukul 7.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 1. 2 Untuk i ∈{s,t,u} memenuhi i +∈ {1,14,16} jika dan hanya jika i– ∈{1,14,16}.
37
3
4 5
Setiap i ∈ {s,t,u} dan {i +, i –} ⊆ {1,14,16}, berlaku i + dikunjungi terlebih dahulu dari pada i–. Tempat 14 dan 16 dikunjungi tepat 1 kali. Tempat 14 dan 16 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = s , ∃ D 1s + = 7.00 ∈ [7.00, 7.15]
∧ D1s − = 7.40∈ [7.40,8.00] ∋ ? 7.00 + 40 ≤ 7.40 1 1 1 ? x11,14 = x14 ,16 = 1 ⇒ Ds − ≤ Dt +
⇒ 7.40 ≤ D1t + Untuk i = t , ∃ D1t + = 9.00 ∈ [9.00, 9.10]
∧ D1t − = 10.00 ∈ [10.00,10.10] ∋
1 ⇒ 7.40 ≤ 10.00 ? x11,14 = x14 ,16 =1 ? 9.00 + 60 ≤ 10.00
?
1 1 x14 ,16 = x16,1 =1
⇒ ⇒
Untuk i = u , ∃
Du1 +
≤ Du1 + 10.00 ≤ D1u +
D1t −
= 10.10∈ [10.10,10.15]
∧ D1u − = 10.50 ∈ [10.40, 11.00] ∋ ?
1 x14 ,16
=
1 x16 ,1
= 1 ⇒ 10.00 ≤ 10.10
? 10.10 + 40 ≤ 10.50 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 140 unit, karena kuantitas maksimum pada TR i ∈ {s,t,u} adalah sebesar 110 unit. 7 Rute kendaraan cycle 1-14-16-1 berhenti di Depot 1 pada pukul 10.50 . Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 1. Akibatnya cycle 1-14-16-1 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R1,4. 6
Cycle 1-14-15-1 Ambil {1,14,15} ⊆ V1. Cycle 1-14-15-1 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 1-14-15-1, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.15. Kendaraan dapat berangkat dari Depot 1 pada pukul 7.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 1. 2 Untuk i ∈ {s,x,y} memenuhi i + ∈ {1,14,15} jika dan hanya jika i − ∈{1,14,15}.
3
4 5
Setiap i ∈ {s,x,y} dan {i +, i − } ⊆ {1,14,15}, berlaku i + dikunjungi terlebih dahulu dari pada i − . Tempat 14 dan 15 dikunjungi tepat 1 kali. Tempat 14 dan 15 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = s , ∃ D1s + = 7.00∈ [7.00, 7.15]
∧ D1s − = 7.40 ∈ [7.40, 8.00] ∋ ? 7.00 + 40 ≤ 7.40 1 1 1 ? x11,14 = x14 ,15 = 1 ⇒ D s − ≤ Dx +
⇒ 7.40 ≤ D1x + Untuk i = x , ∃ D1x + = 10.30 ∈ [10.30,10.35]
∧ D1x − = 11.00 ∈ [11.00,11.05] ∋
1 ? x 11,14 = x14 ⇒ 7.40 ≤ 10.30 ,15 =1 ? 10.30+ 25 ≤ 11.00 1 1 1 1 ? x14 ,15 = x15,1 =1 ⇒ D x − ≤ D y +
⇒ 11.00 ≤ D1y + Untuk i = y , ∃ D1y + =11.00 ∈ [11.00,11.05]
∧ D1y − = 11.50 ∈ [11.50, 12.00] ∋ 1 ? x 11,14 = x14 ⇒ 11.00 ≤ 11.00 ,15 =1 ? 11.00 + 40 ≤ 11.50 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 140 unit, karena kuantitas maksimum pada TR i ∈ {s,x,y} adalah sebesar 110 unit. 7 Rute kendaraan cycle 1-14-15-1 berhenti di Depot 1 pada pukul 11.50. Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 1. Akibatnya cycle 1-14-15-1 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R1,5.
Cycle 1-13-14 -15-1 Ambil {1,13,14,15} ⊆ V1 . Cycle f memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 1-13-14-15-1, kendaraan berangkat dari Depot 1 antara pukul 7.00 – 7.15. Kendaraan dapat berangkat dari Depot 1 pada pukul 7.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 1.
38
2
3
4 5
Setiap i ∈ {v,w ,x,y} memenuhi i + ∈ {1,13,14,15} jika dan hanya jika i − ∈ {1,13,14,15}. Setiap i ∈ {v,w,x,y} dan {i+ , i − } ⊆ {1,13,14,15}, berlaku i + dikunjungi terlebih dahulu dari pada i − . Tempat {1,13,14,15} dikunjungi tepat 1 kali. Tempat {1,13,14,15} dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = v , ∃ Dv1 + = 7.00∈ [7.00, 7.15]
∧ D1v − = 8.00∈ [8.00,8.15] ? 7.00 + 30 ≤ 8.00 ?
x 11,13
∋
⇒ 8.00 ≤ Untuk i = w , ∃
∧
D1w −
D1w +
= 8.40∈ [8.40, 9.00]
= 10.00 ∈ [10.00, 10.20] ∋
1 = x13 ,14 = 1 ⇒ 8.00 ≤ 8.40 ? 8.40+ 75 ≤ 10.00 1 1 1 1 ? x13 ,14 = x14,15 =1 ⇒ Dw − ≤ Dx +
?
x 11,13
⇒ 10.00 ≤ D1x + Untuk i = x , ∃ D 1x + = 10.30 ∈ [10.30,10.35]
∧ D1x − = 11.00 ∈ [11.00,11.05] ∋
1 ? x11,14 = x14 ,15 = 1 ⇒ 10.00 ≤ 10.30 ? 10.30+ 25 ≤ 11.00
?
1 1 x14 ,15 = x15,1
= 1⇒
D1x
dan d. Tidak ada D 1h − ∈ [10.40, 10.50] yang memenuhi
−
≤
⇒ 11.00 ≤
D 1y
Untuk i = y , ∃ D 1y + = 11.00 ∈ [11.00,11.15]
∧ D1y − = 11.50 ∈ [11.50,12.00] ∋ 1 1 ? x14 ,15 = x 15,1 = 1 ⇒ 11.00 ≤ 11.00 ? 11.00 + 40 ≤ 11.50 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 140 unit, karena kuantitas maksimum pada TR i ∈ {v,w,x,y} adalah sebesar 100 unit. 7 Rute kendaraan cycle 1-13-14-15-1 berhenti pada Depot 1 pukul 11.50. Batas waktu maksimum kedatangan kendaraan pada Depot 1 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 1. Akibatnya cycle 1-13-14-15-1 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R1,6.
dengan
Dd1 + ∈
Cycle 1-13-14-16-1 Cycle 1-13-14-16-1 bukan merupakan rute fisibel PDPTW karena tidak terpenuhinya Syarat 5 dalam Definisi 13. Perhatikan TR w dan t. Tidak ada D1w − ∈ [10.00, 10.20] yang
D1w − ≤ D1t + ,
dengan
Dt1 + ∈
[9.00, 9.10]. Cycle 2-6-3-5-2 Ambil {2,3,5,6} ⊆ V2. Cycle 2-6-3-5-2 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 2-6-3-5-2, kendaraan berangkat dari Depot 2 antara pukul 8.00 – 8.15. Kendaraan dapat berangkat dari Depot 2 pada pukul 8.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 2. 2 Untuk i ∈ {f,g,h,i} memenuhi i + ∈ {2,3,5,6} jika dan hanya jika i − ∈ {2,3,5,6}. 3
+
D1y +
D1h − ≤ D1d + ,
[9.50,10.10].
memenuhi
1 1 1 = x13 ,14 = 1 ⇒ Dv − ≤ D w +
D1w +
Cycle 1-3-5-6-1 Cycle 1-3-5-6-1 buk an merupakan rute fisibel PDPTW, karena tidak terpenuhinya Syarat 5 dalam Definisi 13. Perhatikan TR h
4 5
Setiap i ∈ {f,g,h,i} dan {i+ , i − } ⊆ + {2,3,5,6} berlaku i dikunjungi terlebih dahulu dari pada i − . Tempat 3, 5 dan 6 dikunjungi tepat 1 kali. Tempat 3, 5 dan 6 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = f , ∃ D 2f + = 8.00 ∈ [8.00, 8.15]
∧ D 2f − = 9.10 ∈ [9.10, 9.15] ∋ ? 8.00+ 60 ≤ 9.10 ⇒ D 2f − ≤ Dg2 + ? x 22,6 = x 62,3 =1
⇒ 9.10 ≤ Dg2 + Untuk i = g , ∃ Dg2 + = 9.15 ∈ [9.15, 9.20]
∧ Dg2 − = 10.00 ∈ [9.40, 10.00] ∋ x22,6 = x62,3 =1 ⇒ 9.10 ≤ 9.15 ? 9.15 + 25 ≤ 10.00 ? x 62,3 = x 32,5 =1 ⇒ D g2 − ≤ Dh2 + ?
⇒ 10.00 ≤ Dh2 +
39
Untuk i = h , ∃ Dh2 + = 10.10 ∈ [10.10,10.20]
?
∧ Dh2 − = 10.40 ∈ [10.40, 10. 50] ∋
⇒ 8.00 ≤ Dk2 +
? x62, 3 = x32,5 = 1 ⇒ 10.00 ≤ 10.10 ? 10.10+ 30 ≤ 10.40 ?
x 32,5
=
x 52,2
=1
⇒
Dh2
−
≤
⇒ 10.40 ≤
Di2
+
Di2 +
∧ Di2 − = 12.00 ∈ [12.00,12.15] ∋
? x 32,5 = x 52, 2 =1 ⇒ 10.40 ≤ 11.00 ? 11.00 + 60 ≤ 12.00 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 100 unit, karena kuantitas maksimum pada TR i ∈ {f,g,h,i} adalah sebesar 100 unit. 7 Rute kendaraan cycle 2-6-3-5-2 berhenti pada Depot 2 pukul 12.00. Batas waktu maksimum kedatangan kendaraan pada Depot 2 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 2. Akibatnya cycle 2-6-3-5-2 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R2,1. Cycle 2-7-9-8-2 Ambil {2,7,8,9} ⊆ V2. Cycle 2-7-9-8-2 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 2-7-9-8-2, kendaraan berangkat dari Depot 2 antara pukul 7.30 – 7.40. Kendaraan dapat berangkat dari Depot 2 pada pukul 7.30, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 2. 2 Untuk i ∈ {j,k,l,m} memenuhi i + ∈ {2,7,8,9} jika dan hanya jika i − ∈ {2,7,8,9} . 3 Setiap i ∈ {j,k,l,m} dan {i +, i − } ⊆ + V2′, 2 berlaku i dikunjungi terlebih dahulu
5
dari pada i − . Tempat 7, 8 dan 9 dikunjungi tepat 1 kali. Tempat 7, 8 dan 9 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = j , ∃ D 2j + = 7.30 ∈ [7.30, 7.40]
∧ D 2j − = 8.00∈ [8.00, 10.00] ∋ ? 7.30+ 30 ≤ 8.00
Untuk i = k , ∃ Dk2 + = 8.00 ∈ [8.00, 10.00]
∧ Dk2 − = 8.30 ∈ [8.00, 10.00] ∋
Untuk i = i , ∃ Di2 + = 11.00 ∈ [11.00, 11.15]
4
x22,7 = x72, 9 = 1 ⇒ D 2j − ≤ Dk2 +
x22,7 = x72,9 =1 ⇒ 8.00 ≤ 8.00 ? 8.00+ 30 ≤ 8.30 2 ? x 72,9 = x9,8 = 1 ⇒ Dk2 − ≤ Dl2 + ?
⇒ 8.30 ≤ Dl2 + Untuk i = l , ∃ Dl2 + = 8.30 ∈ [8.00, 10.00]
∧ Dl2 − = 9.00 ∈ [8.00, 10.00] ∋
2 ? x 72,9 = x9,8 = 1 ⇒ 8.30 ≤ 8.30 ? 8.30+ 30 ≤ 9.00
?
2
x9,8 = x82,2 = 1 ⇒ Dl2 − ≤ Dm2 + ⇒ 9.00 ≤ Dm2 +
Untuk i = m , ∃ D m2 + = 10.00 ∈ [10.00,10.10]
∧ Dm2 − = 11.00 ∈ [10.40,11.00] ?
x92,8
=
x 82,2
∋
= 1 ⇒ 9.00 ≤ 10.00
? 10.00 + 55 ≤ 11.00 6 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 100 unit, karena kuantitas maksimum pada TR i ∈{j,k,l,m } adalah sebesar 70 unit. 7 Rute kendaraan cycle 2-7-9-8-2 berhenti di Depot 2 pukul pada 11.00. Batas waktu maksimum kedatangan kendaraan pada Depot 2 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 2. Akibatnya cycle 2-7-9-8-2 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R2,2. Cycle 2-7-9-10-8-2 Ambil {2,7,8,9,10} ⊆ V2. Cycle 2-7-9-108-2 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 2-7-9-10-8-2, kendaraan berangkat dari Depot 2 antara pukul 7.30 – 7.40. Kendaraan dapat berangkat dari Depot 2 pada pukul 7.30, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 2. 2 Untuk i ∈ {j,k,o,p,m } memenuhi i + ∈ {2,7,8,9,10} jika dan hanya jika − i ∈ {2,7,8,9,10}.
40
3
4 5
Setiap i ∈ {j,k,o,p,m} dan {i + , i − } ⊆ {2,7,8,9,10} berlaku i + dikunjungi − terlebih dahulu dari pada i . Tempat 2, 7, 8, 9 dan 10 dikunjungi tepat 1 kali. Tempat 2, 7, 8, 9 dan 10 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = j , ∃ D 2j + = 7.30 ∈ [7.30, 7.40]
∧ D 2j − = 8.00∈ [8.00, 10.00] ∋ ? 7.30+ 30 ≤ 8.00 ?
x 22, 7 = x 72,9 = 1 ⇒ D 2j − ≤ Dk2 +
⇒ 8.00 ≤ Dk2 + Untuk i = k , ∃ Dk2 + = 8.00∈ [8.00, 10.00]
∧ Dk2 − = 8.30∈ [8.00, 10.00] ∋
= =1 ⇒ 8.00 ≤ 8.00 ? 8.00+ 30 ≤ 8.30 ? x72, 9 = x 92,10 = 1 ⇒ Dk2 − ≤ Do2 + ?
x 22, 7
12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 2. Akibatnya cycle 2-7-9-10-8-2 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R2,3. Cycle 2-12-11-2 Ambil {2,11,12} ⊆ V2. Cycle 2-12-11-2 memenuhi ketujuh syarat dalam definisi rute fisibel PDPTW. 1 Dalam cycle 2-12-11-2, kendaraan berangkat dari Depot 2 antara pukul 8.00 – 8.15. Kendaraan dapat berangkat dari depot l pada pukul 8.00, sehingga batas waktu pengambilan tidak mendahului waktu pemberangkatan kendaraan pada Depot 2. 2 Untuk i ∈ {z,aa,bb } memenuhi i + ∈
x 72, 9
⇒ 8,30 ≤ Do2 + Untuk i = o , ∃ Do2 + = 8.30∈ [8.00,10.00]
∧ Do2 − = 9.00∈ [8.00, 10.00] ∋
3
4 5
⇒ 8.30 ≤ 8.30
? x72, 9 = x 92,10 =1
? 8.30+ 30 ≤ 9.00 2 2 2 ? x 92,10 = x 10 ,8 = 1 ⇒ Do − ≤ D p +
2 ∧ D z − = 9.00∈ [9.00, 9.20] ∋ ? 8.00+ 60 ≤ 9.00 2 2 2 ? x 22,12 = x12 ,11 =1 ⇒ D z − ≤ D aa
⇒ 9.00 ≤ D 2p + Untuk i = p , ∃ D 2p + = 9.00 ∈ [8.00,10.00]
⇒ 9.00 ≤
2 ∧ D p − = 9.30∈ [8.00, 10.00] ∋
Untuk i = aa , ∃
2 ? x 92,10 = x10 , 8 = 1 ⇒ 9.00 ≤ 9.00
∧
? 9.00+ 30 ≤ 9.30 ?
∧ ? 6
7
Dm2 − = 10.40 2 2 x 10 ,8 = x 8 ,2
+
−
+
= 9.20 ∈ [9.20,9.30]
= 10.00 ∈ [10.00, 10.15] ∋
= 10.00 ∈ [10.00,10.10]
⇒ 10.00 ≤
∈ [10.40,11.00] ∋
Untuk i = b, ∃
= 1 ⇒ 9.30 ≤ 10.00
? 10.00+ 35 ≤ 10.40 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 100 unit, karena kuantitas maksimum pada TR i ∈ {j,k,o,p,m} adalah sebesar 70 unit. Rute kendaraan cycle 2-7-9-10-8-2 berhenti pada Depot 2 pukul 10.40. Batas waktu maksimum kedatangan kendaraan pada Depot 2 adalah pukul
+
+
2 x12 ? ,11 =1 ⇒ 9.00 ≤ 9.20 ? 9.20+ 30 ≤ 10.00 2 2 2 2 ? x12 ,11 = x 11, 2 =1 ⇒ Daa − ≤ D bb
⇒ 9.30 ≤ Dm2 + Untuk i = m , ∃
2 Daa
2 D aa
2 D aa
x 22,12 =
2 2 2 2 x 10 ,8 = x 8, 2 = 1 ⇒ D p − ≤ Dm +
Dm2
{2,11,12} jika dan hanya jika i − ∈ {2,11,12}. Setiap i ∈ {z,aa,bb} dan {i+, i − } ⊆ {2,11, 12}berlaku i+ dikunjungi terlebih dahulu dari pada i − . Tempat 11 dan 12 dikunjungi tepat 1 kali. Tempat 11 dan 12 dikunjungi sesuai dengan kendala waktunya, karena rute tersebut memenuhi: Untuk i = z, ∃ D z2 + = 8.00 ∈ [8.00, 8.15]
∧ ? 6
2 D bb
+
2 D bb
+
+
=10.30 ∈ [10.30,10.40]
∋
2 D bb − = 12.00 ∈ [12.00, 12.30] 2 2 x 12 ,11 = x 11, 2 = 1 ⇒ 10.00 ≤ 10.30
? 10.30 + 50 ≤ 12.00 Muatan barang yang dibawa oleh kendaraan tidak pernah melebihi 100 unit, karena kuantitas maksimum pada TR i ∈ {z,aa,bb} adalah sebesar 70 unit.
41
7
Rute kendaraan cycle 2-12-11-2 berhenti di Depot 2 pada pukul 12.00 . Batas waktu maksimum kedatangan kendaraan pada Depot 2 adalah pukul 12.00. Rute tersebut tidak melewati batas waktu tiba kendaraan pada Depot 2. Akibatnya cycle 2-12-11-2 merupakan rute fisibel PDPTW. Rute ini dinotasikan sebagai R 2,4.
Cycle 2-6-3-4-5-2 Cycle 2-6-3-4-5-2 bukan merupakan rute fisibel PDPTW. Hal ini disebabkan tidak terpenuhinya Syarat 6 dalam Defini si 13. Perhatikan TR b. Kuantitas pengiriman barang pada TR b melebihi kuantitas kendaraan yang dapat diangkut oleh kendaraan T ipe 2 (qb > Q2).
Lampiran 4 RMP0, P1,0 dan P2,0 • Hasil perhitungan RMP0 : min 330 x1,1 + 550 x1,2 x2,2 + 380 x2,4 subject to: a) x1,1 = 1 l) x2,2 b) x1,1 = 1 m) x2,2 c) x1,1 = 1 n) x1,2 d) x1,1 = 1 o) x1,2 e) x1,1 = 1 p) x1,2 f) x2,1 = 1 q) x1,2 g) x2,1 = 1 r) x1,2 h) x2,1 = 1 s) x1,4 i) x2,1 = 1 t) x1,4 j) x2,2 = 1 u) x1,4 k) x2,2 = 1 v) x1,6 end
+ 240 x1,4 + 260 x1,6 + 260 x2,1+ 300
= 1 = 1 = 1 = 1 = 1 = 1 = 1 = 1 = 1 = 1 = 1
LP OPTIMUM FOUND AT STEP
w) x1,6 x) x1,6 y) x1,6 z) x2,4 aa)x2,4 bb)x2,4 1) x1,1 x1,6 2) x2,1
= 1 = 1 = 1 = 1 = 1 = 1 + x1,2 + x1,4 + <= 4 + x2,2 + x2,4 <= 4
0
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1,1 X1,2 X1,4 X1,6 X2,1 X2,2 X2,4
ROW A) B) C) D) E) F) G) H) I) J) K)
2320.000 VALUE 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
REDUCED COST 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
DUAL PRICES -330.000000 0.000000 0.000000 0.000000 0.000000 -260.000000 0.000000 0.000000 0.000000 -300.000000 0.000000
42
L) M) N) O) P) Q) R) S) T) U) V) W) X) Y) Z) AA) BB) 1) 2) NO. ITERATIONS= •
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 1.000000
0.000000 0.000000 -550.000000 0.000000 0.000000 0.000000 0.000000 -240.000000 0.000000 0.000000 -260.000000 0.000000 0.000000 0.000000 -380.000000 0.000000 0.000000 0.000000 0.000000
0
Hasil perhitungan P1,0 : Masalah P1,0 diselesaikan dengan menggunakan sebagian kendala, yaitu Kendala (a), (b), (c), (d) dan (k) . Solusi dari masalah tersebut adalah rute kendaraan yang memiliki biaya tereduksi minimum dan belum dijamin kefisibelannya. Hasil perhitungan P 1,0 dengan Kendala (a), (b), (c), (d) dan (k) adalah sebagai berikut: MIN -230 x1,3 + 90 x3,4 + 70 x4,5 + 40 x5,6 + 30 x6,1 + 80 x3,5 + + 90 x9,8 - 480 x1,9 + 90 x9,10 + 110 x10,8 + 140 x8,7 + 140 x7,1 - 190 x1,14 + 90 x14,16 + 100 x16,1 - 170 x1,13 + 50 x13,14 + 70 x14,15 + 50 x15,1 SUBJECT TO a) x1,3 + x1,9 + x1,13 + x1,14 = 1 b) x16,1 + x15,1 + x7,1 + x6,1 = 1 c.1) x1,3 + x1,9 + x1,13 + x1,14 - Ya = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ya = 0 c.2) x1,3 - Yb = 0 x3,4 + x3,5 - Yb = 0 c.3) x3,4 - Yc = 0 x4,5 - Yc = 0 c.4) x4,5 + x3,5 - Yd = 0 x5,6 - Yd = 0 c.5) x5,6 - Ye = 0 x6,1 - Ye = 0 c.6) x1,3 - Yh = 0 x3,4 + x3,5 - Yh = 0 c.7) x1,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.8) x1,3 + x1,9 + x1,13 + x1,14 - Yn = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yn = 0 c.9) x1,9 - Yo = 0 x9,10 + x9,8 - Yo = 0 c.102) x9,10 - Yp =0 x10,8 - Yp =0 c.11) x9,8 + x10,8 - Yq = 0 x8,7 - Yq = 0 c.12) x8,7 - Yr = 0 x7,1 - Yr = 0
43
c.13) x1,3 + x1,9 + x1,13 + x1,14 - Ys = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ys = 0 c.14) x1,14 + x13,14 - Yt = 0 x14,16 + x14,15 - Yt = 0 c.15) x14,16 - Yu = 0 x16,1 - Yu = 0 c.16) x1,3 + x1,9 + x1,13 + x1,14 - Yv = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yv = 0 c.17) x1,13 - Yw = 0 x13,14 - Yw = 0 c.18) x1,14 + x13,14 - Yx = 0 x14,16 + x14,15 - Yx = 0 c.19) x14,15 - Yy = 0 x15,1 - Yy = 0 END LP OPTIMUM FOUND AT STEP
11
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1,3 X3,4 X4,5 X5,6 X6,1 X3,5 X9,8 X1,9 X9,10 X10,8 X8,7 X7,1 X1,14 X14,16 X16,1 X1,13 X13,14 X14,15 X15,1 YA YB YC YD YE YH YL YN YO YP YQ YR YS YT YU YV YW
-110.0000 VALUE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 1.000000 0.000000
REDUCED COST 30.000000 80.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 110.000000 0.000000 0.000000 0.000000 0.000000 110.000000 0.000000 70.000000 0.000000 40.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 0.000000
44
YX YY
0.000000 0.000000
0.000000 0.000000
Rute yang dihasilkan adalah rute 1-9-8-7-1. Untuk memeriksa kefisibelannya, ambil D1n + =7.00, D1n − = 8.00 , D1l + = 8.00, D1l − = 8.30, D 1q + = 9.00, D1q − = 9. 30 , D 1r − = 10.40 dan D1r + = 10.10, sehingga rute tersebut memenuhi Kendala (e), (f), (g), (h) dan (i). Rute 1-9-8-7-1 juga memenuhi Kendala (j). Akibatnya rute tersebut merupakan rute yang fisibel. •
Hasil perhitungan P2,0 : Masalah P2,0 diselesaikan dengan menggunakan sebagian kendala, yaitu Kendala (a), (b), (c), (d) dan (k) . Solusi dari masalah tersebut adalah rute kendaraan yang memiliki biaya tereduksi minimum dan belum dijamin kefisibelannya. Hasil perhitungan P2,0 dengan Kendala (a), (b), (c), (d) dan (k) adalah sebagai berikut: MIN 60 x3,4 + 50 x4,5 - 180 x2,6 + 70 x6,3+ 70 x3,5 + 40 x5,2 250 x2,7 + 60 x7,9 + 90 x9,8 + 100 x8,2 + 40 x9,10 + 40 x10,8 + - 250 x2,12 + 100 x12,11 + 150 x11,12 subject to a) x2,7 + x2,12 + x2,6 = 1 b) x5,2 + x8,2 + x11,12 = 1 c.1) x2,7 + x2,12 + x2,6 - Yf = 0 x5,2 + x8,2 + x11,12 - Yf = 0 c.2) x2,6 - Yg = 0 x6,3 - Yg = 0 c.3) x6,3 - Yh = 0 x3,5 + x3,4 - Yh = 0 c.4) x4,5 + x3,5 - Yi = 0 x5,2 - Yi = 0 c.5) x6,3 - Yb = 0 x3,5 + x3,4 - Yb = 0 c.6) x3,4 - Ye = 0 x4,5 - Ye = 0 c.7) x2,7 + x2,12 + x2,6 - Yj = 0 x5,2 + x8,2 + x11,12 - Yj = 0 c.8) x2,7 - Yk = 0 x7,9 - Yk = 0 c.9) x7,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.10) x9,8 + x10,8 - Ym = 0 x8,2 - Ym = 0 c.11) x7,9 - Yo = 0 x9,8 + x9,10 - Yo = 0 c.12) x9,10 - Yp = 0 x10,8 - Yp = 0 c.13) x2,7 + x2,12 + x2,6 - Yz = 0 x5,2 + x8,2 + x11,12 - Yz = 0 c.14) x2,12 - Yaa = 0 x12,11 - Yaa = 0 c.15) x12,11 - Ybb = 0 x11,12 - Ybb = 0 END LP OPTIMUM FOUND AT STEP
7
OBJECTIVE FUNCTION VALUE 1)
-10.00000
45
VARIABLE X3,4 X4,5 X2,6 X6,3 X3,5 X5,2 X2,7 X7,9 X9,8 X8,2 X9,10 X10,8 X2,12 X12,11 X11,12 YF YG YH YI YB YE YD YJ YK YL YM YO YP ZQ YZ YAA YBB
VALUE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000
REDUCED COST 0.000000 50.000000 10.000000 0.000000 0.000000 0.000000 0.000000 0.000000 10.000000 0.000000 0.000000 0.000000 0.000000 0.000000 10.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
Rute yang dihasilkan adalah rute 2-7-9-10-8-2. Untuk memeriksa kefisibelannya, ambil D 2j + =7.30, D 2j − = 8.00, Dk2 + = 8.00, Dk2 − = 8.30, Do2 + = 8.30, Do2 − = 9.00, D 2p + = 9.00, D 2p − =9.30, Dm2 − = 10.40 dan Dm2 + = 10.00, sehingga rute tersebut memenuhi kendala (e), (f),
(g), (h) dan (i). Rute 2-7-9-10-8-2 juga memenuhi kendala (j). Akibatnya rute tersebut merupakan rute yang fisibel.
Lampiran 5 RMP1, P1,1 dan P2,1 •
Hasil perhitungan RMP1 :
min 330 x2,1 subject a) x1,1 b) x1,1 c) x1,1 d) x1,1 e) x1,1 f) x2,1 g) x2,1 h) x2,1 i) x2,1
x1,1 + 550 x1,2 + 440 x1,3 + 300 x2,2 + 380 x2,4 to: = 1 j) x2,2 = 1 = 1 k) x2,2 = 1 = 1 l) x1,3 + x2,2 = 1 m) x2,2 = 1 = 1 n) x1,2 + x1,3 = 1 o) x1,2 = 1 = 1 p) x1,2 = 1 = 1 q) x1,2 + x1,3 = 1 r) x1,2 + x1,3
+ 240 x1,4 + 260 x1,6 + 260
= 1 = 1
= 1 = 1
46
s) x1,4 = 1 t) x1,4 = 1 u) x1,4 = 1 v) x1,6 = 1 w) x1,6 = 1 x) x1,6 = 1 end
y) x1,6 z) x2,4 aa)x2,4 bb)x2,4 1) x1,1 2) x2,1
LP OPTIMUM FOUND AT STEP
= 1 = 1 = 1 = 1 + x1,2 + x1,3 + x1,4 + x1,6 <= 4 + x2,2 + x2,4 <= 4
1
OBJECTIVE FUNCTION VALUE 1)
2320.000
VARIABLE X1,1 X1,2 X1,3 X1,4 X1,6 X2,1 X2,2 X2,4
ROW A) B) C) D) E) F) G) H) I) J) K) L) M) N) O) P) Q) R) S) T) U) V) W) X) Y) Z) AA) BB) 1) 2)
VALUE 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000
SLACK OR SURPLUS 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 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000
NO. ITERATIONS=
1
REDUCED COST 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
DUAL PRICES -330.000000 0.000000 0.000000 0.000000 0.000000 -260.000000 0.000000 0.000000 0.000000 -300.000000 0.000000 0.000000 0.000000 -440.000000 0.000000 -110.000000 0.000000 0.000000 -240.000000 0.000000 0.000000 -260.000000 0.000000 0.000000 0.000000 -380.000000 0.000000 0.000000 0.000000 0.000000
47
•
Hasil perhitungan P1,1 : Masalah P 1,1 diselesaikan dengan menggunakan kendala -kendala seperti pada masalah P 1,0 dalam Lampiran 4., sehingga diperoleh hasil berikut: MIN -230 x1,3 + 90 x3,4 + 70 x4,5 + 40 x5,6 + 30 x6,1 + 80 x3,5 370 x1,9 + 90 x9,10 + 0 x10,8 + 140 x8,7 + 140 x7,1 - 190 x1,14 + 90 x14,16 + 100 x16,1 - 170 x1,13 + 50 x13,14 + 70 x14,15 + 50 x15,1 + 90 x9,8 SUBJECT TO a) x1,3 + x1,9 + x1,13 + x1,14 = 1 b) x16,1 + x15,1 + x7,1 + x6,1 = 1 c.1) x1,3 + x1,9 + x1,13 + x1,14 - Ya = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ya = 0 c.2) x1,3 - Yb = 0 x3,4 + x3,5 - Yb = 0 c.3) x3,4 - Yc = 0 x4,5 - Yc = 0 c.4) x4,5 + x3,5 - Yd = 0 x5,6 - Yd = 0 c.5) x5,6 - Ye = 0 x6,1 - Ye = 0 c.6) x1,3 - Yh = 0 x3,4 + x3,5 - Yh = 0 c.7) x1,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.8) x1,3 + x1,9 + x1,13 + x1,14 - Yn = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yn = 0 c.9) x1,9 - Yo = 0 x9,10 + x9,8 - Yo = 0 c.102) x9,10 - Yp =0 x10,8 - Yp =0 c.11) x9,8 + x10,8 - Yq = 0 x8,7 - Yq = 0 c.12) x8,7 - Yr = 0 x7,1 - Yr = 0 c.13)x1,3 + x1,9 + x1,13 + x1,14 - Ys = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ys = 0 c.14) x1,14 + x13,14 - Yt = 0 x14,16 + x14,15 - Yt = 0 c.15) x14,16 - Yu = 0 x16,1 - Yu = 0 c.16) x1,3 + x1,9 + x1,13 + x1,14 - Yv = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yv = 0 c.17) x1,13 - Yw = 0 x13,14 - Yw = 0 c.18) x1,14 + x13,14 - Yx = 0 x14,16 + x14,15 - Yx = 0 c.19) x14,15 - Yy = 0 x15,1 - Yy = 0 END INTE Ya INTE Yb INTE Yc
NO. ITERATIONS= 39 BRANCHES= 1 DETERM.= LP OPTIMUM FOUND AT STEP
1.000E 9
0
48
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1,3 X3,4 X4,5 X5,6 X6,1 X3,5 X1,9 X9,10 X8,7 X7,1 X1,14 X14,16 X16,1 X1,13 X13,14 X14,15 X15,1 X9,8 YA YB YC YD YE YG YH YK YL YN YO YP X10,8 YQ YR YS YT YU YV YW YX YY
-80.00000 VALUE 1.000000 0.000000 0.000000 1.000000 1.000000 1.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 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000
REDUCED COST 0.000000 80.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 80.000000 0.000000 10.000000 70.000000 0.000000 80.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 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Rute yang dihasilkan adalah rute 1-3-5-6-1. Rute ini bukan merupakan rute yang fisibel, karena untuk x3,5 = x5,6 = 1 tidak berlaku D1h − ≤ Dd1 + , dengan D1h − ∈ [10.40, 10.50] dan
D1d + ∈ [9.50,10.10]. Akibatnya x3,5 + x 5,6 ≤ 1, artinya variabel x3,5 dan x5,6 tidak dapat digunakan secara bersamaan dalam suatu rute kendaraan. Akibat ini kemudian ditambahkan ke dalam kendala masalah P1,1 dari sebagian kendala. Masalah ini dinotasikan sebagai masalah P1,′1 dan kemudian diperoleh hasil sebagai berikut: MIN -230 x1,3 + 90 x3,4 + 70 x4,5 + 40 x5,6 + 30 x6,1 + 80 x3,5 370 x1,9 + 90 x9,10 + 0 x10,8 + 140 x8,7 + 140 x7,1 - 190 x1,14 +
49
90 x14,16 + 100 x16,1 - 170 x1,13 + 50 x13,14 + 70 x14,15 + 50 x15,1 + 90 x9,8 SUBJECT TO a) x1,3 + x1,9 + x1,13 + x1,14 = 1 b) x16,1 + x15,1 + x7,1 + x6,1 = 1 c.1) x1,3 + x1,9 + x1,13 + x1,14 - Ya = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ya = 0 c.2) x1,3 - Yb = 0 x3,4 + x3,5 - Yb = 0 c.3) x3,4 - Yc = 0 x4,5 - Yc = 0 c.4) x4,5 + x3,5 - Yd = 0 x5,6 - Yd = 0 c.5) x5,6 - Ye = 0 x6,1 - Ye = 0 c.6) x1,3 - Yh = 0 x3,4 + x3,5 - Yh = 0 c.7) x1,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.8) x1,3 + x1,9 + x1,13 + x1,14 - Yn = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yn = 0 c.9) x1,9 - Yo = 0 x9,10 + x9,8 - Yo = 0 c.102) x9,10 - Yp =0 x10,8 - Yp =0 c.11) x9,8 + x10,8 - Yq = 0 x8,7 - Yq = 0 c.12) x8,7 - Yr = 0 x7,1 - Yr = 0 c.13) x1,3 + x1,9 + x1,13 + x1,14 - Ys = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ys = 0 c.14) x1,14 + x13,14 - Yt = 0 x14,16 + x14,15 - Yt = 0 c.15) x14,16 - Yu = 0 x16,1 - Yu = 0 c.16) x1,3 + x1,9 + x1,13 + x1,14 - Yv = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yv = 0 c.17) x1,13 - Yw = 0 x13,14 - Yw = 0 c.18) x1,14 + x13,14 - Yx = 0 x14,16 + x14,15 - Yx = 0 c.19) x14,15 - Yy = 0 x15,1 - Yy = 0 g.9) x3,5 + x5,6 <= 1 END INTE Ya INTE Yb INTE Yc OBJECTIVE FUNCTION VALUE 1) VARIABLE YA YB YC X1,3 X3,4
-70.00000 VALUE 1.000000 0.000000 0.000000 0.000000 0.000000
REDUCED COST -70.000000 -10.000000 80.000000 0.000000 0.000000
50
X4,5 X5,6 X6,1 X3,5 X1,9 X9,10 X8,7 X7,1 X1,14 X14,16 X16,1 X1,13 X13,14 X14,15 X15,1 X9,8 YD YE YG YH YN YO YP X10,8 YQ YR YS YT YU YV YW YX YY
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 1.000000 0.000000 1.000000 1.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 70.000000 0.000000 70.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 70.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Rute yang dihasilkan adalah rute 1-14-15-1. Untuk memeriksa kefisibelannya, ambil D1s + = 7.00,
D1s − = 7.40, D1x + = 10.30, D1x − = 11.00, D1y + =11.00 dan D 1y − = 11.50, sehingga rute tersebut memenuhi Kendala (e), (f), (g), (h) dan (i). Rute 2-7-9-10-8-2 juga memenuhi Kendala (j). Akibatnya rute tersebut merupakan rute yang fisibel. •
Hasil perhitungan P2,1 : Masalah P 2,1 diselesaikan dengan menggunakan kendala -kendala seperti pada masalah P 2,0 dalam Lampiran 4., sehingga diperoleh hasil berikut: MIN 60 x3,4 + 50 x4,5 - 180 x2,6 + 70 x6,3+ 70 x3,5 + 40 x5,2 250 x2,7 + 60 x7,9 + 90 x9,8 + 100 x8,2 + 40 x9,10 - 20 x10,8 - 250 x2,12 + 100 x12,11 + 150 x11,12 subject to a) x2,7 + x2,12 + x2,6 = 1 b) x5,2 + x8,2 + x11,12 = 1 c.1) x2,7 + x2,12 + x2,6 - Yf = 0 x5,2 + x8,2 + x11,12 - Yf = 0 c.2) x2,6 - Yg = 0 x6,3 - Yg = 0 c.3) x6,3 - Yh = 0 x3,5 + x3,4 - Yh = 0 c.4) x4,5 + x3,5 - Yi = 0 x5,2 - Yi = 0
51
c.5) x6,3 - Yb = 0 x3,5 + x3,4 - Yb = 0 c.6) x3,4 - Ye = 0 x4,5 - Ye = 0 c.7) x2,7 + x2,12 + x2,6 - Yj = 0 x5,2 + x8,2 + x11,12 - Yj = 0 c.8) x2,7 - Yk = 0 x7,9 - Yk = 0 c.9) x7,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.10) x9,8 + x10,8 - Ym = 0 x8,2 - Ym = 0 c.11) x7,9 - Yo = 0 x9,8 + x9,10 - Yo = 0 c.12) x9,10 - Yp = 0 x10,8 - Yp = 0 c.13) x2,7 + x2,12 + x2,6 - Yz = 0 x5,2 + x8,2 + x11,12 - Yz = 0 c.14) x2,12 - Yaa = 0 x12,11 - Yaa = 0 c.15) x12,11 - Ybb = 0 x11,12 - Ybb = 0 END LP OPTIMUM FOUND AT STEP
1
OBJECTIVE FUNCTION VALUE 1) VARIABLE X3,4 X4,5 X2,6 X6,3 X3,5 X5,2 X2,7 X7,9 X9,8 X8,2 X9,10 X10,8 X2,12 X12,11 X11,12 YF YG YH YI YB YE YD YJ YK YL YM YO YP
-70.00000 VALUE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
REDUCED COST 0.000000 50.000000 70.000000 0.000000 0.000000 0.000000 0.000000 0.000000 70.000000 0.000000 0.000000 0.000000 0.000000 70.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
52
ZQ YZ YAA YBB
1.000000 1.000000 0.000000 0.000000
0.000000 0.000000 0.000000 0.000000
Rute yang dihasilkan adalah rute 2-7-9-10-8-2. Rute ini merupakan rute yang fisibel (lihat hasil perhitungan P2,0 pada Lampiran 4). Lampiran 6 RMP2, P1,2 dan P2,2 • Hasil perhitungan RMP2 : • min 330 x1,1 + 550 x1,2 + 440 x1,3 + 240 x1,4 + 170 x1,5 + 260 x1,6 + 260 x2,1 + 300 x2,2 + 290 x2,3 + 380 x2,4 subject to: a) x1,1 = 1 q) x1,2 + x1,3 = 1 b) x1,1 = 1 r) x1,2 + x1,3 = 1 c) x1,1 = 1 s) x1,4 + x1,5 = 1 d) x1,1 = 1 t) x1,4 = 1 e) x1,1 = 1 u) x1,4 = 1 f) x2,1 = 1 v) x1,6 = 1 g) x2,1 = 1 w) x1,6 = 1 h) x2,1 = 1 x) x1,5 + x1,6 = 1 i) x2,1 = 1 y) x1,5 + x1,6 = 1 j) x2,2 + x2,3 = 1 z) x2,4 = 1 k) x2,2 + x2,3 = 1 aa) x2,4 = 1 l) x1,3 + x2,2 = 1 bb) x2,4 = 1 m) x2,2 + x2,3 = 1 1) x1,1 + x1,2 + x1,3 + x1,4 + x1,5 + n) x1,2 + x1,3 = 1 x1,6 <= 4 o) x1,2 + x2,3 = 1 2) x2,1 + x2,2 + x2,3 + x2,4 <= 4 p) x1,2 + x2,3 = 1 end
LP OPTIMUM FOUND AT STEP
2
OBJECTIVE FUNCTION VALUE 1) VARIABLE X1,1 X1,2 X1,3 X1,4 X1,5 X1,6 X2,1 X2,2 X2,3 X2,4
ROW A) B) C) D) E) F)
2200.000 VALUE 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 1.000000 1.000000
SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
REDUCED COST 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.000000 0.000000 0.000000
DUAL PRICES -330.000000 0.000000 0.000000 0.000000 0.000000 -260.000000
53
G) H) I) J) K) L) M) N) O) P) Q) R) S) T) U) V) W) X) Y) Z) AA) BB) 1) 2) NO. ITERATIONS= •
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 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000
0.000000 0.000000 0.000000 -290.000000 0.000000 110.000000 0.000000 -550.000000 0.000000 0.000000 0.000000 0.000000 -240.000000 0.000000 0.000000 -330.000000 0.000000 0.000000 70.000000 -380.000000 0.000000 0.000000 0.000000 0.000000
2
Hasil perhitungan P1,2 : Masalah P1,2 diselesaikan dengan menggunakan kendala-kendala seperti pada masalah P1,′1
dalam Lampiran 5. Hasil perhitungannya adalah sebagai berikut: MIN -230 x1,3 + 90 x3,4 + 70 x4,5 + 40 x5,6 + 30 x6,1 + 80 x3,5 370 x1,9 + 90 x9,10 + 0 x10,8 + 140 x8,7 + 140 x7,1- 190 x1,14 + 90 x14,16 + 100 x16,1 - 240 x1,13 + 50 x13,14 + 70 x14,15 + 120 x15,1 + 10 x7,9 + 90 x9,8 a) x1,3 + x1,9 + x1,13 + x1,14 = 1 b) x16,1 + x15,1 + x7,1 + x6,1 = 1 c.1) x1,3 + x1,9 + x1,13 + x1,14 - Ya = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ya = 0 c.2) x1,3 - Yb = 0 x3,4 + x3,5 - Yb = 0 c.3) x3,4 - Yc = 0 x4,5 - Yc = 0 c.4) x4,5 + x3,5 - Yd = 0 x5,6 - Yd = 0 c.5) x5,6 - Ye = 0 x6,1 - Ye = 0 c.6) x1,3 - Yh = 0 x3,4 + x3,5 - Yh = 0 c.7) x1,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.8) x1,3 + x1,9 + x1,13 + x1,14 - Yn = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yn = 0 c.9) x1,9 - Yo = 0 x9,10 + x9,8 - Yo = 0 c.102) x9,10 - Yp =0 x10,8 - Yp =0
54
c.11) x9,8 + x10,8 - Yq = 0 x8,7 - Yq = 0 c.12) x8,7 - Yr = 0 x7,1 - Yr = 0 c.13) x1,3 + x1,9 + x1,13 + x1,14 - Ys = 0 x16,1 + x15,1 + x7,1 + x6,1 - Ys = 0 c.14) x1,14 + x13,14 - Yt = 0 x14,16 + x14,15 - Yt = 0 c.15) x14,16 - Yu = 0 x16,1 - Yu = 0 c.16) x1,3 + x1,9 + x1,13 + x1,14 - Yv = 0 x16,1 + x15,1 + x7,1 + x6,1 - Yv = 0 c.17) x1,13 - Yw = 0 x13,14 - Yw = 0 c.18) x1,14 + x13,14 - Yx = 0 x14,16 + x14,15 - Yx = 0 c.19) x14,15 - Yy = 0 x15,1 - Yy = 0 g.9) x3,5 + x5,6 <= 1 End Inte Ya Inte Yb LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) VARIABLE YA YB X1,3 X3,4 X4,5 X5,6 X6,1 X3,5 X1,9 X9,10 X8,7 X7,1 X1,14 X14,16 X16,1 X1,13 X13,14 X14,15 X15,1 X7,9 X9,8 YC YD YE YG YH YN YO YP
0.0000000E+00 VALUE 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.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 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000
REDUCED COST -30.000000 80.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 240.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
55
X10,8 YQ YR YS YT YU YV YW YX YY
0.000000 0.000000 0.000000 1.000000 0.000000 0.000000 1.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
Rute yang dihasilkan adalah rute 1-3-4-5-6-1 dengan biaya sebesar 0, artinya tidak ada lagi rute-rute yang memiliki biaya tereduksi negatif termasuk rute yang fisibel, sehingga rute 1-3-4-56-1 tidak perlu diperiksa kefisibelannya. •
Hasil perhitungan P2,2 : Masalah P 2,1 diselesaikan dengan menggunakan kendala -kendala seperti pada masalah P 2,1 dalam Lampiran 5., sehingga diperoleh hasil berikut: MIN 60 x3,4 + 50 x4,5 - 180 x2,6 + 70 x6,3+ 70 x3,5 + 40 x5,2 250 x2,7 + 60 x7,9 + 90 x9,8 + 100 x8,2 + 40 x9,10 + 200 x10,8 - 250 x2,12 + 100 x12,11 + 150 x11,12 a) x2,7 + x2,12 + x2,6 = 1 b) x5,2 + x8,2 + x11,12 = 1 c.1) x2,7 + x2,12 + x2,6 - Yf = 0 x5,2 + x8,2 + x11,12 - Yf = 0 c.2) x2,6 - Yg = 0 x6,3 - Yg = 0 c.3) x6,3 - Yh = 0 x3,5 + x3,4 - Yh = 0 c.4) x4,5 + x3,5 - Yi = 0 x5,2 - Yi = 0 c.5) x6,3 - Yb = 0 x3,5 + x3,4 - Yb = 0 c.6) x3,4 - Ye = 0 x4,5 - Ye = 0 c.7) x2,7 + x2,12 + x2,6 - Yj = 0 x5,2 + x8,2 + x11,12 - Yj = 0 c.8) x2,7 - Yk = 0 x7,9 - Yk = 0 c.9) x7,9 - Yl = 0 x9,8 + x9,10 - Yl = 0 c.10) x9,8 + x10,8 - Ym = 0 x8,2 - Ym = 0 c.11) x7,9 - Yo = 0 x9,8 + x9,10 - Yo = 0 c.12) x9,10 - Yp = 0 x10,8 - Yp = 0 c.13) x2,7 + x2,12 + x2,6 - Yz = 0 x5,2 + x8,2 + x11,12 - Yz = 0 c.14) x2,12 - Yaa = 0 x12,11 - Yaa = 0 c.15) x12,11 - Ybb = 0 x11,12 - Ybb = 0 END
56
LP OPTIMUM FOUND AT STEP
2
OBJECTIVE FUNCTION VALUE 1) VARIABLE X3,4 X4,5 X2,6 X6,3 X3,5 X5,2 X2,7 X7,9 X9,8 X8,2 X9,10 X10,8 X2,12 X12,11 X11,12 YF YG YH YI YB YE YD YJ YK YL YM YO YP ZQ YZ YAA YBB
0.0000000E+00 VALUE 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 1.000000 1.000000 1.000000 1.000000 0.000000 1.000000 1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000 0.000000 0.000000
REDUCED COST 0.000000 50.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 150.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 0.000000 0.000000 0.000000
Rute yang dihasilkan adalah rute 2-6-3-5-2 dengan biaya sebesar 0, artinya tidak ada lagi ruterute yang memiliki biaya tereduksi negatif termasuk rute yang fisibel, sehingga rute 2-6-3-5-2 tidak perlu diperiksa kefisibelannya.
