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

LI Xiang; LI Su-jian; LI Hong

doi:10.13374/j.issn2095-9389.2017.06.019

Volume 39 Issue 6

Jun. 2017

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Engineering > 2017 > 39(6): 953-961

LI Xiang, LI Su-jian, LI Hong. Simulated annealing with large-neighborhood search for two-echelon location routing problem[J]. Chinese Journal of Engineering, 2017, 39(6): 953-961. doi: 10.13374/j.issn2095-9389.2017.06.019

Citation:

LI Xiang, LI Su-jian, LI Hong. Simulated annealing with large-neighborhood search for two-echelon location routing problem[J]. Chinese Journal of Engineering, 2017, 39(6): 953-961. doi: 10.13374/j.issn2095-9389.2017.06.019

Citation:

PDF( 1692 KB)

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

doi: 10.13374/j.issn2095-9389.2017.06.019

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

Received Date: 2016-11-02

Abstract

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

FullText(HTML)

References(16)

References

[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