Jurnal Matematika Vol. 11, No.1, Juni 2021, pp. 41-48

Article DOI: 10.24843/JMAT.2021.v11.i01.p135

ISSN: 1693-1394

Penerapan Kombinasi Genetic Algorithm dan Iterated Local Search Pada Multi-Depot

Capacitated Vehicle Routing Problem

Inggrid Dwi Safira

Jurusan Matematika, FMIPA – Universitas Jember e-mail: [email protected]

Agustina Pradjaningsih

Jurusan Matematika, FMIPA – Universitas Jember e-mail: [email protected]

Abduh Riski

Jurusan Matematika, FMIPA – Universitas Jember e-mail: [email protected]

Abstract: The logistics is a system for distributing goods or products from the company to customers. One of the problems in the logistics worlds is determining the distribution route of goods. This problem is called the vehicle routing problem (VRP). Multi-depot capacitated vehicle routing problem is a variation of the vehicle routing proble (VRP) which is based on the problem of distribution of goods where the number of depots is more than one with the addition that each vehicle has a capacity limit to be transported. In this study, the authors apply a combination of two metaheuristic algorithms, namely the Genetic Algorithm (GA) and Iterated Local Search (ILS), here in after referred to as the GA&ILS algorithm. This study aims to analyze the result of the application of the GA&ILS algorithm to solve MDCVRP on 20 simulation data grouped into four sizes (25, 50, 75, and 100 customer points). Based on the results of the research, it was found that the GA&ILS algorithm is optimal for small-scale data, but not optimal for large-scale data.

Keywords: MDCVRP, VRP, optimization, metaheuristic, applied mathematics

Abstrak: Logistik adalah suatu sistem untuk mengirimkan barang atau produk dari perusahaan kepada pelanggan. Salah satu permasalahan dalam dunia logistik yaitu penentuan rute distribusi barang. Permasalahan ini disebut dengan vehicle routing problem (VRP). Multi-depot capacitated vehicle routing problem (MDCVRP) adalah variasi dari vehicle routing problem (VRP) yang didasarkan pada permasalahan distribusi barang dimana jumlah depot lebih dari satu dengan tambahan bahwa setiap kendaraan memiliki batas kapasitas yang diangkut. Dalam penelitian ini, penulis menerapkan kombinasi dua algoritma metaheuristik, yaitu Algoritma Genetika (GA) dan Iterated Local Search (ILS), yang selanjutnya disebut sebagai algoritma GA&ILS. Penelitian ini bertujuan untuk menganalisis hasil penerapan algoritma GA&ILS untuk menyelesaikan MDCVRP pada 20 data simulasi yang dikelompokkan menjadi empat ukuran (25, 50, 75, dan 100 titik pelanggan). Berdasarkan

hasil penelitian didapatkan bahwa algoritma GA&ILS optimal untuk data skala kecil, namun tidak optimal untuk data skala besar.

Kata Kunci: MDCVRP, VRP, optimasi, metaheuristik, matematika terapan

  • 1.    Pendahuluan

Sistem logistik merupakan suatu sistem untuk menyalurkan barang atau produk dari perusahaan kepada para pelanggan. Dalam dunia industri, manajemen sistem distribusi sangat penting untuk diperhatikan karena berkaitan dengan pengeluaran biaya perusahaan dan kepuasan pelanggan. Pemilihan rute yang baik mampu meminimalisir biaya distribusi serta mempercepat tersalurkannya produk ke tangan pelanggan. Penentuan rute terbaik mudah dilakukan jika pelanggan yang dilayani hanya sedikit. Namun, jika jumlah pelanggan yang harus dilayani menjadi sangat banyak, penentuan rute terbaik juga menjadi sangat sulit. Selain itu, pada beberapa kasus perusahaan juga harus mempertimbangkan jumlah serta kapasitas kendaraan distribusi yang digunakan. Oleh karena itu, banyak matematikawan memodelkan permasalahan tersebut dalam model matematis agar lebih mudah diselesaikan. Model dari permasalahan ini biasa disebut dengan permasalahan Vehicle Routing Problem (VRP) (Kurniawan, et al., 2014).

