Variable Neighborhood Search

Given a set of n data objects and their pairwise dissimilarities, the goal of quartet clustering is to construct an optimal tree from the total number of possible combinations of quartet topologies on n, where optimality means that the sum of the dissimilarities of the embedded (or consistent) quartet topologies is minimal. This corresponds to an NP-hard combinatorial optimization problem, also referred to as minimum quartet tree cost (MQTC) problem. We provide details and formulation of this challenging problem, and propose a basic greedy heuristic that is characterized by a very high speed and some interesting implementation details. The solution approach, though simple, substantially improves the performance of a Reduced Variable Neighborhood Search for the MQTC problem. The latter is one of the most popular heuristic algorithms for tackling the MQTC problem.

Clustering is an automated and powerful technique for data analysis. It aims to divide a given set of data points into clusters which are homogeneous and/or well separated. A major challenge with clustering is to define an appropriate clustering criterion that can express a good separation of data into homogeneous groups such that the obtained clustering solution is meaningful and useful to the user. To circumvent this issue, it is suggested that the domain expert could provide background information about the dataset, which can be incorporated by a clustering algorithm in order to improve the solution. Performing clustering under this assumption is known as semi-supervised clustering. This work explores semi-supervised clustering through the k-medoids model. Results obtained by a Variable Neighborhood Search (VNS) heuristic show that the k-medoids model presents classification accuracy compared to the traditional k-means approach. Furthermore, the model demonstrates high flexibility and performance by combining kernel projections with pairwise constraints.

In this paper we address a metaheuristic for an combinatorial optimization problem. For any given graph \(\mathcal {G}=(V,E)\) (where the nodes represent items and edges correlations), we want to find the clique \(\mathcal {C} \subseteq V\) such that the number of links shared between \(\mathcal {C}\) and \(V - \mathcal {C}\) is maximized. This problem is known in the literature as the Max Cut-Clique (MCC).

The contributions of this paper are three-fold. First, the complexity of the MCC is established, and we offer bounds for the MCC using elementary graph theory. Second, an exact Integer Linear Programming (ILP) formulation for the MCC is offered. Third, a full GRASP/VND methodology enriched with a Tabu Search is here developed, where the main ingredients are novel local searches and a Restricted Candidate List that trades greediness for randomization in a multi-start fashion. A dynamic Tabu list considers a bounding technique based on the previous analysis.

Finally, a fair comparison between our hybrid algorithm and the globally optimum solution using the ILP formulation confirms that the globally optimum solution is found by our heuristic for graphs with hundreds of nodes, but more efficiently in terms of time and memory requirements.

In this paper a multi-level capacitated lotsizing problem with machine-capacity-constraint and backlogging is studied. The main objective is to minimize the total cost which includes the inventory and delaying costs of produced items. Since the problem under study is NP-hard, a variable neighborhood search (VNS) combined with CPLEX solver is proposed as a solution approach. Neighborhood is changed according to VNS scheme employing four different functions and is locally optimized for a set of partial MIP problems that can be easily solved.

Finally, extensive computational tests demonstrate that the proposed search algorithm can find good quality solutions for all examined problems. The objective values obtained by the proposed algorithm are comparable to the results of state-of-the art, much more complicated algorithms.

This work presents a new variant of the Location Inventory Routing Problem (LIRP), called Pollution LIRP (PLIRP). The PLIRP considers both economic and environmental impacts. A Mixed Integer Programming (MIP) formulation is employed and experimental results on ten randomly generated small-sized instances using CPLEX are reported. Furthermore, it is shown that, CPLEX could not compute any feasible solution on another set of ten randomly generated medium-sized instances, with a time limit of five hours. Therefore, for solving more computationally challenging instances, two Basic Variable Neighborhood Search (BVNS) metaheuristic approaches are proposed. A comparative analysis between CPLEX and BVNS on these 20 problem instances is reported.

This paper extends some explanations about the convergence of a type of Evolution Strategies guided by Neighborhood Structures, the Neighborhood Guided Evolution Strategies. Different well-known Neighborhood Structures commonly applied to Vehicle Routing Problems are used to highlight the evolution of the move operators during the evolutionary process of a self-adaptive Reduced Variable Neighborhood Search procedure. Since the proposal uses only few components for its search, we believe it can be seen inside the scope of the recently proposed “Less Is More Approach”.

The Order Batching Problem (OBP) can be considered a family of optimization problems related to the retrieval of goods in a warehouse. The original and most extended version of the problem consists in minimizing the total time needed to collect a group of orders. However, this version has been evolved with many other variants, where the restrictions and/or the objective function might change. In this paper, we deal with the Online Order Batching Problem (OOBP) version, which introduces the novelty to the OBP of considering orders that have arrived to the warehouse once the retrieval of previous orders has started. This family of problems has been deeply studied by the heuristic community in the past. Notice, that solving any variant of the OBP include two important activities: grouping the orders into batches (batching) and determining the route to follow by a picker to retrieve the items within the same batch (routing). We review the most outstanding proposals in the literature for the OOBP variant and we propose a new version of a competitive Variable Neighborhood Search (VNS) algorithm to tackle the problem.

