Catálogo de publicaciones - libros

Scalability constitutes a key property in Peer-to-Peer environments. One way to foster this property is the introduction of super-peers, a concept which has gained widespread acceptance in recent years. However, the problem of finding the set of super-peers that minimizes the total communication cost is NP-hard. We present a new heuristic based on Evolutionary Techniques and Local Search to solve this problem. Using actual Internet distance measurements, we demonstrate the savings in total communication cost attainable by such a super-peer topology. Our heuristic can also be applied to the more general Uncapacitated Single Assignment -Hub Median Problem. The Local Search is then further enhanced by generalized . We show that our heuristic is competitive with other heuristics even in this general problem, and present new best solutions for the largest instances in the well known Australia Post data set.

This paper studies the Split Delivery Vehicle Routing problem (SDVRP), a variant of the VRP in which multiple visits to customers are allowed. This NP-hard problem is solved by a recent metaheuristic called Memetic Algorithm with Population Management or MA|PM (Sörensen, 2003). It consists in a genetic algorithm, combined with a local search procedure for intensification and a distance measure to control population diversity. Special moves dedicated to split deliveries are introduced in the local search. This solution approach is evaluated and compared with the tabu search algorithm of Archetti et al. (2006) and with lower bounds designed by Belenguer et al. (2000). Our method outperforms the tabu search both in solution quality and running time. On a set of 49 instances, it improves the best-known solution 32 times. The savings obtained confirm the interest and the power of the MA|PM.

We present two hybrid Metaheuristics, a hybrid Iterated Local Search and a hybrid Simulated Annealing, for solving real-world extensions of the Vehicle Routing Problem with Time Windows. Both hybrid Metaheuristics are based on the same neighborhood generating operators and local search procedures. The initial solutions are obtained by the Coefficient Weighted Distance Time Heuristics with automated parameter tuning. The strategies are compared in an empirical study on four real-world problems. A performance measure is used that also considers multiple restarts of the algorithms.

In this paper the influence of structural information obtained from a problem relaxation on the performance of an ACO algorithm for the symmetric TSP is studied. More precisely, a very simple ACO algorithm is guided by including Minimal Spanning Tree information into the visibility. Empirical results on a large number of benchmark instances from TSPLIB are presented. The paper concludes with remarks on some more elaborate ideas for using problem relaxation within ACO.

This paper proposes a local search algorithm that makes use of a complex neighborhood relation based on a hybridization with a constructive heuristics for the classical resource-constrained project scheduling problem (RCPSP).

We perform an experimental analysis to tune the parameters of our algorithm and to compare it with a tabu search based on a combination of neighborhood relations borrowed from the literature. Finally, we show that our algorithm is also competitive with the ones reported in the literature.

This paper deals with the Permutation Flow Shop scheduling problem with the objective of minimizing total flow time, and therefore reducing in-process inventory. A new hybrid metaheuristic Genetic Algorithm - Cluster Search is proposed for the scheduling problem solution. The performance of the proposed method is evaluated and results are compared with the best reported in the literature. Experimental tests show the new method superiority for the test problems set, regarding the solution quality.

Optimization in sports is a field of increasing interest. A novel problem in sports management is the Referee Assignment Problem, in which a limited number of referees with different qualifications and availabilities should be assigned to a set of games already scheduled. We extend and improve a previous three-phase approach for this problem, based on a constructive heuristic, a repair heuristic to make the initial solutions feasible, and an ILS improvement heuristic. We propose a new constructive algorithm based on a greedy criterion to build initial solutions. Furthermore, we develop a hybridization strategy in which a mixed integer programming exact algorithm replaces the original neighborhood-based local search within the ILS heuristic. Computational experiments are performed for large realistic instances. The use of time-to-target-solution-value plots is emphasized in the evaluation of the numerical results, illustrating the efficiency and the robustness of the new approach. The proposed hybridization of MIP with local search can be extended to other metaheuristics and applications, opening a new research avenue to more robust algorithms.

Sudoku is a notorious logic-based puzzle that is popular with puzzle enthusiasts the world over. From a computational perspective, Sudoku is also a problem that belongs to the set of NP-complete problems, implying that we cannot hope to find a polynomially bounded algorithm for solving the problem in general. Considering this feature, in this paper we demonstrate how a metaheuristic-based method for solving Sudoku puzzles (which was reported by the same author in an earlier paper), can actually be significantly improved if it is coupled with Constraint Programming techniques. Our results, which have been gained through a large amount of empirical work, suggest that this combination of techniques results in a hybrid algorithm that is significantly more powerful than either of its constituent parts.

Finding appropriate values for the parameters of an algorithm is a challenging, important, and time consuming task. While typically parameters are tuned by hand, recent studies have shown that automatic tuning procedures can effectively handle this task and often find better parameter settings. has been proposed specifically for this purpose and it has proven to be very effective in a number of cases. is a racing algorithm that starts by considering a number of candidate parameter settings and eliminates inferior ones as soon as enough statistical evidence arises against them. In this paper, we propose two modifications to the usual way of applying that on the one hand, make it suitable for tuning tasks with a very large number of initial candidate parameter settings and, on the other hand, allow a significant reduction of the number of function evaluations without any major loss in solution quality. We evaluate the proposed modifications on a number of stochastic local search algorithms and we show their effectiveness.

In recent years it has been shown by means of practical applications that the incorporation of branch & bound concepts within construction-based metaheuristics can be very useful. In this paper, we attempt to give an explanation of why this type of hybridization works. First, we introduce the concepts of primal and dual problem knowledge, and we show that metaheuristics only exploit the primal problem knowledge. In contrast, hybrid metaheuristic that include branch & bound concepts exploit both the primal and the dual problem knowledge. After giving a survey of these techniques, we conclude the paper with an application example that concerns the longest common subsequence problem.