1,720,979 research outputs found
A biased random-key genetic algorithm for the set orienteering problem
Full text linkThis paper addresses the Set Orienteering Problem which is a generalization of the Orienteering Problem where the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster. The problem consists of finding a tour that maximizes the collected profit but, since the cost of the tour is limited by a threshold, only a subset of clusters can usually be visited. We propose a Biased Random-Key Genetic Algorithm for solving the Set Orienteering Problem in which three local search procedures are applied to improve the fitness of the chromosomes. In addition, we introduced three rules useful to reduce the size of the instances and to speed up the resolution of the problem. Finally, a hashtable is used to quickly retrieve the information that are required several times during the computation. The computational results, carried out on benchmark instances, show that our algorithm is significantly faster than the other algorithms, proposed in the literature, and it provides solutions very close to the best-known ones
Optimization of sensor battery charging to maximize lifetime in a wireless sensors network
No full textThe maximum network lifetime is a well known and studied optimization problem. The aim is to appropriately schedule the activation intervals of the individual sensing devices composing a wireless sensor network used for monitoring purposes, in order to keep the network operational for the longest period of time (network lifetime). In this work, we extend this problem by taking into account the issue of charging the sensor batteries. More specifically, it has to be decided how much charge should be provided to each sensor, given the existence of a charging device with limited energy availability. An exact column generation algorithm embedding a genetic algorithm for the subproblem is proposed. Computational results reveal that by appropriately choosing the charge levels, remarkable network lifetime improvements can be obtained, in particular when the available energy is scarce
A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs
No full textThis article addresses the minimum spanning tree problem with conflicting edge pairs, a variant of the classical minimum spanning tree where, given a list of conflicting edges, the goal is to find the cheapest spanning tree with no edges in conflict. We adopt a Lagrangian relaxation approach together with a dual ascent and a subgradient procedure to find tight lower bounds on the optimal solution. The algorithm is also equipped with a heuristics approach which provides an upper bound by removing the conflicts from possible infeasible solutions met during the calculation of the lower bounds. The computational results, carried out on benchmark instances, show that the proposed algorithm finds the optimal solutions on several instances. Moreover, the lower bounds it provides are much more accurate than ones provided by other Lagrangian approaches available in the literature and they are computed is much less time
Hybridizing Carousel Greedy and Kernel Search: A new approach for the maximum flow problem with conflict constraints
No full textThis work addresses a variant of the maximum flow problem where specific pairs of arcs are not allowed to carry positive flow simultaneously.
Such restrictions are known in the literature as \textit{negative disjunctive constraints} or \textit{conflict constraints}.
The problem is known to be strongly NP-hard and several exact approaches have been proposed in the literature.
In this paper, we present a heuristic algorithm for the problem, based on two different approaches: Carousel Greedy and Kernel Search. These two approaches are merged to obtain a fast and effective matheuristic, named Kernousel. In particular, the computational results reveal that exploiting the information gathered by the Carousel Greedy to build the set of most promising variables (the \textit{kernel set}), makes the Kernel Search more effective. To validate the performance of the new hybrid method, we compare it with the two components running individually. Results are also evaluated against the best-known solutions available in the literature for the problem. The new hybrid method provides 15 new best-known values on benchmark instances
The constrained forward shortest path tour problem: Mathematical modeling and GRASP approximate solutions
No full textThis paper deals with the Constrained Forward Shortest Path Tour Problem, an NP-complete variant of the Forward Shortest Path Tour Problem. Given a directed weighted graph G = (V, A), where the set of nodes V is partitioned into clusters T1, ..., TN, the aim is determining a shortest path between two given nodes, s and d, with the properties that clusters must be visited according to a given order, and each arc can be crossed at most once. We introduce a mathematical formulation of the problem, and a reduction procedure to reduce the number of variables involved in the model. Furthermore, we propose a Greedy Randomized Adaptive Search Procedure (GRASP) algorithm to solve large instances of the problem. Computational tests show that the reduction procedure is very effective and its application significantly speeds up the resolution of the model. Moreover, the computational results certify the effectiveness of GRASP that often finds the optimal solution and, in general, provides quickly high-quality sub-optimal solutions
Hybridizing Carousel Greedy and Kernel Search: A new approach for the maximum flow problem with conflict constraints
No full textThis work addresses a variant of the maximum flow problem where specific pairs of arcs are not allowed to carry positive flow simultaneously. Such restrictions are known in the literature as negative disjunctive constraints or conflict constraints. The problem is known to be strongly NP-hard and several exact approaches have been proposed in the literature. In this paper, we present a heuristic algorithm for the problem, based on two different approaches: Carousel Greedy and Kernel Search. These two approaches are merged to obtain a fast and effective matheuristic, named Kernousel. In particular, the computational results reveal that exploiting the information gathered by the Carousel Greedy to build the set of most promising variables (the kernel set ), makes the Kernel Search more effective. To validate the performance of the new hybrid method, we compare it with the two components running individually. Results are also evaluated against the best-known solutions available in the literature for the problem. The new hybrid method provides 15 new best-known values on benchmark instances
A genetic approach for the 2-edge-connected minimum branch vertices problem
No full textThis article addresses the 2-edge-connected minimum branch vertices problem, a variant of the minimum branch vertices problem in which the spanning subgraph is required to be 2-edge-connected for survivability reasons. The problem has been recently introduced and finds application in optical networks design scenarios, where branch vertices are associated to switch devices that allow to split the entering light signals and send them to several adjacent vertices. An exact approach to the problem has been proposed in the literature. In this paper, we formally prove its NP-completeness and propose a genetic algorithm, which exploits some literature-provided procedures for efficiently checking and restoring solutions feasibility, and makes use of novel ad-hoc designed operators aiming to improve their values, reducing the number of branch vertices. The computational tests show that, on the benchmark instances, the genetic algorithm very often finds the optimal solution. Moreover, in order to further investigate the effectiveness and the performance of our algorithm, we generated a new set of random instances where the optimal solution is known a priori
Artificial neural network for technical feasibility prediction of seismic retrofitting in existing RC structures
No full textThe seismic analysis of reinforced concrete (RC) structures generally requires significant computational effort, which can be challenging or at least time-consuming also for the modern computing systems. Particularly, huge computational effort is required for running optimisation procedures intended at selecting the “best” retrofitting solution among the wide set of technical feasible ones. Therefore, this paper proposes the use of Machine Learning instead of the mechanistic analyses executed as part of an optimisation procedure for seismic retrofitting of RC existing structures recently proposed by the authors. Specifically, an Artificial Neural Network is trained and employed as a possible substitute of finite element analysis for a rapid and accurate assessment of the relevant performance exhibited by the enhanced configurations of an RC existing building typology. The obtained results demonstrate the effectiveness of an artificial neural network as a computational model to approximate a finite element analysis in seismic retrofitting of RC structures by considering several structural configurations. The proposed methodology can be used to speed-up the search of a viable RC strengthening configuration within the whole parametric field of relevance, which can be subsequently refined using more detailed and computationally expensive FE methods
Solving the Set Covering Problem with Conflicts on Sets: A new parallel GRASP
No full textIn this paper, we analyze a new variant of the well-known NP-hard Set Covering Problem, characterized by pairwise conflicts among subsets of items. Two subsets in conflict can belong to a solution provided that a positive penalty is paid. The problem looks for the optimal collection of subsets representing a cover and minimizing the sum of covering and penalty costs. We introduce two integer linear programming formulations and a quadratic one for the problem and provide a parallel GRASP (Greedy Randomized Adaptive Search Procedure) that, during parallel executions of the same basic procedure, shares information among threads. We tailor such a parallel processing to address the specific problem in an innovative way that allows us to prevent redundant computations in different threads, ultimately saving time. To evaluate the performance of our algorithm, we conduct extensive experiments on a large set of new instances obtained by adapting existing instances for the Set Covering Problem. Computational results show that the proposed approach is extremely effective and efficient providing better results than Gurobi (tackling three alternative mathematical formulations of the problem) in less than 1/6 of the computational time
An adaptive heuristic approach to compute upper and lower bounds for the close-enough traveling salesman problem
No full textThis paper addresses the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem, in which the traveler visits a node if it passes through the neighborhood set of that node. We apply an effective strategy to discretize the neighborhoods of the nodes and the carousel greedy algorithm to appropriately select the neighborhoods that, step by step, are added to the partial solution until a feasible solution is generated. Our heuristic, based on these ingredients, is able to compute tight upper and lower bounds on the optimal solution relatively quickly. The computational results, carried out on benchmark instances, show that our heuristic often finds the optimal solution, on the instances where it is known, and in general, the upper bounds are more accurate than those from other algorithms available in the literature. Summary of Contribution: In this paper, we focus on the close-enough traveling salesman problem. This is a problem that has attracted research attention over the last 10 years; it has numerous real-world applications. For instance, consider the task of meter reading for utility companies. Homes and businesses have meters that measure the usage of gas, water, and electricity. Each meter transmits signals that can be read by a meter reader vehicle via radio-frequency identification (RFID) technology if the distance between the meter and the reader is less than r units. Each meter plays the role of a target point and the neighborhood is a disc of radius r centered at each target point. Now, suppose the meter reader vehicle is a drone and the goal is to visit each disc while minimizing the amount of energy expended by the drone. To solve this problem, we develop a metaheuristic approach, called (lb/ub)Alg, which computes both upper and lower bounds on the optimal solution value. This metaheuristic uses an innovative discretization scheme and the Carousel Greedy algorithm to obtain high-quality solutions. On benchmark instances where the optimal solution is known, (lb/ub)Alg obtains this solution 83% of the time. Over the remaining 17% of these instances, the deviation from the optimality is 0.05%, on average. On the instances with the highest overlap ratio, (lb/ub)Alg does especially well
- …
