Ants can solve the team orienteering problem

The team orienteering problem (TOP) involves finding a set of paths from the starting point to the ending point such that the total collected reward received from visiting a subset of locations is maximized and the length of each path is restricted by a pre-specified limit. In this paper, an ant colony optimization (ACO) approach is proposed for the team orienteering problem. Four methods, i.e., the sequential, deterministic-concurrent and random-concurrent and simultaneous methods, are proposed to construct candidate solutions in the framework of ACO. We compare these methods according to the results obtained on well-known problems from the literature. Finally, we compare the algorithm with several existing algorithms. The results show that our algorithm is promising.     

Solving power system optimization problems using simulated annealing

Based on the simulated annealing technique and the constrained form of power system optimization problems, this paper develops a simulated-annealing-based optimization algorithm for power-system optimization problems. The algorithm is general, and it possesses the ability to determine the global optimum solution. The developed algorithm is demonstrated by its application to the problem of the economic dispatch of electric power.     

An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem

In this paper, an improved two-stage simulated annealing algorithm is presented for the minimum linear arrangement problem for graphs. This algorithm integrates several distinguished features including an efficient heuristic to generate good quality initial solutions, a highly discriminating evaluation function, a special neighborhood function and an effective cooling schedule. The algorithm is evaluated on a set of 30 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of 17 previous best results.     

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.     

Iterated local search for the team orienteering problem with time windows

A personalised electronic tourist guide assists tourists in planning and enjoying their trip. The planning problem that needs to be solved, in real-time, can be modelled as a team orienteering problem with time windows (TOPTW). In the TOPTW, a set of locations is given, each with a score, a service time and a time window. The goal is to maximise the sum of the collected scores by a fixed number of routes. The routes allow to visit locations at the right time and they are limited in length. The main contribution of this paper is a simple, fast and effective iterated local search meta-heuristic to solve the TOPTW. An insert step is combined with a shake step to escape from local optima. The specific shake step implementation and the fast evaluation of possible improvements, produces a heuristic that performs very well on a large and diverse set of instances. The average gap between the obtained results and the best-known solutions is only 1.8% and the average computation time is decreased with a factor of several hundreds. For 31 instances, new best solutions are computed.     

Solving dynamic double row layout problem via combining simulated annealing and mathematical programming

Double row layout problem (DRLP) is to allocate facilities on two rows separated by a straight aisle. Aiming at the dynamic environment of product processing in practice, we propose a dynamic double-row layout problem (DDRLP) where material flows change over time in different processing periods. A mixed-integer programming model is established for this problem. A methodology combining an improved simulated annealing (ISA) with mathematical programming (MP) is proposed to resolve it. Firstly, a mixed coding scheme is designed to represent both of sequence of facilities and their exact locations. Secondly, an improved simulated annealing algorithm is suggested to produce a solution to DDRLP. Finally, MP is used to improve this solution by determining the optimal exact location for each facility. Experiments show that this methodology is able to obtain the optimal solutions for small size problems and outperforms an exact approach (CPLEX) for problems of realistic size.     

An augmented large neighborhood search method for solving the team orienteering problem

In the Team Orienteering Problem (TOP), a team of vehicles attempts to collect rewards at a given number of stops within a specified time frame. Once a vehicle visits a stop and collects its reward, no other vehicles can collect the reward again. Typically, a team cannot visit all stops and therefore has to identify the “best” set of stops to visit in order to maximize total rewards. We propose a large neighborhood search method with three improvement algorithms: a local search improvement, a shift and insertion improvement, and replacement improvement. Our proposed approach can find the best known solutions for 386 of the 387 benchmark instances, for the one instance which our solution is not the current best it is only varies by one from the best. Our approach outperforms all the previous approaches in terms of solution quality and computation time.     

Solving a part classification problem using simulated annealing-like hybrid algorithm

