A heuristic algorithm for constrained multi-source Weber problem – The variational inequality approach

For solving the well-known multi-source Weber problem (MWP), each iteration of the heuristic alternate location–allocation algorithm consists of a location phase and an allocation phase. The task of the location phase is to solve finitely many single-source Weber problems (SWP), which are reduced by the heuristic of nearest center reclassification for the customers in the previous allocation phase. This paper considers the more general and practical case – the MWP with constraints (CMWP). In particular, a variational inequality approach is contributed to solving the involved constrained SWP (CSWP), and thus a new heuristic algorithm for CMWP is presented. The involved CSWP in the location phases are reformulated into some linear variational inequalities, whose special structures lead to a new projection–contraction (PC) method. Global convergence of the PC method is proved under mild assumptions. The new heuristic algorithm using the PC method in the location phases approaches to the heuristic solution of CMWP efficiently, which is verified by the preliminary numerical results reported 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.     

The capacitated distribution and waste disposal problem

We study the problem of the simultaneous design of a distribution network with plants and waste disposal units, and the coordination of product flows and waste flows within this network. The objective is to minimize the sum of fixed costs for opening plants and waste disposal units, and variable costs related to product and waste flows. The problem is complicated by (i) capacity constraints on plants and waste disposal units, (ii) service requirements (i.e. production must cover total demand) and (iii) waste, arising from production, to be disposed of at waste disposal units. We discuss alternative mathematical model formulations for the two-level distribution and waste disposal problem with capacity constraints. Lower bounding and upper bounding procedures are analyzed. The bounds are shown to be quite effective when embedded in a standard branch and bound algorithm. Finally, the results of a computational study are reported.     

Two phased hybrid local search for the periodic capacitated arc routing problem

The periodic capacitated arc routing problem (PCARP) is a challenging general model with important applications. The PCARP has two hierarchical optimization objectives: a primary objective of minimizing the number of vehicles (F_v) and a secondary objective of minimizing the total cost (F_c). In this paper, we propose an effective two phased hybrid local search (HLS) algorithm for the PCARP. The first phase makes a particular effort to optimize the primary objective while the second phase seeks to further optimize both objectives by using the resulting number of vehicles of the first phase as an upper bound to prune the search space. For both phases, combined local search heuristics are devised to ensure an effective exploration of the search space. Experimental results on 63 benchmark instances demonstrate that HLS performs remarkably well both in terms of computational efficiency and solution quality. In particular, HLS discovers 44 improved best known values (new upper bounds) for the total cost objective F_c while attaining all the known optimal values regarding the objective of the number of vehicles F_v. To our knowledge, this is the first PCARP algorithm reaching such a performance. Key components of HLS are analyzed to better understand their contributions to the overall performance.     

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

LP-based approximation for uniform capacitated facility location problem

In this paper, we study uniform hard capacitated facility location problem. The standard LP for the problem is known to have an unbounded integrality gap. We present constant factor approximation by rounding a solution to the standard LP with a slight $(1+ϵ)$ violation in the capacities.Our result shows that the standard LP is not too bad.Our algorithm is simple and more efficient as compared to the strengthened LP-based true approximation that uses the inefficient ellipsoid method with a separation oracle. True approximations are also known for the problem using local search techniques that suffer from the problem of convergence. Moreover, solutions based on standard LP are easier to integrate with other LP-based algorithms.The result is also extended to give the first approximation for uniform hard capacitated $k$-facility location problem violating the capacities by a factor of $(1+ϵ)$ and breaking the barrier of 2 in capacity violation. The result violates the cardinality by a factor of $\frac{2}{1+ϵ}$.     

An effective VNS for the capacitated p-median problem

In the capacitated p-median problem (CPMP), a set of n customers is to be partitioned into p disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally.     

A heuristic for the container loading problem: A tertiary-tree-based dynamic space decomposition approach

Increasing fuel costs, post-911 security concerns, and economic globalization provide a strong incentive for container carriers to use available container space more efficiently, thereby minimizing the number of container trips and reducing socio-economic vulnerability. A heuristic algorithm based on a tertiary tree model is proposed to handle the container loading problem (CLP) with weakly heterogeneous boxes. A dynamic space decomposition method based on the tertiary tree structure is developed to partition the remaining container space after a block of homogeneous rectangular boxes is loaded into a container. This decomposition approach, together with an optimal-fitting sequencing and an inner-right-corner-occupying placement rule, permits a holistic loading strategy to pack a container. Comparative studies with existing algorithms and an illustrative example demonstrate the efficiency of this algorithm.     

A Lagrangean heuristic for the maximal covering location problem

We develop a Lagrangean heuristic for the maximal covering location problem. Upper bounds are given by a vertex addition and substitution heuristic and lower bounds are produced through a subgradient optimization algorithm. The procedure was tested in networks of up to 150 vertices. A duality gap was generally present at the end of the heuristic for the larger problems. The test problems were run in an IBM 3090-600J ‘super-computer’; the maximum computing time was kept below three minutes of CPU.     

