Variable neighborhood search for the travelling deliveryman problem

A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit is minimum. The deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.     

Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows

This paper presents operators searching large neighborhoods in order to solve the vehicle routing problem. They make use of the pruning and propagation techniques of constraint programming which allow an efficient search of such neighborhoods. The advantages of using a large neighborhood are not only the increased probability of finding a better solution at each iteration but also the reduction of the need to invoke specially-designed methods to avoid local minima. These operators are combined in a variable neighborhood descent in order to take advantage of the different neighborhood structures they generate.     

The variable neighborhood search for the two machine flow shop problem with a passive prefetch

We consider the two machine flow shop scheduling problem with passive loading of the buffer on the second machine. To compute lower bounds for the global optimum, we present four integer linear programming formulations of the problem. Three local search methods with variable neighborhoods are developed for obtaining upper bounds. Some new large neighborhood is designed. Our methods use this neighborhood along with some other well-known neighborhoods. For computational experiments, we present a new class of test instances with known global optima. Computational results indicate a high efficiency of the proposed approach for the new class of instances as well as for other classes of instances of the problem.     

Creating very large scale neighborhoods out of smaller ones by compounding moves

This paper discusses neighborhood search algorithms where the size of the neighborhood is “very large” with respect to the size of the input data. We concentrate on such a very large scale neighborhood (VLSN) search technique based on compounding independent moves (CIM) such as 2-opts, swaps, and insertions. We present a systematic way of creating and searching CIM neighborhoods for routing problems with side constraints. For such problems, the exact search of the CIM neighborhood becomes NP-hard. We introduce a multi-label shortest path algorithm for searching these neighborhoods heuristically. Results of a computational study on the vehicle routing problem with capacity and distance restrictions shows that CIM algorithms are very competitive approaches for solving vehicle routing problems. Overall, the solutions generated by the CIM algorithm have the best performance among the current solution methodologies in terms of percentage deviation from the best-known solutions for large-scale capacitated VRP instances.     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

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.     

Ejection chain and filter-and-fan methods in combinatorial optimization

The design of effective neighborhood structures is fundamentally important for creating better local search and metaheuristic algorithms for combinatorial optimization. Significant efforts have been made to develop larger and more powerful neighborhoods that are able to explore the solution space more effectively while keeping computation complexity within acceptable levels. The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications to a number of important combinatorial optimization problems. The features of the methods that make them effective in these applications are highlighted to provide insights into solving challenging problems in other settings.     

Efficient 2 and 3-Flip Neighborhood Search Algorithms for the MAX SAT: Experimental Evaluation

For problems SAT and MAX SAT, local search algorithms are widely acknowledged as one of the most effective approaches. Most of the local search algorithms are based on the 1-flip neighborhood, which is the set of solutions obtainable by flipping the truth assignment of one variable. In this paper, we consider r-flip neighborhoods for r = 2, 3, and examine their effectiveness by computational experiments. In the accompanying paper, we proposed new implementations of these neighborhoods, and showed that the expected size of 2-flip neighborhood is O(n + m) and that of 3-flip neighborhood is O(m + t ² n), compared to their original size O(n ²) andO(n ³), respectively, where n is the number of variables, m is the number of clauses and t is the maximum number of appearances of one variable. These are used in this paper under the framework of tabu search and other metaheuristic methods, and compared with other existing algorithms with 1-flip neighborhood. The results exhibit good prospects of larger neighborhoods.     

Ejection chain and filter-and-fan methods in combinatorial optimization

The design of effective neighborhood structures is fundamental to the performance of local search and metaheuristic algorithms for combinatorial optimization. Significant efforts have been made in the creation of larger and more powerful neighborhoods that are able to explore the solution space more extensively and effectively while keeping computation complexity within acceptable levels. The most important advances in this domain derive from dynamic and adaptive neighborhood constructions originating in ejection chain methods and a special form of a candidate list design that constitutes the core of the filter-and-fan method. The objective of this paper is to lay out the general framework of the ejection chain and filter-and-fan methods and present applications to a number of important combinatorial optimization problems. The features of the methods that make them effective in these applications is expected to provide insights into solving challenging problems in other settings.     

Efficient generation of super condensed neighborhoods

Indexing methods for the approximate string matching problem spend a considerable effort generating condensed neighborhoods. Condensed neighborhoods, however, are not a minimal representation of a pattern neighborhood. Super condensed neighborhoods, proposed in this work, are smaller, provably minimal and can be used to locate approximate matches that can later be extended by on-line search. We present an algorithm for generating Super Condensed Neighborhoods. The algorithm can be implemented either by using dynamic programming or non-deterministic automata. The time complexity is O(ms) for the first case and O(kms) for the second, where m is the pattern size, s is the size of the super condensed neighborhood and k the number of errors. Previous algorithms depended on the size of the condensed neighborhood instead. These algorithms can be implemented using Bit-Parallelism and Increased Bit-Parallelism techniques. Our experimental results show that the resulting algorithms are fast and achieve significant speedups, when compared with the existing proposals that use condensed neighborhoods.     

Matching based very large-scale neighborhoods for?parallel machine scheduling

In this paper we study very large-scale neighborhoods for the minimum total weighted completion time problem on parallel machines, which is known to be strongly $\mathcal{NP}$ -hard. We develop two different ideas leading to very large-scale neighborhoods in which the best improving neighbor can be determined by calculating a weighted matching. The first neighborhood is introduced in a general fashion using combined operations of a basic neighborhood. Several examples for basic neighborhoods are given. The second approach is based on a partitioning of the job sets on the machines and a reassignment of them. In a computational study we evaluate the possibilities and the limitations of the presented very large-scale neighborhoods.     