The School Timetabling Problem is widely known and it appears at the beginning of the school term of the institutions. Due to its complexity, it is usually solved by heuristic methods. In this work, we developed two algorithms based on the Variable Neighborhood Search (VNS) metaheuristic. The first one, named Skewed General Variable Neighborhood Search (SGVNS), uses Variable Neighborhood Descent (VND) as local search method. The second one, so-called Adaptive VNS, is based on VNS and probabilistically chooses the neighborhoods to do local searches, with the probability being higher for the more successful neighborhoods. The computational experiments show a good adherence of these algorithms for solving the problem, especially comparing them with previous works using the same metaheuristic, as well as with previous published results of the winning algorithm of the International Timetabling Competition of 2011.

The Maximum Balanced Biclique Problem (MBBP) consists of identifying a complete bipartite graph, or biclique, of maximum size within an input bipartite graph. This combinatorial optimization problem is solvable in polynomial time when the balance constraint is removed. However, it becomes \(\mathcal {NP}\)–hard when the induced subgraph is required to have the same number of vertices in each layer. Biclique graphs have been proven to be useful in several real-life applications, most of them in the field of biology, and the MBBP in particular can be applied in the design of programmable logic arrays or nanoelectronic systems. Most of the approaches found in literature for this problem are heuristic algorithms based on the idea of removing vertices from the input graph until a feasible solution is obtained; and more recently in the state of the art an evolutionary algorithm (MA/SM) has been proposed. As stated in previous works it is difficult to propose an effective local search method for this problem. Therefore, we propose the use of Reduced Variable Neighborhood Search (RVNS). This methodology is based on a random exploration of the considered neighborhoods and it does not require a local search.

Recent advances in networks technology require from advanced technologies for monitoring and controlling weaknesses in networks. Networks are naturally dynamic systems to which a wide variety of devices are continuously connecting and disconnecting. This dynamic nature force us to maintain a constant analysis looking for weak points that can eventually disconnect the network. The detection of weak points is devoted to find which nodes must be reinforced in order to increase the safety of the network. This work tackles the \( \alpha \) separator problem, which aims to find a minimum set of nodes that disconnect the network in subnetworks of size smaller than a given threshold. A Variable Neighborhood Search algorithm is proposed for finding the minimum \( \alpha \) separator in different network topologies, comparing the obtained results with the best algorithm found in the state of the art.

This study proposes a new cooperative approach to the Multiple-Choice Knapsack problem with Setup (MCKS) that effectively combines variable neighborhood search (VNS) with an integer programing (IP). Our approach, based on a local search technique with an adaptive perturbation mechanism to assign the classes to knapsack, and then if the assignment is identified to be promising by comparing its result to the upper bound, we applied the IP to select the items in knapsack. For the numerical experiment, we generated different instances for MCKS. In the experimental setting, we compared our cooperative approach to the Mixed Integer Programming provided in literature. Experimental results clearly showed the efficiency and effectiveness of our cooperative approach with −0.11% as gap of the objective function and 13 s vs. 2868 s as computation time.

The Multi-Depot Vehicle Routing Problem (MDVRP) is a variant of the Vehicle Routing Problem (VRP) that consists in designing a set of vehicle routes to serve all customers, such that the maximum number of vehicle per depot, the vehicle capacity and the maximum time for each route are respected. The objective is to minimize the total cost of transportation. This paper presents an algorithm, named VNSALS, based on the Variable Neighborhood Search (VNS) with Adaptive Local Search (ALS) for solving it. The main procedures of VNSALS are perturbation, ALS and cluster refinement. The perturbation procedure of VNS is important to diversify the solutions and avoid getting stuck in local optima. The ALS procedure consists in memorizing the results found after applying a local search and in using this memory to select the most promising neighborhood for the next local search application. The choice of the neighborhood is very important to improve the solution in heuristic methods because the complexity of the local search is high and expensive. On the other hand, customer’s reallocation keeps the clusters more balanced. VNSALS is tested in classical instances of MDVRP for evaluating its efficiency and the results are presented and discussed.

This paper deals with the Weighted Generalized Regenerator Location Problem (WGRLP) that arises in the design of optical telecommunication networks. During the transmission of optical signal, its quality deteriorates with the distance from the source, and therefore, it has to be regenerated by installing regenerators at some of the nodes in the network. The WGRLP involves weights assigned to potential regenerator locations, reflecting the costs of regenerator deployment. The objective of WGRLP is to minimize the sum of weights assigned to locations with installed regenerators, while ensuring a good quality communication among terminal nodes. As telecommunication networks usually involve large number of nodes, an efficient optimization method is required to deal with real-life problem dimensions. In this paper, a Skewed Variable Neighborhood Search method (SVNS) is proposed as solution approach for the WGRLP. The designed SVNS uses adequate data structures for solution representation and efficient procedures for objective function update, feasibility check, and solution repair. Computational results on the WGRLP data set from the literature show that the proposed SVNS reaches all known optimal solutions on small and medium size instances in short running times and outperforms existing heuristic approaches for the WGRLP. In addition, SVNS is tested on large scale WGRLP instances not considered in the literature so far. The presented computational results indicate the potential of SVNS as solution method for WGRLP and related network design problems.

