MODEL PERSOALAN RUTE TERBUKA KENDARAAN DENGAN KETERBATASAN WAKTU DAN ADANYA PERSINGGAHAN
TESIS
Oleh AGHNI SYAHMARANI 107021008/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universita Sumatera Utara
MODEL PERSOALAN RUTE TERBUKA KENDARAAN DENGAN KETERBATASAN WAKTU DAN ADANYA PERSINGGAHAN
TESIS
Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Oleh AGHNI SYAHMARANI 107021008/MT
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2012
Universita Sumatera Utara
Judul Tesis
: MODEL PERSOALAN RUTE TERBUKA KENDARAAN DENGAN KETERBATASAN WAKTU DAN PERSINGGAHAN Nama Mahasiswa : Aghni Syahmarani Nomor Pokok : 107021008 Program Studi : Magister Matematika
Menyetujui, Komisi Pembimbing
(Prof. Dr. Saib Suwilo, MSc) Ketua
(Prof. Dr. Opim Salim S, MSc) Anggota
Ketua Program Studi
Dekan
(Prof. Dr. Herman Mawengkang)
(Dr. Sutarman, MSc)
Tanggal lulus: 17 Desember 2012
Universita Sumatera Utara
Telah diuji pada Tanggal 17 Desember 2012
PANITIA PENGUJI TESIS Ketua : Anggota :
Prof. Dr. Saib Suwilo, MSc 1. Prof. Dr. Opim Salim S, MSc 2. Prof. Dr. Herman Mawengkang 3. Dr. Yulita Molliq, M.Sc
Universita Sumatera Utara
PERNYATAAN
MODEL PERSOALAN RUTE TERBUKA KENDARAAN DENGAN KETERBATASAN WAKTU DAN ADANYA PERSINGGAHAN
TESIS
Dengan ini saya menyatakan bahwa di dalam tesis ini tidak terdapat karya yang pernah diajukan untuk memperoleh gelar Magister di suatu perguruan tinggi dan sepanjang sepengetahuan juga tidak terdapat karya atau pendapat yang pernah ditulis atau diterbitkan oleh orang lain, kecuali secara tertulis diacu dalam naskah ini disebutkan dalam daftar pustaka.
Medan, 17 Desember 2012 Penulis,
Aghni Syahmarani
i Universita Sumatera Utara
ABSTRAK Open vehicle routing problem (OVRP) merupakan versi lain dari Vehicle Routing Problem (VRP) dimana rute kendaraannya terbuka, artinya kendaraan tersebut tidak perlu kembali ke depot, ataupun jika dibutuhkan untuk kembali, kendaraan akan mengunjungi rute yang sama dengan rute awal keberangkatannya. Penelitian ini mengambil salah satu kasus OVRP dengan kendala keterbatasan waktu ditambah dengan adanya persinggahan kendaraan (Open Vehicle Routing Problem with Time Windows and Driver Stopping/ OVRPTWDS). Model OVRPTWDS dikembangkan dari model Open Vehicle Routing Problem with Time Windows (OVRPTW) dengan penambahan kendala waktu istirahat yang dilakukan selama proses distribusi. Kerangka dasar dari pemodelan ini adalah NP-Hard.
Kata kunci: VRP, OVRP, OVRPTW, NP-Hard
ii Universita Sumatera Utara
ABSTRACT The open vehicle routing problem (OVRP) is another version of the vehicle routing problem (VRP) with open routes, in which the vehicles are not required to return to the depot, but if they do, it must be by revisiting the customers assigned to them in the reverse order. This research takes one of OVRP cases which constrains are time windows under driver stopping (Open Vehicle Routing Problem with Time Windows and Driver Stopping/ OVRPTWDS). The OVRPTWDS developed by Open Vehicle Routing Problem with Time Windows (OVRPTW) model by adding driver stopping times in distribution process. The basic framework of the model is NP-hard.
Keyword: VRP, OVRP, OVRPTW, NP-Hard.
iii Universita Sumatera Utara
KATA PENGANTAR Setinggi puji dan sedalam syukur penulis serahkan kehadirat Allah SWT yang telah memberikan berkat dan rahmadNya sehingga penulis dapat menyelesaikan tesis yang berjudul ”PERSOALAN RUTE TERBUKA KENDARAAN DENGAN KETERBATASAN WAKTU DAN ADANYA PERSINGGAHAN”. Tesis ini merupakan salah satu syarat untuk menyelesaikan studi pada Program Studi Magister Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Universitas Sumatera Utara. Pada kesempatan ini, penulis menyampaikan terimakasih sebesar-besarnya kepada : Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc(CTM), Sp.A(K) selaku Rektor Universitas Sumatera Utara Dr. Sutarman, M.Sc selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) Universitas Sumatera Utara. Prof. Dr. Herman Mawengkang selaku Ketua Program Studi Magister Matematika FMIPA USU yang telah banyak memberikan bantuan dalam penulisan tesis ini. Prof. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Studi Magister Matematika FMIPA USU dan selaku Pembimbing Utama yang telah banyak memberikan bimbingan dan arahan serta motivasi kepada penulis dalam penulisan tesis ini. Prof. Dr. Opim Salim S, M.Sc selaku Pembimbing Kedua yang juga telah banyak memberikan bimbingan kepada penulis dalam penulisan tesis ini. Seluruh Staf Pengajar pada Program Studi Magister Matematika FMIPA USU yang telah banyak memberikan ilmu pengetahuan selama masa perkuliahan. Kakanda Misiani, S.Si selaku Staf Administrasi Program Studi Magister Matematika FMIPA USU yang telah banyak memberikan pelayanan yang baik kepada penulis selama mengikuti perkuliahan. Seluruh rekan-rekan Mahasiswa Program Studi Magister Matematika FMIPA iv Universita Sumatera Utara
USU tahun 2010 genap (Rina, Dhia, Lena, Novi, Kak Vivi, Amin, Agusmanto, Bang Zul, Bang Hindra dan Bang Ronal) yang telah memberikan bantuan moril dan dorongan kepada penulis dalam penulisan tesis ini. Tak lupa penulis mengucapkan terimakasih sebesar-besarnya dan penghargaan setinggi-tingginya kepada ibunda tercinta Marhamah Kamal, BA dan ayahanda Ahmad Syahruddin, S.PdI yang mencurahkan kasih sayang dan dukungan kepada penulis, terlebih yang dengan setia mendampingi dan membantu penulis selama mengikuti perkuliahan hingga sampai penulisan tesis ini. Tak lupa pula kepada adik-adikku Ahmad Qawiy Syahmara, Desi Fatwani, Mia Maysura dan Ahmad Zakiy Syahmara yang telah memberikan semangat selama penulisan tesis ini. Terima kasih juga buat Yusrizal, S.KG yang telah memberikan semangat dan dorongan kepada penulis dalam penulisan tesis ini. Terima kasih kepada sahabat-sahabatku serta rekan-rekan lainnya yang tidak dapat disebutkan satu-persatu. Semoga Allah SWT memberikan balasan atas jasa-jasa mereka yang telah diberikan kepada penulis. Penulis menyadari bahwa tesis ini masih jauh dari sempurna, untuk itu penulis mengharapkan kritik saran untuk penyempurnaan tesis ini. Semoga tesis ini dapat bermanfaat bagi pembaca dan pihak-pihak lain yang memerlukannya. Terimakasih.
Medan,
Desember 2012
Penulis, Aghni Syahmarani
v Universita Sumatera Utara
RIWAYAT HIDUP Aghni Syahmarani dilahirkan di Medan pada tanggal 9 Desember 1987 dari pasangan Bapak Ahmad Syahruddin, S.PdI & Ibu Marhamah Kamal,BA. Penulis menamatkan pendidikan Sekolah Dasar 094109 Raya Pinantar, Kecamatan Raya, Kabupaten Simalungun tahun 2000, Sekolah Menengah Pertama (SMP) Negeri 9 Medan tahun 2003, Sekolah Menengah Atas (SMA) Negeri I Medan tahun 2006. Pada tahun 2006 memasuki Perguruan Tinggi Universitas Sumatera Utara fakultas MIPA jurusan Matematika pada Strata Satu (S-I) dan lulus tahun 2010. Pada tahun 2011, penulis melanjutkan pendidikan pada Program Studi Magister Matematika Universitas Sumatera Utara. September 2011, penulis bekerja sebagai staf pengajar di Universitas Quality di jurusan pendidikan matematika. Kemudian pada Oktober 2011, penulis dipercayakan sebagai asisten laboratorium komputer D3 Statistika Universitas Sumatera utara. Penulis juga dipercaya sebagai asisten dosen di Universitas Sumatera Utara dan beberapa Universitas Swasta di Medan sampai sekarang.
vi Universita Sumatera Utara
DAFTAR ISI Halaman PERNYATAAN
i
ABSTRAK
ii
ABSTRACT
iii
KATA PENGANTAR
iv
RIWAYAT HIDUP
vi
DAFTAR ISI
vii
BAB 1 PENDAHULUAN
1
1.1 Perumusan Masalah
3
1.2 Tujuan Penelitian
3
1.3 Manfaat Penelitian
3
1.4 Metode Penelitian
4
BAB 2 TINJAUAN PUSTAKA
5
BAB 3 MODEL-MODEL VEHICLE ROUTING PROBLEM DAN OPEN VEHICLE ROUTING PROBLEM
8
3.1 Vehicle Routing Problem
8
3.2 Open Vehicle Routing Problem
11
3.3 Beberapa Model Open Vehicle Routing Problem
13
BAB 4 PERSOALAN RUTE TERBUKA KENDARAAN DENGAN KETERBATASAN WAKTU DAN ADANYA PERSINGGAHAN 19 BAB 5 KESIMPULAN
25
DAFTAR PUSTAKA
27
vii Universita Sumatera Utara