Part classification and coding is still considered as laborious and time-consuming exercise. Keeping in view, the crucial role, which it plays, in developing automated CAPP systems, the attempts have been made in this article to automate a few elements of this exercise using a shape analysis model. In this study, a 24-vector directional template is contemplated to represent the feature elements of the parts (candidate and prototype). Various transformation processes such as deformation, straightening, bypassing, insertion and deletion are embedded in the proposed simulated annealing (SA)-like hybrid algorithm to match the candidate part with their prototype. For a candidate part, searching its matching prototype from the information data is computationally expensive and requires large search space. However, the proposed SA-like hybrid algorithm for solving the part classification problem considerably minimizes the search space and ensures early convergence of the solution.The application of the proposed approach is illustrated by an example part. The proposed approach is applied for the classification of 100 candidate parts and their prototypes to demonstrate the effectiveness of the algorithm.     

Study on continuous network design problem using simulated annealing and genetic algorithm

In general, a continuous network design problem (CNDP) is formulated as a bi-level program. The objective function at the upper level is defined as the total travel time on the network, plus total investment costs of link capacity expansions. The lower level problem is formulated as a certain traffic assignment model. It is well known that such bi-level program is non-convex and non-differentiable and algorithms for finding global optimal solutions are preferable to be used in solving it. Simulated annealing (SA) and genetic algorithm (GA) are two global methods and can then be used to determine the optimal solution of CNDP. Since application of SA and GA on continuous network design on real transportation network requires solving traffic assignment model many times at each iteration of the algorithm, computation time needed is tremendous. It is important to compare the efficacy of the two methods and choose the more efficient one as reference method in practice. In this paper, the continuous network design problem has been studied using SA and GA on a simulated network. The lower level program is formulated as user equilibrium traffic assignment model and Frank–Wolf method is used to solve it. It is found that when demand is large, SA is more efficient than GA in solving CNDP, and much more computational effort is needed for GA to achieve the same optimal solution as SA. However, when demand is light, GA can reach a more optimal solution at the expense of more computation time. It is also found that increasing the iteration number at each temperature in SA does not necessarily improve solution. The finding in this example is different from [Karoonsoontawong, A., & Waller, S. T. (2006). Dynamic continuous network design problem – Linear bilevel programming and metaheuristic approaches. Network Modeling 2006 Transportation Research Record (1964) (pp. 104–117)]. The reason might be the bi-level model in this example is nonlinear while the bi-level model in their study is linear.     

Simulation optimization using simulated annealing

The purpose of this study is to investigate the feasibility of using a simulated annealing algorithm in conjunction with a simulation model to find the optimal parameter levels at which to operate a system. In particular, we discuss an effort to use simulated annealing to find a combination of input parameter values for a model which optimizes a nonconvex, nonconcave objective function of the input parameters. In the absence on an optimal annealing schedule, we demonstrate that multiple runs of the simulated annealing algorithm can result in an optimal or near-optimal solution to the problem.     

Solving a single-machine scheduling problem with maintenance,job deterioration and learning effect by simulated annealing

This paper presents a new nonlinear multi-objective mathematical model for a single-machine scheduling problem with three objectives: (1) minimizing the sum of the weighted jobs completion, (2) minimizing the sum of the weighted delay times, and (3) maximizing the sum of the job values in makespan. In addition, a number of constraints are incorporated in this presented model, such as repairing and maintenance periods, deterioration of jobs, and learning effect of the work process. Since this type of scheduling problem belongs to a class of NP-hard ones, its solution by common software packages is almost impossible, or at best very time consuming. Thus, a meta-heuristic algorithm based on simulated annealing (SA) is proposed to solve such a hard problem. At a final stage, the related results obtained by the proposed SA are compared with those results reported by the Lingo 8 software in order to demonstrate the efficiency and capability of our proposed SA algorithm.     

A simulated annealing approach to the traveling tournament problem

Automating the scheduling of sport leagues has received considerable attention in recent years, as these applications involve significant revenues and generate challenging combinatorial optimization problems. This paper considers the traveling tournament problem (TTP) which abstracts the salient features of major league baseball (MLB) in the United States. It proposes a simulated annealing algorithm (TTSA) for the TTP that explores both feasible and infeasible schedules, uses a large neighborhood with complex moves, and includes advanced techniques such as strategic oscillation and reheats to balance the exploration of the feasible and infeasible regions and to escape local minima at very low temperatures. TTSA matches the best-known solutions on the small instances of the TTP and produces significant improvements over previous approaches on the larger instances. Moreover, TTSA is shown to be robust, because its worst solution quality over 50 runs is always smaller or equal to the best-known solutions. A Preliminary version of this paper was presented at the CP'AI'OR'03 Workshop.     

Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques

In this paper, we present a new method, called the genetic simulated annealing ant colony system with particle swarm optimization techniques, for solving the traveling salesman problem. We also make experiments using the 25 data sets obtained from the TSPLIB (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) and compare the experimental results of the proposed method with the methods of Angeniol, Vaubois, and Texier (1988), Somhom, Modares, and Enkawa (1997), Masutti and Castro (2009) and Pasti and Castro (2006). The experimental results show that both the average solution and the percentage deviation of the average solution to the best known solution of the proposed method are better than the methods of Angeniol et al., 1988, Angeniol et al., 1988, Somhom et al., 1997, Masutti and Castro, 2009, Pasti and Castro, 2006.     

Parallel simulated annealing using speculative computation

A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log₂P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic     

求解VRPSDP问题的改进模拟退火遗传算法

配送和回收一体化的车辆路径问题（VRPSDP）是一种非常复杂的NP难题。针对这一问题,设计了一种改进的模拟退火遗传算法ISAGA,采用非零自然数编码机制和弱可行解到强可行解的解码机制,将3PM交叉算子和退火选择相结合,形成贪心3PM交叉算子,引进insert 、swap和2-opt分别对解进行迭代优化,并将模拟退火算法和遗传算法巧妙地结合,使得遗传算法在前期发挥着全局搜索的强大功能;后期用模拟退火算法来处理遗传算法前期的全局较优解,充分利用模拟退火算法后期局部搜索的强大功能。经过国际公认的测试算例验证,ISAGA算法在Min算例、Salhi和Nagy算例中均找到了比现有算法已知最好解更优的解。     

Fuzzy model tuning using simulated annealing

This paper presents the use of simulated annealing metaheuristic for tuning Mamdani type fuzzy models. Structure of the Mamdani fuzzy model is learned from input–output data pairs using Wang and Mendel’s method and fuzzy c-means clustering algorithm. Then, parameters of the fuzzy system are tuned through simulated annealing. In this paper, we perform experiments to examine effects of (a) initial solution generated by Wang and Mendel’s method and fuzzy c-means clustering method, (b) membership function update procedure, (c) probability parameter for the calculation of the initial temperature, (d) temperature update coefficient used for cooling schedule, and (e) randomness level in the disturbance mechanism used in simulated annealing algorithm on the tuning of Mamdani type fuzzy models. Experiments are performed with Mackey–Glass chaotic time series. The results indicate that Wang and Mendel’s method provides better starting configuration for simulated annealing compared to fuzzy c-means clustering method, and for the membership function update parameter, MFChangeRate ∈  (0, 1], and the probability parameter for the calculation of the initial temperature, P₀ ∈  (0, 1), values close to zero produced better results.     

Flow-shop sequencing using hybrid simulated annealing

Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.     

A simple simulated annealing algorithm for the maximum clique problem

Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.     

A simulated annealing approach to the multiconstraint zero-one knapsack problem

The multiconstraint 0–1 knapsack problem encounters when deciding how to use a knapsack with multiple resource constraints. The problem is known to be NP-hard, thus a “good” algorithm for its optimal solution is very unlikely to exist. We show how the concept of simulated annealing may be used for solving this problem approximately. 57 data sets from literature demonstrate, that the algorithm converges very rapidly towards the optimum solution.     

A simulated annealing heuristic for the capacitated location routing problem

The location routing problem (LRP) is a relatively new research direction within location analysis that takes into account vehicle routing aspects. The goal of LRP is to solve a facility location problem and a vehicle routing problem simultaneously. We propose a simulated annealing (SA) based heuristic for solving the LRP. The proposed SALRP heuristic is tested on three sets of well-known benchmark instances and the results are compared with other heuristics in the literature. The computational study indicates that the proposed SALRP heuristic is competitive with other well-known algorithms.