Iterated local search

In this section, we describe the ILS procedure which is used to solve the proposed problem (Algorithm 1). The ILS is a metaheuristic algorithm that combines local search and perturbation procedures to search the feasible region more efficiently (Lourenço et al. 2003). In particular, this algorithm has been successfully applied to solve similar problems such as TOP (Vansteenwegen et al. 2009; Gunawan et al. 2015; Zachariadis and Kiranoudis 2011). For this reason, we use the ILS as one of the proposed methods for solving our problem. In this algorithm, a solution is created by following one of the proposed procedures in Sect. 3.1. The algorithm is composed of two loops. The inner loop is to improve the solution’s cost by applying local search procedures. Essentially, at each iteration, a local search procedure is selected by using the roulette wheel technique (see Sect. 3.3.1). Before entering the outer loop, as long as the solution can be improved, the LS algorithm is applied. The pseudocode of the LS procedure is depicted in Algorithm 2. In fact, we tested several orders of the moves and the current order is the best combination. In this combination, at first we utilize the swap procedures followed by the extraction–insertion procedures. The reason of using the deletion and insertion procedures is that they can further improve the solutions obtained by applying the two mentioned procedures (i.e., swap and extraction–insertion), and this is why we call them after each execution of the swap and extraction–insertion procedures. The whole procedure is iterated for “iter1” iterations. In addition, during the execution of the outer loop, the goal is to escape from local optima by utilizing the perturbation procedure. The outer loop is repeated “iter0” iterations. The corresponding values for iter0 and iter1 will be set in Sect. 4.4.

In each iteration of the ILS algorithm, one of the local search procedures is selected based on roulette wheel (see line 11 in Algorithm 1). In this method, in the first iteration the possibility of choosing a move is equal to 1n where n is the total number of moves. The possibility of selecting different procedures in later iterations is proportional to the effectiveness of the procedures in the previous iterations. Essentially, if the best solution is improved by applying a specific procedure, the possibility of selecting the corresponding procedure is increased in the subsequent iteration.

To escape from local optima, after every “iter1” iterations of the inner loop, the perturbation procedure is applied on the best found solution (see line 31 in Algorithm 1). In this procedure at first, ρ percent of the visited facilities are selected, randomly, and removed from their corresponding routes and added to the set F (set of unrouted facilities). Each time a facility is removed from the route, the assignment of customers is updated. In the second step, a facility is selected from F, randomly, and is added into its best feasible insertion position. The preliminary results show in case that we use the same set of customers in the structure of the perturbed solution, there will be a high probability to get stuck in a local optima solution by applying the local search procedure. In fact, by inserting the facilities randomly, we try to escape from local optima and expand the search space. After inserting the facility, the objective function and the subset F are updated. This step is iterated as long as we are not able to insert a new facility.