Variable neighborhood search for minimum cost berth allocation

The berth allocation problem is to allocate space along the quayside to incoming ships at a container terminal in order to minimize some objective function. We consider minimization of total costs for waiting and handling as well as earliness or tardiness of completion, for all ships. We assume ships can arrive at any given time, i.e., before or after the berths become available. The resulting problem, which subsumes several previous ones, is expressed as a linear mixed 0–1 program. As it turns out to be too time-consuming for exact solution of instances of realistic size, a Variable Neighborhood Search (VNS) heuristic is proposed, and compared with Multi-Start (MS), a Genetic Search algorithm (GA) and a Memetic Search algorithm (MA). VNS provides optimal solutions for all instances solved to optimality in a previous paper of the first two authors and outperforms MS, MA and GA on large instances.     

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.     

A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

This paper presents a solution methodology for the heterogeneous fleet vehicle routing problem with time windows. The objective is to minimize the total distribution costs, or similarly to determine the optimal fleet size and mix that minimizes both the total distance travelled by vehicles and the fixed vehicle costs, such that all problem’s constraints are satisfied. The problem is solved using a two-phase solution framework based upon a hybridized Tabu Search, within a new Reactive Variable Neighborhood Search metaheuristic algorithm. Computational experiments on benchmark data sets yield high quality solutions, illustrating the effectiveness of the approach and its applicability to realistic routing problems. This work is supported by the General Secretariat for Research and Technology of the Hellenic Ministry of Development under contract GSRT NM-67.     

Two local search approaches for solving real-life car sequencing problems

The NP-hard problem of car sequencing appears as the heart of the logistic process of many car manufacturers. The subject of the ROADEF’2005 challenge addressed a car sequencing problem proposed by the car manufacturer RENAULT, more complex than the academic problem generally addressed in the literature. This paper describes two local search approaches for this problem. In the first part, a new approach by very large-scale neighborhood search is presented. This approach, designed during the qualification stage preceding the final, is based on an original integer linear programming formulation. The second part is dedicated to the approach which enabled us to win the ROADEF’2005 challenge. Inspired by the latest works on the subject, this one is based on very fast explorations of small neighborhoods. Our contribution here is mainly algorithmic, in particular by showing how much exploiting invariants speeds up the neighborhood evaluation and contributes to the diversification of the search. Finally, the two approaches are compared and discussed through an extensive computational study on RENAULT’s benchmarks. The main conclusion drawn at this point is that sophisticated metaheuristics are useless to solve car sequencing problems. More generally, our victory on ROADEF’2005 challenge demonstrates that algorithmic aspects, sometimes neglected, remain the key ingredients for designing and engineering high-performance local search heuristics.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

基于小波域马尔可夫随机场模型的压缩传感图像重构

目前在压缩传感重构算法中利用图像的可稀疏性表示先验知识,从比奈奎斯特采样少得多的观测值中恢复原始图像。除了稀疏性之外,邻域系数的相关性也可以作为先验知识加速重构算法收敛。为了克服目前算法中没有利用邻域系数相关性的缺点,提出了基于小波域马尔可夫随机场模型的压缩传感图像重构算法,根据显著性度量对变换系数进行分类得到具有马尔可夫性的初始掩模,利用ICM算法完成掩模优化,实现系数更新,并将算法与未考虑邻域相关性的算法进行了比较。实验结果证明了算法的有效性。     

Codimension Two PL Embeddings of Spheres with Nonstandard Regular Neighborhoods

For a given polyhedron K(?)M,the notation RM(K)denotes a regular neigh- borhood of K in M.The authors study the following problem:find all pairs(m,k) such that if K is a compact k-polyhedron and M a PL m-manifold,then R_M(f(K))≌R_M(g(K))for each two homotopic PL embeddings f,g:K→M.It is proved that R_S~(k 2)(S~k)(?)S~k×D~2 for each k(?)2 and some PL sphere S~k(?)S~(k 2)(even for any PL sphere S~k(?)S~(K 2)having an isolated non-locally flat point with the singularity S~(k-1)(?) S~(k 1)such thatπ_1(S~(k 1)-S~(k-1))(?)Z).     

Scheduling periodic customer visits for a traveling salesperson

The problem considered in this paper deals with determining daily routes for a traveling salesperson who provides customers in Upper Austria with product range information of a large, global food wholesaler. Each customer has to be visited at least once a year, with some customers requiring up to one visit per month. Further, some customers may not be visited each day of the week. Our decision support system uses a commercial GIS software to extract customer data for input into the optimization procedure and to visualize the results obtained by the algorithm. The optimization approach is based on the variable neighborhood search algorithm which assigns customers to days and determines routes for the salesperson for each day with the primary objective to minimize the total travel time of the salesperson. Another objective studied is to minimize the number of days needed by the salesperson to visit all customers in a given month. Further we analyze the effects of changes in the business environment like increases in the amount or flexibility of the salesperson’s working time and variations in the possible days for customer visits. Finally, we enrich the objective function by considering periodicity requirements for customer visits. Specifically, we penalize irregular schedules, where the time between two successive customer visits varies.     

Remarks on the second neighborhood problem

The second neighborhood conjecture of Seymour asserts that for any orientation G = (V,E), there exists a vertex υ ∈ V so that |N⁺(υ)| ≤ |N⁺⁺(υ)|. The conjecture was resolved by Fisher for tournaments. In this article, we prove the second neighborhood conjecture for several additional classes of dense orientations. We also prove some approximation results, and reduce an asymptotic version of the conjecture to a finite case. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 208–220, 2007     

基于局部均值的K-近质心近邻光谱分类

天体光谱包含着许多重要的关于天体的物理和化学信息,如天体表面的有效温度、重力加速度以及化学丰度等,天体光谱的处理和分析对天文研究具有重要的科学意义。一些大型巡天计划的实施(如SDSS,LAMOST等)使我们获得了海量的天文光谱数据,因此天文光谱数据的自动分类成为重要的科学研究课题,然而面对如此海量的光谱数据,一些传统的光谱自动分类方法已经不适用,迫切需要寻找高效率的光谱自动分类技术。研究了基于局部均值的K-近质心近邻(local mean-based K-nearest centroid neighbor,LMKNCN)算法在恒星(Star)、星系(Galaxy)和类星体(Quasar,QSO)的光谱分类中的应用。LMKNCN算法的基本思想是根据近质心近邻原则,从每一类训练样本集中为待测样本点选取k个近质心近邻点,然后根据每一类中所选取的k个近质心近邻点的均值点到待测样本点x的距离来判别x的所属类别。针对美国SDSS-DR8的天体光谱数据,对比了K-近邻、K-近质心近邻、LMKNCN三种算法在恒星、星系和类星体的光谱分类中所表现的性能,结果表明三种方法中,LMKNCN算法对这三种光谱的识别率高于其他两种算法或者与其相当,而且其平均分类正确率高于另外两种算法,特别是在类星体的识别率上表现的更好。表明了该算法对天文光谱大数据的快速处理和有效利用具有重要的意义。