Skewed VNS enclosing second order algorithm for the degree constrained minimum spanning tree problem

We develop ideas to enhance the performance of the variable neighborhood search (VNS) by guiding the search in the shaking phase, and by employing the Skewed strategy. For this purpose, Second Order algorithms and Skewed functions expressing structural differences are embedded in an efficient VNS proposed in the literature for the degree constrained minimum spanning tree problem. Given an undirected graph with weights associated with its edges, the degree constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. Computational experiments are conducted on the largest and hardest benchmark instances found in the literature to date. We report results showing that the VNS with the proposed strategies improved the best known solutions for all the hardest benchmark instances. Moreover, these new best solutions significantly reduced the gaps with respect to tight lower bounds reported in the literature.     

Real-world flexible resource profile scheduling with multiple criteria: learning scalarization functions for MIP and heuristic approaches

This article addresses a scheduling problem for a chemical research laboratory. Activities with potentially variable, non-rectangular resource allocation profiles must be scheduled on discrete renewable resources. A mixed-integer programming (MIP) formulation for the problem includes maximum time lags, custom resource allocation constraints, and multiple nonstandard objectives. We present a list scheduling heuristic that mimics the human decision maker and thus provides reference solutions. These solutions are the basis for an automated learning-based determination of coefficients for the convex combination of objectives used by the MIP and a dedicated variable neighborhood search (VNS) approach. The development of the VNS also involves the design of new neighborhood structures that prove particularly effective for the custom objectives under consideration. Relative improvements of up to 60% are achievable for isolated objectives, as demonstrated by the final computational study based on a broad spectrum of randomly generated instances of different sizes and real-world data from the company’s live system.     

Variable neighborhood search: Principles and applications

Systematic change of neighborhood within a possibly randomized local search algorithm yields a simple and effective metaheuristic for combinatorial and global optimization, called variable neighborhood search (VNS). We present a basic scheme for this purpose, which can easily be implemented using any local search algorithm as a subroutine. Its effectiveness is illustrated by solving several classical combinatorial or global optimization problems. Moreover, several extensions are proposed for solving large problem instances: using VNS within the successive approximation method yields a two-level VNS, called variable neighborhood decomposition search (VNDS); modifying the basic scheme to explore easily valleys far from the incumbent solution yields an efficient skewed VNS (SVNS) heuristic. Finally, we show how to stabilize column generation algorithms with help of VNS and discuss various ways to use VNS in graph theory, i.e., to suggest, disprove or give hints on how to prove conjectures, an area where metaheuristics do not appear to have been applied before.     

Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem

We consider the generalized version of the classical Minimum Spanning Tree problem where the nodes of a graph are partitioned into clusters and exactly one node from each cluster must be connected. We present a Variable Neighborhood Search (VNS) approach which uses three different neighborhood types. Two of them work in complementary ways in order to maximize search effectivity. Both are large in the sense that they contain exponentially many candidate solutions, but efficient polynomial-time algorithms are used to identify best neighbors. For the third neighborhood type we apply Mixed Integer Programming to optimize local parts within candidate solution trees. Tests on Euclidean and random instances with up to 1280 nodes indicate especially on instances with many nodes per cluster significant advantages over previously published metaheuristic approaches. This work is supported by the RTN ADONET under grant 504438.     

General variable neighborhood search for the uncapacitated single allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

In this paper we propose a general variable neighborhood search heuristic for solving the uncapacitated single allocation p-hub center problem (USApHCP). For the local search step we develop a nested variable neighborhood descent strategy. The proposed approach is tested on benchmark instances from the literature and found to outperform the state-of-the-art heuristic based on ant colony optimization. We also test our heuristic on large scale instances that were not previously considered as test instances for the USApHCP. Moreover, exact solutions were reached by our GVNS for all instances where optimal solutions are known.     

Variable Neighborhood Decomposition Search

The recent Variable Neighborhood Search (VNS) metaheuristic combines local search with systematic changes of neighborhood in the descent and escape from local optimum phases. When solving large instances of various problems, its efficiency may be enhanced through decomposition. The resulting two level VNS, called Variable Neighborhood Decomposition Search (VNDS), is presented and illustrated on the p-median problem. Results on 1400, 3038 and 5934 node instances from the TSP library show VNDS improves notably upon VNS in less computing time, and gives much better results than Fast Interchange (FI), in the same time that FI takes for a single descent. Moreover, Reduced VNS (RVNS), which does not use a descent phase, gives results similar to those of FI in much less computing time.     

Serial-batching group scheduling with release times and the combined effects of deterioration and truncated job-dependent learning

