Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

In the capacitated p-median problem with single source constraint, also known as the capacitated clustering problem, a given set of n weighted points is to be partitioned into p clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centres that minimizes the total scatter of points allocated to these clusters. In this paper, a (λ, μ)-interchange neighbourhood based on the concept of λ-interchange of points restricted to μ-adjacent clusters is proposed. Structural properties of centres are identified and exploited to derive special data structures for their efficient evaluations. Different search and selection strategies including the variable neighbourhood search descent with respect to μ-nearest points are investigated. The most efficient strategies are then embedded in a guided construction search metaheuristic framework based either on a periodic local search procedure or a greedy random adaptive search procedure to solve the problem. Computational experience is reported on a standard set of benchmarks. The computational experience demonstrates the competitive performance of the proposed algorithms when compared to the best-known procedures in the literature in terms of solution quality and computational requirement.     

Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation

Hub and spoke type networks are often designed to solve problems that require the transfer of large quantities of commodities. This can be an extremely difficult problem to solve for constructive approaches such as ant colony optimisation due to the multiple optimisation components and the fact that the quadratic nature of the objective function makes it difficult to determine the effect of adding a particular solution component. Additionally, the amount of traffic that can be routed through each hub is constrained and the number of hubs is not known a-priori. Four variations of the ant colony optimisation meta-heuristic that explore different construction modelling choices are developed. The effects of solution component assignment order and the form of local search heuristics are also investigated. The results reveal that each of the approaches can return optimal solution costs in a reasonable amount of computational time. This may be largely attributed to the combination of integer linear preprocessing, powerful multiple neighbourhood local search heuristic and the good starting solutions provided by the ant colonies.     

The directional p-median problem: Definition,complexity, and algorithms

An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. p-Median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this paper, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the assigned supply point for a given demand point to lie above and to the right of it. In a previous work, we showed that the directional p-median problem is polynomially solvable in one dimension; we give here an improved solution through reformulating the problem as a special case of the constrained shortest path problem. We have previously proven that the problem is NP-complete in two or more dimensions; we present here an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for real-world applications with thousands of demand points.     

Density Based Problem Space Search for the Capacitated Clustering p-Median Problem

In the Capacitated Clustering Problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises total scatter of points allocated to them. In this paper a new constructive method, a general framework to improve the performance of greedy constructive heuristics, and a problem space search procedure for the CCP are proposed. The constructive heuristic finds patterns of natural subgrouping in the input data using concept of density of points. Elements of adaptive computation and periodic construction–deconstruction concepts are implemented within the constructive heuristic to develop a general framework for building efficient heuristics. The problem-space search procedure is based on perturbations of input data for which a controlled perturbation strategy, intensification and diversification strategies are developed. The implemented algorithms are compared with existing methods on a standard set of bench-marks and on new sets of large-sized instances. The results illustrate the strengths of our algorithms in terms of solution quality and computational efficiency.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

Lagrangean duals and exact solution to the capacitated p-center problem

In this work, we address the capacitated p-center problem (CpCP). We study two auxiliary problems, discuss their relation to CpCP, and analyze the lower bounds obtained with two different Lagrangean duals based on each of these auxiliary problems. We also compare two different strategies for solving exactly CpCP, based on binary search and sequential search, respectively. Various data sets from the literature have been used for evaluating the performance of the proposed algorithms.     

Heuristics for multiple facility location in a network using the variance criterion

In cyclic networks the p-variance location problem is NP-hard, and therefore it is suitable to use heuristic methods to find approximate solutions to the problem. To this end, two strategies are explored, the first using combinatorial search procedures over the vertex set, whereas the second searches for the solution over the entire network. The initial vertex set solutions are generated by using tabu search, variable neighbourhood search and interchange procedures. The heuristics have been tested on instances of up to 30 vertices and 70 edges, and their performances compared.     

Improvement heuristic for the flow-shop scheduling problem: An adaptive-learning approach

We propose an improvement-heuristic approach for the general flow-shop problem (n/m/C_max) based on the idea of adaptive learning. The approach employs a one-pass heuristic to give a good starting solution in the search space and uses a weight parameter to perturb the data of the original problem to obtain improved solutions. The weights are then adjusted employing a learning strategy which involves reinforcement and backtracking. The learning is similar to that in neural networks. The random perturbation allows a non-deterministic local search. We apply the improvement-heuristic approach in conjunction with three well-known heuristics in the literature, namely, Palmer’s Slope Index, CDS and NEH. We test our approach on several benchmark problem sets including Taillard’s, Carlier’s, Heller’s and Reeves’. We compare our results to the best-known upper-bound solutions and find that for many problems we match the best-known upper bound. For one problem we discover a new upper bound.     

A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem

We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman’s tour and designing the optimal travelling salesman’s tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.     

Comparing branch-and-price algorithms for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity k-splittable Maximum Flow Problem consists in routing as much flow as possible through a capacitated network such that each commodity uses at most k paths and the capacities are satisfied. The problem appears in telecommunications, specifically when considering Multi-Protocol Label Switching. The problem has previously been solved to optimality through branch-and-price. In this paper we propose two exact solution methods both based on an alternative decomposition. The two methods differ in their branching strategy. The first method, which branches on forbidden edge sequences, shows some performance difficulty due to large search trees. The second method, which branches on forbidden and forced edge sequences, demonstrates much better performance. The latter also outperforms a leading exact solution method from the literature. Furthermore, a heuristic algorithm is presented. The heuristic is fast and yields good solution values.     

