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

Date Published: April 17, 2019

Publisher: Public Library of Science

Author(s): Kun Miao, Hailan Duan, Feng Qian, Ye Dong, Chi-Tsun Cheng.


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).

Partial Text

Wireless sensor networks (WSNs) consist of small nodes with sensing, computation, and wireless communications capabilities that are randomly assigned in monitoring areas. One of the fundamental services provided by WSNs is the monitoring of a specified region of interest. Currently, WSNs are widely used in traffic monitoring, sea resource reconnaissance, military applications, etc. [1]. However, sensors often fail randomly at run time for various reasons such as power depletion or hardware defects, creating unmonitored locations in the given environment. Such locations are often referred to as sensing holes. In order to fill these sensing holes, redundant sensors or previously deployed sensors [2] need to be moved to a particular location, a process that is called sensor relocation [3].

In the process of solving for the shortest trajectory, we first look for a Hamiltonian cycle connecting all the sensor holes. This process is called the first stage. Only by finding a correct Hamiltonian cycle can we lay the foundation for the second stage and find the optimal path of the robot.

In the carrier-based coverage repair problem in wireless sensor and robot networks, passive sensors are pickup customers, and sensing holes are delivery customers. In the following, a “passive sensor” is represented by “p-node,” and a “sensing hole” is represented by “d-node.”

The key to obtaining an optimal path is to build the P-path (CEL). A complete CEL is a feasible solution. N feasible solutions are obtained with N running times, in which the shortest one is regarded as the best path.

The benchmark instances are from the literature [13]. The depot is placed at (0, 0), and the node property of this node is q0=0. Random 2D coordinates for n-1 sensors were generated in the square -500,5002 (n is the total number of nodes). The proportion of delivery nodes and pickup nodes was set at exactly 1:3, and the mobile robot capacity was set as only a quarter of the total number of sensing holes. The travel cost xij was the Euclidean distance between node i and node j.

We extended the carrier-based coverage repair problem in wireless sensor and robot networks proposed by Falcon et al. [13] to the application scenario of large-scale sensor replacement. In order to adapt to this large-scale problem, the mature, excellent LKH algorithm is used in the first stage to obtain the optimal LKH cycle to connect damaged sensors. Then, in the second stage, ellipse sets and the CEL are designed as candidate sets for selecting edges and nodes. Further, expansion, extension‚ and constriction on the edges are proposed to update the CEL with the guidance of the LKH cycle. In comparison with the other two algorithms, the proposed two-stage method reduces the computational time significantly, and the experimental results with 400 and 500 sensors show that the optimization results are much better than those obtained with the compared algorithms.




Leave a Reply

Your email address will not be published.