An efficient iterated local search algorithm for the corridor allocation problem

• A multi-start iterated local search is proposed for corridor allocation problem. • Variable neighborhood descent (VND) is utilized within iterated local search. • Five neighborhood search mechanisms are employed in VND and perturbation. • Effectiveness of the algorithm is tested on several benchmark instances. • Best known results are improved for 34 of 82 benchmark instances. The corridor allocation problem (CAP) seeks the optimal arrangement of departments along the two sides of a corridor with respect to two key considerations; there should be no gap between two consecutive departments, and both of the rows should start at the same level of the corridor. In this study, a new and comprehensive multi-start iterated local search (ILS) algorithm is developed for CAP to search the solution space more effectively. The proposed algorithm utilizes a variable neighborhood descent (VND) for local search. The VND algorithm employs five neighborhood search mechanisms (swap, insert, inverse, cross, and block insert) and a tabu list to avoid cycling. The performance of the proposed ILS is evaluated on well-known instances of various sizes. Objective function values of 34 out of 82 benchmark instances are improved by the proposed algorithm. The computational results also show that the algorithm is capable of dealing with larger-sized problems with up to eighty departments.