Feng Qian School of Pharmaceutical Sciences and Collaborative Innovation Center for Diagnosis and Treatment of Infectious Diseases United States
Ye Dong Affiliated Cancer Hospital of Guangzhou Medical University China
PLoS One 2019 17;14(4):e0215107. Epub 2019 Apr 17.
School of Civil Engineering, Central South University, Changsha, Hunan, China.
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).
We have submitted your request - we will update you on status within the next 48 hours.
Sign up for further access to Scientific Publications and Authors!
What are PubFacts Points?
PubFacts points are rewards to PubFacts members, which allow you to better promote your profile and articles throughout PubFacts.com
How do I earn PubFacts Points?
Each member is given 50 PubFacts points upon signing up. You can earn additional points by completing 100% of your profile, creating and participating in discussions, and sharing other members research.
What can I do with PubFacts Points?
Currently, you can use PubFacts Points to promote and increase readership of your articles.