We present a novel multi-population biased random-key genetic algorithm (BRKGA) for the 2D and 3D bin packing problem. The approach uses a maximal-space representation to manage the free spaces in the bins. The proposed algorithm uses a decoder based on a novel placement procedure within a multi-population genetic algorithm based on random keys. The BRKGA … Read more
The single row facility layout is the NP-Hard problem of arranging facilities with given lengths on a line, so as to minimize the weighted sum of the distances between all pairs of facilities. Owing to the computational complexity of the problem, researchers have developed several heuristics to obtain good quality solutions. In this paper, we … Read more
Facility location-network design problems seek to simultaneously determine the locations of fa- cilities and the design of the network connecting the facilities so as to best serve a set of clients accessing the facilities via the network. Here we study a dynamic (multi-period) version of the problem, subject to a budget constraint limiting the investment … Read more
A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. GRASP heuristics are multistart procedures which apply local search to a set of starting solutions generated with a randomized greedy algorithm or semi-greedy method. The best local optimum found over the iterations is returned as the heuristic solution. Path-relinking is a search … Read more
The Capacitated Arc Routing Problem (CARP) stands among the hardest combinatorial problems to solve or to find high quality solutions. This becomes even more true when dealing with large instances. This paper investigates methods to improve on lower and upper bounds of instances on graphs with over two hundred vertices and three hundred edges, dimensions … Read more
In this paper, we describe brkgaAPI, an efficient and easy-to-use object oriented application programming interface for the algorithmic framework of biased random-key genetic algorithms. Our cross-platform library automatically handles the large portion of problem-independent modules that are part of the framework, including population management and evolutionary dynamics, leaving to the user the task of implementing … Read more
The document describes COIN-OR METSlib, a C++ framework for local search based metaheuristics. METSlib has been used to implement a massively parallel VRP algorithm, a state of the art Vertex Coloring Problem solver, a Timetabling software, and in many other projects. Article Download View COIN-OR METSlib: a Metaheuristics Framework in Modern C++.
In this paper we propose an adaptation of the GRASP metaheuristic to solve multi-objective combinatorial optimization problems. In particular we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with path-relinking for single-objective optimization. In this paper, we propose different … Read more
In many telecommunication network architectures a given set of client nodes must be served by different kinds of facility, which provide di fferent services and have diff erent capabilities. Such facilities must be located and dimensioned in the design phase. We tackle a particular location problem in which two sets of facilities, mid level and high level, … Read more
The use of metaheuristics in Multi-objective Combinatorial Optimization, particularly Ant Colony Optimization (ACO), has grown recently. This paper proposes an approach where multi-species ants compete for food resources. Each species has its own search strategy and do not access pheromone information of other species. As in nature, successful ant populations are allowed to grow, whereas … Read more