New relationships for multi-neighborhood search for the minimum linear arrangement problem

We develop a series of theorems about the graph structure of the classical Minimum Linear Arrangement (MinLA) problem which disclose properties that can be exploited by Multi-Neighborhood Search (MNS) algorithms. As a foundation, we differentiate between swaps of labels attached to adjacent and non-adjacent nodes to create two new neighborhood classes, and show how our theorems yield efficient algorithms for updating key arrays used by local search procedures. In addition, we introduce a class of neighborhoods called set-based neighborhoods supported by a theorem that identifies solutions (labelings) for the MinLA problem in polynomial time that dominate exponential numbers of alternative solutions. The component neighborhoods within this new neighborhood class can be applied in various sequences in conjunction with the first two new neighborhoods introduced. Our results also apply to problems with objectives different than those of MinLA. Finally, our results make it possible to exploit the new neighborhoods according to the user's choice of MNS protocols and alternative local search algorithms.     

基于一类新方向的宽邻域路径跟踪内点算法

基于一类带有参数theta的新方向, 提出了求解单调线性互补问题的宽邻 域路径跟踪内点算法, 且当theta=1时即为经典牛顿方向. 当取theta为与问题规模 n无关的常数时, 算法具有O(nL)迭代复杂性, 其中L是输入数据的长度, 这与经典宽邻 域算法的复杂性相同; 当取theta=\sqrt{n/\beta\tau}时, 算法具有O(\sqrt{n}L)迭代复杂性, 这里的\beta, \tau是邻域参数, 这与窄邻域算法的复杂性相同. 这是首次研究包括经典宽邻域路径跟踪算法的一类内点算法, 给出了统一的算法框架和收敛性分析方法.     

Neighborhood analysis: a case study on curriculum-based course timetabling

In this paper, we present an in-depth analysis of neighborhood relations for local search algorithms. Using a curriculum-based course timetabling problem as a case study, we investigate the search capability of four neighborhoods based on three evaluation criteria: percentage of improving neighbors, improvement strength and search steps. This analysis shows clear correlations of the search performance of a neighborhood with these criteria and provides useful insights on the very nature of the neighborhood. This study helps understand why a neighborhood performs better than another one and why and how some neighborhoods can be favorably combined to increase their search power. This study reduces the existing gap between reporting experimental assessments of local search-based algorithms and understanding their behaviors.     

Bringing order into the neighborhoods: relaxation guided variable neighborhood search

In this article we investigate a new variant of Variable Neighborhood Search (VNS): Relaxation Guided Variable Neighborhood Search. It is based on the general VNS scheme and a new Variable Neighborhood Descent (VND) algorithm. The ordering of the neighborhood structures in this VND is determined dynamically by solving relaxations of them. The objective values of these relaxations are used as indicators for the potential gains of searching the corresponding neighborhoods. We tested this new approach on the well-studied multidimensional knapsack problem. Computational experiments show that our approach is beneficial to the search, improving the obtained results. The concept is, in principle, more generally applicable and seems to be promising for many other combinatorial optimization problems approached by VNS. NICTA is funded by the Australian Government’s Backing Australia’s Ability initiative, in part through the Australian Research Council.The Institute of Computer Graphics and Algorithms is supported by the European RTN ADONET under grant 504438.     

A variable neighborhood-based heuristic for the heterogeneous fleet vehicle routing problem

The heterogeneous fleet vehicle routing problem is investigated using some adaptations of the variable neighborhood search (VNS). The initial solution is obtained by Dijkstra’s algorithm based on a cost network constructed by the sweep algorithm and the 2-opt. Our VNS algorithm uses several neighborhoods which are adapted for this problem. In addition, a number of local search methods together with a diversification procedure are used. Two VNS variants, which differ in the order the diversification and Dijkstra’s algorithm are used, are implemented. Both variants appear to be competitive and produce new best results when tested on the data sets from the literature. We also constructed larger data sets for which benchmarking results are provided for future comparison.     

Categorical neighborhood operators

We introduce and study a concept of neighborhood operator on a category. Such an operator is obtained by assigning a suitably axiomatized stack of subobjects - the neighborhoods - to every subobject of each object in the category. We discuss closure and interior operators, convergence, separation and compactness with respect to a neighborhood operator, defined in a natural way.     

General variable neighborhood search for the continuous optimization

We suggest a new heuristic for solving unconstrained continuous optimization problems. It is based on a generalized version of the variable neighborhood search metaheuristic. Different neighborhoods and distributions, induced from different metrics are ranked and used to get random points in the shaking step. We also propose VNS for solving constrained optimization problems. The constraints are handled using exterior point penalty functions within an algorithm that combines sequential and exact penalty transformations. The extensive computer analysis that includes the comparison with genetic algorithm and some other approaches on standard test functions are given. With our approach we obtain encouraging results.     

On the Structure of asymptotics of the solution of a second-order elliptic equation in a neighborhood of an angular point

The behavior of solutions of elliptic equations in neighborhoods of angular and conical boundary points has been well studied; the asymptotics of these solutions has been constructed. In the present paper, we propose a new approach to constructing asymptotic decompositions in a neighborhood of an angular boundary point, which allows us to describe the structure of these asymptotics in a relatively simple and illustrative way.