Two effective simulated annealing algorithms for the Location-Routing Problem

Two heuristics based on the simulated annealing method are presented for solving the capacitated version of the Location-Routing Problem. The first heuristic has four components, which are: generate an initial solution from using a greedy procedure based on allocating customers to the closest facilities; apply four neighborhood operators based on swap and insertion moves; perturb the best solution by solving 0-1 knapsack problems and, then, improve the resultant solution with the Lin-Kernighan heuristic; and, diversify the solution into closing and opening different facilities. The second heuristic is a simplified version of the first one in which the third component is disregarded because it may be time-consuming. Computational experiments conducted on three sets of benchmark instances show that the two heuristics are very competitive and have outperformed other methods published in the literature. They presented an overall average gap of 0.17% and 0.13%, respectively, and improved previous solutions within a reasonable computing time for nine large instances.