An Improved Algorithm for the Non-Guillotine-Constrained Cutting-Stock Problem

A personal-computer-based algorithm to solve the non-guillotine-constrained two-dimensional cutting-stock problem is developed. The problem is constrained to single-sized rectangles placed orthogonally on a larger containing rectangle. The algorithm uses the linear combination of box lengths and widths that minimizes waste along the cutting stock's length and width to determine an optimal layout. The algorithm's performance is evaluated using two sets of test cases and compared to the results of other algorithms.     

A Note on the Two-Dimensional Rectangular Cutting-Stock Problem

The concept of orthogonality in the Two-Dimensional Rectangular Cutting-Stock Problem is introduced. None of the published approaches for solving this problem permit non-orthogonal cutting patterns. An example is given to show that this may prevent the optimal cutting pattern from being obtained. The application of orthogonality to the problem of obtaining the minimum area rectangular enclosure of a number of rectangles is also discussed.     

An Application of Tabu Search Heuristic for the Maximum Edge-Weighted Subgraph Problem

The purpose of this article is to describe an efficient search heuristic for the Maximum Edge-weighted Subgraph (MEwS) problem. This problem requires to find a subgraph such that the sum of the weights associated with the edges of the subgraph is maximized subject to a cardinality constraint. In this study a tabu search heuristic for the MEwS problem is proposed. Different algorithms to obtain an initial solution are presented. One neighborhood search strategy is also proposed. Preliminary computational results are reported for randomly generated test problems of MEwS problem with different densities and sizes. For most of test problems, the tabu search heuristic found good solutions. In addition, for large size test problems, the tabu search outperformed the local search heuristic appearing in the literature.     

Nested Heuristic Methods for the Location-Routeing Problem

The concept of ‘nested methods’ is adopted to solve the location-routeing problem. Unlike the sequential and iterative approaches, in this method we treat the routeing element as a sub-problem within the larger problem of location. Efficient techniques that take into account the above concept and which use a neighbourhood structure inspired from computational geometry are presented. A simple version of tabu search is also embedded into our methods to improve the solutions further. Computational testing is carried out on five sets of problems of 400 customers with five levels of depot fixed costs, and the results obtained are encouraging.     

Heuristic Methods for the Data Placement Problem

Databases require a management system which is capable of retrieving and storing information as efficiently as possible. The data placement problem is concerned with obtaining an optimal assignment of data tuples onto secondary storage devices. Such tuples have complicated interrelationships which make it difficult to find an exact solution to our problem in a realistic time.We therefore consider heuristic methods—three of which are discussed and compared — the ‘greedy’ graph-collapsing method, the probabilistic hill-climbing method of simulated annealing and a third ‘greedy’ heuristic, the random improvement method, which is a local search heuristic. Overall, the best performance is obtained from the graph-collapsing method for the less complicated situations, but for larger-scale problems with complex interrelationships between tuples the simulated annealing and random improvement algorithms give better results.     

A Hybrid Heuristic for the p-Median Problem

Given n customers and a set F of m potential facilities, the p-median problem consists in finding a subset of F with p facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present a multistart hybrid heuristic that combines elements of several traditional metaheuristics to find near-optimal solutions to this problem. Empirical results on instances from the literature attest the robustness of the algorithm, which performs at least as well as other methods, and often better in terms of both running time and solution quality. In all cases the solutions obtained by our method were within 0.1% of the best known upper bounds.     

Heuristic for the Asymmetric Travelling Salesman Problem

The paper describes a heuristic algorithm for the asymmetric travelling salesman problem. The procedure is a generalization of Webb's Simple Loss 1 Method and is of the sequential type, i.e. in each step one link of the tour is fixed. The method proved to produce "high quality" near optimal solutions in a computing time, which only grows proportional to n^1.82.     

Application of Homogenization Techniques to a Seismic Problem

The subduction channel is a concept to explain certain phenomena observed by geoscientists around subduciton zones. Although many theories concering this have been formulated, the proof of the existence of such a channel is still open. We use homogenization techniques for wave propagation properties of the material to account for the microstrucural effects on seismic waves in such a supposed subduction channel. In order to assist the search for it we want to reveal the effects that it would have on elastic waves propagating in the crust, which are observed via surface measurement. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Heuristic Procedures for the Capacitated Vehicle Routing Problem

In this paper we present two new heuristic procedures for the Capacitated Vehicle Routing Problem (CVRP). The first one solves the problem from scratch, while the second one uses the information provided by a strong linear relaxation of the original problem. This second algorithm is designed to be used in a branch and cut approach to solve to optimality CVRP instances. In both heuristics, the initial solution is improved using tabu search techniques. Computational results over a set of known instances, most of them with a proved optimal solution, are given.     

