两级选址-路径问题的大规模邻域搜索模拟退火算法
Simulated annealing with large-neighborhood search for two-echelon location routing problem
-
摘要: 针对目前越来越普遍的多级配送模式,建立以总成本最小为目标函数的两级选址-路径问题模型,并提出了大规模邻域搜索模拟退火算法进行求解.在模拟退火算法框架中,嵌入大规模邻域搜索过程,包含破坏、重组和局部搜索方法,从而进一步提高算法在解空间中构建邻域的范围.采用两级选址-路径问题标准算例对算法求解效果进行验证,并与标准模拟退火算法和国际已知最优解进行对比.结果显示,所建模型和算法正确有效,并且在求解大规模问题时算法能够取得相对更好的优化结果.Abstract: Considering the multi-level distribution network has becoming more and more common, a two-echelon location routing problem (2E-LRP) model was established based on minimum total cost objective function. To solve the 2E-LRP model, a simulated annealing with large neighborhood search algorithm was developed. In the framework of the simulated annealing algorithm, a large neighborhood search process was embedded, which includes destroy-and-repair principles as well as some local search methods to further improve the range of the neighborhood search in the solution space. The proposed model and algorithm were tested by two-echelon benchmark instances and compared with the standard simulated annealing algorithm solutions and the internationally best known solutions. The results show the proposed model and algorithm to be correct and that the algorithm can obtain better solutions than standard simulated annealing when solving large-scale problems.