基于模拟退火算法的城市物流多目标配送车辆路径优化研究

基于传统模拟退火算法,通过引入记忆函数、结合GIS手段,运用SPSS聚类分析来确定初始化状态种群、多种群并行机制和新状态的产生.依据种群规模采用不同产生算法来改进算法,并将改进算法应用于城市物流中确定的多目标车辆路径优化问题,验证了算法的可行性与实用价值.此外,改进算法分别与传统模拟退火算法和GIS图解法相比较,优化效率和准确率都得到了很大的提高.     

Derivative-Free Filter Simulated Annealing Method for Constrained Continuous Global Optimization

In this paper, a simulated-annealing-based method called Filter Simulated Annealing (FSA) method is proposed to deal with the constrained global optimization problem. The considered problem is reformulated so as to take the form of optimizing two functions, the objective function and the constraint violation function. Then, the FSA method is applied to solve the reformulated problem. The FSA method invokes a multi-start diversification scheme in order to achieve an efficient exploration process. To deal with the considered problem, a filter-set-based procedure is built in the FSA structure. Finally, an intensification scheme is applied as a final stage of the proposed method in order to overcome the slow convergence of SA-based methods. The computational results obtained by the FSA method are promising and show a superior performance of the proposed method, which is a point-to-point method, against population-based methods.     

An Application of a Multi-Objective Tabu Search Algorithm to a Bicriteria Flowshop Problem

This paper proposes a new tabu search algorithm for multi-objective combinatorial problems with the goal of obtaining a good approximation of the Pareto-optimal or efficient solutions. The algorithm works with several paths of solutions in parallel, each with its own tabu list, and the Pareto dominance concept is used to select solutions from the neighborhoods. In this way we obtain at each step a set of local nondominated points. The dispersion of points is achieved by a clustering procedure that groups together close points of this set and then selects the centroids of the clusters as search directions. A nice feature of this multi-objective algorithm is that it introduces only one additional parameter, namely, the number of paths. The algorithm is applied to the permutation flowshop scheduling problem in order to minimize the criteria of makespan and maximum tardiness. For instances involving two machines, the performance of the algorithm is tested against a Branch-and-Bound algorithm proposed in the literature, and for more than two machines it is compared with that of a tabu search algorithm and a genetic local search algorithm, both from the literature. Computational results show that the heuristic yields a better approximation than these algorithms.     

Parallel Simulated Annealing Algorithms in Global Optimization

Global optimization involves the difficult task of the identification of global extremities of mathematical functions. Such problems are often encountered in practice in various fields, e.g., molecular biology, physics, industrial chemistry. In this work, we develop five different parallel Simulated Annealing (SA) algorithms and compare them on an extensive test bed used previously for the assessment of various solution approaches in global optimization. The parallel SA algorithms consist of various categories: the asynchronous approach where no information is exchanged among parallel runs and the synchronous approaches where solutions are exchanged using genetic operators, or where solutions are transmitted only occasionally, or where highly coupled synchronization is achieved at every iteration. One of these approaches, which occasionally applies partial information exchanges (controlled in terms of solution quality), provides particularly notable results for functions with vast search spaces of up to 400 dimensions. Previous attempts with other approaches, such as sequential SA, adaptive partitioning algorithms and clustering algorithms, to identify the global optima of these functions have failed without exception.     

Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling

In this paper the resource-constrained project scheduling problem with multiple execution modes for each activity and the makespan as the minimization criterion is considered. A simulated annealing approach to solve this problem is presented. The feasible solution representation is based on a precedence feasible list of activities and a mode assignment. A comprehensive computational experiment is described, performed on a set of standard test problems constructed by the ProGen project generator. The results are analyzed and discussed and some final remarks are included.     

不确定条件下工程项目的多目标模糊均衡优化

在工程项目多目标优化问题研究基础上,研究不确定环境下工程项目多目标均衡优化问题.利用模糊数表示费用变化率和质量变化率,考虑模糊集的不同可能性水平,建立工程项目多目标模糊均衡优化模型,给出模型的求解方法和步骤,得到不同可能性水平下多目标优化问题的最优折衷解变化范围.优化方法使决策者能够根据决策风险的大小进行最优目标值的确定.     

