Penyelesaian Capacitated Vehicle Routing Problem (CVRP) dengan Nearest Neighbour (Studi Kasus: Russian CVRP Instances)
DOI:
https://doi.org/10.31004/jutin.v8i3.46463Keywords:
CVRP, Nearest Neighbour, Heuristic, Optimization, InstanceAbstract
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
How to Cite
Issue
Section
License
Copyright (c) 2025 Ekra Sanggala, Muhammad Ardhya Bisma
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
