Majalah Ilmiah Teknologi Elektro, Vol. 20, No. 2, Juli - Desember 2021

DOI: https://doi.org/10.24843/MITE.2021.v20i02.P14                                                              299

Pengembangan Aplikasi Penentuan Rute Pengiriman Barang Berdasarkan Berat dan Time Windows Menggunakan Metode Nearest Neighbour dan Tabu Search

Putu Irvan Arya Purwadana1, I Made Candiasa2, I Nyoman Sukajaya3

[Submission: 20-06-2021, Accepted: 13-08-2021]

Abstract— One of practical example of CVRPTW (Capacitated Vehicle Routing Problem with Time Windows) is delivery. Important factors in delivery are cost, speed, service and consistency. In order for these factors to be met optimally, the capacity and time windows must be considered. Capacity affects service and consistency, so the right route must be choosen with the shortest distance and the right capacity. Time windows affects on the speed and costs so that the delivery must be carried out according specified time and company operating hours. This research purpose to produce delivery routes that consider capacity and delivery time. There are two steps in calculation, which is clustering and searching of optimal delivery route. The clustering step uses a polar angle and the optimal route searching uses the nearest neighbour and the tabu search. The results of the comparison between the route generated by the system with the company's current route indicate that the delivery route generated by the system can makes delivery distance efficiency of 12.18%, delivery time of 5.54% and delivery cost efficiency of 12.18%.

Intisari— Salah satu contoh praktis dari CVRPTW adalah pengiriman barang. Faktor penting dalam pengiriman barang adalah biaya, kecepatan, pelayanan dan konsistensi. Agar faktor-faktor tersebut terpenuhi secara optimal harus diperhatikan muatan barang serta time windows. Muatan berpengaruh pada faktor pelayanan dan konsistensi, sehingga harus dipilih rute yang tepat dengan jarak terpendek serta ketepatan kapasitas barang. Time windows berpengaruh pada faktor kecepatan dan biaya pengiriman sehingga pengiriman barang harus dilakukan sesuai waktu yang ditentukan dan jam operasional perusahaan. Penelitian ini bertujuan menghasilkan rute pengiriman barang yang memperhatikan kapasitas muatan dan waktu tempuh pengiriman. Terdapat dua tahapan penyelesaian yaitu tahap clustering dan pencarian rute optimal. Tahap clustering menggunakan sudut polar dan tpencarian rute optimal menggunakan metode nearest neighbour tabu search. Hasil pengujian perbandingan rute yang dihasilkan oleh sistem dengan rute perusahaan saat ini menunjukkan bahwa rute pengiriman yang dihasilkan oleh sistem dapat melakukan efisiensi jarak pengiriman sebesar 12.18%, waktu pengiriman sebesar 5.54% dan biaya pengiriman sebesar 12.18%.

Kata Kunci— CVRPTW, Nearest Neighbour, Tabu Search.

I Putu Irvan Arya Puwadana: Pengembangan Aplikasi Penentuan Rute


  • I.    pendahuluan

VRP (Vehicle Routing Problem) merupakan salah satu model matematika yang dapat menyelesaikan permasalahan pendistribusian barang pada sistem transportasi dengan tujuan untuk menemukan rute perjalanan dengan biaya yang minimum dalam pendistribusian barang [1]. Terdapat beberapa jenis VRP salah satunya adalah CVRPTW yang merupakan kombinasi antara CVRP (Capacitated Vehicle Routing Problem) dan VRPTW (Vehicle Routing Problem with Time Windows). CVRPTW memiliki tujuan membangun serta mengoptimalkan rute pengiriman agar dapat dapat melakukan delivery permintaan pelanggan dengan permasalahan yaitu muatan dan time windows. Contoh praktis dari model permasalahan CVRPTW adalah penentuan rute pengiriman barang [2].

Proses pengiriman barang memiliki peran penting dalam sebuah jaringan bisnis, baik itu untuk konsumen maupun untuk kepentingan perusahaan [3]. Menentukan rute pengiriman yang optimal merupakan cara untuk meminimalisasi biaya distribusi. Penentuan rute distribusi juga menentukan jumlah waktu dan biaya yang diperlukan oleh perusahaan [4]. Terdapat beberapa faktor utama yang harus diperhatikan dalam pengiriman barang yaitu biaya, kecepatan, pelayanan dan konsistensi. Faktor utama tersebut dapat terpenuhi apabila memperhatikan kendala pengiriman seperti muatan barang serta waktu atau time windows. Muatan berpengaruh pada faktor pelayanan dan konsistensi dalam pengiriman barang, oleh karena itu harus melakukan pemilihan rute yang tepat sehingga jarak tempuh yang dilalui merupakan jarak tempuh yang terpendek. Selain itu, perlu diperhatikan ketepatan dalam penentuan kapasitas barang yang dikirim sehingga barang yang dikirim tidak kurang atau melebihi kapasitas kendaraan pengiriman. Waktu atau time windows berpengaruh pada faktor kecepatan dan biaya pengiriman sehingga pengiriman barang harus dikerjakan sesuai dengan waktu ditentukan ke pelanggan dan juga jam operasional perusahaan sehingga tidak terjadi keterlambatan pengiriman dan menambah beban karyawan perusahaan [5].