We study the single-processor scheduling problem with time restrictions in order to minimize the makespan. In this problem, n independent jobs have to be processed on a single processor, subject only to the following constraint: During any time period of length \(\alpha >0\) the number of jobs being executed is less than or equal to a given integer value B. It has been shown that the problem is NP-hard even for B = 2. We propose the two metaheuristics variable neighborhood search and a fixed neighborhood search to solve the problem. We conduct computational experiments on randomly generated instances. The results indicate that our algorithms are effective and efficient regarding the quality of the solutions and the computational times required for finding them.

Variable neighborhood searches and evolutionary techniques have shown their effectiveness when dealing with many combinatorial optimisation problems. This study proposes to combine these two techniques for addressing the routing problem using electric and modular vehicles. This is a recent problem that aims to overcome recharging battery constraints while maintaining a certain performance regarding to the fleet cost and the traveled distance. An experimental study on benchmark instances is provided to show the relevance of the proposed algorithm.

In this paper, we consider the integrated Berth Allocation and Crane Assignment problem, with availability constraints and high tides restrictions, in bulk port context. We were inspired by a real case study of a port owned by our industrial partner. The objective is to minimize the total penalty of tardiness. First, we implemented a greedy heuristic to compute an initial solution. Then, we proposed a sequential Variable Neighborhood Descent (seq-VND) for the problem. In addition, we compared the efficiency of different scenarios for the seq-VND against results given by a mathematical model for the problem.

The well-known Vehicle Routing-Allocation Problem (VRAP) receives recently more attention than the classical routing problems. This article deals with a special case of the VRAP named the multi-vehicle multi-Covering Tour Problem (mm-CTP-p). More precisely, the mm-CTP-p is a generalized variant of the multi-vehicle Covering Tour Problem (m-CTP-p). In both problems, the objective is to find a minimum length set of vehicle routes while satisfying the total demands by visiting vertices by the route or covering vertices which does not included in any route. But, in the m-CTP-p, the demand of a vertex can be satisfied with only one coverage whereas in the mm-CTP-p, a vertex must be covered several times to be completely served. Indeed, a vertex is covered if it lies within a specified distance of at least one vertex of a route. We develop a General Variable Neighborhood Search algorithm (GVNS) with a mixed Variable Neighborhood Descent (mixed-VND) method to solve the problem. Experiments were conducted using benchmark instances from the literature. Extensive computational results on mm-CTP-p problems show the performance of our method.

In this paper a Permutation Flowshop Scheduling Problem is solved using a hybridization of the Firefly algorithm with Variable Neighborhood Search algorithm. The Permutation Flowshop Scheduling Problem (PFSP) is one of the most computationally complex problems. It belongs to the class of combinatorial optimization problems characterized as NP-hard. In order to find high quality solutions in reasonable computational time, heuristic and metaheuristic algorithms have been used for solving the problem. The proposed method, Hybrid Firefly Variable Neighborhood Search algorithm, uses in the local search phase of the algorithm a number of local search algorithms, 1-0 relocate, 1-1 exchange and 2-opt. In order to test the effectiveness and efficiency of the proposed method we used a set of benchmark instances of different sizes from the literature.

In this work we examine the impact of three shaking procedures on the performance of a GVNS metaheuristic algorithm for solving the Asymmetric Travelling Salesman Problem (ATSP). The first shaking procedure is a perturbation method that is commonly used in the literature as intensified shaking method. The second one is a quantum-inspired shaking method, while the third one is a shuffle method. The shaped GVNS schemes are tested with both first and best improvement and with a time limit of one and two minutes. Experimental analysis shows that the first two methods perform equivalently and much better than the shuffle approach, when using the best improvement strategy. The first method also outperforms the other two when using the first improvement strategy, while the second method produces results that are closer to the results of the third in this case.

In this paper we deal with a generalization of the multi-depot capacitated vehicle routing problem namely the multi-depot covering tour vehicle routing problem (MDCTVRP). This problem is considered more challenging since it deals with some situations where it is not possible to visit all the customers with the vehicles routes. In this problem, a customer can receive its demand directly by visiting it along the tour using a set of vehicles located at different depots or by covering it. A customer is considered as covered if it is located within an acceptable distance from at least one visited customer in the tour. The latter can satisfy its demand. We propose a general variable neighborhood search algorithm to solve the MDCTVRP. In this paper we use a variable neighborhood search (VNS) with a variable neighborhood descent (VND) method as a local search. Experiments were conducted on benchmark instances from the literature.