1,721,003 research outputs found
A Tabu Search algorithm for solving chance-constrained programs
No full textSolution of real world problems have to deal with some uncertainties. This is particularly true for
the planning of services whose requests are unknown a priori.
Several approaches for solving stochastic problems are reported in the literature. Metaheuristics
seem to be a powerful tool for computing good and robust solutions. However, the efficiency of algorithms based on Local Search, such as Tabu Search, suffers from the complexity of evaluating
the objective function after each move.
In this paper, we propose a Tabu Search algorithm which exploits simulation approach to solve chance-constrained programs. We prove its efficiency reporting the results of extensive computational experiments
Better and faster solutions for the maximum diversity problem
Full text linkThe aim of the Maximum Diversity Problem (MDP) is to extract a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise distances between the elements of M is maximum. This problem, introduced by Glover [7], has been deeply studied using GRASP methodologies [6, 1, 17, 2, 16]. Usually, effective algorithms owe their success more to the careful exploitation of problem-specific features than to the application of general-purpose methods. A solution for MDP has a very simple structure which can not be exploited for sophisticated neighborhood search. This paper explores the performance of three alternative solution approaches, that is Tabu Search, Variable Neighborhood Search and Scatter Search, comparing them with those of best GRASP algorithms in literature. We also focus our attention on the comparison of these three methods applied in their pure form
Comparing local search metaheuristics for the maximum diversity problem
No full textThe Maximum Diversity Problem (MDP) requires to extract a subset M of given cardinality from a set N, maximising the sum of the pair-wise diversities between the extracted elements. The MDP has recently been the subject of much research, and several sophisticated heuristics have been proposed to solve it. The present work compares four local search metaheuristics for the MDP, all based on the same Tabu Search procedure, with the aim to identify what additional elements provide the strongest improvement. The four metaheuristics are an Exploring Tabu Search, a Scatter Search, a Variable Neighbourhood Search and a simple Random Restart algorithm. All of them prove competitive with the best algorithms proposed in the literature. Quite surprisingly, the best ones are the simple Random Restart algorithm and a Variable Neighbourhood Search algorithm with an unusual parameter setting, which makes it quite close to random restart. Although this is probably related to the elementary structure of the MDP, it also suggests that, more often than expected, simpler algorithms might be better
A simulation model for trust and reputation system evaluation in a P2P network
No full textA peer-to-peer (P2P) network is an exchange community of anonymous peers or individuals. The evolution of P2P network has determined the need of trust and reputation systems (TRS) in order to improve the reliability of local interactions: collecting in some way the local experiences, the TRS assesses the possibility that an individual has a malicious behavior, i.e., he cheats other individuals. In this paper we present an agent-based simulation model for the evaluation of a generic TRS within a decentralized P2P network. We describe some minimal requirements that, in our opinion, every P2P simulators should have. Moreover, we propose a completemodel of peers in which the behavior of both good and malicious peers is accurately defined
Composing medical crews with equity and efficiency
Full text linkHealth service, Manpower planning, Optimization,
Comparing metaheuristic algorithms for Sonet network design problems
Full text linkThis paper considers two problems that arise in the design of optical telecommunication networks when a ring-based topology is adopted, namely the SONET Ring Assignment Problem and the Intraring Synchronous Optical Network Design Problem. We show that these two network topology problems correspond to graph partitioning problems with capacity constraints: the first is a vertex partitioning problem, while the latter is an edge partitioning problem. We consider solution methods for both problems, based on metaheuristic algorithms. We first describe variable objective functions that depend on the transition from one solution to a neighboring one, then we apply several diversification and intensification techniques including Path Relinking, eXploring Tabu Search and Scatter Search. Finally we propose a diversification method based on the use of multiple neighborhoods. A set of extensive computational results is used to compare the behaviour of the proposed methods and objective functions
Optimal Operations Management and Network Planning of a District Heating System with a Combined Heat and Power Plant
Full text linkDistrict heating plants are becoming more common in European cities. These systems make it possible to furnish users with warm water while locating the production plants in the outskirts having the double benefit of lowering the impact of pollution on the center of the city and achieving better conversion performances. In order to amortize the costs throughout the year, the system often includes a combined heat and power (CHP) plant, to exploit the energy during the summer as well, when the demand for warm water decreases. A linear programming model for the optimal resource management of such a plant is presented and some results for a real case are reported. A distribution network design problem is also addressed and solved by means of mixed integer linear programming
Tabu search vs. GRASP for the maximum diversity problem
Full text linkThe Maximum Diversity Problem (MDP) consists in determining a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise distances between the elements of M is maximum. This problem, introduced by Glover [6], has been deeply studied using GRASP methodologies [5, 1, 13, 2]. GRASP is often characterized by a strong design effort dedicated to build high quality randomized starting solutions, while the subsequent improvement phase is usually performed by a standard local search technique. The purpose of this paper is to explore a somewhat opposite approach, that is to refine the local search phase, by adopting Tabu Search methodologies, while keeping a very simple initialization procedure. Extensive computational results show that Tabu Search achieves both better results and much shorter computational times with respect to those reported for GRASP
- …
