Variable Neighborhood Search for a Dynamic Rich Vehicle Routing Problem with time windows

A Dynamic Rich Vehicle Routing Problem with Time Windows has been tackled as a real-world application, in which customers requests can be either known at the beginning of the planning horizon or dynamically revealed over the day. Several real constraints, such as heterogeneous fleet of vehicles, multiple and soft time windows and customers priorities, are taken into consideration. Using exact methods is not a suitable solution for this kind of problems, given the fact that the arrival of a new request has to be followed by a quick re-optimization phase to include it into the solution at hand. Therefore, we have proposed a metaheuristic procedure based on Variable Neighborhood Search to solve this particular problem. The computational experiments reported in this work indicate that the proposed method is feasible to solve this real-world problem and competitive with the best results from the literature. Finally, it is worth mentioning that the software developed in this work has been inserted into the fleet management system of a company in Spain.     

Variable Neighborhood Search strategies for the Order Batching Problem

The Order Batching Problem is an optimization problem belonging to the operational management aspect of a warehouse. It consists of grouping the orders received in a warehouse (each order is composed by a list of items to be collected) in a set of batches in such a way that the time needed to collect all the orders is minimized. Each batch has to be collected by a single picker without exceeding a capacity limit. In this paper we propose several strategies based on the Variable Neighborhood Search methodology to tackle the problem. Our approach outperforms, in terms of quality and computing time, previous attempts in the state of the art. These results are confirmed by non-parametric statistical tests.     

MaxMinMin p-dispersion problem: A variable neighborhood search approach

In this work we have developed a Variable Neighborhood Search (VNS) method in order to solve the MaxMinMin p-dispersion problem, which adds a new type of plateau search mechanism to the classical VNS metaheuristic framework. Besides, several other contributions have been made to the basic VNS heuristic in terms of the ascent and perturbation functions. To the best of our knowledge this is the first application of the VNS to the MaxMinMin problem and our approach, compared to previous methods, finds or improves the results for all of the large-sized benchmarks with low computational efforts. Finding most of the proven optimal solutions in a fraction of a second, the robustness and quality of the solutions and the low complexity of the methods demonstrate the strength of the proposed heuristic solution procedures.     

基于邻域搜索的改进最大最小蚁群算法

针对蚁群算法求解旅行商问题时易陷入局部最优的问题,提出一个改进的混合最大最小蚁群算法,并应用于求解旅行商问题.上述算法设计了一种新的信息素更新模型,单个蚂蚁每走一步就进行信息素局部更新,在所有的蚂蚁搜索一周后,最优路径蚂蚁进行全局信息素更新.提出一种新的邻域搜索模型,将邻域大小设置为原来的一半,提高了计算的效率.在每个蚂蚁的一个周期循环后,使用邻域搜索算法优化最优解的路径长度.仿真结果表明,改进算法具有较高的求解精度和收敛速度.     

Variable Neighborhood Search based algorithms for high school timetabling

This work presents the application of Variable Neighborhood Search (VNS) based algorithms to the High School Timetabling Problem. The addressed model of the problem was proposed by the Third International Timetabling Competition (ITC 2011), which released many instances from educational institutions around the world and attracted 17 competitors. Some of the VNS algorithm variants were able to outperform the winner of Third ITC solver, which proposed a Simulated Annealing – Iterated local Search approach. This result coupled with another reports in the literature points that VNS based algorithms are a practical solution method for providing high quality solutions for some hard timetabling problems. Moreover they are easy to implement with few parameters to adjust.     

Reactive Search strategies using Reinforcement Learning,local search algorithms and Variable Neighborhood Search

Optimization techniques known as metaheuristics have been applied successfully to solve different problems, in which their development is characterized by the appropriate selection of parameters (values) for its execution. Where the adjustment of a parameter is required, this parameter will be tested until viable results are obtained. Normally, such adjustments are made by the developer deploying the metaheuristic. The quality of the results of a test instance [The term instance is used to refer to the assignment of values to the input variables of a problem.] will not be transferred to the instances that were not tested yet and its feedback may require a slow process of “trial and error” where the algorithm has to be adjusted for a specific application. Within this context of metaheuristics the Reactive Search emerged defending the integration of machine learning within heuristic searches for solving complex optimization problems. Based in the integration that the Reactive Search proposes between machine learning and metaheuristics, emerged the idea of putting Reinforcement Learning, more specifically the Q-learning algorithm with a reactive behavior, to select which local search is the most appropriate in a given time of a search, to succeed another local search that can not improve the current solution in the VNS metaheuristic. In this work we propose a reactive implementation using Reinforcement Learning for the self-tuning of the implemented algorithm, applied to the Symmetric Travelling Salesman Problem.     