Permasalahan tersebut dapat diatasi dengan cara membangun aplikasi yang dapat membentuk rute pengiriman barang. Rute yang dibentuk tidak hanya memperhatikan kapasitas muatan namun juga memperhatikan time windows yaitu waktu tempuh pengiriman dan pelayanan untuk masing-masing pelanggaan agar bersesuaian dengan jam operasional perusahaan. Terdapat dua tahapan dalam menyelesaikan permasalahan pengiriman barang pada penelitian yaitu tahap clustering dan tahap pencarian rute optimal. Tahap clustering atau pengelompokkan menggunakan sudut polar terkecil dimana setiap data pengiriman diurutkan berdasarkan nilai p-ISSN:1693 – 2951; e-ISSN: 2503-2372


sudut polarnya, setelah itu dikelompokkan barang mana saja yang dapat diangkut oleh kendaraan 1 dan jika sudah melebihi kapasitas diangkut oleh kendaraan 2 dan seterusnya. Tahap pencarian rute optimal memiliki sub proses yaitu pencarian rute awal dan pencarian rute alternatif. Proses pencarian rute awal diselesaikan menggunakan metode nearest neighbour sedangkan proses pencarian rute dengan rute alternatif untuk tiap kendaraan diselesaikan dengan menggunakan metode tabu search. Metode nearest neighbour adalah salah satu metode untuk menentukan jalur dengan cara mencari lokasi pengiriman yang paling dekat dari semua lokasi pengiriman lain yang sedang dikunjungi [6]. Metode nearest neighbour memiliki kelebihan yaitu sederhana dan juga dapat diimplementasikan sebagai dasar bagi metode metaheuristik lainnya dalam penentuan rute serta menyelesaikan masalah VRP [7]. Metode tabu search merupakan metode metaheuristik dengan konsep local search yang dapat diimplementasikan dalam memecahkan masalah optimasi kombinatorial. Kelebihan metode tabu search yaitu kemampuan untuk keluar dari solusi optimal lokal dan menghasilkan solusi yang menjanjikan dalam waktu komputasi yang masuk akal [8].

Berdasarkan penelitian yang dilakukan sebelumnya oleh [9] terkait penggunaan metode nearest neighbour dalam menentukan rute distribusi pada PT API menghasilkan penghematan jarak sebesar 26,59% atau setara dengan 538,2 Km, mereduksi waktu pendistribusian produk sebesar 19,07% atau setara dengan 9,37 jam, penghematan biaya bahan bakar sebesar 26,59% atau setara dengan Rp. 403.650, penghematan biaya sopir dan pendamping sebesar 4,50% atau setara dengan Rp. 272.850. Total penhematan total biaya distribusi sebesar 25,71% atau setara dengan Rp. 676.500. Selain itu pada penelitian oleh [10] menggunakan studi kasus pendistribusian roti di CV Jogja Transport melakukan perbandingan metode genetika dan metode nearest neighbour dilihat dari segi efektivitas daya angkut kendaraan, metode nearest neighbour lebih efektif dibandingkan metode genetika kendaraan karena mampu memaksimalkan kapasitas angkut kendaraan yaitu mengangkut 420 roti (100%) walaupun berdasarkan jarak tempuh memiliki selisih jarak 6,4 km dari yang dihasilkan oleh metode genetika. Penelitian terkait metode tabu search dilakukan oleh [11] untuk menyelesaiakan masalah VRP pada PT. Samudra Kencana Mina menghasilkan rute distirbusi dengan total jarak 169,7 km sedangkan rute pengiriman actual dari perusahaan sebesar 246,8 km hal ini menunjukkan terjadi penghematan rute distribusi sebesar 77,1 km. Penelitian oleh [12] melakukan perbandingan antara metode sweep dan metode tabu search dalam menyelesaikan permasalahan CVRP dimana dapat disimpulkan untuk dua jenis kasus diperoleh bahwa dalam menentukan rute pengiriman yang optimal metode tabu search lebih baik dari metode sweep karena menghasilkan rute dengan jarak yang lebih pendek.

Berdasarkan penelitian yang telah dilakukan sebelumnya, penelitian ini memiliki perbedaan yaitu tidak hanya menggunakan satu metode penyelesaian melainkan menggunakan kombinasi dua buah metode yaitu metode nearest neighbour dan metode tabu search. Kombinasi kedua metode ini digunakan untuk menghasilkan rute pengiriman yang optimal berdasarkan hasil seleksi beberapa alternatif rute yang tersedia. Selain itu, penelitian ini juga memiliki kelebihan yaitu terdapat fitur yang memudahkan driver untuk melakukan

pengiriman barang berupa digital map sehingga driver dapat melihat keseluruhan rute pengiriman dan juga rute pengiriman dari satu titik pengiriman ke titik pengiriman lainnya.

  • II.    Landasan Teori

  • A.    CVRPTW