Permasalahan VRP merupakan salah satu topik optimasi yang sering dibahas dalam ilmu matematika terapan. Permasalahan MDCVRP (Multi-depot Capacitated Vehicle Routing Problem) merupakan salah satu variasi dari VRP yang dikembangkan berdasarkan kondisi dunia industri dewasa ini dan sangat menarik untuk dibahas, dimana jumlah pusat distribusi lebih dari satu dan dengan tambahan bahwa setiap kendaraan memiliki batas kapasitas yang diangkut (Permana, et al., 2015). Terdapat beberapa penelitian mengenai permasalahan MDCVRP dalam beberapa tahun terakhir, antara lain: (1) algoritma nested particle swarm optimization oleh (Geetha & Poonthalir, 2013); (2) kombinasi algoritma biased randomized dan iterated local search oleh (Juan, et al., 2015); dan (3) algoritma cooperative coevolutionary oleh (Oliveira, et al., 2016). Dari penelitian-penelitian tersebut disimpulkan bahwa permasalahan MDCVRP masih menjadi salah satu topik yang menarik untuk dibahas dan diteliti lebih lanjut. Selain itu, algoritma yang diterapkan pada penelitian-penelitian tersebut tidak efektif pada data skala besar, sehingga penerapan algoritma optimasi lain juga perlu dilakukan guna mencari metode penyelesaian terbaik.

Dewasa ini, penerapan algoritma hybrid lebih banyak diminati oleh para peneliti untuk menyelesaikan permasalahan optimasi. Hal ini dikarenakan banyak algoritma hybrid yang dibuktikan mampu memberikan hasil yang lebih baik. Salah satu algoritma hybrid yang memiliki performa sangat baik adalah kombinasi genetic algorithm (GA) dan

iterated local search (ILS) yang diajukan oleh (Derbel, et al., 2011). Berdasarkan penelitiannya, disimpulkan bahwa algoritma yang diajukannya GA&ILS lebih baik daripada algoritma genetika saja dalam menyelesaikan permasalahan Location-Routing Problem (LRP). Permasalahan LRP ini merupakan permasalahan yang hampir sama dengan permasalahan MDCVRP. Perbedaannya terletak pada jumlah kendaraan tiap depot pada LRP hanya satu saja dengan kapasitas tidak terbatas, sedangkan pada MDCVRP setiap depot memiliki lebih dari satu kendaraan dengan masing-masing kendaraan mempunyai batas kapasitas.

Berdasarkan uraian di atas, penulis bermaksud untuk menerapkan algoritma GA&ILS pada permasalahan MDCVRP. Algoritma diujikan pada data simulasi yang merupakan gabungan data riil dan data random. Data riil diambil dari data jarak antar desa di Kabupaten Jember serta data biaya kendaraan dan bahan bakar. Data random adalah data yang dibangkitkan secara acak untuk jumlah permintaan pelanggan, kapasitas depot dan kapasitas kendaraan. Penelitian ini bertujuan untuk menganalisis efektivitas dan efisiensi dari penerapan algoritma GA&ILS untuk menyelesaikan permasalahan MDCVRP.

  • 2.    Metode Penelitian

Data yang digunakan dalam penelitian ini adalah gabungan dari data asli dan random. Terdapat beberapa data yang digunakan, yaitu koordinat (latitude dan longitude), jarak, kapasitas depot, permintaan pelanggan, kapasitas kendaraan, biaya kendaraan dan biaya bahan bakar. Terdapat 20 data MDCVRP yang digunakan sebagai bahan simulasi uji algoritma. Data tersebut diambil dari data utama 2 titik depot dan 197 titik pelanggan. Data simulasi yang digunakan dibagi secara acak menjadi empat ukuran yaitu 25 titik pelanggan, 50 titik pelanggan, 75 titik pelanggan dan 100 titik pelanggan. Dari setiap ukuran tersebut, terdapat lima jenis data yang titik-titik pelanggannya diambil secara acak. Dalam penelitian ini, barang yang digunakan diasumsikan dikemas dalam kardus dengan ukuran panjang 38 cm, lebar 24 cm, dan tinggi 24 cm. Jenis kendaraan yang digunakan adalah mobil truk small box dengan media penyimpanan berukuran panjang 237 cm, lebar 155 cm, dan tinggi 129 cm.

