Jessi Febria1, Christine Dewi1,2, Evangs Mailoa1*

1 Faculty of Information Technology, Satya Wacana Christian University, Central Java, Indonesia
2 Department of Information Management, Chaoyang University of Technology, Taiwan, ROC


 

Download Citation: |
Download PDF


ABSTRACT


Vaccines are the solution that is currently underway to tackle COVID-19. In this paper, vaccine distribution for hospitals in Central Java is developed. The problem case in this paper is classified as a Capacitated Vehicle Routing Problem (CVRP). The method proposed is using an initial route that follows the cluster-first route-second method (CFRS). The same size K-means is used for the clustering phase and the Greedy algorithm is used for the routing phase. The result of the initial route is a clustered route for each vehicle with a balanced capacity. Then, each cluster was re-optimized using metaheuristics Guided Local Search from Google OR-tools. Our experiment results have proven that using the initial route has the effect of reducing runtime by 97.37% - 99.17% when compared to without the initial route. This is because using initial routes with the same size K-means means breaking the problem into parts, then using the Greedy algorithm can reduce the number of possible routes. However, the total distance increased by 8.22% - 16.69% because no cluster member is allowed to move to another cluster.


Keywords: Capacitated vehicle routing problem, Vaccine distribution, K-means.


Share this article with your colleagues

 


REFERENCES


  1. Ancele, Y., Hà, M.H., Lersteau, C., Matellini, D.B., Nguyena, T.T. 2021. Toward a more flexible VRP with pickup and delivery allowing consolidations, Transportation Research Part C: Emerging Technologies, 128, p. 103077. DOI: https://doi.org/10.1016/j.trc.2021.103077

  2. Caric, T., Gold, H. 2008. Vehicle routing problem. Edited by T. Caric and H. Gol. InTech. DOI: 10.5772/64.

  3. Comert, S.E., Yazgan, H.R., Kır, S., Yener, F. 2018. A cluster first-route second approach for a capacitated vehicle routing problem: A case study, International Journal of Procurement Management, 11, 399–419. DOI: 10.1504/IJPM.2018.092766.

  4. Dantzig, G.B., Ramser, J.H. 1959. The truck dispatching problem, Management Science, 6, 80–91. DOI: https://doi.org/10.1287/mnsc.6.1.80

  5. Delahaye, D., Chaimatanan, S., Mongeau, M. 2019. Simulated annealing: From basics to applications, International Series in Operations Research and Management Science, 272, 1–35. DOI: 10.1007/978-3-319-91086-4_1.

  6. Dorigo, M., Socha, K. 2018. An introduction to ant colony optimization, Handbook of Approximation Algorithms and Metaheuristics, Second Edition, 395–408. DOI: 10.1201/9781351236423-23.

  7. Gil, A.F., Sánchez, M.G., Lalla-Ruiz, E., Castro, C. 2020. Cumulative VRP with time windows: A trade-off analysis, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12433 LNCS, 277–291. DOI: https://doi.org/10.1007/978-3-030-59747-4_18

  8. Google developers, 2020. Google OR-Tools reference. Available at: https://developers.google.com/optimization/reference (Accessed: March 31, 2021).

  9. Ibrahim, A.A., Lo, N., Abdulaziz, R.O., Ishaya, J.A. 2019. Capacitated vehicle routing problem, International Journal of Research-Granthaalayah, 7, 310–327. doi: https://doi.org/10.29121/granthaalayah.v7.i3.2019.976

  10. Jayarathna, N., Lanel, J., Juman, Z.A.M.S. 2020. Five years of multi-depot vehicle routing problems, Journal of Sustainable Development of Transport and Logistics, 5, 109–123. DOI: 10.14254/JSDTL.2020.5-2.10.

  11. Kramer, O. 2017. Genetic algorithms, Studies in Computational Intelligence, 679, 11–19. DOI: 10.1007/978-3-319-52156-5_2.

  12. Li, L., Chen, Y., Meng, J. 2020. Improved Tabu search algorithm for solving the vehicle routing problem with soft time windows in B2C environment, in Proceedings of the 32nd Chinese Control and Decision Conference, CCDC 2020. Institute of Electrical and Electronics Engineers Inc., 3629–3633. DOI: 10.1109/CCDC49329.2020.9164444.

  13. Lloyd, S. 1982. Least squares quantization in PCM, IEEE Transactions on Information Theory, 28, 129–137.

  14. Mackay, D.J.C. 1995. Information theory, Inference, and Learning Algorithms. Available at: http://www.inference.phy.cam.ac.uk/mackay/itila/ (Accessed: March 31, 2021).

  15. Mostafa, N., Eltawil, A. 2017. Solving the heterogeneous capacitated vehicle routing problem using K-means clustering and valid inequalities, Proceedings of the International Conference on Industrial Engineering and Operations Management Rabat, Morocco, 11–13.

  16. Perron, L. 2011. Operations research and constraint programming at google, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag, p. 2. DOI: 10.1007/978-3-642-23786-7_2.

  17. Shalaby, M.A.W., Mohammed, A.R., Kassem, S. 2020. Modified fuzzy c-means clustering approach to solve the capacitated vehicle routing problem, Proceedings - 2020 21st International Arab Conference on Information Technology, ACIT. DOI: 10.1109/ACIT50332.2020.9300082.

  18. Sinaga, K.P., Yang, M.S. 2020. Unsupervised K-means clustering algorithm, IEEE Access, 8, 80716–80727. DOI: 10.1109/ACCESS.2020.2988796.

  19. Sivaram, M., Batri, K., Mohammed, A.S., Porkodi, V. 2019. Exploiting the local optima in genetic algorithm using Tabu search, Indian Journal of Science and Technology. DOI: 10.17485/just/2019/v12i1/139577.

  20. Smith, K.J. 2011. Precalculus: A functional approach to graphing and problem solving. Jones\& Bartlett Publishers.

  21. Tanggap COVID-19 Provinsi Jawa Tengah, 2021. Rumah sakit rujukan COVID-19 Di jawa tengah. Available at: https://corona.jatengprov.go.id/rumah-sakit (Accessed: February 23, 2021).

  22. Tsang, E.P.K. 2016. Market microstructure view project guided local search. doi: 10.1007/978-3-319-07153-4_2-1.

  23. Weintraub, R.L., Subramanian, L., Karlage, A., Ahmad, I., Rosenberg, J. 2021. Covid-19 vaccine to vaccination: Why leaders must invest in delivery strategies now, Health Affairs, 40, 33–41. DOI: https://doi.org/10.1377/hlthaff.2020.01523

  24. World Health Organization R&D Blue Print, 2021. Draft landscape and tracker of COVID-19 candidate vaccines. Available at: https://www.who.int/publications/m/item/draft-landscape-of-covid-19-candidate-vaccines (Accessed: March 31, 2021).


ARTICLE INFORMATION


Received: 2021-04-20
Revised: 2021-08-10
Accepted: 2021-09-07
Publication Date: 2021-12-01


Cite this article:

Febria, J., Dewi, C., Mailoa, E. Optimization of capacitated vehicle routing problem using initial route with same size K-means and greedy algorithm for vaccines distribution. International Journal of Applied Science and Engineering, 18, 2021103. https://doi.org/10.6703/IJASE.202112_18(6).002

  Copyright The Author(s). This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are cited.