A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure

A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A greedy randomized adaptive search procedure heuristic based on this neighborhood structure and using variable neighborhood descent for local search is described. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristic is quite robust and outperforms the other algorithms in the literature in terms of solution quality and time‐to‐target value.     

Solving the uncapacitated facility location problem using tabu search

A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.     

A new lower bound for the flow shop group scheduling problem

This paper presents a new lower bound that is used to evaluate nodes in a branch and bound procedure for the flow shop group scheduling problem. This lower bound is compared to the one developed by [CIRP Annals, 25 (1976) 419] and tested on small randomly generated problems. A two-phased heuristic procedure is proposed which uses branch and bound in the first phase to develop a family sequence and then uses an interchange procedure in the second phase to develop job within family sequences. The heuristic procedure is tested on larger randomly generated problems.     

Dynamic location problem under uncertainty with a regret‐based measure of robustness

In this paper, we present a dynamic uncapacitated facility location problem that considers uncertainty in fixed and assignment costs as well as in the sets of potential facility locations and possible customers. Uncertainty is represented via a set of scenarios. Our aim is to minimize the expected total cost, explicitly considering regret. Regret is understood as a measure, for each scenario, of the loss incurred for not choosing that scenario's optimal solution if that scenario indeed occurred. We guarantee that the regret for each scenario is always upper bounded. We present a mixed integer programming model for the problem and we propose a solution approach based on Lagrangean relaxation integrating a local neighborhood search and a subgradient algorithm to update Lagrangean multipliers. The problem and the solutions obtained are first analyzed through the use of illustrative examples. Computational results over sets of randomly generated test problems are also provided.     

Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent

The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.     

Bounds for the single source modular capacitated plant location problem

In this paper, we propose a discrete location problem, which we call the Single Source Modular Capacitated Location Problem (SS-MCLP). The problem consists of finding the location and capacity of the facilities, to serve a set of customers at a minimum total cost. The demand of each customer must be satisfied by one facility only and the capacities of the open facilities must be chosen from a finite and discrete set of allowable capacities. Because the SS-MCLP is a difficult problem, a lagrangean heuristic, enhanced by tabu search or local search was developed in order to obtain good feasible solutions. When needed, the lower bounds are used in order to evaluate the quality of the feasible solutions. Our method was tested computationally on randomly generated test problems some of which are with large dimensions considering the literature related to this type of problem. The computational results obtained were compared with those provided by the commercial software Cplex.     

Capacitated facility location problem with general setup cost

This paper presents an extension of the capacitated facility location problem (CFLP), in which the general setup cost functions and multiple facilities in one site are considered. The setup costs consist of a fixed term (site setup cost) plus a second term (facility setup costs). The facility setup cost functions are generally non-linear functions of the size of the facility in the same site. Two equivalent mixed integer linear programming (MIP) models are formulated for the problem and solved by general MIP solver. A Lagrangian heuristic algorithm (LHA) is also developed to find approximate solutions for this NP-hard problem. Extensive computational experiments are taken on randomly generated data and also well-known existing data (with some necessary modifications). The detailed results are provided and the heuristic algorithm is shown to be efficient.     