CVRPTW adalah tipe VRP dengan kombinasi CVRP dan VRPTW. CVRPTW memiliki tujuan untuk menghasilkan rute pengiriman yang optimal guna memenuhi permintaan delivery oleh pelanggan. CVRPTW memiliki dua kendala utama yaitu kapasitas dan time windows. Kendala kapasitas berarti setiap kendaraan yang melakukan pengiriman mempunyai kapasitas tertentu sehingga kendaraan akan berhenti melayani pelanggan selanjutnya apabila kapasitas kendaraan sudah penuh. Kendala time windows ada dua jenis yaitu waktu pengiriman untuk pelanggan dan waktu buka tutup pada depot. Time windows untuk pelanggan merupakan rentang waktu yang diberikan bagi setiap kendaraan untuk melayani masing-masing pelanggan [13].

  • B.    Pengiriman Barang

Pengiriman barang didasari kegiatan penjualan barang [14]. Kegiatan penjualan yaitu penjualan barang maupun jasa yang dibayar secara tunai atau non tunai [15]. Pengiriman barang secara umum adalah proses persiapan barang dari gudang ke lokasi tujuan pengiriman agar sesuai dengan faktur pemesanan dan pengiriman serta penanganan barang sesuai dengan prosedurnya agar menjaga kondisi barang [16]. Biaya, kecepatan, pelayanan dan konsistensi merupakan empat faktor penting dalam kegiatan pengiriman barang.

  • C.    Metode Nearest Neighbour

Metode nearest neighbour adalah salah satu contoh metode heuristik yang dapat diimplementasikan kedalam masalah rute. Konsep dari metode ini adalah mencari titik awal pengiriman dilanjutkan dengan mencari titik selanjutnya yang memiliki jarak terpendek dari titik awal tersebut. Penentuan rute metode nearest neighbour mulai dengan mencari daerah terdekat yang memiliki jarak paling pendek lalu menentukan daerah selanjutnya yang akan dikunjungi yang dengan jarak terpendek pula. Dalam pemecahan masalah VRP, metode nearest neighbour telah terbukti cepat, efektif dan berkualitas layak [17]. Metode nearest neighbour memiliki langkah-langkah perhitungan sebagai berikut [18].

  • 1)    Menentukan lokasi awal perjalanan atau rute pengiriman yaitu gudang atau depot.

  • 2)    Menentukan lokasi pengiriman selanjutnya dengan jarak terdekat dari lokasi awal dan tidak melebihi kapasitas kendaraan.

  • a.    Apabila kapasitas kendaraan belum penuh setelah lokasi pengiriman ditentukan maka kembali ke langkah 2 dan lokasi pengiriman terpilih tersebut menjadi lokasi awal pengiriman yang baru.

  • b.    Apabilakapasitas kendaraan penuh maka proses selesai atau dapat membuat rute baru dengan kembali ke Langkah 1.

  • 3)    Algoritma selesai apabila semua lokasi tujuan pengiriman semua tujuan pengiriman telah dikunjungi satu kali.

Majalah Ilmiah Teknologi Elektro, Vol. 20, No. 2, Juli - Desember 2021

DOI: https://doi.org/10.24843/MITE.2021.v20i02.P14                                                              301

  • D.    Metode Tabu Search

Tahun 1986, Fred Glover memperkenalkan metode tabu Search untuk memecahkan masalah optimum local dengan metode local search. Konsep dari tabu search yaitu mencegah terjadinya solusi non-improving menggunakan kemampuan local search bertemu sebuah local optimum. Hal ini terjadi karena metode tabu search mengimplementasikan sebuah ide kunci yang bisa dihubungkan dengan konsep intelegensia buatan dengan menggunakan tabu list yaitu sebuah memori yang merekam sejarah terbaru, Tabu search menggunakan sebuah memori untuk menyimpan sekumpulan solusi yang baru saja dievaluasi yang disebut tabu list. Tahapan perhitungan metode metode tabu search sebagai berikut [19].

  • 1)    Langkah 1: Pilih Solusi awal i dalam himpunan S. Tetapkan I* = I dan k=0 dimana 1* adalah solusi terbaik dan k adalah banyaknya perulangan yang terjadi saat dilakukannya pencarian solusi terbaik 1*.

  • 2)    Langkah 2: Tetapkan k = k + 1 dan hasilkan himpunan bagian V* dari solusi dalam solusi himpunan N(i,k^ sehingga tabu conditions tidak terpenuhi tetapi aspirations conditions terpenuhi.

  • 3)    Langkah 3: Pilih solusi terbaik j dalam himpunan bagian V* tetapkan i = j.

  • 4)    Langkah 4: Jika f(l) ≤ /(i*) maka tetapkan i* = i.

  • 5)    Langkah 5: Update tabu dan aspirations conditions.

  • 6)    Langkah 6: Jika kondisi berhenti (stopping conditions) terpenuhi, maka pencarian berhenti. Jika tidak, lakukan langkah 2.

