Self-organizing map-based solution for the Orienteering problem with neighborhoods
Self-organizing map-based solution for the Orienteering problem with neighborhoods
复制标题
基于自组织地图的邻里定向问题解决方案
DOI：
10.1109/smc.2016.7844421
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Graeme Best
中科院分区：
文献类型：
--
作者：
J. Faigl;Robert Pěnička;Graeme Best
利用自组织映射(SOM)的无监督学习方法解决定向问题(OP)。提出了一种基于SOM的旅行商问题(TSP)的新算法来解决该问题。这两个问题在寻找访问给定地点的旅行团时是相似的；然而，操作员需要确定最有价值的旅行团，该旅行团通过访问某个地点的子集来最大化所获得的回报，同时将旅行长度保持在指定的旅行预算之内。该随机搜索算法基于SOM的无监督学习，在每个学习阶段构造一个可行解。报道的结果支持了提出的想法的可行性，并表明该算法的性能与现有的启发式算法具有竞争力。此外，提出的基于SOM的方法的关键优势是能够解决与邻居的广义OP，其中可以通过在位置附近的任何地方旅行来获得奖励。这一问题的泛化更适合使用无线数据传输的数据收集任务，并允许节省访问给定位置的不必要的旅行成本。
In this paper, we address the Orienteering problem (OP) by the unsupervised learning of the self-organizing map (SOM). We propose to solve the OP with a new algorithm based on SOM for the Traveling salesman problem (TSP). Both problems are similar in finding a tour visiting the given locations; however, the OP stands to determine the most valuable tour that maximizes the rewards collected by visiting a subset of the locations while keeping the tour length under the specified travel budget. The proposed stochastic search algorithm is based on unsupervised learning of SOM and it constructs a feasible solution during each learning epoch. The reported results support feasibility of the proposed idea and show the performance is competitive with existing heuristics. Moreover, the key advantage of the proposed SOM-based approach is the ability to address the generalized OP with Neighborhoods, where rewards can be collected by traveling anywhere within the neighborhood of the locations. This problem generalization better fits data collection missions with wireless data transmission and it allows to save unnecessary travel costs to visit the given locations.