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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Graph Attention Model for the Team Orienteering Problem

  • Ivan Guillermo Peña-Arenas,
  • Rym Nesrine Guibadj,
  • Cyril Fonlupt,
  • Sohaib Afifi

摘要

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.