School of Civil Engineering, Central South University, Changsha, Hunan, China.
PLoS One. 2019 Apr 17;14(4):e0215107. doi: 10.1371/journal.pone.0215107. eCollection 2019.
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).
在基于载体的覆盖修复问题中，单个移动机器人通过在感兴趣区域中捡起备用传感器或从无线传感器和机器人网络中的基站携带它们来替换损坏的传感器。目标是找到机器人的最短路径。该问题是旅行商问题 (TSP) 的扩展。因此，它也被称为带选择性取货和送货的单商品旅行商问题 (1-TSP-SELPD)。为了在更大的传感器分布场景中更有效地解决这个问题，我们在本文中提出了一种两阶段方法。在第一阶段，使用成熟有效的 Lin-Kernighan-Helsgaun (LKH) 算法为所有送货节点形成哈密顿回路，这被视为第二阶段的启发式算法。在第二阶段，为选择取货节点设置椭圆区域，并构建边缘有序列表（候选边列表，CEL）为椭圆提供主轴。选择取货节点和构建 CEL 的过程重复进行，直到访问完所有送货节点。最终的 CEL 存储可行解。为了更新它，CEL 应用了三种操作——扩展、延伸和收缩。实验结果表明，该方法减少了计算时间，并在高维问题中取得了更好的结果，这可能有助于为更复杂的传感器网络提供解决方案，并为单商品取货和送货旅行商问题 (1-PDTSP) 开发有效和高效的算法做出贡献。
