Penyelesaian Capacitated Vehicle Routing Problem (CVRP) dengan Nearest Neighbour (Studi Kasus: Russian CVRP Instances)

Authors

  • Ekra Sanggala Universitas Logistik & Bisnis Internasional
  • Muhammad Ardhya Bisma Universitas Logistik dan Bisnis Internasional

DOI:

https://doi.org/10.31004/jutin.v8i3.46463

Keywords:

CVRP, Nearest Neighbour, Heuristic, Optimization, Instance

Abstract

Capacitated Vehicle Routing Problem (CVRP) is one of the most popular VRP variants. Nearest Neighbour (NN) is a very simple and very easy heuristic. The basic concept of Nearest Neighbour is to choose the closest point that has never been visited. Russian CVRP Instances created by the author based on Russian history and places in Russia. The total route length for each CVRP Instance is AK-47-CVRP (60857 km), Gagarin-108-CVRP (75920 km), Mendeleev-101-CVRP (116248 km), Petersburg-182-CVRP (2713 km), Popov-250-CVRP (164974 km), Russia-10-Nodes-CVRP (15911 km), Russia-20-Nodes-CVRP (21480 km), Siege-of-Leningrad-872-CVRP (11012 km), World-Cup-Stadium-12-CVRP (10793 km) and Yashin-270-CVRP (105616 km).

References

Abidin, S. Z., Jaini, N. I., & Daud, H. (2025). Decision-Making Support in Vehicle Routing Problems: A Review of Recent Literature. Journal of Advanced Research in Applied Sciences and Engineering Technology, 44(2), 124–134. https://doi.org/10.37934/araset.44.2.124134

Bashkim IDRIZI, A. (2020). NECESSITY FOR GEOMETRIC CORRECTIONS OF DISTANCES IN WEB AND MOBILE MAPS Bashkim IDRIZI. 1, 462–470.

Buyukozdemir, K., Bas, A., Yildiz, K., & Uslu, B. C. (2021). A Review of Heuristic Approaches to Vehicle Routing Problems. 2021 IEEE Asia-Pacific Conference on Computer Science and Data Engineering, CSDE 2021, October 2022, 10–15. https://doi.org/10.1109/CSDE53843.2021.9718378

Garey, M. R. (1979). D, S. Johnson, Computers and Intractability. In A Guide to the Theory of NP-Completeness.

Gmbh, U. (n.d.). GeoNames. Retrieved May 24, 2025, from https://www.geonames.org/

Hameed, A. S., Alrikabi, H. M. B., Abdul–razaq, A. A., Nasser, H. K., Mutar, M. L., & Katea, H. H. (2025). A Detailed Review of the Capacitated Vehicle Routing Problem: Model, Computational Complexity, Solutions, and Practical Applications. Journal of Internet Services and Information Security, 15(1), 218–235. https://doi.org/10.58346/JISIS.2025.I1.014

Hansen, J. S. (2011). GNU Octave: Beginner’s Guide: Become a proficient octave user by learning this high-level scientific numerical tool from the ground up. Packt Publishing Ltd.

Kalatzantonakis, P., Sifaleras, A., & Samaras, N. (2020). Cooperative versus non-cooperative parallel variable neighborhood search strategies: a case study on the capacitated vehicle routing problem. Journal of Global Optimization, 78(2), 327–348. https://doi.org/10.1007/s10898-019-00866-y

Kumar, K., Zindani, D., & Davim, J. P. (2019). Optimizing Engineering Problems through Heuristic Techniques. CRC Press.

Liu, F., Lu, C., Gui, L., Zhang, Q., Tong, X., & Yuan, M. (2023). Heuristics for Vehicle Routing Problem: A Survey and Recent Advances. 1–67. http://arxiv.org/abs/2303.04147

Masudin, I., Sa’Diyah, R. F., Utama, D. M., Restuputri, D. P., & Jie, F. (2019). Capacitated Vehicle Routing Problems: Nearest Neighbour vs. Tabu Search. International Journal of Computer Theory and Engineering, 11(4), 76–79. https://doi.org/10.7763/IJCTE.2019.V11.1246

Nilsson, C. (2003). Heuristics for the traveling salesman problem. Linkoping University, 38(0085–9), 26.

Quarteroni, A., Saleri, F., & Gervasio, P. (2006). Scientific computing with MATLAB and Octave (Vol. 3). Springer.

Sanggala, E., & Bisma, M. A. (2023a). Analysis of The Ant Number Effects on Ant Colony Optimization for Solving Russia-20-Nodes-SDVRP Instance. Sainteks: Jurnal Sain Dan Teknik, 5(2), 163–174.

Sanggala, E., & Bisma, M. A. (2023b). Perbandingan Savings Algorithm dengan Nearest Neighbour dalam Menyelesaikan Russian TSP Instances. Jurnal Media Teknik Dan Sistem Industri, 7(1), 27. https://doi.org/10.35194/jmtsi.v7i1.3039

Sharma, S. K., Routroy, S., & Yadav, U. (2018). Vehicle routing problem: recent literature review of its variants. International Journal of Operational Research, 33(1), 1–31.

Toth, P., & Vigo, D. (2002). The vehicle routing problem. SIAM.

Downloads

Published

2025-07-04

How to Cite

Sanggala, E., & Bisma, M. A. (2025). Penyelesaian Capacitated Vehicle Routing Problem (CVRP) dengan Nearest Neighbour (Studi Kasus: Russian CVRP Instances). Jurnal Teknik Industri Terintegrasi (JUTIN), 8(3), 2586–2599. https://doi.org/10.31004/jutin.v8i3.46463

Issue

Vol. 8 No. 3 (2025): July

Section

Articles of Research

License

Copyright (c) 2025 Ekra Sanggala, Muhammad Ardhya Bisma

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.