A tabu search heuristic procedure for the capacitated facility location problem

A tabu search heuristic procedure is developed, implemented and computationally tested for the capacitated facility location problem. The procedure uses different memory structures. Visited solutions are stored in a primogenitary linked quad tree. For each facility, the recent move at which the facility changed its status and the frequency it has been open are also stored. These memory structures are used to guide the main search process as well as the diversification and intensification processes. Lower bounds on the decreases of total cost are used to measure the attractiveness of the moves and to select moves in the search process. A specialized network algorithm is developed to exploit the problem structure in solving transportation problems. Criterion altering, solution reconciling and path relinking are used to perform intensification functions. The performance of the procedure is tested through computational experiments using test problems from the literature and new test problems randomly generated. It found optimal solutions for almost all test problems from the literature. As compared to the heuristic method of Lagrangean relaxation with improved subgradient scheme, the tabu search heuristic procedure found much better solutions using much less CPU time.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

A heuristic algorithm for the asymmetric capacitated vehicle routing problem

We consider the Asymmetric Capacitated Vehicle Routing Problem (ACVRP[, a particular case of the standard asymmetric Vehicle Routing Problem arising when only the vehicle capacity constraints are imposed. ACVRP is known to be NP-hard and finds practical applications, e.g. in distribution and scheduling. In this paper we describe the extension to ACVRP of the two well-known Clarke-Wright and Fisher-Jaikumar heuristic algorithms. We also propose a new heuristic algorithm for ACVRP that, starting with an initial infeasible solution, determines the final set of vehicle routes through an insertion procedure as well as intea-route and inter-route arc exchanges. The initial infeasible solution is obtained by using the additive bounding procedures for ACVRP described by Fischetti, Toth and Vigo in 1992. Extensive computational results on several classes of randomly generated test problems involving up to 300 customers and on some real instances of distribution problems in urban areas, are presented. The results obtained show that the proposed approach favourably compares with previous algorithms from the literature.     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

A partial dual algorithm for the capacitated warehouse location problem

The Capacitated Warehouse Location Problem (CWLP) consists of the ordinary transportation problem with the additional feature of a fixed cost associated with each supplier. A supplier can be used towards meeting the demands of the customers only if the corresponding fixed cost is incurred. The problem is to determine which suppliers to use and how the customer demands should be met, so that total cost is minimised.Most of the recently published algorithms for CWLP use branch and bound based on a Lagrangian relaxation of demand constraints. Here, a partial dual of a tight LP formulation is used in order to take advantage of the properties of transportation problems. Computational results are given which show good overall performance of the algorithm, with the size of the tree search being reduced compared with previous published results.     

A cutting plane algorithm for the capacitated facility location problem

The Capacitated Facility Location Problem (CFLP) is to locate a set of facilities with capacity constraints, to satisfy at the minimum cost the order-demands of a set of clients. A multi-source version of the problem is considered in which each client can be served by more than one facility. In this paper we present a reformulation of the CFLP based on Mixed Dicut Inequalities, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables. By aggregating flow variables, any Mixed Dicut Inequality turns into a binary minimum knapsack inequality with a single continuous variable. We will refer to the convex hull of the feasible solutions of this minimum knapsack problem as the Mixed Dicut polytope. We observe that the Mixed Dicut polytope is a rich source of valid inequalities for the CFLP: basic families of valid CFLP inequalities, like Variable Upper Bounds, Cover, Flow Cover and Effective Capacity Inequalities, are valid for the Mixed Dicut polytope. Furthermore we observe that new families of valid inequalities for the CFLP can be derived by the lifting procedures studied for the minimum knapsack problem with a single continuous variable. To deal with large-scale instances, we have developed a Branch-and-Cut-and-Price algorithm, where the separation algorithm consists of the complete enumeration of the facets of the Mixed Dicut polytope for a set of candidate Mixed Dicut Inequalities. We observe that our procedure returns inequalities that dominate most of the known classes of inequalities presented in the literature. We report on computational experience with instances up to 1000 facilities and 1000 clients to validate the approach.     

A cut-and-solve based algorithm for the single-source capacitated facility location problem

In this paper, we present a cut-and-solve (CS) based exact algorithm for the Single Source Capacitated Facility Location Problem (SSCFLP). At each level of CS’s branching tree, it has only two nodes, corresponding to the Sparse Problem (SP) and the Dense Problem (DP), respectively. The SP, whose solution space is relatively small with the values of some variables fixed to zero, is solved to optimality by using a commercial MIP solver and its solution if it exists provides an upper bound to the SSCFLP. Meanwhile, the resolution of the LP of DP provides a lower bound for the SSCFLP. A cutting plane method which combines the lifted cover inequalities and Fenchel cutting planes to separate the 0–1 knapsack polytopes is applied to strengthen the lower bound of SSCFLP and that of DP. These lower bounds are further tightened with a partial integrality strategy. Numerical tests on benchmark instances demonstrate the effectiveness of the proposed cutting plane algorithm and the partial integrality strategy in reducing integrality gap and the effectiveness of the CS approach in searching an optimal solution in a reasonable time. Computational results on large sized instances are also presented.     

A comparison of heuristics and relaxations for the capacitated plant location problem

Approaches proposed in the literature for the Capacitated Plant Location Problem are compared. The comparison is based on new theoretical and computational results. The main emphasis is on relaxations. In particular, dominance relations among the various relaxations found in the literature are identified. In the computational study, the relaxations are compared as a function of various characteristics of the test problems. Several of these relaxations can be used to generate heuristic feasible solutions that are better than the classical greedy or interchange heuristics, both in computing time and in the quality of the solutions found.     

An efficient heuristic algorithm for the capacitated p-\! median problem

The capacitated $p$ -median problem (CPMP) is one of the well-known facility-location problems. The objective of the problem is to minimize total cost of locating a set of capacitated service points and allocating a set of demand points to the located service points, while the total allocated demand for each service point is not be greater than its capacity limit. This paper presents an efficient heuristic algorithm based on the local branching and relaxation induced neighborhood search methods for the CPMP. The proposed algorithm is a heuristic technique that utilizes a general mixed integer programming solver to explore neighborhoods. The parameters of the proposed algorithm are tuned by design of experiments. The proposed method is tested on a large set of benchmark instances. The results show that the method outperforms the best method found in the literature.     

A scatter search heuristic for the capacitated clustering problem

This paper proposes a scatter search-based heuristic approach to the capacitated clustering problem. In this problem, a given set of customers with known demands must be partitioned into p distinct clusters. Each cluster is specified by a customer acting as a cluster center for this cluster. The objective is to minimize the sum of distances from all cluster centers to all other customers in their cluster, such that a given capacity limit of the cluster is not exceeded and that every customer is assigned to exactly one cluster. Computational results on a set of instances from the literature indicate that the heuristic is among the best heuristics developed for this problem.     

A perturbation-based heuristic for the capacitated multisource Weber problem

This paper proposes a perturbation-based heuristic for the capacitated multisource Weber problem. This procedure is based on an effective use of borderline customers. Several implementations are considered and the two most appropriate are then computationally enhanced by using a reduced neighbourhood when solving the transportation problem. Computational results are presented using data sets from the literature, originally used for the uncapacitated case, with encouraging results.     

A greedy heuristic for the capacitated minimum spanning tree problem

This paper develops a greedy heuristic for the capacitated minimum spanning tree problem (CMSTP), based on the two widely known methods of Prim and of Esau–Williams. The proposed algorithm intertwines two-stages: an enhanced combination of the Prim and Esau–Williams approaches via augmented and synthetic node selection criteria, and an increase of the feasible solution space by perturbing the input data using the law of cosines. Computational tests on benchmark problems show that the new heuristic provides extremely good performance results for the CMSTP, justifying its effectiveness and robustness. Furthermore, excluding the feasible space expansion, we show that we can still obtain good quality solutions in very short computational times.     

A Lagrangian heuristic algorithm for a public healthcare facility location problem

We consider a healthcare facility location problem in which there are two types of patients, low-income patients and middle- and high-income patients. The former can use only public facilities, while the latter can use both public facilities and private facilities. We focus on the problem of determining locations of public healthcare facilities to be established within a given budget and allocating the patients to the facilities for the objective of maximizing the number of served patients while considering preference of the patients for the public and private facilities. We present an integer programming formulation for the problem and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. Results of computational experiments on a number of problem instances show that the algorithm gives good solutions in a reasonable computation time and may be effectively used by the healthcare authorities of the government.     

Valid inequalities and facets of the capacitated plant location problem

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research.     

A capacitated competitive facility location problem

We consider a mathematical model similar in a sense to competitive location problems. There are two competing parties that sequentially open their facilities aiming to “capture” customers and maximize profit. In our model, we assume that facilities’ capacities are bounded. The model is formulated as a bilevel integer mathematical program, and we study the problem of obtaining its optimal (cooperative) solution. It is shown that the problem can be reformulated as that of maximization of a pseudo-Boolean function with the number of arguments equal to the number of places available for facility opening. We propose an algorithm for calculating an upper bound for values that the function takes on subsets which are specified by partial (0, 1)-vectors.     

A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines

This paper addresses the capacitated lot-sizing problem involving the production of multiple items on unrelated parallel machines. A production plan should be determined in order to meet the forecast demand for the items, without exceeding the capacity of the machines and minimize the sum of production, setup and inventory costs. A heuristic based on the Lagrangian relaxation of the capacity constraints and subgradient optimization is proposed. Initially, the heuristic is tested on instances of the single machine problem and results are compared with heuristics from the literature. For parallel machines and small problems the heuristic performance is tested against optimal solutions, and for larger problems it is compared with the lower bound provided by the Lagrangian relaxation.     

Heuristics for the capacitated plant location model

The paper generalizes heuristics for the uncapacitated plant location model to the capacitated case. The heuristics are ADD, DROP, SHIFT, ALA (Alternate Location Allocation) and VSM (Vertex Substitution Method). The generalizations take place within an unifying framework based on elementary ADD and DROP operations.Heuristics from the literature are discussed and compared to the procedures developed in this paper.     

A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.