Mauricio G.C. Resende Telecommunication systems make use of optical signals to transmit information. The strength of a signal in an optical network deteriorates and loses power as it gets farther from the source, mainly due to attenuation. Therefore, to enable the signal to arrive at its intended destination with good quality, it is necessary to regenerate it periodically … Read more
One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding … Read more
This paper presents a multi-population biased random-key genetic algorithm (BRKGA) for the Single Container Loading Problem (CLP) where several rectangular boxes of different sizes are loaded into a single rectangular container. The approach uses a maximal-space representation to manage the free spaces in the container. The proposed algorithm hybridizes a novel placement procedure with a … Read more
The problem of routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned different wavelengths. This problem was shown to be NP-hard when the objective is to … Read more
Path-relinking is major enhancement to heuristic search methods for solving combinatorial optimization problems, leading to significant improvements in both solution quality and running times. We review its fundamentals and implementation strategies, as well as advanced hybridizations with more elaborate metaheuristic schemes such as genetic algorithms and scatter search. Numerical examples are discussed and algorithms compared … Read more
GRASP with path-relinking (GRASP+PR) is a metaheuristic for finding optimal or near-optimal solutions of combinatorial optimization problems. This paper proposes a new automatic parameter tuning procedure for GRASP+PR heuristics based on a biased random-key genetic algorithm (BRKGA). Given a GRASP+PR heuristic with N input parameters, the tuning procedure makes use of a BRKGA in a … Read more
Random-key genetic algorithms were introduced by Bean (1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are … Read more
This paper proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with N nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2, …, … Read more
Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic – based on the CGRASP and GENCAN methods – for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP-GENCAN … Read more
This paper presents a biased random-keys genetic algorithm for the Resource Constrained Project Scheduling Problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all … Read more