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

Kun Miao
Kun Miao
Roche Innovation Center Shanghai
Feng Qian
Feng Qian
School of Pharmaceutical Sciences and Collaborative Innovation Center for Diagnosis and Treatment of Infectious Diseases
United States
Ye Dong
Ye Dong
Affiliated Cancer Hospital of Guangzhou Medical University

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

Download full-text PDF


Still can't find the full text of the article?

We can help you send a request to the authors directly.
April 2019
11 Reads

Publication Analysis

Top Keywords

traveling salesman
salesman problem
delivery nodes
one-commodity pickup-and-delivery
second stage
pickup-and-delivery traveling
selecting pickup
experimental proposed
lin-kernighan-helsgaun lkh
lkh algorithm
mature effective
cel experimental
stage mature
proposed method
effective lin-kernighan-helsgaun
cycle delivery
nodes regarded
constriction-are applied
applied cel


(Supplied by CrossRef)
Sensor Relocation in Mobile Sensor Networks
G Wang et al.
Proc of IEEE Infocom 2005
A Comprehensive Review of Sensor Relocation
W Shi et al.
Hangzhou: IEEE 2011
Dynamic Coverage of Mobile Sensor Networks
B Liu et al.
IEEE Transactions On Parallel and Distributed Systems 2013
Localized Movement-Assisted Sensor Deployment Algorithm for Hole Detection and Healing
M R Senouci et al.
IEEE Transactions On Parallel and Distributed Systems 2014
Enhanced Delegation Forwarding in Delay Tolerant Networks
X Chen et al.
International Journal of Parallel Emergent & Distributed Systems 2011
An Energy-Efficient Hole-Healing Mechanism for Wireless Sensor Networks with Obstacles
C Y Chang et al.
Wireless Communications & Mobile Computing 2013
Planning Robust Sensor Relocation Trajectories for a Mobile Robot with Evolutionary Multi-Objective Optimization
B Desjardins et al.
Computational Intelligence in Wireless Sensor Networks 2017
Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication
A Nayak et al.
Wiley-Interscience 2010

Similar Publications