Dimana:

i = Solusi yang ditemukan

  • i* = Solusi terbaik dari solusi yang ditemukan

k = Perulangan

j = Solusi yang ditemukan untuk perulangan berikutnya

S = Himpunan solusi yang mungkin

  • V* = Himpunan bagian dari N(i, k)

N(i,k) = Himpunan solusi yang mungkin untuk semua perulangan

  • III.    Metodologi Penelitian

Metode penelitian dari Aplikasi Penentuan Rute Pengiriman Barang berdasarkan Berat dan Time Windows menggunakan Metode Nearest Neighbour dan Tabu Search pada Gambar 1:

  • 1)    Tahap identifikasi masalah melakukan observasi dan wawancara terhadap perusahaan terkait SOP pengiriman barang yang dimiliki perusahaan, proses penentuan rute pengiriman barang, faktor yang mempengaruhi pengiriman barang dan masalah pada proses pengiriman barang.

  • 2)    Tahap studi literatur mengumpulkan teori yang menunjang serta berkaitan dengan penentuan rute pengiriman barang, Metode nearest neighbour dan tabu search melalui penelitian terdahulu, buku, e-book, jurnal penelitian internasional dan nasional dan paper publikasi.

Gambar 1: Metodologi Penelitian

  • 3)    Tahap pengumpulan data melakukan wawancara terhadap perusahaan untuk menentukan faktor berpengaruh pada proses penentuan rute pengiriman barang dan untuk mendapatkan data primer yang akan digunakan pada aplikasi yaitu data pengiriman barang.

  • 4)    Tahap desain yakni mendesain ERD yang nantinya akan dijadikan acuan untuk pengembangan basis data serta perancangan diagram konteks serta DFD untuk pengembangan user interface.

  • 5)    Tahap implementasi sistem membuat coding GUI, coding fungsi input, proses dan output yang dapat dilakukan oleh aplikasi serta coding perhitungan metode nearest neighbour dan tabu search.

  • 6)    Tahap pengujian sistem dilakukan dengan melakukan perbandingan hasil rute yang dihasilkan pada sistem dengan rute aktual perusahaan. Kesimpulan dapat ditarik berdasarkan hasil pengujian.

  • IV.    Hasil dan Pembahasan

  • A.    Desain

Desain sistem menampilkan rancangan untuk pengembangan aplikasi yang terdiri dari diagram konteks, DFD dan ERD. Diagram konteks menunjukkan entitas yang terlibat dalam sistem secara keseluruhan beserta aliran data dan informasinya, DFD menggambarkan informasi yang bergerak sebagai masukan maupun keluaran sistem dan ERD membuat model sistem berdasarkan kebutuhan [20]. Diagram konteks ditampilkan pada Gambar 2:

I Putu Irvan Arya Puwadana: Pengembangan Aplikasi Penentuan Rute


p-ISSN:1693 – 2951; e-ISSN: 2503-2372



username, password, data kendaraan, data transaksi, data user, data driver

Aplikasi Penentuan Rute Pengiriman Barang



info signin, info data user, info data kendaraan, infro data driver, info data transaksi

Gambar 2: Diagram Konteks

Gambar 2: menampilkan diagram konteks dimana terdapat empat entitas yang terlibat yaitu admin, pengelola, operator dan driver. Entitas admin adalah pengguna sistem yang dapat melakukan sign in, manajemen data user dan lihat data transaksi. Entitas customer adalah entitas luar yang memberikan data pengiriman yang dimasukkan oleh operator. Entitas operator adalah pengguna sistem yang dapat melakukan manajemen data transkasi dan generate untuk mendapatkan rute pengiriman barang. Entitas driver adalah pengguna sistem yang dapat melihat data pengiriman dan mengubah status pengiriman barang.

DFD level 0 menggambarkan aliran data secara detail yang terjadi pada sistem. Proses yang terdapat tiga proses dan lima data storage yang terlibat dalam proses yang ditampilkan pada Gambar 3:

Menejemen

Master Data

Gambar 3: DFD


d3

kendaraan

d4

driver


Gambar 3: menampilkan DFD Level 0 dari sistem dimana terdapat tiga proses utama yaitu sign in, proses manajemen master data dan proses pencarian rute pengiriman serta tiga entitas yang terlibat adalah admin, operator dan driver. Data storage yang digunakan adalah data user, data transaksi, data kendaraan, data driver dan data generate.

ERD digunakan untuk mendeskripsikan permodelan struktur data dan hubungan antar data. ERD ditampilkan pada Gambar 4:

Gambar 4: ERD


Gambar 4: menampilkan ERD dimana pengelolaan data transaksi oleh entitas user (operator) serta atribut yang dimiliki entitas transaksi beserta relasinya yang berkaitan dengan proses pencarian informasi transaksi dan generate rute. Entitas transaksi untuk menyimpan data transaksi, entitas user yang menyimpan data pengguna, entitas generate menyimpan data hasil generate untuk menentukan rute dan entitas driver menyimpan data driver dan entitas kendaraan menyimpan detail data kendaraan.

  • B.    Implementasi

