A Graph Attention Model for the Team Orienteering Problem
摘要
The Team Orienteering Problem (TOP) is a combinatorial optimization problem where the objective is to determine a set of routes that maximizes the profit earned from visiting customers without exceeding a travel cost or time limit. Recent advancements have shown that combining machine learning approaches with optimization techniques can effectively tackle complex combinatorial problems. In this paper, we introduce two deep reinforcement learning methods to solve the TOP. The first framework is a Hybrid Graph Attention Model (HGAM) that integrates a deep learning neural network with dynamic programming algorithm (optimal splitting). The algorithm operates in two steps: first, a giant tour—a sequence of customers or locations—is generated using a deep neural network; second, this tour is evaluated through an optimal splitting algorithm. The second framework is a full-learning approach based on sampling decoding and mask mechanism to generate a feasible routes. Our experimental results demonstrate that HGAM not only outperforms a full-learning approach but also provides significantly faster results, at the cost of lower solution quality compared to specialized heuristics designed for the TOP.