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 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.     

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

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

An Adaptive Large Neighborhood Search for an E-grocery Delivery Routing Problem

Online shopping has become ever more indispensable to many people with busy schedules who have a growing need for services ranging for a wide variety of goods, which include standard (or “staple”) goods as well as “premium” goods, i.e. goods such as organic food, specialty gifts, etc. that offer higher value to consumers and higher profit margins to retailers. In this paper, we introduce a new mathematical programming formulation and present an efficient solution approach for planning the delivery services of online groceries to fulfill this diverse consumer demand without incurring additional inventory costs. We refer to our proposed model as the E-grocery Delivery Routing Problem (EDRP) as it generically represents a family of problems that an online grocery is likely to face. The EDRP is based on a distribution network where premium goods are acquired from a set of external vendors at multiple locations in the supply network and delivered to customers in a single visit. To solve this problem, we develop an improved Adaptive Large Neighborhood Search (ALNS) heuristic by introducing new removal, insertion, and vendor selection/allocation mechanisms. We validate the performance of the proposed ALNS heuristic through an extensive computational study using both the well-known Vehicle Routing Problem with Time Windows instances of Solomon and a set of new benchmark instances generated for the EDRP. The results suggest that the proposed solution methodology is effective in obtaining high quality solutions fast.     

Multiple Phase Neighborhood Search-GRASP for the Capacitated Vehicle Routing Problem

Greedy Randomized Adaptive Search Procedure (GRASP) has been proved to be a very efficient algorithm for the solution of the Traveling Salesman Problem. Also, it has been proved that expanding the local search with the use of two or more different local search strategies helps the algorithm to avoid trapping in a local optimum. In this paper, a new modified version of GRASP, called Multiple Phase Neighborhood Search-GRASP (MPNS-GRASP), for the solution of the Vehicle Routing Problem is proposed. In this method, a stopping criterion based on Lagrangean Relaxation and Subgradient Optimization is utilized. In addition, a different way for expanding the neighborhood search is used based on a new strategy, the Circle Restricted Local Search Moves strategy. The algorithm was tested on two sets of benchmark instances and gave very satisfactory results. In both sets of instances the results have solution qualities with average values near to the optimum values and in a number of them the algorithm finds the optimum. The computational time of the algorithm is decreased significantly compared to other heuristic and metaheuristic algorithms due to the fact that the new strategy, the Expanding Neighborhood Search Strategy, is used.     

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.     

求解UCARPP问题的变邻域搜索算法

针对无向网络中带有收益值有容限的弧路径问题,提出一种变邻域搜索算法。生成需求边的有序列,以相同概率初始化每条边的方向,采用分割算法构造初始解,运用6种邻域结构进行广域搜索,使用局部搜索算法改进解,利用旋轮法选择邻域结构。实验结果表明,该算法能提高效率,避免早期陷入局部最优,稳定性较好。     

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.     

禁忌搜索与GA算法结合求解背包问题

综合禁忌搜索和标准遗传算法尝试求解0-1背包问题,在此之前文章先简要介绍了这两种算法,并把这两种算法分别与文章中所述的综合算法进行了比较,给出了具体的算法描述和求解过程.通过算例仿真的实验对各个算法的流程、仿真结果、评价数据进行比较,分析了各自的优缺点.     

Clustering Search for the Berth Allocation Problem

This work presents a new approach to the Berth Allocation Problem (BAP) for ships in ports. Due to the increasing demand for ships carrying containers, the BAP can be considered as a major optimization problem in marine terminals. In this paper, the BAP is considered as dynamic and modeled in discrete case and we propose a new alternative to solve it. The proposed alternative is based on applying the Clustering Search (CS) method using the Simulated Annealing (SA) for solutions generation. The CS is an iterative method which divides the search space in clusters and it is composed of a metaheuristic for solutions generation, a grouping process and a local search heuristic. The computational results are compared against recent methods found in the literature.     

Variable Neighborhood Search for extremal vertices : The AutoGraphiX-III system

More than fifteen years after the beginning of the development of AutoGraphiX (AGX), a third version of the software is made available. Since the program was rewritten from scratch, it was the opportunity to look forward and consider new avenues. From the user׳s point of view, the interface is completely changed, which allows the display of multiple information which was not possible in the previous versions. However, one of the main improvements is that it is designed to help researchers in the field of complex networks. In these days when increasing research is applied to complex networks (such as social networks), the use of quantities related to vertices, indicating the centrality (the importance of an actor in the network measured as a topological indicator) naturally leads researchers toward the mathematical study of these quantities. This new paradigm implies a complete change in the optimization algorithm that now natively handles multi objective optimization problems involving vertex-related measures.     

车辆合乘问题的分布式复合变邻域搜索算法

针对长期车辆合乘问题(long-term carpooling problem,LTCPP),提出一种基于分布式的复合变邻域搜索算法,利用分布式计算的优势可快速求解出大规模用户的合乘匹配方案。首先构建带有时间窗约束和车容量约束的数学模型,建立成本计算的目标函数;然后按复合距离优先算法将所有用户分配到各合乘小组中,最终得到满足约束条件的初始合乘方案。通过对变邻域搜索算法进行分布式处理,使算法可以对初始合乘方案进行并行迭代优化计算,得到最终的合乘方案。实验结果表明,该算法在速度和大规模问题求解质量上具有明显的优势。     

一种求解车间作业调度问题的混合邻域结构搜索算法

车间作业调度问题是优化组合中一个著名的难题,问题的目标是在满足约束条件的前提下,使调度的加工周期尽可能小。文章中提出了利用新的混合邻域结构进行搜索来求解车间作业调度问题。对于算法关键的邻域构造问题以及跳坑策略给出了提高算法优度的解决方案。采用43个不同规模和难度的国际标准算例做为本算法的测试实验集,39个算例找到了最优解,其中包括著名的难例FT10。与当前国外学者提出的一种先进算法进行了比较,算法的优度高于被比较的先进算法。     

时空相关的混载校车路径问题邻域搜索

为节约混载校车路径问题求解过程中邻域解搜索的时间,引入时空距离和时空相关度概念,将邻域搜索空间限定在合理的范围内.该算法首先计算站点间的时空距离,再附加上简单约束的预判断,从而得到时空相关度矩阵.然后对于任意学生乘车站点,将其他可能与之直接相连的站点按照时空相关度排序,形成一个邻接列表.在邻域搜索过程中,通过限定邻接列表长度,仅尝试最终接受概率较大的一部分移动操作,以此缩小邻域搜索空间,从而提高算法效率.在国际标准案例上的测试结果表明,基于时空相关度的搜索策略能在基本不降低求解质量的情况下,平均节省50％以上的求解时间.     

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.     

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

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

Variable neighborhood descent heuristic for solving reverse logistics multi-item dynamic lot-sizing problems

The multi-product dynamic lot sizing problem with product returns and recovery is an important problem that appears in reverse logistics and is known to be NP-hard. In this paper we propose an efficient variable neighborhood descent heuristic algorithm for solving this problem. Furthermore, we present a new benchmark set with the largest instances in the literature. The computational results demonstrate that our approach outperforms the state-of-the-art Gurobi optimizer.     

分阶搜索法对雪尔维斯特问题的算法分析

本文给出了分阶搜索法的定义和推论,并探讨了一道世界著名数学难题“雪尔维斯特问题”三阶搜索的问题表示与算法分析。