1
ALGORITMA SEQUENTIAL INSERTION UNTUK MENYELESAIKAN MASALAH MULTIPLE TRIP VEHICLE ROUTING PROBLEM (MTVRP) Nine Winda Yunita1, Sapti Wahyuningsih2, dan Darmawan Satyananda3 Universitas Negeri Malang E-mail:
[email protected] Abstrak: Multiple Trip Vehicle Routing Problem (MTVRP) adalah
permasalahan dari VRP dengan perluasan dan penambahan multiple trip pada setiap kendaraan ketika mendistribusikan barang serta time window pelayanan customer. Pada artikel ini, permasalahan MTVRP diselesaikan dengan menggunakan algoritma sequential insertion. Proses pencarian rute pada algoritma tersebut dimulai dengan memilih pelanggan awal (seed customer) dengan kriteria jarak terjauh dari depot, dilanjutkan dengan mencari jarak terpendek dari seed customer kemudian disisipkan pada posisi terbaik. Proses ini dilakukan sampai semua titik telah terpilih. Kelebihan algoritma sequential insertion ini adalah pada pemilihan seed customer berdasarkan jarak terjauh dari depot serta pemilihan customer selanjutnya dengan mencari jarak terdekat dari seed customer. Karena iterasi yang berulang dengan proses yang sama sehingga diperlukan suatu program untuk mempermudah pencarian rute yakni program Borland Delphi. Kata kunci: Vehicle Routing Problem (VRP), Multiple Trip Vehicle Routing Problem (MTVRP), Algoritma Sequential Insertion Dalam kehidupan sehari-hari graph digunakan untuk menggambar berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi objekobjek agar lebih mudah dimengerti. Beberapa contoh graph yang dijumpai dalam kehidupan nyata, antara lain struktur organisasi, bagan alir pengambilan mata kuliah, masalah transportasi, dan distribusi produk. Pencarian rute kendaraan dapat mengoptimalkan jalur-jalur pengiriman sehingga biaya pendistribusian berkurang. Salah satu terapan dari teori graph yang banyak digunakan untuk menyelesaikan permasalahan pencarian rute kendaraan adalah multiple trip vehicle routing problem (mtvrp). MTVRP adalah permasalahan dari Vehicle Routing Problem (VRP) dengan perluasan dan penambahan multiple trip pada setiap kendaraan ketika mendistribusikan barang serta time window pelayanan customer. Setiap kendaraan dapat memiliki lebih dari satu rute pada periode perencanaan . Tujuannya adalah bagaimana menentukan sejumlah rute minimum yang berawal dan berakhir di outlet untuk sekumpulan kendaraan agar tiap customer dapat dilayani dengan memenuhi kendala yang ada. Kendala yang ada tersebut adalah jumlah permintaan tidak boleh melebihi kapasitas kendaraan dan total waktu, baik waktu tempuh (travel time) maupun waktu pelayanan (service time), tidak boleh melebihi batas waktu (time window) yang telah ditentukan, dan setiap customer hanya dilayani oleh satu kendaraan sehingga dapat ditentukan banyaknya kendaraan yang dibutuhkan dengan total jarak tempuh minimum. 1. 2. 3.
Nine Winda Yunita adalah mahasiswa jurusan Matematika FMIPA Universitas Negeri Malang Sapti Wahyuningsih adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang Darmawan Satyananda adalah dosen jurusan Matematika FMIPA Universitas Negeri Malang
2
Terdapat beberapa metode ataupun algoritma yang dikembangkan untuk menyelesaikan permasalahan Multiple Trip Vehicle Routing Problem (MTVRP). Algoritma-algoritma yang dikembangkan untuk menyelesaikan permasalahan tersebut adalah “Metode Insertion Heuristic” yang dibahas oleh Oktaviani Gladis Dwi pada skripsi tahun 2010, “Algortima Saving Procedure for Multiple Use Of Vehicle (SPMU)” yang dibahas oleh Budiarto Ricky pada skripsi tahun 2010, “Algoritma Sequential Insertion” yang dibahas oleh Pintomurti Florentia pada skripsi tahun 2012. Pada jurnal Econometric Institute Report EI 9938/A Poot Alexander dkk, 1999 menyatakan bahwa algoritma sequential insertion diawali dengan memilih suatu pelanggan untuk menduduki posisi sebagai pelanggan awal (seed customer) pada rute dan tur pertama. Selanjutnya, tiap pelanggan akan dicoba disisipkan pada suatu busur (edge) tertentu yang memberikan kriteria terbaik bagi rute saat ini, batasan time window terpenuhi, dan total muatan kendaraan bagi rute saat ini tidak melebihi kapasitas kendaraan. Ada beberapa kriteria yang dapat digunakan yaitu earliest deadline (deadline tercepat), earliest ready time (waktu siap menerima pelayanan tercepat), shortest time window (waktu penyelesaian tercepat), longest travel time (waktu tempuh terjauh), dan random (acak) (Suprayogi, 2008). Kelebihan algoritma sequential insertion dengan kriteria longest travel time (waktu tempuh terjauh) sebagai seed customer yakni dalam menentukan seed customer dapat langsung ditentukan dengan mencari jarak terjauh antar customer dan depot. Untuk customer selanjutnya dipilih customer yang mempunyai jarak terdekat dengan customer sebelumnya. Berdasarkan uraian diatas akan dikaji penggunaan algoritma sequential insertion pada multiple trip vehicle routing problem. HASIL YANG DIHARAPKAN 1. Mengetahui karakteristik dari MTVRP serta permodelan matematikanya. 2. Menerapkan algoritma sequential insertion pada contoh penerapan MTVRP. 3. Mengimplementasikan algoritma sequential insertion dalam program Borland Delphi 7. HASIL DAN PEMBAHASAN Aldous dan Wilson (2000: 6) mengungkapkan gagasan tentang graph, yaitu diagram yang merepresentasikan titik yang disebut verteks sebagai objek dan garis yang disebut sisi merepresentasikan hubungan antar objek. Graph yang digunakan untuk masalah pencarian rute kendaraan adalah graph komplit yang telah diberi bobot yaitu bilangan yang berasosiasi pada setiap sisi. Graph komplit adalah graph yang setiap dua titik yang berbeda dihubungkan oleh satu sisi. Graph komplit berbobot digunakan sebagai model dalam multiple trip vehicle routing problem. •
Multiple Trip Vehicle Routing Problem Multiple Trip Vehicle Routing Problem (MTVRP) merupakan pengembangan dari keterbatasan waktu dan rute pada model Vehicle Routing Problem (VRP) dengan penambahan kendala bahwa kendaraan yang digunakan dapat memiliki lebih dari satu rute pada periode perencanaan. Pada model ini
3
dapat menggunakan banyak rute sepanjang waktu tempuh total, dengan aturan bahwa tidak boleh melampaui limit waktu yang telah ditetapkan sebelumnya. Formulasi MTVRP dengan tujuan meminimalkan total biaya atau total jarak tempuh dari rute perjalanan pendistribusian barang atau jasa (Emirul Bahar, 2003) adalah sebagai berikut: ∑ ∈ ∑∈ a. Kendala ini untuk meminimalisasi biaya transportasi total dari rute. b. ∑ ∈ ∑ ∈ ≥1 ∀ ∈ Batasan tersebut untuk menjamin bahwa seluruh customer dapat dilayani. c. ∑ = 1, ∀ ∈ {0} Batasan ini untuk memastikan bahwa setiap customer dikunjungi tepat satu kali oleh satu kendaraan. d. ∑ = Kendala ini memastikan bahwa terdapat K kendaraan yang beroperasi memulai rute dari depot. e. ∑ ∈! ≤ , ∀" = 1,2, … , Kendala tersebut menjamin bahwa total permintaan konsumen dalam setiap rute tidak melebihi kapasitas kendaraan. f. ∑ ∈ % ≤ %&'( ∀" ∈ Batasan ini memastikan bahwa total waktu rute suatu kendaraan tidak melebihi waktu maksimum. g. ∑ ≥1 ∀" ∈ Kendala ini menjamin bahwa tiap kendaraan minimal melewati 1 jalur. ∈ {0,1} ∀ " ∈ ,∀ ) ∈ * h. Batasan tersebut menjamin variabel keputusan merupakan integer biner. Dengan variabel keputusan: 1, , "- ". -)-- " . //0 -"- )01. ) =+ 0, , "- 2.3Keterangan formulasi : : himpunan kendaraan pada depot, dengan = {1,2, … , "} * : himpunan rute yang ditempuh kendaraan ", dengan * = {* , * 4 , … , * } : himpunan titik : jumlah permintaan customer i ) : indeks rute : biaya operasional kendaraan " yang menempuh rute ) : konstanta, yang bernilai 1 jika kendaraan " dengan rute ) yang menuju customer , dan bernilai 0 untuk kondisi lainnya % : waktu perjalanan kendaraan untuk menempuh rute ) %&'( : waktu perjalanan maksimum untuk suatu kendaraan •
ALGORITMA SEQUENTIAL INSERTION PADA MULTIPLE TRIP VEHICLE ROUTING PROBLEM Algoritma insertion ada dua macam yaitu algoritma parallel dan algoritma sequential insertion. Algoritma sequential insertion adalah dasar dari semua algoritma insertion (Alexander Poot dkk,1999).
4
Algoritma sequential insertion diawali dengan memilih suatu pelanggan untuk menduduki posisi sebagai pelanggan awal (seed customer) pada rute dan tur pertama. Selanjutnya, tiap pelanggan akan dicoba disisipkan pada suatu busur (edge) tertentu yang memberikan kriteria terbaik bagi rute saat ini, batasan time window terpenuhi, dan total muatan kendaraan bagi rute saat ini tidak melebihi kapasitas kendaraan. Langkah-langkah menyelesaikan multiple trip vehicle routing problem dengan menggunakan algoritma sequential insertion adalah sebagai berikut: Langkah 1: Memilih kendaraan Pilih kendaraan terbesar yang tidak melangsungkan perjalanan dan tidak digunakan sebelumnya. Langkah 2: Memilih pelanggan pertama (seed customer) Pilih pelanggan yang paling penting (contohnya pelanggan dengan jarak terjauh dari depot atau waktu pelayanan tercepat) dan layak dalam kendaraan. Jika gagal untuk memilih pelanggan kembali ke langkah 1, jika tidak tetapkan pelanggan pada kendaraan saat ini. Langkah 3: Menambahkan pelanggan ke rute baru Pertama buat daftar kandidat untuk dimasukkan dalam rute. Kandidat adalah pelanggan yang tidak sedang dilayani serta memenuhi kendala kapasitas dan lokasinya tidak terlalu jauh dari pelanggan pertama (seed customer). Hitung untuk masing-masing kandidat penyisipan biayanya yaitu jarak ekstra yang dibutuhkan untuk melayani pelanggan. Urutkan pelanggan dalam daftar tidak penurunan pemesanan dari penyisipan biaya. Setiap kali coba untuk menyisipkan kandidat selanjutnya pada posisi terbaik yang memungkinkan pada rute. Jika tidak dapat menemukan pelanggan untuk disisipkan beberapa kali, maka lanjutkan ke langkah 4. Langkah 4: Pindah rute ke kendaraan yang lebih kecil Coba untuk memindahkan rute ke kendaraan yang lebih kecil dari tipe kendaraan yang sama dan nomor daerah, untuk menghemat kapasitas kendaraan, tanpa melanggar kendala apapun. Jika rute telah dipindah ke kendarann lain, maka kembali ke langkah 3, jika tidak kembali ke langkah 1.
5
Berikut ini flowchart program algoritma sequential insertion. Begin
Memilih kendaraan
k= 1,2, ... , K
F
End
Memilih pelanggan awal jauh:=0
for i:=1 to jmlTitik do
F c0i >=jauh jauh=c0i
T
Menambah pelanggan ke rute baru
for i:=1 to jmlTitik do
for j:=1 to jmlTitik do
terkecil:=999; cij <= terkecil terkecil = cij
Pindahkan perjalanan ke kendaraan yang lebih kecil
F
Ki < Ki+1
T
Gambar 1 Flowchart program Algoritma Sequential Insertion Keunggulan algoritma ini terletak pada pencarian seed customer. Pada Gambar 1 diatas terletak pada coi >= jauh, dengan jauh = coi. Kemudian dilanjutkan dengan mencari jarak terdekat dengan i (customer yang terpilih). Pada gambar diatas terletak pada pemisalan jarak terdekat sebagai terkecil = 999, kemudian untuk setiap customer dicari cij <= terkecil. Sehingga diperoleh jarak terdekat terkecil = cij.
6
Setelah membuat rancangan flowchart program yang akan dibuat langkah selanjutnya adalah membuat rancangan tampilan program. Karena luas form yang terbatas dan menggunakan banyak komponen, maka digunakan komponen PageControl. Satu page control akan berisi banyak page (tabsheet) yang saling bertumpuk (Darmawan:2012). Pada program MTVRP ini digunakan 5 tabsheet. Untuk tabsheet pertama menggunakan komponen Image. Tabsheet kedua dan ketiga menggunakan komponen StringGird. Pada tabsheet keempat menggunakan komponen Memo. Sedangkan pada tabsheet kelima sama dengan tabsheet pertama menggunakan komponen Image, akan tetapi pada tabsheet rute ini untuk menampilkan rute yang terbentuk dari hasil perhitungan. Selain itu di form utama ini juga terdapat kolom kapasitas, kecepatan rata-rata, time window serta waktu pelayanan. Pada program juga dilengkapi dengan button Reset, Open, Save, dan Keluar. •
Contoh Multiple Trip Vehicle Routing Problem dengan Algoritma Sequential Insertion Perusahaan pigura yang berada di kota Batu memiliki 9 agen yang terdapat di kota Malang, Blitar, Kediri, Tulungagung, Jogjakarta, Klaten, Surakarta, Magelang, Semarang. Setiap agen memiliki permintaan yang berbedabeda. Perusahaan tersebut mengirimkan pigura dengan menggunakan kendaraan sebanyak 2 mobil box dengan kecepatan 80 km/jam dan memiliki kapasitas 400 box pigura. Perusahaan tesebut dapat melayani customer mulai pukul 12.00 sampai pukul 12.00 dua hari berikutnya. Waktu yang dibutuhkan untuk persiapan sebelum berangkat mengirim kira-kira 1jam. Sedangkan waktu yang dibutuhkan untuk mengangkat box pigura di tempat customer kira-kira 0.0125 jam. Permintaan setiap customer serta jarak antar customer disajikan pada Tabel 1 dan Tabel 2 berikut. Tabel 1 Permintaan customer Customer
1
2
3
4
5
6
7
8
9
Permintaan
132
73
50
132
100
74
83
145
65
56 0 1 2 3 4 5 6 7 8 9
Tabel 2 Jarak antara perusahaan dengan customer dan antar customer 0 0
1 19.9 0
2 95.7 76.3
3 80.6 99.3
4 111 105
5 323 341
6 490 309
7 256 275
8 341 360
9 330 400
0
44.7 0
35.6 31.9 0
291 244 239 0
259 212 215 33.4 0
224 178 181 67.7 34.8 0
309 263 266 60.7 69.2 85.4 0
298 251 285 141 107 109 87.3 0
Keterangan : 0 = Perusahaan pigura di kota Batu 1 = Agen di kota Malang
2 = Agen di kota Blitar 3 = Agen di kota Kediri
7
4 = Agen di kota Tulungagung 5 = Agen di kota Jogjakarta 6 = Agen di kota Klaten
7 = Agen di kota Surakarta 8 = Agen di kota Magelang 9 = Agen di kota Semarang
Penyelesaian menggunakan algoritma sequential insertion. Langkah 1 : Kendaraan 1 Langkah 2 : Terpilih customer 6 Kendala kapasitas 78 = 74 ≤ ; (memenuhi) %<=<>? = @<8 + % 8 + %8 = 13.175 ≤ % (memenuhi) Rute terpilih : 0 – 6 – 0 Langkah 3 : a. Penyisipan customer 5 Kendala kapasitas = 78 + 7E = 74 + 100 ≤ ; (memenuhi) Mencari posisi terbaik 1. 0 – 5 – 6 – 0 %<=<>? = @<8 + @<E + % E + %E8 + %8 = 12.755 ≤ % (memenuhi) 2. 0 – 6 – 5 – 0 %<=<>? = @<8 + @<E + % 8 + %E8 + %E = 12.755 ≤ % (memenuhi) Rute terpilih : 0 – 5 – 6 – 0 b. Penyisipan customer 7 Kendala kapasitas = 78 + 7E + 7F
= 74 + 100 + 83 ≤ ; (memenuhi)
Mencari posisi terbaik 1. 0 – 7 – 5 – 6 – 0 %<=<>? = @<8 + @<E + @
? = @<8 + @<E + @? = @<8 + @<E + @? = 14.61 jam 2. 0 – 2 – 4 – 8 – 0 dengan %<=<>? = 13.60375 jam 3. 0 – 1 – 0 dengan %<=<>? = 2.1475 jam
8
Penyelesaian menggunakan program.
Gambar 2 Hasil perhitungan
Gambar 3 Hasil rute
Dari Gambar 2 diatas diperoleh hasil rute [0,3,9,5,6,7,0] dengan waktu tempuh 14,61 jam, [0,2,4,8,0] dengan waktu tempuh 13,60375 jam, dan [0,1,0] dengan waktu tempuh 2,1475 jam. Gambar 3 adalah hasil gambar rute yang diperoleh pada hasil perhitungan Gambar 2. PENUTUP Kesimpulan Berdasarkan pembahasan dapat disimpulkan bahwa: 1. Multiple Trip Vehicle Routing Problem (MTVRP) merupakan pengembangan dari keterbatasan waktu dan rute pada model Vehicle Routing Problem (VRP). Multiple Trip Vehicle Routing Problem (MTVRP) dapat didefinisikan G = (N, E) adalah suatu graph dimana N = {0, 1, …, n} adalah himpunan titik dan E ⊆ N x N adalah himpunan sisi. Karakteristik dari MTVRP adalah setiap customer dilayani tepat satu kendaraan, jumlah dari permintaan customer dalam satu kendaraan tidak melebihi kapasitas kendaraan, terdapat waktu pengiriman (time window) maksimum, dan setiap kendaraan mungkin melewati lebih dari satu lintasan dengan waktu tidak boleh melewati waktu maksimum. Tujuan MTVRP adalah meminimalisasi
9
∑ ∈ ∑∈ biaya transportasi total dari rute dinyatakan dengan serta memenuhi kendala kapasitas ∑ ∈! ≤ , dan waktu ∑∈ % ≤ %&'( . 2. Algoritma sequential insertion dapat menghasilkan rute yang optimal dengan pemilihan seed customer yang tepat. Ada beberapa kriteria pemilihan seed customer yakni deadline tercepat, waktu siap menerima pelayanan tercepat, waktu pelayanan tercepat, jarak terjauh dari depot, dan random. Algoritma sequential insertion dapat diterapkan dalam kehidupan sehari-hari, seperti pencarian rute untuk pengiriman barang. 3. Penggunaan program dimulai dengan menginputkan kecepatan rata-rata kendaraan, kapasitas kendaraan, time window, dan waktu persiapan pada kolom yang telah disediakan. Kemudian dilanjutkan dengan menginputkan banyaknya titik, permintaan setiap customer serta jarak antar customer. Output yang dihasilkan pada program tersebut adalah hasil rute dengan waktu yang ditempuh serta gambar rutenya. Pada program MTVRP tersebut telah dicoba 14, 18, 23, 29, 36, 38, 56, 66, dan 90 titik. Saran Pencarian rute yang optimal bergantung pada pemilihan seed customer yang tepat. Oleh karena itu, untuk selanjutnya dapat dikembangkan dengan kriteria pemilihan seed customer deadline tercepat maupun random.heterogen dan selain distribusi seragam serta meningkatkan jumlah pelanggan dan kapasitas kendaraan. DAFTAR RUJUKAN Aldous, Joan and Robin J. Wilson. 2000. Graph and Application. Great Britain : Springer. Bahar, Emirul. 2003. Analisis Penentuan Jalur Transportasi Limbah Minyak Pada Aktivitas Pelayaran Laut Untuk Menghasikan Total Biaya Pelayaran Minimum. Jurnal Ekonomi & Bisnis No.2, Jilid 8. Budiarto, Ricky. 2010. Multiple Vehicle Routing Problem (MTVRP) dengan Algoritma Self-Developed dan Saving Procedure for Multiple Use Of Vehicle (SPMU). Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Oktaviani, Gladis Dwi. 2010. Implementasi Metode Insertion Heuristic dalam Penyelesaian Multiple Trip Vehicle Routing Problem (MTVRP) dan Analisanya. Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pintomurti, Florentia. 2012. Algoritma sequential insertion pada penyelesaian Vehicle Routing Problem With Multiple Trips and Intermediate Facility (VRPMTIF). Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Poot, Alexander, Kant, Goos and Wagelmans, Albert P. M. 1999. A Savings Based Method for Real-Life Vehicle Routing Problems. Econometric Institute Report EI 9938/A. Satyananda, Darmawan. 2012. Panduan Praktikum Struktur Data. Malang. Jurusan Matematika. Universitas Negeri Malang.
10
Suprayogi, Yusuf Priyandari. 2008. Algoritma Sequential Insertion untuk Memecahkan Vehicle Routing Problem dengan Multiple Trips, Time Window dan Simultaneous Pickup Delivery. Jurnal Performa (2008) Vol.7, No.1:88-96. Wilson, R. J and Watkins, J. J. 1990. Graph an Introductory Approach a First Course in Discrete Mathematics. Canada : John Willy and Sons, Inc.
