Completion of CVRP with a Combination of Sweep and Local Search Algorithms (Case Study: PT. AJW)

Zakaria Alfikri Sirait; Riri Syafitri Lubis

doi:10.25217/numerical.v7i1.3446

Authors

Zakaria Alfikri Sirait Universitas Islam Negeri Sumatera Utara
Riri Syafitri Lubis Universitas Islam Negeri Sumatera Utara Medan

DOI:

https://doi.org/10.25217/numerical.v7i1.3446

Keywords:

Algortima Sweep, CVRP, Distribution, Local Search, Shortest Route

Abstract

AJW is a consumer goods distribution company for Indofood products and non-Indofood products. PT. AJW moves throughout Karo district. The number of tourist attractions in Karo makes the demand for goods higher such as Pop noodles, Indomie, chitato and others. Thus, having an impact on the distribution of goods Based on the author's observations at PT. AJW Kabanjahe has no standard provisions in determining the route, the delivery of goods is still carried out based on requests from consumers so that it ignores the distance traveled and time. A way that can solve this distribution problem is the Capacitated Vehicle Routing Problem (CVRP). CVRP is a problem in determining the optimal route by looking at the problem that each vehicle has a capacity limit. To solve CVRP problems, a good heuristic algorithm is used is the sweep algorithm and local search route improvement. This study uses the sweep algorithm to solve the CVRP problem, and the routes obtained by the sweep algorithm will be improved with local search. The sweep algorithm is a simple method of calculation, even for calculating large problems. The sweep algorithm will be combined with local search. Local search is an algorithm used to get shorter routes. The combination of the two algorithms is perfect for solving CVRP problems. After research, a distance of 39.96 km was obtained compared to the company's route of 103.5 km. So the percentage of mileage savings is 61.39%. This shows that sweep algorithms can minimize distance while saving company expenses

References

F. J. Sesa, H. Syarifudin, and Y. Rizal, “Optimasi Rute Pengiriman Produk dengan Meminimumkan Biaya Transportasi Menggunakan Metode Saving Matrix di PT . DEF,” Journal Of Mathematics UNP, vol. Vol 4, No, no. 4, 2019.

Muhammad, Bakhtiar, and M. Rahmi, “Penentuan Rute Transportasi Distribusi Sirup Untuk Meminimalkan Biaya,” Industrial Engineering Journal, vol. 6, no. 1, pp. 10–15, 2017.

A. S. Kusuma and Sumiati, “PENERAPAN METODE CLARKE AND WRIGHT SAVING HEURISTIC DALAM MENENTUKAN RUTE,” Jurnal Manajemen Industri dan Teknologi, vol. 01, no. 04, pp. 1–11, 2020.

C.N. Olivia, “Penyelesaian Vehicle Routing Problem With Simultaneuos Pick up and Delivery Menggunakan Metode Constrain Programming,” Institusi Teknologi Harapan Bangsa, 2019.

S. K. Sharma, S. Routroy, and U. Yadav, “Vehicle routing problem: Recent literature review of its variants,” International Journal of Operational Research, vol. 33, no. 1. 2018. doi: 10.1504/IJOR.2018.094229.

S. Kristina, R. Doddy Sianturi, and R. Husnadi, “Penerapan Model Capacitated Vehicle Routing Problem (CVRP) Menggunakan Google OR-Tools untuk Penentuan Rute Pengantaran Obat pada Perusahaan Pedagang Besar Farmasi (PBF),” Jurnal Telematika, vol. 15, no. 2, pp. 101–106, 2020.

M. Sari, A. Dhoruri, and R. S. Eminugroho, “Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Saving Matriks, Sequential Insertion dan Nearest Neighbour di Victoria RO,” Jurnal Matematika-S1, vol. 5, no. 3, pp. 1–11, 2016.

Y. A. Respati, E. Zaini, and A. Imran, “Model Penjadwalan No-Wait Job Shop Menggunakan Algoritma Variabel Neighbourhood Descent dengan Threshold untuk Meminimisasi Makespan,” Reka Integra, Jurnal Online Teknik Industri Itenas, Bandung, vol. 3, no. 1, 2015.

R. A. Pratama, P. H. Utomo, and S. Wibowo, “PERBANDINGAN SOLUSI CVRP PADA DISTRIBUSI BUKU AQILA DI SURAKARTA MENGGUNAKAN ALGORITME TABU SEARCH DAN ALGORITME ACO,” JRAM: Jurnal Riset dan Aplikasi Matematika, vol. 6, no. 1, pp. 13–22, 2022.

F. Chicano, B. Hu, and P. García-Sánchez, “Evolutionary computation in combinatorial optimization: 16th European conference, EvoCOP 2016 Porto, Portugal, march 30 – april 1, 2016 proceedings,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016.

A. Rozalina, S. Uslianti, and P. Anggela, “Optimasi Rute Distribusi Dengan Penyelesaian VRP Menggunakan Algoritma Sweep PD. XYZ di Pontianak,” Tin, vol. 4, no. 1, pp. 45–50, 2020.

R. Saraswati, W. Sutopo, and Muh. Hisjam, “Penyelesaian Capacitated Vechile Routing Problem Dengan Menggunakan Algoritma Sweep Untuk Penentuan Rute Distribusi Koran : Studi Kasus,” Jurnal Manajemen Pemasaran, vol. 11, no. 2, pp. 41–44, 2017, doi: 10.9744/pemasaran.11.2.41-44.

I. A.A, L. N., A. R.O, and I. J.A, “CAPACITATED VEHICLE ROUTING PROBLEM,” International Journal of Research -GRANTHAALAYAH, vol. 7, no. 3, 2019, doi: 10.29121/granthaalayah.v7.i3.2019.976.

T. W. Lesmana and P. Gultom, “BATU BARA DENGAN JARAK TERPENDEK DAN KAPASITAS,” vol. 8, no. 1, 2022.

H. Koswara, “Penentuan Rute Distribusi Produk Kaos Pada Dobujack Inv. Menggunakan Metode Nearest Neighbour Dan (1-0) Insertion Intra Route,” Jurnal Rekayasa Sistem & Industri (JRSI), vol. 4, no. 02, pp. 192–198, 2018, doi: 10.25124/jrsi.v4i02.286.

F. Arnold and K. Sörensen, “Knowledge-guided local search for the vehicle routing problem,” Comput Oper Res, vol. 105, pp. 32–46, 2019, doi: 10.1016/j.cor.2019.01.002.

F. R. Yunizar, A. Imran, and A. I. S. Tjaja, “Penerapan Algoritma Sweep Dan Algoritma (1-0) Insertion Intra Route untuk Mengoptimalkan Rute Distribusi J&C COOKIES,” Fti, pp. 1–12, 2022.

E. Arifta and F. Rakhmawati, “Analysis of Book Distribution Routes Using the Capacity Vehicle Routing Problem (CVRP) Method Using the Sweep Algorithm,” Sinkron, vol. 8, no. 1, pp. 360–367, 2023, doi: 10.33395/sinkron.v8i1.12013.

R. R. MAULINA, “Penerapan Algoritma Sweep untuk Penyelesaian Open Vehicle Routing Problem pada Kasus Distribusi Produk,” Repository.Unej.Ac.Id, 2019.

M. Ruben and A. Imran, “Usulan Rute Distribusi Menggunakan Algoritma Sweep Dan Local Search (Studi Kasus Di Perusahaan X),” Jurnal Rekayasa Sistem Industri, vol. 6, no. 1, pp. 40–44, 2020, doi: 10.33884/jrsi.v6i1.2491.