PENYELESAIAN MASALAH PENGIRIMAN PAKET KILAT UNTUK JENIS NEXT-DAY SERVICE DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM
Oleh: WULAN ANGGRAENI G54101038
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
ABSTRAK WULAN ANGGRAENI. Penyelesaian Masalah Pengiriman Paket Kilat untuk Jenis Next-Day Service dengan Menggunakan Teknik Pembangkitan Kolom. Dibimbing oleh AMRIL AMAN dan PRAPTO TRI SUPRIYO. Pengiriman paket kilat jenis next-day service adalah pelayanan pengiriman paket sampai ke tempat tujuan keesokan harinya. Masalah pengiriman paket untuk jenis ini dapat dipandang menjadi dua permasalahan yaitu, masalah arus pergerakan paket dan masalah jaringan pelayanan. Definisi dari masalah arus pergerakan paket adalah mengirimkan sejumlah paket dari kota asal ke kota tujuan dengan mempertimbangkan situasi dimana kota asal dan kota tujuan dihubungkan melalui sebuah jaringan busur dengan kapasitas terbatas. Pergerakan dari kota asal ke kota tujuan dapat dibuat sebagai sebuah jaringan. Pembuatan struktur jaringan ini bertujuan untuk memudahkan proses perumusan masalah. Perumusan masalah ini dapat menggunakan tiga alternatif perumusan masalah yaitu, node-arc formulation, path formulation dan subnetwork formulation. Dalam arti sederhana, model jaringan pelayanan berusaha menentukan rencana pelayanan pengiriman sebuah paket deri sejumlah sumber ke sejumlah tujuan. Tujuan dari model ini adalah menentukan jaringan pelayanan dan menentukan arus pergerakan paket pada jaringan pelayanan tersebut, sedemikian rupa menghasilkan total biaya minimum. Jaringan pelayanan ini mempunyai dua variabel keputusan yaitu, Jumlah suatu jenis armada yang beroperasi pada suatu rute dan Prosentase aliran paket untuk setiap kombinasi path yang berdaerah asal sama. Perumusan masalah ini sulit dipecahkan sehingga diperlukan suatu metode heuristik untuk menyelesaikan masalah diatas. Metode heuristik ini mempunyai dua tahap yaitu pemilihan variabel dan penyelesaian masalah. Dalam karya ilmiah ini penyelesaian masalah arus pergerakan paket dalam skala besar dapat menggunakan teknik pembangkitan kolom, sedangkan penyelesaian masalah jaringan pelayanan dalam skala besar dapat menggunakan branch and price algorithm. Branch and price algorithm adalah suatu teknik yang mengkombinasikan teknik pembangkitan kolom dengan kerangka branch and bound. Teknik pembangkitan kolom merupakan teknik untuk menyelesaikan pemrograman linear dengan hanya menggunakan sebagian variabel dari masalah keseluruhan.
PENYELESAIAN MASALAH PENGIRIMAN PAKET KILAT UNTUK JENIS NEXT-DAY SERVICE DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM
Skripsi
Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan alam Institut Pertanian Bogor
Oleh: WULAN ANGGRAENI G54101038
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
Judul
:
Nama NRP
: :
PENYELESAIAN MASALAH PENGIRIMAN PAKET KILAT UNTUK JENIS NEXT-DAY SERVICE DENGAN MENGGUNAKAN TEKNIK PEMBANGKITAN KOLOM Wulan Anggraeni G54101038
Menyetujui,
Pembimbing I
Pembimbing II
Dr. Ir Amril Aman, M.Sc NIP. 130 937 092
Drs. Prapto Tri Supriyo, M.Kom NIP. 131 878 952
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. Ir Yonny Koesmaryono, M.S NIP. 131 473 999
Tanggal Lulus :
RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 4 November 1983 sebagai anak kedua dari tiga bersaudara dari pasangan bapak Djaman Mertoardjo dan Ibu Edja Sutedja. Pada tahun 2001 penulis lulus dari SMUN 109 Jakarta dan berhasil menjadi mahasiswa Jurusan Matematika (yang sekarang berganti nama menjadi Departemen Matematika), Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor melalui jalur USMI (Undangan Seleksi Masuk IPB). Selama mengikuti kegiatan perkuliahan, penulis aktif dalam kegiatan Badan Eksekutif Mahasiswa FMIPA pada tahun 2002/2003. Selain itu penulis juga pernah aktif dalam kepengurusan GUMATIKA (Gugus Mahasiswa Matematika) pada periode 2002/2003.
PRAKATA Bismillaahirrahmaaniiahiim, Puji dan syukur penulis panjatkan kepada ALLAH SWT atas segala karunia, rahmat tak terhingga dan kekuatan sehingga penulis dapat menyelesaikan karya ilmiah ini. Dengan segala kerendahan hati, penulis iingin mengucapkan terimakasih kepada: 1. Bapal Amril Aman selaku pembimbing 1 yang telah memberikan ketulusan hati untuk memberikan saran dan masukan yang tak terbalaskan. 2. Bapak Prapto Tri Supriyo selaku pembimbing 2 yang telah membantu dalam penulisan karya ilmiah ini. 3. Bapak Siswandi atas bimbingan dan kesediannya menjadi penguji. 4. Bapa dan mama tercinta yang tiada hentinya memberikan nasihat, doa dan dukungan. Terimakasih atas segenap kasih sayang yang tak akan pernah terbalas. Kakakku Elita yang telah memberikan semangat untuk menyelesaikan karya ilmiah ini dan Adikku Rinno yang telah memberikan keceriaan. 5. Seluruh dosen beserta staf Departemen Matematika atas ilmunya yang tak ternilai 6. Muhammad Hatta Gussetiyo yang telah memberikan kesabaran, semangat, dan perhatian. 7. Sahabat terbaikku Ningrum dan Yenny yang telah mengisi 5 tahun terakhir dengan kebersamaan yang indah. 8. teman-teman angkatan 38 atas kenangan yang indah selama masa perkuliahan. 9. Seluruh rekan seperjuangan angkatan 35, 36, 37, 39 dan 40. 10. Serta semua pihak yang telah membantu terselesaikannya skripsi ini. Penulis menyadari dalam penyusunan 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 memerlukan.
Bogor, Juli 2006 Wulan Anggraeni
DAFTAR ISI Halaman DAFTAR TABEL ……………………………………………………………………………. viii DAFTAR GAMBAR …………………………………………………………………………. viii DAFTAR LAMPIRAN ………………………………………………………………………. I
ix
PENDAHULUAN Latar Belakang ……………………………………………………………………… Tujuan ……………………………………………………………………………….
1 1
LANDASAN TEORI Pemrograman Linear ………………………………………………………………... Teknik Pembangkitan Kolom ………………………………………………………. Pemrograman Linear Bilangan Bulat ………………………………………………. Graf …………………………………………………………………………….........
1 3 3 3
III GAMBARAN DAN PERUMUSAN MASALAH Gambaran Masalah …………………………………………………………………. Perumusan Masalah …………………………………………………………………
6 9
II
IV PENYELESAIAN MASALAH Penyelesaian Masalah Arus Paket dengan Menggunakan Teknik Pembangkitan kolom ……………………………………………………………………………….. Penyelesaian Masalah Jaringan Pelayanan dengan Menggunakan Branch and Price Algorithm………………………………………………………………………
15
V
SIMPULAN ………………………………………………………………………………
20
DAFTAR PUSTAKA …………………………………………………………………………
21
LAMPIRAN …………………………………………………………………………………..
22
17
DAFTAR TABEL 1 2 3
Halaman Jumlah Pengiriman Paket yang Harus Dikirimkan…………………................................ 22 Kapasitas Maksimum Setiap Busur dan Biaya Setiap Busur …………………………… 22 Biaya untuk Setiap Kemungkinan q …………………………………….......................... 29
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11
Halaman Graf G = (V, E) …………………………………………………………………. …….... 4 Contoh Tree ……………………………………………………………………………… 4 Digraph D = (V, A) …………………………………………………………………….... 4 Contoh Network …………………………………………………………………………. 5 Contoh Graf G = (V, E) …………………………………………………………………. 5 Contoh Digraph D = (V, A) ……………………………………………………………… 5 Contoh Graf Pengambilan Paket ………………………………………………………… 6 Contoh Graf Pengantaran Paket …………………………………………………………. 7 Graf Rute Pengiriman Paket …………………………………………….......................... 8 Graf Pengiriman Paket …………………………………………………………………… 22 q = 1, SO ( k ) = 1 …………………………………………………………………………… 23
12 q = 2, SO ( k ) = 1 …………………………………………………………………………..
23
13 q = 3, SO ( k ) = 1 …………………………………………………………………………..
23
14 q = 4, SO ( k ) = 1 …………………………………………………………………………..
23
15 q = 5, SO ( k ) = 1 …………………………………………………………………………..
23
16 q = 6, SO ( k ) = 1 …………………………………………………………………………..
23
17 q = 7, SO ( k ) = 1 …………………………………………………………………………..
24
18 q = 8, SO ( k ) = 1 …………………………………………………………………………..
24
19 q = 9, SO ( k ) = 1 …………………………………………………………………………..
24
20 q = 10, SO ( k ) = 1 …………………………………………………………………………
24
21 q = 11, SO ( k ) = 1 …………………………………………………………………………
24
22 q = 12, SO ( k ) = 1 …………………………………………………………………………
24
23 q = 13, SO ( k ) = 1 …………………………………………………………………………
24
24 q = 14, SO ( k ) = 1 …………………………………………………………………………
24
25 q = 15, SO ( k ) = 1 …………………………………………………………………………
24
26 q = 16, SO ( k ) = 1 …………………………………………………………………………
25
27 q = 17, SO ( k ) = 1 …………………………………………………………………………
25
28 q = 18, SO ( k ) = 1 …………………………………………………………………………
25
29 q = 19, SO ( k ) = 1 …………………………………………………………………………
25
30 q = 20, SO ( k ) = 1 …………………………………………………………………………
25
31 q = 21, SO ( k ) = 1 …………………………………………………………………………
25
32 q = 22, SO ( k ) = 1 …………………………………………………………………………
26
33 q = 23, SO ( k ) = 1 …………………………………………………………………………
26
34 q = 24, SO ( k ) = 1 ………………………………………………………………………….
26
35 q = 25, SO ( k ) = 1 …………………………………………………………………………
26
36 q = 26, SO ( k ) = 2 …………………………………………………………………………
26
37 q = 27, SO ( k ) = 2 …………………………………………………………………………
26
38 q = 28, SO ( k ) = 2 …………………………………………………………………………
26
39 q = 29, SO ( k ) = 2 …………………………………………………………………………
26
40 q = 30, SO ( k ) = 2 …………………………………………………………………………
27
41 q = 31, SO ( k ) = 2 …………………………………………………………………………
27
42 q = 32, SO ( k ) = 2 …………………………………………………………………………
27
43 q = 33, SO ( k ) = 2 …………………………………………………………………………
27
44 q = 34, SO ( k ) = 2 …………………………………………………………………………
27
45 q = 35, SO ( k ) = 2 …………………………………………………………………………
27
46 q = 36, SO ( k ) = 2 …………………………………………………………………………
27
47 q = 37, SO ( k ) = 2 …………………………………………………………………………
27
48 q = 38, SO ( k ) = 2 …………………………………………………………………………
28
49 q = 39, SO ( k ) = 2 …………………………………………………………………………
28
50 q = 40, SO ( k ) = 2 …………………………………………………………………………
28
51 q = 41, SO ( k ) = 2 …………………………………………………………………………
28
52 q = 42, SO ( k ) = 2 …………………………………………………………………………
28
53 q = 43, SO ( k ) = 2 …………………………………………………………………………
28
54 q = 44, SO ( k ) = 2 …………………………………………………………………………
28
55 q = 45, SO ( k ) = 2 …………………………………………………………………………
28
56 q = 46, SO ( k ) = 2 …………………………………………………………………………
28
57 q = 47, SO ( k ) = 2 …………………………………………………………………………
28
58 q = 48, SO ( k ) = 2 …………………………………………………………………………
29
59 q = 49, SO ( k ) = 2 …………………………………………………………………………
29
60 q = 50, SO ( k ) = 2 …………………………………………………………………………
29
61 Kemungkinan Kombinasi Path yang Menghasilkan Solusi Optimal …………………….
37
DAFTAR LAMPIRAN Halaman 1 2 3 4
Contoh Arus Pergerakan Paket ………………………………………………………….. RP0 ……………………………………………………………………………………… RP1 ………………………………………………………………………………………. RP2 ………………………………………………………………………………………
22 32 33 34
5
RP3 ……………………………………………………………………………………….
35