A Hybrid Meta-Heuristic for Multi-Objective Optimization: MOSATS

Real optimization problems often involve not one, but multiple objectives, usually in conflict. In single-objective optimization there exists a global optimum, while in the multi-objective case no optimal solution is clearly defined but rather a set of solutions, called the Pareto-optimal front. Thus, the goal of multi-objective strategies is to generate a set of non-dominated solutions as an approximation to this front. However, the majority of problems of this kind cannot be solved exactly because they have very large and highly complex search spaces. In recent years, meta-heuristics have become important tools for solving multi-objective problems encountered in industry as well as in the theoretical field. This paper presents a novel approach based on hybridizing Simulated Annealing and Tabu Search. Experiments on the Graph Partitioning Problem show that this new method is a better tool for approximating the efficient set than other strategies also based on these meta-heuristics.     

Simulated Annealing Algorithms for Continuous Global Optimization: Convergence Conditions

In this paper, simulated annealing algorithms for continuous global optimization are considered. After a review of recent convergence results from the literature, a class of algorithms is presented for which strong convergence results can be proved without introducing assumptions which are too restrictive. The main idea of the paper is that of relating both the temperature value and the support dimension of the next candidate point, so that they are small at points with function value close to the current record and bounded away from zero otherwise.     

An Interactive Method for 0-1 Multiobjective Problems Using Simulated Annealing and Tabu Search

This paper presents an interactive method for solving general 0-1 multiobjective linear programs using Simulated Annealing and Tabu Search. The interactive protocol with the decision maker is based on the specification of reservation levels for the objective function values. These reservation levels narrow the scope of the search in each interaction in order to identify regions of major interest to the decision maker. Metaheuristic approaches are used to generate potentially nondominated solutions in the computational phases. Generic versions of Simulated Annealing and Tabu Search for 0-1 single objective linear problems were developed which include a general routine for repairing unfeasible solutions. This routine improves significantly the results of single objective problems and, consequently, the quality of the potentially nondominated solutions generated for the multiobjective problems. Computational results and examples are presented.     

A Distributed Evolutionary Simulated Annealing Algorithm for Combinatorial Optimisation Problems

In this paper, the Evolutionary Simulated Annealing (ESA) algorithm, its distributed implementation (dESA) and its application to two combinatorial problems are presented. ESA consists of a population, a simulated annealing operator, instead of the more usual reproduction operators used in evolutionary algorithms, and a selection operator. The implementation is based on a multi island (agent) system running on the Distributed Resource Machine (DRM), which is a novel, scalable, distributed virtual machine based on Java technology. As WAN/LAN systems are the most common multi-machine systems, dESA implementation is based on them rather than any other parallel machine. The problems tackled are well-known combinatorial optimisation problems, namely, the classical job-shop scheduling problem and the uncapacitated facility location problem. They are difficult benchmarks, widely used to measure the efficiency of metaheuristics with respect to both the quality of the solutions and the central processing unit (CPU) time spent. Both applications show that dESA solves problems finding either the optimum or a very near optimum solution within a reasonable time outperforming the recent reported approaches for each one allowing the faster solution of existing problems and the solution of larger problems.     

Metaheuristics in Combinatorial Optimization

The emergence of metaheuristics for solving difficult combinatorial optimization problems is one of the most notable achievements of the last two decades in operations research. This paper provides an account of the most recent developments in the field and identifies some common issues and trends. Examples of applications are also reported for vehicle routing and scheduling problems.     

Convergence of the Simulated Annealing Algorithm for Continuous Global Optimization

A class of simulated annealing algorithms for continuous global optimization is considered in this paper. The global convergence property is analyzed with respect to the objective value sequence and the minimum objective value sequence induced by simulated annealing algorithms. The convergence analysis provides the appropriate conditions on both the generation probability density function and the temperature updating function. Different forms of temperature updating functions are obtained with respect to different kinds of generation probability density functions, leading to different types of simulated annealing algorithms which all guarantee the convergence to the global optimum.     