A compromised large-scale neighborhood search heuristic for capacitated air cargo loading planning

Cost effectiveness is central to the air freight forwarders. In this work, we study how an air freight forwarder should plan its cargo loading in order to minimize the total freight cost given a limited number of rented containers. To solve the problem efficiently for practical implementation, we propose a new large-scale neighborhood search heuristic. The proposed large-scale neighborhood relaxes the subset-disjoint restriction made in the existing literature; the relaxation risks a possibility of infeasible exchanges while at the same time it avoids the potentially large amount of checking effort required to enforce the subset-disjoint restriction. An efficient procedure is then used to search for improvement in the neighborhood. We have also proposed a subproblem to address the difficulties caused by the fixed charges. The compromised large-scale neighborhood (CLSN) search heuristic has shown stably superior performance when compared with the traditional large-scale neighborhood search and the mixed integer programming model.     

A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem

Research in the domain of examination timetabling is moving towards developing methods that generalise well over a range of problems. This is achieved by implementing hyper-heuristic systems to find the best heuristic or heuristic combination to allocate examinations when constructing a timetable for a problem. Heuristic combinations usually take the form of a list of low-level heuristics that are applied sequentially. This study proposes an alternative representation for heuristic combinations, namely, a hierarchical combination of heuristics. Furthermore, the heuristics in each combination are applied simultaneously rather than sequentially. The study also introduces a new low-level heuristic, namely, highest cost. A set of heuristic combinations of this format have been tested on the 13 Carter benchmarks. The quality of the examination timetables induced using these combinations are comparable to, and in some cases better than, those produced by hyper-heuristic systems combining and applying heuristic combinations sequentially.     

A heuristic procedure for solving the dynamic probabilistic project expediting problem

Because of activity duration uncertainties, large-scale projects can often be modeled most realistically as probabilistic activity networks. The complex interactions among activities with uncertain durations virtually assures a low probability that these projects will be completed before predetermined due dates. As a result, it is often necessary to expedite individual activities in these projects to improve due date performance. This research introduces a dynamically applied matrix simulation approach for selecting expediting options in order to control the probability of successful project completion before predefined due dates. Experiments are conducted to demonstrate the ability of this new approach to generate quality alternatives and efficiently evaluate large-scale projects.     

A heuristic lagrangean algorithm for the capacitated plant location problem

Lagrangean techniques have been widely applied to the uncapacitated plant location problem, and in some cases they have proven to be successfull even when capacitated problems with additional constraints are taken into account. In our paper we study the application of these techniques to the capacitated plant location problem when the model considered is a pure integer one. Several lagrangean decompositions are considered and for some of them heuristic algorithms have been designed to solve the resulting lagrangean subproblems, the heuristics consisting of a two phase procedure. The first (location phase) defines a set of multipliers from the analysis of the dual LP relaxation, and makes a choice of the plants considering the resulting subproblems as a particular case of the general assignment problems. Several heuristics have been studied for this second phase, based either on a decomposition of knapsack type subproblems through a definition of a set of penalties, or of looking into the duality gap and trying to reduce it. Computational experience is reported.     

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 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 distance-based point-reassignment heuristic for the k-hyperplane clustering problem

We consider the k-Hyperplane Clustering problem where, given a set of m   points in Rⁿ${\mathbb{R}}^n$, we have to partition the set into k subsets (clusters) and determine a hyperplane for each of them, so as to minimize the sum of the squares of the Euclidean distances between the points and the hyperplane of the corresponding clusters. We give a nonconvex mixed-integer quadratically constrained quadratic programming formulation for the problem. Since even very small-size instances are challenging for state-of-the-art spatial branch-and-bound solvers like Couenne, we propose a heuristic in which many “critical” points are reassigned at each iteration. Such points, which are likely to be ill-assigned in the current solution, are identified using a distance-based criterion and their number is progressively decreased to zero. Our algorithm outperforms the best available one proposed by Bradley and Mangasarian on a set of real-world and structured randomly generated instances. For the largest instances, we obtain an average improvement in the solution quality of 54%.     

A model for the capacitated,hop-constrained,per-packet wireless mesh network design problem

Three critical factors in wireless mesh network design are the number of hops between supply and demand points, the bandwidth capacity of the transport media, and the technique used to route packets within the network. Most previous research on network design has focused on the issue of hop constraints and/or bandwidth capacity in wired networks while assuming a per-flow routing scheme. However, networks that employ per-packet routing schemes in wireless networks involve different design issues that are unique to this type of problem. We present a methodology for designing wireless mesh networks that consider bandwidth capacity, hop constraints, and profitability for networks employing a per-packet routing system.     

An exact algorithm for solving a capacitated location-routing problem

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem in which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints, generalized subtour elimination constraints, and chain barring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations.