A GRASP heuristic using path‐relinking and restarts for the Steiner traveling salesman problem

The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization. Given a set of nodes and the distances between them, it consists in finding the shortest route that visits each node exactly once and returns to the first. Nevertheless, more flexible and applicable formulations of this problem exist and can be considered. The Steiner TSP (STSP) is a variant of the TSP that assumes that only a given subset of nodes must be visited by the shortest route, eventually visiting some nodes and edges more than once. In this paper, we adapt some classical TSP constructive heuristics and neighborhood structures to the STSP variant. In particular, we propose a reduced 2‐opt neighborhood and we show that it leads to better results in smaller computation times. Computational results with an implementation of a GRASP heuristic using path‐relinking and restarts are reported. In addition, ten large test instances are generated. All instances and their best‐known solutions are made available for download and benchmarking purposes.     

Savings based ant colony optimization for the capacitated minimum spanning tree problem

The problem of connecting a set of client nodes with known demands to a root node through a minimum cost tree network, subject to capacity constraints on all links is known as the capacitated minimum spanning tree (CMST) problem. As the problem is NP-hard, we propose a hybrid ant colony optimization (ACO) algorithm to tackle it heuristically. The algorithm exploits two important problem characteristics: (i) the CMST problem is closely related to the capacitated vehicle routing problem (CVRP), and (ii) given a clustering of client nodes that satisfies capacity constraints, the solution is to find a MST for each cluster, which can be done exactly in polynomial time. Our ACO exploits these two characteristics of the CMST by a solution construction originally developed for the CVRP. Given the CVRP solution, we then apply an implementation of Prim's algorithm to each cluster to obtain a feasible CMST solution. Results from a comprehensive computational study indicate the efficiency and effectiveness of the proposed approach.     

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.     

A hybrid column generation with GRASP and path relinking for the network load balancing problem

In this paper, a hybrid meta-heuristic is proposed which combines the GRASP with path relinking method and Column Generation. The key idea of this method is to run a GRASP with path relinking search on a restricted search space, defined by Column Generation, instead of running the search on the complete search space of the problem. Moreover, column generation is used not only to compute the initial restricted search space but also to modify it during the whole algorithm. The proposed heuristic is used to solve the network load balancing problem: given a capacitated telecommunications network with single path routing and an estimated traffic demand matrix, the network load balancing problem is the determination of a routing path for each traffic commodity such that the network load balancing is optimized, i.e., the worst link load is minimized, among all such solutions, the second worst link load is minimized, and continuing in this way until all link loads are minimized. The computational results presented in this paper show that, for the network load balancing problem, the proposed heuristic is effective in obtaining better quality solutions in shorter running times.     

Rough‐fuzzy quadratic minimum spanning tree problem

A quadratic minimum spanning tree problem determines a minimum spanning tree of a network whose edges are associated with linear and quadratic weights. Linear weights represent the edge costs whereas the quadratic weights are the interaction costs between a pair of edges of the graph. In this study, a bi‐objective rough‐fuzzy quadratic minimum spanning tree problem has been proposed for a connected graph, where the linear and the quadratic weights are represented as rough‐fuzzy variables. The proposed model is formulated by using rough‐fuzzy chance‐constrained programming technique. Subsequently, three related theorems are also proposed for the crisp transformation of the proposed model. The crisp equivalent models are solved with a classical multi‐objective solution technique, the epsilon‐constraint method and two multi‐objective evolutionary algorithms: (a) nondominated sorting genetic algorithm II (NSGA‐II) and (b) multi‐objective cross‐generational elitist selection, heterogeneous recombination, and cataclysmic mutation (MOCHC) algorithm. A numerical example is provided to illustrate the proposed model when solved with different methodologies. A sensitivity analysis of the example is also performed at different confidence levels. The performance of NSGA‐II and MOCHC are analysed on five randomly generated instances of the proposed model. Finally, a numerical illustration of an application of the proposed model is also presented in this study.     

Improved heuristics for the bounded-diameter minimum spanning tree problem

Given an undirected, connected, weighted graph and a positive integer k, the bounded-diameter minimum spanning tree (BDMST) problem seeks a spanning tree of the graph with smallest weight, among all spanning trees of the graph, which contain no path with more than k edges. In general, this problem is NP-Hard for 4 ≤ k < n − 1, where n is the number of vertices in the graph. This work is an improvement over two existing greedy heuristics, called randomized greedy heuristic (RGH) and centre-based tree construction heuristic (CBTC), and a permutation-coded evolutionary algorithm for the BDMST problem. We have proposed two improvements in RGH/CBTC. The first improvement iteratively tries to modify the bounded-diameter spanning tree obtained by RGH/CBTC so as to reduce its cost, whereas the second improves the speed. We have modified the crossover and mutation operators and the decoder used in permutation-coded evolutionary algorithm so as to improve its performance. Computational results show the effectiveness of our approaches. Our approaches obtained better quality solutions in a much shorter time on all test problem instances considered.     

