A one-commodity pickup-and-delivery traveling salesman problem solved by a two-stage method: A sensor relocation application

In the carrier-based coverage repair problem, a single mobile robot replaces damaged sensors by picking up spare ones in the region of interest or carrying them from a base station in wireless sensor and robot networks. The objective is to find the shortest path of the robot. The problem is an extension of the traveling salesman problem (TSP). Thus, it is also called the one-commodity traveling salesman problem with selective pickup and delivery (1-TSP-SELPD). In order to solve this problem in a larger sensor distribution scenario more efficiently, we propose a two-stage approach in this paper. In the first stage, the mature and effective Lin–Kernighan–Helsgaun (LKH) algorithm is used to form a Hamiltonian cycle for all delivery nodes, which is regarded as a heuristic for the second stage. In the second stage, elliptical regions are set for selecting pickup nodes‚ and an edge-ordered list (candidate edge list, CEL) is constructed to provide major axes for the ellipses. The process of selecting pickup nodes and constructing the CEL is repeated until all the delivery nodes are visited. The final CEL stores a feasible solution. To update it, three operations—expansion, extension, and constriction—are applied to the CEL. The experimental results show that the proposed method reduces the computing time and achieves better results in higher-dimensional problems, which may facilitate the provision of solutions for more complicated sensor networks and can contribute to the development of effective and efficient algorithms for the one-commodity pickup-and-delivery traveling salesman problem (1-PDTSP).