共查询到10条相似文献,搜索用时 93 毫秒
1.
Félix García-López Belén Melián-Batista José A. Moreno-Pérez J. Marcos Moreno-Vega 《Journal of Heuristics》2002,8(3):375-388
The Variable Neighborhood Search (VNS) is a recent metaheuristic that combines series of random and improving local searches based on systematically changed neighborhoods. When a local minimum is reached, a shake procedure performs a random search. This determines a new starting point for running an improving search. The use of interchange moves provides a simple implementation of the VNS algorithm for the p-Median Problem. Several strategies for the parallelization of the VNS are considered and coded in C using OpenMP. They are compared in a shared memory machine with large instances. 相似文献
2.
Charles Audet Vincent Béchard Sébastien Le Digabel 《Journal of Global Optimization》2008,41(2):299-318
This paper proposes a way to combine the Mesh Adaptive Direct Search (MADS) algorithm, which extends the Generalized Pattern
Search (GPS) algorithm, with the Variable Neighborhood Search (VNS) metaheuristic, for nonsmooth constrained optimization.
The resulting algorithm retains the convergence properties of MADS, and allows the far reaching exploration features of VNS
to move away from local solutions. The paper also proposes a generic way to use surrogate functions in the VNS search. Numerical
results illustrate advantages and limitations of this method. 相似文献
3.
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. 相似文献
4.
Teodor Gabriel Crainic Michel Gendreau Pierre Hansen Nenad Mladenović 《Journal of Heuristics》2004,10(3):293-314
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. 相似文献
5.
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. 相似文献
6.
This paper presents a Variable Neighborhood Search (VNS) algorithm for the container loading problem. The algorithm combines
a constructive procedure based on the concept of maximal-space, with five new movements defined directly on the physical layout
of the packed boxes, which involve insertion and deletion strategies.
The new algorithm is tested on the complete set of Bischoff and Ratcliff problems, ranging from weakly to strongly heterogeneous
instances, and outperforms all the reported algorithms which have used those test instances. 相似文献
7.
A variable neighborhood search for the capacitated arc routing problem with intermediate facilities 总被引:2,自引:0,他引:2
Michael Polacek Karl F. Doerner Richard F. Hartl Vittorio Maniezzo 《Journal of Heuristics》2008,14(5):405-423
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. 相似文献
8.
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. 相似文献
9.
Sylvain Perron Pierre Hansen Sbastien Le Digabel Nenad Mladenovi 《European Journal of Operational Research》2010,202(3):864-879
We examine the example of a multinational corporation that attempts to maximize its global after tax profits by determining the flow of goods, the transfer prices, and the transportation cost allocation between each of its subsidiaries. Vidal and Goetschalckx [Vidal, C.J., Goetschalckx, M., 2001. A global supply chain model with transfer pricing and transportation cost allocation. European Journal of Operational Research 129 (1), 134–158] proposed a bilinear model of this problem and solved it by an Alternate heuristic. We propose a reformulation of this model reducing the number of bilinear terms and accelerating considerably the exact solution. We also present three other solution methods: an implementation of Variable Neighborhood Search (VNS) designed for any bilinear model, an implementation of VNS specifically designed for the problem considered here and an exact method based on a branch and cut algorithm. The solution methods are tested on artificial instances. These results show that our implementation of VNS outperforms the two other heuristics. The exact method found the optimal solution of all small instances and of 26% of medium instances. 相似文献
10.
This paper presents a General Variable Neighborhood Search (GVNS) heuristic for the Traveling Salesman Problem with Time Windows (TSPTW). The heuristic is composed by both constructive and optimization stages. In the first stage, the heuristic constructs a feasible solution using VNS, and in the optimization stage the heuristic improves the feasible solution with a General VNS heuristic. Both constructive and optimization stages take advantage of elimination tests, partial neighbor evaluation and neighborhood partitioning techniques. Experimental results show that this approach is efficient, reducing significantly the computation time and improving some best known results from the literature. 相似文献