We address a variant of the Euclidean traveling salesman problem known as the close-enough traveling salesman problem (CETSP), where the traveler visits a node if it enters a compact neighborhood set of that node. We formulate a mixed-integer programming model based on a discretization scheme for the problem. Both lower and upper bounds on the optimal CETSP tour length can be derived from the solution of this model, and the quality of the bounds obtained depends on the granularity of the discretization scheme. Our approach first develops valid inequalities that enhance the bound and solvability of this formulation. We then provide two alternative formulations, one that yields an improved lower bound on the optimal CETSP tour length, and one that greatly improves the solvability of the original formulation by recasting it as a two-stage problem amenable to decomposition. Computational results demonstrate the effectiveness of the proposed methods.

We propose an algorithm for maximizing the lifetime of a wireless sensor network when there is a mobile sink and the underlying application can tolerate some amount of delay in delivering the data to the sink. The algorithm is distributed, and in addition, mostly uses local information. Such an algorithm can be implemented by parallel and/or distributed execution and the overhead of message passing is low. It is also possible to embed the algorithm into a network protocol so that the sensor nodes and the sink can run it directly as part of the network operation. We give a proof of the algorithm's optimality and the boundedness of the queue sizes, both in the long-run average sense. The proof is based on analyzing a Lyapunov drift.