Sebelum membentuk rute pengiriman, diperlukan proses clustering barang untuk kendaraan 1 dan kendaraan 2 agar tidak melebihi kapasitas kendaraan tersebut. Data pengiriman ditunjukkan pada Tabel 1:

TABEL I

Data Pengiriman


ID_Pelanggan

Kapasitas

ID_Pelanggan

Kapasitas

1

100

11

90

2

90

12

75

3

85

13

75

4

130

14

125

5

110

15

125

6

125

16

50

7

135

17

50

8

50

18

150

9

125

19

125

10

75

20

75


Tabel 1: menunjukkan data pengiriman dimana data ini digunakan untuk mencari matriks jarak dan waktu yang dapat membantu dalam proses clustering. Langkah pertama dalam proses clustering yaitu menghitung derajat polar dari titik pengiriman awal dan titik tujuan, setelah itu melakukan pengurutan data pengiriman berdasarkan derajat polarnya.

Majalah Ilmiah Teknologi Elektro, Vol. 20, No. 2, Juli - Desember 2021

DOI: https://doi.org/10.24843/MITE.2021.v20i02.P14                                                            303

Berdasarkan urutan derajat polar inilah dikelompokkan data pengiriman untuk kendaraan 1 dan kendaraan 2 dengan tetap memperhatikan maksimum kapasitas kendaraan. Hasil clustering untuk kendaraan 1 (K1) dan kendaraan 2 (K2) ditunjukkan pada Tabel 2:

tabu list kemudian diseleksi untuk mendapatkan rute pengiriman terpendek. Rute pengiriman akhir pengiriman setelah proses seleksi pada tabu list ditunjukkan pada Tabel 5:

TABEL V

Rute Pengiriman Barang

TABEL III

HAsil CLUSTERING

Hasil Clustering

Kapasitas

K1

12 – 16 – 17 – 20 – 14 – 9 – 13 – 15 – 4 – 11

975

K2

6 – 1 – 3 – 5 – 8 – 2 – 7 – 10 – 18 – 19

990

Rute Pengiriman

Total Jarak

Total Waktu

K1

0 – 17 – 12 – 11 – 15 – 14 – 4 –

13 – 9 – 16 – 20 – 0

26910

288

K2

0 – 19 – 18 – 10 – 2 – 6 – 1 – 5

– 3 – 8 – 7 – 0

27450

290

Tabel 2: menampilkan hasil clustering untuk masing-masing kendaraan. Langkah kedua adalah mencari solusi awal menggunakan metode metode nearest neighbour. Metode nearest neighbour bekerja dengan mencari titik pengiriman dengan jarak terpendek dari titik awal pengiriman ke titik pengiriman berikutnya hingga semua titik pengiriman terpenuhi. Hasil uji coba untuk mencari solusi awal untuk kendaraan 1 dan kendaraan 2 ditunjukkan pada Tabel 3:

TABEL IIIII

Rute Pengiriman Awal

Rute Pengiriman Awal

K2

0 – 17 – 12 – 11 – 15 – 14 – 4 – 13 – 9 – 20 – 16 – 0

K1

0 – 19 – 10 – 18 – 3 – 8 – 1 – 5 – 2 – 6 – 7 – 0

Tabel 3: menampilkan rute awal untuk masing-masing kendaraan. Berdasarkan rute awal yang dihasilkan, dilakukan pencarian rute alternatif dengan menggunakan metode tabu search. Pada metode tabu search, proses iterasi dilakukan dengan menukar dua titik pengiriman. Proses iterasi berhenti ketika rute yang sama dibuat dan jumlah iterasi telah terpenuhi. Hasil rute terbaik di setiap proses iterasi dimasukkan dalam tabu list. Tabu list untuk kendaraan 1 dan kendaraan 2 ditunjukkan pada Tabel 4:

Tabel 5: menunjukkan rute terbaik yang dihasilkan dengan metode tabu search, dimana rute terbaik untuk kendaraan 1 memiliki total jarak tempuh 26,910 km dengan total waktu tempuh 288 menit. Sedangkan rute terbaik kendaraan 2 memiliki total jarak tempuh 27,450 dengan total waktu tempuh 290 menit. Tampilan rute pengiriman yang dihasilkan oleh sistem ditunjukkan pada Gambar 5:

Gambar 5: Rute Pengiriman Barang untuk Kendaraan 1 dan Kendaraan

TABEL IVV Tabu List

Iterasi

Rute

Total Jarak

Total Waktu

K1

1

0 – 17 – 12 – 11 – 15 – 14 – 4

– 13 – 9 – 16 – 20 – 0

26910

288

2

0 – 17 – 12 – 11 – 15 – 14 – 4

– 13 – 9 – 20 – 16 – 0

26911

288

3

0 – 17 – 12 – 11 – 15 – 14 – 4

– 13 – 9 – 16 – 20 – 0

