兩級選址-路徑問題的大規模鄰域搜索模擬退火算法

李想; 李蘇劍; 李宏

doi:10.13374/j.issn2095-9389.2017.06.019

兩級選址-路徑問題的大規模鄰域搜索模擬退火算法

doi: 10.13374/j.issn2095-9389.2017.06.019

北京科技大學機械工程學院, 北京 100083

詳細信息

中圖分類號: F224.3
計量
- 文章訪問數: 886
- HTML全文瀏覽量: 278
- PDF下載量: 59
- 被引次數: 0
出版歷程
- 收稿日期: 2016-11-02

Simulated annealing with large-neighborhood search for two-echelon location routing problem

School of Mechanical Engineering, University of Science and Technology Beijing, Beijing 100083, China

摘要

摘要: 針對目前越來越普遍的多級配送模式,建立以總成本最小為目標函數的兩級選址-路徑問題模型,并提出了大規模鄰域搜索模擬退火算法進行求解.在模擬退火算法框架中,嵌入大規模鄰域搜索過程,包含破壞、重組和局部搜索方法,從而進一步提高算法在解空間中構建鄰域的范圍.采用兩級選址-路徑問題標準算例對算法求解效果進行驗證,并與標準模擬退火算法和國際已知最優解進行對比.結果顯示,所建模型和算法正確有效,并且在求解大規模問題時算法能夠取得相對更好的優化結果.
- 模擬退火算法 /
- 大規模鄰域搜索 /
- 兩級選址-路徑問題 /
- 破壞重組
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.
- simulated annealing algorithm /
- large-neighborhood search /
- two-echelon location routing problem /
- destroy-and-repair

HTML全文

參考文獻(16)

[1]	Karaoglan I, Altiparmak F, Kara I, et al. A branch and cut algorithm for the location-routing problem with simultaneous pickup and delivery. Eur J Operational Res, 2011, 211(2):318
[4]	Duhamel C, Lacomme P, Prins C, et al. A GRASP×ELS approach for the capacitated location-routing problem. Comput Operations Res, 2010, 37(11):1912
[5]	Marinakis Y. An improved particle swarm optimization algorithm for the capacitated location routing problem and for the location routing problem with stochastic demands. Appl Soft Computing, 2015, 37:680
[6]	Ponboon S, Qureshi A G, Taniguchi E. Branch-and-price algorithm for the location-routing problem with time windows. Transportation Res Part E Logistics Transportation Rev, 2016, 86:1
[7]	Lopes R B, Ferreira C, Santos B S. A simple and effective evolutionary algorithm for the capacitated location-routing problem. Comput Operations Res, 2016, 70:155
[9]	Jacobsen S K, Madsen O B G. A comparative study of heuristics for a two-level routing-location problem. Eur J Operational Res, 1980, 5(6):378
[10]	Nguyen V P, Prins C, Prodhon C. A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem. Eng Appl Artif Intelligence, 2012, 25(1):56
[12]	Steinbrunn M, Moerkotte G, Kemper A. Heuristic and randomized optimization for the join ordering problem. VLDB J, 1997, 6(3):191
[13]	Yu V F, Lin S Y. A simulated annealing heuristic for the open location-routing problem. Comput Operations Res, 2015, 62:184
[14]	Shaw P. Using constraint programming and local search methods to solve vehicle routing problems//International Conference on Principles and Practice of Constraint Programming-CP98. Heidelberg:Springer, 1998:417
[15]	Schrimpf G, Schneider J, Stamm-Wilbrandt H, et al. Record breaking optimization results using the ruin and recreate principle. J Comput Phys, 2000, 159(2):139
[16]	Pisinger D, Ropke S. Large neighborhood search//Handbook of Metaheuristics. New York:Springer US, 2010:399
[18]	Breunig U, Schmid V, Hartl R F, et al. A large neighborhood based heuristic for two-echelon routing problems. Comput Operations Res, 2016, 76:208
[19]	Toth P, Vigo D. The granular tabu search and its application to the vehicle-routing problem. Informs J Computing, 2003, 15(4):333
[20]	Vidal T, Crainic T G, Gendreau M, et al. Heuristics for multiattribute vehicle routing problems:a survey and synthesis. Eur J Operational Res, 2013, 231(1):1
[21]	Croes G A. A method for solving traveling-salesman problems. Operations Res, 1958, 6(6):791