共查询到20条相似文献,搜索用时 15 毫秒
1.
Cutting stock problems deal with the generation of a set of cutting patterns that minimizes waste. Sometimes it is also important to find the processing sequence of this set of patterns to minimize the maximum queue of partially cut orders. In such instances a cutting sequencing problem has to be solved. This paper presents a new mathematical model and a three-phase approach for the cutting sequencing problem. In the first phase, a greedy algorithm produces a good starting solution that is improved in the second phase by a tabu search, or a generalized local search procedure, while, in the last phase, the problem is optimally solved by an implicit enumeration procedure that uses the best solution previously found as an upper bound. Computing experience, based on 300 randomly generated problems, shows the good performance of the heuristic methods presented. 相似文献
2.
3.
In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems. 相似文献
4.
M. Woodside-Oriakhi C. Lucas J.E. Beasley 《European Journal of Operational Research》2011,213(3):538-550
This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time. 相似文献
5.
This article addresses an extension of the multi-depot vehicle routing problem in which vehicles may be replenished at intermediate depots along their route. It proposes a heuristic combining the adaptative memory principle, a tabu search method for the solution of subproblems, and integer programming. Tests are conducted on randomly generated instances. 相似文献
6.
Irina Gribkovskaia Øyvind Halskau sr. Gilbert Laporte Martin Vlček 《European Journal of Operational Research》2007
The single vehicle routing problem with pickups and deliveries (SVRPPD) is defined on a graph in which pickup and delivery demands are associated with the customer vertices. The problem consists of designing a least cost route for a vehicle of capacity Q. Each customer is allowed to be visited once for a combined pickup and delivery, or twice if these two operations are performed separately. This article proposes a mixed integer linear programming model for the SVRPPD. It introduces the concept of general solution which encompasses known solution shapes such as Hamiltonian, double-path and lasso. Classical construction and improvement heuristics, as well as a tabu search heuristic, are developed and tested over several instances. Computational results show that the best solutions generated by the heuristics are frequently non-Hamiltonian and may contain up to two customers visited twice. 相似文献
7.
The purpose of this study is to develop some understanding of the benefits that can be derived from the inclusion of diversification strategies in tabu search methods. To do so, we discuss the implementation of various diversification strategies in several tabu search heuristics developed for the maximum clique problem. Computational results on a large set of randomly generated test problems are reported and compared to assess the impact of these techniques on solution quality and running time. 相似文献
8.
Gerald Paul 《Operations Research Letters》2010,38(6):577-581
For almost two decades the question of whether tabu search (TS) or simulated annealing (SA) performs better for the quadratic assignment problem has been unresolved. To answer this question satisfactorily, we compare performance at various values of targeted solution quality, running each heuristic at its optimal number of iterations for each target. We find that for a number of varied problem instances, SA performs better for higher quality targets while TS performs better for lower quality targets. 相似文献
9.
Alysson M. Costa Jean-François Cordeau Gilbert Laporte 《European Journal of Operational Research》2008
This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. 相似文献
10.
Lijun WeiWee-Chong Oon Wenbin Zhu Andrew Lim 《European Journal of Operational Research》2011,215(2):337-346
In this paper, we propose a greedy heuristic for the 2D rectangular packing problem (2DRP) that represents packings using a skyline; the use of this heuristic in a simple tabu search approach outperforms the best existing approach for the 2DRP on benchmark test cases. We then make use of this 2DRP approach as a subroutine in an “iterative doubling” binary search on the height of the packing to solve the 2D rectangular strip packing problem (2DSP). This approach outperforms all existing approaches on standard benchmark test cases for the 2DSP. 相似文献
11.
The attribute based hill climber (ABHC) is a variant of the general tabu-search principle which has shown to be competitive with respect to quality as well as efficiency to other local search heuristics for the two corner stone problems in combinatorial optimization: the travelling salesman problem and the quadratic assignment problem. ABHC is completely parameter-free, and its generic logic depends on the concept of partitioning the solution space based on solution “attributes”, which is the problem-specific choice. In this paper we analyze the effectiveness of this concept and the efficiency of the ABHC heuristic for the general vehicle routing problem. 相似文献
12.
This paper considers the design and analysis of algorithms for the multi-depot vehicle routing problem with time windows (MDVRPTW). Given the intrinsic difficulty of this problem class, approximation methods of the type ‘cluster first, route second’ (two-step approaches) seem to offer the most promise for practical size problems. After describing six heuristics for the cluster part (assignment of customers to depots) an initial computational study of their performance is conducted. Finding, as expected, that the heuristics with the best results (in terms of the routing results) are those with the largest computational efforts. 相似文献
13.
The fleet size and mix vehicle routing problem consists of defining the type, the number of vehicles of each type, as well as the order in which to serve the customers with each vehicle when a company has to distribute goods to a set of customers geographically spread, with the objective of minimizing the total costs. In this paper, a heuristic algorithm based on tabu search is proposed and tested on several benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature. 相似文献
14.
15.
This paper deals with a ring-mesh network design problem arising from the deployment of an optical transport network. The
problem seeks to find an optimal clustering of traffic demands in the network such that the total cost of optical add-drop
multiplexer (OADM) and optical cross-connect (OXC) is minimized, while satisfying the OADM ring capacity constraint, the node
cardinality constraint, and the OXC capacity constraint. We formulate the problem as an integer programming model and propose
several alternative modeling techniques designed to improve the mathematical representation of the problem. We then develop
various classes of valid inequalities to tighten the mathematical formulation of the problem and describe an algorithmic approach
that coordinates tailored routines with a commercial solver CPLEX. We also propose an effective tabu search procedure for
finding a good feasible solution as well as for providing a good incumbent solution for the column generation based heuristic
procedure that enhances the solvability of the problem. Computational results exhibit the viability of the proposed method. 相似文献
16.
The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. 相似文献
17.
We propose and develop an efficient implementation of the robust tabu search heuristic for sparse quadratic assignment problems. The traditional implementation of the heuristic applicable to all quadratic assignment problems is of O(N2) complexity per iteration for problems of size N. Using multiple priority queues to determine the next best move instead of scanning all possible moves, and using adjacency lists to minimize the operations needed to determine the cost of moves, we reduce the asymptotic (N → ∞) complexity per iteration to O(N log N). For practical sized problems, the complexity is O(N). 相似文献
18.
Maria Cândida Mourão Ana Catarina Nunes Christian Prins 《European Journal of Operational Research》2009
The sectoring arc routing problem (SARP) is introduced to model activities associated with the streets of large urban areas, like municipal waste collection. The aim is to partition the street network into a given number of sectors and to build a set of vehicle trips in each sector, to minimize the total duration of the trips. Two two-phase heuristics and one best insertion method are proposed. In the two-phase methods, phase 1 constructs the sectors using two possible heuristics, while phase 2 solves a mixed capacitated arc routing problem (MCARP) to compute the trips in each sector. The best insertion method determines sectors and trips simultaneously. In addition to solution cost, some evaluation criteria such as imbalance, diameter and dispersion measures are used to compare algorithms. Numerical results on large instances with up to 401 nodes and 1056 links (arcs or edges) are reported and analysed. 相似文献
19.
This paper introduces an iterated tabu search heuristic for the daily car sequencing problem in which a set of cars must be sequenced so as to satisfy requirements from the paint shop and the assembly line. The iterated tabu search heuristic combines a classical tabu search with perturbation operators that help escape from local optima. The resulting heuristic is flexible, easy to implement, and fast. It has produced very good results on a set of test instances provided by the French car manufacturer Renault. 相似文献
20.
A tabu search algorithm for the Open Shop problem 总被引:1,自引:0,他引:1
In this paper we consider the minimum makespan Open Shop problem without preemption. It is well-known that the case with only
two machines can be optimally solved in linear time, whereas the problem with an arbitrary number of machines is NP-hard in
the strong sense. We propose a tabu search algorithm for the solution of the problem which uses simple list scheduling algorithms
to build the starting solutions. The algorithm is extensively tested on randomly generated instances. 相似文献