Skip to main content
main-content
Top

About this book

This book constitutes the refereed post-conference proceedings of the 6th International Conference on Variable Neighborhood Search, ICVNS 2018, held in Sithonia, Greece, in October 2018.

ICVNS 2018 received 49 submissions of which 23 full papers were carefully reviewed and selected.

VNS is a metaheuristic based on systematic changes in the neighborhood structure within a search for solving optimization problems and related tasks. The main goal of ICVNS 2018 was to provide a stimulating environment in which researchers coming from various scientific fields could share and discuss their knowledge, expertise, and ideas related to the VNS metaheuristic and its applications.

Table of Contents

Frontmatter

Open Access

Improved Variable Neighbourhood Search Heuristic for Quartet Clustering

Abstract
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.
Sergio Consoli, Jan Korst, Steffen Pauws, Gijs Geleijnse

On the k-Medoids Model for Semi-supervised Clustering

Abstract
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.
Rodrigo Randel, Daniel Aloise, Nenad Mladenović, Pierre Hansen

Complexity and Heuristics for the Max Cut-Clique Problem

Abstract
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.
Mathias Bourel, Eduardo Canale, Franco Robledo, Pablo Romero, Luis Stábile

A VNS Approach to Solve Multi-level Capacitated Lotsizing Problem with Backlogging

Abstract
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.
Jerzy Duda, Adam Stawowy

How to Locate Disperse Obnoxious Facility Centers?

Abstract
The bi-objective obnoxious p-median problem has not been extensively studied in the literature yet, even having an enormous real interest. The problem seeks to locate p facilities but maximizing two different objectives that are usually in conflict: the sum of the minimum distance between each customer and their nearest facility center, and the dispersion among facilities, i.e., the sum of the minimum distance from each facility to the rest of the selected facilities. This problem arises when the interest is focused on locating obnoxious facilities such as waste or hazardous material, nuclear power or chemical plants, noisy or polluting services like airports. To address the bi-objective obnoxious p-median problem we propose a variable neighborhood search approach. Computational experiments show promising results. Specifically, the proposed algorithm obtains high-quality efficient solutions compared to the state-of-art efficient solutions.
Jesús Sánchez-Oro, J. Manuel Colmenar, Enrique García-Galán, Ana D. López-Sánchez

Basic VNS Algorithms for Solving the Pollution Location Inventory Routing Problem

Abstract
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.
Panagiotis Karakostas, Angelo Sifaleras, Michael C. Georgiadis

Less Is More: The Neighborhood Guided Evolution Strategies Convergence on Some Classic Neighborhood Operators

Abstract
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”.
Vitor Nazário Coelho, Igor Machado Coelho, Nenad Mladenović, Helena Ramalhinho, Luiz Satoru Ochi, Frederico G. Guimarães, Marcone J. F. Souza

New VNS Variants for the Online Order Batching Problem

Abstract
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.
Sergio Gil-Borrás, Eduardo G. Pardo, Antonio Alonso-Ayuso, Abraham Duarte

An Adaptive VNS and Skewed GVNS Approaches for School Timetabling Problems

Abstract
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.
Ulisses Rezende Teixeira, Marcone Jamilson Freitas Souza, Sérgio Ricardo de Souza, Vitor Nazário Coelho

Finding Balanced Bicliques in Bipartite Graphs Using Variable Neighborhood Search

Abstract
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.
Juan David Quintana, Jesús Sánchez-Oro, Abraham Duarte

General Variable Neighborhood Search for Scheduling Heterogeneous Vehicles in Agriculture