A swarm intelligence approach to the quadratic minimum spanning tree problem

The quadratic minimum spanning tree problem (Q-MST) is an extension of the minimum spanning tree problem (MST). In Q-MST, in addition to edge costs, costs are also associated with ordered pairs of distinct edges and one has to find a spanning tree that minimizes the sumtotal of the costs of individual edges present in the spanning tree and the costs of the ordered pairs containing only edges present in the spanning tree. Though MST can be solved in polynomial time, Q-MST is NP-Hard. In this paper we present an artificial bee colony (ABC) algorithm to solve Q-MST. The ABC algorithm is a new swarm intelligence approach inspired by intelligent foraging behavior of honey bees. Computational results show the effectiveness of our approach.     

A filter-and-fan algorithm for the capacitated minimum spanning tree problem

The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new CMST heuristic algorithm that effectively combines the classical node-based and tree-based neighborhoods embodied in a filter-and-fan (F&F) approach, a local search procedure that generates compound moves in a tree search fashion. The overall algorithm is guided by a multi-level oscillation strategy used to trigger each type of neighborhood while allowing the search to cross feasibility boundaries. Computational results carried out on a standard set of 135 benchmark problems show that a simple F&F design competes effectively with prior CMST metaheuristics, rivaling the best methods, which are significantly more complex.     

Enhanced second order algorithm applied to the capacitated minimum spanning tree problem

Given a centralized undirected graph with costs associated with its edges, the capacitated minimum spanning tree problem is to find a minimum cost spanning tree of the given graph, subject to a capacity constraint in all subtrees incident in the central node. As the problem is NP-hard, we propose an enhanced version of the well-known second order algorithm, described in [Karnaugh M. A new class of algorithms for multipoint network optimization. IEEE Transactions on Communications 1976;COM-24:500–5.]. The original version of this algorithm is based on a look-ahead strategy, used for a tentative inclusion of a constraint to the problem, performed in each iteration. In the new enhanced version, we propose the inclusion of look-behind steps, which can be seen as the reverse of the look-ahead procedure. Therefore and using some memory features, the method can continue even when facing the traditional stopping criterion of the original algorithm. Computational experiments showing the effectiveness of the new method on benchmark instances are reported.     

Modeling and solving the rooted distance-constrained minimum spanning tree problem

In this paper we discuss models and methods for solving the rooted distance constrained minimum spanning tree problem which is defined as follows: given a graph G=(V,E)$G=(V,E)$ with node set V={0,1,…,n}$V=\{0,1,\dots ,n\}$ and edge set E$E$, two integer weights, a cost _ce$c_e$ and a delay _we$w_e$ associated with each edge e$e$ of E$E$, and a natural (time limit) number H$H$, we wish to find a spanning tree T$T$ of the graph with minimum total cost and such that the unique path from a specified root node, node 0, to any other node has total delay not greater than H$H$. This problem generalizes the well known hop-constrained spanning tree problem and arises in the design of centralized networks with quality of service constraints and also in package shipment with service guarantee constraints. We present three theoretically equivalent modeling approaches, a column generation scheme, a Lagrangian relaxation combined with subgradient optimization procedure, both based on a path formulation of the problem, and a shortest path (compact) reformulation of the problem which views the underlying subproblem as defined in a layered extended graph. We present results for complete graph instances with up to 40 nodes. Our results indicate that the layered graph path reformulation model is still quite good when the arc weights are reasonably small. Lagrangian relaxation combined with subgradient optimization procedure appears to work much better than column generation and seems to be a quite reasonable approach to the problem for large weight, and even small weight, instances.     

A biased random-key genetic algorithm for the capacitated minimum spanning tree problem

This paper focuses on the capacitated minimum spanning tree (CMST) problem. Given a central processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals, the goal is to design a minimum cost network to carry this demand. Potential links exist between any pair of terminals and between the central processor and the terminals. Each potential link can be included in the design at a given cost. The CMST problem is to design a minimum-cost network connecting the terminals with the central processor so that the flow on any arc of the network is at most Q. A biased random-key genetic algorithm (BRKGA) is a metaheuristic for combinatorial optimization which evolves a population of random vectors that encode solutions to the combinatorial optimization problem. This paper explores several solution encodings as well as different strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem. Computational experiments are presented showing the effectiveness of the approach: Seven new best-known solutions are presented for the set of benchmark instances used in the experiments.     

Min‐degree constrained minimum spanning tree problem: complexity,properties, and formulations

This paper addresses a new combinatorial problem, the Min‐Degree Constrained Minimum Spanning Tree (md‐MST), that can be stated as: given a weighted undirected graph with positive costs on the edges and a node‐degrees function , the md‐MST is to find a minimum cost spanning tree T of G, where each node i of T either has at least a degree of or is a leaf node. This problem is closely related to the well‐known Degree Constrained Minimum Spanning Tree (d‐MST) problem, where the degree constraint is an upper bound instead. The general NP‐hardness for the md‐MST is established and some properties related to the feasibility of the solutions for this problem are presented, in particular we prove some bounds on the number of internal and leaf nodes. Flow‐based formulations are proposed and computational experiments involving the associated Linear Programming (LP) relaxations are presented.     

