PERMASALAHAN P-HUB MEDIAN DENGAN LINTASAN TERPENDEK
SKRIPSI
RAJA DAVID PASARIBU 080803039
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
UNIVERSITAS SUMATERA UTARA
PERMASALAHAN P-HUB MEDIAN DENGAN LINTASAN TERPENDEK SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar sarjana sains
RAJA DAVID PASARIBU 080803039
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
UNIVERSITAS SUMATERA UTARA
ii
PERSETUJUAN
Judul Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
:PERMASALAHAN P-HUB MEDIAN DENGAN LINTASAN TERPENDEK : SKRIPSI : RAJA DAVID PASARIBU : 080803039 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, Juli 2012
Komisi Pembimbing
:
Pembimbing 2
Prof. Dr. Herman Mawengkang NIP 19461128 1974031 001
Pembimbing 1
Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D. NIP 196209011988031002
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua.
Prof. Drs. Tulus, Vordipl.Math, M.Si, Ph.D. NIP 196209011988031002
UNIVERSITAS SUMATERA UTARA
iii
PERNYATAAN
PERMASALAHAN P-HUB MEDIAN DENGAN LINTASAN TERPENDEK SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Juli 2012
RAJA DAVID PASARIBU 080803039
UNIVERSITAS SUMATERA UTARA
iv
PENGHARGAAN
Puji dan syukur penulis hanturkan ke hadirat Tuhan Yang Maha Kuasa Atas rahmat dan karuniaNya sehingga dengan kemampuan yang terbatas penulis dapat menyelesaikan penulisan tugas akhir ini.
Tugas akhir ini dibuat dan diajukan sebagai salah satu syarat untuk menempuh ujian sarjana matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara.
Penulis
menyadari
sepenuhnya
keterbatasan
ilmu
pengetahuan
dan
kemampuan penulis, sehingga tugas akhir ini masih jauh dari sempurna. Untuk itu, segala saran dan kritik dari pembaca tugas akhir ini sangat penulis harapkan demi kesempurnaan tugas akhir ini.
Dalam penulisan berbagai pihak dan pada
tugas
akhir ini, penulis telah banyak dibantu oleh
kesempatan ini
penulis mengucapkan banyak terima
kasih kepada :
1. Bapak Prof. Drs. Tulus, Vordipl.Math., M.Si., Ph.D, selaku dosen pembimbing I dan Bapak Prof. Dr. Herman Mawengkang, selaku dosen pembimbing II, yang telah memberikan masukan dan pengarahan serta bimbingan kepada penulis selama penulisan tugas akhir ini.
2. Bapak Drs. Sawaluddin, M.IT dan Bapak Syahril Efendi, S.Si., M.IT selaku dosen penguji saya. 3. Bapak
Prof.
Drs. Tulus, Vordipl.Math., M.Si., Ph.D dan
Ibu
Dra. Mardiningsih M.Si selaku ketua dan sekretaris jurusan Matematika FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM.
UNIVERSITAS SUMATERA UTARA
v
4. Bapak Dekan serta seluruh staf pengajar jurusan Matematika. 5. Rekan-rekan mahasiswa jurusan Matematika khususnya angkatan β08 yang telah memberi banyak masukan bagi penulis terkhusus untuk Hasoloan, Geta, Eve dan Melda. 6. Teman teman KTB βFuzzyβ : Sardes, Indra, Charles, Lukas, Anri, Wilser dan Kak Tiur yang banyak memberi semangat dan dorongan bagi penulis selama pengerjaan tulisan ini. 7. Ayahanda M. PASARIBU, ibunda G.HUTAGALUNG, kakak saya RINA WATY PASARIBU, serta adik-adik saya RIFKA dan REYNOLD yang memberi segala bantuan, dorongan dan semangat kepada saya.
Kiranya Tuhan Yang Maha Kuasa melimpahkan rahmat dan kasihnya atas segala jerih payah, bantuan serta pengorbanan yang telah diberikan oleh semua pihak dalam membantu penulisan selama ini.
Medan,
Juli 2012
Penulis
RAJA DAVID PASARIBU
UNIVERSITAS SUMATERA UTARA
vi
ABSTRAK
Hub merupakan fasilitas yang bertugas melayani pengurutan (sorting), pemilihan (switching), pemindahan dari satu angkutan ke angkutan lainnya (transshipment) di dalam jaringan transportasi barang. Permasalahan p-hub median termasuk permasalahan lokasi-alokasi kasus diskrit dimana semua hub terhubung penuh. Di dalam tugas akhir ini akan diperkenalkan model formulasi biaya model Mixed Integrer Linear Programming (MILP) untuk persolan p-hub median alokasi tunggal tak berkapasitas (uncapacitaced single allocation p-hub median) disingkat USApHMP. Selanjutnya akan diperkenalkan algoritma lintasan terpendek FloydWarshall dalam menyelesaikan permasalahan p-hub median serta algoritma penentuan batas bawah untuk permasalahan p-hub median Kata kunci: Hub, Simpul Spoke, Mixed Integrer Linear Programming (MILP), uncapacitaced single allocation p-hub median (USApHMP)
UNIVERSITAS SUMATERA UTARA
vii
P-HUB MEDIAN PROBLEMS BASED ON SHORTEST PATH
ABSTRACT
Hub are facilities that serve as sorting, switching, and transhipment in a transportation network. P-hub median problem is a discrete case location allocation problem which all hub is fully connected. In this paper will be intoduced Mixed Integrer Linear Programming (MILP) formulation models of cost for p-hub median problem allocation for uncapacitaced single allocation p-hub median(USApHMP). In this paper also introduced Floyd-Warshall shortest path algorithm to solve p-hub median problems and lower bounds algorithm for p-hub median problems. Keywords: Hub, Spoke Nodes, Mixed Integrer Linear Programming (MILP), uncapacitaced single allocation p-hub median (USApHMP)
UNIVERSITAS SUMATERA UTARA
viii
DAFTAR ISI
Halaman Persetujuan
ii
Pernyataan
iii
Penghargaan
iv
Abstrak
vi
Abstract
vii
Daftar Isi
viii
Daftar Tabel
x
Daftar Gambar
xi
Bab 1 Pendahuluan 1.1 1.2 1.3 1.4 1.5 1.6 1.7
Latar Belakang Perumusan Masalah Batasan Masalah Tinjauan Pustaka Tujuan Penelitian Kontribusi Penelitian Metode Penelitian
1 3 3 3 6 6 7
Bab 2 Landasan Teori 2.1
2.2
Beberapa Konsep Dasar Graf 2.1.1 Ketetanggaan 2.1.2 Graf Berbobot 2.1.3 Representasi Graf 2.1.4 Matriks Ketetanggaan (Adjacency Matriks) 2.1.5 Matriks Bersisian (Incidency Matriks)
8 9 10 10 10 11
2.1.6 Senarai ketetanggaan (Adjacency list)
12
Masalah Lintasan Terpendek (Shortest Path Problem)
12
UNIVERSITAS SUMATERA UTARA
ix
2.3 2.4 2.5 2.6
2.7
2.2.1 Pencarian Lintasan Terpendek 2.2.2 Penggolongan Algoritma Shortest Finding Secara Umum Program Linear Program Integrer Masalah Lokasi Hub
15 15 15 17 21
Ciri-Ciri Jaringan Hub dan Spoke 2.6.1 Keuntungan Hub 2.6.2 Kerugian Hub Jenis Masalah Lokasi Hub
24 24 26 28
2.7.1 Alokasi Single vs. Multiple
28
2.7.2 Kapasitas (Capacitaced) Formulasi Tata Nama Permasalahan Hub
29 29
2.8
Bab 3 Pembahasan 3.1 3.2 3.3 3.4 3.5
Permasalahan p-Hub Median Masalah Alokasi Tunggal p-Hub Median (Single Allocation p-hub Median Problem/USApHMP) Masalah alokasi jamak p-hub median (Multiple Allocation phub Median Problem/UMApHMP) Algoritma Lintasan Terpendek dalam p-Hub Median Penerapan Lintasan Terpendek dalam Permasalahan p-Hub Median
31 32 34 36 37
Bab 4 Kesimpulan dan Saran 4.1 4.2 Daftar Pustaka
Kesimpulan Saran
48 48 49
UNIVERSITAS SUMATERA UTARA
x
DAFTAR TABEL Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5 Tabel 3.6 Tabel 3.7 Tabel 3.8 Tabel 3.9 Tabel 3.10 Tabel 3.11 Tabel 3.12
Jarak Antar Kota (Dalam Km) β Tabel penghitungan πΆππ untuk simpul hub k = 4, dan l = 5, 7 β Tabel penghitungan πΆππ untuk simpul hub k = 5, dan l = 4, 7 β Tabel penghitungan πΆππ untuk simpul hub k = 7, dan l = 4, 5 Tabel penghitungan πΆππβ untuk nonhub i = 1, dan simpul hub k = 4, 5, 7 Tabel penghitungan πΆππβ untuk nonhub i = 2, dan simpul hub k = 4, 5, 7 Tabel penghitungan πΆππβ untuk nonhub i = 3, dan simpul hub k = 4, 5, 7 Tabel penghitungan πΆππβ untuk nonhub i = 6, dan simpul hub k = 4, 5, 7 Tabel penghitungan πΆππβ untuk nonhub i = 8, dan simpul hub k = 4, 5, 7 Tabel penghitungan πΆππβ untuk nonhub i = 9, dan simpul hub k = 4, 5, 7 Tabel penghitungan πΆππβ untuk nonhub i = 10, dan simpul hub k = 4, 5, 7 Tabel Pasangan Lintasan Terpendek dari Pasangan Simpul Asal ke Simpul Tujuan Tertentu
38 39 40 41 41 42 43 43 44 44 45 45
UNIVERSITAS SUMATERA UTARA
xi
DAFTAR GAMBAR
Gambar 1.1 Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 2.7 Gambar 2.8 Gambar 2.9 Gambar 2.10 Gambar 3.1 Gambar 3.2
Sistem Hub dan Spoke Graf Tak berarah Graf Berarah Graf Ketetanggaan Graf Berbobot Graf Ketetanggaan Graf Matriks Bersisian Graf Terbobot 7 Kota di Amerika Tipikal Masalah Jaringan Lokasi Hub Jaringan Transportasi Klasik Skema Penugasan dalam Permasalahan Lokasi Hub Gambar aliran biaya dari simpul i ke simpul tujuan j melalui hub k dan l Jaringan p-hub median yang menghubungkan 10 kota
1 8 9 9 10 11 11 14 22 24 29 35 47
UNIVERSITAS SUMATERA UTARA
