Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

The branch and cut method for the facility location problem with client’s preferences

Numerical study is provided of the methods for solving the facility location problem when the clients choose some suppliers by their own preferences. Various formulations of this problem as an integer linear programming problem are considered. The authors implement a cutting plane method based on the earlier proposed family of valid inequalities which arises from connection with the problem for a pair of matrices. The results of numerical experiment are presented for testing this method. An optimal solution is obtained by the two versions of the branch and cut method with the suggested cutting plane method. The simulated annealing method is proposed for obtaining the upper bounds of the optimal solution used in exact methods. Numerical experiment approves the efficiency of the implemented approach in comparison with the previously available methods.     

A simulated annealing technique for multi-objective simulation optimization

In this paper, we present a simulated annealing algorithm for solving multi-objective simulation optimization problems. The algorithm is based on the idea of simulated annealing with constant temperature, and uses a rule for accepting a candidate solution that depends on the individual estimated objective function values. The algorithm is shown to converge almost surely to an optimal solution. It is applied to a multi-objective inventory problem; the numerical results show that the algorithm converges rapidly.     

Heuristics for the Maximum Outerplanar Subgraph Problem

Determining the maximum outerplanar subgraph of a given graph is known to be an NP-complete problem. In the literature there are no earlier experiment on approximating the maximum outerplanar subgraph problem. In this paper we compare solution quality and running times of different heuristics for finding maximum outerplanar subgraphs. We compare a greedy heuristic against a triangular cactus heuristic and its greedy variation. We also use the solutions from the greedy heuristics as initial solutions for a simulated annealing algorithm.The main experimental result is that simulated annealing with initial solution taken from the greedy triangular cactus heuristic yields the best known approximations for the maximum outerplanar subgraph problem.Work funded by the Tampere Graduate School in Information Science and Engineering (TISE) and supported by the Academy of Finland (Project 51528).     

A Hybrid Method for Solving the Multi-objective Assignment Problem

Most of the well known methods for solving multi-objective combinatorial optimization problems deal with only two objectives. In this paper, we develop a metaheuristic method for solving multi-objective assignment problems with three or more objectives. This method is based on the dominance cost variant of the multi-objective simulated annealing (DCMOSA) and hybridizes neighborhood search techniques which consist of either a local search or a multi-objective branch and bound search (here the multi-objective branch and bound search is used as a local move to a fragment of a solution).     

Parallelization of population-based multi-objective meta-heuristics: An empirical study

In single-objective optimization it is possible to find a global optimum, while in the multi-objective case no optimal solution is clearly defined, but several that simultaneously optimize all the objectives. However, the majority of this kind of problems cannot be solved exactly as they have very large and highly complex search spaces. Recently, meta-heuristic approaches have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. Most of these meta-heuristics use a population of solutions, and hence the runtime increases when the population size grows. An interesting way to overcome this problem is to apply parallel processing. This paper analyzes the performance of several parallel paradigms in the context of population-based multi-objective meta-heuristics. In particular, we evaluate four alternative parallelizations of the Pareto simulated annealing algorithm, in terms of quality of the solutions, and speedup.     

Multi-objective performance improvements of general finite single-server queueing networks

Optimizing the performance of general finite single-server acyclic queueing networks is a challenging problem and has been the subject of many studies. The version of the optimization problem treated here considers the minimization of the buffer areas and the service rates simultaneously with the maximization of the throughput. These are conflicting objectives, and the most appropriate methodology appears to be a multi-objective methodology. In fact, algorithms have previously been proposed, and the aim here is to show that the use of a mixed methodology can occasionally improve solutions without a significant increase in the computational costs. This paper shows that improvements in throughput can be achieved through a solution of a type of stochastic knapsack problem, which consists of redistributing the buffer spaces between the lines while preserving the overall capacity using a simulated annealing algorithm; that is, one objective is improved (the throughput) without worsening the other (the overall allocated capacity). A set of computational experiments are presented to demonstrate the effectiveness of the proposed approach. Additionally, some of the insights presented here may help scientists and practitioners in finite single-server queueing network planning.     

A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling

In this study, a general framework is proposed that combines the distinctive features of three well-known approaches: the adaptive memory programming, the simulated annealing, and the tabu search methods. Four variants of a heuristic based on this framework are developed and presented. The performance of the proposed methods is evaluated and compared with a conventional simulated annealing approach using benchmark problems for job shop scheduling. The unique feature of the proposed framework is the use of two short-term memories. The first memory temporarily prevents further changes in the configuration of a provisional solution by maintaining the presence of good elements of such solutions. The purpose of the second memory is to keep track of good solutions found during an iteration, so that the best of these can be used as the starting point in a subsequent iteration. Our computational results for the job shop scheduling problem clearly indicate that the proposed methods significantly outperform the conventional simulated annealing.     

A hybrid metaheuristic algorithm for dynamic rail car fleet sizing problem

The aim of this paper is to present a model and a solution method for rail freight car fleet sizing problem. The mathematical model is dynamic and multi-periodic and car demands and travel times are assumed deterministic, and the proposed solution method is hybridization of genetic algorithms and simulated annealing algorithms. Experimental analysis is conducted using several test problems. The results of the proposed algorithm and CPLEX software are compared. The results show high efficiency and effectiveness of the proposed algorithm. The solution method is applied to solve fleet sizing problem in the Iran Railways as a case study.