Modeling And Scatter Search Optimization Research Based On The Extended Corridor Allocation Problem

With the rapid development of the global economy,shortening the production cycle and reducing the production cost are the most important factors for the enterprises to win the market.The reasonable facility layout can not only save 10%to 30%cost,but also reduce the material transmission distance and the residence time of WIP.One special class of the facility layout problem is the corridor allocation problem(CAP)which not only has numerous applications in service field,but also potentially has important applications in industry field.Therefore,the research on the CAP has important theoretical value and practical significance.The CAP seeks an arrangement of facilities along a central corridor for the purpose of minimizing the total flow cost among facilities.The CAP is a typical combinatorial optimization problem,which has the NP-hard property and the difficulty of problem solving.Based on this,an improved scatter search(ISS)algorithm is proposed.In the algorithm a kind of two-stage hybrid improvement strategy is proposed,that is,firstly the speeding-up insertion method is applied to the local optimization of the solutions,then simulated annealing operation is introduced to further optimize the optimal solutions in the current reference set,so as to increase the likelihood of obtaining the global optimum.Instead of the traditional single reference set,the 2-tier reference set involving high quality and diverse solutions is designed to expand the search scope and avoid local optimum.In addition,the dynamic reference set update method is adopted and the relatively poor solutions are replaced timely,which accelerates the algorithm convergence speed.Meanwhile,the reduplicated solution in the improved subset generation method is not allowed which helps to increase the efficiency.Finally,the proposed approach is evaluated on test instances of various sizes.Computational results demonstrate that the ISS algorithm shows better performance in solving quality and stability by comparing with the simulated annealing algorithm and the scatter search algorithm,and surpasses the other 6 methods.In the existing research of the CAP,the corridor width and the total flow entrance are not taken into consideration.The paper takes into account a fact that these two factors will have an impact on the total flow cost.Thus two mixed integer programming models of the extended CAP are constructed and the GUROBI software is used to demonstrate their validity.Furthermore,the ISS algorithm is applied to solve the problems,not only the optimal solutions of the small scale problem are obtained,but also the near optimal solution of the large scale problems are quickly obtained in a reasonable time.Comparative analysis shows that,if the effect of corridor width is considered in the early stage of layout design,then the total flow cost among facilities can save up to 27.59%,if the effect of corridor width and total flow entrance are considered simultaneously,then 6.08%total flow cost can be reduced at least.Moreover,in order to facilitate the application of the proposed approach,the influences of different seed solutions,crossover operators and insertion methods to the solving performance of the algorithm are analyzed,and the results demonstrate the superiority of the selected mechanisms in the paper.Finally,the proposed algorithm is applied to the optimization of workshop layout and several suggestions are put forward.