A GRASP with path-relinking heuristic for the survivable IP/MPLS-over-WSON multi-layer network optimization problem

In this paper we deal with the survivable internet protocol (IP)/multi-protocol label switching (MPLS)-over-wavelength switched optical network (WSON) multi-layer network optimization problem (SIMNO). This problem entails planning an IP/MPLS network layer over a photonic mesh infrastructure whilst, at the same time, ensuring the highest availability of services and minimizing the capital expenditures (CAPEX) investments. Such a problem is currently identified as an open issue among network operators, and hence, its solution is of great interest. To tackle SIMNO, we first provide an integer linear programming (ILP) formulation which provides an insight into the complexity of its managing. Then, a greedy randomized adaptive search procedure (GRASP) with path-relinking (PR) together with a biased random-key genetic algorithm (BRKGA) are specifically developed to help solve the problem. The performance of both heuristics is exhaustively tested and compared making use of various network and traffic instances. Numerical experiments show the benefits of using GRASP instead of BRKGA when dealing with highly complex network scenarios. Moreover, we verified that the use of GRASP with PR remarkably improves the basic GRASP algorithm, particularly in real-sized, complex scenarios such as those proposed in this paper.     

Comparison of metaheuristics for the k‐labeled spanning forest problem

In this paper, we study the k‐labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer‐positive value are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP‐hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high‐quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high‐quality performance and completely automate the resulting optimization strategy.     

A new hybrid parallel genetic algorithm for the job‐shop scheduling problem

The job‐shop scheduling problem (JSSP) is considered one of the most difficult NP‐hard problems. Numerous studies in the past have shown that as exact methods for the problem solution are intractable, even for small problem sizes, efficient heuristic algorithms must achieve a good balance between the well‐known themes of exploitation and exploration of the vast search space. In this paper, we propose a new hybrid parallel genetic algorithm with specialized crossover and mutation operators utilizing path‐relinking concepts from combinatorial optimization approaches and tabu search in particular. The new scheme relies also on the recently introduced concepts of solution backbones for the JSSP in order to intensify the search in promising regions. We compare the resulting algorithm with a number of state‐of‐the‐art approaches for the JSSP on a number of well‐known test‐beds; the results indicate that our proposed genetic algorithm compares fairly well with some of the best‐performing genetic algorithms for the problem.     

A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem

The two-echelon location-routing problem (LRP-2E) is raised by the design of transportation networks with two types of trips: first-level trips serving from one main depot a set of satellite depots, to be located, and second-level trips supplying customers from these satellites. In the proposed multi-start iterated local search (MS-ILS), three greedy randomized heuristics are used cyclically to get initial solutions. Each ILS run alternates between two search spaces: LRP-2E solutions, and travelling salesman (TSP) tours covering the main depot and the customers. The number of iterations allotted to a run is reduced whenever a known solution (stored in a tabu list) is revisited. MS-ILS can be reinforced by a path-relinking procedure (PR), used internally for intensification, as post-optimization, or both. On two sets with 24 and 30 LRP-2E instances, MS-ILS outperforms on average two GRASP algorithms and adding PR brings a further improvement. Our metaheuristic also surpasses a tabu search on 30 instances for a more general problem with several main depots. It is still effective on a particular case, the capacitated location-routing problem (CLRP): In a comparison with four published metaheuristics, only one (LRGTS, Prins et al., 2007) does better.     

Using iterated local search for solving the flow‐shop problem: Parallelization,parametrization, and randomization issues

Iterated local search (ILS) is a powerful framework for developing efficient algorithms for the permutation flow‐shop problem (PFSP). These algorithms are relatively simple to implement and use very few parameters, which facilitates the associated fine‐tuning process. Therefore, they constitute an attractive solution for real‐life applications. In this paper, we discuss some parallelization, parametrization, and randomization issues related to ILS‐based algorithms for solving the PFSP. In particular, the following research questions are analyzed: (a) Is it possible to simplify even more the parameter setting in an ILS framework without affecting performance? (b) How do parallelized versions of these algorithms behave as we simultaneously vary the number of different runs and the computation time? (c) For a parallelized version of these algorithms, is it worthwhile to randomize the initial solution so that different starting points are considered? (d) Are these algorithms affected by the use of a “good‐quality” pseudorandom number generator? In this paper, we introduce the new ILS‐ESP (where ESP is efficient, simple, and parallelizable) algorithm that is specifically designed to take advantage of parallel computing, allowing us to obtain competitive results in “real time” for all tested instances. The ILS‐ESP also uses “natural” parameters, which simplifies the calibration process. An extensive set of computational experiments has been carried out in order to answer the aforementioned research questions.     

A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem

The set k‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLL_ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL_ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL_ccsm performs better than its competitors in terms of solution quality in most classical instances.