A metaheuristic approach for the sequencing by hybridization problem with positive and negative errors

This work introduces a metaheuristic method for the reconstruction of the DNA string from its l-mer content in the presence of large amounts of positive and negative errors. The procedure consists of three parts: the formulation of the problem as an asymmetric traveling salesman problem (ATSP), a technique for handling the positive errors and an optimization algorithm that solves the formulated problem. The optimization algorithm is a variation of the threshold accepting method with intense local search and its function is controlled by a size diminishing shell. The optimization algorithm is used consecutively on ATSPs of continuously decreasing sizes till it reaches a final solution. The proposed method provides solutions of better quality compared to algorithms in the recent bibliography.     

A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants

This paper proposes a mathematical model, valid inequalities and polyhedral results for the minimum labeling Hamiltonian cycle problem. This problem is defined on an unweighted graph in which each edge has a label. The aim is to determine a Hamiltonian cycle with the least number of labels. We also define two variants of this problem by assigning weights to the edges and by considering the tour length either as an objective or as a constraint. A branch-and-cut algorithm for the three problems is developed, and computational results are reported on randomly generated instances and on modified instances from TSPLIB.     

Honey bees mating optimization algorithm for the Euclidean traveling salesman problem

This paper introduces a new hybrid algorithmic nature inspired approach based on Honey Bees Mating Optimization for successfully solving the Euclidean Traveling Salesman Problem. The proposed algorithm for the solution of the Traveling Salesman Problem, the Honey Bees Mating Optimization (HBMOTSP), combines a Honey Bees Mating Optimization (HBMO) algorithm, the Multiple Phase Neighborhood Search-Greedy Randomized Adaptive Search Procedure (MPNS-GRASP) algorithm and the Expanding Neighborhood Search Strategy. Besides these two procedures, the proposed algorithm has, also, two additional main innovative features compared to other Honey Bees Mating Optimization algorithms concerning the crossover operator and the workers. The main contribution of this paper is that it shows that the HBMO can be used in hybrid synthesis with other metaheuristics for the solution of the TSP with remarkable results both to quality and computational efficiency. The proposed algorithm was tested on a set of 74 benchmark instances from the TSPLIB and in all but eleven instances the best known solution has been found. For the rest instances the quality of the produced solution deviates less than 0.1% from the optimum.     

The double traveling salesman problem with multiple stacks: A variable neighborhood search approach

The double traveling salesman problem with multiple stacks (DTSPMS) is a vehicle routing problem that consists on finding the minimum total length tours in two separated networks, one for pickups and one for deliveries. A set of orders is given, each one consisting of a pickup location and a delivery location, and it is required to send an item from the former location to the latter one. Repacking is not allowed, but collected items can be packed in several rows in such a way that each row must obey the LIFO principle. In this paper, a variable neighborhood search approach using four new neighborhood structures is presented to solve the problem.     

Metaheuristics for the traveling salesman problem with pickups, deliveries and handling costs

This paper studies the Traveling Salesman Problem with Pickups, Deliveries, and Handling Costs. The subproblem of minimizing the handling cost for a fixed route is analyzed in detail. It is solved by means of an exact dynamic programming algorithm with quadratic complexity and by an approximate linear time algorithm. Three metaheuristics integrating these solution methods are developed. These are based on tabu search, iterated local search and iterated tabu search. The three heuristics are tested and compared on instances adapted from the related literature. The results show that the combination of tabu search and exact dynamic programming performs the best, but using the approximate linear time algorithm considerably decreases the CPU time at the cost of slightly worse solutions.     

一种SAT邻域的快速搜索算法

用局部搜索算法求解SAT问题．通常都需要在较大的邻域中。寻找合适的邻解。如果对邻域中的每个邻解。都通过重新判断每个子句是否为可满足来得到其可满足的子句个数．则时间耗费较多。已经有一些经典的处理方法．例如通过修改邻域结构．来减小搜索空间。从另外一个角度来考虑搜索过程．根据当前解和邻解的内在关系．介绍一种SAT邻域的快速搜索算法。该算法能在不影响解质量的前提下．快速寻找合适的邻解．从而进一步提高局部搜索算法的求解速度。另外．该算法还提供用于提高解质量的信息。有助于研究新的局部搜索算法。     