An LP rounding algorithm for approximating uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP, for short) in which each client can be either assigned to some opened facility or rejected by paying a penalty. Existing approaches [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642] and [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795] for this variant of facility location problem are all based on primal-dual method. In this paper, we present an efficient linear programming (LP) rounding based approach to show that LP rounding techniques are equally capable of solving this variant of facility location problem. Our algorithm uses a two-phase filtering technique (generalized from Lin and Vitter's [?-approximation with minimum packing constraint violation, in: Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, p. 771]) to identify those to-be-rejected clients and open facilities for the remaining ones. Our approach achieves an approximation ratio of 2+2/e (≈2.736) which is worse than the best approximation ratio of 2 achieved by the much more sophisticated dual fitting technique [K. Jain, M. Mahdian, E. Markakis, A. Saberi, V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, J. ACM 50 (2003) 795], but better than the approximation ratio of 3 achieved by the primal-dual method [M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Algorithms for facility location problems with outliers, in: Proc. Symposium on Discrete Algorithms, 2001, p. 642]. Our algorithm is simple, natural, and can be easily integrated into existing LP rounding based algorithms for facility location problem to deal with outliers.     

On solving unreliable planar location problems

In this paper, we generalize conventional P-median location problems by considering the unreliability of facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. We proposed efficient solution methods to determine locations of these facilities in the unreliable location model. Space-filling curve-based algorithms are developed to determine initial locations of these facilities. The unreliable P-median location problem is then decomposed to P 1-median location problems; each problem is solved to the optimum. A bounding procedure is used to monitor the iterative search, and to provide a consistent basis for termination. Extensive computational tests have indicated that the heuristics are efficient and effective for solving unreliable location problems.Scope and purposeThis paper addresses an important class of location problems, where p unreliable facilities are to be located on the plane, so as to minimize the expected travel distance or related transportation cost between the customers and their nearest available facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. Potential application of the unreliable location problem is found in numerous areas. The facilities to be located can be fire station or emergency shelter, where it fails to provide service during some time window, due to the capacity or resource constraints. Alternatively, the facilities can be telecommunication posts or logistic/distribution centers, where the service is unavailable due to breakdown, repair, shutdown of unknown causes. In this paper, we prescribed heuristic procedures to determine the location of new facilities in the unreliable location problems. The numerical study of 2800 randomly generated instances has shown that these solution procedures are both efficient and effective, in terms of computational time and solution quality.     

Cross-facility management of production and transportation planning problem

This paper studies an integrated production and transportation planning problem in a two-stage supply chain. This supply chain consists of a number of facilities, each capable of producing the final product, and a number of retailers. We assume that retailers’ demands are known deterministically and there are no production or transportation capacity constraints. We formulate the problem as a network flow problem with fixed charge costs. This is an NP  -hard problem. To solve the problem we propose a primal-dual based heuristic that generates upper and lower bounds and runs in O(FRT²)$O({\mathit{FRT}}^2)$. The quality of the upper and lower bounds is tested on a large set of randomly generated problems. The maximum error reported for these problems is 4.36% and the maximum running time is 7.65 cpu seconds.     

Effective replenishment policies for the multi-item dynamic lot-sizing problem with storage capacities

We address the dynamic lot-sizing problem considering multiple items and storage capacity. Despite we can easily characterize a subset of optimal solutions just extending the properties of the single-item case, these results are not helpful to design an efficient algorithm. Accordingly, heuristics are appropriate approaches to obtain near-optimal solutions for this NP-hard problem. Thus, we propose a heuristic procedure based on the smoothing technique, which is tested on a large set of randomly generated instances. The computational results show that the method is able to build policies that are both easily implemented and very effective, since they are on average 5% above the best solution reported by CPLEX. Moreover, an additional computational experiment is carried out to show that the performance of this new heuristic is on average better and more robust than other methods previously proposed for this problem.     

The facility and transfer points location problem

In this paper, we investigate the location of a facility and several transfer points to serve as collector points for customers who need the services of the facility. For example, demand for emergency services is generated at a set of demand points that need the services of a central facility (such as a hospital). Patients are transferred to a helicopter pad (transfer point) at normal speed, and from there they are transferred to the facility at increased speed. The model involves the location of multiple transfer points and one facility. Locating one transfer point when the set of demand points and the location of the facility are known was investigated in Berman et al. (2004a). Location of several transfer points when the location of the facility is given is investigated in Berman et al. (2004b). In this paper, we propose heuristic approaches for the solution of this problem and report computational experiments on a test set of 40 problems.     

A modified simple heuristic for the p-median problem, with facilities design applications

Facilities design is closely related to efficient use of available resources. This paper presents a heuristic approach to solve two core problems of a good facilities design: facility location and facility layout. The latter group of problems will be solved for warehouse and production systems in particular. All these problems can be formulated as p-median clustering problems. Teitz and Bart (Oper. Res. 16 (1968) 955–961) developed the vertex substitution method to solve those problems. This paper introduces effective improvements on this heuristic. The approach is tested on a large number of randomly generated cases and on problems taken from the literature. The results demonstrate the effectiveness and superiority of our method.     

A compact model and tight bounds for a combined location-routing problem

This paper considers a combined location-routing problem. We define an auxiliary network and give a compact formulation of the problem in terms of finding a set of paths in the auxiliary network that fulfill additional constraints. The LP solution to the considered model provides an initial lower bound and is also used in a rounding procedure that provides the initial solution for a Tabu search heuristic. Additionally, we propose a different lower bound based on the structure of the problem. The results of computational testing on a set of randomly generated instances are promising.     

The multi-period incremental service facility location problem

In this paper we introduce the multi-period incremental service facility location problem where the goal is to set a number of new facilities over a finite time horizon so as to cover dynamically the demand of a given set of customers. We prove that the coefficient matrix of the allocation subproblem that results when fixing the set of facilities to open is totally unimodular. This allows to solve efficiently the Lagrangean problem that relaxes constraints requiring customers to be assigned to open facilities. We propose a solution approach that provides both lower and upper bounds by combining subgradient optimization to solve a Lagrangean dual with an ad hoc heuristic that uses information from the Lagrangean subproblem to generate feasible solutions. Numerical results obtained in the computational experiments show that the obtained solutions are very good. In general, we get very small percent gaps between upper and lower bounds with little computation effort.     

Optimizing the Location of a Production Firm

A facility needs to be located in the plane to sell goods to a set of demand points. The cost for producing an item and the actual transportation cost per unit distance are given. The planner needs to determine the best location for the facility, the price charged at the source (mill price) and the transportation rate per unit distance to be charged to customers. Demand by customers is elastic and assumed declining linearly with the total charge. For each customer two parameters are given: the demand at charge zero and the decline of demand per unit charge. The objective is to find a location for the facility in the plane, the mill price charged to customers and the unit transportation rate charged to customers such that the company’s profit is maximized. The problem is formulated and an algorithm that finds the optimal solution is designed and tested on randomly generated problems.     

基于Wang-Landau算法的动态设施布局方法

动态设施布局问题是设施在车间内多个阶段的布局规划问题。目前,针对动态设施布局问题,国内外学者对离散模型研究较多,而对连续模型的研究却较少。根据连续动态设施布局的特性与需求,构建了不等面积设施的动态设施布局连续模型。求解该模型的难点在于缺乏一种高效的布局优化方法。Wang-Landau算法是一种改进的蒙特卡罗算法。通过将Wang-Landau算法与空位点放置策略、外推移动策略、内压移动策略三种启发式策略相结合,提出一种基于Wang-Landau抽样的启发式算法,并以此求解该模型。使用文献中已有的测试算例对提出的算法进行测试,计算结果表明,所提出的算法在求解连续动态设施布局问题上是有效的。     

Solving a combined cutting-stock and lot-sizing problem with a column generating procedure

In NonÅs and Thorstenson [A combined cutting stock and lot sizing problem. European Journal of Operational Research 120(2) (2000) 327–42] a combined cutting-stock and lot-sizing problem is outlined under static and deterministic conditions. In this paper we suggest a new column generating solution procedure for this problem that works well on both small and large-sized problems. The procedure includes characteristics from both the column generating procedure in NonÅs and Thorstenson, which works well on small-sized problems, and from the sequential heuristic due to Haessler [A heuristic programming solution to a nonlinear cutting stock problem, Management Science 17(12) (1971) 793–802], which works well on large-sized problems. Numerical results are presented that show that the new heuristic performs better than both of the earlier procedures. Comparisons with results obtained by other authors indicate that the procedure works well also for the extended cutting-stock problem with only a setup cost for each pattern change.     

A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose some dominance properties and two lower bounds. We also present an efficient heuristic. A branch-and-bound algorithm, in which the heuristic, the lower bounds and the dominance properties are incorporated, is proposed and tested on a large set of randomly generated instances.     

GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location problem with customer preference ordering

In this study, a maximal covering location problem is investigated. In this problem, we want to maximize the demand of a set of customers covered by a set of p facilities located among a set of potential sites. It is assumed that a set of facilities that belong to other firms exists and that customers freely choose allocation to the facilities within a coverage radius. The problem can be formulated as a bilevel mathematical programming problem, in which the leader locates facilities in order to maximize the demand covered and the follower allocates customers to the most preferred facility among those selected by the leader and facilities from other firms. We propose a greedy randomized adaptive search procedure (GRASP) heuristic and a hybrid GRASP-Tabu heuristic to find near optimal solutions. Results of the heuristic approaches are compared to solutions obtained with a single-level reformulation of the problem. Computational experiments demonstrate that the proposed algorithms can find very good quality solutions with a small computational burden. The most important feature of the proposed heuristics is that, despite their simplicity, optimal or near-optimal solutions can be determined very efficiently.