Logistics Distribution Network Shortest Path Based On Pruning Strategy

With the development of the logistics distribution industry,the size of the logistics network increases rapidly and the distribution path becomes more and more complex.As a basic problem of the logistic,the shortest path problem has been paid much attention.The traditional shortest path problem is mainly used to find the path with shortest distance,however,we should take the time and cost of the distribution path into account so as to apply to the actual logistics distribution networks.So we need to calculate the shortest path under specific constraints.Besides,the traditional algorithms cost large calculation and have low computational efficiency when solving complex networks,and they even can't deal with the large-scale networks.Therefore,finding an effective way to deal with the shortest path problem in large and complex scale of networks is the urgent problem to be solved.In this paper,we proposed a method for shortest path problem based on a pruning strategy.In this method the actual logistics distribution network is transformed into a directed acyclic graph model,and two indexes are established for the vertices: the dual-interval index and the cost index.According to the indexes,we combine the pruning algorithms with the traditional shortest path algorithms,then the LSP algorithm based on cost index and the LSP-D algorithm based on dual-interval index and a dynamic pruning algorithm called LSP-V algorithm are formed.Final a real network data experiment was done to show the effectiveness of the pruning strategy.And the experiment on public large-scale data network proved that the LSP-V algorithm is the most efficient.