This paper investigates a single machine serial-batching scheduling problem considering release times, setup time, and group scheduling, with the combined effects of deterioration and truncated job-dependent learning. The objective of the studied problem is to minimize the makespan. Firstly, we analyze the special case where all groups have the same arrival time, and propose the optimal structural properties on jobs sequencing, jobs batching, batches sequencing, and groups sequencing. Next, the corresponding batching rule and algorithm are developed. Based on these properties and the scheduling algorithm, we develop a hybrid VNS–ASHLO algorithm incorporating variable neighborhood search (VNS) and adaptive simplified human learning optimization (ASHLO) algorithms to solve the general case of the studied problem. Computational experiments on randomly generated instances are conducted to compare the proposed VNS–ASHLO with the algorithms of VNS, ASHLO, Simulated Annealing (SA), and Particle Swarm Optimization (PSO). The results based on instances of different scales show the effectiveness and efficiency of the proposed algorithm.     

Solving the unconstrained optimization problem by a variable neighborhood search

This paper presents variable neighborhood search (VNS) for the problem of finding the global minimum of a nonconvex function. The variable neighborhood search, which changes systematically neighborhood structures in the search for finding a better solution, is used to guide a set of standard improvement heuristics. This algorithm was tested on some standard test functions, and successful results were obtained. Its performance was compared with the other algorithms, and observed to be better.     

Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem

The aim of this work is to introduce several proposals for combining two metaheuristics: variable neighborhood search (VNS) and estimation of distribution algorithms (EDAs). Although each of these metaheuristics has been previously hybridized in several ways, this paper constitutes the first attempt to combine both optimization methods. The different ways of combining VNS and EDAs will be classified into three groups. In the first group, we will consider combinations where the philosophy underlying VNS is embedded in EDAs. Considering different neighborhood spaces (points, populations or probability distributions), we will obtain instantiations for the approaches in this group. The second group of algorithms is obtained when probabilistic models (or any other machine learning paradigm) are used in order to exploit the good and bad shakes of the randomly generated solutions in a reduced variable neighborhood search. The last group of algorithms contains the results of alternating VNS and EDAs. An application of the first approach is presented in the protein side chain placement problem. The results obtained show the superiority of the hybrid algorithm in comparison with EDAs and VNS.     

The tree representation for the pickup and delivery traveling salesman problem with LIFO loading

The feasible solutions of the traveling salesman problem with pickup and delivery (TSPPD) are commonly represented by vertex lists. However, when the TSPPD is required to follow a policy that loading and unloading operations must be performed in a last-in-first-out (LIFO) manner, we show that its feasible solutions can be represented by trees. Consequently, we develop a novel variable neighborhood search (VNS) heuristic for the TSPPD with last-in-first-out loading (TSPPDL) involving several search operators based on the tree data structure. Extensive experiments suggest that our VNS heuristic is superior to the current best heuristics for the TSPPDL in terms of solution quality, while requiring no more computing time as the size of the problem increases.     

Hybrid variable neighbourhood approaches to university exam timetabling

In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.     

A parallel multi-neighborhood cooperative tabu search for capacitated vehicle routing problems

This paper presents a parallel tabu search algorithm that utilizes several different neighborhood structures for solving the capacitated vehicle routing problem. Single neighborhood or neighborhood combinations are encapsulated in tabu search threads and they cooperate through a solution pool for the purpose of exploiting their joint power. The computational experiments on 32 large scale benchmark instances show that the proposed method is highly effective and competitive, providing new best solutions to four instances while the average deviation of all best solutions found from the collective best results reported in the literature is about 0.22%. We are also able to associate the beneficial use of special neighborhoods with some test instance characteristics and uncover some sources of the collective power of multi-neighborhood cooperation.     

Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem

The response time variability problem (RTVP) is a scheduling problem with a wide range of real-world applications: mixed-model assembly lines, multi-threaded computer systems, network environments, broadcast of commercial videotapes and machine maintenance, among others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. Since the RTVP is NP-hard, several heuristic and metaheuristic techniques are needed to solve non-small instances. The published metaheuristic procedure that obtained the best solutions, on average, for non-small RTVP instances is an algorithm based on a variant of the variable neighbourhood search (VNS), called Reduced VNS (RVNS). We propose hybridising RVNS with three existing algorithms based on tabu search, multi-start and particle swarm optimisation. The aim is to combine the strengths of the metaheuristics. A computational experiment is carried out and it is shown that, on average, all proposed hybrid methods are able to improve the best published solutions.     

Applying the pilot method to improve VNS and GRASP metaheuristics for the design of SDH/WDM networks

