A hybrid data mining GRASP with path-relinking

The exploration of hybrid metaheuristics—combination of metaheuristics with concepts and processes from other research areas—has been an important trend in combinatorial optimization research. An instance of this study is the hybrid version of the GRASP metaheuristic that incorporates a data mining process. Traditional GRASP is an iterative metaheuristic which returns the best solution reached over all iterations. In the hybrid GRASP proposal, after executing a significant number of iterations, the data mining process extracts patterns from an elite set of sub-optimal solutions for the optimization problem. These patterns present characteristics of near optimal solutions and can be used to guide the following GRASP iterations in the search through the combinatorial solution space. The hybrid data mining GRASP has been successfully applied for different combinatorial problems: the set packing problem, the maximum diversity problem, the server replication for reliable multicast problem and the p-median problem. In this work, we show that, not only the traditional GRASP, but also GRASP improved with the path-relinking heuristic—a memory-based intensification strategy—could benefit from exploring a data mining procedure. Computational experiments, comparing traditional GRASP with path-relinking and different path-relinking hybrid proposals, showed that employing the combination of path-relinking and data mining made the GRASP find better results in less computational time. Another contribution of this work is the application of the path-relinking hybrid proposal for the 2-path network design problem, which improved the state-of-the-art solutions for this problem.     

A GRASP with evolutionary path relinking for the truck and trailer routing problem

In the truck and trailer routing problem (TTRP) a heterogeneous fleet composed of trucks and trailers has to serve a set of customers, some only accessible by truck and others accessible with a truck pulling a trailer. This problem is solved using a route-first, cluster-second procedure embedded within a hybrid metaheuristic based on a greedy randomized adaptive search procedure (GRASP), a variable neighborhood search (VNS) and a path relinking (PR). We test PR as a post-optimization procedure, as an intensification mechanism, and within evolutionary path relinking (EvPR). Numerical experiments show that all the variants of the proposed GRASP with path relinking outperform all previously published methods. Remarkably, GRASP with EvPR obtains average gaps to best-known solutions of less than 1% and provides several new best solutions.     

Probabilistic stopping rules for GRASP heuristics and extensions

The main drawback of most metaheuristics is the absence of effective stopping criteria. Most implementations of such algorithms stop after performing a given maximum number of iterations or a given maximum number of consecutive iterations without improvement in the best‐known solution value, or after the stabilization of the set of elite solutions found along the search. We propose effective probabilistic stopping rules for randomized metaheuristics such as GRASP (Greedy Randomized Adaptive Search Procedures). We show how the probability density function of the solution values obtained along the iterations of such algorithms can be used to implement stopping rules based on the tradeoff between solution quality and the time needed to find a solution that might improve the best solution found. We show experimentally that, in the particular case of GRASP heuristics, the solution values obtained along its iterations fit a normal distribution that may be used to give an online estimation of the number of solutions obtained in forthcoming iterations that might be at least as good as the incumbent. This estimation is used to validate the stopping rule based on the tradeoff between solution quality and the time needed to find a solution that might improve the incumbent. The robustness of this strategy is illustrated and validated by a thorough computational study reporting results obtained with GRASP implementations to four different combinatorial optimization problems.     

Finding weaknesses in networks using Greedy Randomized Adaptive Search Procedure and Path Relinking

In recent years, the relevance of cybersecurity has been increasingly evident to companies and institutions, as well as to final users. Because of that, it is important to ensure the robustness of a network. With the aim of improving the security of the network, it is desirable to find out which are the most critical nodes in order to protect them from external attackers. This work tackles this problem, named the α-separator problem, from a heuristic perspective, proposing an algorithm based on the Greedy Randomized Adaptive Search Procedure (GRASP). In particular, a novel approach for the constructive procedure is proposed, where centrality metrics derived from social network analysis are used as a greedy criterion. Furthermore, the quality of the provided solutions is improved by means of a combination method based on Path Relinking (PR). This work explores different variants of PR, also adapting the most recent one, Exterior PR, for the problem under consideration. The combination of GRASP + PR allows the algorithm to obtain high-quality solutions within a reasonable computing time. The proposal is supported by a set of intensive computational experiments that show the quality of the proposal, comparing it with the most competitive algorithm found in the state of art.     

