Boosting graph search with attention network for solving the general orienteering problem

Abstract

Recently, several studies explore to use neural networks(NNs) to solve different routing problems, which is an auspicious direction. These studies usually design an encoder–decoder based framework that uses encoder embeddings of nodes and the problem-specific context to iteratively generate node sequence(path), and further optimize the produced result on top, such as a beam search. However, these models are limited to accepting only the coordinates of nodes as input, disregarding the self-referential nature of the studied routing problems, and failing to account for the low reliability of node selection in the initial stages, thereby posing challenges for real-world applications.In this paper, we take the orienteering problem as an example to tackle these limitations in the previous studies. We propose a novel combination of a variant beam search algorithm and a learned heuristic for solving the general orienteering problem. We acquire the heuristic with an attention network that takes the distances among nodes as input, and learn it via a reinforcement learning framework. The empirical studies show that our method can surpass a wide range of baselines and achieve results iteratively generate the optimal or highly specialized approach.

Keywords

• Orienteering problem
• Beam search
• Attention mechanism