26910

288

K2

1

0 – 19 – 10 – 18 – 3 – 6 – 1 –

5 – 2 – 8 – 7 – 0

28372

293

2

0 – 19 – 10 – 18 – 2 – 6 – 1 –

5 – 3 – 8 – 7 – 0

27540

290

3

0 – 19 – 18 – 10 – 2 – 6 – 1 –

5 – 3 – 8 – 7 – 0

27450

290

4

0 – 19 – 10 – 18 – 2 – 6 – 1 –

5 – 3 – 8 – 7 – 0

27540

290

  • C.    Pengujian

Pengujian dilakukan dengan membandingkan rute yang dihasilkan oleh sistem dengan rute yang ada pada perusahaan saat ini. Parameter yang diuji pada pencarian rute adalah jarak total yang dihasilkan, waktu total pengiriman, biaya pengiriman dan gaji karyawan. Perbandingan rute yang dihasilkan oleh sistem dengan rute perusahaan untuk 20 data pengiriman ditunjukkan pada Tabel 6:

TABEL VI

Perbandingan Hasil Rute Pengiriman Sistem dan Perusahaan untuk 20 Data Pengiriman

Tabel 4: menunjukkan tabu list untuk setiap kendaraan, dapat dilihat pada tabu list memuat semua solusi terbaik dari setiap iterasi yang dilakukan. Semua solusi yang terdapat pada

I Putu Irvan Arya Puwadana: Pengembangan Aplikasi Penentuan Rute


Tabel 6: menampilkan perbandingan rute yang dihasilkan oleh sistem dengan rute pengiriman yang digunakan pada perusahaan. Berdasarkan hasil perbandingan terlihat bahwa rute yang dihasilkan oleh perusahaan sangat berbeda dari rute p-ISSN:1693 – 2951; e-ISSN: 2503-2372



Rute Perusahaan

Rute Sistem

K1

0 – 19 – 18 – 10 – 7 – 8 – 3

– 2 – 5 – 1 – 6 – 0

0 – 17 – 12 – 11 – 15 – 14 –

4 – 13 – 9 – 16 – 20 – 0

K2

0 – 4 – 13 – 9 – 16 – 20 – 12

– 14 – 15 – 11 – 17 – 0

0 – 19 – 18 – 10 – 2 – 6 – 1 –

5 – 3 – 8 – 7 – 0

yang dihasilkan oleh sistem, hal ini dikarenakan rute perusahaan dibentuk berdasarkan pengetahuan dan pengalaman pengirim. Perbandingan hasil rute pengiriman berdasarkan parameter pengujian yang digunakan ditunjukkan pada Tabel 7:

TABEL VII Perbandingan Hasil Pengujian untuk 20 Data Pengiriman

Total Jarak Perusah aan

Total Jarak Siste m

Total Waktu Perusah aan

Total Wakt u Siste m

Total Muatan Perusah aan

Total Muat an Siste m

K 1

32401

26910

295

288

990

990

K

2

28577

27450

315

290

975

1000

Tabel 7: menampilkan perbandingan hasil rute dari sistem dan perusahaan berdasarkan parameter pengujian yang digunakan yaitu total jarak, total waktu dan total muatan. Total jarak yang dihasilkan dari rute pengiriman perusahaan untuk kendaraan 1 adalah 32,401 km sedangkan total jarak yang dihasilkan dari rute sistem adalah 26,910 km, sehingga selisih total jarak rute perusahaan dengan rute sistem adalah 5,491 km. Total jarak yang dihasilkan dari rute pengiriman perusahaan untuk kendaraan 2 adalah 28,577 km sedangkan total jarak yang dihasilkan dari rute sistem adalah 27,450 km, sehingga selisih total jarak rute perusahaan dengan rute sistem adalah 1,127 km. Total waktu yang dihasilkan dari rute pengiriman perusahaan untuk kendaraan 1 adalah 295 menit sedangkan total waktu yang dihasilkan dari rute sistem adalah 288 menit, sehingga selisih total waktu rute perusahaan dengan rute sistem adalah 7 menit. Total waktu yang dihasilkan dari rute pengiriman perusahaan untuk kendaraan 2 adalah 315 menit sedangkan total waktu yang dihasilkan dari rute sistem adalah 290 menit, sehingga selisih total waktu rute perusahaan dengan rute sistem adalah 25 menit. Pada kendaraan 2 total waktu pengiriman yang dibutuhkan perusahaan melebihi time windows yang telah ditetapkan sehingga dalam keadaan dilapangan pengirim harus bekerja melewati jam kerja atau lembur. Total muatan yang dihasilkan dari rute pengiriman perusahaan dan rute pengiriman sistem untuk kendaraan 1 bernilai sama yaitu 990 kg. Total muatan yang dihasilkan dari rute pengiriman perusahaan untuk kendaraan 2 adalah 990 kg sedangkan total muatan yang dihasilkan dari rute sistem adalah 1000 kg, sehingga selisih total muatan rute perusahaan dengan rute sistem adalah 10 kg. Rute pengiriman yang dihasilkan oleh sistem untuk kendaraan 1 dan 2 berhasil melakukan efisiensi jarak pengiriman sebesar 12,18%, waktu pengiriman sebesar 5,54% dan muatan sebesar 1,27%. Selain itu juga dilakukan perbandingan biaya yang dikeluarkan untuk pengiriman dari rute perusahaan dan rute sistem. Perbandingan hasil biaya pengiriman ditunjukkan pada Tabel 8:

