Two New Heuristic Procedures for the Joint Replenishment Problem

In this paper, we develop two new efficient heuristic procedures for the joint replenishment problem. Each of the two heuristic procedures generates iteratively a near-optimal replenishment policy starting with ordering frequencies that are derived from the solution to a relaxed version of the joint replenishment problem. Both heuristic procedures are illustrated with an example problem involving five jointly ordered items. Seven more illustrative problems, taken from the joint replenishment problem literature, are also solved to assess the cost performance of the two heuristic procedures. They both provide the global optimal replenishment policies for all the illustrative problems.     

An Interior Point Heuristic for the Hamiltonian Cycle Problem via Markov Decision Processes

We consider the Hamiltonian cycle problem embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We show that Hamiltonian cycles (if any) correspond to the global minima of a suitably constructed indefinite quadratic programming problem over the frequency space. We show that the above indefinite quadratic can be approximated by quadratic functions that are `nearly convex' and as such suitable for the application of logarithmic barrier methods. We develop an interior-point type algorithm that involves an arc elimination heuristic that appears to perform rather well in moderate size graphs. The approach has the potential for further improvements.     

Curve Shortening Flow in Arbitrary Dimensional Euclidian Space

In this paper, curve shortening flow in Euclidian space R^n（n≥3） is studied, and S. Altschuler＇s results about flow for space curves are generalized. We prove that the curve shortening flow converges to a straight line in infinite time if the initial curve is a ramp. We also prove the planar phenomenon when the curve shortening flow blows up.     

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.     

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.     

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.     

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.     

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 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.     

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 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 Methods for the Multi-product Dynamic Lot Size Problem

Many heuristics exist for the single-item dynamic lot-size problem, for example, the Silver-Meal, the part period balancing and a simple variant of the part period balancing. The worst case performances of these heuristics have been shown to be zero, 1/3 and 1/2 respectively. These heuristics can be generalized to the dynamic version of the joint replenishment problem, that is, the multi-product dynamic lot-size problem. Such a generalization of the Silver-Meal heuristic has been shown to perform well on a set of test problems. This paper generalizes the part period balancing heuristic, and a simple variant of it to the multiproduct dynamic lot-size problem, and shows that the worst case performances of the generalized heuristics remain 1/3 and 1/2 respectively. An improved version of the generalized Silver-Meal heuristic is also given.     

Heuristic Procedures for Solving the Discrete Ordered Median Problem

We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median and p-center. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega (1996) for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS) proposed by Hansen and Mladenović (1997) for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare them.     

An Iterative Construction Heuristic for the Ore Selection Problem

The ore selection problem involves choosing a processing option for a number of mining blocks that maximises the expected payoff for a given level of financial risk. An innovative neighbourhood search heuristic is proposed for the ore selection problem. This iterative construction heuristic employs a stochastic demolition and reconstruction strategy. Computational experiments with this heuristic for two ore selection problem instances, one involving 2,500 blocks and the other involving 78,000 blocks, are given. These problem instances are made publicly available for use by future workers. Our computational experiments indicate that the proposed heuristic produces better quality solutions faster than a relay hybrid (constructive-simulated annealing) heuristic.     

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.     

A Repeated Matching Heuristic for the Vehicle Routeing Problem

A new heuristic for the vehicle routeing problem which makes use of repeated matching is described. The numerical results are comparable to or better than the best published for most of the 14 benchmark problems commonly used to evaluate VRP heuristics.     

Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.