Abstract
A new variant of Vehicle Scheduling Problem (VSP), denoted as Vehicle Scheduling Problem with Heterogeneous Vehicles (VSP-HV), which arises from optimizing the sugar beet transportation in a sugar factory in Serbia is introduced. The objective of the considered VSP-HV is to minimize the time required for daily transportation of sugar beet by heterogeneous vehicles under problem-specific constraints. General Variable Neighborhood Search (GVNS) is designed as a solution method for the considered problem. A computational study is conducted on the set of real-life instances, as well as on the set of generated instances of larger dimensions. A Mixed Integer Quadratically Constraint Programming (MIQCP) model is developed and used within commercial Lingo 17 solver to obtain optimal or feasible solutions for small-size real-life problem instances. Experimental results show that the proposed GVNS quickly reaches all known optimal solutions or improves the upper bounds of feasible solutions on small-size instances. On larger problem instances, for which Lingo 17 could not find feasible solutions, GVNS provided its best solutions for limited CPU time.
Ana Anokić, Zorica Stanimirović, Đorđe Stakić, Tatjana Davidović

Detecting Weak Points in Networks Using Variable Neighborhood Search

Abstract
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.
Sergio Pérez-Peló, Jesús Sánchez-Oro, Abraham Duarte

A Variable Neighborhood Search with Integer Programming for the Zero-One Multiple-Choice Knapsack Problem with Setup

Abstract
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.
Yassine Adouani, Bassem Jarboui, Malek Masmoudi

A VNS-Based Algorithm with Adaptive Local Search for Solving the Multi-Depot Vehicle Routing Problem

Abstract
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.
Sinaide Nunes Bezerra, Marcone Jamilson Freitas Souza, Sérgio Ricardo de Souza, Vitor Nazário Coelho

Skewed Variable Neighborhood Search Method for the Weighted Generalized Regenerator Location Problem

Abstract
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.
Lazar Mrkela, Zorica Stanimirović

Using a Variable Neighborhood Search to Solve the Single Processor Scheduling Problem with Time Restrictions

Abstract
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.
Rachid Benmansour, Oliver Braun, Saïd Hanafi, Nenad Mladenovic

An Evolutionary Variable Neighborhood Descent for Addressing an Electric VRP Variant

Abstract
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.
Dhekra Rezgui, Hend Bouziri, Wassila Aggoune-Mtalaa, Jouhaina Chaouachi Siala

A Variable Neighborhood Descent Heuristic for the Multi-quay Berth Allocation and Crane Assignment Problem Under Availability Constraints

Abstract
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.
Issam Krimi, Afaf Aloullal, Rachid Benmansour, Abdessamad Ait El Cadi, Laurent Deshayes, David Duvivier

A Variable Neighborhood Search Approach for Solving the Multidimensional Multi-Way Number Partitioning Problem

Abstract
This paper presents an implementation of the Variable Neighborhood Search (VNS) metaheuristic for solving the optimization version of the Multidimensional Multi-Way Number Partitioning Problem (MDMWNPP). This problem consists in distributing the vectors of a given sequence into k disjoint subsets such that the sums of each subset form a set of vectors with minimum diameter. The proposed VNS for solving MDMWNPP has a good performance over instances with three and four subsets. A comparative study of results found from this proposed VNS and an implementation of Memetic Algorithm (MA) is carried out, running in the same proportional time interval. Although the average results are different, the statistical tests show that results of the proposed VNS are not significantly better than MA in a set of instances analyzed.
Alexandre Frias Faria, Sérgio Ricardo de Souza, Marcone Jamilson Freitas Souza, Carlos Alexandre Silva, Vitor Nazário Coelho

A General Variable Neighborhood Search with Mixed VND for the multi-Vehicle multi-Covering Tour Problem

Abstract
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.
Manel Kammoun, Houda Derbel, Bassem Jarboui

A Hybrid Firefly - VNS Algorithm for the Permutation Flowshop Scheduling Problem

Abstract
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.
Andromachi Taxidou, Ioannis Karafyllidis, Magdalene Marinaki, Yannis Marinakis, Athanasios Migdalas

Studying the Impact of Perturbation Methods on the Efficiency of GVNS for the ATSP

Abstract
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.
Christos Papalitsas, Theodore Andronikos, Panagiotis Karakostas

A GVNS Algorithm to Solve VRP with Optional Visits

Abstract
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.
Manel Kammoun, Houda Derbel, Bassem Jarboui

Backmatter

Additional information

Premium Partner

    image credits