A tabu search approach for the minimum sum-of-squares clustering problem

In this paper, a tabu search based clustering approach called TS-Clustering is proposed to deal with the minimum sum-of-squares clustering problem. In the TS-Clustering algorithm, five improvement operations and three neighborhood modes are given. The improvement operation is used to enhance the clustering solution obtained in the process of iterations, and the neighborhood mode is used to create the neighborhood of tabu search. The superiority of the proposed method over some known clustering techniques is demonstrated for artificial and real life data sets.     

A scatter search approach to the optimum disassembly sequence problem

One of the most difficult problems faced by OR researchers in the reverse logistics field consists in determining an efficient disassembly sequence for a product at its end of life. In this paper, a scatter search (SS) metaheuristic is presented aiming to deal with the optimum disassembly sequence problem for the case of complex products with sequence-dependent disassembly costs, and assuming that only one component can be released at each time. The algorithm was tested over a set of 48 products consisting of 25, 50, 75 and 100 right-angled parallelepiped components, connected by different kinds of joints. A feasible disassembly sequence, consisting on the reverse of the assembly sequence, is always usable. Comparing by using some statistical analysis the costs of the sequence proposed by the SS algorithm with those corresponding to the reverse order, efficiency of the metaheuristic is shown up.     

New and efficient DCA based algorithms for minimum sum-of-squares clustering

The purpose of this paper is to develop new efficient approaches based on DC (Difference of Convex functions) programming and DCA (DC Algorithm) to perform clustering via minimum sum-of-squares Euclidean distance. We consider the two most widely used models for the so-called Minimum Sum-of-Squares Clustering (MSSC in short) that are a bilevel programming problem and a mixed integer program. Firstly, the mixed integer formulation of MSSC is carefully studied and is reformulated as a continuous optimization problem via a new result on exact penalty technique in DC programming. DCA is then investigated to the resulting problem. Secondly, we introduce a Gaussian kernel version of the bilevel programming formulation of MSSC, named GKMSSC. The GKMSSC problem is formulated as a DC program for which a simple and efficient DCA scheme is developed. A regularization technique is investigated for exploiting the nice effect of DC decomposition and a simple procedure for finding good starting points of DCA is developed. The proposed DCA schemes are original and very inexpensive because they amount to computing, at each iteration, the projection of points onto a simplex and/or onto a ball, and/or onto a box, which are all determined in the explicit form. Numerical results on real word datasets show the efficiency, the scalability of DCA and its great superiority with respect to k-means and kernel k-means, standard methods for clustering.     

Solving the minimum sum-of-squares clustering problem by hyperbolic smoothing and partition into boundary and gravitational regions

This article considers the minimum sum-of-squares clustering (MSSC) problem. The mathematical modeling of this problem leads to a min-sum-min formulation which, in addition to its intrinsic bi-level nature, has the significant characteristic of being strongly nondifferentiable. To overcome these difficulties, the proposed resolution method, called hyperbolic smoothing, adopts a smoothing strategy using a special C^∞ differentiable class function. The final solution is obtained by solving a sequence of low dimension differentiable unconstrained optimization subproblems which gradually approach the original problem. This paper introduces the method of partition of the set of observations into two nonoverlapping groups: “data in frontier” and “data in gravitational regions”. The resulting combination of the two methodologies for the MSSC problem has interesting properties, which drastically simplify the computational tasks.     

A hybrid scatter search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem (PTSP) is an important theoretical and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing the hybrid scatter search (HSS) by incorporating the nearest neighbor rule (NNR), threshold accepting (TA) and edge recombination (ER) crossover into a scatter search conceptual framework to solve the PTSP. A set of numerical experiments were conducted to test the validity of the HSS based on the test problems from Tang and Miller-Hooks’ study. The numerical results showed that the HSS can effectively solve the PTSP in most of the tested cases in terms of objective function value. Moreover, the results also indicated that incorporating threshold accepting into the scatter search framework can further increase the computation efficiency while maintaining solution quality. These findings show the potential of the proposed HSS in solving the large-scale PTSP.     

