VEHICLE ROUTING PROBLEM WITH SIMULTANEOUS PICKUP AND DELIVERY MENGGUNAKAN ALGORITMA TABU SEARCH UNTUK MEMINIMALKAN RUTE TRANSPORTASI (Studi Kasus Pada “UD. Parama Ma’ruf”) Skripsi Diajukan Kepada Universitas Muhammadiyah Malang Untuk Memenuhi Salah Satu Persyaratan Akademik Dalam Menyelesaikan Program Sarjana Teknik
Disusun Oleh :
WIDI PURWO SAPUTRO 201010140311117
JURUSAN TEKNIK INDUSTRI FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH MALANG (2016) i
ii
iii
iv
v
vi
vii
viii
KATA PENGANTAR
Puji syukur alhamdulillah Penulis panjatkan kehadirat Allah SWT atas berkat, rahmat, taufik dan hidayah-Nya, penyusunan skripsi yang berjudul “Vehicle Routing Problem With Simultaneous Pickup And Delivery Menggunakan Algoritma Tabu Search Untuk Meminimalkan Rute Transportasi (Studi Kasus Pada UD. Parama Ma’ruf)” dapat diselesaikan dengan baik. Penulis menyadari bahwa dalam proses penulisan skripsi ini banyak mengalami kendala, namun berkat bantuan, bimbingan, kerjasama dari berbagai pihak dan berkah dari Allah SWT sehingga kendala-kendala yang dihadapi tersebut dapat diatasi. Oleh karena itu Penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada Ibu Annisa Kesy Garside, S.T., M.T. selaku pembimbing I dan Bapak Teguh Baroto, S.T., M.T. selaku pembimbing II yang telah dengan sabar, tekun, tulus, dan ikhlas meluangkan waktu, tenaga, dan pikiran memberikan bimbingan, motivasi, arahan, dan saran-saran yang sangat berharga kepada penulis selama menyusun skripsi.
Selanjutnya ucapan terima kasih penulis sampaikan pula kepada: 1. Bapak Drs. H Fauzan MPd selaku Rektor Universitas Muhammadiyah Malang. 2. Bapak Ir. Sudarman, MT selaku Dekan Fakultas Teknik Universitas Muhammadiyah Malang. 3. Bapak Ilyas Mas’udin, Ph.D selaku ketua Jurusan Teknik Industri Universitas Muhammadiyah Malang yang telah memberikan dorongan dan semangat untuk segera menyelesaikan penyusunan skripsi ini. 4. Bapak Dana Marsetiya Utama, ST., MT dan Ibu Dian Palupi Restuputri, S.T., M.T. selaku dosen penguji skripsi, yang telah memberikan masukan yang sangat berguna untuk memperbaiki penyusunan skripsi ini.
ix
5. Ibu Shanty Kusuma Dewi, ST., MT selaku koordinator skripsi yang telah meluangkan waktunya untuk memberikan saran kepada penulis selama proses perkuliahan hingga penyelesaian tugas akhir ini. 6. Bapak dan Ibu Dosen Jurusan Teknik Industri Universitas Muhammadiyah Malang yang telah memberi bekal ilmu pengetahuan sehingga penulis dapat menyelesaikan studi dan menyelesaikan penulisan skripsi ini. 7. Mas eko selaku owner UD. Parama Ma’ruf yang telah mengizinkan dan membantu penulis untuk melakukan penelitian dalam rangka penyelesaian penulisan skripsi ini. 8. Ibunda Wiwik Murtiningsih dan Ayahanda Susanto yang sangat banyak memberikan bantuan moril, materil, arahan, dan selalu mendoakan keberhasilan dan keselamatan selama menempuh pendidikan. 9. Saudara tercinta (Mba Kiki Desiani, Mba Chusnul Chotimah, Neng Ma’rifatul Kholifah) atas dukungan, semangat, dan kasih sayang yang diberikan kepada penulis. 10. Rekan–rekan
Mahasiswa
Teknik
Industri
2010
Universitas
Muhammadiyah Malang yang sudah penulis anggap sebagai saudara yang telah menemani penulis didalam kehidupan kampus, memberi warna baru pada kehidupan penulis, banyak memberikan masukan dan dorongan semangat kepada penulis baik selama dalam mengikuti perkuliahan maupun dalam penulisan skripsi ini. 11. Rekan-rekan
Alumni
Muhammadiyah
Malang
Mahasiswa yang
telah
Teknik
Industri
memberikan
Universitas
masukan
dan
pengelamannya selama perkuliahan. 12. Keluarga besar LAB TI UMM yang telah memeberikan banyak pengalaman, dorongan, dan masukan kepada penulis selama proses perkuliahan sampai sekarang. 13. Keluarga besar LAB MATC UMM yang telah memeberikan banyak pengalaman, dorongan, dan masukan kepada penulis selama proses perkuliahan sampai sekarang.
x
14. Rekan-rekan setempat tinggal di asrama Al-Hilal yang selalu memberi semangat dan hiburan selama proses perkuliahan sampai sekarang. 15. Semua pihak yang tidak dapat penulis sebut satu persatu yang telah membantu dalam penyelesaian penulisan skripsi ini.
Akhir kata, dengan segala kerendahan hati penulis menyadari masih banyak terdapat kekurangan-kekurangan pada tugas akhir ini, sehingga penulis mengharapkan adanya saran dan kritik yang bersifat membangun demi kesempurnaan skripsi ini. Semoga tugas akhir ini dapat memeberikan manfaat bagi penulis dan pembaca.
Malang, 2 Mei 2016 Penulis
Widi Purwo Saputro
xi
DAFTAR ISI halaman Halaman Sampul Skripsi ............................................................................... i Lembar Pengesahan Skripsi ......................................................................... ii Surat Pernyataan Keaslian .......................................................................... iii Kata Pengantar ............................................................................................ iii Abstrak ..........................................................................................................vi Daftar Isi .......................................................................................................vi Daftar Tabel ............................................................................................... viii Daftar Gambar .............................................................................................ix BAB I PENDAHULUAN .......................................................................... 1 1.1 Latar Belakang ...................................................................................... 1 1.2 Rumusan Masalah ................................................................................. 2 1.3 Tujuan Penelitian .................................................................................. 2 1.4 Manfaat Penelitian ................................................................................. 2 1.5 Batasan Masalah dan Asumsi................................................................. 2 1.6 Sistematika Penulisan ............................................................................ 3 BAB II LANDASAN TEORI...................................................................... 5 2.1 Distribusi .............................................................................................. 5 2.1.1. Saluran Distribusi ......................................................................... 6 2.1.2. Perantara Saluran (Penyetor) ......................................................... 6 2.2 Vehicle Routing Problem (VRP) ............................................................ 8 2.3 Vehicle Routing Problem With Simultaneous Pick-up and Delivery (VRPSPD) .......................................................................................... 12 2.3.1. Formulasi Matematika VRPSPD ................................................. 13 2.4 Algoritma Tabu Search ....................................................................... 15 2.5 Algoritma Tabu Search Untuk VRPSPD............................................. 16 BAB III METODOLOGI PENELITIAN .................................................. 27 3.1 Flowchart Penelitian .............................................................................. 27 3.2 Deskripsi Flowchart .............................................................................. 27 BAB IV PENGUMPULAN DAN PENGOLAHAN DATA ...................... 30 4.1 Tinjauan Perusahaan .............................................................................. 30 4.2 Pengumpulan Data ................................................................................. 30 4.2.1. Data Kendaraan ......................................................................... 30 4.2.2. Data Permintaan ........................................................................ 31 4.2.3. Data Jarak ................................................................................. 31 4.2.4. Data Rute Aktual Perusahaan .................................................... 32 4.3 Pengolahan Data .................................................................................... 32 BAB V ANALISA PEMBAHASAN......................................................... 46 5.1 Analisa Sistem Rute Pendistribusian pada Perusahaan ........................... 46 5.2 Analisa Hasil Rute Menggunakan Algoritma Tabu Search ..................... 47
xii
BAB VI PENUTUP .................................................................................... 49 6.1 Kesimpulan ........................................................................................... 49 6.2 Saran ..................................................................................................... 49 DAFTAR PUSTAKA ................................................................................... 50
xiii
DAFTAR TABEL Tabel
Halaman
4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8
Permintaan ............................................................................................ 31 Matrix Jarak .......................................................................................... 31 Grup dan rute kendaraan awal ............................................................... 32 Rute dan jarak solusi awal berdasarkan IGR1 ...................................... 33 Jalur dan jarak solusi neighborhood pada iterasi ke-2............................ 35 Jalur dan jarak solusi neighborhood pada iterasi ke-3............................ 36 Jalur dan jarak solusi neighborhood pada iterasi ke-4............................ 38 Frekuensi penggunaan sisi pada 4 iterasi pertama dengan nilai awal menggunakan IGR1 .............................................................................. 40 4.9 Nilai eco_movei 2-opt untuk move yang fisibel ..................................... 41 4.10 Jalur dan jarak dari solusi neighborhood pada fase intensifikasi ............ 42 4.11 Nilai eco_moved 2-opt untuk move yang fisibel ..................................... 43 4.12 Jalur dan jarak dari solusi neighborhood pada fase diversifikasi ............ 43 5.1 Rute aktual pendistribusian pada perusahaan......................................... 46
xiv
DAFTAR GAMBAR Gambar 2.1 2.2 2.3 2.4 2.5 2.6 3.1 4.1 4.2 4.3 4.4 4.5 4.6
Halaman
Vehicle Routing Problem......................................................................... 9 Mekanisme Umum Tabu Search ........................................................... 16 Relokasi ................................................................................................ 19 Interchange........................................................................................... 20 Crossover ............................................................................................. 20 2-opt ..................................................................................................... 21 Flowchart Penelitian ............................................................................. 29 Rute solusi awal menggunakan IGR1 .................................................... 33 Solusi awal dan solusi move crossover .................................................. 34 Solusi dari iterasi ke 2 dan solusi move crossover ................................. 36 Solusi dari iterasi ke 2 dan solusi move relokasi .................................... 38 Solusi dari iterasi ke 4 dan solusi move intensifikasi .............................. 41 Solusi dari iterasi ke 4 dan solusi move diversifikasi ............................. 44
xv
DAFTAR PUSTAKA
Abbas, Salim, 1998. Manajemen Transportasi. Jakarta: Penerbit Raja Grafindo Persada. Baldacci, R., Battara, M. dan Vigo, D. 2008. Routing a Heterogeneous Fleet of Vehicles, dalam The Vehicle Routing Problem; Latest Advances and New Chalenges, Operation Research/Computer Sciences Interfaces, edn. Golden, B., Raghaven, S., and Wasil, E., Springer Science and Bussines Media, LLC, New York. Chopra, Sunil and meindl, Peter. 2004. Supply Chain Management; Strategy Planning, and Operation, 2nd Edition, Prectice Hall, Upper Saddle River, NY. Glover F, Laguna M. 1997. Tabu Search. Boston (US): Kluwer Academic. Golden, B., Raghaven S., dan Wasil, E. 2008. The Vehicle Routing Problem; Latest Advances and Challenges. Springer. Haksever, Lengiz, Render, Barry, Russel, Roberta S., dan Murdick, Robert G. 2000. Service Management and Operations, 2nd edn, Prentice Hall, Inc. Idaman,
Syukrio.
2013.
Penyelesaian
Vehicle
Routing
Problem
With
Simultaneous Pick-Up and Delivery Service Menggunakan Algoritme Tabu Search. Skripsi Jurusan Matematika, Institut Pertanian, Bogor. IDSIA Instituto Dalle Molle di Studi sull Intelegensia Artificiale. 2007. Vehicle Routing Problem. Http://www.idsia.ch/. Tanggal akses: 12 Desember 2007. Kotler,
Philip.
1991.
Manajemen
Pemasaran,
Analisis,
Perencanaan,
Implementasi, dan Pengendalian. Jakarta: Erlangga. Kumar, S. N. dan Panneerselvam, R. 2012. A Survey On The Vehicle Routing Problem and Its Variants. Intellegent Information Management. Lambert, D.M., Stock, J.R., 2001. Strategic Logistic Manajement, Fourth Edition, Mc Graw Hill, New York – USA. Montane FAT, Galvao RD. 2006. A tabu search algorithm for the vehicle routing
xvi
problem with simultaneous pick-up and delivery service. Computer & Operations Research. 33:595-619. Doi:10.1016/j.cor.2004.07.009. Nasution. 2004. Manajemen Transportasi (Edisi Kedua). Jakarta: Penerbit Ghalia Indonesia. Pradhana FE, Sugiharti E, Kharis M. 2012. Penerapan algoritma tabu search untuk menyelesaikan vehicle routing problem. UJM. 1(1):1-6. Schneider U. 2011. A tabu search tutorial based on a real-world scheduling problem. CEJOR. 19:467-493. Doi:10.1007/s10100-010-0137-8. Toth, Paolo and Vigo, D., 2002. Vehicle Routing Problem, SIAM, Philadelphia, USA.
xvii
