A COMBINATION K-MEANS CLUSTERING AND 2-OPT ALGORITHM FOR SOLVING THE TWO ECHELON E-COMMERCE LOGISTIC DISTRIBUTION

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.