A multi-objective scatter search for a dynamic cell formation problem

Cellular manufacturing system—an important application of group technology (GT)—has been recognized as an effective way to enhance the productivity in a factory. Consequently, a multi-objective dynamic cell formation problem is presented in this paper, where the total cell load variation and sum of the miscellaneous costs (machine cost, inter-cell material handling cost, and machine relocation cost) are to be minimized simultaneously. Since this type of problem is NP-hard, a new multi-objective scatter search (MOSS) is designed for finding locally Pareto-optimal frontier. To demonstrate the efficiency of the proposed algorithm, MOSS is compared with two salient multi-objective genetic algorithms, i.e. SPEA-II and NSGA-II based on some comparison metrics and statistical approach. The computational results indicate the superiority of the proposed MOSS compared to these two genetic algorithms.     

改进的求解约束P-Median问题的分散搜索算法

对解决约束P-中位问题已有的分散搜索算法进行改进。通过划分中心点服务范围的新方法指派需求点以构造初始解,用基于外包矩形的局部搜索方法来提高邻域解搜索的效率,结合路径重连算法,扩展邻域解的搜索范围,来提高解的质量。实验表明此算法能够得到优化且连续的解。     

一种新的求解多维背包问题的分散算法

为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,其结果优于其他现有的方法,并获得了较好的结果。     

A multi-objective scatter search for a mixed-model assembly line sequencing problem

A mixed-model assembly line (MMAL) is a type of production line where a variety of product models similar to product characteristics are assembled. There is a set of criteria on which to judge sequences of product models in terms of the effective utilization of this line. In this paper, we consider three objectives, simultaneously: minimizing total utility work, total production rate variation, and total setup cost. A multi-objective sequencing problem and its mathematical formulation are described. Since this type of problem is NP-hard, a new multi-objective scatter search (MOSS) is designed for searching locally Pareto-optimal frontier for the problem. To validate the performance of the proposed algorithm, in terms of solution quality and diversity level, various test problems are made and the reliability of the proposed algorithm, based on some comparison metrics, is compared with three prominent multi-objective genetic algorithms, i.e. PS-NC GA, NSGA-II, and SPEA-II. The computational results show that the proposed MOSS outperforms the existing genetic algorithms, especially for the large-sized problems.     

混合分散搜索算法求解带容量约束车辆路径问题

设计一种解决带容量约束车辆路径问题的混合分散搜索算法. 在基本分散搜索的基础上, 保留参考集更新策略和组合策略的全局搜索能力. 采用随机插入法作为解的多样性产生方法, 以扩大搜索空间, 避免陷入局部最优.应用简化的变邻域搜索作为改进策略进行局部开发, 引入邻域半径减少策略提高开发效率. 对改进后的新种群实施精英保留策略, 保证算法收敛. 实验结果分析表明, 混合分散搜索算法优于所对比的算法, 寻优能力可靠.

     

A tabu search approach for the livestock collection problem

We present a problem dealing with transportation of live animals to slaughterhouses. The problem is taken from the Norwegian meat industry, and may be viewed as a vehicle routing problem extended with inventory constraints to ensure a smooth production flow at the slaughterhouse. In addition, several constraints to ensure animal welfare have to be met. These include duration limits for how long animals can stay on the vehicle as well as rules for mixing different animal categories. In this paper, we show that this real-world problem can be solved heuristically, even if it is large both in size and complexity. A tabu search based solution method for the problem is presented, and results from computational testing are given, including comparisons with manual solutions from today's planning system.     

Clustering search algorithm for the capacitated centered clustering problem

The capacitated centered clustering problem (CCCP) consists in partitioning a set of n points into p disjoint clusters with a known capacity. Each cluster is specified by a centroid. The objective is to minimize the total dissimilarity within each cluster, such that a given capacity limit of the cluster is not exceeded. This paper presents a solution procedure for the CCCP, using the hybrid metaheuristic clustering search (CS), whose main idea is to identify promising areas of the search space by generating solutions through a metaheuristic and clustering them into groups that are then further explored with local search heuristics. Computational results in test problems of the literature show that the CS found a significant number of new best-known solutions in reasonable computational times.     

