A combination K-means clustering and 2-opt algorithm for solving the two echelon e-commerce logistic distribution

• Autorzy: Zuhanda Muhammad Khahfi , Suwilo Saib , Sitompul Opim , Mardiningsih Mardiningsih

Identyfikatory

DOI

10.17270/J.LOG.2022.734

• Języki publikacji: EN

Abstrakty

EN

Background: The rise of e-commerce in the community makes competition between logistics companies increasingly tight. Every e-commerce application offers the convenience and choices needed by the community. The Two-Echelon Vehicle Routing Problem (2E-VRP) model has been widely developed in recent years. 2E-VRP makes it possible for customers to combine shipments from several different stores due to satellites in their distribution stream. The aim of this paper is to optimize a two-echelon logistics distribution network for package delivery on e-commerce platforms, where vans operate in the first echelon and motorcycles operate in the second echelon. The problem is formulated as 2E-VRP, where total travel costs and fuel consumption are minimized. This optimization is based on determining the flow in each echelon and choosing the optimal routing solution for vans and motorcycles. Methods: This paper proposes a combination of the K-means Clustering Algorithm and the 2-opt Algorithm to solve the optimization problem. Many previous studies have used the K-means algorithm to help streamline the search for solutions. In the solution series, clustering is carried out between the satellite and the customer in the first echelon using the K-means algorithm. To determine the optimal k-cluster, we analyzed it using the silhouette, gap statistic, and elbow methods. Furthermore, the routing at each echelon is solved by the 2-opt heuristic method. At the end of the article, we present testing of several instances with the different number of clusters. The study results indicate an influence on the determination of the number of clusters in minimizing the objective function. Results: This paper looks at 100 customers, 10 satellites, and 1 depot. By working in two stages, the first stage is the resolution of satellite and customer problems, and the second stage is the resolution of problems between the satellite and the depots. We compare distance and cost solutions with a different number of k-clusters. From the test results, the number of k-clusters shows an effect of number and distance on the solution. Conclusions: In the 2E-VRP model, determining the location of the cluster between the satellite and the customer is very important in preparing the delivery schedule in logistics distribution within the city. The benefit is that the vehicle can divide the destination according to the location characteristics of the satellite and the customer, although setting the how many clusters do not guarantee obtaining the optimal distance. And the test results also show that the more satellites there are, the higher the shipping costs. For further research, we will try to complete the model with the metaheuristic genetic algorithm method and compare it with the 2-opt heuristic method.

Słowa kluczowe

EN

two echelon vehicle routing problem; e-commerce; logistic distribution; K-means clustering; 2-opt algorithm

PL

problem marszrutyzacji; e-commerce; dystrybucja; grupowanie K-średnich

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2022
• Tom: Vol. 18, no. 2
• Strony: 213--225
• Opis fizyczny: Bibliogr. 29 poz., rys., tab., wykr.

Twórcy

autor

Zuhanda Muhammad Khahfi

• Graduate School of Mathematics, Universitas Sumatera Utara, Medan, Indonesia

• https://orcid.org/0000-0002-6850-5561

autor

Suwilo Saib

• Department of mathematics, Universitas Sumatera Utara, Medan, Indonesia

• https://orcid.org/0000-0002-6653-9127

autor

Sitompul Opim

• Department of Information Technology, Universitas Sumatera Utara, Medan, Indonesia

• https://orcid.org/0000-0001-6069-184

autor

Mardiningsih Mardiningsih

• Department of Mathematics, Medan, Indonesia

• https://orcid.org/0000-0002-1565-730X

Bibliografia

• 1. Arkhand, M., Jannat, Z. and Murase, K., 2017. Capacitated Vehicle Routing Problem Solving using Adaptive Sweep and Velocity Tentative PSO. International Journal of Advanced Computer Science and Applications , 8(12): 288-295. https://doi.org/10.14569/ijacsa.2017.081237
• 2. Agárdi, A., Kovács, L. and Bányai, T., 2021. An Attraction Map Framework of a Complex Multi-Echelon Vehicle Routing Problem with Random Walk Analysis. Applied Sciences, 11(5): 1-23. https://doi.org/10.3390/app11052100
• 3. Barma, P.S., Dutta, J. and Mukherjee, A., 2019. A 2-opt guided discrete antlion optimizationalgorithm for multi depotvehicle routing problem. Decision Making: Applications in Management and Engineering, 2(2):112:125.
• 4. Breunig, U., Baldacci, R., Hartl, R.F. and Vidal, T., 2019. The electric two-echelon vehicle routing problem. Computers and Operations Research, 103: 1-28. https://doi.org/10.1016/j.cor.2018.11.005
• 5. Chen, C., Demir, E. and Huang, Y., 2021. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots. European Journal of Operational Research, 294(3): 12-34. https://doi.org/10.1016/j.ejor.2021.02.027
• 6. El-Mandouh, A.M., Mahmoud, H.A., Abd-Elmegid, L.A. and Haggag, M.H. 2019. Optimized K-means clustering model based on gap statistic. International Journal of Advanced Computer Science and Applications 10(1): 183-188. https://doi.org/10.14569/IJACSA.2019.0100124
• 7. Englert, M., Röglin, H. and Vöcking, B., 2014. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica, 68:190-264. https://doi.org/10.1007/s00453-013-9801-4
• 8. Erniyati and Citra, P., 2019. The implementation of the Kruskal algorithm for the search for the shortest path to the location of a building store in the city of Bogor. In: IOP Conference Series: Materials Science and Engineering, 621 1: 1-9. https://doi.org/10.1088/1757-899X/621/1/012010
• 9. He, Y., Wen, J. and Huang, M., 2016. Study on emergency relief VRP based on clustering and PSO. 11th International Conference on Computational Intelligence and Security, 1: 43-47. https://doi.org/10.1109/CIS.2015.19
• 10. Hougardy, S., Zaiser, F. and Zhong, X. 2020. The approximation ratio of the 2-Opt Heuristic for the metric Traveling Salesman Problem. Operations Research Letters, 48(4): 401-404. https://doi.org/10.1016/j.orl.2020.05.007
• 11. Ikotun, A.M., Almutari, M.S. and Ezugwu, A.E. 2021. K‐means‐based nature‐inspired metaheuristic algorithms for automatic data clustering problems: Recent advances and future directions. Applied Sciences (Switzerland), 11(23): 1-61. https://doi.org/10.3390/app112311246
• 12. Kassem, S., Korayem, L., Khorshid, M. and Tharwat, A. 2019. A hybrid bat algorithm to solve the capacitated vehicle routing problem. Novel Intelligent and Leading Emerging Sciences Conference, 1: 222-225. https://doi.org/10.1109/NILES.2019.8909300
• 13. Kovács, L., Agárdi, A. and Bányai, T., 2020. Fitness landscape analysis and edge weighting-based optimization of vehicle routing problems. Processes, 8(11): 1-22. https://doi.org/10.3390/pr8111363
• 14. Lee, K., Chae, J., Song, B. and Choi, D., 2020. A model for sustainable courier services: Vehicle routing with exclusive lanes. Sustainability (Switzerland), 12(3): 1-19. https://doi.org/10.3390/su12031077
• 15. Leon Villalba, A.F. and Cristina Gonzalez La Rotta, E., 2020. Comparison of Dbscan and K-means clustering methods in the selection of representative clients for a vehicle routing model. Congreso Internacional de Innovacion y Tendencias en Ingenieria, CONIITI 2020 - Conference Proceedings, 1: 1-6. https://doi.org/10.1109/CONIITI51147.2020.9240399
• 16. Li, H., Wang, H., Chen, J. and Bai, M., 2020. Two-echelon vehicle routing problem with time windows and mobile satellites. Transportation Research Part B: Methodological, 138: 179-201. https://doi.org/10.1016/j.trb.2020.05.010
• 17. Li, H., Wang, H., Chen, J. and Bai, M., 2021. Two-echelon vehicle routing problem with satellite bi-synchronization. European Journal of Operational Research, 288(3): 1- 37. https://doi.org/10.1016/j.ejor.2020.06.019
• 18. Liu, D., Liu, D., Deng, Z., Mao, X., Yang, Y., Yang, Y. and Kaisar, E.I., 2020. Two-Echelon Vehicle-Routing Problem: Optimization of Autonomous Delivery Vehicle-Assisted E-Grocery Distribution. IEEE Access, 8: 108705-108719. https://doi.org/10.1109/ACCESS.2020.3001753
• 19. McNabb, M.E., Weir, J.D., Hill, R.R. and Hall, S.N., 2015. Testing local search move operators on the vehicle routing problem with split deliveries and time windows. Computers and Operations Research, 56: 93-109. https://doi.org/10.1016/j.cor.2014.11.007
• 20. Rahman, A. and Asih, H.M., 2020. Optimizing shipping routes to minimize cost using particle swarm optimization. International Journal of Industrial Optimization, 1(1): 53-60. https://doi.org/10.12928/ijio.v1i1.1605
• 21. Rana, S.M.S., Hoque, M.R. and Kabir, M.H., 2019. Evaluation of Security Threat of ZigBee Protocol to Enhance the Security of ZigBee based IoT Platform. Journal of Applied Science and Technology, 11(01), 37-45.
• 22. Redi, A.A.N.P., Jewpanya, P., Kurniawan, A.C., Persada, S.F., Nadlifatin, R. and Dewi, O.A.C., 2020., A simulated annealing algorithm for solving two-echelon vehicle routing problem with locker facilities. Algorithms, 13(9): 1-14. https://doi.org/10.3390/a13090218
• 23. Sabo, C., Pop, P.C. and Horvat-Marc, A., 2020. On the selective vehicle routing problem. Mathematics, 8(5): 1-11. https://doi.org/10.3390/MATH8050771
• 24. Saputra, D.M., Saputra, D. and Oswari, L.D., 2020. Effect of Distance Metrics in Determining K-Value in K-means Clustering Using Elbow and Silhouette Method. Advances in Intelligent Systems Research, 172: 341-346. https://doi.org/10.2991/aisr.k.200424.051
• 25. Shi, C., Wei, B., Wei, S., Wang, W., Liu, H. and Liu, J., 2021. A quantitative discriminant method of elbow point for the optimal number of clusters in clustering algorithm. Eurasip Journal on Wireless Communications and Networking, 1: 1-15. https://doi.org/10.1186/s13638-021-01910-w
• 26. W. Rizkallah, L., F. Ahmed, M. and M. Darwish, N., 2020. A clustering algorithm for solving the vehicle routing assignment problem in polynomial time. International Journal of Engineering & Technology, 9(1): 1-13. https://doi.org/10.14419/ijet.v9i1.22231
• 27. Xia, X., Liao, W., Zhang, Y. and Peng, X., 2021. A discrete spider monkey optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing, 111: 1-13. https://doi.org/10.1016/j.asoc.2021.107676
• 28. Yan, X., Huang, H., Hao, Z. and Wang, J., 2020. A Graph-Based Fuzzy Evolutionary Algorithm for Solving Two-Echelon Vehicle Routing Problems. IEEE Transactions on Evolutionary Computation, 24(1): 129-141. https://doi.org/10.1109/TEVC.2019.2911736
• 29. Zhang, Y., Zhou, S., Ji, X., Chen, B., Liu, H., Xiao, Y. and Chang, W., 2021. The Mathematical Model and an Genetic Algorithm for the Two-Echelon Electric Vehicle Routing Problem. Journal of Physics: Conference Series, 1813: 1-7. https://doi.org/10.1088/1742-6596/1813/1/012006

Uwagi

PL

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).