1
BAB 1 PENDAHULUAN 1.1. Latar Belakang Persoalan rute terpendek merupakan suatu jaringan pengarahan rute perjalanan di mana seseorang pengarah jalan ingin menentukan rute terpendek antara dua kota berdasarkan rute alternatif yang tersedia yang biasanya terdiri dari satu atau beberapa kota tujuan. Masalah ini umumnya menggunakan representasi graph untuk memodelkan persoalan yang diwakili sehingga lebih memudahkan penyelesaiannya. Masalahnya adalah bagaimana cara mengunjungi vertek pada graph dari vertek awal ke vertek akhir dengan bobot minimum, dalam hal ini bobot yang digunakan adalah jarak dan kota-kota yang dikunjungi diasumsikan sebagai vertek yang saling terhubung. Masalah rute terpendek suatu masalah klasik yang sering dijumpai dalam kehidupan sehari-hari di berbagai sektor kehidupan, antara lain di bidang transportasi, komunikasi dan komputasi. Masalah ini menjadi masalah yang penting karena berkaitan dengan masalah meminimumkan biaya dan efisiensi waktu yang dibutuhkan. Masalah rute terpendek untuk semua pasangan vertek adalah masalah menentukan
lintasan
terpendek
untuk
setiap
vertek
yang
ada,
dengan
mengoptimalkan fungsi tujuan (objektif) tertentu. Dalam pengiriman barang dari suatu tempat ke tempat yang lain, tempat tujuan pengiriman barang sangat bervariasi, begitu juga kendaraan pengangkut baik dari darat, laut, ataupun udara dengan mempertimbangkan efisiensi waktu dan biaya. Untuk itu diperlukan ketepatan dalam menentukan jalur atau rute untuk menentukan tujuan kendaraan pengangkut yang akan dituju. Dengan tersedianya kendaraan lebih dari satu untuk melayani tempat-tempat pengiriman barang yang akan dituju berarti menambah permasalahan dalam pendistribusian barang karena mungkin ada beberapa
2
kendaraan pengangkut yang digunakan secara bersama untuk melayani tempat-tempat tersebut. Jalur-jalur yang terbentuk memiliki tingkat efisiensi masing-masing. Pendistribusian barang yang terdiri dari beberapa kendaraan yang indentik dikenal dengan metode Vehicle Routing Problem atau disebut dengan VRP, pertama kali diperkenalkan pada tahun 1959 oleh Dantzig dan Ramser, menurut mereka VRP adalah suatu masalah di mana sebuah set rute akan dibentuk dari sejumlah verteks atau konsumen dengan banyak kendaraan yang disediakan di depot (vertek awal). Adapun setiap konsumen hanya akan dilalui oleh satu kendaraan saja dan kendaraan kembali lagi ke depot. Pendistribusian barang yang terdiri dari satu kendaraan dikenal dengan metode Traveling Salesman Problem atau disebut dengan TSP, diperkenalkan oleh H. Whitney dan M. Flood. TSP dinyatakan sebagai permasalahan dalam mencari jarak minimal sebuah tur tertutup terhadap sejumlah n kota di mana kota-kota yang ada hanya dikunjungi sekali dengan kota awal juga merupakan kota akhir (tujuan). Pada tahun 1969, Henry dan Lapordere memperkenalkan Traveling Generalized Salesman Problem atau biasa disebut dengan GTSP yang merupakan perluasan dari TSP dimana vertek (konsumen) dari graph tersebut dikelompokkan ke dalam kluster dan masalahnya adalah untuk menemukan biaya minimum Tur Hamiltonian setiap kluster dikunjungi tepat sekali yaitu mengunjungi satu vertek yang mewakili kluster. Pada tahun 2000, Ghiani dan Improta memperkenalkan metode baru untuk solusi persoalan dalam pendistribusian barang ke beberapa konsumen yaitu dikenal dengan Generalized Vehicle Rounting Problem dan dinotasikan dengan GVRP yang merupakan pengembangan dari metode VRP dan GTSP. GVRP dikatakan pengembangan dari metode VRP jika vertek-vertek dari VRP dipartisi menjadi sejumlah rangkaian vertek-vertek yang disebut kluster kemudian ditentukan rute yang optimal dari depot ke sejumlah kluster yang telah ditetapkan yang meliputi tepat satu vertek dari setiap kluster. GVRP dikatakan pengembangan dari metode GTSP jika
3
kendaraan yang digunakan untuk pendistribusian barang kebeberapa konsumen lebih dari satu kendaraan yang identik dan kapasitasnya terbatas. Pemecahan masalah GVRP yang dilakukan secara manual dengan mencari dan memeriksa jalur perjalanan yang terpendek tidaklah efisien, hanya akan menghabiskan tenaga dan waktu saja. Apalagi cara tersebut hanya akan efektif jika jumlah kota atau konsumennya sedikit. Jika cara tersebut diterapkan pada jumlah kota atau jumlah konsumen yang banyak maka cara tersebut tidak tepat untuk digunakan. Oleh karena itu, diperlukan algoritma yang dapat memecahkan permasalahan tersebut. Untuk menghasilkan rute yang efisien dapat digunakan metode heuristik. Metode heuristik cenderung sulit dipahami tetapi sangat handal dalam menyelesaikan masalah ini. Sulit dipahami karena banyak step-step yang harus dikerjakan untuk mendapatkan solusi yang optimal dan dikatakan handal karena dalam algoritma ini ada prosedur pencarian solusi optimal yang dilakukan berulang-ulang sampai didapatkan solusi yang optimal. Metode heuristik terdiri dari beberapa macam algoritma yang biasa digunakan. Salah satunya adalah algoritma aditif atau biasa disebut dengan algoritma enumerasi implisit. Salah satu implementasi yang dapat dihasilkan dari algoritma enumerasi implisit yang dihadapi saat ini ialah permasalahan rute kendaraan yang berhubungan dengan distribusi logistik. Masalah ini didefinisikan sebagai salah satu masalah GVRP untuk memimalisasi biaya dan armada kendaraan yang digunakan dalam mendistribusi persediaan atau barang tertentu dari depot ke beberapa konsumen dan akan kembali ke depot. Kegiatan ini dibatasi oleh kapasitas kendaraan dan permintaan tiap konsumen. Pada prakteknya tidak semua algoritma itu efektif untuk diterapkan atau diimplentasikan pada suatu masalah tertentu. Hal ini disebabkan karena setiap
4
algoritma mempunyai penampilan yang berbeda dalam penyelesaian suatu masalah. Suatu algoritma dikatakan baik jika algoritma tersebut efektif dan efisien. Algoritma yang efektif dan efisien diukur dari berapa jumlah waktu dan ruang memori yang dibutuhkan untuk menjalankanya. Kompleksitas algoritma adalah besaran yang dipakai untuk mengukur kebutuhan waktu atau ruang suatu algoritma. Semakin kecil kompleksitasnya maka semakin efisien algoritma tersebut. Studi kasus yang diterapkan untuk aplikasi adalah suatu perusahaan yang bergerak dalam produksi beberapa jenis kertas karton yang didistribusikan ke berbagai konsumen. Proses pendistribusian dilakukan dengan mengirimkan barang dari pabrik ke satu konsumen dan tidak ke beberapa konsumen. Tujuan dari penelitian ini adalah memberikan alternatif solusi agar proses pendistribusian barang lebih efisien dari kondisi saat ini. Untuk menentukan rute pengiriman barang dari pabrik ke konsumen, maka dilakukan penghitungan dan analisa dengan metode GVRP.
1.2. Rumusan Masalah Generalized vehicle Rounting Problem (GVRP) termasuk kedalam masalah umum optimasi kombinatorial maka GVRP termasuk masalah NP-Hard, sehingga sangat sulit untuk mencari solusi dari masalah ini dengan pendekatan eksak. Untuk menyelesaikan GVRP digunakan pendekatan secara heuristik. Salah satu metode heuristik yang dikenal adalah Algoritma enumerasi Implisit. Permasalahan dari Tugas Akhir ini adalah mengetahui bagaimana performa dari algoritma enumerasi implisit untuk menyelesaikan GVRP.
5
1.3. Batasan Masalah Dalam penelitian ini masalah hanya dibatasi pada permasalahan kluster disebut Generalized vehicle Rounting Problem (GVRP) Simetrik Euclidean di mana jarak antara dua vertek dan sebaliknya sama.
1.4.
Tujuan dan Manfaat Penelitian Tujuan yang ingin di capai dalam penelitian ini adalah sebagai berikut:
1. Menyusun model matematika dari masalah optimasi transportasi dengan jumlah persediaan, jumlah permintaan dan varibel keputusannya berupa variabel biner. 2. Menyelesaikan masalah optimasi transportasi dengan menggunakan algoritma aditif atau enumerasi implisit. 3. Menyusun model rute transportasi yang diimplementasikan dengan suatu graph.
Manfaat dari penelitian ini adalah sebagai berikut: 1. Menawarkan penyelesaian yang lebih mudah dalam perhitungan (sesuai dengan tujuan algoritma heuristik) untuk pencarian rute terpendek 2. Secara umum penelitian ini diharapkan dapat memberikan sumbangan terhadap ilmu pengetahuan dan menambah pengetahuan dalam bidang matematika terapan terutama optimisasi dan masalah menentukan rute terpendek. 3. Secara khusus penelitian ini diharapkan dapat memberikan gambaran tentang masalah rute terpendek dengan jumlah persediaan, jumlah permintaan, dan varibel keputusannya yang dinyatakan dengan variabel biner. 4. Metode penyelesaian dari program linier integer nol-satu yaitu algoritma enumerasi implisit yang digunakan dalam penelitian ini diharapkan dapat membantu untuk menyelesaikan masalah.
6
1.5. Tinjauan Pustaka Penelitian dalam tesis ini adalah mengkaji kembali jurnal yang ditulis oleh Kara dan Marc (2012) yang membahas tentang model matematika dari Generalized Vehicle Rounting Problem (GVRP) untuk menentukan total rute minimum yang ditempuh oleh beberapa kendaraan yang identik dalam pendistribusian barang ke beberapa konsumen yang telah ditetapkan, pendistribusian barang tersebut akan dimodelkan dalam suatu masalah optimisasi transportasi dengan jumlah persediaan, jumlah permintaan, dan variabel keputusannya berbentuk bilangan integer nol-satu karena dengan variabel nol-satu mampu memberikan keputusan rute yang akan dipilh sebagai rute optimal. Sebelum membahas definisi dan ekstensi dari GVRP sebagai metode yang memodelkan rute transportasi pendistribusian terlebih dahulu akan dibahas definisidefinisi dari graph berarah, graph berbobot dan derajat dari graph yang masingmasing dijelaskan oleh Acharjya (2009), Susanna (2012) dan Scheinerman (2006), menentukan bobot dari graph dijelaskan oleh Mutakhiro (2007). Metode GVRP merupakan generalisasi dari Vehicle Routing Problem (VRP) dan juga merupakan generalisasi dari Generalized Traveling Salesman Problem (GTSP), oleh karena itu akan dijelaskan definisi dan ekstensi dari VRP yang dijelaskan oleh Gendreau (2010) dalam papernya dan GTSP dijelaskan oleh Petrica (2007) dan juga dijelaskan oleh G. Laporte (2002)
dalam papernya yang merupakan masalah khusus dari GTSP.
Kemudian akan dijelaskan tentang definisi dan ekstensi dari GVRP yang diambil dari paper Kara dan Marc (2012) dan juga dijelaskan Petrica (2012) dalam papernya. Metode yang digunakan untuk menyelesaikan masalah tranportasi yang dimodelkan oleh GVRP dalam peneliatian ini adalah dengan mengunakan program linier integer nol-satu yang nantinya akan menghasikan variabel biner sebagai variabel keputusan yang memberikan solusi dalam kasus menentukan rute transportasi pendistribusian barang ke konsumen-konsumen yang telah ditetapkan.
7
Sebelumnya diberikan contoh ilustrasi dari program linier integer yang dijelaskan Arga, W. (1985), contoh-contoh penjelasan aplikasi program linier integer nol-satu dijelaskan oleh Arefin (2013). Untuk menentukan variabel keputusan (variabel biner) tersebut dari model GVRP yang telah dihasilkan digunakan algoritma enumerasi implisit yang dijelaskan oleh Geoffrion (1967) sedangkan definisi dari algoritma enumerasi implisit dijelaskan Taha (1996).
1.6. Metodologi Penelitian Metode yang dilakukan dalam penelitian ini adalah studi literatur dan pengolahan data. Sumber literatur diperoleh dari buku, artikel dan jurnal yang terkait dengan tema penelitian. Tahap penelitian ini dibagi menjadi tiga tahapan yaitu: Tahap pertama, mempelajari metode untuk memecahkan model matematika yang telah disusun (program linier integer nol-satu), yaitu dengan menggunakan Algorima Aditif atau biasa disebut dengan algoritma enumerasi implisit. Sehingga dari model matematika tersebut diperoleh varibel keputusan biner (integer nol-satu) yang merupakan keputusan untuk menentukan solusi optimal dari masalah yang diteliti, bernilai 1 jika rute yang bersangkutan termasuk dalam rute yang dilalui oleh mobil pendistribusian dan bernilai 0 jika rute yang bersangkutan tidak termasuk dalam rute yang dilalui oleh mobil pendistribusian. Tahap kedua, melakukan pengumpulan data yang berhubungan dengan rute yang dilalui oleh kendaraan distribusi. Adapun data-data yang dikumpulkan berupa peta lokasi pabrik dan lokasi tiap konsumen, jarak gudang ke masing-masing konsumen, jarak antar konsumen, data konsumen dan lokasi tiap konsumen, jumlah permintaan tiap konsumen, dan spesifikasi kendaraan distribusi. Kemudian dari data tersebut disusun model matematika masalah optimisasi transportasi yaitu menyusun ke model matematika Generalzed Vehicle Rounting Problem (GVRP) dengan memperhatikan jumlah persediaan, jumlah permintaan dan variabel keputusannya
8
berupa variabel biner. Adapun model matematikanya dalam bentuk program linier integer nol-satu. Tahap ketiga, membahasakan algoritma enumerasi implisit kedalam bahasa pemrograman MATLAB
dan juga
menggunakan software LINDO
untuk
mempermudah menyelesaian persoalan numerik dari model GVRP yang dihadapi.
1.7. Sistematika Penulisan Sistematika penulisan tugas akhir ini yaitu menggunakan sistematika sebagai berikut: BAB I
PENDAHULUAN
Bab ini menjelaskan tentang latar belakang masalah, tujuan dan manfaat penelitian, tinjauan pustaka, metode penelitian, dan sistematika penulisan. BAB II
DASAR TEORI
Bab ini berisi tentang penjelasan Generalized Vehicle Rounting Problem (GVRP), Vehicle Routing Problem (VRP) dan Generalized Traveling Salesman Problem (GTSP), masalah transportasi, masalah rute terpendek dan penjelasan tentang algoritma aditif atau enumerasi implisit sebagai algoritma untuk menyelesaikan masalah kasus transportasi. BAB III
MODEL MATEMATIKA GVRP DAN EKSTENSINYA
Bab ini, membahas pembentukan model matematika GVRP ke dalam model program linier integer nol-satu yang dapat dimodelkan dari basis vertek dan basis alur. Selanjutnya dibahas tentang beberapa model-model ekstensinya yaitu ketika permintaan kluster sama dengan satu yang disebut dengan GMTSP, ketika jumlah kendaraan distribusi sama dengan satu yang disebut dengan GTSP. Terakhir dijelaskan tentang model CGVRP yang bertujuan untuk menentukan rute optimal
9
semua vertek yang ada di dalam kluster. Selanjutnya diberikan contoh simulasi numerik pendistribusian barang yang diselesaikan dengan metode GVRP dan dilanjutkan dengan metode CGVRP. BAB IV
STUDI KASUS: PENDISTRIBUSIAN KERTAS KARTON
Bab ini, membahas simulasi numerik untuk menentukan rute terpendek yang dilakukan untuk pendistribusian kertas karton adapun data-data yang diperlukan berupa data jarak depot ke setiap konsumen, jarak tiap konsumen, permintaan tiap konsumen, kapasitas kendaraan yang digunakan dalam pendistribusian. Selanjutnya dilakukan perbandingan hasil rute terpendek dengan metode yang dilakukan dengan metode-metode yang telah melakukan penelitian-penelitian sebelumnya. BAB V
PENUTUP
Bab ini, membuat kesimpulan, saran dan arah penelitian lanjutan.