Heuristics for a coupled-operation scheduling problem

In this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimize the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n²) complexity for each permutation. Several heuristic algorithms are proposed: a deterministic and randomized construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well.     

The double travelling salesman problem with multiple stacks – Formulation and heuristic solution approaches

This paper introduces the double travelling salesman problem with multiple stacks and presents four different metaheuristic approaches to its solution. The double TSP with multiple stacks is concerned with determining the shortest route performing pickups and deliveries in two separated networks (one for pickups and one for deliveries) using only one container. Repacking is not allowed, instead each item can be positioned in one of several rows in the container, such that each row can be considered a LIFO (last in, first out) stack, but no mutual constraints exist between the rows. Two different neighbourhood structures are developed for the problem and used with each of three local search metaheuristics. Additionally some simpler removal and reinsertion operators are used in a Large neighbourhood search framework. Finally some computational results are given along with lower bounds on the objective value.     

Greedy random adaptive memory programming search for the capacitated clustering problem

In the capacitated clustering problem (CCP), a given set of n weighted points is to be partitioned into p clusters such that, the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centers that minimises the total scatter of points allocated to these centers. In this paper, we propose a merger of Greedy Random Adaptive Search Procedure (GRASP) and Adaptive Memory Programming (AMP) into a new GRAMPS framework for the CCP. A learning process is kept in charge of tracking information on the best components in an elite set of GRAMPS solutions. The information are strategically combined with problem-domain data to restart the construction search phase. At early stage of constructions, priorities are given to problem-domain data and progressively shifted towards generated information as the learning increases. GRAMPS is implemented with an efficient local search descent based on a restricted λ-interchange neighbourhood. Extensive experiments are reported on on a standard set of bench-marks from the literature and on a new set of large instances. The results show that GRAMPS has an efficient learning mechanism and is competitive with the existing methods in the literature.     

Efficient solution of large scale,single-source,capacitated plant location problems

The single-source, capacitated plant location problem is considered. This problem differs from the capacitated plant location problem by the additional requirement that each customer must be supplied with all its demand from a single plant. An efficient heuristic solution, capable of solving large problem instances, is presented. The heuristic combines Lagrangian relaxation with restricted neighbourhood search. Computational experiments on two sets of problem instances are presented.     

J-means and I-means for minimum sum-of-squares clustering on networks

Given a graph, the Edge minimum sum-of-squares clustering problem requires finding p prototypes (cluster centres) by minimizing the sum of their squared distances from a set of vertices to their nearest prototype, where a prototype can be either a vertex or an inner point of an edge. In this paper we have implemented Variable neighborhood search based heuristic for solving it. We consider three different local search procedures, K-means, J-means, and a new I-means heuristic. Experimental results indicate that the implemented VNS-based heuristic produces the best known results in the literature.     

A variable selection method based on Tabu search for logistic regression models

A Tabu search method is proposed and analysed for selecting variables that are subsequently used in Logistic Regression Models. The aim is to find from among a set of m variables a smaller subset which enables the efficient classification of cases. Reducing dimensionality has some very well-known advantages that are summarized in literature. The specific problem consists in finding, for a small integer value of p, a subset of size p of the original set of variables that yields the greatest percentage of hits in Logistic Regression. The proposed Tabu search method performs a deep search in the solution space that alternates between a basic phase (that uses simple moves) and a diversification phase (to explore regions not previously visited). Testing shows that it obtains significantly better results than the Stepwise, Backward or Forward methods used by classic statistical packages. Some results of applying these methods are presented.     

An optimization model for trim loss minimization in an automotive glass plant

This paper deals with glass cutting in an Italian plant producing parts for the automotive market. Glass cutting is basically organised in two phases: first, large rectangular sheets of the same type are obtained from a ribbon of flat glass and sent to warehouse; then, sheets of various types are taken from the warehouse and cut into small rectangular parts of various sizes according to demand. In both phases, trim loss is generated. A problem then arises of fulfilling the demand of small parts using a limited assortment of large sheets and minimizing the total trim loss. In this paper we describe a heuristic algorithm based on a p-median model with additional constraints that take into account all the relevant shop floor requirements. A computational study conducted on real instances provided by the plant is presented and discussed.     

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

Lagrangian relaxation guided problem space search heuristics for generalized assignment problems

We develop and test a heuristic based on Lagrangian relaxation and problem space search to solve the generalized assignment problem (GAP). The heuristic combines the iterative search capability of subgradient optimization used to solve the Lagrangian relaxation of the GAP formulation and the perturbation scheme of problem space search to obtain high-quality solutions to the GAP. We test the heuristic using different upper bound generation routines developed within the overall mechanism. Using the existing problem data sets of various levels of difficulty and sizes, including the challenging largest instances, we observe that the heuristic with a specific version of the upper bound routine works well on most of the benchmark instances known and provides high-quality solutions quickly. An advantage of the approach is its generic nature, simplicity, and implementation flexibility.