Simulated annealing for the quadratic assignment problem: A further study

Concentrating on the generating mode of random permutation solutions and the corresponding theory and evaluation problems, this paper carries out a further study on the Simulated Annealing (SA) algorithm for the Quadratic Assignment Problem (QAP) which has many applications in practice. The paper introduces and analyzes the six different kinds of interchanges of facility locations for generating random permutations. The theoretical analyses prove that the relevant generation probabilities satisfy the asymptotical convergence conditions. The results of experimental evaluations reveal the relations between the random sampling modes, and show that adopting the proper generating mode the SA algorithm can produce better quality solutions of the QAP. At the same time, the conclusions reached in the paper are available for many extensive heuristics to solve combinatorial optimization problems.     

The dynamic space allocation problem: Applying hybrid GRASP and Tabu search metaheuristics

This work is devoted to the Dynamic Space Allocation Problem, where project duration is divided into a number of consecutive periods, each of them associated with a number of activities. The resources required by the activities have to be available in the corresponding workspaces and those sitting idle during a period have to be stored. This problem contains the Quadratic Assignment Problem (QAP) as a particular case, which puts it in the NP-hard class. In this context, the difficulty of identifying optimal solutions, even for instances of medium size, justifies the use of heuristic techniques. This work proposes a construction and a hybrid algorithm (HGT) based on the GRASP and Tabu search metaheuristics. Comparisons are presented for values obtained by HGT, pure GRASP versions, Tabu search and literature results. Computational results show the proposed methods to be competitive in relation to instances in the literature and to existing techniques.     

Self Controlling Tabu Search algorithm for the Quadratic Assignment Problem

This paper addresses the application of the principles of feedback and self-controlling software to the tabu search algorithm. We introduce two new reaction strategies for the tabu search algorithm. The first strategy treats the tabu search algorithm as a target system to be controlled and uses a control-theoretic approach to adjust the algorithm parameters that affect search intensification. The second strategy is a flexible diversification strategy which can adjust the algorithm’s parameters based on the search history. These two strategies, combined with tabu search, form the Self Controlling Tabu Search (SC-Tabu) algorithm. The algorithm is implemented and tested on the Quadratic Assignment Problem (QAP). The results show that the self-controlling features of the algorithm make it possible to achieve good performance on different types of QAP instances.     

A Tabu search algorithm for the network pricing problem

In this paper, we propose an efficient Tabu Search procedure for solving the NP-hard network pricing problem. By exploiting the problem's features, the algorithm allows the near-optimal solution of problem instances that are out of reach of exact combinatorial methods.     

求解二次指派问题的最优迭代最大最小蚂蚁算法

为提高二次指派问题的求解质量,设计了一个有效的最大最小蚂蚁求解算法。首先,运用最优迭代思想,让每只蚂蚁从当前最优路径中随机地选择位置及其对应的任务作为下一轮迭代的初始值,增强每轮搜索的有效性;其次,采用加入新任务后目标值的增量作为启发式因子来引导状态转移,增加每步搜索的目的性;然后,应用多精英策略来进行信息素更新,增加解的多样性;并设计有效的双重变异技术来提高解的质量,提高算法的收敛速度;最后,应用QAPLIB数据集进行了大量实验,结果表明:该算法在二次指派问题的求解质量和稳定性上显著优于其他算法。     

Improving simulated annealing with variable neighborhood search to solve the resource-constrained scheduling problem

The purpose of this paper is to improve the simulated annealing method with a variable neighborhood search to solve the resource-constrained scheduling problem. We also compare numerically this method with other neighborhood search (local search) techniques: threshold accepting methods and tabu search. Furthermore, we combine these techniques with multistart diversification strategies and with the variable neighborhood search technique. A thorough numerical study is completed to set the parameters of the different methods and to compare the quality of the solutions that they generate. The numerical results indicate that the simulated annealing method improved with a variable neighborhood search technique is indeed the best solution method. This research was supported by NSERC grant (OGP 0008312) the first author received a FCAR fellowship during her M.Sc. studies.     

A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problem

A two-stage memory architecture is maintained within the framework of great deluge algorithm for the solution of single-objective quadratic assignment problem. Search operators exploiting the accumulated experience in memory are also implemented to direct the search towards more promising regions of the solution space. The level-based acceptance criterion of the great deluge algorithm is applied for each best solution extracted in a particular iteration. The use of short- and long-term memory-based search supported by effective move operators resulted in a powerful combinatorial optimization algorithm. A successful variant of tabu search is employed as the local search method that is only applied over a few randomly selected memory elements when the second stage memory is updated. The success of the presented approach is illustrated using sets of well-known benchmark problems and evaluated in comparison to well-known combinatorial optimization algorithms. Experimental evaluations clearly demonstrate that the presented approach is a competitive and powerful alternative for solving quadratic assignment problems.     

Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem

In this paper we perform extensive computational experiments solving quadratic assignment problems using various variants of a hybrid genetic algorithm. We introduce a new tabu search (simple tabu). We compared the modified robust tabu and the simple tabu as improvement algorithms in a hybrid genetic algorithm with other tabu searches (concentric tabu, ring moves, all moves, robust tabu) with superior results. We also tested several modifications of the hybrid genetic algorithm and all of them produced good results.     

强化最优和最差狼的郊狼优化算法及其二次指派问题应用

针对郊狼优化算法（COA）优化性能不足的问题，提出一种强化最优和最差狼的COA（BWCOA）方法。首先，对于组内最差郊狼的成长，在最优郊狼引导的基础上引入全局最优郊狼引导操作，以提高最差郊狼的社会适应能力（局部搜索能力）；然后，在组内最优郊狼的成长过程中嵌入一种随机扰动操作，即以郊狼之间的随机扰动促进成长，发挥组内每个郊狼的能动性，提高种群的多样性进而强化全局搜索能力；最后，组内其他郊狼的成长方式保持不变。将BWCOA运用到复杂函数优化和以医院科室布局为例的二次指派问题（QAP）中。在CEC-2014复杂函数上的实验结果表明，与COA以及其他最先进的算法相比，BWCOA获得1.63的平均均值排名和Friedman检验中1.68的秩均值，均排名第一。另外，在6组QAP上的实验结果表明，BWCOA获得了5次均值最优的结果。实验结果均表明BWCOA具有更强的竞争性。     

求解两物种小系统发育问题的模拟退火算法

针对复制-丢失比对问题模型,提出求解复制-丢失演化模型下两物种小系统发育问题(SPP)的模拟退火算法(SA2SP)。SA2SP引入比对算法用于构造问题初始解;引入标记算法用于构建问题解的目标函数,以得到问题解的进化代价;同时还引入3种智能邻域函数,利用基因序列的进化特性,指导性地产生邻域解。利用4种真实菌属的核糖体核糖核酸(rRNA)和转运核糖核酸(tRNA)基因数据对算法的性能进行测试,实验结果表明, SA2SP能够获得较伪布尔线性规划(PBLP)求解算法更小的进化代价,是求解复制-丢失演化模型下两物种小系统发育问题的一种有效方法。     

A simulated annealing approach for the multi-periodic rail-car fleet sizing problem

In this paper, we proposed a new formulation and a solution procedure for optimizing the fleet size and freight car allocation wherein car demands and travel times are assumed to be deterministic and unmet demands are backordered. We assume that unmet demands become zero at the end of the planning horizon, i.e., the car demands are totally satisfied through the horizon. There are important interactions between decisions on sizing a rail car fleet and utilizing that fleet. Consequently, the optimum use of rail-cars for demands response in the length of the time periods is one of the main advantages of the proposed model. The model also provides rail network information such as yard capacity, unmet demands, and number of loaded and empty rail-car at any given time and location. Computational tests showed that small-size instances can be solved by the exact approach in a fair amount of CPU time, but it is not feasible for medium and large-size instances. To tackle this problem, a Simulated Annealing (SA) algorithm is proposed to solve the model. The algorithm works efficiently on a neighborhood search within solution space, acceptance probability, and inferior solutions to escape from trap (i.e., local optimal solution). Numerical examples are solved to check for the efficiency and validity of the SA algorithm.     

Design of robust layout for Dynamic Plant Layout Problems

In this paper, a design for robust facility layout is proposed under the dynamic demand environment. The general strategy for a multi period layout planning problem is adaptive approach. This approach for Dynamic Plant Layout Problem (DPLP) assumes that a layout will accommodate changes from time to time with low rearrangement and production interruption costs, and that the machines can be easily relocated. On the other hand the robust layout approach, assumes that rearrangement and production interruption costs are too high and hence, tries to minimize the total material handling costs in all periods using a single layout. Robust approach suggests a single layout for multiple scenarios as well as for multiple periods. As a solution procedure for the proposed model, a Simulated Annealing (SA) algorithm is suggested, which perform well for the problems from literature and QAPLIB website. The application of suggested model for robust layout to cellular layouts has given better results compared to the robust cellular layout model of literature. For the standard DPLP of the literature, the solution values of the suggested model are very near to the results of adaptive approach. The Total Penalty Cost (TPC) is used to test the suitability of the suggested layout to be a robust layout for the given data set. TPC values indicate that the suggested layout is suitable as robust layout for the given data sets.     

