共查询到20条相似文献,搜索用时 31 毫秒
1.
Simulated annealing metaheuristics for the vehicle routing problem with time windows 总被引:9,自引:0,他引:9
This paper develops simulated annealing metaheuristics for the vehicle routing and scheduling problem with time window constraints.
Two different neighborhood structures, the λ-interchange mechanism of Osman and thek-node interchange process of Christofides and Beasley, are implemented. The enhancement of the annealing process with a short-term
memory function via a tabu list is examined as a basis for improving the metaheuristic approach. Computational results on
test problems from the literature as well as large-scale real-world problem are reported. The metaheuristics achieve solutions
that compare favorably with previously reported results. 相似文献
2.
In this paper, we address the flowpath design issue of Automated Guided Vehicle Systems (AGVSs). In particular, we concentrate on the design of unidirectional flowpaths (i.e. vehicles are restricted to travel only in one direction along a given segment of the flowpath). We have developed intelligent heuristics — simulated annealing and tabu search algorithms for the design of unidirectional AGVSs. Different versions of simulated annealing and tabu search algorithms are implemented. Our extensive computational results indicate that both simulated annealing and tabu search yield solutions of adequate quality for all practical purposes. A tabu search implementation with the use of a frequency-based memory structure dominates all tested heuristics in terms of solution quality (i.e. percent deviation from optimality), with an impressive average performance over 45 test problems of less than 0.85% deviation from optimality. 相似文献
3.
Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem 总被引:3,自引:0,他引:3
Miroslaw Malek Mohan Guruswamy Mihir Pandya Howard Owens 《Annals of Operations Research》1989,21(1):59-84
This paper describes serial and parallel implementations of two different search techniques applied to the traveling salesman problem. A novel approach has been taken to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses abbreviated cooling schedule and achieves a superlinear speedup. Also a new search technique, called tabu search, has been adapted to execute in a parallel computing environment. Comparison between simulated annealing and tabu search indicate that tabu search consistently outperforms simulated annealing with respect to computation time while giving comparable solutions. Examples include 25, 33, 42, 50, 57, 75 and 100 city problems. 相似文献
4.
Dalila Boughaci Belaïd Benhamou Habiba Drias 《Journal of Mathematical Modelling and Algorithms》2010,9(2):165-180
In this paper, both stochastic local search (SLS) and tabu search (TS) are studied for the optimal winner determination problem
(WDP) in combinatorial auctions. The proposed methods are evaluated on various benchmark problems, and compared with the hybrid
simulated annealing (SAGII), the memetic algorithms (MA) and Casanova. The computational experiments show that the SLS provides
competitive results and finds solutions of a higher quality than TS and Casanova methods. 相似文献
5.
Hari K. Rajagopalan F. Elizabeth Vergara Cem Saydam Jing Xiao 《European Journal of Operational Research》2007
This article employs a statistical experimental design to guide and evaluate the development of four meta-heuristics applied to a probabilistic location model. The meta-heuristics evaluated include evolutionary algorithm, tabu search, simulated annealing, and a hybridized hill-climbing algorithm. Comparative results are analyzed using ANOVA. Our findings show that all four implementations produce high quality solutions. In particular, it was found that on average tabu search and simulated annealing find their best solutions in the least amount of time, with relatively small variability. This is especially important for large-size problems when dynamic redeployment is required. 相似文献
6.
Alexander G. Nikolaev Sheldon H. Jacobson Shane N. Hall Darrall Henderson 《Computational Optimization and Applications》2011,49(3):407-433
This paper presents a framework for analyzing and comparing sub-optimal performance of local search algorithms for hard discrete
optimization problems. The β-acceptable solution probability is introduced that captures how effectively an algorithm has performed to date and how effectively
an algorithm can be expected to perform in the future. Using this probability, the necessary conditions for a local search
algorithm to converge in probability to β-acceptable solutions are derived. To evaluate and compare the effectiveness of local search algorithms, two estimators for
the expected number of iterations to visit a β-acceptable solution are obtained. Computational experiments are reported with simulated annealing and tabu search applied
to four small traveling salesman problem instances, and the Lin-Kernighan-Helsgaun algorithm applied to eight medium to large
traveling salesman problem instances (all with known optimal solutions), to illustrate the application of these estimators. 相似文献
7.
In this paper the usage of a stochastic optimization algorithm as a model search tool is proposed for the Bayesian variable selection problem in generalized linear models. Combining aspects of three well known stochastic optimization algorithms, namely, simulated annealing, genetic algorithm and tabu search, a powerful model search algorithm is produced. After choosing suitable priors, the posterior model probability is used as a criterion function for the algorithm; in cases when it is not analytically tractable Laplace approximation is used. The proposed algorithm is illustrated on normal linear and logistic regression models, for simulated and real-life examples, and it is shown that, with a very low computational cost, it achieves improved performance when compared with popular MCMC algorithms, such as the MCMC model composition, as well as with “vanilla” versions of simulated annealing, genetic algorithm and tabu search. 相似文献
8.
We develop a search procedure for project scheduling problems with multiple resource constraints as well as precedence constraints. The procedure is applied to three popular search heuristics, simulated annealing, tabu search and genetic algorithms. In the heuristics, a solution is represented with a string of numbers each of which denotes priority of each activity. The priorities are used to select an activity for scheduling among competing ones. The search heuristics with this encoding method can always generate feasible neighbourhood solutions for a given solution. Moreover, this encoding method is very flexible in that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints can be considered without much difficulty. Results of computational tests on the performance of the search heuristics showed that the search heuristics, especially the simulated annealing and tabu search algorithms worked better than existing heuristics. 相似文献
9.
John G. Klincewicz 《Annals of Operations Research》1992,40(1):283-302
In the discretep-hub location problem, various nodes interact with each other by sending and receiving given levels of traffic (such as telecommunications traffic, data transmissions, airline passengers, packages, etc.). It is necessary to choosep of the given nodes to act as hubs, which are fully interconnected; it is also necessary to connect each other node to one of these hubs so that traffic can be sent between any pair of nodes by using the hubs as switching points. The objective is to minimize the sum of the costs for sending traffic along the links connecting the various nodes. Like many combinatorial problems, thep-hub location problem has many local optima. Heuristics, such as exchange methods, can terminate once such a local optimum is encountered. In this paper, we describe new heuristics for thep-hub location problem, based on tabu search and on a greedy randomized adaptive search procedure (GRASP). These recently developed approaches to combinatorial optimization are capable of examining several local optima, so that, overall, superior solutions are found. Computational experience is reported in which both tabu search and GRASP found optimal hub locations (subject to the assumption that nodes must be assigned to the nearest hub) in over 90% of test problems. For problems for which such optima are not known, tabu search and GRASP generated new best-known solutions. 相似文献
10.
Andrew Sohn 《Annals of Operations Research》1996,63(1):29-55
Simulated annealing is known to be highly sequential due to dependences between iterations. While the conventional speculative
computation with a binary tree has been found effective for parallel simulated annealing, its performance is limited to (logp)-fold speedup due to parallel execution of logp iterations onp processors. This report presents a new approach to parallel simulated annealing, calledgeneralized speculative computation (GSC). The GSC is synchronous, maintaining the same decision sequence as sequential simulated annealing. The use of two loop
indices encoded in a single integer eliminates broadcasting of central data structure to all processors. The master-slave
parallel programming paradigm simplifies controlling the activities ofp iterations which are executed in parallel onp processors. To verify the performance of GSC, we implemented 100-city to 500-city Traveling Salesman Problems on the AP1000
massively parallel multiprocessor. Execution results on the AP1000 demonstrate that the GSC approach can indeed be an effective
method for parallel simulated annealing as it gave over 20-fold speedup on 100 processors. 相似文献
11.
Patric R. J.
stergrd 《组合设计杂志》1997,5(1):71-80
The problem of finding good covering codes in Hamming spaces is considered. Many different local search methods have been used to find packing codes (the dual problem), whereas practically all published results on searches for covering codes are based on simulated annealing. In this article tabu search is evaluated and compared against the simulated annealing method. A novel neighborhood function is also presented. The combination of a new optimization method and a new neighborhood function turns out to speed up the search for covering codes remarkably compared to the traditional simulated annealing approach. Using the new approach, the best known upper bound for the football pool problem for 9 matches is improved to 1341. © 1997 John Wiley & Sons, Inc. 相似文献
12.
We use Bayesian decision theory to address a variable selection problem arising in attempts to indirectly measure the quality of hospital care, by comparing observed mortality rates to expected values based on patient sickness at admission. Our method weighs data collection costs against predictive accuracy to find an optimal subset of the available admission sickness variables. The approach involves maximizing expected utility across possible subsets, using Monte Carlo methods based on random division of the available data into N modeling and validation splits to approximate the expectation. After exploring the geometry of the solution space, we compare a variety of stochastic optimization methods –- including genetic algorithms (GA), simulated annealing (SA), tabu search (TS), threshold acceptance (TA), and messy simulated annealing (MSA) –- on their performance in finding good subsets of variables, and we clarify the role of N in the optimization. Preliminary results indicate that TS is somewhat better than TA and SA in this problem, with MSA and GA well behind the other three methods. Sensitivity analysis reveals broad stability of our conclusions. 相似文献
13.
Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem 总被引:37,自引:0,他引:37
Ibrahim Hassan Osman 《Annals of Operations Research》1993,41(4):421-451
The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature. 相似文献
14.
A comparison of local search methods for flow shop scheduling 总被引:1,自引:0,他引:1
Local search techniques are widely used to obtain approximate solutions to a variety of combinatorial optimization problems. Two important categories of local search methods are neighbourhood search and genetic algorithms. Commonly used neighbourhood search methods include descent, threshold accepting, simulated annealing and tabu search. In this paper, we present a computational study that compares these four neighbourhood search methods, a genetic algorithm, and a hybrid method in which descent is incorporated into the genetic algorithm. The performance of these six local search methods is evaluated on the problem of scheduling jobs in a permutation flow shop to minimize the total weighted completion time. Based on the results of extensive computational tests, simulated annealing is found to generate better quality solutions than the other neighborhood search methods. However, the results also indicate that the hybrid genetic descent algorithm is superior to simulated annealing. 相似文献
15.
David L. Woodruff David M. Rocke 《Journal of computational and graphical statistics》2013,22(1):69-95
Abstract A method of robust estimation of multivariate location and shape that has attracted a lot of attention recently is Rousseeuw's minimum volume ellipsoid estimator (MVE). This estimator has a high breakdown point but is difficult to compute successfully. In this article, we apply methods of heuristic search to this problem, including simulated annealing, genetic algorithms, and tabu search, and compare the results to the undirected random search algorithm that is often cited. Heuristic search provides several effective algorithms that are far more computationally efficient than random search. Furthermore, random search, as currently implemented, is shown to be ineffective for larger problems. 相似文献
16.
An efficient algorithm for range computation of polynomials using the Bernstein form 总被引:1,自引:0,他引:1
We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial
approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a
new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the
proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function
method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search
and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments
and qualitative comparisons. 相似文献
17.
Solving the flight perturbation problem with meta heuristics 总被引:1,自引:0,他引:1
Tobias Andersson 《Journal of Heuristics》2006,12(1-2):37-53
When there is a perturbation in a carefully constructed aircraft schedule, e.g. an aircraft breakdown, it is important to
minimize the negative consequences of this disturbance. Here, a tabu search and a simulated annealing approach to the flight
perturbation problem are presented. The heuristics use a tree-search algorithm to find new schedules for the aircraft, and
utilize a path relinking strategy to explore paths between structurally different solutions. The computational results indicate
that the solution strategies, especially the tabu search, can be successfully used to solve the flight perturbation problem. 相似文献
18.
Daniel Costa 《Annals of Operations Research》1993,41(4):343-358
A generalization of the classical graph coloring model is studied in this paper. The problem we are interested in is a variant of the generalT-coloring problem related in the literature. We want to color the vertices of a graph in such a way that the two colors assigned to two adjacent verticesi andj differ by at least
ij
, wheret
ij
is a fixed coefficient associated to the edge [i, j]. The goal is to minimize the length of the spectrum of colors used. We present here the results produced by well-known heuristics (tabu search and simulated annealing) applied to the considered problem. The results are compared with optimal colorings obtained by a branch-and-bound algorithm. 相似文献
19.
The minimum weight vertex cover problem is a basic combinatorial optimization problem defined as follows. Given an undirected graph and positive weights for all vertices the objective is to determine a subset of the vertices which covers all edges such that the sum of the related cost values is minimized. In this paper we apply a modified reactive tabu search approach for solving the problem. While the initial concept of reactive tabu search involves a random walk we propose to replace this random walk by a controlled simulated annealing. Numerical results are presented outperforming previous metaheuristic approaches in most cases. 相似文献
20.
《European Journal of Operational Research》2001,134(1):103-119
The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported. 相似文献