A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem

Given a graph with its vertex set partitioned into a set of groups, nonnegative costs associated to its edges, and nonnegative prizes associated to its vertices, the prize‐collecting generalized minimum spanning tree problem consists in finding a subtree of this graph that spans exactly one vertex of each group and minimizes the sum of the costs of the edges of the tree less the prizes of the selected vertices. It is a generalization of the NP‐hard generalized minimum spanning tree optimization problem. We propose a GRASP (greedy randomized adaptive search procedure) heuristic for its approximate solution, incorporating path‐relinking for search intensification and a restart strategy for search diversification. The hybridization of the GRASP with path‐relinking and restarts heuristic with a data mining strategy that is applied along with the GRASP iterations, after the elite set is modified and becomes stable, contributes to making the heuristic more robust. The computational experiments show that the heuristic developed in this work found very good solutions for test problems with up to 439 vertices. All input data for the test instances and detailed numerical results are made available from Mendeley Data.     

GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem

In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the “exterior form” of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. Our computational experiments show the superiority of this approach compared with the previous best method for MDTWNP and with alternative methods for this problem that use other forms of PR.     

求解多车型校车路径问题的带参数选择机制的GRASP算法

考虑到校车路径安排过程中不同车型容量和成本的差异,建立了多车型校车路径问题(SBRP)模型,并提出了一种带参数选择机制的贪婪随机自适应(GRASP)算法进行求解。在初始解构造阶段,设计一组阈值参数控制受限候选列表(RCL)的大小,使用轮盘赌法选择阈值参数。完成初始解构造后,使用可变邻域搜索(VNS)进行邻域解改进,并记录所选择的参数和解的目标值。算法迭代过程中,先设置相同阈值参数的选择概率,每隔若干次迭代后,评估每个阈值参数的性能并修改其选择概率,使得算法能够得到更好的平均解。使用基准测试案例进行了测试,比较了基本GRASP算法与设计的GRASP算法的性能,并与现有求解多车型校车路径问题的算法进行对比,实验结果表明所设计的算法是有效的。     

Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem

The quadratic multiple knapsack problem (QMKP) concerns assigning a set of objects, which interact among themselves through paired profit values, to a set of capacity-constrained knapsacks such that the overall profit of the objects included in the knapsacks is maximized and the total weight of the objects in each knapsack does not exceed the capacity of the knapsack. In this paper we present a highly effective tabu search (TS) approach for QMKP that incorporates a hybridization scheme combining both feasible and infeasible local searches. The feasible local search focuses its search on the most relevant feasible solutions, while the infeasible local search explores a large search space composed of both feasible and infeasible solutions, and employs several tailored move selection rules to keep the infeasible solutions close to the feasible regions located in promising areas. Extensive computational results on a set of 60 benchmark instances in the literature illustrate that the new TS approach compares very favorably with the current state-of-the-art solution methods for QMKP. In particular, the TS approach finds improved best solutions for ten instances. We also analyze the hybridization scheme in the TS approach to ascertain its effect on the performance of the solution method.     

A hybrid Lagrangean heuristic with GRASP and path-relinking for set k-covering

The set multicovering or set k-covering problem is an extension of the classical set covering problem, in which each object is required to be covered at least k times. The problem finds applications in the design of communication networks and in computational biology. We describe a GRASP with path-relinking heuristic for the set k-covering problem, as well as the template of a family of Lagrangean heuristics. The hybrid GRASP Lagrangean heuristic employs the GRASP with path-relinking heuristic using modified costs to obtain approximate solutions for the original problem. Computational experiments carried out on 135 test instances show experimentally that the Lagrangean heuristics performed consistently better than GRASP as well as GRASP with path-relinking. By properly tuning the parameters of the GRASP Lagrangean heuristic, it is possible to obtain a good trade-off between solution quality and running times. Furthermore, the GRASP Lagrangean heuristic makes better use of the dual information provided by subgradient optimization and is able to discover better solutions and to escape from locally optimal solutions even after the stabilization of the lower bounds, when other Lagrangean strategies fail to find new improving solutions.     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.