具有捕食策略的混合随机优化算法及其多极值函数优化

SAGACIA是一种混合随机优化算法,该算法虽已吸收了模拟退火算法、遗传算法和趋化性算法的优点,但搜索过程中仍存在收敛速度慢以及采用固定步长影响搜索精度的缺点,而捕食搜索策略通过限制的调节能较快锁定最优区域,从而提高收敛速度。结合两者的优缺点,提出一种具有捕食搜索策略的自适应调整步长SAGACIA算法,改进后的算法通过捕食搜索策略平衡了算法的局域搜索和全局搜索,提高了收敛速度;邻域搜索采用自适应步长,避免了最优解附近的震荡,提高了搜索精度。实验仿真结果表明,改进后的SAGACIA算法具有较快的收敛速度和较高的寻优精度,证明了算法改进的有效性和可行性。     

基于遗传模拟退火算法的立体仓库储位优化

针对自动化立体仓库储位分配问题,结合仓库运作特点和安全性要求,构建了自动化立体仓库储位优化问题的多目标模型,并提出了求解模型的基于Sigmoid曲线的改进自适应遗传模拟退火算法（SAGA）。首先,以降低货品出入库时间、同组货品距离和货架重心为目标建立储位优化模型;然后,为了克服遗传算法（GA）局部搜索能力差和易陷入局部最优的缺点,引入基于Sigmoid曲线的自适应交叉变异操作和逆转操作,同时完成与SAGA的融合;最后,对改进遗传SAGA进行算法优化性、稳定性和收敛性测试。仿真实验表明,相比模拟退火（SA）算法的求解结果,该算法对货品出入库时间的优化度提高了37.7949个百分点、对同组货品距离提高了58.4630个百分点、对货架重心优化度提高了25.9275个百分点,并且该算法具有更好的稳定性和收敛性。由此验证了改进遗传SAGA求解问题的有效性,该算法可为自动化立体仓库储位优化提供决策方法。     

A distributed implementation of simulated annealing for the travelling salesman problem

This paper describes and analyses a novel distributed implementation of the simulated annealing algorithm to find a good solution to the travelling salesman problem. The implementation runs on a linear chain of processors driven by a host processor, which plays only a supervisory role, so that the bulk of processing takes place on the chain and the efficiency of the algorithm remains high as the number of processors is increased.     

Solving the truck and trailer routing problem based on a simulated annealing heuristic

In this study, we consider the application of a simulated annealing (SA) heuristic to the truck and trailer routing problem (TTRP), a variant of the vehicle routing problem (VRP). In the TTRP, some customers can be serviced by either a complete vehicle (that is, a truck pulling a trailer) or a single truck, while others can only be serviced by a single truck for various reasons. SA has seen widespread applications to various combinatorial optimization problems, including the VRP. However, to our best knowledge, it has not been applied to the TTRP. So far, all the best known results for benchmark TTRP instances were obtained using tabu search (TS). We applied SA to the TTRP and obtained 17 best solutions to the 21 benchmark TTRP benchmark problems, including 11 new best solutions. Moreover, the computational time required by the proposed SA heuristic is less than those reported in prior studies. The results suggest that SA is competitive with TS on solving the TTRP.     

A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

The assembly flowshop scheduling problem has been addressed recently in the literature. There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search, and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems, i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%.     

Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem

We consider the university course timetabling problem, which is one of the most studied problems in educational timetabling. In particular, we focus our attention on the formulation known as the curriculum-based course timetabling problem (CB-CTT), which has been tackled by many researchers and for which there are many available benchmarks.The contribution of this paper is twofold. First, we propose an effective and robust single-stage simulated annealing method for solving the problem. Second, we design and apply an extensive and statistically-principled methodology for the parameter tuning procedure. The outcome of this analysis is a methodology for modeling the relationship between search method parameters and instance features that allows us to set the parameters for unseen instances on the basis of a simple inspection of the instance itself. Using this methodology, our algorithm, despite its apparent simplicity, has been able to achieve high quality results on a set of popular benchmarks.A final contribution of the paper is a novel set of real-world instances, which could be used as a benchmark for future comparison.     

Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem

The post-enrolment course timetabling (PE-CTT) is one of the most studied timetabling problems, for which many instances and results are available. In this work we design a metaheuristic approach based on simulated annealing to solve the PE-CTT. We consider all the different variants of the problem that have been proposed in the literature and we perform a comprehensive experimental analysis on all the available public instances. The outcome is that our solver, properly engineered and tuned, performs very well on all cases, providing the new best known results on many instances and state-of-the-art values for the others.