Hybrid Adaptive Large Neighborhood Search for the Optimal Statistic Median Problem

In this paper, the problem of maximizing the median of a convex combination of vectors having important applications in finance is considered. The objective function is a highly nonlinear, nondifferentiable function with many local minima and the problem was shown to be APX hard. We present two hybrid Large Neighborhood Search algorithms that are based on mixed-integer programs and include a time limit for their running times. We have tested the algorithms on three testbeds and showed their superiority compared to other state-of-the-art heuristics for the considered problem. Furthermore, we achieved a significant reduction in running time for large instances compared to solving it exactly while retaining high quality of the solutions returned.     

A new formulation and approach for the black and white traveling salesman problem

This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.     

Visualizing proportions and dissimilarities by Space-filling maps: A Large Neighborhood Search approach

In this paper we address the problem of visualizing a set of individuals, which have attached a statistical value given as a proportion, and a dissimilarity measure. Each individual is represented as a region within the unit square, in such a way that the area of the regions represent the proportions and the distances between them represent the dissimilarities. To enhance the interpretability of the representation, the regions are required to satisfy two properties. First, they must form a partition of the unit square, namely, the portions in which it is divided must cover its area without overlapping. Second, the portions must be made of a connected union of rectangles which verify the so-called box-connectivity constraints, yielding a visualization map called Space-filling Box-connected Map (SBM). The construction of an SBM is formally stated as a mathematical optimization problem, which is solved heuristically by using the Large Neighborhood Search technique. The methodology proposed in this paper is applied to three real-world datasets: the first one concerning financial markets in Europe and Asia, the second one about the letters in the English alphabet, and finally the provinces of The Netherlands as a geographical application.     

AnO(logk)-approximation algorithm for thek minimum spanning tree problem in the plane

Givenn points in the Euclidean plane, we consider the problem of finding the minimum tree spanning anyk points. The problem isNP-hard and we give anO(logk)-approximation algorithm.     

A novel discretization scheme for the close enough traveling salesman problem

This paper addresses a variant of the Euclidean traveling salesman problem in which the traveler visits a node if it passes through the neighborhood set of that node. The problem is known as the close-enough traveling salesman problem. We introduce a new effective discretization scheme that allows us to compute both a lower and an upper bound for the optimal solution. Moreover, we apply a graph reduction algorithm that significantly reduces the problem size and speeds up computation of the bounds. We evaluate the effectiveness and the performance of our approach on several benchmark instances. The computational results show that our algorithm is faster than the other algorithms available in the literature and that the bounds it provides are almost always more accurate.     

Hybridizations of evolutionary algorithms with Large Neighborhood Search

Recent developments of evolutionary algorithms (EAs) for discrete optimization problems are often characterized by the hybridization of EAs with local search methods, in particular, with Large Neighborhood Search. In this survey, we consider some of the most promising directions of this kind of hybridization and provide examples in the context of well-known optimization problems. We distinguish different approaches by the algorithmic components in which they make use of Large Neighborhood Search: initialization, recombination and the local improvement stages of hybrid EAs.     

结合变邻域搜索的竞争Hopfield神经网络解决最大分散度问题

提出一种结合变邻域搜索的离散竞争Hopfield神经网络,用于求解最大分散度问题。为了克服神经网络易陷入局部最小值的问题,将变邻域搜索的思想引入到离散竞争Hopfield神经网络中,一旦网络陷入局部最小值,变邻域搜索能帮助神经网络动态改变搜索邻域,从而跳出局部最小值去搜寻更优的解。最后,针对最大分散度问题的实验结果表明,提出的算法具有良好的性能。     

Heuristic methods for the optimal statistic median problem

We consider the problem of finding the convex combination of vectors for which the median is maximum. The objective function of this problem is non-concave and non-differentiable, with many local optima that can trap any subgradient algorithm. So we analyzed and tested some heuristic procedures to find optimal or near-optimal solutions. First, we introduced a variant of Random Restart, in which starting solutions are the vertices of the simplex, and we proved that small size problems are solved by this procedure. Then, we analyzed two versions of Variable Neighborhood Search that are used to explore the whole space of the feasible solutions, and we show that the continuous version is more powerful than the discrete version.