A Novel Hybrid Metaheuristic for Solving Automobile Part Delivery Logistics With Clustering Customer Distribution

With the continuous maturity of the automobile industry, the cluster network effect has been gradually formed among automobile parts' suppliers. How to carry out reasonable and efficient distribution in the cluster network has become one of the greatest challenges in today's automobile manufacturers. In this paper, we conducted a field survey of a real-world automobile logistics company and collected data. After analyzing the relevant transportation modes, we concluded that the problem could be classified as a clustered vehicle routing problem (CluVRP). A CluVRP considers gathering customers according to geographical proximity on the basis of the classical capacitated vehicle routing problem (CVRP). An accompanying problem is that there is a hard constraint that all customers in a cluster must be served consecutively by the same vehicle. Because the CluVRP is NP-hard, a hybrid metaheuristic solution approach was proposed. First, the shortest distance best fit decreasing (SD-BFD) algorithm was used to construct an initial solution. Second, a clustering feature was considered in order to divide the problem into two levels for optimization: the intra-cluster level and the inter-cluster level. For the intra-cluster level, the variable neighborhood search (VNS) was applied; for the inter-cluster level, the Lin-Kernighan (LK) considering dummy point was employed for optimizing. The computational performances of the hybrid metaheuristic algorithms are tested on three sets of instances and compared with the results from previous papers and the company's manually calculated solutions. The results show that the proposed algorithm is excellent in both the operation time and the final solution value, which is significant to improve distribution efficiency, reduce transportation costs, and improve customer satisfaction.