TABEL VIII Perbandingan Biaya Pengiriman

Biaya Pengiriman Perusahaan

Biaya Pengiriman Sistem

Total Efisiensi

K1

Rp. 51.843

Rp. 43.056

Rp. 8787

K2

Rp. 45.723

Rp. 43.920

Rp. 1803

Jumlah

Rp 97.566

Rp. 86.976

Rp. 10.590

Tabel 8: menampilkan hasil perbandingan biaya pengiriman berdasarkan rute perusahaan dan rute sistem. Perkiraan biaya pengiriman perusahaan adalah Rp. 1.600 untuk 1 km, biaya inilah yang dijadikan acuan untuk perhitungan biaya pengiriman untuk 20 data pengiriman. Jumlah biaya pengiriman perusahaan dalam untuk kendaraan 1 dan 2 untuk satu kali pengiriman sebesar Rp. 97.566 sedangkan biaya pengiriman rute sistem untuk kendaraan 1 dan 2 dalam satu bulan sebesar Rp. 86.976. Selisih biaya pengiriman rute perusahaan dan rute sistem sebesar Rp. 10.590. Hal ini membuktikan bahwa rute pengiriman yang dihasilkan sistem sistem dapat melakukan efisiensi biaya pengiriman sebesar 12,18%. Berdasarkan hasil perbandingan parameter inilah dapat disimpulkan bahwa rute yang dihasilkan oleh sistem lebih efisien dibandingkan dengan rute perusahaan karena dapat mengurangi jarak pengiriman, waktu pengiriman, biaya pengiriman serta dapat memaksimalkan muatan barang pada kendaraan.

  • V.    Kesimpulan

Adapun hal yang dapat disimpulakan pada penelitian ini yaitu adalah aplikasi penentuan rute pengiriman barang dapat menghasilkan rute yang lebih baik dibandingkan rute perusahaan yang ada saat ini. Hasil pengujian efektivitas dengan menggunakan 20 data pengiriman menunjukkan bahwa rute pengiriman barang dihasilkan oleh sistem untuk kendaraan 1 dan 2 berhasil melakukan efisiensi jarak pengiriman sebesar 12,18%, waktu pengiriman sebesar 5,54% dan efisiensi biaya pengiriman sebesar 12,19% dibandingkan dengan rute pengiriman barang perusahaan saat ini.

  • VI.    Referensi

  • [1]    W. Irawan, M. Manaqib, and N. Fitriyati, “Implementation of the Model Capacited Vehicle Routing Problem with Time Windows with a Goal Programming Approach in Determining the Best Route for Goods Distribution,” J. Mat. Stat. dan Komputasi, vol. 17, no. 2, pp. 231–239, 2020, doi: 10.20956/jmsk.v17i2.11107.

  • [2]    H. Prasetyo, A. L. Putri, and G. Fauza, “Biased Random Key Genetic Algorithm Design with Multiple Populations to Solve Capacitated Vehicle Routing Problem with Time Windows,” AIP Conf. Proc., vol. 1977, 2018, doi: 10.1063/1.5042908.

  • [3]    R. Yohanes, S. Santoso, and R. M. Heryanto, “Penentuan Rute Distribusi yang Mempertimbangkan Multi Trips , Time Window , dan Simultaneous Pickup Delivery dengan Menggunakan Algoritma Sequential Insertion,” in Seminar Nasional Teknik Industri Universitas Gajah Mada, 2020, pp. 64–68.

  • [4]    G. Melina Sari, R. Maini Heryanto, and S. Santoso, “Penentuan Rute Distribusi Menggunakan Model Integer Linear Programming dengan Metode Branch and Bound,” Go-Integratif J. Tek. Sist. dan Ind., vol. 1, no. 01, pp. 69–79, 2020, doi: 10.35261/gijtsi.v1i01.4265.

  • [5]    Y. D. Putra, I. N. S. Kumara, N. Wayan, S. Aryani, I. Bagus, and A. Swamardika, “Metode Behaviorally Anchored Rating Scale ( BARS ),” Maj. Ilm. Teknol. Elektro, vol. 20, no. 1, pp. 104–111, 2021.

  • [6]    I. W. A. S. Darma, “Implementation of Zoning and K-Nearest Neighbor in Character Recognition of Wrésastra Script,” Lontar Komput. J. Ilm. Teknol. Inf., vol. 10, no. 1, p. 9, 2019, doi: 10.24843/lkjiti.2019.v10.i01.p02.

  • [7]    L. Leymena, C. S. B. W, and W. Sutopo, “Analisis Penentuan Rute Distribusi Menggunakan Metode Nearest Neighbor,” in Seminar dan Konferensi Nasional IDEC, 2019, p. E14.1-E14.7, [Online]. Available:                                https://idec.ft.uns.ac.id/wp-