The Cross-Entropy Method for Combinatorial and Continuous Optimization

We present a new and fast method, called the cross-entropy method, for finding the optimal solution of combinatorial and continuous nonconvex optimization problems with convex bounded domains. To find the optimal solution we solve a sequence of simple auxiliary smooth optimization problems based on Kullback-Leibler cross-entropy, importance sampling, Markov chain and Boltzmann distribution. We use importance sampling as an important ingredient for adaptive adjustment of the temperature in the Boltzmann distribution and use Kullback-Leibler cross-entropy to find the optimal solution. In fact, we use the mode of a unimodal importance sampling distribution, like the mode of beta distribution, as an estimate of the optimal solution for continuous optimization and Markov chains approach for combinatorial optimization. In the later case we show almost surely convergence of our algorithm to the optimal solution. Supporting numerical results for both continuous and combinatorial optimization problems are given as well. Our empirical studies suggest that the cross-entropy method has polynomial in the size of the problem running time complexity.     

模糊置换流水车间调度的多目标模型

为了求解同时考虑模糊加工时间和模糊交货期的多目标置换流水车间调度问题,提出一种模糊多目标调度模型。针对目标之一的最大化满意度,考虑决策者偏好,建立基于悲观准则的偏好满意度模型,并在此基础上,兼顾考虑可信度,对满意度模型进行改进;针对Pareto最优解的选取,引入模糊集理论和概率论,运用面积补偿法将最大模糊完工时间去模糊化,便于可行解之间进行比较。最后,采用随机系列算例以及典型算例进行优化计算,计算结果验证了模型的有效性。     

Annealing Algorithms for Multisource Absolute Location Problems on Graph

A methodology is presented for applying annealing techniques tomultisource absolute location problems on graph. Two kinds ofobjective functions are considered: barycenters and centers. Aclass of new algorithms is described: its development startsfrom the iterative cluster-and-locate algorithm and reliesupon the relaxation of the integrality constraints onallocation variables. Experimental results are reported.     

Best Practice Simulated Annealing for the Airline Crew Scheduling Problem

We report about a study of a simulated annealing algorithm for the airline crew pairing problem based on a run-cutting formulation. Computational results are reported for some real-world short- to medium-haul test problems with up to 4600 flights per month. Furthermore we find that run time can be saved and solution quality can be improved by using a problem specific initial solution, by relaxing constraints as far as possible, by combining simulated annealing with a problem specific local improvement heuristic and by multiple independent runs.     

并行机问题的模拟退火调度算法研究

研究了一类调度目标是最小化最大完成时间的并行机调度问题.考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解.分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法.除了交换变换,还引入插入变换以改变各子调度中作业个数.大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解.     

基于模拟退火算法的矩形优化排样问题的研究

考虑了一种矩形优化排样系统中遗传算法和模拟退火算法的结合算法.首先建立了该系统的通用数学模型.然后给出了求解该问题的遗传模拟退火算法.最后用VC++6.0模拟算例的结果表明该算法是一种行之有效的方法.     

Aspiration Based Simulated Annealing Algorithm

An aspiration based simulated annealing algorithm for continuousvariables has been proposed. The new algorithm is similar to the one givenby Dekkers and Aarts (1991) except that a kind of memory is introduced intothe procedure with a self-regulatory mechanism. The algorithm has beenapplied to a set of standard global optimization problems and a number ofmore difficult, complex, practical problems and its performance comparedwith that of the algorithm of Dekkers and Aarts (1991). The new algorithmappears to offer a useful alternative to some of the currently availablestochastic algorithms for global optimization.     

基于模拟退火的CRS算法

本文是对非线性规划问题提出的一种算法,该算法把模拟退火算法应用到CRS算法中,根据模拟退火算法每一次迭代都体现集中和扩散两个策略的平衡的特点,使CRS算法更能够搜索到全局最优解,而不会陷入局部最优解。最后把提出的算法应用到两个典型的函数优化问题中,结果表明,算法是可行的、有效的