Search results for "Heuristic"
showing 10 items of 476 documents
General Concepts in Metaheuristic Search
2017
Metaheuristics have become a very popular family of solution methods for optimization problems because they are capable of finding “acceptable” solutions in a “reasonable” amount of time. Most optimization problems in practice are too complex to be approached by exact methods that can guarantee finding global optimal solutions. The time required to find and verify globally optimal solutions is impractical in most applications. An entire computational theory, which we will not discussed here, has been developed around problem complexity. It suffices to say that it is now known that the great majority of the optimization problems found in practice fall within a category that makes them “compu…
Advanced Scatter Search for the Max-Cut Problem
2009
The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity prob…
GRASP and path relinking for the max–min diversity problem
2010
The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary p…
A comparison of different solution approaches to the vehicle scheduling problem in a practical case
2000
Abstract The Vehicle Scheduling Problem (VSP) consists in assigning a set of scheduled trips to a set of vehicles, satisfying a set of constraints and optimizing an objective function. A wide literature exists for the VSP, but usually not all the practical requirements of the real cases are taken into account. In the present paper a practical case is studied, and for it a traditional method is tailored and two innovative heuristics are developed. As the problem presents a multicriteria nature, each of the three algorithms adopts a different approach to multicriteria optimization. Scalarization of the different criteria is performed by the traditional algorithm. A lexicographic approach is f…
Hybridizing the cross-entropy method: An application to the max-cut problem
2009
Cross-entropy has been recently proposed as a heuristic method for solving combinatorial optimization problems. We briefly review this methodology and then suggest a hybrid version with the goal of improving its performance. In the context of the well-known max-cut problem, we compare an implementation of the original cross-entropy method with our proposed version. The suggested changes are not particular to the max-cut problem and could be considered for future applications to other combinatorial optimization problems.
Adaptive and Dynamic Ant Colony Search Algorithm for Optimal Distribution Systems Reinforcement Strategy
2006
The metaheuristic technique of Ant Colony Search has been revised here in order to deal with dynamic search optimization problems having a large search space and mixed integer variables. The problem to which it has been applied is an electrical distribution systems management problem. This kind of issues is indeed getting increasingly complicated due to the introduction of new energy trading strategies, new environmental constraints and new technologies. In particular, in this paper, the problem of finding the optimal reinforcement strategy to provide reliable and economic service to customers in a given time frame is investigated. Utilities indeed need efficient software tools to take deci…
Local search based evolutionary multi-objective optimization algorithm for constrained and unconstrained problems
2009
Evolutionary multi-objective optimization algorithms are commonly used to obtain a set of non-dominated solutions for over a decade. Recently, a lot of emphasis have been laid on hybridizing evolutionary algorithms with MCDM and mathematical programming algorithms to yield a computationally efficient and convergent procedure. In this paper, we test an augmented local search based EMO procedure rigorously on a test suite of constrained and unconstrained multi-objective optimization problems. The success of our approach on most of the test problems not only provides confidence but also stresses the importance of hybrid evolutionary algorithms in solving multi-objective optimization problems.
Using a TSP heuristic for routing order pickers in warehouses
2010
In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-sp…
Optimal positioning of irregular shapes in stamping die strip
2010
The nesting of two-dimensional shapes is a common problem, where raw material has to be economically cut. As for the single-pass single-row strip layout, several algorithms, based on established methods, have been proposed. Moreover, it should be noticed that the optimum layout should also consider a few constraints, like grain orientation for subsequent forming operation, correct bridge width, and the commercial roll of metal width in order to make solutions applicable in real industrial environments. Most of the procedures until now shown in literature are quite complex and often ignore these real constraints. They usually make use of sliding techniques and are not able to effectively wor…
Construction and optimality of a special class of balanced designs
2006
The use of balanced designs is generally advisable in experimental practice. In technological experiments, balanced designs optimize the exploitation of experimental resources, whereas in marketing research experiments they avoid erroneous conclusions caused by the misinterpretation of interviewed customers. In general, the balancing property assures the minimum variance of first-order effect estimates. In this work the authors consider situations in which all factors are categorical and minimum run size is required. In a symmetrical case, it is often possible to find an economical balanced design by means of algebraic methods. Conversely, in an asymmetrical case algebraic methods lead to e…