content/uploads/2019/05/ID119.pdf.

Majalah Ilmiah Teknologi Elektro, Vol. 20, No. 2, Juli - Desember 2021 DOI: https://doi.org/10.24843/MITE.2021.v20i02.P14

305


  • [8]    N. Tiandini and W. Anggraeni, “Penerapan Metode Kombinasi Algoritma Genetika dan Tabu Search dalam Optimasi,” J. Tek. ITS, vol. 6, no. 1, 2017.

  • [9]    W. Prasetyo and M. Tamyiz, “Vehicle Routing Problem dengan Aplikasi Metode Nearest Neihbor,” J. Res. Technol., vol. 3, no. 2, pp. 88–89, 2017.

  • [10]    H. Hutomo and E. R. Sari, “Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Algoritma Genetika Dan Nearest Neighbour Pada Pendistribusian Roti,” J. Mat., vol. 6, no. 2, pp. 52– 62,            2017,             [Online].             Available:

http://journal.student.uny.ac.id/ojs/index.php/math/article/viewFile/ 6850/6591.

  • [11]    C. Y. L and P. W. Endang, “Analisa Vehicle Routing Problem (VRP) Pada Produk Frozen Seafood dengan Menggunakan Algoritma Tabu Search (Studi Kasus : PT. Samudra Kencana Mina Sidoarjo),” vol. 12, no. 02, pp. 32–42, 2017.

  • [12]    I. M. Ari Santosa, N. Nyoman Utami Januhari, I. P. Ramayasa, and I. Ketut Dedy Suryawan, “Comparison of Sweep and Tabu Search Methods in Searching for Item Delivery Routes based on Volume,” 2019 1st Int. Conf. Cybern. Intell. Syst. ICORIS 2019, vol. I, pp. 257– 262, 2019, doi: 10.1109/ICORIS.2019.8874875.

  • [13]    N. L. A. Ayuningrum and F. Y. Saptaningtyas, “Implementasi Algoritma Genetika dengan Variasi Crossover dalam Penyelesaian Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) pada Pendistribusian Air Mineral,” J. Mat., vol. 6, no. 3, pp. 62–72, 2017.

  • [14]    I. A. S. S. Anjani, L. Jasa, and I. R. Agung, “Rancang Bangun Sistem Minimarket Otomatis Berbasis IoT,” Maj. Ilm. Teknol. Elektro, vol. 19, no. 2, p. 255, 2020, doi: 10.24843/mite.2020.v19i02.p19.

  • [15]    A. Purwadana, D. P. Githa, and D. P. Singgih, “Aplikasi Optimalisasi Pengiriman Barang Menggunakan Metode Tabu Search Berbasis Web,” vol. 6, no. 3, pp. 234–243, 2018.

  • [16]    K. Meliantari, D. Putra Githa, and N. K. Ayu Wirdiani, “Optimasi Distribusi Produk Menggunakan Metode Cheapest Insertion Heuristic Berbasis Web,” J. Ilm. Merpati (Menara Penelit. Akad. Teknol. Informasi), vol. 6, no. 3, p. 204, 2018, doi: 10.24843/jim.2018.v06.i03.p07.

  • [17]    Suryani, D. K. R. Kuncoro, and L. D. Fathimahhayati, “Perbandingan Penerapan Metode Nearest Neighbour dan Insertion untuk Penentuan Rute Distribusi Optimal Produk Roti pada UKM Hasan Bakery,” Profisiensi, vol. 6, no. 1, pp. 41–49, 2018.

  • [18]    S. Martono and H. L. H. S. Warnars, “Penentuan Rute Pengiriman Barang Dengan Metode Nearest Neighbor,” Petir, vol. 13, no. 1, pp. 44–57, 2020, doi: 10.33322/petir.v13i1.869.

  • [19]    P. M. Hasugian, “Pengembangan Aplikasi Untuk Mempermudah Pencarian,” J. Inform. Pelita Nusant., vol. 2, no. 1, pp. 1–5, 2017.

  • [20]    N. L. A. M. Rahayu Dewi, R. S. Hartati, and Y. Divayana, “Penerapan Metode Prototype dalam Perancangan Sistem Informasi Penerimaan Karyawan Berbasis Website pada Berlian Agency,” Maj. Ilm. Teknol. Elektro, vol. 20, no. 1, p. 147, 2021, doi: 10.24843/mite.2021.v20i01.p17.

    I Putu Irvan Arya Puwadana: Pengembangan Aplikasi Penentuan Rute


    p-ISSN:1693 – 2951; e-ISSN: 2503-2372



{ Halaman ini sengaja dikosongkan }

ISSN 1693 – 2951

I Putu Irvan Arya Puwadana: Pengembangan Aplikasi Penentuan Rute