On self-organizing maps for orienteering problems
Jan Faigl · 2017
This paper concerns principles of unsupervised learning of self-organizing maps (SOMs) to address optimization routing problems called the Orienteering Problem (OP) and its multi-vehicle variant called the Team Orienteering Problem (TOP). The problems are similar to the traveling salesman problem in finding an optimal tour to visit all the given locations, but here, each location has specified reward that can be collected by the tour and the problem is to select the most valuable subset of the locations that can be visited within the travel budget. In existing SOM for the OP, the locations to be visited are duplicated to adapt the network to locations with higher rewards more frequently. The proposed novel SOM-based solution overcomes this necessity and based on the presented results it significantly reduces the computational burden of the adaptation procedure. Besides, the proposed approach improves the quality of solutions and makes SOM competitive to existing heuristics for the OP, but still behind computationally expensive metaheuristics for the TOP. On the other hand, the main benefit of the SOM-based approaches over the existing heuristics is in solving the generalized variant of the OP and TOP with neighborhoods. These variants of the problem formulation allow to better utilize the travel budget for instances where the reward associated with the location can be collected by visiting a particular neighborhood of the location and not exactly the location itself. This generalized problem formulation better models situations of the robotic data collection, e.g., using wireless communication or range sensors.