A Comparative Study of Capacitated Vehicle Routing Problem Heuristic Model
Abstract
CVRP is a variant of VRP that can be used to find the minimum distance and number of vehicles. In this paper, three algorithm for initial solutions are compared to find the minimum distance for shipping goods from distribution center to all outlets routinely in West Jakarta – Improved Clarke and Wright (ICW) algorithm, Karagul Tokat Aydemir (KTA) algorithm , and Sweeping – Cluster First Route Second algorithm. The results show that Sweeping algorithm is the shortest total distance compared to other two algorithm which is 48.57% shorter than KTA algorithm and 33.33% shorter to ICW algorithm. Larger sample sizes need to be evaluated to strengthen this findings.
Index Terms—CVRP, ICW, KTA, Sweeping algorithm
Downloads
Download data is not yet available.
References
[1] K. Jerabek, P. Majercak, T. Kliestik, K. Valaskova,”Application of Clark and Wright’s Savings Algorithm Model to Solve Routing Problem in Supply Logistics”. 2016. Preliminary communication. DOI 10.17818/NM/2016/SI7.
[2] A. Chandra and B. Setiawan,”Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method”. 2018. Jurnal Manajemen Transportasi & Logistik, Vol.05 no.02, p.105 – 116. ISSN 2355-4721.
[3] A. Chandra and A. Naro,”Studi Komparatif Metaheuristics untuk Mengoptimalkan Jalur Distribusi”. 2019. Laporan Riset Internal (unpublished report). Universitas Mercu Buana
[4] G.D.Konstantakopoulos, S.P. Gayialis, I.P.Tatsiopoulos,”Vehicle Routing Problem for Urban Freight Transportation: A Review”, Conference Paper, June 2017.
[5] T. Caric, S. Pasagic, Z. Lanovic,”Vehicle Routing Problem Models”, Science in Traffic Review Volume 16 No.1, 2004, pp.59-62.
[6] F.W. Takes and W.A. Kosters,”Applying Monte Carlo Techniques in the Capacitated Vehicle Routing Problem”, White Paper, Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands, 2010.
[7] T. Pichpibul and R. Kawtummachai,”An Improved Clarkee and Wrigth Savings Algorithm for the Capacitated Vehicle Routing Problem”, Science Asia 38, 2012, pp.307-318.
[8] Y. Marinakis, A. Migdalas,”Annotated Bibliography in Vehicle Routing”, Operations Research, An International Journal Volume 7 no.1, 2007, pp.27-46.
[9] F.W. Takes and W.A. Kosters,”Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem”, Leiden Institute of Advanced Computer Science, Leiden University, 2010, The Netherlands.
[10] R.B.S. Shankar, K.D. Reddy, P. Venkataramaiah,”Solution to a Capacitated Vehicle Routing Problem Using Heuristics and Firefly Algorithm”, International Journal of Applied Engineering Research Volume 13 no.21, 2018, pp. 15247-15254. ISSN 0973-4562.
[11] T. Pichpibul and R. Kawtummachai,”A Heuristic Approach Based on Clarkee – Wright Algorithm for Open Vehicle Routing Problem”, The Scientific World Journal Volume 2013. http://dx.doi.org/10.1155/2013/874349.
[12] K. Karagul, S. Tokat, F. Aydemir,”Physics-inspired Optimization Algorithm for Obtaining Initial Routes of Capacitated Vehicle Routing Problem”, EURO Working Group on Vehicle Routing and Logistic Optimization (VeRoLog), 2014, Oslo, Norway.
[13] K. Karagul, S. Tokat, F. Aydemir,”A New Algorithm to The Construction of The Initial Routes for the Capacitated Vehicle Routing Problem”, Journal of Engineering Sciences and Design Volume 4 no.3, 2016, pp.215-216.
[14] N. Suthikarnnarunai,”A Sweeping Algorithm for the Mix Fleet Vehicle Routing Problem”, Proceedings of International Multiconference of Engineers and Computer Scientists Volume II, 2008, Hong Kong.
[15] R.C. Larson and A.R. Odoni,”Urban Operations Research. Chapter 6: Applications of Network Models”. 1981. Prentice Hall, New Jersey.This article can be downloaded at this web: http://mit.edu/urban_or_book/www/book/chapter6/6.4.12.html
[16] E.Baran,”Route Determination for Capacitated Vehicle Routing Problem with Two Different Hybrid Heuristic Algorithm”, International Journal of Engineering Science and Application Volume 2 no.2, 2018, pp.55-64.
[17] K.Karagul, S.Tokat, E.Aydemir,”A New Algorithm for the Establishment of Initial Route for Capacity Constaints Vehicle Routing Problem”, Journal of Engineering Sciences and Design Volume 4 no.3, 2016, pp.215-226. DOI: 10.21923/jesd.60313.
[18] K.Karagul, M.G. Kay, S. Tokat, “A New Method for Generating Initial Solutions fo Capacitated Vehicle Routing Problem”, Journal of Science 31(2), 2018, pp.489-513.
[19] R.F. Hartl, S.N. Parragh,”Transportation Logistics: An Introduction to Vehicle Route Problem: Cluster First Route Second Heuristics”, 2012. This article can be downloaded at web address: https://prolog.univie.ac.at/teaching/LVAs/KFKTL/WS%2012/TL-Part5-VRP-Intro-Handout.pdf
[20] R.B.S. Shankar, K.D. Reddy,”A Comparative Study on Heuristic and Metaheuristic Approach in Solving a Capacitated Vehicle Routing Problem”, International Journal of Innovative Science and Research Technology Volume 3, Issue 9, September 2018, pp.94-98. ISSN no.2456-2165.
[21] B. Wibowo. (2016). Budhi’s Notes. Part II – Solving Vehicle Routing Problem with Excel. Available: https://budhiwibowo.files.wordpress.com/2016/03/dss-case-2-vehicle-routing-problem.xlsx.
[2] A. Chandra and B. Setiawan,”Optimizing the Distribution Routes Using Vehicle Routing Problem (VRP) Method”. 2018. Jurnal Manajemen Transportasi & Logistik, Vol.05 no.02, p.105 – 116. ISSN 2355-4721.
[3] A. Chandra and A. Naro,”Studi Komparatif Metaheuristics untuk Mengoptimalkan Jalur Distribusi”. 2019. Laporan Riset Internal (unpublished report). Universitas Mercu Buana
[4] G.D.Konstantakopoulos, S.P. Gayialis, I.P.Tatsiopoulos,”Vehicle Routing Problem for Urban Freight Transportation: A Review”, Conference Paper, June 2017.
[5] T. Caric, S. Pasagic, Z. Lanovic,”Vehicle Routing Problem Models”, Science in Traffic Review Volume 16 No.1, 2004, pp.59-62.
[6] F.W. Takes and W.A. Kosters,”Applying Monte Carlo Techniques in the Capacitated Vehicle Routing Problem”, White Paper, Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands, 2010.
[7] T. Pichpibul and R. Kawtummachai,”An Improved Clarkee and Wrigth Savings Algorithm for the Capacitated Vehicle Routing Problem”, Science Asia 38, 2012, pp.307-318.
[8] Y. Marinakis, A. Migdalas,”Annotated Bibliography in Vehicle Routing”, Operations Research, An International Journal Volume 7 no.1, 2007, pp.27-46.
[9] F.W. Takes and W.A. Kosters,”Applying Monte Carlo Techniques to the Capacitated Vehicle Routing Problem”, Leiden Institute of Advanced Computer Science, Leiden University, 2010, The Netherlands.
[10] R.B.S. Shankar, K.D. Reddy, P. Venkataramaiah,”Solution to a Capacitated Vehicle Routing Problem Using Heuristics and Firefly Algorithm”, International Journal of Applied Engineering Research Volume 13 no.21, 2018, pp. 15247-15254. ISSN 0973-4562.
[11] T. Pichpibul and R. Kawtummachai,”A Heuristic Approach Based on Clarkee – Wright Algorithm for Open Vehicle Routing Problem”, The Scientific World Journal Volume 2013. http://dx.doi.org/10.1155/2013/874349.
[12] K. Karagul, S. Tokat, F. Aydemir,”Physics-inspired Optimization Algorithm for Obtaining Initial Routes of Capacitated Vehicle Routing Problem”, EURO Working Group on Vehicle Routing and Logistic Optimization (VeRoLog), 2014, Oslo, Norway.
[13] K. Karagul, S. Tokat, F. Aydemir,”A New Algorithm to The Construction of The Initial Routes for the Capacitated Vehicle Routing Problem”, Journal of Engineering Sciences and Design Volume 4 no.3, 2016, pp.215-216.
[14] N. Suthikarnnarunai,”A Sweeping Algorithm for the Mix Fleet Vehicle Routing Problem”, Proceedings of International Multiconference of Engineers and Computer Scientists Volume II, 2008, Hong Kong.
[15] R.C. Larson and A.R. Odoni,”Urban Operations Research. Chapter 6: Applications of Network Models”. 1981. Prentice Hall, New Jersey.This article can be downloaded at this web: http://mit.edu/urban_or_book/www/book/chapter6/6.4.12.html
[16] E.Baran,”Route Determination for Capacitated Vehicle Routing Problem with Two Different Hybrid Heuristic Algorithm”, International Journal of Engineering Science and Application Volume 2 no.2, 2018, pp.55-64.
[17] K.Karagul, S.Tokat, E.Aydemir,”A New Algorithm for the Establishment of Initial Route for Capacity Constaints Vehicle Routing Problem”, Journal of Engineering Sciences and Design Volume 4 no.3, 2016, pp.215-226. DOI: 10.21923/jesd.60313.
[18] K.Karagul, M.G. Kay, S. Tokat, “A New Method for Generating Initial Solutions fo Capacitated Vehicle Routing Problem”, Journal of Science 31(2), 2018, pp.489-513.
[19] R.F. Hartl, S.N. Parragh,”Transportation Logistics: An Introduction to Vehicle Route Problem: Cluster First Route Second Heuristics”, 2012. This article can be downloaded at web address: https://prolog.univie.ac.at/teaching/LVAs/KFKTL/WS%2012/TL-Part5-VRP-Intro-Handout.pdf
[20] R.B.S. Shankar, K.D. Reddy,”A Comparative Study on Heuristic and Metaheuristic Approach in Solving a Capacitated Vehicle Routing Problem”, International Journal of Innovative Science and Research Technology Volume 3, Issue 9, September 2018, pp.94-98. ISSN no.2456-2165.
[21] B. Wibowo. (2016). Budhi’s Notes. Part II – Solving Vehicle Routing Problem with Excel. Available: https://budhiwibowo.files.wordpress.com/2016/03/dss-case-2-vehicle-routing-problem.xlsx.
Published
2020-12-14
How to Cite
CHANDRA, Agung; NARO, Aulia.
A Comparative Study of Capacitated Vehicle Routing Problem Heuristic Model.
International Journal of Engineering and Emerging Technology, [S.l.], v. 5, n. 2, p. 94-100, dec. 2020.
ISSN 2579-5988.
Available at: <https://ojs.unud.ac.id/index.php/ijeet/article/view/61535>. Date accessed: 25 apr. 2024.
doi: https://doi.org/10.24843/IJEET.2020.v05.i02.p015.
Section
Articles
Indexed By