Data yang telah dikumpulkan dalam penelitian ini, kemudian diselesaikan menggunakan program penerapan algoritma GA&ILS. Dimana simulasi program dijalankan sebanyak 10 kali untuk setiap data. Solusi terbaik dari simulasi program digunakan untuk menganalisis hasil penerapan algoritma. Metode yang digunakan untuk menganalisis hasil penerapan algoritma terdapat dua metode yaitu berdasarkan persentase deviasi dan ilustrasi rute distribusi. Berdasarkan persentase deviasi, semakin nilai persentase deviasi memiliki arti algoritma semakin konvergen. Persentase deviasi dihitung menggunakan persamaan (1)

PD


RRB - BTT BTTT


× 100%


Dengan PD adalah persentase deviasi, RRB adalah rata-rata biaya, dan BTT adalah biaya total terkecil. Dari sisi ilustrasi distribusi, rute yang terbentuk tidak memiliki garis yang saling berpotongan untuk masing-masing kendaraan atau membentuk Hamiltonian cycle (Filar & Krass, 1994).

  • 3.    Hasil dan Pembahasan

Pada penelitian ini, program simulasi yang telah dibuat, dijalankan untuk menyelesaikan permasalahan MDCVRP dengan data yang telah dikumpulkan. Perangkat komputer yang digunakan dalam penelitian ini untuk menjalankan program simulasi adalah Laptop dengan Processor Intel® Celeron® CPU N3060 @1.60GHz RAM 4,00GB. Nilai parameter yang digunakan dalam simulasi ini antara lain: jumlah populasi N = 275, iterasi maksimal GS&ILS Imax = 2000 (data 25 dan 50 titik) dan Imax = 5000 (data 75 dan 100 titik), iterasi maksimal ILS T = 20. Pada setiap data, program simulasi dijalankan sebanyak sepuluh kali percobaan. Rangkuman hasil simulasi akhir penyelesaian 20 data MDCVRP yang telah dilakukan dapat dilihat pada Tabel 1.

Tabel 1. Hasil Simulasi Program

No

Data

Rata-rata Biaya

Biaya Terkecil

Persentase

Deviasi (%)

Waktu

Komputasi (s)

1

Data 25a

473.300

473.300

0

12851,3196

2

Data 25b

476.940

476.500

0,0923

12861,7482

3

Data 25c

478.900

478.600

0,0627

21937,0142

4

Data 25d

492.040

491.600

0,0895

22167,5157

5

Data 25e

518.780

518.300

0,0926

20896,1019

6

Data 50a

929.180

923.600

0,6042

22827,4608

7

Data 50b

834.960

832.500

0,2954

22447,4220

8

Data 50c

789.620

788.500

0,1420

29555,3544

9

Data 50d

808.160

800.600

0,9442

21411,4748

10

Data 50e

753.070

749.300

0,5031

21633,7809

11

Data 75a

1.158.490

1.141.300

1,5061

78823,5472

12

Data 75b

1.163.260

1.147.600

1,3646

78379,3245

13

Data 75c

1.186.440

1.164.500

1,8796

78788,6563

14

Data 75d

1.130.550

1.113.600

1,5221

78280,5265

15

Data 75e

1.235.310

1.220.900

1,1802

78148,3859

16

Data 100a

1.568.235

1.509.250

3,9082

102606,0168

17

Data 100b

1.548.810

1.516.650

2,1204

101600,9944

18

Data 100c

1.545.540

1.510.700

2,3062

102441,5586

No.

Rata-rata      Biaya      Persentase       Waktu

Biaya        Terkecil     Deviasi (%)    Komputasi (s)

19

20

Data 100d     1.601.560      1.569.600       2,0362       103736,7284

Data 100e      1.515.560      1.461.600       3,6918        102519,4666

Berdasarkan hasil simulasi akhir program penerapan algoritma GA&ILS pada permasalahan MDCVRP dengan menggunakan 20 data (lihat Tabel 1), dapat diketahui beberapa hal sebagai berikut. Pertama, persentase deviasi secara rata-rata, semakin besar datanya yang digunakan, maka nilai persentase deviasi juga semakin besar. Hal ini, dimungkinkan bahwa semakin besar data diselesaikan mengakibatkan algoritma GA&ILS semakin lama untuk konvergen menuju solusi optimal. Kedua, dari 20 data yang digunakan, algoritma GA&ILS mampu konvergen ke satu solusi dari sepuluh kali percobaan terjadi pada data25a (data 25 titik pelanggan variasi pertama). Dari kedua hasil tersebut dapat dianalisis bahwa algoritma GA&ILS masih memiliki kekurangan yaitu kurang mampu menghindari terjabak optimum lokal. Selain itu, apabila dilihat dari waktu komputasi program, algoritma GA&ILS membutuhkan waktu yang cukup lama untuk menyelesaikan permasalahan MDCVRP, sehingga dapat dikatakan kurang efisien.