Variable neighborhood search (VNS) and Greedy randomized adaptive search procedure (GRASP) are among the well studied local search based metaheuristics providing good results for many combinatorial optimization problems throughout the last decade. While they are usually explored in different environments one may encounter quite obvious commonalities. Based on previous successful applications of these two types of metaheuristics on various network design problems in telecommunications, we further enhance these approaches by incorporating ideas from the pilot method. The different heuristics are compared among each other as well as against objective function values obtained from a mathematical programming formulation based on a commercial solver. The problem instances cover a large variety of networks and demand patterns.     

A basic variable neighborhood search heuristic for the uncapacitated multiple allocation <Emphasis Type="Italic">p</Emphasis>-hub center problem

The uncapacitated multiple allocation p-hub center problem (UMApHCP) consists of choosing p hub locations from a set of nodes with pairwise traffic demands in order to route the traffic between the origin-destination pairs such that the maximum cost between origin-destination pairs is minimum. It is assumed that transportation between non-hub nodes is possible only via chosen hub nodes. In this paper we propose a basic variable neighborhood search (VNS) heuristic for solving this NP hard problem. In addition we apply two mathematical formulations of the UMApHCP in order to detect limitations of the current state-of-the-art solver used for this problem. The heuristics are tested on benchmark instances for p-hub problems. The obtained results reveal the superiority of the proposed basic VNS over the state-of-the-art as well as over a multi-start local search heuristic developed by us in this paper.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

Cooperative Parallel Variable Neighborhood Search for the p-Median

We propose a cooperative multi-search method for the Variable Neighborhood Search (VNS) meta-heuristic based on the central-memory mechanism that has been successfully applied to a number of difficult combinatorial problems. In this approach, several independent VNS meta-heuristics cooperate by asynchronously exchanging information about the best solutions identified so far, thus conserving the simplicity of the original, sequential VNS ideas. The p-median problem (PM) serves as test case. Extensive experimentations have been conducted on the classical TSPLIB benchmark problem instances with up to 11948 customers and 1000 medians, without any particular calibration of the parallel method. The results indicate that, compared to sequential VNS, the cooperative strategy yields significant gains in terms of computation time without a loss in solution quality.     

变邻域模拟退火算法求解速度时变的VRPTW问题

本文在经典的带时间窗的车辆路径问题(VRPTW)的基础上,考虑不同时间段车辆行驶速度不同的情况,研究速度时变的带时间窗车辆路径问题(TDVRPTW),使问题更具实际意义。本文用分段函数表示不同时间段下的车辆行驶速度,并解决了速度时变条件下行驶时间计算的问题。针对模拟退火算法(SA)在求解VRPTW问题时易陷入局部最优解,变邻域搜索算法(VNS)在求解VRPTW问题时收敛速度慢的问题,本文将模拟退火算法以一定概率接受非最优解的思想和变邻域搜索算法系统地改变当前解的邻域结构以拓展搜索范围的思想结合起来,提出了一种改进的算法——变邻域模拟退火算法(SAVN),使算法在退火过程中一陷入局部最优解就改变邻域结构,更换搜索范围,以此提升算法跳出局部最优解的能力,加快收敛速度。通过在仿真实验中将SAVN算法的求解结果与VNS算法、SA算法进行对比,验证了SAVN算法确实能显著提升算法跳出局部最优解的能力。     

A variable neighborhood search with an effective local search for uncapacitated multilevel lot-sizing problems

In this study, we improved the variable neighborhood search (VNS) algorithm for solving uncapacitated multilevel lot-sizing (MLLS) problems. The improvement is twofold. First, we developed an effective local search method known as the Ancestors Depth-first Traversal Search (ADTS), which can be embedded in the VNS to significantly improve the solution quality. Second, we proposed a common and efficient approach for the rapid calculation of the cost change for the VNS and other generate-and-test algorithms. The new VNS algorithm was tested against 176 benchmark problems of different scales (small, medium, and large). The experimental results show that the new VNS algorithm outperforms all of the existing algorithms in the literature for solving uncapacitated MLLS problems because it was able to find all optimal solutions (100%) for 96 small-sized problems and new best-known solutions for 5 of 40 medium-sized problems and for 30 of 40 large-sized problems.     

Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem

In this paper we develop, study and test new neighborhood structures for the Hop-constrained Minimum Spanning Tree Problem (HMSTP). These neighborhoods are defined by restricted versions of a new dynamic programming formulation for the problem and provide a systematic way of searching neighborhood structures based on node-level exchanges. We have also developed several local search methods that are based on the new neighborhoods. Computational experiments for a set of benchmark instances with up to 80 nodes show that the more elaborate methods produce in a quite fast way, heuristic solutions that are, for all cases, within 2% of the optimum.