1,721,054 research outputs found
A Dual Ascent Approach to the Bounded-Degree Spanning Tree Problem
No full textGiven a connected graph G a vertex is said to be of the branch type if its
degree is greater than 2. We consider the problem of nding a spanning
tree of G which minimizes the number of branch vertices. Such a problem
has been proved to be NP-complete, and some efcient heuristics
to solve it have been proposed in the literature. In the paper we present
a new heuristic algorithm based on solving the Lagrangean dual of the
original mixed integer programming problem by means of a dual ascent
procedure requiring update of one multiplier at a time
Exact and Heuristic Methods to Maximize Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges
No full textWireless sensor networks involve many dierent real-world contexts, such as monitoring and control tasks for traffic, surveillance, military and environmental applications, among others. Usually, these applications consider the use of a large number of low-cost sensing devices to monitor the activities
occurring in a certain set of target locations. We want to individuate a set of covers (that is, subsets of sensors that can cover the whole set of targets) and appropriate activation times for each of them in order to maximize the total amount of time in which the monitoring activity can be performed (network
lifetime), under the constraint given by the limited power of the battery contained in each sensor. A variant of this problem considers that each sensor can be activated in a certain number of alternative power levels, which determine dierent sensing ranges and power consumptions. We present some heuristic
approaches and an exact approach based on the Column Generation technique. An extensive experimental
phase proves the advantage in terms of solution quality of using adjustable sensing ranges with respect to the classical single range scheme
A branch‐and‐bound algorithm for the double travelling salesman problem with two stacks
No full textThis article studies the double traveling salesman problem with two stacks. A number of requests have to be
served where each request consists in the pickup and
delivery of an item. All the pickup operations have to be
performed before any delivery can take place. A single
vehicle is available that starts from a depot, performs all
the pickup operations and returns to the depot. Then, it
performs all the delivery operations and returns to the
depot. The items are loaded in two stacks, each served
independently from the other with a last-in-first-out policy. The objective is the minimization of the total cost
of the pickup and delivery tours. We propose a branchand-bound approach to solve the problem. The algorithm
uses properties of the problem both to tighten the lower
bounds and to avoid the exploration of redundant subtrees. Computational results performed on benchmark
instances reveal that the algorithm outperforms the other
exact approaches for this problem
Maximizing Lifetime and Handling Reliability in Wireless Sensor Networks Using Adjustable Sensing Ranges
No full textWireless sensor networks are generally characterized by a large number of small sensing devices (sensors), randomly disposed all over the region of interest in order to perform a monitoring activity on a set of target points. To maximize the total coverage time during which all the target are simultaneously monitored (i.e., the network lifetime) sensors can be opportunely scheduled by switching them between on and off mode so that the limited battery power is efficiently used. In this paper, we propose a methodology to prevent sensor failure that results in a shortage of network lifetime only when a sensor effectively fails. Indeed, when a sensor fails, the monitoring radii of the other sensors in the cover can be opportunely enlarged to maintain coverage of the entire set of targets. In this way, each target can be ‘potentially’ k-covered, but network lifetime would be affected only if a sensor effectively fails. In this paper we address the problem of maximizing network lifetime by potentially ensuring k-coverage of the targets by means of adjustable sensing radii. Our preliminary analysis and results will be presented
A cluster-lightening route reduction strategy for the vehicle routing problem with time windows
No full textAn Additive Branch-and-Bound Algorithm for the Pickup and Delivery Traveling Salesman Problem with LIFO or FIFO Loading
No full textThis paper introduces an additive branch-and-bound algorithm for two variants of the pickup and delivery traveling salesman problem in which loading and unloading operations have to be performed either in a Last-In-First-Out (LIFO) or in a First-In-First-Out (FIFO) order. Two relaxations are used within the additive approach: the assignment problem and the shortest spanning r-arborescence problem. The quality of the lower bounds is further improved by a set of elimination rules applied at each node of the search tree to remove from the problem arcs that cannot belong to feasible solutions because of precedence relationships. The performance of the algorithm and the effectiveness of the elimination rules are assessed on instances from the literature
Efficient preflow push algorithms
No full textAlgorithms for the maximum flow problem can be grouped into two categories: augmenting path algorithms [Ford LR, Fulkerson DR. Flows in networks. Princeton University Press: Princeton, NJ: 1962], and preflow push algorithms [GoldbergAV, Tarjan RE.A new approach to the maximum flow problem. In: Proceedings of the 18th annual ACM symposium on theory of computing, 1986; p. 136–46]. Preflow push algorithms are characterized by a drawback known as ping pong effect. In this paper we present a technique that allows to avoid such an effect and can be considered as an approach combining the augmenting path and preflow push methods. An extended experimentation shows the effectiveness of the proposed approach
Bounded-degree spanning tree problems: models and new algorithms
No full textGiven a connected graph G, a vertex v of G is said to be a branch vertex if its degree is greater than 2.We consider two problems arising in the context of optical networks:
(i) Finding a spanning tree of G with the minimum number of branch vertices and
(ii) Finding a spanning tree of G such that the degree sum of the branch vertices is minimized.
For these NP-hard problems, heuristics, that give good quality solutions, do not exist in the literature. In this paper we analyze the relation between the problems, provide a single commodity flow formulation to solve the problems by means of a solver and develop different heuristic strategies to compute feasible solutions that are
compared with the exact ones. Our extensive computational results show the algorithms to be very fast and effective
- …