Selanjutnya, hasil terbaik dari sepuluh percobaan setiap data dianalisis berdasarkan ilustrasi rute distribusinya. Hasil ilustrasi tersebut dapat dilihat pada Gambar 1 sampai dengan Gambar 4.

Gambar 1. Ilustrasi rute distribusi 25 titik

Gambar 2. Ilustrasi rute distribusi 50 titik

Gambar 3. Ilustrasi rute distribusi 75 titik

Gambar 4. Ilustrasi rute distribusi 100 titik

Berdasarkan hasil ilustrasi yang telah digambarkan, hasil terbaik algoritma GA&ILS pada data 25 titik pelanggan dapat dikatakan optimal, karena memenuhi konsep Hamiltonian cycle atau tidak terdapat garis berpotongan. Kemudian, pada ilustrasi rute distribusi dari solusi terbaik algoritma GA&ILS untuk data 50 titik sampai dengan 100 titik, masih ditemukan adanya rute kendaraan yang memiliki garis berpotongan. Dengan demikian, hasil tersebut dapat dikatakan belum optimal.

Berdasarkan analisis yang telah diuraikan, dapat diketahui bahwa algoritma GA&ILS tidak optimal untuk menyelesaikan permasalahan MDCVRP. Selain itu, dalam percobaan yang telah dilakukan, algoritma GA&ILS membutuhkan waktu komputasi yang cukup lama. Oleh karena itu, dapat dikatakan bahwa algoritma GA&ILS juga tidak efisien.

  • 4.    Kesimpulan dan Saran

Berdasarkan hasil dan pembahasan yang telah diuraikan sebelumnya, maka kesimpulan yang dapat diambil adalah algoritma GA&ILS tidak optimal untuk diterapkan dalam permasalahan MDCVRP. Hal ini dikarenakan dari beberapa percobaan yang telah dilakukan, algoritma GA&ILS tidak mampu mencapai nilai optimal dan lambat korvergen. Berdasarkan ilustrasi rute distribusi terdapat beberapa rute yang berpotongan. Algoritma GA&ILS juga beberapa kali terjebak optimum lokal.

Saran yang dapat penulis berikan untuk penelitian selanjutnya adalah menambahkan algoritma heuristik sebagai acuan pembangkitan solusi awal, sehingga algoritma GA&ILS dapat lebih mudah konvergen ke solusi optimal. Dengan demikian, diharapkan dengan penambahan tersebut, waktu penyelesaian masalah dapat lebih singkat.

Daftar Pustaka

Derbel, H., Jarboui, B., Hanafi, S. & Chabchoub, H., 2011. Genetic Algorithm with

Iterated Local Search for Solving a Location-Routing Problem. Expert Systems with Applications, Volume 39, pp. 2865-2871.

Filar, J. A. & Krass, D., 1994. Hamiltonian Cycles and Markov Chains. Mathematics of Operations Research, 19(1), pp. 223-237.

Geetha, S. & Poonthalir, G., 2013. Nested Particle Swarm Optimization for Multi-Depot Vehicle Routing Problem. Int. J. Operational Research, 16(3), pp. 329-348.

Juan, A. A., Pascual, I., Guimarans, D. & Barriors, B., 2015. Combining Biased Randomized with Iterated Local Search for Solving the Multidepot Vehicle Routing Problem. International Transactions in Operational Research, 22(4), pp. 647-667.

Kurniawan, I. S., Susanty, S. & Adianto, H., 2014. Usulan Rute Pendistribusian Air Mineral dalam Kemasan Menggunakan Metode Nearest Neighbour dan Clarke &

Wright Savings (Studi Kasus PT. X Bandung). Reka Integra, 1(4), pp. 125-136.

Oliveira, F. B. d. et al., 2016. A Cooperative Coevolutionary Algorithm for the MultiDepot Vehivle Routing Problem. Expert Systems with Applications, Volume 43, pp. 117-130.

Permana, A., Sulistyo, M. D. & Wulandari, G. S., 2015. Optimasi Genetic Algorithm dengan Simulated Anneling untuk Multiple Depot Capacitated Vehicle Routing Problem. Indonesia Symposium on Computing.

48