A Two-phase Heuristic for the Two-dimensional Cutting-stock Problem

The two-dimensional cutting-stock problem consists of laying out a specified list of rectangular pieces on rectangular sheets, in such a way as to minimize the number of sheets used. A pattern is a combination of piece widths whose sum does not exceed the sheet's width. We present a new heuristic algorithm for this problem based on an approach with two phases: strategic phase and tactical phase. The first phase takes a global view of the problem and proposes a list of patterns to the second phase, which in turn is in charge of actually laying out these patterns on sheets. The strategic module relaxes the global problem to a one-dimensional cutting-stock problem and solves it using linear programming, while the tactical module is a recursive algorithm based on repeated knapsack operations and other heuristics.     

An Improved Heuristic for the Quadratic Assignment Problem

A technique is described whereby the computational efficiency of the Lashkari-Jaisingh heuristic for the quadratic assignment problem is greatly enhanced. Results for the modified heuristic are presented which demonstrate that it provides solutions of consistently high quality at relatively small computational cost.     

A Heuristic Approach to Quadratic Assignment Problem

A new algorithm for solving quadratic assignment problems is presented. The algorithm, which employs a sequential search technique, constructs a matrix of lower bounds on the costs of locating facilities at different sites. It then improves the elements of this matrix, one by one, by solving a succession of linear assignment problems. After all the elements of the matrix are improved, a feasible assignment is obtained, which results in an improved value for the objective function of the quadratic assignment problem. The procedure is repeated until the desired accuracy in the objective function value is obtained.     

A New Heuristic for the Quadratic Assignment Problem

We propose a new heuristic for the solution of the quadratic assignment problem. The heuristic combines ideas from tabu search and genetic algorithms. Run times are very short compared with other heuristic procedures. The heuristic performed very well on a set of test problems.     

启发式匈牙利法求解货郎担问题

针对利用动态规划求解货郎担问题的复杂难度,提出了启发式匈牙利法求解,给出了它的算法步骤及时间复杂度分析,并通过实例具体描述了启发式匈牙利法求解的过程,发现能够较快地找到最优方案,算法具有一定的实用性.     

Heuristic Techniques for Single Line Train Scheduling

Optimising a train schedule on a single line track is known to be NP-Hard with respect to the number of conflicts in the schedule. This makes it difficult to determine optimum solutions to real life problems in reasonable time and raises the need for good heuristic techniques. The heuristics applied and compared in this paper are a local search heuristic with an improved neighbourhood structure, genetic algorithms, tabu search and two hybrid algorithms. When no time constraints are enforced on solution time, the genetic and hybrid algorithms were within five percent of the optimal solution for at least ninety percent of the test problems.     

A Heuristic Method for a Job-Scheduling Problem

A batch of jobs is to be processed on a certain production line. Each job can be done in several states of the line but at varying production costs and there is also a cost of changing states. The batch is to be scheduled at minimum total cost. A method of breaking down the problem and using a branching process to generate sequences of states is given. It takes advantage of special features of the cost structure.     

同顺序流水作业排序问题的一个启发式算法

本文主要给出了同顺序m×n排序问题初始序的选取方法以及通过计算可避免出现高重循环的初始序的排序算法,然后又给出了利用矩阵可行线性质将初始序调试成较优序的可行方法.利用该文方法对n=15,m=3～14的144个例题计算,得出平均相对误差为3.145%的结果,对于m=3与m=4的128个例题计算,得出平均相对误差为0.6306%.统计结果表明该方法可在实际中进行应用.     

一类最小-最大车辆路线问题的启发式算法研究

针对个性化和多样性的需求,建立以缩短最长子线路为目标的最小-最大车辆路径问题模型, 并提出启发式算法求解。首先,采用自然数编码,使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;引入爬山算法,加强局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,保证算法能够收敛到全局最优。最后,通过实例的计算,表明本算法均优于遗传算法和禁忌搜索算法,并为大规模解决实际问题提供思路。     

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

The multilevel generalized assignment problem is a problem of assigning agents to tasks where the agents can perform tasks at more than one efficiency level. A profit is associated with each assignment and the objective of the problem is profit maximization. Two heuristic solution methods are presented for the problem. The heuristics are developed from solution methods for the generalized assignment problem. One method uses a regret minimization approach whilst the other method uses a repair approach on a relaxation of the problem. The heuristics are able to solve moderately large instances of the problem rapidly and effectively. Procedures for deriving an upper bound on the solution of the problem are also described. On larger and harder instances of the problem one heuristic is particularly effective.