Region Division in Logistics Distribution With a Two-Stage Optimization Algorithm

Abstract

When facing the problem of modern logistics distribution under the large-scale network, the reasonable delivery task allocation has become an important part. For this problem, this paper uses the idea of decentralized control to establish a region division model in logistics distribution and transforms it into the multiple traveling salesmen problem with constraints of the road network and task allocation. The optimization goal of the model is to minimize the sum of the distances for logistics transport agents traveling all demand points in the system, with the constraints on the equilibrium of commodity requirements in each sub region. Then, a two-stage algorithm is proposed to solve the model. In the first stage, the $K$ -means clustering method is used to obtain a highly feasible initial solution; In the second stage, the initial solution is optimized by the algorithm which is combining swap algorithm and tabu search algorithm. In the two-stage solution evaluation, the TSP solution based on the Lin-Kernighan algorithm is applied to obtain the sets of demand points with ranking of the route and the corresponding shortest distances for each divided sub region. Finally, to verify the effectiveness of the proposed model and solving method, two cases are presented in this paper. The region division method in logistics distribution proposed in this paper not only helps to reduce the total distance, but also helps to balance the workload of the logistics transport agents, thereby making great potential to reduce logistics costs and improving the overall operational efficiency of logistics distribution.

Keywords

• Distribution region
• Lin-Kernighan algorithms
• MTSP
• K-mean
• swap algorithm
• tabu search