A scatter search for a multi-type transshipment point location problem with multicommodity flow

In this paper, we consider a multi-type transshipment point location problem with multicommodity flow which aims at locating transshipment points (TPs) and determining the type for each open TP. As an extension of the classical two-stage capacitated facility location problem, our problem allows flows of commodities to move among TPs and does not impose restrictions on the number of TPs traversed by flows going from plants to customers. In order to obtain high-quality feasible solutions, we propose a clustering-based scatter search in which the seed solution generation, the diversification technique and the local search are designed using the clusters generated by a data mining technique, the K-means method. The computational results show that the scatter search performs efficiently over different kinds of instances. Moreover, the solution quality is also good since the average gaps to lower bounds range between 1 and 3%.     

混合模拟退火及分散搜索优化过道布置问题

针对过道布置问题的求解复杂性,提出了一种混合模拟退火及分散搜索算法。该算法通过引入模拟退火操作进一步优化参考集中的解,以提高获得全局最优解的概率。设计了包含高质量和多样性解的双层参考集,扩大了搜索范围,避免算法陷入局部最优。同时采用动态参考集更新方法,及时替换参考集中质量或多样性较差的解,加快算法的收敛速度,并改进子集产生方法,避免产生重复的解,从而提高算法的求解效率。应用所提算法对24个不同规模的测试问题进行验算与对比,结果表明所提算法的求解质量与平稳性均优于基本模拟退火算法和分散搜索算法,且较已有的4种方法更具求解优势。     

An adaptive tabu search algorithm for the capacitated clustering problem

In the Capacitated Clustering Problem, a given set of customers with distinct demands must be partitioned into p clusters with limited capacities. The objective is to find p customers, called medians, from which the sum of the distances to all other customers in the cluster is minimized. In this article, a new adaptive tabu search approach is applied to solve the problem. Initial solutions are obtained by four constructive heuristics that use weights and distances as optimization criteria. Two neighborhood generation mechanisms are used by the local search heuristic: pairwise interchange and insertion . Computational results from 20 instances found in the literature indicate that the proposed method outperforms alternative metaheuristics developed for solving this problem.     

A large neighborhood search approach for the paint shop scheduling problem

Journal of Scheduling - Minimizing the setup costs caused by color changes is one of the main concerns for paint shop scheduling in the automotive industry. Yet, finding an optimized color sequence...     

Using an enhanced scatter search algorithm for a resource-constrained project scheduling problem

The resource-constrained project scheduling problem is one of the classical problems in the field of operations research. There are many criteria to efficiently determine the desired schedule of a project. In this paper, a well-known criterion namely project’s makespan is considered. Due to the complexity of the problem, it is very difficult to obtain optimum solution for this kind of problems by means of traditional methods. Therefore, an enhanced scatter search, based on a new path relinking and two prominent permutation-based and crossover operators, is devised to solve the problem. In order to validate the performance of the proposed algorithm, in terms of solution quality, the algorithm is applied to various test problems available on the literature and the reliability of it, is compared with well-reported benchmark algorithms. The computational results reveal that the proposed algorithm has appropriate results in comparison with the existing benchmark algorithms.     

Local search optimisation applied to the minimum distance problem

In practical terms all coded electronic signals are prone to corruption during transmission but may be corrected by using error-correcting codes. The minimum distance of a code is important because it is the major parameter affecting the error-correcting performance of a code. In this paper a recent heuristic combinatorial optimisation algorithm, called ant colony optimisation (ACO), is applied to the problem of determining minimum distances of error-correcting codes.The ACO algorithm is motivated by analogy with natural phenomena, in particular, the ability of a colony of ants to ‘optimise’ their collective endeavours. In this paper the biological background for ACO is explained and its computational implementation is presented in an error-correcting code context. The particular implementation of ACO makes use of a tabu search (TS) improvement phase to give a computationally enhanced algorithm (ACOTS). Two classes of codes are then used to show that ACOTS is a useful and viable optimisation technique to investigate minimum distances of error-correcting codes.